Refactor code so that each major class has a .h file and .C file
[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 bool BoundFactsCalculator::CalculateBoundedFacts() {    
14     /* We use a dataflow analysis to calculate what registers are bounded 
15      * at each node. The key points of the dataflow analysis are how
16      * to calculate the meet and how to calculate the transfer function.
17      * 1. The meet should be simply an intersection of all the bounded facts 
18      * along all paths. 
19      * 2. To calculate the transfer function, we first get the symbolic expression
20      * of the instrution for the node. Then depending on the instruction operation
21      * and the meet result, we know what are still bounded. For example, loading 
22      * memory is always unbounded; doing and operation on a register with a constant
23      * makes the register bounded. 
24      */
25     
26
27     queue<Node::Ptr> workingList;
28     set<Node::Ptr> inQueue;
29     map<Node::Ptr, int> inQueueLimit;
30
31     NodeIterator nbegin, nend;
32     slice->allNodes(nbegin, nend);
33
34     for (; nbegin != nend; ++nbegin) {
35         workingList.push(*nbegin);
36         inQueue.insert(*nbegin);
37     }
38
39
40     while (!workingList.empty()) {
41         Node::Ptr curNode = workingList.front();
42         workingList.pop();
43         inQueue.erase(curNode);
44         
45         SliceNode::Ptr node = boost::static_pointer_cast<SliceNode>(curNode);
46
47         ++inQueueLimit[curNode];
48         if (inQueueLimit[curNode] > IN_QUEUE_LIMIT) continue;
49
50         BoundFact* oldFact = GetBoundFact(curNode);
51         parsing_printf("Calculate Meet for %lx", node->addr());
52         if (node->assign())
53             parsing_printf(", insn: %s\n", node->assign()->insn()->format().c_str());
54         else
55             parsing_printf(", the VirtualExit node\n");
56         parsing_printf("\tOld fact for %lx:\n", node->addr());
57         if (oldFact == NULL) parsing_printf("\t\t do not exist\n"); else oldFact->Print();
58         BoundFact* newFact = Meet(curNode);
59         parsing_printf("\tNew fact at %lx\n", node->addr());
60         newFact->Print();
61         if (oldFact == NULL || *oldFact != *newFact) {
62             parsing_printf("\tFacts change!\n");
63             if (oldFact != NULL) delete oldFact;
64             boundFacts[curNode] = newFact;
65             curNode->outs(nbegin, nend);
66             for (; nbegin != nend; ++nbegin)
67                 if (inQueue.find(*nbegin) == inQueue.end()) {
68                     workingList.push(*nbegin);
69                     inQueue.insert(*nbegin);
70                 }
71         } else parsing_printf("\tFacts do not change!\n");
72     }
73
74     return true;
75 }
76
77
78
79
80 void BoundFactsCalculator::ThunkBound(BoundFact* curFact, Node::Ptr src, Node::Ptr trg) {
81
82     // This function checks whether any found thunk is between 
83     // the src node and the trg node. If there is any, then we have 
84     // extra bound information to be added.
85     ParseAPI::Block *srcBlock;
86     Address srcAddr = 0;
87     if (src == Node::Ptr()) 
88         srcBlock = func->entry();
89     else {
90         SliceNode::Ptr srcNode = boost::static_pointer_cast<SliceNode>(src);
91         srcBlock = srcNode->block();
92         srcAddr = srcNode->addr();
93
94     }
95     SliceNode::Ptr trgNode = boost::static_pointer_cast<SliceNode>(trg);                               
96     ParseAPI::Block *trgBlock = trgNode->block();
97     Address trgAddr = trgNode->addr();
98
99     for (auto tit = thunks.begin(); tit != thunks.end(); ++tit) {
100         ParseAPI::Block* thunkBlock = tit->second.block;
101         parsing_printf("\t\tCheck srcAddr at %lx, trgAddr at %lx, thunk at %lx\n", srcAddr, trgAddr, tit->first);
102         if (src != Node::Ptr()) {
103             if (srcBlock == thunkBlock) {
104                 if (srcAddr > tit->first) continue;
105             } else {
106                 if (rf.thunk_ins[thunkBlock].find(srcBlock) == rf.thunk_ins[thunkBlock].end()) continue;
107             }
108         }
109         if (trgBlock == thunkBlock) {
110             if (trgAddr < tit->first) continue;
111         } else {
112             if (rf.thunk_outs[thunkBlock].find(trgBlock) == rf.thunk_outs[thunkBlock].end()) continue;
113         }
114
115         parsing_printf("\t\t\tfind thunk at %lx between the source and the target. Add fact", tit->first);
116         BoundValue *bv = new BoundValue(tit->second.value);
117         bv->Print();
118         curFact->GenFact(VariableAST::create(Variable(AbsRegion(Absloc(tit->second.reg)))), bv);
119     }
120
121
122 }
123
124
125 static bool IsConditionalJump(Instruction::Ptr insn) {
126     entryID id = insn->getOperation().getID();
127
128     if (id == e_jz || id == e_jnz ||
129         id == e_jb || id == e_jnb ||
130         id == e_jbe || id == e_jnbe ||
131         id == e_jb_jnaej_j || id == e_jnb_jae_j ||
132         id == e_jle || id == e_jl ||
133         id == e_jnl || id == e_jnle) return true;
134     return false;
135 }
136
137 BoundFact* BoundFactsCalculator::Meet(Node::Ptr curNode) {
138
139     SliceNode::Ptr node = boost::static_pointer_cast<SliceNode>(curNode);     
140
141     EdgeIterator gbegin, gend;
142     curNode->ins(gbegin, gend);    
143     BoundFact* newFact = NULL;
144     
145     bool first = true;  
146     for (; gbegin != gend; ++gbegin) {
147         TypedSliceEdge::Ptr edge = boost::static_pointer_cast<TypedSliceEdge>(*gbegin); 
148         SliceNode::Ptr srcNode = boost::static_pointer_cast<SliceNode>(edge->source()); 
149         BoundFact *prevFact = GetBoundFact(srcNode);        
150         
151         if (prevFact == NULL) {
152             parsing_printf("\t\tIncoming node %lx has not been calculated yet, default to top\n", srcNode->addr());
153             prevFact = new BoundFact();
154         } else {            
155             // Otherwise, create a new copy.
156             // We do not want to overwrite the bound fact
157             // of the predecessor
158             prevFact = new BoundFact(*prevFact);
159         }
160         parsing_printf("\t\tMeet incoming edge from %lx\n", srcNode->addr());
161         parsing_printf("\t\tThe fact from %lx before applying transfer function\n", srcNode->addr());
162         prevFact->Print();
163
164         if (srcNode->assign() && srcNode->assign()->out().absloc().type() == Absloc::Register &&
165             (srcNode->assign()->out().absloc().reg() == x86::zf || srcNode->assign()->out().absloc().reg() == x86_64::zf)) {
166             // zf should be only predecessor of this node
167             parsing_printf("\t\tThe predecessor node is zf assignment!\n");
168             prevFact->SetPredicate(srcNode->assign());      
169         } else if (srcNode->assign() && IsConditionalJump(srcNode->assign()->insn())) {
170             // If the predecessor is a conditional jump,
171             // we can determine bound fact based on the predicate and the edge type
172             parsing_printf("\t\tThe predecessor node is a conditional jump!\n");
173             if (!prevFact->ConditionalJumpBound(srcNode->assign()->insn(), edge->type())) {
174                 fprintf(stderr, "From %lx to %lx\n", srcNode->addr(), node->addr());
175                 assert(0);
176             }
177         } else {
178             // The predecessor is not a conditional jump,
179             // then we can determine buond fact based on the src assignment
180             parsing_printf("\t\tThe predecessor node is normal node\n");
181             if (srcNode->assign()) parsing_printf("\t\t\tentry id %d\n", srcNode->assign()->insn()->getOperation().getID());
182             CalcTransferFunction(srcNode, prevFact);
183         }
184         ThunkBound(prevFact, srcNode, node);
185         parsing_printf("\t\tFact from %lx after applying transfer function\n", srcNode->addr());
186         prevFact->Print();
187         if (first) {
188             // For the first incoming dataflow fact,
189             // we just copy it.
190             // We can do this because if an a-loc
191             // is missing in the fact map, we assume
192             // the a-loc is top. 
193             first = false;
194             newFact = prevFact;
195         } else {
196             newFact->Meet(*prevFact);
197             delete prevFact;
198         }
199     }
200
201
202     if (newFact == NULL) {
203         // This should only happen for nodes without incoming edges;
204         if (firstBlock) {
205             // If the indirect jump is in the entry block
206             // of the function, we assume that rax is in
207             // range [0,8] for analyzing the movaps table.
208             // NEED TO HAVE A SAFE WAY TO DO THIS!!
209             parsing_printf("\t\tApplying entry block rax assumption!\n");
210             newFact = new BoundFact();
211             AST::Ptr axAST;
212             if (func->entry()->obj()->cs()->getAddressWidth() == 8)
213                 axAST = VariableAST::create(Variable(AbsRegion(Absloc(x86_64::rax))));
214             else
215                 // DOES THIS REALLY SHOW UP IN 32-BIT CODE???
216                 axAST = VariableAST::create(Variable(AbsRegion(Absloc(x86::eax))));
217             newFact->GenFact(axAST, new BoundValue(StridedInterval(1,0,8)));
218         } else {
219             newFact = new BoundFact();
220         }
221         ThunkBound(newFact, Node::Ptr(), node);
222     }
223     return newFact;
224 }
225
226 void BoundFactsCalculator::CalcTransferFunction(Node::Ptr curNode, BoundFact *newFact){
227
228     SliceNode::Ptr node = boost::static_pointer_cast<SliceNode>(curNode);    
229     AbsRegion &ar = node->assign()->out();
230     Instruction::Ptr insn = node->assign()->insn();
231
232     parsing_printf("\t\t\tExpanding assignment %s in instruction at %lx: %s.\n", node->assign()->format().c_str(), node->addr(), insn->format().c_str());
233     
234     pair<AST::Ptr, bool> expandRet = SymEval::expand(node->assign(), false);
235         
236     if (expandRet.first == NULL) {
237         // If the instruction is outside the set of instrutions we
238         // add instruction semantics. We assume this instruction
239         // kills all bound fact.
240         parsing_printf("\t\t\t No semantic support for this instruction. Kill all bound fact\n");
241         newFact->SetToBottom();
242         return;
243     }
244     
245     parsing_printf("\t\t\t AST after expanding (without simplify) %s\n", expandRet.first->format().c_str());
246     AST::Ptr calculation = SimplifyAnAST(expandRet.first, insn->size());
247     parsing_printf("\t\t\t AST after expanding %s\n", calculation->format().c_str());
248         
249     BoundCalcVisitor bcv(*newFact);
250     calculation->accept(&bcv);
251
252     if (bcv.IsResultBounded(calculation)) { 
253         parsing_printf("\t\t\tGenenerate bound fact for %s\n", ar.absloc().format().c_str());
254         newFact->GenFact(VariableAST::create(Variable(ar)), new BoundValue(*bcv.GetResultBound(calculation)));
255     }
256     else {
257         parsing_printf("\t\t\tKill bound fact for %s\n", ar.absloc().format().c_str());
258         newFact->KillFact(VariableAST::create(Variable(ar)));
259     }
260     parsing_printf("\t\t\tCalculating transfer function: Output facts\n");
261     newFact->Print();
262
263 }                                               
264
265 BoundFact* BoundFactsCalculator::GetBoundFact(Node::Ptr node) {
266     auto fit = boundFacts.find(node);
267     if (fit == boundFacts.end())
268         return NULL;
269     else
270         return fit->second;
271 }
272
273 BoundFactsCalculator::~BoundFactsCalculator() {
274     for (auto fit = boundFacts.begin(); fit != boundFacts.end(); ++fit)
275         if (fit->second != NULL)
276             delete fit->second;
277     boundFacts.clear();
278 }
279
280