remove unnecessary assertion for unknown phdr_type (#757)
[dyninst.git] / parseAPI / src / JumpTableFormatPred.C
1 #include "JumpTableFormatPred.h"
2 #include "SymbolicExpression.h"
3 #include "IndirectASTVisitor.h"
4 #include "SymEval.h"
5 #include "CodeObject.h"
6 #include "CodeSource.h"
7 #include "debug_parse.h"
8 using namespace Dyninst;
9 using namespace Dyninst::DataflowAPI;
10 using namespace Dyninst::ParseAPI;
11 using namespace Dyninst::InstructionAPI;
12
13 JumpTableFormatPred::JumpTableFormatPred(ParseAPI::Function *f,
14                                          ParseAPI::Block *b,
15                                          ReachFact &r,
16                                          ThunkData &t,
17                                          SymbolicExpression &sym):
18       func(f), block(b), rf(r), thunks(t), se(sym){
19     jumpTableFormat = true;
20     findIndex = false;
21     findTableBase = false;
22     firstMemoryRead = true;
23     toc_address = 0;
24     if (b->obj()->cs()->getArch() == Arch_ppc64) {
25         FindTOC();
26     }
27 }
28
29 static bool ComputeTOC(Address &ret, Address entry, Block* b) {
30     if (!b->region()->isCode(entry)) return false;
31     const uint32_t * buf = (const uint32_t*) b->region()->getPtrToInstruction(entry);
32     if (buf == NULL) return false;
33
34     uint32_t i1 = buf[0];
35     uint32_t i2 = buf[1];
36
37     uint32_t p1 = i1 >> 16;
38     uint32_t p2 = i2 >> 16;
39
40     // lis and addis treat imm unsigned
41     Address a1 = i1 & 0xffff;
42     // addi treats imm signed
43     Address a2 = i2 & 0xffff;
44     if (a2 & 0x8000) a2 = a2 | SIGNEX_64_16;
45
46     // Check for two types of preamble
47     // Preamble 1: used in executables
48     // lis r2, IMM       bytes: IMM1 IMM2 40 3c 
49     // addi r2, r2, IMM  bytes: IMM1 IMM2 42 38
50     if (p1 == 0x3c40 && p2 == 0x3842) {
51         ret = (a1 << 16) + a2;
52         return true;
53     }
54     
55     // Preamble 2: used in libraries
56     // addis r2, r12, IMM   bytes: IMM1 IMM2 4c 3c
57     // addi r2, r2,IMM      bytes: IMM1 IMM2 42 38
58     if (p1 == 0x3c4c && p2 == 0x3842) {
59         ret = entry + (a1 << 16) + a2;
60         return true;
61     }
62     return false;
63 }
64
65 void JumpTableFormatPred::FindTOC() {
66         // Little endian powerpc changes its ABI, which does not have .opd section, but often load R2 at function entry
67     if (ComputeTOC(toc_address, func->addr(), block) || 
68         ComputeTOC(toc_address, func->addr() - 8, block)) {
69         parsing_printf("\t find TOC address %lx in R2\n", toc_address);
70         return;        
71     }
72     parsing_printf("\tDid not find TOC for function at %lx\n", func->addr());
73 }
74
75 static int CountInDegree(SliceNode::Ptr n) {
76     NodeIterator nbegin, nend; 
77     int count = 0;
78     n->ins(nbegin, nend);
79     for (; nbegin != nend; ++count, ++nbegin);
80     return count;
81 }
82
83 bool JumpTableFormatPred::modifyCurrentFrame(Slicer::SliceFrame &frame, Graph::Ptr g, Slicer* s) {
84     if (!jumpTableFormat) return false;
85
86     /* We start to inspect the current slice graph.
87      * 1. If we have determined the jump table format, we can stop this slice.
88      * 2. If we have determined the index variable, we can remove the variable 
89      *    from the current slice and only keep slicing on other variables.
90      * 3. If we have determined that this is not a known jump table, 
91      *    we also stop slicing.
92      */
93
94     queue<SliceNode::Ptr> working_list;
95     unordered_set<Assignment::Ptr, Assignment::AssignmentPtrHasher> inQueue;
96     NodeIterator nbegin, nend; 
97     
98     bool setFirstMemoryRead = false;
99
100     g->adjustEntryAndExitNodes();
101     // We do not try to slice on the heap absregion,
102     // as it will not help us determine the jump table format.
103     // But we record this memory read, so that later we can determine
104     // whether the size of the read and whether it is zero extended or sign extended
105     for (auto rit = frame.active.begin(); rit != frame.active.end(); ++rit)
106         if (rit->first.type() == Absloc::Heap || rit->first.type() == Absloc::Stack) {
107             // If this is the first memory read we encoutered,
108             // this is likely to be a jump table read and we need to keep
109             // slice on its address.
110             if (firstMemoryRead) {
111                 memLoc = rit->second[0].ptr;
112                 firstMemoryRead = false;
113                 frame.active.erase(rit);
114         setFirstMemoryRead = true;
115             } else {
116                 // For a later memory read, if we have not disqualified this indirect jump,
117                 // it is likely to be a jump table. There are two cases to be handled:
118                 // 1) On ppc, this could be a read from TOC (read from a constant address)
119                 // 2) This memory read is assumed 
120                 // and likely to be a spill for a certain register. We syntactically find the location
121                 // where the memory is written and keep slicing on the source register
122                 SliceNode::Ptr readNode;
123                 parsing_printf("\t\tfind another memory read %s %s\n", rit->first.format().c_str(), rit->second[0].ptr->format().c_str());
124                 if (!findRead(g, readNode)) {
125                     parsing_printf("\tWARNING: a potential memory spill cannot be handled.\n");
126                     jumpTableFormat = false;
127                     return false;
128                 }
129                 if (isTOCRead(frame, readNode)) {
130                     break;
131                 }
132                 // We then do the following things
133                 // 1. delete all absregions introduced by this read node from the active map
134                 // 2. search for the closest instruction that writes the same memory location,
135                 //    through memoery operand ast matching
136                 // 3. change the slicing location and add back the source
137                 if (!adjustSliceFrame(frame, readNode, s)) {
138                     parsing_printf("Cannot track through the memory read\n");
139                     jumpTableFormat = false;
140                     return false;
141                 }
142                 g->deleteNode(readNode);
143                 return true;
144
145             }
146             break;
147         }
148
149
150     g->entryNodes(nbegin, nend);
151
152     // This map trakcs the expanded and substituted ASTs for each assignment in the current slice
153     std::unordered_map<Assignment::Ptr, AST::Ptr, Assignment::AssignmentPtrHasher> exprs;
154     std::unordered_map<Assignment::Ptr, int, Assignment::AssignmentPtrHasher> inDegree;
155     for (; nbegin != nend; ++nbegin) {
156         SliceNode::Ptr n = boost::static_pointer_cast<SliceNode>(*nbegin);
157         working_list.push(n);
158         inQueue.insert(n->assign());
159     }
160     
161     g->allNodes(nbegin, nend);
162     for (; nbegin != nend; ++nbegin) {
163         SliceNode::Ptr n = boost::static_pointer_cast<SliceNode>(*nbegin);
164         inDegree[n->assign()] = CountInDegree(n);
165     }
166     AST::Ptr jumpTarget;
167     while (!working_list.empty()) {
168         SliceNode::Ptr n = working_list.front();
169         working_list.pop();
170         if (!n->assign()) {
171             parsing_printf("\tWARNING: Encountering a slice node with no assignment!\n");
172             continue;
173         }
174         if (exprs.find(n->assign()) != exprs.end()) {
175             parsing_printf("\tWARNING: Jump table format slice contains cycle!\n");
176             jumpTableFormat = false;
177             return false;
178         }
179
180         /* We expand this assignment.
181          * The jump table format should only involve basic instructions
182          * such as mov, arithmetic, loading addresses.
183          * If we encounter an instruction that we do not have semantics,
184          * we should inspect this case.
185          */
186         pair<AST::Ptr, bool> expandRet = se.ExpandAssignment(n->assign(), true);
187         if (!expandRet.second || expandRet.first == NULL) {
188             parsing_printf("\tWARNING: Jump table format slice contains unknown instructions: %s. Stop slicing along the path\n",
189                                            n->assign()->insn().format().c_str());
190         if (setFirstMemoryRead) firstMemoryRead = true;
191         g->deleteNode(n);
192             return false;
193         }
194         if (n->assign()->out().generator() != NULL) {
195             parsing_printf("\tWARNING: Jump table format slice contains writes to memory\n");
196             jumpTableFormat = false;
197             return false;
198         }
199
200         // We make a deep copy of the AST because the AST from ExpandAssignment 
201         // may be used later. So, we do not want to destroy the AST of the assignment
202         AST::Ptr exp = SymbolicExpression::DeepCopyAnAST(expandRet.first);
203         // We start plug in ASTs from predecessors
204         n->ins(nbegin, nend);
205         map<AST::Ptr, AST::Ptr> inputs;
206         map<AST::Ptr, Address> input_addr;
207         if (block->obj()->cs()->getArch() == Arch_ppc64) {
208             inputs.insert(make_pair(VariableAST::create(Variable(AbsRegion(Absloc(ppc64::r2)))),
209                           ConstantAST::create(Constant(toc_address, 64))));
210         }
211         if (aliases.find(n->assign()) != aliases.end()) {
212             inputs.insert(aliases[n->assign()]);
213             parsing_printf("\t Replacing %s with %s\n", aliases[n->assign()].first->format().c_str(),aliases[n->assign()].second->format().c_str());
214             exp = SymbolicExpression::SubstituteAnAST(exp, inputs);
215             inputs.clear();
216         }
217         parsing_printf("JumpTableFormatPred: analyze %s at %lx\n", n->assign()->format().c_str(), n->assign()->addr());
218         for (; nbegin != nend; ++nbegin) {
219             SliceNode::Ptr p = boost::static_pointer_cast<SliceNode>(*nbegin);
220
221             if (exprs.find(p->assign()) == exprs.end()) {
222                 parsing_printf("\tWARNING: For %s, its predecessor %s does not have an expression\n", n->assign()->format().c_str(), p->assign()->format().c_str());
223                 jumpTableFormat = false;
224                 return false;
225             }
226             AST::Ptr rhs = exprs[p->assign()];      
227             AST::Ptr lhs = VariableAST::create(Variable(p->assign()->out())); 
228             bool find = false;
229             for (auto iit = inputs.begin(); iit != inputs.end(); ++iit)
230                 if (*(iit->first) == *lhs) {
231                     find = true;
232                     if (p->assign()->addr() < input_addr[iit->first]) {
233                         inputs[iit->first] = rhs;
234                         input_addr[iit->first] = p->assign()->addr();
235                     }
236                     break;
237                 }
238             if (!find) {
239                 inputs[lhs] = rhs;
240                 input_addr[lhs] = p->assign()->addr();
241             }
242             parsing_printf("\t\t pred %s at %lx, lhs %s, rhs %s\n", p->assign()->format().c_str(), p->assign()->addr(), lhs->format().c_str(), rhs->format().c_str());
243
244         }
245         parsing_printf("Input map:\n");
246         for (auto iit = inputs.begin(); iit != inputs.end(); ++iit) {
247             parsing_printf("\t %s %s\n", iit->first->format().c_str(), iit->second->format().c_str());
248         }
249         if (g->isExitNode(n)) {
250             // Here we try to detect the case where there are multiple
251             // paths to the indirect jump, and on some of the paths, the jump
252             // target has constnt values, and on some other path, the jump target
253             // may have a jump table format
254             int nonConstant = 0;
255             int match = 0;
256             for (auto iit = inputs.begin(); iit != inputs.end(); ++iit) {
257                 AST::Ptr lhs = iit->first;
258                 AST::Ptr rhs = iit->second;
259                 if (*lhs == *exp) {
260                     match++;
261                     if (rhs->getID() == AST::V_ConstantAST) {
262                         ConstantAST::Ptr c = boost::static_pointer_cast<ConstantAST>(rhs);
263                         constAddr.insert(c->val().val);
264                     } else {
265                         nonConstant++;
266                         jumpTarget = rhs;
267                     }
268                 }
269             }
270             if (match == 0) {
271                 // Thiw will happen when the indirect jump directly reads from memory,
272                 // instead of jumping to the value of a register.
273                 exp = SymbolicExpression::SubstituteAnAST(exp, inputs);
274                 jumpTarget = exp;
275                 break;
276             }
277             if (nonConstant > 1) {
278                 parsing_printf("Find %d different jump target formats\n", nonConstant);
279                 jumpTableFormat = false;
280                 return false;
281             } else if (nonConstant == 0) {
282                 parsing_printf("Only constant target values found so far, no need to check jump target format\n");
283                 return true;
284             }
285             break;
286         }
287         // TODO: need to consider thunk
288         exp = SymbolicExpression::SubstituteAnAST(exp, inputs);
289         exprs[n->assign()] = exp;
290         parsing_printf("\t expression %s\n", exp->format().c_str());
291
292         // Enumerate every successor and add them to the working list
293         n->outs(nbegin, nend);
294         for (; nbegin != nend; ++nbegin) {
295             SliceNode::Ptr p = boost::static_pointer_cast<SliceNode>(*nbegin);
296             inDegree[p->assign()] --;
297             if (inDegree[p->assign()] == 0 && inQueue.find(p->assign()) == inQueue.end()) {
298                 inQueue.insert(p->assign());
299                 working_list.push(p);
300             }
301         }
302     }
303     if (!jumpTarget) {
304         parsing_printf("\t Do not find a potential jump target expression\n");
305         jumpTableFormat = false;
306         return false;
307
308     }
309     JumpTableFormatVisitor jtfv(block);
310     assert(jumpTarget);
311     jumpTarget = se.SimplifyAnAST(jumpTarget, 0, true);
312     parsing_printf("Check expression %s\n", jumpTarget->format().c_str());    
313     jumpTarget->accept(&jtfv);
314     if (jtfv.findIncorrectFormat) {
315         jumpTableFormat = false;
316         return false;
317     }
318     
319     if (!findIndex && jtfv.findIndex) {
320         if (frame.active.find(jtfv.index) == frame.active.end()) {
321             parsing_printf("\tWARNING: found index variable %s, but it is not in the active map of the slice frame!\n", index.format().c_str());
322             jumpTableFormat = false;
323             return false;
324         }
325         if (frame.active[jtfv.index].size() > 1) {
326             parsing_printf("\tWARNING: index variable has more than one slicing element!\n");
327         }
328         indexLoc = frame.active[jtfv.index][0].ptr;
329         // We have found the index variable.
330         // Now we leave it alone and let the jump table index slice to find its bound
331         frame.active.erase(jtfv.index);
332         index = jtfv.index;
333         findIndex = true;
334     }
335     jumpTargetExpr = jumpTarget;
336     if (jtfv.findIndex && jtfv.findTableBase) { 
337         findTableBase = true;
338         parsing_printf("\tFind both table index and table base, current jump target %s\n", jumpTargetExpr->format().c_str());
339         return false;
340     }
341
342     // We have not found all elements of the jump table,
343     // and we have not rejected this indirect jump as a jump table.
344     // Let's continue slicing.
345     return true;
346 }
347
348 string JumpTableFormatPred::format() {
349     if (jumpTargetExpr) return jumpTargetExpr->format();
350     return string("");
351 }
352
353 bool JumpTableFormatPred::findRead(Graph::Ptr g, SliceNode::Ptr &readNode) {
354     NodeIterator gbegin, gend;
355     g->allNodes(gbegin, gend);
356     for (; gbegin != gend; ++gbegin) {
357         SliceNode::Ptr n = boost::static_pointer_cast<SliceNode>(*gbegin);
358         if (n->assign() == memLoc) {
359             continue;
360         }
361         if (n->assign() && n->assign()->insn().isValid() && n->assign()->insn().readsMemory()) {
362             readNode = n;
363             return true;
364         }
365     }
366     return false;
367 }
368
369 static Assignment::Ptr SearchForWrite(SliceNode::Ptr n, AbsRegion &src, Slicer::Location &loc, Slicer *s) {
370     
371
372     queue<Block*> workingList;
373     set<Block*> inQueue;
374     workingList.push(n->block());
375     inQueue.insert(n->block());
376
377     set<Expression::Ptr> memReads;
378     n->assign()->insn().getMemoryReadOperands(memReads);
379     if (memReads.size() != 1) {
380         parsing_printf("\tThe instruction has %d memory read operands, Should have only one\n", memReads.size());
381         return Assignment::Ptr();
382     }
383     Expression::Ptr memRead = *memReads.begin();
384     parsing_printf("\tsearch for memory operand %s\n", memRead->format().c_str());
385     Block* targetBlock = NULL;
386     Instruction targetInsn;
387     Address targetAddr;
388
389     while (!workingList.empty() && targetBlock == NULL) {
390         Block* curBlock = workingList.front();
391         workingList.pop();
392         // If the current block is the starting block,
393         // we need to make sure we only inspect instructions before the starting instruction
394         Address addr = 0;
395         if (curBlock == n->block()) {
396             addr = n->addr();
397         }
398
399         Block::Insns insns;
400         curBlock->getInsns(insns);
401
402         for (auto iit = insns.rbegin(); iit != insns.rend(); ++iit) {
403             if (addr > 0 && iit->first > addr) continue;
404             Instruction i = iit->second;
405             // We find an the first instruction that only writes to memory
406             // and the memory operand has the exact AST as the memory read.
407             // Ideally, we need an architecture independent way to check whether this is a move instruction.
408             // Category c_NoCategory excludes lots of non-move instructions
409             if (!i.readsMemory() && i.writesMemory() && i.getCategory() == c_NoCategory) {
410                 set<Expression::Ptr> memWrites;
411                 i.getMemoryWriteOperands(memWrites);
412                 if (memWrites.size() == 1 && *memRead == *(*memWrites.begin())) {
413                     targetBlock = curBlock;
414                     targetInsn = i;
415                     targetAddr = iit->first;
416                     parsing_printf("\t\tFind matching at %lx\n", targetAddr);
417
418                     // Now we try to identify the source register
419                     std::vector<Operand> ops;
420                     i.getOperands(ops);
421                     for (auto oit = ops.begin(); oit != ops.end(); ++oit) {
422                         if (!(*oit).writesMemory() && !(*oit).readsMemory()) {
423                             std::set<RegisterAST::Ptr> regsRead;
424                             oit->getReadSet(regsRead);
425                             if (regsRead.empty()) continue;
426                             src = AbsRegion(Absloc( (*regsRead.begin())->getID() ));
427                             parsing_printf("\t\tContinue to slice on %s\n", src.format().c_str());
428                             break;
429                         }
430                     }
431
432                     loc.block = curBlock;
433                     s->getInsnsBackward(loc);
434                     while (loc.addr() > targetAddr) {
435                         loc.rcurrent++;
436                     }
437                     break;
438                 }
439             }
440         }
441         Block::edgelist sources;
442         curBlock->copy_sources(sources); 
443         for (auto eit = sources.begin(); eit != sources.end(); ++eit) {
444             ParseAPI::Edge *e = *eit;
445             if (e->interproc()) continue;
446             if (e->type() == CATCH) continue;
447             if (inQueue.find(e->src()) != inQueue.end()) continue;
448             inQueue.insert(e->src());
449             workingList.push(e->src());     
450         }
451     }
452     
453     if (targetBlock == NULL) {
454         parsing_printf("\t\t Cannot find match\n");
455         return Assignment::Ptr();
456     }
457
458     AssignmentConverter ac(true, false);
459     vector<Assignment::Ptr> assignments;
460     ac.convert(targetInsn, targetAddr, n->func(), targetBlock, assignments);    
461     return assignments[0];
462 }
463
464 bool JumpTableFormatPred::adjustSliceFrame(Slicer::SliceFrame &frame, SliceNode::Ptr n, Slicer* s) {
465     // Delete all active regions introduce by this memory read,
466     // such as memory region, stack pointer, frame pointer
467     std::vector<AbsRegion>& inputs = n->assign()->inputs();
468     for (auto iit = inputs.begin(); iit != inputs.end(); ++iit) {
469         parsing_printf("\tdelete %s from active map\n", iit->format().c_str());
470         frame.active.erase(*iit);
471     }
472
473     // Search backward for the instruction that writes to the memory location
474     AbsRegion src;
475     Assignment::Ptr assign = SearchForWrite(n, src, frame.loc, s);
476     if (!assign) return false;
477     
478     NodeIterator nbegin, nend;
479     n->outs(nbegin, nend);
480     parsing_printf("\tadd %s to active map\n", src.format().c_str());
481     for (; nbegin != nend; ++nbegin) {
482         SliceNode::Ptr next = boost::static_pointer_cast<SliceNode>(*nbegin);
483         frame.active[src].push_back(Slicer::Element(next->block(), next->func(), src, next->assign()));
484         if (n->assign()->out() != src) {
485             aliases[next->assign()] = make_pair(VariableAST::create(Variable(n->assign()->out())), VariableAST::create(Variable(src)));
486         }   
487
488     }
489     return true;
490 }
491
492 bool JumpTableFormatPred::isTOCRead(Slicer::SliceFrame &frame, SliceNode::Ptr n) {
493     // Delete all active regions introduce by this memory read,
494     // such as memory region, er
495     std::vector<AbsRegion>& inputs = n->assign()->inputs();
496     bool findR2 = false;
497     for (auto iit = inputs.begin(); iit != inputs.end(); ++iit) {
498         if (*iit == AbsRegion(Absloc(ppc32::r2)) || *iit == AbsRegion(Absloc(ppc64::r2))) {
499             findR2 = true;
500             break;
501         }
502     }
503     if (!findR2) return false;
504     parsing_printf("\tTOC Read\n");
505     for (auto iit = inputs.begin(); iit != inputs.end(); ++iit) {
506         parsing_printf("\tdelete %s from active map\n", iit->format().c_str());
507         frame.active.erase(*iit);
508     }
509     return true;
510 }
511
512 bool JumpTableFormatPred::ignoreEdge(ParseAPI::Edge *e) {
513     // Assume that jump tables are independent
514     if (e->type() == INDIRECT) return true;
515     return false;
516 }