Stop slicing when we are sure an indirect jump is not a jump table
[dyninst.git] / parseAPI / src / IndirectASTVisitor.C
1 #include "dyntypes.h"
2 #include "IndirectASTVisitor.h"
3 #include "debug_parse.h"
4 #include "CodeObject.h"
5 #include <algorithm>
6
7 using namespace Dyninst::ParseAPI;
8
9 AST::Ptr SimplifyVisitor::visit(DataflowAPI::RoseAST *ast) {
10         unsigned totalChildren = ast->numChildren();
11         for (unsigned i = 0 ; i < totalChildren; ++i) {
12             ast->child(i)->accept(this);
13             ast->setChild(i, SimplifyRoot(ast->child(i), size));
14         }
15         return AST::Ptr();
16 }
17
18 AST::Ptr SimplifyRoot(AST::Ptr ast, uint64_t insnSize) {
19     if (ast->getID() == AST::V_RoseAST) {
20         RoseAST::Ptr roseAST = boost::static_pointer_cast<RoseAST>(ast); 
21         
22         switch (roseAST->val().op) {
23             case ROSEOperation::invertOp:
24                 if (roseAST->child(0)->getID() == AST::V_RoseAST) {
25                     RoseAST::Ptr child = boost::static_pointer_cast<RoseAST>(roseAST->child(0));
26                     if (child->val().op == ROSEOperation::invertOp) return child->child(0);
27                 } else if (roseAST->child(0)->getID() == AST::V_ConstantAST) {
28                     ConstantAST::Ptr child = boost::static_pointer_cast<ConstantAST>(roseAST->child(0));
29                     size_t size = child->val().size;
30                     uint64_t val = child->val().val;
31                     if (size < 64) {
32                         uint64_t mask = (1ULL << size) - 1;
33                         val = (~val) & mask;
34                     } else
35                         val = ~val;
36                     return ConstantAST::create(Constant(val, size));
37                 }
38                 break;
39             case ROSEOperation::extendMSBOp:
40             case ROSEOperation::extractOp:
41             case ROSEOperation::signExtendOp:
42             case ROSEOperation::concatOp:
43                 return roseAST->child(0);
44
45             case ROSEOperation::addOp:
46                 if (roseAST->child(0)->getID() == AST::V_ConstantAST && roseAST->child(1)->getID() == AST::V_ConstantAST) {
47                     ConstantAST::Ptr child0 = boost::static_pointer_cast<ConstantAST>(roseAST->child(0));
48                     ConstantAST::Ptr child1 = boost::static_pointer_cast<ConstantAST>(roseAST->child(1));
49                     uint64_t val = child0->val().val + child1->val().val;
50                     size_t size;
51                     if (child0->val().size > child1->val().size)
52                         size = child0->val().size;
53                     else
54                         size = child1->val().size;
55                     return ConstantAST::create(Constant(val,size));
56                 }
57                 if (roseAST->child(0)->getID() == AST::V_ConstantAST) {
58                     ConstantAST::Ptr child = boost::static_pointer_cast<ConstantAST>(roseAST->child(0));
59                     if (child->val().val == 0) return roseAST->child(1);
60                 }
61                 if (roseAST->child(1)->getID() == AST::V_ConstantAST) {
62                     ConstantAST::Ptr child = boost::static_pointer_cast<ConstantAST>(roseAST->child(1));
63                     if (child->val().val == 0) return roseAST->child(0);
64                 }
65
66                 break;
67             case ROSEOperation::sMultOp:
68             case ROSEOperation::uMultOp:
69                 if (roseAST->child(0)->getID() == AST::V_ConstantAST) {
70                     ConstantAST::Ptr child0 = boost::static_pointer_cast<ConstantAST>(roseAST->child(0));
71                     if (child0->val().val == 1) return roseAST->child(1);
72                 }
73
74                 if (roseAST->child(1)->getID() == AST::V_ConstantAST) {
75                     ConstantAST::Ptr child1 = boost::static_pointer_cast<ConstantAST>(roseAST->child(1));
76                     if (child1->val().val == 1) return roseAST->child(0);
77                 }
78                 break;
79
80             case ROSEOperation::xorOp:
81                 if (roseAST->child(0)->getID() == AST::V_VariableAST && roseAST->child(1)->getID() == AST::V_VariableAST) {
82                     VariableAST::Ptr child0 = boost::static_pointer_cast<VariableAST>(roseAST->child(0)); 
83                     VariableAST::Ptr child1 = boost::static_pointer_cast<VariableAST>(roseAST->child(1)); 
84                     if (child0->val() == child1->val()) {
85                         return ConstantAST::create(Constant(0 , 32));
86                     }
87                 }
88                 break;
89             case ROSEOperation::derefOp:
90                 // Any 8-bit value is bounded in [0,255].
91                 // Need to keep the length of the dereference if it is 8-bit.
92                 // However, dereference longer than 8-bit should be regarded the same.
93                 if (roseAST->val().size == 8)
94                     return ast;
95                 else
96                     return RoseAST::create(ROSEOperation(ROSEOperation::derefOp), ast->child(0));
97                 break;
98             default:
99                 break;
100
101         }
102     } else if (ast->getID() == AST::V_VariableAST) {
103         VariableAST::Ptr varAST = boost::static_pointer_cast<VariableAST>(ast);
104         if (varAST->val().reg.absloc().isPC()) {
105             MachRegister pc = varAST->val().reg.absloc().reg();
106             return ConstantAST::create(Constant(varAST->val().addr + insnSize, getArchAddressWidth(pc.getArchitecture()) * 8));
107         }
108         // We do not care about the address of the a-loc
109         // because we will keep tracking the changes of 
110         // each a-loc. Also, this brings a benefit that
111         // we can directly use ast->isStrictEqual() to 
112         // compare two ast.
113         return VariableAST::create(Variable(varAST->val().reg));
114     } else if (ast->getID() == AST::V_ConstantAST) {
115         ConstantAST::Ptr constAST = boost::static_pointer_cast<ConstantAST>(ast);
116         size_t size = constAST->val().size;
117         uint64_t val = constAST->val().val;     
118         if (size == 32)
119             if (!(val & (1ULL << (size - 1))))
120                 return ConstantAST::create(Constant(val, 64));
121     }
122
123     return ast;
124 }
125
126
127 AST::Ptr SimplifyAnAST(AST::Ptr ast, uint64_t size) {
128     SimplifyVisitor sv(size);
129     ast->accept(&sv);
130     return SimplifyRoot(ast, size);
131 }
132
133 AST::Ptr BoundCalcVisitor::visit(DataflowAPI::RoseAST *ast) {
134     BoundValue *astBound = boundFact.GetBound(ast);
135     if (astBound != NULL) {
136         bound.insert(make_pair(ast, new BoundValue(*astBound)));
137         return AST::Ptr();
138     }
139     unsigned totalChildren = ast->numChildren();
140     for (unsigned i = 0 ; i < totalChildren; ++i) {
141         ast->child(i)->accept(this);
142     }
143     switch (ast->val().op) {
144         case ROSEOperation::addOp:
145             if (IsResultBounded(ast->child(0)) && IsResultBounded(ast->child(1))) {         
146                 BoundValue* val = new BoundValue(*GetResultBound(ast->child(0)));               
147                 val->Add(*GetResultBound(ast->child(1)));
148                 if (*val != BoundValue::top)
149                     bound.insert(make_pair(ast, val));
150             }       
151             break;
152         case ROSEOperation::invertOp:
153             if (IsResultBounded(ast->child(0))) {
154                 BoundValue *val = new BoundValue(*GetResultBound(ast->child(0)));
155                 if (val->tableReadSize)
156                     val->isInverted = true;
157                 else {
158                     val->Invert();
159                 }
160                 if (*val != BoundValue::top)
161                     bound.insert(make_pair(ast,val));
162             }
163             break;
164         case ROSEOperation::andOp: {
165             // For and operation, even one of them is a top,
166             // we may still produce bound result.
167             // For example, top And 0[3,3] => 1[0,3]
168             //
169             // the bound produced by and may be more relaxed than
170             // a cmp bound not found yet. So we only apply and
171             // bound when this is the last attempt
172             if (handleOneByteRead) {
173                 BoundValue *val = NULL;
174                 if (IsResultBounded(ast->child(0)))
175                     val = new BoundValue(*GetResultBound(ast->child(0)));
176                 else
177                     val = new BoundValue(BoundValue::top);
178                 if (IsResultBounded(ast->child(1)))
179                     val->And(GetResultBound(ast->child(1))->interval);
180                 else
181                     val->And(StridedInterval::top);
182                 // the result of an AND operation should not be
183                 // the table lookup. Set all other values to default
184                 val->ClearTableCheck();
185                 if (*val != BoundValue::top)
186                     bound.insert(make_pair(ast, val));
187             }
188             break;
189         }
190         case ROSEOperation::sMultOp:
191         case ROSEOperation::uMultOp:
192             if (IsResultBounded(ast->child(0)) && IsResultBounded(ast->child(1))) {
193                 BoundValue *val = new BoundValue(*GetResultBound(ast->child(0)));
194                 val->Mul(*GetResultBound(ast->child(1)));
195                 if (*val != BoundValue::top)
196                     bound.insert(make_pair(ast, val));
197             }
198             break;
199         case ROSEOperation::shiftLOp:
200             if (IsResultBounded(ast->child(0)) && IsResultBounded(ast->child(1))) {
201                 BoundValue *val = new BoundValue(*GetResultBound(ast->child(0)));
202                 val->ShiftLeft(*GetResultBound(ast->child(1)));
203                 if (*val != BoundValue::top)
204                     bound.insert(make_pair(ast, val));
205             }
206             break;
207         case ROSEOperation::shiftROp:
208             if (IsResultBounded(ast->child(0)) && IsResultBounded(ast->child(1))) {
209                 BoundValue *val = new BoundValue(*GetResultBound(ast->child(0)));
210                 val->ShiftRight(*GetResultBound(ast->child(1)));
211                 if (*val != BoundValue::top)
212                     bound.insert(make_pair(ast, val));
213             }
214             break;
215         case ROSEOperation::derefOp: 
216             if (IsResultBounded(ast->child(0))) {
217                 BoundValue *val = new BoundValue(*GetResultBound(ast->child(0)));
218                 val->MemoryRead(block, derefSize);
219                 if (*val != BoundValue::top)
220                     bound.insert(make_pair(ast, val));
221             } else if (handleOneByteRead && ast->val().size == 8) {
222                 // Any 8-bit value is bounded in [0,255]
223                 // But I should only do this when I know the read 
224                 // itself is not a jump table
225                 bound.insert(make_pair(ast, new BoundValue(StridedInterval(1,0,255))));
226             }
227             break;
228         case ROSEOperation::orOp: 
229             if (IsResultBounded(ast->child(0)) && IsResultBounded(ast->child(1))) {
230                 BoundValue *val = new BoundValue(*GetResultBound(ast->child(0)));
231                 val->Or(*GetResultBound(ast->child(1)));
232                 if (*val != BoundValue::top)
233                     bound.insert(make_pair(ast, val));
234             }
235             break;
236         case ROSEOperation::ifOp:
237             if (IsResultBounded(ast->child(1)) && IsResultBounded(ast->child(2))) {
238                 BoundValue *val = new BoundValue(*GetResultBound(ast->child(1)));
239                 val->Join(*GetResultBound(ast->child(2)));
240                 if (*val != BoundValue::top)
241                     bound.insert(make_pair(ast, val));
242             }
243         default:
244             break;
245     }
246     return AST::Ptr();
247    
248 }
249
250 AST::Ptr BoundCalcVisitor::visit(DataflowAPI::ConstantAST *ast) {
251     const Constant &v = ast->val();
252     int64_t value = v.val;
253     if (v.size != 1 && v.size != 64 && (value & (1ULL << (v.size - 1)))) {
254         // Compute the two complements in bits of v.size
255         // and change it to a negative number
256         value = -(((~value) & ((1ULL << v.size) - 1)) + 1);
257     }
258     bound.insert(make_pair(ast, new BoundValue(value)));
259     return AST::Ptr();
260 }
261
262 AST::Ptr BoundCalcVisitor::visit(DataflowAPI::VariableAST *ast) {
263     BoundValue *astBound = boundFact.GetBound(ast);
264     if (astBound != NULL) 
265         bound.insert(make_pair(ast, new BoundValue(*astBound)));
266     return AST::Ptr();
267 }
268
269 BoundValue* BoundCalcVisitor::GetResultBound(AST::Ptr ast) {
270     if (IsResultBounded(ast)) {
271         return bound.find(ast.get())->second;
272     } else {
273         return NULL;
274     }       
275 }
276
277 BoundCalcVisitor::~BoundCalcVisitor() {
278     for (auto bit = bound.begin(); bit != bound.end(); ++bit)
279         if (bit->second != NULL)
280             delete bit->second;
281     bound.clear();
282 }
283
284
285 AST::Ptr JumpCondVisitor::visit(DataflowAPI::RoseAST *ast) {
286     if (ast->val().op == ROSEOperation::invertOp) {
287         invertFlag = true;
288         return AST::Ptr();
289     }
290     unsigned totalChildren = ast->numChildren();
291     for (unsigned i = 0 ; i < totalChildren; ++i) {
292         ast->child(i)->accept(this);
293     }
294     return AST::Ptr();
295 }
296
297 AST::Ptr ComparisonVisitor::visit(DataflowAPI::RoseAST *ast) {
298     // For cmp type instruction setting zf
299     // Looking like <eqZero?>(<add>(<V([x86_64::rbx])>,<Imm:8>,),)
300     // Assuming ast has been simplified
301     if (ast->val().op == ROSEOperation::equalToZeroOp) {
302         bool minuendIsZero = true;
303         AST::Ptr child = ast->child(0); 
304         if (child->getID() == AST::V_RoseAST) {
305             RoseAST::Ptr childRose = boost::static_pointer_cast<RoseAST>(child);
306             if (childRose->val().op == ROSEOperation::addOp) {
307                 minuendIsZero = false;
308                 subtrahend = childRose->child(0);
309                 minuend = childRose->child(1);
310                 // If the minuend is a constant, then
311                 // the minuend is currently in its two-complement form
312                 if (minuend->getID() == AST::V_ConstantAST) {
313                     ConstantAST::Ptr constAST = boost::static_pointer_cast<ConstantAST>(minuend);
314                     uint64_t val = constAST->val().val;
315                     int size = constAST->val().size;
316                     if (size < 64) 
317                         val = ((~val)+ 1) & ((1ULL << size) - 1);
318                     else if (size == 64)
319                         val = (~val) + 1;
320                     else
321                         parsing_printf("WARNING: constant bit size %d exceeds 64!\n", size);
322                     minuend = ConstantAST::create(Constant(val, size));
323                 } else {
324                     // Otherwise, the minuend ast is in the form of add(invert(minuend), 1)
325                     // Need to extract the real minuend
326                     minuend = minuend->child(0)->child(0);
327                 }
328             }   
329         } 
330         if (minuendIsZero) {
331             // The minuend is 0, thus the add operation is subsume.
332              subtrahend = ast->child(0);
333              minuend = ConstantAST::create(Constant(0));
334         }
335     }
336     return AST::Ptr();
337 }
338
339 AST::Ptr SubstituteAnAST(AST::Ptr ast, const BoundFact::AliasMap &aliasMap) {
340     for (auto ait = aliasMap.begin(); ait != aliasMap.end(); ++ait)
341         if (*ast == *(ait->first)) {
342             return ait->second;
343         }
344     unsigned totalChildren = ast->numChildren();
345     for (unsigned i = 0 ; i < totalChildren; ++i) {
346         ast->setChild(i, SubstituteAnAST(ast->child(i), aliasMap));
347     }
348     return ast;
349
350 }
351
352
353 AST::Ptr DeepCopyAnAST(AST::Ptr ast) {
354     if (ast->getID() == AST::V_RoseAST) {
355         RoseAST::Ptr roseAST = boost::static_pointer_cast<RoseAST>(ast);
356         AST::Children kids;
357         unsigned totalChildren = ast->numChildren();
358         for (unsigned i = 0 ; i < totalChildren; ++i) {
359             kids.push_back(DeepCopyAnAST(ast->child(i)));
360         }
361         return RoseAST::create(ROSEOperation(roseAST->val()), kids);
362     } else if (ast->getID() == AST::V_VariableAST) {
363         VariableAST::Ptr varAST = boost::static_pointer_cast<VariableAST>(ast);
364         return VariableAST::create(Variable(varAST->val()));
365     } else if (ast->getID() == AST::V_ConstantAST) {
366         ConstantAST::Ptr constAST = boost::static_pointer_cast<ConstantAST>(ast);
367         return ConstantAST::create(Constant(constAST->val()));
368     } else if (ast->getID() == AST::V_BottomAST) {
369         BottomAST::Ptr bottomAST = boost::static_pointer_cast<BottomAST>(ast);
370         return BottomAST::create(bottomAST->val());
371     } else {
372         fprintf(stderr, "ast type %d, %s\n", ast->getID(), ast->format().c_str());
373         assert(0);      
374     }
375 }
376
377 AST::Ptr JumpTableFormatVisitor::visit(DataflowAPI::RoseAST *ast) {
378
379     bool findIncorrectFormat = false;
380     if (ast->val().op == ROSEOperation::derefOp) {
381         // We only check the first memory read
382         if (ast->child(0)->getID() == AST::V_RoseAST) {
383             RoseAST::Ptr roseAST = boost::static_pointer_cast<RoseAST>(ast->child(0));
384             if (roseAST->val().op == ROSEOperation::derefOp) {
385                 // Two directly nested memory accesses cannot be jump tables
386                 parsing_printf("Two directly nested memory access, not jump table format\n");
387                 findIncorrectFormat = true;
388             } else if (roseAST->val().op == ROSEOperation::addOp) {
389                 Address tableBase = 0;
390                 if (roseAST->child(0)->getID() == AST::V_ConstantAST) {
391                     ConstantAST::Ptr constAST = boost::static_pointer_cast<ConstantAST>(roseAST->child(0));
392                     tableBase = constAST->val().val;
393                 }
394                 if (roseAST->child(1)->getID() == AST::V_ConstantAST) {
395                     ConstantAST::Ptr constAST = boost::static_pointer_cast<ConstantAST>(roseAST->child(1));
396                     tableBase = constAST->val().val;
397                 }
398                 if (tableBase) {
399                     Architecture arch = b->obj()->cs()->getArch();
400                     if (arch == Arch_x86) {
401                         tableBase &= 0xffffffff;
402                     }
403 #if defined(os_windows)
404                     tableBase -= b->obj()->cs()->loadAddress();
405 #endif
406                     if (!b->obj()->cs()->isValidAddress(tableBase)) {
407                         parsing_printf("\ttableBase 0x%lx invalid, not jump table format\n", tableBase);
408                         findIncorrectFormat = true;
409                     }
410                 }
411             }
412         }
413     }
414     if (!findIncorrectFormat) {
415         unsigned totalChildren = ast->numChildren();
416         for (unsigned i = 0 ; i < totalChildren; ++i) {
417             ast->child(i)->accept(this);
418         }
419     } else format = false;
420     return AST::Ptr();
421 }