More switches to unordered_set and unordered_map
[dyninst.git] / parseAPI / src / BoundFactCalculator.C
1 #include "dyntypes.h"
2 #include "CodeObject.h"
3 #include "CodeSource.h"
4
5 #include "BoundFactCalculator.h"
6 #include "IndirectASTVisitor.h"
7 #include "debug_parse.h"
8 #include "BackwardSlicing.h"
9 #include "Instruction.h"
10
11 using namespace Dyninst::InstructionAPI;
12
13 void BoundFactsCalculator::NaturalDFS(Node::Ptr cur) {
14     nodeColor[cur] = 1;
15     NodeIterator nbegin, nend;
16     cur->outs(nbegin, nend);
17
18     for (; nbegin != nend; ++nbegin) 
19         if (nodeColor.find(*nbegin) == nodeColor.end())
20             NaturalDFS(*nbegin);
21
22     reverseOrder.push_back(cur);
23    
24 }
25
26 void BoundFactsCalculator::ReverseDFS(Node::Ptr cur) {
27     nodeColor[cur] = 1;
28     analysisOrder[cur] = orderStamp;
29     NodeIterator nbegin, nend;
30     cur->ins(nbegin, nend);
31
32     for (; nbegin != nend; ++nbegin) 
33         if (nodeColor.find(*nbegin) == nodeColor.end())
34             ReverseDFS(*nbegin);
35 }
36
37 static void BuildEdgeFromVirtualEntry(SliceNode::Ptr virtualEntry,
38                                       ParseAPI::Block *curBlock,
39                                       map<ParseAPI::Block*, vector<SliceNode::Ptr> >&targetMap,
40                                       set<ParseAPI::Block*> &visit,
41                                       GraphPtr slice) {
42     if (targetMap.find(curBlock) != targetMap.end()) {
43         const vector<SliceNode::Ptr> &targets = targetMap[curBlock];
44         for (auto nit = targets.begin(); nit != targets.end(); ++nit) {
45             SliceNode::Ptr trgNode = *nit; 
46             slice->insertPair(virtualEntry, trgNode, TypedSliceEdge::create(virtualEntry, trgNode, FALLTHROUGH));
47         }
48         return;
49     }
50     if (visit.find(curBlock) != visit.end()) return;
51     visit.insert(curBlock);
52     for (auto eit = curBlock->targets().begin(); eit != curBlock->targets().end(); ++eit)
53         if ((*eit)->type() != CALL && (*eit)->type() != RET) {
54             BuildEdgeFromVirtualEntry(virtualEntry, (*eit)->trg(), targetMap, visit, slice);       
55         }
56 }                                     
57
58 void BoundFactsCalculator::DetermineAnalysisOrder() {
59     NodeIterator nbegin, nend;
60     slice->allNodes(nbegin, nend);
61
62     nodeColor.clear();
63     reverseOrder.clear();
64     analysisOrder.clear();
65     for (; nbegin != nend; ++nbegin) 
66         if (nodeColor.find(*nbegin) == nodeColor.end()) {
67             NaturalDFS(*nbegin);
68         }
69     nodeColor.clear();
70     orderStamp = 0;
71     for (auto nit = reverseOrder.rbegin(); nit != reverseOrder.rend(); ++nit)
72         if (nodeColor.find(*nit) == nodeColor.end()) {
73             ++orderStamp;
74             ReverseDFS(*nit);
75         }
76
77     // Create a virtual entry node that has
78     // edges into all entry SCCs
79     SliceNode::Ptr virtualEntry = SliceNode::create(Assignment::Ptr(), func->entry(), func);
80     analysisOrder[virtualEntry] = 0;
81     for (int curOrder = 1; curOrder <= orderStamp; ++curOrder) {
82         // First determine all nodes in this SCC
83         vector<Node::Ptr> curNodes;
84         NodeIterator nbegin, nend;
85         slice->allNodes(nbegin, nend);
86         for (; nbegin != nend; ++nbegin) {
87             if (analysisOrder[*nbegin] == curOrder) {
88                 curNodes.push_back(*nbegin);
89             } 
90         }
91
92         // If this SCC does not have any outside edge,
93         // it is an entry SCC and we need to connect
94         // the virtual entry to it
95         if (!HasIncomingEdgesFromLowerLevel(curOrder, curNodes)) {
96             if (curNodes.size() == 1) {
97                 // If the SCC has only one node,
98                 // we connect the virtual entry to this single node
99                 SliceNode::Ptr node = boost::static_pointer_cast<SliceNode>(*(curNodes.begin()));
100                 slice->insertPair(virtualEntry, node, TypedSliceEdge::create(virtualEntry, node, FALLTHROUGH));
101             } else {
102                 // If there are more than one node in this SCC,
103                 // we do a DFS to see which nodes in the SCC can be
104                 // reached from the entry of the function without passing
105                 // through other nodes in the SCC.
106                 // Basically, we only connect edges from the virtual entry
107                 // to the entries of the SCC
108                 set<ParseAPI::Block*> visit;
109                 map<ParseAPI::Block*, vector<SliceNode::Ptr> >targetMap;
110                 for (auto nit = curNodes.begin(); nit != curNodes.end(); ++nit) {
111                     SliceNode::Ptr node = boost::static_pointer_cast<SliceNode>(*nit);
112                     ParseAPI::Block * b = node->block();
113                     Address addr = node->addr();
114                     if (targetMap.find(b) == targetMap.end()) {
115                         targetMap[b].push_back(node);
116                     } else if (targetMap[b][0]->addr() > addr) {
117                         targetMap[b].clear();
118                         targetMap[b].push_back(node);
119                     } else if (targetMap[b][0]->addr() == addr) {
120                         targetMap[b].push_back(node);
121                     }
122                 }
123                 BuildEdgeFromVirtualEntry(virtualEntry, virtualEntry->block(), targetMap, visit, slice); 
124             }
125         }
126     }
127     slice->clearEntryNodes();
128     slice->markAsEntryNode(virtualEntry);
129 }
130
131 bool BoundFactsCalculator::HasIncomingEdgesFromLowerLevel(int curOrder, vector<Node::Ptr>& curNodes) {
132     for (auto nit = curNodes.begin(); nit != curNodes.end(); ++nit) {
133         Node::Ptr cur = *nit;
134         NodeIterator nbegin, nend;
135         cur->ins(nbegin, nend);
136         for (; nbegin != nend; ++nbegin) 
137             if (analysisOrder[*nbegin] < curOrder) return true;
138     }
139     return false;
140
141 }
142
143 bool BoundFactsCalculator::CalculateBoundedFacts() {    
144     /* We use a dataflow analysis to calculate the value bound
145      * of each register and potentially some memory locations.
146      * The key steps of the dataflow analysis are 
147      * 1. Determine the analysis order:
148      *    First calculate all strongly connected components (SCC)
149      *    of the graph. The flow analysis inside a SCC is 
150      *    iterative. The flow analysis between several SCCs
151      *    is done topologically. 
152      * 2. For each node, need to calculate the meet and 
153      *    calculate the transfer function.
154      * 1. The meet should be simply an intersection of all the bounded facts 
155      * along all paths. 
156      * 2. To calculate the transfer function, we first get the symbolic expression
157      * of the instrution for the node. Then depending on the instruction operation
158      * and the meet result, we know what are still bounded. For example, loading 
159      * memory is always unbounded; doing and operation on a register with a constant
160      * makes the register bounded. 
161      */
162     
163     DetermineAnalysisOrder();
164 /*
165     if (jumpAddr == 0x4049c1) {
166         slice->printDOT("target_final.dot");
167         exit(0);
168     }
169 */    
170     queue<Node::Ptr> workingList;
171     unordered_set<Node::Ptr, Node::NodePtrHasher> inQueue;
172     unordered_map<Node::Ptr, int, Node::NodePtrHasher> inQueueLimit;
173
174     for (int curOrder = 0; curOrder <= orderStamp; ++curOrder) {
175         // We first determine which nodes are
176         // in this SCC
177         vector<Node::Ptr> curNodes;
178         NodeIterator nbegin, nend;
179         slice->allNodes(nbegin, nend);
180         for (; nbegin != nend; ++nbegin) {
181             if (analysisOrder[*nbegin] == curOrder) {
182                 curNodes.push_back(*nbegin);
183                 workingList.push(*nbegin);
184                 inQueue.insert(*nbegin);
185             } 
186         }
187
188         if (!HasIncomingEdgesFromLowerLevel(curOrder, curNodes)) {
189             // If this SCC is an entry SCC,
190             // we choose a node inside the SCC
191             // and let it be top.
192             // This should only contain the virtual entry node
193             parsing_printf("This SCC does not incoming edges from outside\n");
194             boundFacts[curNodes[0]] = new BoundFact();
195         }
196         parsing_printf("Starting analysis inside SCC %d\n", curOrder);
197         // We now start iterative analysis inside the SCC
198         while (!workingList.empty()) {
199             Node::Ptr curNode = workingList.front();
200             workingList.pop();
201             inQueue.erase(curNode);
202             
203             SliceNode::Ptr node = boost::static_pointer_cast<SliceNode>(curNode);
204             ++inQueueLimit[curNode];
205             if (inQueueLimit[curNode] > IN_QUEUE_LIMIT) continue;
206             
207             BoundFact* oldFact = GetBoundFact(curNode);
208             parsing_printf("Calculate Meet for %lx", node->addr());
209             if (node->assign()) {
210                 parsing_printf(", insn: %s\n", node->assign()->insn()->format().c_str());
211             }
212             else {
213                 if (node->block() == NULL) 
214                     parsing_printf(", the VirtualExit node\n");
215                 else
216                     parsing_printf(", the VirtualEntry node\n");
217
218             }
219             parsing_printf("\tOld fact for %lx:\n", node->addr());
220             if (oldFact == NULL) parsing_printf("\t\t do not exist\n"); else oldFact->Print();
221             BoundFact* newFact = Meet(curNode);
222             parsing_printf("\tNew fact at %lx\n", node->addr());
223             if (newFact != NULL) newFact->Print(); else parsing_printf("\t\tNot calculated\n");
224             if (newFact != NULL && (oldFact == NULL || *oldFact != *newFact)) {
225                 parsing_printf("\tFacts change!\n");
226                 if (oldFact != NULL) delete oldFact;
227                 boundFacts[curNode] = newFact;
228                 curNode->outs(nbegin, nend);
229                 for (; nbegin != nend; ++nbegin)
230                     // We only add node inside current SCC into the working list
231                     if (inQueue.find(*nbegin) == inQueue.end() && analysisOrder[*nbegin] == curOrder) {
232                         workingList.push(*nbegin);
233                         inQueue.insert(*nbegin);
234                     }
235             } else {
236                 if (newFact != NULL) delete newFact;
237                 parsing_printf("\tFacts do not change!\n");
238             }
239
240         }
241
242
243
244 /*
245         if (jumpAddr == 0x805351a) {
246             VariableAST::Ptr ecx = VariableAST::create(Variable(AbsRegion(Absloc(x86::ecx))));
247             BoundValue *val = newFact->GetBound(ecx);
248             if (val == NULL) {
249                 printf("\tecx is top\n");
250             }
251             else {
252                 printf("\tecx: %d[%lx,%lx]\n", val->interval.stride, val->interval.low, val->interval.high);
253             }
254         }
255 */      
256     }
257
258     return true;
259 }
260
261
262
263
264 void BoundFactsCalculator::ThunkBound(BoundFact* curFact, Node::Ptr src, Node::Ptr trg) {
265
266     // This function checks whether any found thunk is between 
267     // the src node and the trg node. If there is any, then we have 
268     // extra bound information to be added.
269     ParseAPI::Block *srcBlock;
270     Address srcAddr = 0;
271     if (src == Node::Ptr()) 
272         srcBlock = func->entry();
273     else {
274         SliceNode::Ptr srcNode = boost::static_pointer_cast<SliceNode>(src);
275         srcBlock = srcNode->block();
276         srcAddr = srcNode->addr();
277
278     }
279     SliceNode::Ptr trgNode = boost::static_pointer_cast<SliceNode>(trg);                               
280     ParseAPI::Block *trgBlock = trgNode->block();
281     Address trgAddr = trgNode->addr();
282
283     for (auto tit = thunks.begin(); tit != thunks.end(); ++tit) {
284         ParseAPI::Block* thunkBlock = tit->second.block;
285         parsing_printf("\t\tCheck srcAddr at %lx, trgAddr at %lx, thunk at %lx\n", srcAddr, trgAddr, tit->first);
286         if (src != Node::Ptr()) {
287             if (srcBlock == thunkBlock) {
288                 if (srcAddr > tit->first) continue;
289             } else {
290                 if (rf.thunk_ins[thunkBlock].find(srcBlock) == rf.thunk_ins[thunkBlock].end()) continue;
291             }
292         }
293         if (trgBlock == thunkBlock) {
294             if (trgAddr < tit->first) continue;
295         } else {
296             if (rf.thunk_outs[thunkBlock].find(trgBlock) == rf.thunk_outs[thunkBlock].end()) continue;
297         }
298
299         parsing_printf("\t\t\tfind thunk at %lx between the source and the target. Add fact", tit->first);
300         BoundValue *bv = new BoundValue(tit->second.value);
301         bv->Print();
302         curFact->GenFact(VariableAST::create(Variable(AbsRegion(Absloc(tit->second.reg)))), bv, false);
303     }
304
305
306 }
307
308
309 static bool IsConditionalJump(Instruction::Ptr insn) {
310     entryID id = insn->getOperation().getID();
311
312     if (id == e_jz || id == e_jnz ||
313         id == e_jb || id == e_jnb ||
314         id == e_jbe || id == e_jnbe ||
315         id == e_jb_jnaej_j || id == e_jnb_jae_j ||
316         id == e_jle || id == e_jl ||
317         id == e_jnl || id == e_jnle) return true;
318     return false;
319 }
320
321 BoundFact* BoundFactsCalculator::Meet(Node::Ptr curNode) {
322
323     SliceNode::Ptr node = boost::static_pointer_cast<SliceNode>(curNode);     
324
325     EdgeIterator gbegin, gend;
326     curNode->ins(gbegin, gend);    
327     BoundFact* newFact = NULL;
328     
329     bool first = true;  
330     for (; gbegin != gend; ++gbegin) {
331         TypedSliceEdge::Ptr edge = boost::static_pointer_cast<TypedSliceEdge>(*gbegin); 
332         SliceNode::Ptr srcNode = boost::static_pointer_cast<SliceNode>(edge->source()); 
333         BoundFact *prevFact = GetBoundFact(srcNode);        
334         if (prevFact == NULL) {
335             parsing_printf("\t\tIncoming node %lx has not been calculated yet, ignore it\n", srcNode->addr());
336             continue;
337         } else {            
338             // Otherwise, create a new copy.
339             // We do not want to overwrite the bound fact
340             // of the predecessor
341             prevFact = new BoundFact(*prevFact);
342         }
343         parsing_printf("\t\tMeet incoming edge from %lx\n", srcNode->addr());
344         parsing_printf("\t\tThe fact from %lx before applying transfer function\n", srcNode->addr());
345         prevFact->Print();
346         if (!srcNode->assign()) {
347             parsing_printf("\t\tThe predecessor node is the virtual entry ndoe\n");
348             if (firstBlock) {
349                 // If the indirect jump is in the entry block
350                 // of the function, we assume that rax is in
351                 // range [0,8] for analyzing the movaps table.
352                 // NEED TO HAVE A SAFE WAY TO DO THIS!!
353                 parsing_printf("\t\tApplying entry block rax assumption!\n");
354                 AST::Ptr axAST;
355                 if (func->entry()->obj()->cs()->getAddressWidth() == 8)
356                     axAST = VariableAST::create(Variable(AbsRegion(Absloc(x86_64::rax))));
357                 else
358                     // DOES THIS REALLY SHOW UP IN 32-BIT CODE???
359                     axAST = VariableAST::create(Variable(AbsRegion(Absloc(x86::eax))));
360                 prevFact->GenFact(axAST, new BoundValue(StridedInterval(1,0,8)), false);
361             }
362         } else if (srcNode->assign() && srcNode->assign()->out().absloc().type() == Absloc::Register &&
363             (srcNode->assign()->out().absloc().reg() == x86::zf || srcNode->assign()->out().absloc().reg() == x86_64::zf)) {
364             // zf should be only predecessor of this node
365             parsing_printf("\t\tThe predecessor node is zf assignment!\n");
366             prevFact->SetPredicate(srcNode->assign(), ExpandAssignment(srcNode->assign()) );        
367         } else if (srcNode->assign() && IsConditionalJump(srcNode->assign()->insn())) {
368             // If the predecessor is a conditional jump,
369             // we can determine bound fact based on the predicate and the edge type
370             parsing_printf("\t\tThe predecessor node is a conditional jump!\n");
371             if (!prevFact->ConditionalJumpBound(srcNode->assign()->insn(), edge->type())) {
372                 fprintf(stderr, "From %lx to %lx\n", srcNode->addr(), node->addr());
373                 assert(0);
374             }
375         } else {
376             // The predecessor is not a conditional jump,
377             // then we can determine buond fact based on the src assignment
378             parsing_printf("\t\tThe predecessor node is normal node\n");
379             if (srcNode->assign()) parsing_printf("\t\t\tentry id %d\n", srcNode->assign()->insn()->getOperation().getID());
380             CalcTransferFunction(srcNode, prevFact);
381         }
382         ThunkBound(prevFact, srcNode, node);
383         parsing_printf("\t\tFact from %lx after applying transfer function\n", srcNode->addr());
384         prevFact->Print();
385         if (first) {
386             // For the first incoming dataflow fact,
387             // we just copy it.
388             // We can do this because if an a-loc
389             // is missing in the fact map, we assume
390             // the a-loc is top. 
391             first = false;
392             newFact = prevFact;
393         } else {
394             newFact->Meet(*prevFact);
395             delete prevFact;
396         }
397     }
398     return newFact;
399 }
400
401 void BoundFactsCalculator::CalcTransferFunction(Node::Ptr curNode, BoundFact *newFact){
402
403     SliceNode::Ptr node = boost::static_pointer_cast<SliceNode>(curNode);    
404     AbsRegion &ar = node->assign()->out();
405     Instruction::Ptr insn = node->assign()->insn();
406
407     parsing_printf("\t\t\tExpanding assignment %s in instruction at %lx: %s.\n", node->assign()->format().c_str(), node->addr(), insn->format().c_str());
408     
409     pair<AST::Ptr, bool> expandRet = ExpandAssignment(node->assign());
410         
411     if (expandRet.first == NULL) {
412         // If the instruction is outside the set of instrutions we
413         // add instruction semantics. We assume this instruction
414         // kills all bound fact.
415 //      parsing_printf("\t\t\t No semantic support for this instruction. Kill all bound fact\n");
416 //      newFact->SetToBottom();
417         parsing_printf("\t\t\t No semantic support for this instruction. Assume it does not affect jump target calculation. Ignore it (Treat as identity function)\n"); 
418         return;
419     }
420     
421     parsing_printf("\t\t\t AST after expanding (without simplify) %s\n", expandRet.first->format().c_str());
422     AST::Ptr calculation = SimplifyAnAST(expandRet.first, insn->size());
423     parsing_printf("\t\t\t AST after expanding %s\n", calculation->format().c_str());
424         
425     BoundCalcVisitor bcv(*newFact, node->block());
426     calculation->accept(&bcv);
427     
428     AST::Ptr outAST = VariableAST::create(Variable(ar));
429     if (bcv.IsResultBounded(calculation)) { 
430         parsing_printf("\t\t\tGenerate bound fact for %s\n", ar.absloc().format().c_str());
431         newFact->GenFact(outAST, new BoundValue(*bcv.GetResultBound(calculation)), false);
432     }
433     else {
434         parsing_printf("\t\t\tKill bound fact for %s\n", ar.absloc().format().c_str());
435         newFact->KillFact(outAST, false);
436     }
437     if (calculation->getID() == AST::V_VariableAST) {
438         // We only track alising between registers
439         parsing_printf("\t\t\t%s and %s are equal\n", calculation->format().c_str(), outAST->format().c_str());
440         newFact->InsertRelation(calculation, outAST, BoundFact::Equal);
441     }
442     newFact->AdjustPredicate(outAST, calculation);
443
444     // Now try to track all aliasing
445     newFact->TrackAlias(DeepCopyAnAST(calculation), ar);
446
447     parsing_printf("\t\t\tCalculating transfer function: Output facts\n");
448     newFact->Print();
449
450 }                                               
451
452 BoundFact* BoundFactsCalculator::GetBoundFact(Node::Ptr node) {
453     auto fit = boundFacts.find(node);
454     if (fit == boundFacts.end())
455         return NULL;
456     else
457         return fit->second;
458 }
459
460 BoundFactsCalculator::~BoundFactsCalculator() {
461     for (auto fit = boundFacts.begin(); fit != boundFacts.end(); ++fit)
462         if (fit->second != NULL)
463             delete fit->second;
464     boundFacts.clear();
465 }
466
467 pair<AST::Ptr, bool> BoundFactsCalculator::ExpandAssignment(Assignment::Ptr assign) {
468     if (expandCache.find(assign) != expandCache.end()) {
469         AST::Ptr ast = expandCache[assign];
470         if (ast) return make_pair(DeepCopyAnAST(ast), true); else return make_pair(ast, false);
471     } else {
472         pair<AST::Ptr, bool> expandRet = SymEval::expand(assign, false);
473         if (expandRet.second && expandRet.first) {
474             expandCache[assign] = DeepCopyAnAST(expandRet.first);
475         } else {
476             expandCache[assign] = AST::Ptr();
477         }
478         return expandRet;
479     }
480 }
481