Fix inconsistency between ROSE and instructionAPI for operands of ASCII
[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
9 bool BoundFactsCalculator::CalculateBoundedFacts() {    
10     /* We use a dataflow analysis to calculate what registers are bounded 
11      * at each node. The key points of the dataflow analysis are how
12      * to calculate the meet and how to calculate the transfer function.
13      * 1. The meet should be simply an intersection of all the bounded facts 
14      * along all paths. 
15      * 2. To calculate the transfer function, we first get the symbolic expression
16      * of the instrution for the node. Then depending on the instruction operation
17      * and the meet result, we know what are still bounded. For example, loading 
18      * memory is always unbounded; doing and operation on a register with a constant
19      * makes the register bounded. 
20      */
21     
22
23     queue<Node::Ptr> workingList;
24     map<Node::Ptr, int> inQueueLimit;
25
26     NodeIterator nbegin, nend;
27     slice->allNodes(nbegin, nend);
28
29     for (; nbegin != nend; ++nbegin) {
30         workingList.push(*nbegin);
31     }
32
33
34     while (!workingList.empty()) {
35         Node::Ptr curNode = workingList.front();
36         workingList.pop();
37
38         ++inQueueLimit[curNode];
39         if (inQueueLimit[curNode] > IN_QUEUE_LIMIT) continue;
40
41         BoundFact* oldFact = GetBoundFact(curNode);
42         BoundFact* newFact = Meet(curNode);
43         CalcTransferFunction(curNode, newFact);
44
45         if (oldFact == NULL || *oldFact != *newFact) {
46             if (oldFact != NULL) delete oldFact;
47             boundFacts[curNode] = newFact;
48             curNode->outs(nbegin, nend);
49             for (; nbegin != nend; ++nbegin)
50                 workingList.push(*nbegin);
51         }
52     }
53
54     return true;
55 }
56
57
58 void BoundFactsCalculator::ConditionalJumpBound(BoundFact* curFact, Node::Ptr src, Node::Ptr trg) {
59
60     /* This function checks whether any potential table guard is between the two nodes
61      * that we are calculating the meet. Essentially, if there is a conditional jump 
62      * between the two nodes, we know extra bound information.     
63      */   
64
65     ParseAPI::Block *srcBlock;
66     if (src == Node::Ptr()) 
67         srcBlock = func->entry();
68     else {
69         SliceNode::Ptr srcNode = boost::static_pointer_cast<SliceNode>(src);
70         srcBlock = srcNode->block();
71
72     }
73     SliceNode::Ptr trgNode = boost::static_pointer_cast<SliceNode>(trg);                               
74     ParseAPI::Block *trgBlock = trgNode->block();
75
76     for (auto git = guards.begin(); git != guards.end(); ++git) {
77         parsing_printf("Checking guard at %lx\n", git->jmpInsnAddr);
78         if (!git->constantBound) {
79             parsing_printf("\t not a constant bound, skip\n");
80             continue;
81         }           
82
83         ParseAPI::Block *guardBlock = git->block;
84         // Note that the guardBlock and the srcBlock can be the same, 
85         // but since the conditional jump will always be the last instruction
86         // in the block, if they are in the same block, the src can reach the guard
87         if (src != Node::Ptr() && rf.incoming[guardBlock].find(srcBlock) == rf.incoming[guardBlock].end()) {
88             parsing_printf("\t this guard is not between the source block %lx and the target %lx, skip\n", srcBlock->start(), guardBlock->start());
89             continue;
90         }           
91         bool pred_taken = rf.branch_taken[guardBlock].find(trgBlock) != rf.branch_taken[guardBlock].end();
92         bool pred_ft = rf.branch_ft[guardBlock].find(trgBlock) != rf.branch_ft[guardBlock].end();
93         parsing_printf("pred_taken : %d, pred_ft: %d\n", pred_taken, pred_ft);
94         // If both branches reach the trg node, then this conditional jump 
95         // does not bound any variable for the trg node.
96         if (pred_taken ^ pred_ft) {
97             // Here I need to figure out which branch bounds the variable and 
98             // check it is the bounded path that reaches the trg node.
99             AST::Ptr cmpAST;
100             bool boundedOnTakenBranch = git->varSubtrahend ^ git->jumpWhenNoZF;
101             if (   (boundedOnTakenBranch && pred_taken)
102                 // In thic case, we jump when the variable is smaller than the constant.
103                 // So the condition taken path is the path that bounds the value.
104                 || (!boundedOnTakenBranch && pred_ft) ) {
105                 // In thic case, we jump when the variable is larger than the constant.
106                 // So the fallthrough path is the path that bounds the value.
107
108                 if (curFact->cmpBoundFactLive == false || git->cmpBound > curFact->cmpBound) {
109                     curFact->cmpAST = git->cmpAST;
110                     curFact->cmpBound = git->cmpBound;
111                     curFact->cmpBoundFactLive = true;
112                     curFact->cmpUsedRegs = git->usedRegs;
113                 }
114             }
115         }
116     }
117     if (!curFact->cmpBoundFactLive && firstBlock && src == Node::Ptr()) {
118         // If this is indirect jump is in the first block,
119         // it is possible that it is a jump table for a function 
120         // with variable number of arguments. Then the convention
121         // is that al contains the number of argument.
122         MachRegister reg;
123         if (func->obj()->cs()->getAddressWidth() == 8) reg = x86_64::rax; else reg = x86::eax;
124         curFact->cmpAST = VariableAST::create(Variable(Absloc(reg)));
125         curFact->cmpBound = 8;
126         curFact->cmpUsedRegs.insert(reg);
127         curFact->cmpBoundFactLive = true;
128     }
129 }
130
131 void BoundFactsCalculator::ThunkBound(BoundFact* curFact, Node::Ptr src, Node::Ptr trg) {
132
133     // This function checks whether any found thunk is between 
134     // the src node and the trg node. If there is any, then we have 
135     // extra bound information to be added.
136     ParseAPI::Block *srcBlock;
137     Address srcAddr = 0;
138     if (src == Node::Ptr()) 
139         srcBlock = func->entry();
140     else {
141         SliceNode::Ptr srcNode = boost::static_pointer_cast<SliceNode>(src);
142         srcBlock = srcNode->block();
143         srcAddr = srcNode->addr();
144
145     }
146     SliceNode::Ptr trgNode = boost::static_pointer_cast<SliceNode>(trg);                               
147     ParseAPI::Block *trgBlock = trgNode->block();
148     Address trgAddr = trgNode->addr();
149
150     for (auto tit = thunks.begin(); tit != thunks.end(); ++tit) {
151         ParseAPI::Block* thunkBlock = tit->second.block;
152         parsing_printf("Check srcAddr at %lx, trgAddr at %lx, thunk at %lx\n", srcAddr, trgAddr, tit->first);
153         if (src != Node::Ptr()) {
154             if (srcBlock == thunkBlock) {
155                 if (srcAddr > tit->first) continue;
156             } else {
157                 if (rf.thunk_ins[thunkBlock].find(srcBlock) == rf.thunk_ins[thunkBlock].end()) continue;
158             }
159         }
160         if (trgBlock == thunkBlock) {
161             if (trgAddr < tit->first) continue;
162         } else {
163             if (rf.thunk_outs[thunkBlock].find(trgBlock) == rf.thunk_outs[thunkBlock].end()) continue;
164         }
165
166         parsing_printf("\t find thunk at %lx between the source and the target. Add fact", tit->first);
167         BoundValue *bv = new BoundValue(Equal, tit->second.value);
168         bv->Print();
169         curFact->GenFact(Absloc(tit->second.reg), bv);
170     }
171
172
173 }
174
175
176 BoundFact* BoundFactsCalculator::Meet(Node::Ptr curNode) {
177
178     SliceNode::Ptr node = boost::static_pointer_cast<SliceNode>(curNode); 
179     parsing_printf("Calculate Meet for %lx\n", node->addr());
180
181     NodeIterator gbegin, gend;
182     curNode->ins(gbegin, gend);    
183     BoundFact* newFact = new BoundFact();
184
185     if (gbegin != gend) {
186         bool first = true;      
187         for (; gbegin != gend; ++gbegin) {
188             SliceNode::Ptr meetSliceNode = boost::static_pointer_cast<SliceNode>(*gbegin); 
189             BoundFact *prevFact = GetBoundFact(*gbegin);            
190             if (prevFact == NULL) {
191                 parsing_printf("\tIncoming node %lx has not been calculated yet\n", meetSliceNode->addr());
192                 continue;
193             }
194             prevFact = new BoundFact(*prevFact);
195             parsing_printf("\tMeet incoming edge from %lx\n", meetSliceNode->addr());
196
197             ConditionalJumpBound(prevFact, *gbegin, curNode);
198             ThunkBound(prevFact, *gbegin, curNode);
199             if (first) {
200                 first = false;
201                 *newFact = *prevFact;
202             } else {
203                 newFact->Intersect(*prevFact);
204             }
205             parsing_printf("New fact after the change is\n");
206             newFact->Print();
207             delete prevFact;
208
209         }
210     } else {
211         ConditionalJumpBound(newFact, Node::Ptr(), curNode);
212         ThunkBound(newFact, Node::Ptr(), curNode);
213
214         parsing_printf("Meet no incoming nodes\n");
215         newFact->Print();
216     }
217     return newFact;
218 }
219
220 void BoundFactsCalculator::CalcTransferFunction(Node::Ptr curNode, BoundFact *newFact){
221
222     SliceNode::Ptr node = boost::static_pointer_cast<SliceNode>(curNode);    
223     AbsRegion &ar = node->assign()->out();
224     parsing_printf("Expanding assignment %s in instruction at %lx: %s.\n", node->assign()->format().c_str(), node->addr(), node->assign()->insn()->format().c_str());
225     pair<AST::Ptr, bool> expandRet = SymEval::expand(node->assign(), false);
226
227     if (expandRet.first == NULL) {
228         // If the instruction is outside the set of instrutions we
229         // add instruction semantics. We assume this instruction
230         // kills all bound fact.
231         parsing_printf("\t No semantic support for this instruction. Kill all bound fact\n");
232         return;
233     }
234     parsing_printf("\t AST after expanding (without simplify) %s\n", expandRet.first->format().c_str());
235
236     AST::Ptr calculation = SimplifyAnAST(expandRet.first, node->assign()->insn()->size());
237
238     parsing_printf("\t AST after expanding %s\n", calculation->format().c_str());
239     parsing_printf("Calculating transfer function: Input facts\n");
240     newFact->Print();
241
242     BoundCalcVisitor bcv(*newFact);
243     calculation->accept(&bcv);
244
245     if (bcv.IsResultBounded(calculation)) { 
246         parsing_printf("Genenerate bound fact for %s\n", ar.absloc().format().c_str());
247         newFact->GenFact(ar.absloc(), new BoundValue(*bcv.GetResultBound(calculation)));
248     }
249     else {
250         parsing_printf("Kill bound fact for %s\n", ar.absloc().format().c_str());
251         newFact->KillFact(ar.absloc());
252     }
253     parsing_printf("Calculating transfer function: Output facts\n");
254     newFact->Print();
255
256 }                                               
257
258 BoundFact* BoundFactsCalculator::GetBoundFact(Node::Ptr node) {
259     auto fit = boundFacts.find(node);
260     if (fit == boundFacts.end())
261         return NULL;
262     else
263         return fit->second;
264 }
265
266 BoundFactsCalculator::~BoundFactsCalculator() {
267     for (auto fit = boundFacts.begin(); fit != boundFacts.end(); ++fit)
268         if (fit->second != NULL)
269             delete fit->second;
270     boundFacts.clear();
271 }
272
273