Fix the check of whether an instruction is a conditional jump or not
[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             prevFact->ConditionalJumpBound(srcNode->assign()->insn(), edge->type());
171         } else {
172             // The predecessor is not a conditional jump,
173             // then we can determine buond fact based on the src assignment
174             parsing_printf("\t\tThe predecessor node is normal node\n");
175             if (srcNode->assign()) parsing_printf("\t\t\tentry id %d\n", srcNode->assign()->insn()->getOperation().getID());
176             CalcTransferFunction(srcNode, prevFact);
177         }
178         parsing_printf("\t\tFact from %lx fter applying transfer function\n", srcNode->addr());
179         prevFact->Print();
180         if (first) {
181             // For the first incoming dataflow fact,
182             // we just copy it.
183             // We can do this because if an a-loc
184             // is missing in the fact map, we assume
185             // the a-loc is top. 
186             first = false;
187             newFact = prevFact;
188         } else {
189             newFact->Meet(*prevFact);
190             delete prevFact;
191         }
192     }
193
194
195     if (newFact == NULL) {
196         // This should only happen for nodes without incoming edges;
197         if (firstBlock) {
198             // If the indirect jump is in the entry block
199             // of the function, we assume that rax is in
200             // range [0,8] for analyzing the movaps table.
201             // NEED TO HAVE A SAFE WAY TO DO THIS!!
202             parsing_printf("\t\tApplying entry block rax assumption!\n");
203             newFact = new BoundFact();
204             AST::Ptr axAST;
205             if (func->entry()->obj()->cs()->getAddressWidth() == 8)
206                 axAST = VariableAST::create(Variable(AbsRegion(Absloc(x86_64::rax))));
207             else
208                 // DOES THIS REALLY SHOW UP IN 32-BIT CODE???
209                 axAST = VariableAST::create(Variable(AbsRegion(Absloc(x86::eax))));
210             newFact->GenFact(axAST, new BoundValue(StridedInterval(1,0,8)));
211         } else {
212             newFact = new BoundFact();
213         }
214     }
215     return newFact;
216 }
217
218 void BoundFactsCalculator::CalcTransferFunction(Node::Ptr curNode, BoundFact *newFact){
219
220     SliceNode::Ptr node = boost::static_pointer_cast<SliceNode>(curNode);    
221     AbsRegion &ar = node->assign()->out();
222     Instruction::Ptr insn = node->assign()->insn();
223
224     parsing_printf("\t\t\tExpanding assignment %s in instruction at %lx: %s.\n", node->assign()->format().c_str(), node->addr(), insn->format().c_str());
225     
226     pair<AST::Ptr, bool> expandRet = SymEval::expand(node->assign(), false);
227         
228     if (expandRet.first == NULL) {
229         // If the instruction is outside the set of instrutions we
230         // add instruction semantics. We assume this instruction
231         // kills all bound fact.
232         parsing_printf("\t\t\t No semantic support for this instruction. Kill all bound fact\n");
233         newFact->SetToBottom();
234         return;
235     }
236     
237     parsing_printf("\t\t\t AST after expanding (without simplify) %s\n", expandRet.first->format().c_str());
238     AST::Ptr calculation = SimplifyAnAST(expandRet.first, insn->size());
239     parsing_printf("\t\t\t AST after expanding %s\n", calculation->format().c_str());
240         
241     BoundCalcVisitor bcv(*newFact);
242     calculation->accept(&bcv);
243
244     if (bcv.IsResultBounded(calculation)) { 
245         parsing_printf("\t\t\tGenenerate bound fact for %s\n", ar.absloc().format().c_str());
246         newFact->GenFact(VariableAST::create(Variable(ar)), new BoundValue(*bcv.GetResultBound(calculation)));
247     }
248     else {
249         parsing_printf("\t\t\tKill bound fact for %s\n", ar.absloc().format().c_str());
250         newFact->KillFact(VariableAST::create(Variable(ar)));
251     }
252     parsing_printf("\t\t\tCalculating transfer function: Output facts\n");
253     newFact->Print();
254
255 }                                               
256
257 BoundFact* BoundFactsCalculator::GetBoundFact(Node::Ptr node) {
258     auto fit = boundFacts.find(node);
259     if (fit == boundFacts.end())
260         return NULL;
261     else
262         return fit->second;
263 }
264
265 BoundFactsCalculator::~BoundFactsCalculator() {
266     for (auto fit = boundFacts.begin(); fit != boundFacts.end(); ++fit)
267         if (fit->second != NULL)
268             delete fit->second;
269     boundFacts.clear();
270 }
271
272