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