Add support for multiple level jump tables. Current implementation have
[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 void BoundFactsCalculator::DetermineAnalysisOrder() {
37     NodeIterator nbegin, nend;
38     slice->allNodes(nbegin, nend);
39
40     nodeColor.clear();
41     reverseOrder.clear();
42     analysisOrder.clear();
43     for (; nbegin != nend; ++nbegin) 
44         if (nodeColor.find(*nbegin) == nodeColor.end()) {
45             NaturalDFS(*nbegin);
46         }
47     nodeColor.clear();
48     orderStamp = 0;
49     for (auto nit = reverseOrder.rbegin(); nit != reverseOrder.rend(); ++nit)
50         if (nodeColor.find(*nit) == nodeColor.end()) {
51             ++orderStamp;
52             ReverseDFS(*nit);
53         } 
54 }
55
56 bool BoundFactsCalculator::HasIncomingEdgesFromLowerLevel(int curOrder, vector<Node::Ptr>& curNodes) {
57     for (auto nit = curNodes.begin(); nit != curNodes.end(); ++nit) {
58         Node::Ptr cur = *nit;
59         NodeIterator nbegin, nend;
60         cur->ins(nbegin, nend);
61         for (; nbegin != nend; ++nbegin) 
62             if (analysisOrder[*nbegin] < curOrder) return true;
63     }
64     return false;
65
66 }
67
68 bool BoundFactsCalculator::CalculateBoundedFacts() {    
69     /* We use a dataflow analysis to calculate the value bound
70      * of each register and potentially some memory locations.
71      * The key steps of the dataflow analysis are 
72      * 1. Determine the analysis order:
73      *    First calculate all strongly connected components (SCC)
74      *    of the graph. The flow analysis inside a SCC is 
75      *    iterative. The flow analysis between several SCCs
76      *    is done topologically. 
77      * 2. For each node, need to calculate the meet and 
78      *    calculate the transfer function.
79      * 1. The meet should be simply an intersection of all the bounded facts 
80      * along all paths. 
81      * 2. To calculate the transfer function, we first get the symbolic expression
82      * of the instrution for the node. Then depending on the instruction operation
83      * and the meet result, we know what are still bounded. For example, loading 
84      * memory is always unbounded; doing and operation on a register with a constant
85      * makes the register bounded. 
86      */
87     
88     DetermineAnalysisOrder();
89
90     queue<Node::Ptr> workingList;
91     set<Node::Ptr> inQueue;
92     map<Node::Ptr, int> inQueueLimit;
93
94     for (int curOrder = 1; curOrder <= orderStamp; ++curOrder) {
95         // We first determine which nodes are
96         // in this SCC
97         vector<Node::Ptr> curNodes;
98         NodeIterator nbegin, nend;
99         slice->allNodes(nbegin, nend);
100         for (; nbegin != nend; ++nbegin) {
101             if (analysisOrder[*nbegin] == curOrder) {
102                 curNodes.push_back(*nbegin);
103                 workingList.push(*nbegin);
104                 inQueue.insert(*nbegin);
105             } 
106         }
107
108         if (!HasIncomingEdgesFromLowerLevel(curOrder, curNodes)) {
109             // If this SCC is an entry SCC,
110             // we choose a node inside the SCC
111             // and let it be top
112             parsing_printf("This SCC does not incoming edges from outside\n");
113             boundFacts[curNodes[0]] = new BoundFact();
114         }
115         parsing_printf("Starting analysis inside SCC %d\n", curOrder);
116         // We now start iterative analysis inside the SCC
117         while (!workingList.empty()) {
118             Node::Ptr curNode = workingList.front();
119             workingList.pop();
120             inQueue.erase(curNode);
121             
122             SliceNode::Ptr node = boost::static_pointer_cast<SliceNode>(curNode);
123             ++inQueueLimit[curNode];
124             if (inQueueLimit[curNode] > IN_QUEUE_LIMIT) continue;
125             
126             BoundFact* oldFact = GetBoundFact(curNode);
127             parsing_printf("Calculate Meet for %lx", node->addr());
128             if (node->assign()) {
129                 parsing_printf(", insn: %s\n", node->assign()->insn()->format().c_str());
130 //              if (jumpAddr == 0x805351a) printf("insn at %lx: %s\n", node->addr(), node->assign()->insn()->format().c_str());
131             }
132             else {
133                 parsing_printf(", the VirtualExit node\n");
134  //             if (jumpAddr == 0x805351a) printf("virtual node\n");
135
136             }
137             parsing_printf("\tOld fact for %lx:\n", node->addr());
138             if (oldFact == NULL) parsing_printf("\t\t do not exist\n"); else oldFact->Print();
139             BoundFact* newFact = Meet(curNode);
140             parsing_printf("\tNew fact at %lx\n", node->addr());
141             if (newFact != NULL) newFact->Print(); else parsing_printf("\t\tNot calculated\n");
142             if (newFact != NULL && (oldFact == NULL || *oldFact != *newFact)) {
143                 parsing_printf("\tFacts change!\n");
144                 if (oldFact != NULL) delete oldFact;
145                 boundFacts[curNode] = newFact;
146                 curNode->outs(nbegin, nend);
147                 for (; nbegin != nend; ++nbegin)
148                     // We only add node inside current SCC into the working list
149                     if (inQueue.find(*nbegin) == inQueue.end() && analysisOrder[*nbegin] == curOrder) {
150                         workingList.push(*nbegin);
151                         inQueue.insert(*nbegin);
152                     }
153             } else {
154                 if (newFact != NULL) delete newFact;
155                 parsing_printf("\tFacts do not change!\n");
156             }
157
158         }
159
160
161
162 /*
163         if (jumpAddr == 0x805351a) {
164             VariableAST::Ptr ecx = VariableAST::create(Variable(AbsRegion(Absloc(x86::ecx))));
165             BoundValue *val = newFact->GetBound(ecx);
166             if (val == NULL) {
167                 printf("\tecx is top\n");
168             }
169             else {
170                 printf("\tecx: %d[%lx,%lx]\n", val->interval.stride, val->interval.low, val->interval.high);
171             }
172         }
173 */      
174     }
175
176     return true;
177 }
178
179
180
181
182 void BoundFactsCalculator::ThunkBound(BoundFact* curFact, Node::Ptr src, Node::Ptr trg) {
183
184     // This function checks whether any found thunk is between 
185     // the src node and the trg node. If there is any, then we have 
186     // extra bound information to be added.
187     ParseAPI::Block *srcBlock;
188     Address srcAddr = 0;
189     if (src == Node::Ptr()) 
190         srcBlock = func->entry();
191     else {
192         SliceNode::Ptr srcNode = boost::static_pointer_cast<SliceNode>(src);
193         srcBlock = srcNode->block();
194         srcAddr = srcNode->addr();
195
196     }
197     SliceNode::Ptr trgNode = boost::static_pointer_cast<SliceNode>(trg);                               
198     ParseAPI::Block *trgBlock = trgNode->block();
199     Address trgAddr = trgNode->addr();
200
201     for (auto tit = thunks.begin(); tit != thunks.end(); ++tit) {
202         ParseAPI::Block* thunkBlock = tit->second.block;
203         parsing_printf("\t\tCheck srcAddr at %lx, trgAddr at %lx, thunk at %lx\n", srcAddr, trgAddr, tit->first);
204         if (src != Node::Ptr()) {
205             if (srcBlock == thunkBlock) {
206                 if (srcAddr > tit->first) continue;
207             } else {
208                 if (rf.thunk_ins[thunkBlock].find(srcBlock) == rf.thunk_ins[thunkBlock].end()) continue;
209             }
210         }
211         if (trgBlock == thunkBlock) {
212             if (trgAddr < tit->first) continue;
213         } else {
214             if (rf.thunk_outs[thunkBlock].find(trgBlock) == rf.thunk_outs[thunkBlock].end()) continue;
215         }
216
217         parsing_printf("\t\t\tfind thunk at %lx between the source and the target. Add fact", tit->first);
218         BoundValue *bv = new BoundValue(tit->second.value);
219         bv->Print();
220         curFact->GenFact(VariableAST::create(Variable(AbsRegion(Absloc(tit->second.reg)))), bv);
221     }
222
223
224 }
225
226
227 static bool IsConditionalJump(Instruction::Ptr insn) {
228     entryID id = insn->getOperation().getID();
229
230     if (id == e_jz || id == e_jnz ||
231         id == e_jb || id == e_jnb ||
232         id == e_jbe || id == e_jnbe ||
233         id == e_jb_jnaej_j || id == e_jnb_jae_j ||
234         id == e_jle || id == e_jl ||
235         id == e_jnl || id == e_jnle) return true;
236     return false;
237 }
238
239 BoundFact* BoundFactsCalculator::Meet(Node::Ptr curNode) {
240
241     SliceNode::Ptr node = boost::static_pointer_cast<SliceNode>(curNode);     
242
243     EdgeIterator gbegin, gend;
244     curNode->ins(gbegin, gend);    
245     BoundFact* newFact = NULL;
246     
247     bool first = true;  
248     for (; gbegin != gend; ++gbegin) {
249         TypedSliceEdge::Ptr edge = boost::static_pointer_cast<TypedSliceEdge>(*gbegin); 
250         SliceNode::Ptr srcNode = boost::static_pointer_cast<SliceNode>(edge->source()); 
251         BoundFact *prevFact = GetBoundFact(srcNode);        
252         if (prevFact == NULL) {
253             parsing_printf("\t\tIncoming node %lx has not been calculated yet, ignore it\n", srcNode->addr());
254             continue;
255         } else {            
256             // Otherwise, create a new copy.
257             // We do not want to overwrite the bound fact
258             // of the predecessor
259             prevFact = new BoundFact(*prevFact);
260         }
261 /*
262         if (jumpAddr == 0x805351a) {
263             printf("\tMeet incoming edge from %lx\n", srcNode->addr());
264         }
265 */
266         parsing_printf("\t\tMeet incoming edge from %lx\n", srcNode->addr());
267         parsing_printf("\t\tThe fact from %lx before applying transfer function\n", srcNode->addr());
268         prevFact->Print();
269
270         if (srcNode->assign() && srcNode->assign()->out().absloc().type() == Absloc::Register &&
271             (srcNode->assign()->out().absloc().reg() == x86::zf || srcNode->assign()->out().absloc().reg() == x86_64::zf)) {
272             // zf should be only predecessor of this node
273             parsing_printf("\t\tThe predecessor node is zf assignment!\n");
274             prevFact->SetPredicate(srcNode->assign());      
275         } else if (srcNode->assign() && IsConditionalJump(srcNode->assign()->insn())) {
276             // If the predecessor is a conditional jump,
277             // we can determine bound fact based on the predicate and the edge type
278             parsing_printf("\t\tThe predecessor node is a conditional jump!\n");
279             if (!prevFact->ConditionalJumpBound(srcNode->assign()->insn(), edge->type())) {
280                 fprintf(stderr, "From %lx to %lx\n", srcNode->addr(), node->addr());
281                 assert(0);
282             }
283         } else {
284             // The predecessor is not a conditional jump,
285             // then we can determine buond fact based on the src assignment
286             parsing_printf("\t\tThe predecessor node is normal node\n");
287             if (srcNode->assign()) parsing_printf("\t\t\tentry id %d\n", srcNode->assign()->insn()->getOperation().getID());
288             CalcTransferFunction(srcNode, prevFact);
289         }
290         ThunkBound(prevFact, srcNode, node);
291         parsing_printf("\t\tFact from %lx after applying transfer function\n", srcNode->addr());
292         prevFact->Print();
293         if (first) {
294             // For the first incoming dataflow fact,
295             // we just copy it.
296             // We can do this because if an a-loc
297             // is missing in the fact map, we assume
298             // the a-loc is top. 
299             first = false;
300             newFact = prevFact;
301         } else {
302             newFact->Meet(*prevFact);
303             delete prevFact;
304         }
305     }
306
307
308     if (newFact == NULL) {
309         // This should only happen for nodes without incoming edges;
310         if (firstBlock) {
311             // If the indirect jump is in the entry block
312             // of the function, we assume that rax is in
313             // range [0,8] for analyzing the movaps table.
314             // NEED TO HAVE A SAFE WAY TO DO THIS!!
315             parsing_printf("\t\tApplying entry block rax assumption!\n");
316             newFact = new BoundFact();
317             AST::Ptr axAST;
318             if (func->entry()->obj()->cs()->getAddressWidth() == 8)
319                 axAST = VariableAST::create(Variable(AbsRegion(Absloc(x86_64::rax))));
320             else
321                 // DOES THIS REALLY SHOW UP IN 32-BIT CODE???
322                 axAST = VariableAST::create(Variable(AbsRegion(Absloc(x86::eax))));
323             newFact->GenFact(axAST, new BoundValue(StridedInterval(1,0,8)));
324             ThunkBound(newFact, Node::Ptr(), node);
325
326         }    
327     }
328     return newFact;
329 }
330
331 void BoundFactsCalculator::CalcTransferFunction(Node::Ptr curNode, BoundFact *newFact){
332
333     SliceNode::Ptr node = boost::static_pointer_cast<SliceNode>(curNode);    
334     AbsRegion &ar = node->assign()->out();
335     Instruction::Ptr insn = node->assign()->insn();
336
337     parsing_printf("\t\t\tExpanding assignment %s in instruction at %lx: %s.\n", node->assign()->format().c_str(), node->addr(), insn->format().c_str());
338     
339     pair<AST::Ptr, bool> expandRet = SymEval::expand(node->assign(), false);
340         
341     if (expandRet.first == NULL) {
342         // If the instruction is outside the set of instrutions we
343         // add instruction semantics. We assume this instruction
344         // kills all bound fact.
345 //      parsing_printf("\t\t\t No semantic support for this instruction. Kill all bound fact\n");
346 //      newFact->SetToBottom();
347         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"); 
348         return;
349     }
350     
351     parsing_printf("\t\t\t AST after expanding (without simplify) %s\n", expandRet.first->format().c_str());
352     AST::Ptr calculation = SimplifyAnAST(expandRet.first, insn->size());
353     parsing_printf("\t\t\t AST after expanding %s\n", calculation->format().c_str());
354         
355     BoundCalcVisitor bcv(*newFact, node->block());
356     calculation->accept(&bcv);
357     
358     AST::Ptr outAST = VariableAST::create(Variable(ar));
359     if (bcv.IsResultBounded(calculation)) { 
360         parsing_printf("\t\t\tGenenerate bound fact for %s\n", ar.absloc().format().c_str());
361         newFact->GenFact(outAST, new BoundValue(*bcv.GetResultBound(calculation)));
362     }
363     else {
364         parsing_printf("\t\t\tKill bound fact for %s\n", ar.absloc().format().c_str());
365         newFact->KillFact(outAST);
366     }
367     if (calculation->getID() == AST::V_VariableAST) {
368         // We only track alising between registers
369         parsing_printf("\t\t\t%s and %s are equal\n", calculation->format().c_str(), outAST->format().c_str());
370         newFact->InsertRelation(calculation, outAST, BoundFact::Equal);
371     }
372
373     newFact->AdjustPredicate(outAST, calculation);
374     parsing_printf("\t\t\tCalculating transfer function: Output facts\n");
375     newFact->Print();
376
377 }                                               
378
379 BoundFact* BoundFactsCalculator::GetBoundFact(Node::Ptr node) {
380     auto fit = boundFacts.find(node);
381     if (fit == boundFacts.end())
382         return NULL;
383     else
384         return fit->second;
385 }
386
387 BoundFactsCalculator::~BoundFactsCalculator() {
388     for (auto fit = boundFacts.begin(); fit != boundFacts.end(); ++fit)
389         if (fit->second != NULL)
390             delete fit->second;
391     boundFacts.clear();
392 }
393
394