A few more performance fixes on jump table analysis:
[dyninst.git] / parseAPI / src / JumpTablePred.C
1 #include "dyntypes.h"
2 #include "Node.h"
3 #include "Graph.h"
4
5 #include "debug_parse.h"
6 #include "CodeObject.h"
7 #include "JumpTablePred.h"
8 #include "IndirectASTVisitor.h"
9
10 #include "Instruction.h"
11 #include "InstructionDecoder.h"
12
13 #include "AbslocInterface.h"
14 #include "SymEval.h"
15
16 using namespace Dyninst;
17 using namespace Dyninst::DataflowAPI;
18 using namespace Dyninst::ParseAPI;
19 using namespace Dyninst::InstructionAPI;
20 #define SIGNEX_64_32 0xffffffff00000000LL
21 #define SIGNEX_64_16 0xffffffffffff0000LL
22 #define SIGNEX_64_8  0xffffffffffffff00LL
23 #define SIGNEX_32_16 0xffff0000
24 #define SIGNEX_32_8 0xffffff00
25
26 // Assume the table contain less than this many entries.
27 #define MAX_TABLE_ENTRY 1000000
28
29 static void BuildEdgesAux(SliceNode::Ptr srcNode,
30                           ParseAPI::Block* curBlock,
31                           map<ParseAPI::Block*, map<AssignmentPtr, SliceNode::Ptr> > &targetMap,
32                           GraphPtr newG,
33                           set<ParseAPI::Block*> &visit,
34                           EdgeTypeEnum t) {                      
35     if (targetMap.find(curBlock) != targetMap.end()) {
36         // This block contains at least one silce node 
37         // that is reachable from the source DFS node
38         map<AssignmentPtr, SliceNode::Ptr> &candNodes = targetMap[curBlock];
39         Address addr = 0;
40         for (auto cit = candNodes.begin(); cit != candNodes.end(); ++cit)
41             // The node has to be either in a different block from the source node
42             // or in the same block but has a larger address to be considered 
43             // reachable from the source node
44             if (cit->first->addr() > srcNode->addr() || curBlock != srcNode->block())
45                 if (addr == 0 || addr > cit->first->addr()) {
46                     addr = cit->first->addr();
47                 }
48         if (addr != 0) {
49             // There may be several assignments locating 
50             // at the same address. Need to connecting all.
51             if (t == _edgetype_end_) t = FALLTHROUGH;
52             for (auto cit = candNodes.begin(); cit != candNodes.end(); ++cit)
53                 if (cit->first->addr() > srcNode->addr() || curBlock != srcNode->block())
54                     if (addr == cit->first->addr()) {
55                         newG->insertPair(srcNode, cit->second, TypedSliceEdge::create(srcNode, cit->second, t));
56                     }
57             return;
58         }
59     }
60
61     if (visit.find(curBlock) != visit.end()) return;
62     visit.insert(curBlock);
63     for (auto eit = curBlock->targets().begin(); eit != curBlock->targets().end(); ++eit)
64         // Xiaozhu:
65         // Our current slicing code ignores tail calls 
66         // (the slice code only checks if an edge type is CALL or not)
67         // so, I should be consistent here.
68         // If the slice code considers tail calls, need to change
69         // the predicate to (*eit)->interproc()
70         if ((*eit)->type() != CALL && (*eit)->type() != RET) {
71             EdgeTypeEnum newT = t; 
72             if (t == _edgetype_end_) {
73                 if ((*eit)->type() == COND_TAKEN || (*eit)->type() == COND_NOT_TAKEN) 
74                     newT = (*eit)->type();
75                 else 
76                     newT = FALLTHROUGH;
77             } 
78             BuildEdgesAux(srcNode, (*eit)->trg(), targetMap, newG, visit, newT);           
79         }
80 }                         
81
82
83 static void BuildEdges(SliceNode::Ptr curNode,
84                        map<ParseAPI::Block*, map<AssignmentPtr, SliceNode::Ptr> > &targetMap,
85                        GraphPtr newG) {
86     set<ParseAPI::Block*> visit;                     
87     BuildEdgesAux(curNode, curNode->block(), targetMap, newG, visit, _edgetype_end_);
88 }                      
89
90 static bool AssignIsZF(Assignment::Ptr a) {
91     return a->out().absloc().type() == Absloc::Register &&
92            (a->out().absloc().reg() == x86::zf || a->out().absloc().reg() == x86_64::zf);
93 }
94
95 static bool IsPushAndChangeSP(Assignment::Ptr a) {
96     entryID id = a->insn()->getOperation().getID();
97     if (id != e_push) return false;
98     Absloc aloc = a->out().absloc();
99     if (aloc.type() == Absloc::Register && aloc.reg().isStackPointer()) return true;
100     return false;;
101
102 }
103
104 static int AdjustGraphEntryAndExit(GraphPtr gp) {
105     int nodeCount = 0;
106     NodeIterator gbegin, gend;
107     gp->allNodes(gbegin, gend);
108     for (; gbegin != gend; ++gbegin) {
109         ++nodeCount;
110         Node::Ptr ptr = *gbegin;
111         if (!ptr->hasInEdges()) gp->insertEntryNode(ptr);
112         if (!ptr->hasOutEdges()) gp->insertExitNode(ptr);
113     }
114     return nodeCount;
115 }
116
117
118 GraphPtr JumpTablePred::BuildAnalysisGraph() {
119     GraphPtr newG = Graph::createGraph();
120     
121     NodeIterator gbegin, gend;
122     
123     // Create a map to help find whether we have reached a node
124     map<ParseAPI::Block*, map<AssignmentPtr, SliceNode::Ptr> > targetMap;
125
126     // Assignments that are at these addresses have flag assignment colocated
127     set<Address> shouldSkip;
128     for (auto ait = currentAssigns.begin(); ait != currentAssigns.end(); ++ait) {
129         if (AssignIsZF(*ait))
130             shouldSkip.insert((*ait)->addr());
131     }
132     for (auto ait = currentAssigns.begin(); ait != currentAssigns.end(); ++ait) {
133         Assignment::Ptr a = *ait;
134         if (   (AssignIsZF(a) || shouldSkip.find(a->addr()) == shouldSkip.end()) 
135             && !IsPushAndChangeSP(a)
136             && (!a->insn()->writesMemory() || MatchReadAST(a))) {
137             SliceNode::Ptr newNode = SliceNode::create(a, a->block(), a->func());
138             targetMap[a->block()][a] = newNode;
139             newG->addNode(newNode);
140         }
141     }
142
143     // Start from each node to do DFS and build edges
144     newG->allNodes(gbegin, gend);
145     for (; gbegin != gend; ++gbegin) {
146         SliceNode::Ptr node = boost::static_pointer_cast<SliceNode>(*gbegin);
147         BuildEdges(node, targetMap, newG);
148     }
149
150     // Build a virtual exit node
151     SliceNode::Ptr virtualExit = SliceNode::create(Assignment::Ptr(), NULL, NULL);
152     newG->addNode(virtualExit);
153     newG->allNodes(gbegin, gend);
154     for (; gbegin != gend; ++gbegin) {
155         SliceNode::Ptr cur = boost::static_pointer_cast<SliceNode>(*gbegin);
156         if (!cur->hasOutEdges() && cur != virtualExit) {
157             newG->insertPair(cur, virtualExit, TypedSliceEdge::create(cur, virtualExit, FALLTHROUGH));
158         }
159     }
160
161     AdjustGraphEntryAndExit(newG);
162
163
164     return newG;
165
166 }
167
168
169 bool JumpTablePred::endAtPoint(AssignmentPtr ap) {
170         if (ap->insn()->writesMemory()) return true;
171         return false;
172 }
173 bool JumpTablePred::addNodeCallback(AssignmentPtr ap) {
174     if (currentAssigns.find(ap) != currentAssigns.end()) return true;
175     
176     // For flags, we only analyze zf
177     if (ap->out().absloc().type() == Absloc::Register && ap->out().absloc().reg().regClass() == x86::FLAG &&
178        ap->out().absloc().reg() != x86::zf && ap->out().absloc().reg() != x86_64::zf) {
179         return true;
180     }
181
182     pair<AST::Ptr, bool> expandRet = ExpandAssignment(ap);
183     // If we do not have semantics for this instruction,
184     // we assume it does not influence the calculation of jump targets
185     if (!expandRet.second || expandRet.first == NULL) return true;
186
187
188 //    fprintf(stderr, "Adding assignment %s in instruction %s at %lx\n", ap->format().c_str(), ap->insn()->format().c_str(), ap->addr());
189     currentAssigns.insert(ap);
190
191     // If this assignment writes memory,
192     // we only want to analyze it when it writes to 
193     // an AST we have seen before and potentially
194     // can used for aliasing
195     if (ap->insn()->writesMemory()) {
196         if (!MatchReadAST(ap)) return true;
197     }
198
199     // If this assignment reads memory,
200     // we record the AST of the read so
201     // that in the future we can match a
202     // corresponding write to identify aliasing
203     if (ap->insn()->readsMemory() && expandRet.first->getID() == AST::V_RoseAST) {
204         RoseAST::Ptr roseAST = boost::static_pointer_cast<RoseAST>(expandRet.first);
205         if (roseAST->val().op == ROSEOperation::derefOp) {
206             readAST.push_back(expandRet.first);
207         }
208     }
209
210     // We create the CFG based on the found nodes
211     GraphPtr g = BuildAnalysisGraph();
212
213     BoundFactsCalculator bfc(func, g, func->entry() == block, rf, thunks, block->last(), expandCache);
214     bfc.CalculateBoundedFacts();
215
216     BoundValue target;
217     bool ijt = IsJumpTable(g, bfc, target);
218     if (ijt) {
219         bool ret = !FillInOutEdges(target, outEdges);
220 //      fprintf(stderr, "Return %s\n", ret ? "true" : "false");
221 //      if (dyn_debug_parsing) exit(0);
222         return ret;
223     } else {
224 //        fprintf(stderr, "Return true\n");
225 //      if (dyn_debug_parsing) exit(0);
226
227         return true;
228     }   
229
230
231
232 }
233 bool JumpTablePred::FillInOutEdges(BoundValue &target, 
234                                                  vector<pair< Address, Dyninst::ParseAPI::EdgeTypeEnum > >& outEdges) {
235     outEdges.clear();
236     Address tableBase = target.interval.low;
237     Address tableLastEntry = target.interval.high;
238     Architecture arch = block->obj()->cs()->getArch();
239     if (arch == Arch_x86) {
240         tableBase &= 0xffffffff;
241         tableLastEntry &= 0xffffffff;
242     }
243
244 #if defined(os_windows)
245     tableBase -= block->obj()->cs()->loadAddress();
246     tableLastEntry -= block->obj()->cs()->loadAddress();
247 #endif
248
249     parsing_printf("The final target bound fact:\n");
250     target.Print();
251     if (!block->obj()->cs()->isValidAddress(tableBase)) {
252         parsing_printf("\ttableBase 0x%lx invalid, returning false\n", tableBase);
253         return false;
254     }
255
256     for (Address tableEntry = tableBase; tableEntry <= tableLastEntry; tableEntry += target.interval.stride) {
257         if (!block->obj()->cs()->isValidAddress(tableEntry)) continue;
258         Address targetAddress = 0;
259         if (target.tableReadSize > 0) {
260             // Assume the table contents are moved in a sign extended way;
261             switch (target.tableReadSize) {
262                 case 8:
263                     targetAddress = *(const uint64_t *) block->obj()->cs()->getPtrToInstruction(tableEntry);
264                     break;
265                 case 4:
266                     targetAddress = *(const uint32_t *) block->obj()->cs()->getPtrToInstruction(tableEntry);
267                     if ((arch == Arch_x86_64) && (targetAddress & 0x80000000)) {
268                         targetAddress |= SIGNEX_64_32;
269                     }
270                     break;
271                 case 2:
272                     targetAddress = *(const uint16_t *) block->obj()->cs()->getPtrToInstruction(tableEntry);
273                     if ((arch == Arch_x86_64) && (targetAddress & 0x8000)) {
274                         targetAddress |= SIGNEX_64_16;
275                     }
276                     if ((arch == Arch_x86) && (targetAddress & 0x8000)) {
277                         targetAddress |= SIGNEX_32_16;
278                     }
279
280                     break;
281                 case 1:
282                     targetAddress = *(const uint8_t *) block->obj()->cs()->getPtrToInstruction(tableEntry);
283                     if ((arch == Arch_x86_64) && (targetAddress & 0x80)) {
284                         targetAddress |= SIGNEX_64_8;
285                     }
286                     if ((arch == Arch_x86) && (targetAddress & 0x80)) {
287                         targetAddress |= SIGNEX_32_8;
288                     }
289
290                     break;
291
292                 default:
293                     parsing_printf("Invalid memory read size %d\n", target.tableReadSize);
294                     return false;
295             }
296             if (targetAddress != 0) {
297                 if (target.isSubReadContent) 
298                     targetAddress = target.targetBase - targetAddress;
299                 else 
300                     targetAddress += target.targetBase; 
301
302             }
303 #if defined(os_windows)
304             targetAddress -= block->obj()->cs()->loadAddress();
305 #endif
306         } else targetAddress = tableEntry;
307
308         if (block->obj()->cs()->getArch() == Arch_x86) targetAddress &= 0xffffffff;
309         parsing_printf("Jumping to target %lx,", targetAddress);
310         if (block->obj()->cs()->isCode(targetAddress)) {
311             outEdges.push_back(make_pair(targetAddress, INDIRECT));
312             parsing_printf(" is code.\n" );
313         } else {
314             parsing_printf(" not code.\n");
315         }
316         // If the jump target is resolved to be a constant, 
317         if (target.interval.stride == 0) break;
318     }
319     return true;
320 }
321 bool JumpTablePred::IsJumpTable(GraphPtr slice, 
322                                               BoundFactsCalculator &bfc,
323                                               BoundValue &target) {
324     NodeIterator exitBegin, exitEnd, srcBegin, srcEnd;
325     slice->exitNodes(exitBegin, exitEnd);
326     SliceNode::Ptr virtualExit = boost::static_pointer_cast<SliceNode>(*exitBegin);
327     virtualExit->ins(srcBegin, srcEnd);
328     SliceNode::Ptr jumpNode = boost::static_pointer_cast<SliceNode>(*srcBegin);
329     
330     const Absloc &loc = jumpNode->assign()->out().absloc();
331     parsing_printf("Checking final bound fact for %s\n",loc.format().c_str()); 
332     BoundFact *bf = bfc.GetBoundFactOut(virtualExit);
333     BoundValue *tarBoundValue = bf->GetBound(VariableAST::create(Variable(loc)));
334     if (tarBoundValue != NULL) {
335         target = *(tarBoundValue);
336         uint64_t s = target.interval.size();
337         if (s > 0 && s <= MAX_TABLE_ENTRY) return true;
338     }
339     return false;
340 }
341
342 bool JumpTablePred::MatchReadAST(Assignment::Ptr a) {
343     pair<AST::Ptr, bool> expandRet = ExpandAssignment(a);
344     if (!expandRet.second || expandRet.first == NULL) return false;
345     if (a->out().generator() == NULL) return false;
346     AST::Ptr write = SimplifyAnAST(RoseAST::create(ROSEOperation(ROSEOperation::derefOp, a->out().size()), a->out().generator()), a->insn()->size());
347
348     if (write == NULL) return false;
349     for (auto ait = readAST.begin(); ait != readAST.end(); ++ait) 
350         if (*write == **ait) return true;
351     return false;
352 }
353
354 pair<AST::Ptr, bool> JumpTablePred::ExpandAssignment(Assignment::Ptr assign) {
355     if (expandCache.find(assign) != expandCache.end()) {
356         AST::Ptr ast = expandCache[assign];
357 //      if (ast) return make_pair(DeepCopyAnAST(ast), true); else return make_pair(ast, false);
358         if (ast) return make_pair(ast, true); else return make_pair(ast, false);
359
360     } else {
361         pair<AST::Ptr, bool> expandRet = SymEval::expand(assign, false);
362         if (expandRet.second && expandRet.first) {
363             AST::Ptr calculation = SimplifyAnAST(expandRet.first, assign->insn()->size());
364             //expandCache[assign] = DeepCopyAnAST(expandRet.first);
365             expandCache[assign] = calculation;
366         } else {
367             expandCache[assign] = AST::Ptr();
368         }
369         return make_pair( expandCache[assign], expandRet.second );
370     }
371 }
372