remove unnecessary assertion for unknown phdr_type (#757)
[dyninst.git] / parseAPI / src / IndirectAnalyzer.C
1 #include "dyntypes.h"
2 #include "IndirectAnalyzer.h"
3 #include "BoundFactCalculator.h"
4 #include "JumpTableFormatPred.h"
5 #include "JumpTableIndexPred.h"
6 #include "SymbolicExpression.h"
7 #include "IndirectASTVisitor.h"
8 #include "IA_IAPI.h"
9 #include "debug_parse.h"
10
11 #include "CodeObject.h"
12 #include "Graph.h"
13
14 #include "Instruction.h"
15 #include "InstructionDecoder.h"
16 #include "Register.h"
17 #include "SymEval.h"
18 using namespace Dyninst::ParseAPI;
19 using namespace Dyninst::InstructionAPI;
20
21 static bool IsIndexing(AST::Ptr node, AbsRegion &index) {
22     RoseAST::Ptr n = boost::static_pointer_cast<RoseAST>(node);
23     if (n->val().op != ROSEOperation::sMultOp &&
24         n->val().op != ROSEOperation::uMultOp &&
25         n->val().op != ROSEOperation::shiftLOp &&
26         n->val().op != ROSEOperation::rotateLOp) return false;
27     if (n->child(0)->getID() != AST::V_VariableAST) return false;
28     if (n->child(1)->getID() != AST::V_ConstantAST) return false;
29     VariableAST::Ptr var = boost::static_pointer_cast<VariableAST>(n->child(0));
30     index = var->val().reg;
31     return true;
32 }
33
34 static bool IsVariableArgumentFormat(AST::Ptr t, AbsRegion &index) {
35     if (t->getID() != AST::V_RoseAST) {
36         return false;
37     }
38     RoseAST::Ptr rt = boost::static_pointer_cast<RoseAST>(t);
39     if (rt->val().op != ROSEOperation::addOp) {
40         return false;
41     }
42     if (rt->child(0)->getID() != AST::V_ConstantAST || rt->child(1)->getID() != AST::V_RoseAST) {
43         return false;
44     }
45     RoseAST::Ptr c1 = boost::static_pointer_cast<RoseAST>(rt->child(1));
46     if (c1->val().op == ROSEOperation::addOp) {
47         if (c1->child(0)->getID() == AST::V_RoseAST && c1->child(1)->getID() == AST::V_ConstantAST) {
48             RoseAST::Ptr lc = boost::static_pointer_cast<RoseAST>(c1->child(0));
49             ConstantAST::Ptr rc = boost::static_pointer_cast<ConstantAST>(c1->child(1));
50             if (lc->val().op == ROSEOperation::invertOp && rc->val().val == 1) {
51                 return IsIndexing(lc->child(0), index);
52             }
53         }
54         return false;
55     }
56     return IsIndexing(rt->child(1), index);
57
58 }
59
60 bool IndirectControlFlowAnalyzer::NewJumpTableAnalysis(std::vector<std::pair< Address, Dyninst::ParseAPI::EdgeTypeEnum > >& outEdges) {
61     parsing_printf("Apply indirect control flow analysis at %lx for function %s\n", block->last(), func->name().c_str());
62     parsing_printf("Looking for thunk\n");
63 boost::make_lock_guard(*func);
64 //  Find all blocks that reach the block containing the indirect jump
65 //  This is a prerequisit for finding thunks
66     GetAllReachableBlock();
67 //  Now we try to find all thunks in this function.
68 //  We pass in the slice because we may need to add new ndoes.
69     FindAllThunks();
70 //  Calculates all blocks that can reach
71 //  and be reachable from thunk blocks
72     ReachFact rf(thunks);
73
74     // Now we start with the indirect jump instruction,
75     // to determine the format of the (potential) jump table
76     const unsigned char * buf = (const unsigned char*) block->region()->getPtrToInstruction(block->last());
77     InstructionDecoder dec(buf, InstructionDecoder::maxInstructionLength, block->obj()->cs()->getArch());
78     Instruction insn = dec.decode();
79     AssignmentConverter ac(true, false);
80     vector<Assignment::Ptr> assignments;
81     ac.convert(insn, block->last(), func, block, assignments);
82     Slicer formatSlicer(assignments[0], block, func, false, false);
83
84     SymbolicExpression se;
85     se.cs = block->obj()->cs();
86     se.cr = block->region();
87     JumpTableFormatPred jtfp(func, block, rf, thunks, se);
88     GraphPtr slice = formatSlicer.backwardSlice(jtfp);
89     //parsing_printf("\tJump table format: %s\n", jtfp.format().c_str());
90     // If the jump target expression is not in a form we recognize,
91     // we do not try to resolve it
92     parsing_printf("In function %s, Address %lx, jump target format %s, index loc %s, index variable %s, memory read loc %s, isJumpTableFormat %d\n", 
93             func->name().c_str(), 
94             block->last(), 
95             jtfp.format().c_str(), 
96             jtfp.indexLoc ? jtfp.indexLoc->format().c_str() : "null" , 
97             jtfp.index.format().c_str(),
98             jtfp.memLoc ? jtfp.memLoc->format().c_str() : "null",
99             jtfp.isJumpTableFormat());
100
101     bool variableArguFormat = false;
102     if (!jtfp.isJumpTableFormat()) {
103         if (jtfp.jumpTargetExpr && func->entry() == block && IsVariableArgumentFormat(jtfp.jumpTargetExpr, jtfp.index)) {
104             parsing_printf("\tVariable number of arguments format, index %s\n", jtfp.index.format().c_str());
105             variableArguFormat = true;
106         } else {
107             return false;
108         }
109     }
110
111     StridedInterval b;
112     bool scanTable = false;
113     if (!variableArguFormat) {
114         Slicer indexSlicer(jtfp.indexLoc, jtfp.indexLoc->block(), func, false, false);
115         JumpTableIndexPred jtip(func, block, jtfp.index, se);
116         jtip.setSearchForControlFlowDep(true);
117         slice = indexSlicer.backwardSlice(jtip);
118
119         if (!jtip.findBound && block->obj()->cs()->getArch() != Arch_aarch64) {
120
121             // After the slicing is done, we do one last check to
122             // see if we can resolve the indirect jump by assuming
123             // one byte read is in bound [0,255]
124             GraphPtr g = jtip.BuildAnalysisGraph(indexSlicer.visitedEdges);
125             BoundFactsCalculator bfc(func, g, func->entry() == block,  true, se);
126             bfc.CalculateBoundedFacts();
127         
128             StridedInterval target;
129             jtip.IsIndexBounded(g, bfc, target);
130         }
131         if (jtip.findBound) {
132             parsing_printf(" find bound %s for %lx\n", jtip.bound.format().c_str(), block->last());
133             b = jtip.bound;
134         } else {
135             parsing_printf(" Cannot find bound, assume there are at most 256 entries and scan the table for indirect jump at %lx\n", block->last());
136             b = StridedInterval(1, 0, 255);
137             scanTable = true;
138         }
139     } else {
140         b = StridedInterval(1, 0, 8);
141     }
142     std::vector<std::pair< Address, Dyninst::ParseAPI::EdgeTypeEnum > > jumpTableOutEdges;
143
144     Function::JumpTableInstance inst;
145     inst.jumpTargetExpr = jtfp.jumpTargetExpr;
146     inst.memoryReadSize = GetMemoryReadSize(jtfp.memLoc);
147     inst.isZeroExtend = IsZeroExtend(jtfp.memLoc);
148     inst.tableStart = inst.tableEnd = 0;
149     inst.indexStride = 0;
150     inst.block = block;
151     ReadTable(jtfp.jumpTargetExpr,
152               jtfp.index,
153               b,
154               inst.memoryReadSize,
155               inst.isZeroExtend,
156               scanTable,
157               jtfp.constAddr,
158               jumpTableOutEdges,
159               inst.tableStart,
160               inst.tableEnd,
161               inst.indexStride,
162               inst.tableEntryMap);
163
164     inst.tableEnd += inst.indexStride;
165     if (jumpTableOutEdges.size() > 0 && inst.indexStride > 0)
166         func->getJumpTables()[block->last()] = inst;
167
168     parsing_printf(", find %d edges\n", jumpTableOutEdges.size());
169     outEdges.insert(outEdges.end(), jumpTableOutEdges.begin(), jumpTableOutEdges.end());
170     return !jumpTableOutEdges.empty();
171 }                                                      
172
173
174
175
176 // Find all blocks that reach the block containing the indirect jump
177 void IndirectControlFlowAnalyzer::GetAllReachableBlock() {
178     reachable.clear();
179     queue<Block*> q;
180     q.push(block);
181     while (!q.empty()) {
182         ParseAPI::Block *cur = q.front();
183         q.pop();
184         if (reachable.find(cur) != reachable.end()) continue;
185         reachable.insert(cur);
186     boost::lock_guard<Block> g(*cur);
187         for (auto eit = cur->sources().begin(); eit != cur->sources().end(); ++eit)
188             if ((*eit)->intraproc()) {
189                 if ((*eit)->src() == NULL) {
190                     fprintf(stderr, "edge type = %d, target block [%lx, %lx)\n", (*eit)->type(), cur->start(), cur->end());
191                 }
192                 q.push((*eit)->src());
193             }
194     }
195
196 }
197
198
199 static Address ThunkAdjustment(Address afterThunk, MachRegister reg, ParseAPI::Block *b) {
200     // After the call to thunk, there is usually
201     // an add insturction like ADD ebx, OFFSET to adjust
202     // the value coming out of thunk.
203    
204     const unsigned char* buf = (const unsigned char*) (b->region()->getPtrToInstruction(afterThunk));
205     InstructionDecoder dec(buf, b->end() - b->start(), b->obj()->cs()->getArch());
206     Instruction nextInsn = dec.decode();
207     // It has to be an add
208     if (nextInsn.getOperation().getID() != e_add) return 0;
209     vector<Operand> operands;
210     nextInsn.getOperands(operands);
211     RegisterAST::Ptr regAST = boost::dynamic_pointer_cast<RegisterAST>(operands[0].getValue());
212     // The first operand should be a register
213     if (regAST == 0) return 0;
214     if (regAST->getID() != reg) return 0;
215     Result res = operands[1].getValue()->eval();
216     // A not defined result means that
217     // the second operand is not an immediate
218     if (!res.defined) return 0;
219     return res.convert<Address>();
220 }
221
222 void IndirectControlFlowAnalyzer::FindAllThunks() {
223     // Enumuerate every block to find thunk
224     for (auto bit = reachable.begin(); bit != reachable.end(); ++bit) {
225         // We intentional treat a getting PC call as a special case that does not
226         // end a basic block. So, we need to check every instruction to find all thunks
227         ParseAPI::Block *b = *bit;
228         const unsigned char* buf =
229             (const unsigned char*)(b->region()->getPtrToInstruction(b->start()));
230         if( buf == NULL ) {
231             parsing_printf("%s[%d]: failed to get pointer to instruction by offset\n",FILE__, __LINE__);
232             return;
233         }
234         InstructionDecoder dec(buf, b->end() - b->start(), b->obj()->cs()->getArch());
235         InsnAdapter::IA_IAPI* block = InsnAdapter::IA_IAPI::makePlatformIA_IAPI(b->obj()->cs()->getArch(), dec, b->start(), b->obj() , b->region(), b->obj()->cs(), b);
236         Address cur = b->start();
237         while (cur < b->end()) {
238             if (block->getInstruction().getCategory() == c_CallInsn && block->isThunk()) {
239                 bool valid;
240                 Address addr;
241                 boost::tie(valid, addr) = block->getCFT();
242                 const unsigned char *target = (const unsigned char *) b->region()->getPtrToInstruction(addr);
243                 InstructionDecoder targetChecker(target, InstructionDecoder::maxInstructionLength, b->obj()->cs()->getArch());
244                 Instruction thunkFirst = targetChecker.decode();
245                 set<RegisterAST::Ptr> thunkTargetRegs;
246                 thunkFirst.getWriteSet(thunkTargetRegs);
247                 
248                 for (auto curReg = thunkTargetRegs.begin(); curReg != thunkTargetRegs.end(); ++curReg) {
249                     ThunkInfo t;
250                     t.reg = (*curReg)->getID();
251                     t.value = block->getAddr() + block->getInstruction().size();
252                     t.value += ThunkAdjustment(t.value, t.reg, b);
253                     t.block = b;
254                     thunks.insert(make_pair(block->getAddr(), t));
255                     parsing_printf("\tfind thunk at %lx, storing value %lx to %s\n", block->getAddr(), t.value , t.reg.name().c_str());
256                 }
257             }
258             cur += block->getInstruction().size();
259             if (cur < b->end()) block->advance();
260         }
261         delete block;
262     }
263 }
264
265 void IndirectControlFlowAnalyzer::ReadTable(AST::Ptr jumpTargetExpr,
266                                             AbsRegion index,
267                                             StridedInterval &indexBound,
268                                             int memoryReadSize,
269                                             bool isZeroExtend,
270                                             bool scanTable,
271                                             set<Address> &constAddr,
272                                             std::vector<std::pair<Address, Dyninst::ParseAPI::EdgeTypeEnum> > &targetEdges,
273                                             Address &minReadAddress,
274                                             Address &maxReadAddress,
275                                             int &indexStride,
276                                             std::map<Address, Address>& entries) {
277     CodeSource *cs = block->obj()->cs();
278     set<Address> jumpTargets;
279     int start = 0;
280     Address prevReadAddress = 0;
281     if (indexBound.low > 0) start = indexBound.low = start;
282     for (int v = start; v <= indexBound.high; v += indexBound.stride) {
283         JumpTableReadVisitor jtrv(index, v, cs, block->region(), isZeroExtend, memoryReadSize);
284         jumpTargetExpr->accept(&jtrv);
285        if (jtrv.valid && cs->isCode(jtrv.targetAddress)) {
286             if (cs->getArch() == Arch_x86_64 && FindJunkInstruction(jtrv.targetAddress)) {
287                 parsing_printf("WARNING: resolving jump tables leads to junk instruction from %lx\n", jtrv.targetAddress);
288                 break;
289             }
290             if (jtrv.readAddress < minReadAddress || minReadAddress == 0) minReadAddress = jtrv.readAddress;
291             if (jtrv.readAddress > maxReadAddress) maxReadAddress = jtrv.readAddress;
292             if (prevReadAddress > 0) indexStride = jtrv.readAddress - prevReadAddress;
293             prevReadAddress = jtrv.readAddress;
294             parsing_printf("\t index %d, table address %lx, target address %lx\n", v, jtrv.readAddress, jtrv.targetAddress);
295             jumpTargets.insert(jtrv.targetAddress);
296             entries[jtrv.readAddress] = jtrv.targetAddress;
297         } else {
298             // We have a bad entry. We stop here, as we have wrong information
299             // In this case, we keep the good entries
300             parsing_printf("WARNING: resolving jump tables leads to a bad address %lx\n", jtrv.targetAddress);
301             break;
302         }
303         if (indexBound.stride == 0) break;
304     }
305     for (auto ait = constAddr.begin(); ait != constAddr.end(); ++ait) {
306         if (block->region()->isCode(*ait)) {
307             jumpTargets.insert(*ait);
308         }
309     }
310     for (auto tit = jumpTargets.begin(); tit != jumpTargets.end(); ++tit) {
311         targetEdges.push_back(make_pair(*tit, INDIRECT));
312     }
313 }
314
315 int IndirectControlFlowAnalyzer::GetMemoryReadSize(Assignment::Ptr memLoc) {
316     if (!memLoc) {
317         parsing_printf("\tmemLoc is null\n");
318         return 0;
319     }
320     Instruction i = memLoc->insn();
321     std::vector<Operand> ops;
322     i.getOperands(ops);
323     parsing_printf("\t there are %d operands\n", ops.size());
324     for (auto oit = ops.begin(); oit != ops.end(); ++oit) {
325         Operand o = *oit;
326         if (o.readsMemory()) {
327             Expression::Ptr exp = o.getValue();
328             return exp->size();
329         }
330     }
331     return 0;
332 }
333
334 bool IndirectControlFlowAnalyzer::IsZeroExtend(Assignment::Ptr memLoc) {
335     if (!memLoc) {
336         parsing_printf("\tmemLoc is null\n");
337         return false;
338     }
339     Instruction i = memLoc->insn();
340     parsing_printf("check zero extend %s\n", i.format().c_str());
341     if (i.format().find("movz") != string::npos) return true;
342     return false;
343 }
344
345 bool IndirectControlFlowAnalyzer::FindJunkInstruction(Address addr) {
346     unsigned size = block->region()->offset() + block->region()->length() - addr; 
347     const unsigned char* buffer = (const unsigned char *)(func->isrc()->getPtrToInstruction(addr));
348     InstructionDecoder dec(buffer,size,block->region()->getArch());
349     Dyninst::InsnAdapter::IA_IAPI* ahPtr = Dyninst::InsnAdapter::IA_IAPI::makePlatformIA_IAPI(func->obj()->cs()->getArch(), dec, addr, func->obj(), block->region(), func->isrc(), NULL);
350
351     while (!ahPtr->hasCFT()) {
352         Instruction i = ahPtr->current_instruction();
353         if (i.getOperation().getID() == e_No_Entry) {
354             return true;
355         }
356         if (i.size() == 2 && i.rawByte(0) == 0x00 && i.rawByte(1) == 0x00) {
357             return true;
358         }
359         ahPtr->advance();
360     }
361     delete ahPtr;
362     return false;
363 }