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