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