1. When we find potential indexing variable with table stride being 1, we need to...
[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 #include "SymbolicExpression.h"
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, SymbolicExpression::SimplifyRoot(ast->child(i), addr, keepMultiOne));
14         }
15         return AST::Ptr();
16 }
17
18 AST::Ptr BoundCalcVisitor::visit(DataflowAPI::RoseAST *ast) {
19     StridedInterval *astBound = boundFact.GetBound(ast);
20     if (astBound != NULL) {
21         bound.insert(make_pair(ast, new StridedInterval(*astBound)));
22         return AST::Ptr();
23     }
24     unsigned totalChildren = ast->numChildren();
25     for (unsigned i = 0 ; i < totalChildren; ++i) {
26         ast->child(i)->accept(this);
27     }
28     switch (ast->val().op) {
29         case ROSEOperation::addOp:
30             if (IsResultBounded(ast->child(0)) && IsResultBounded(ast->child(1))) {         
31                 StridedInterval* val = new StridedInterval(*GetResultBound(ast->child(0)));             
32                 val->Add(*GetResultBound(ast->child(1)));
33                 if (*val != StridedInterval::top)
34                     bound.insert(make_pair(ast, val));
35             }       
36             break;
37         case ROSEOperation::invertOp:
38             if (IsResultBounded(ast->child(0))) {
39                 StridedInterval *val = new StridedInterval(*GetResultBound(ast->child(0)));
40                 val->Not();
41                 if (*val != StridedInterval::top)
42                     bound.insert(make_pair(ast,val));
43             }
44             break;
45         case ROSEOperation::andOp: {
46             // For and operation, even one of them is a top,
47             // we may still produce bound result.
48             // For example, top And 0[3,3] => 1[0,3]
49             //
50             // the bound produced by and may be more relaxed than
51             // a cmp bound not found yet. So we only apply and
52             // bound when this is the last attempt
53             if (handleOneByteRead) {
54                 parsing_printf("\tTry to generate bound for AND\n");
55                 StridedInterval *val = NULL;
56                 if (IsResultBounded(ast->child(0)))
57                     val = new StridedInterval(*GetResultBound(ast->child(0)));
58                 else
59                     val = new StridedInterval(StridedInterval::top);
60                 if (IsResultBounded(ast->child(1)))
61                     val->And(*GetResultBound(ast->child(1)));
62                 else
63                     val->And(StridedInterval::top);
64                 // the result of an AND operation should not be
65                 // the table lookup. Set all other values to default
66                 if (*val != StridedInterval::top)
67                     bound.insert(make_pair(ast, val));
68             }
69             break;
70         }
71         case ROSEOperation::sMultOp:
72         case ROSEOperation::uMultOp:
73             if (IsResultBounded(ast->child(0)) && IsResultBounded(ast->child(1))) {
74                 StridedInterval *val = new StridedInterval(*GetResultBound(ast->child(0)));
75                 val->Mul(*GetResultBound(ast->child(1)));
76                 if (*val != StridedInterval::top)
77                     bound.insert(make_pair(ast, val));
78             }
79             break;
80         case ROSEOperation::shiftLOp:
81         case ROSEOperation::rotateLOp:
82             if (IsResultBounded(ast->child(0)) && IsResultBounded(ast->child(1))) {
83                 StridedInterval *val = new StridedInterval(*GetResultBound(ast->child(0)));
84                 val->ShiftLeft(*GetResultBound(ast->child(1)));
85                 if (*val != StridedInterval::top)
86                     bound.insert(make_pair(ast, val));
87             }
88             break;
89         case ROSEOperation::shiftROp:
90         case ROSEOperation::rotateROp:
91             if (IsResultBounded(ast->child(0)) && IsResultBounded(ast->child(1))) {
92                 StridedInterval *val = new StridedInterval(*GetResultBound(ast->child(0)));
93                 val->ShiftRight(*GetResultBound(ast->child(1)));
94                 if (*val != StridedInterval::top)
95                     bound.insert(make_pair(ast, val));
96             }
97             break;
98         case ROSEOperation::derefOp: 
99             if (handleOneByteRead && ast->val().size == 8) {
100                 // Any 8-bit value is bounded in [0,255]
101                 // But I should only do this when I know the read 
102                 // itself is not a jump table
103                 bound.insert(make_pair(ast, new StridedInterval(1,0,255)));
104             }
105             break;
106         case ROSEOperation::orOp: 
107             if (IsResultBounded(ast->child(0)) && IsResultBounded(ast->child(1))) {
108                 StridedInterval *val = new StridedInterval(*GetResultBound(ast->child(0)));
109                 val->Or(*GetResultBound(ast->child(1)));
110                 if (*val != StridedInterval::top)
111                     bound.insert(make_pair(ast, val));
112             }
113             break;
114         case ROSEOperation::ifOp:
115             if (IsResultBounded(ast->child(1)) && IsResultBounded(ast->child(2))) {
116                 StridedInterval *val = new StridedInterval(*GetResultBound(ast->child(1)));
117                 val->Join(*GetResultBound(ast->child(2)));
118                 if (*val != StridedInterval::top)
119                     bound.insert(make_pair(ast, val));
120             }
121         default:
122             break;
123     }
124     return AST::Ptr();
125    
126 }
127
128 AST::Ptr BoundCalcVisitor::visit(DataflowAPI::ConstantAST *ast) {
129     const Constant &v = ast->val();
130     int64_t value = v.val;
131     if (v.size != 1 && v.size != 64 && (value & (1ULL << (v.size - 1)))) {
132         // Compute the two complements in bits of v.size
133         // and change it to a negative number
134         value = -(((~value) & ((1ULL << v.size) - 1)) + 1);
135     }
136     parsing_printf("\t\tGet a constant %ld\n", value);
137     bound.insert(make_pair(ast, new StridedInterval(value)));
138     return AST::Ptr();
139 }
140
141 AST::Ptr BoundCalcVisitor::visit(DataflowAPI::VariableAST *ast) {
142     StridedInterval *astBound = boundFact.GetBound(ast);
143     if (astBound != NULL) 
144         bound.insert(make_pair(ast, new StridedInterval(*astBound)));
145     return AST::Ptr();
146 }
147
148 StridedInterval* BoundCalcVisitor::GetResultBound(AST::Ptr ast) {
149     if (IsResultBounded(ast)) {
150         return bound.find(ast.get())->second;
151     } else {
152         return NULL;
153     }       
154 }
155
156 BoundCalcVisitor::~BoundCalcVisitor() {
157     for (auto bit = bound.begin(); bit != bound.end(); ++bit)
158         if (bit->second != NULL)
159             delete bit->second;
160     bound.clear();
161 }
162
163
164 AST::Ptr JumpCondVisitor::visit(DataflowAPI::RoseAST *ast) {
165     if (ast->val().op == ROSEOperation::invertOp) {
166         invertFlag = true;
167         return AST::Ptr();
168     }
169     unsigned totalChildren = ast->numChildren();
170     for (unsigned i = 0 ; i < totalChildren; ++i) {
171         ast->child(i)->accept(this);
172     }
173     return AST::Ptr();
174 }
175
176 AST::Ptr ComparisonVisitor::visit(DataflowAPI::RoseAST *ast) {
177     // For cmp type instruction setting zf
178     // Looking like <eqZero?>(<add>(<V([x86_64::rbx])>,<Imm:8>,),)
179     // Assuming ast has been simplified
180     unsigned totalChildren = ast->numChildren();
181     for (unsigned i = 0 ; i < totalChildren; ++i) {
182         ast->child(i)->accept(this);
183     }
184     if (ast->val().op == ROSEOperation::equalToZeroOp && !subtrahend) {
185         bool minuendIsZero = true;
186         AST::Ptr child = ast->child(0); 
187         if (child->getID() == AST::V_RoseAST) {
188             RoseAST::Ptr childRose = boost::static_pointer_cast<RoseAST>(child);
189             if (childRose->val().op == ROSEOperation::addOp) {
190                 minuendIsZero = false;
191                 subtrahend = childRose->child(0);
192                 minuend = childRose->child(1);
193                 // If the minuend is a constant, then
194                 // the minuend is currently in its two-complement form
195                 if (minuend->getID() == AST::V_ConstantAST) {
196                     ConstantAST::Ptr constAST = boost::static_pointer_cast<ConstantAST>(minuend);
197                     uint64_t val = constAST->val().val;
198                     int size = constAST->val().size;
199                     if (size < 64) 
200                         val = ((~val)+ 1) & ((1ULL << size) - 1);
201                     else if (size == 64)
202                         val = (~val) + 1;
203                     else
204                         parsing_printf("WARNING: constant bit size %d exceeds 64!\n", size);
205                     minuend = ConstantAST::create(Constant(val, size));
206                 } else if (minuend->getID() == AST::V_RoseAST) {
207                     RoseAST::Ptr sub = boost::static_pointer_cast<RoseAST>(minuend);
208                     minuend = AST::Ptr();
209                     if (sub->val().op == ROSEOperation::addOp && sub->child(0)->getID() == AST::V_RoseAST) {
210                         sub = boost::static_pointer_cast<RoseAST>(sub->child(0));
211                         if (sub->val().op == ROSEOperation::invertOp) {
212                             // Otherwise, the minuend ast is in the form of add(invert(minuend), 1)
213                             // Need to extract the real minuend
214                              minuend = sub->child(0);
215                         }
216                     }
217                 }
218             }   
219             if (childRose->val().op == ROSEOperation::xorOp) {
220                 minuendIsZero = false;
221                 subtrahend = childRose->child(0);
222                 minuend = childRose->child(1);
223             }
224
225         } 
226         if (minuendIsZero) {
227             // The minuend is 0, thus the add operation is subsume.
228              subtrahend = ast->child(0);
229              minuend = ConstantAST::create(Constant(0));
230         }
231     }
232     return AST::Ptr();
233 }
234
235 JumpTableFormatVisitor::JumpTableFormatVisitor(ParseAPI::Block *bl) {
236     b = bl;
237     numOfVar = 0;
238     memoryReadLayer = 0; 
239     findIncorrectFormat = false;
240     findTableBase = false;
241     findIndex = false;
242     firstAdd = true;
243 }
244
245 AST::Ptr JumpTableFormatVisitor::visit(DataflowAPI::RoseAST *ast) {
246     if (ast->val().op == ROSEOperation::derefOp) {
247         memoryReadLayer++;
248         if (memoryReadLayer > 1) {
249             parsing_printf("More than one layer of memory accesses, not jump table format\n");
250             findIncorrectFormat = true;
251             return AST::Ptr();
252         }
253         ast->child(0)->accept(this);
254         memoryReadLayer--;
255         return AST::Ptr();
256     }
257
258     if (ast->val().op == ROSEOperation::addOp && memoryReadLayer > 0 && firstAdd) {
259         firstAdd = false;
260         Address tableBase = 0;
261         if (ast->child(0)->getID() == AST::V_ConstantAST && PotentialIndexing(ast->child(1))) {
262             ConstantAST::Ptr constAST = boost::static_pointer_cast<ConstantAST>(ast->child(0));
263             tableBase = (Address)constAST->val().val;
264         }
265         if (ast->child(1)->getID() == AST::V_ConstantAST && PotentialIndexing(ast->child(0))) {
266             ConstantAST::Ptr constAST = boost::static_pointer_cast<ConstantAST>(ast->child(1));
267             tableBase = (Address)constAST->val().val;
268         }
269         if (tableBase) {
270             Architecture arch = b->obj()->cs()->getArch();
271             if (arch == Arch_x86) {
272                 tableBase &= 0xffffffff;
273             }
274 #if defined(os_windows)
275             tableBase -= b->obj()->cs()->loadAddress();
276 #endif
277             if (!b->obj()->cs()->isValidAddress(tableBase)) {
278                 parsing_printf("\ttableBase 0x%lx invalid, not jump table format\n", tableBase);
279                 findIncorrectFormat = true;
280                 return AST::Ptr();
281             }
282 /*
283             if (!b->obj()->cs()->isReadOnly(tableBase)) {
284                 parsing_printf("\ttableBase 0x%lx not read only, not jump table format\n", tableBase);
285                 findIncorrectFormat = true;
286                 return AST::Ptr();
287             }
288 */          
289             findTableBase = true;
290        }
291     } 
292     
293     if ((ast->val().op == ROSEOperation::uMultOp || 
294          ast->val().op == ROSEOperation::sMultOp || 
295          ast->val().op == ROSEOperation::shiftLOp ||
296          ast->val().op == ROSEOperation::rotateLOp) && memoryReadLayer > 0) {
297         if (ast->child(0)->getID() == AST::V_ConstantAST && ast->child(1)->getID() == AST::V_VariableAST) {
298             ConstantAST::Ptr constAst = boost::static_pointer_cast<ConstantAST>(ast->child(0));    
299             if (!((ast->val().op == ROSEOperation::uMultOp || ast->val().op == ROSEOperation::sMultOp) &&
300                 !findTableBase &&
301                 constAst->val().val == 1)) {
302                 findIndex = true;
303                 numOfVar++;
304                 VariableAST::Ptr varAst = boost::static_pointer_cast<VariableAST>(ast->child(1));
305                 index = varAst->val().reg;
306                 return AST::Ptr();
307             }
308         }
309         if (ast->child(1)->getID() == AST::V_ConstantAST && ast->child(0)->getID() == AST::V_VariableAST) {
310             ConstantAST::Ptr constAst = boost::static_pointer_cast<ConstantAST>(ast->child(1));    
311             if (!((ast->val().op == ROSEOperation::uMultOp || ast->val().op == ROSEOperation::sMultOp) &&
312                 !findTableBase &&
313                 constAst->val().val == 1)) {
314                 findIndex = true;
315                 numOfVar++;
316                 VariableAST::Ptr varAst = boost::static_pointer_cast<VariableAST>(ast->child(0));
317                 index = varAst->val().reg;
318                 return AST::Ptr();
319             }
320         }
321     }
322
323     unsigned totalChildren = ast->numChildren();
324     for (unsigned i = 0 ; i < totalChildren; ++i) {
325         ast->child(i)->accept(this);
326     }
327
328     return AST::Ptr();
329 }
330
331 AST::Ptr JumpTableFormatVisitor::visit(DataflowAPI::VariableAST *) {
332     numOfVar++;
333     return AST::Ptr();
334 }
335
336 bool JumpTableFormatVisitor::PotentialIndexing(AST::Ptr ast) {
337     if (ast->getID() == AST::V_VariableAST) return true;
338     if (ast->getID() == AST::V_RoseAST) {
339         RoseAST::Ptr r = boost::static_pointer_cast<RoseAST>(ast);
340         if (r->val().op == ROSEOperation::uMultOp || 
341             r->val().op == ROSEOperation::sMultOp || 
342             r->val().op == ROSEOperation::shiftLOp || 
343             r->val().op == ROSEOperation::rotateLOp) {
344             if (r->child(0)->getID() == AST::V_RoseAST) {
345                 return false;
346             }
347             return true;
348         }
349         if (r->val().op == ROSEOperation::addOp) {
350             // The index can be subtracted 
351             if (r->child(0)->getID() == AST::V_RoseAST && r->child(1)->getID() == AST::V_ConstantAST) {
352                 RoseAST::Ptr lc = boost::static_pointer_cast<RoseAST>(r->child(0));
353                 ConstantAST::Ptr rc = boost::static_pointer_cast<ConstantAST>(r->child(1));
354                 if (lc->val().op == ROSEOperation::invertOp && rc->val().val == 1) {
355                     return PotentialIndexing(lc->child(0));
356                 }
357             }
358         }
359     }
360     return false;
361 }
362
363 JumpTableReadVisitor::JumpTableReadVisitor(AbsRegion i, int v, CodeSource *c, bool ze, int m) {
364     index = i;
365     indexValue = v;
366     cs = c;
367     isZeroExtend = ze;
368     valid = true;
369     memoryReadSize = m;
370 }
371
372 AST::Ptr JumpTableReadVisitor::visit(DataflowAPI::RoseAST *ast) {
373     unsigned totalChildren = ast->numChildren();
374     for (unsigned i = 0 ; i < totalChildren; ++i) {
375         ast->child(i)->accept(this);
376         if (!valid) return AST::Ptr();
377     }
378
379     // As soon as we do not know the value of one child, we will return.
380     // So, we will always have good values for each child at this point.
381     switch (ast->val().op) {
382         case ROSEOperation::addOp:
383             results.insert(make_pair(ast, results[ast->child(0).get()] + results[ast->child(1).get()]));
384             break;
385         case ROSEOperation::invertOp:
386             results.insert(make_pair(ast, ~results[ast->child(0).get()]));
387             break;
388         case ROSEOperation::andOp: 
389             results.insert(make_pair(ast, results[ast->child(0).get()] & results[ast->child(1).get()]));
390             break;
391         case ROSEOperation::sMultOp:
392         case ROSEOperation::uMultOp:
393             results.insert(make_pair(ast, results[ast->child(0).get()] * results[ast->child(1).get()]));
394             break;
395         case ROSEOperation::shiftLOp:
396         case ROSEOperation::rotateLOp:
397             results.insert(make_pair(ast, results[ast->child(0).get()] << results[ast->child(1).get()]));
398             break;
399         case ROSEOperation::shiftROp:
400         case ROSEOperation::rotateROp:
401             results.insert(make_pair(ast, results[ast->child(0).get()] >> results[ast->child(1).get()]));
402             break;
403         case ROSEOperation::derefOp: {
404                 int64_t v;
405                 bool validRead = PerformMemoryRead(results[ast->child(0).get()], v);
406                 if (!validRead) {
407                     valid = false;
408                     // We encounter an invalid table entry
409                     parsing_printf("WARNING: invalid table entry for index value %ld\n", indexValue);
410                     return AST::Ptr();
411                 }
412                 results.insert(make_pair(ast, v));
413             }
414             break;
415         case ROSEOperation::orOp: 
416             results.insert(make_pair(ast, results[ast->child(0).get()] | results[ast->child(1).get()]));
417             break;
418         default:
419             parsing_printf("WARNING: unhandled operation in the jump table format AST!\n");
420             valid = false;
421             break;
422     }
423     targetAddress = results[ast];
424     if (cs->getAddressWidth() == 4) {
425         targetAddress &= 0xffffffff;
426     }
427 #if defined(os_windows)
428     targetAddress -= cs->loadAddress();
429 #endif
430
431     return AST::Ptr();
432    
433 }
434
435 AST::Ptr JumpTableReadVisitor::visit(DataflowAPI::ConstantAST *ast) {
436     const Constant &v = ast->val();
437     int64_t value = v.val;
438     if (v.size != 1 && v.size != 64 && (value & (1ULL << (v.size - 1)))) {
439         // Compute the two complements in bits of v.size
440         // and change it to a negative number
441         value = -(((~value) & ((1ULL << v.size) - 1)) + 1);
442     }
443     results.insert(make_pair(ast, value));
444     return AST::Ptr();
445 }
446
447
448 AST::Ptr JumpTableReadVisitor::visit(DataflowAPI::VariableAST * var) {
449     if (var->val().reg != index) {
450         // The only variable in the jump table format AST should the index.
451         // If it is not the case, something is wrong
452         parsing_printf("WARNING: the jump table format AST contains a variable that is not the index\n");
453         valid = false;
454     }
455     results.insert(make_pair(var, indexValue));
456     return AST::Ptr();
457 }
458
459
460 bool JumpTableReadVisitor::PerformMemoryRead(Address addr, int64_t &v) {
461     int addressWidth = cs->getAddressWidth();
462     if (addressWidth == 4) {
463         addr &= 0xffffffff;
464     }
465
466 #if defined(os_windows)
467     addr -= cs->loadAddress();
468 #endif
469     if (!cs->isCode(addr) && !cs->isData(addr)) return false;
470 //    if (!cs->isReadOnly(addr)) return false;
471     switch (memoryReadSize) {
472         case 8:
473             v = *(const uint64_t *) cs->getPtrToInstruction(addr);
474             break;
475         case 4:
476             v = *(const uint32_t *) cs->getPtrToInstruction(addr);
477             if (isZeroExtend) break;
478             if ((addressWidth == 8) && (v & 0x80000000)) {
479                 v |= SIGNEX_64_32;
480             }
481             break;
482         case 2:
483             v = *(const uint16_t *) cs->getPtrToInstruction(addr);
484             if (isZeroExtend) break;
485             if ((addressWidth == 8) && (v & 0x8000)) {
486                 v |= SIGNEX_64_16;
487             }
488             if ((addressWidth == 4) && (v & 0x8000)) {
489                 v |= SIGNEX_32_16;
490             }
491             break;
492         case 1:
493             v = *(const uint8_t *) cs->getPtrToInstruction(addr);
494             if (isZeroExtend) break;
495             if ((addressWidth == 8) && (v & 0x80)) {
496                 v |= SIGNEX_64_8;
497             }
498             if ((addressWidth == 4) && (v & 0x80)) {
499                 v |= SIGNEX_32_8;
500             }
501             break;          
502         default:
503             parsing_printf("Invalid memory read size %d\n", memoryReadSize);
504             return false;
505     }
506     return true;
507 }