Potential fixes needed for relocating libraries (#754)
[dyninst.git] / parseAPI / src / SymbolicExpression.C
1 #include "SymbolicExpression.h"
2 #include "SymEval.h"
3 #include "Absloc.h"
4 #include "debug_parse.h"
5 #include "IndirectASTVisitor.h"
6 #include "CFG.h"
7 #include "CodeSource.h"
8 #include "CodeObject.h"
9 using namespace std;
10 using namespace Dyninst;
11 using namespace Dyninst::ParseAPI;
12 using namespace Dyninst::DataflowAPI;
13
14 bool SymbolicExpression::ReadMemory(Address addr, uint64_t &v, int ) {
15     int addressWidth = cs->getAddressWidth();
16     if (addressWidth == 4) {
17         addr &= 0xffffffff;
18     }
19
20 #if defined(os_windows)
21     addr -= cs->loadAddress();
22 #endif
23     if (!cs->isReadOnly(addr)) return false;
24     v = *(const uint64_t *) cs->getPtrToInstruction(addr);
25 /*
26     switch (memoryReadSize) {
27         case 0:
28         case 8:
29             v = *(const uint64_t *) cs->getPtrToInstruction(addr);
30             break;
31         case 4:
32             v = *(const uint32_t *) cs->getPtrToInstruction(addr);
33             break;
34         case 2:
35             v = *(const uint16_t *) cs->getPtrToInstruction(addr);
36             break;
37         case 1:
38             v = *(const uint8_t *) cs->getPtrToInstruction(addr);
39             break;          
40         default:
41             parsing_printf("Invalid memory read size %d\n", memoryReadSize);
42             return false;
43     }
44 */
45     return true;
46 }
47
48 AST::Ptr SymbolicExpression::SimplifyRoot(AST::Ptr ast, Address addr, bool keepMultiOne) {
49     if (ast->getID() == AST::V_RoseAST) {
50         RoseAST::Ptr roseAST = boost::static_pointer_cast<RoseAST>(ast); 
51         
52         switch (roseAST->val().op) {
53             case ROSEOperation::invertOp:
54                 if (roseAST->child(0)->getID() == AST::V_RoseAST) {
55                     RoseAST::Ptr child = boost::static_pointer_cast<RoseAST>(roseAST->child(0));
56                     if (child->val().op == ROSEOperation::invertOp) return child->child(0);
57                 } else if (roseAST->child(0)->getID() == AST::V_ConstantAST) {
58                     ConstantAST::Ptr child = boost::static_pointer_cast<ConstantAST>(roseAST->child(0));
59                     size_t size = child->val().size;
60                     uint64_t val = child->val().val;
61                     if (size < 64) {
62                         uint64_t mask = (1ULL << size) - 1;
63                         val = (~val) & mask;
64                     } else
65                         val = ~val;
66                     return ConstantAST::create(Constant(val, size));
67                 }
68                 break;
69             case ROSEOperation::extendMSBOp: {
70                 return roseAST->child(0);
71             }
72             case ROSEOperation::extractOp: {
73                 if (roseAST->child(0)->getID() == AST::V_ConstantAST) {
74                     size_t size = roseAST->val().size;
75                     ConstantAST::Ptr child0 = boost::static_pointer_cast<ConstantAST>(roseAST->child(0));
76                     return ConstantAST::create(Constant(child0->val().val,size));
77                 }
78                 return roseAST->child(0);
79             }
80             case ROSEOperation::signExtendOp: {
81                 if (roseAST->child(0)->getID() == AST::V_ConstantAST && roseAST->child(1)->getID() == AST::V_ConstantAST) {
82                     ConstantAST::Ptr child0 = boost::static_pointer_cast<ConstantAST>(roseAST->child(0));
83                     ConstantAST::Ptr child1 = boost::static_pointer_cast<ConstantAST>(roseAST->child(1));
84                     uint64_t val = child0->val().val;
85                     if (val & (1 << (child0->val().size - 1))) {
86                         switch (child0->val().size) {
87                            case 16:
88                                val = val | SIGNEX_64_16;
89                                break;
90                            case 32:
91                                val = val | SIGNEX_64_32;
92                                break;
93                            default:
94                                break;
95                         }
96                     } 
97                     size_t size = child1->val().val;
98                     return ConstantAST::create(Constant(val,size));
99                 }                   
100                 return roseAST->child(0);
101             }
102             case ROSEOperation::concatOp: {         
103                 if (roseAST->child(0)->getID() == AST::V_ConstantAST && roseAST->child(1)->getID() == AST::V_ConstantAST) {
104                     ConstantAST::Ptr child0 = boost::static_pointer_cast<ConstantAST>(roseAST->child(0));
105                     ConstantAST::Ptr child1 = boost::static_pointer_cast<ConstantAST>(roseAST->child(1));
106                     uint64_t val = (child1->val().val << child0->val().size) + child0->val().val;
107                     size_t size = child1->val().size + child0->val().size;
108                     return ConstantAST::create(Constant(val,size));
109                 }                   
110                 if (roseAST->child(1)->getID() == AST::V_ConstantAST) {
111                     ConstantAST::Ptr child1 = boost::static_pointer_cast<ConstantAST>(roseAST->child(1));
112                     if (child1->val().val == 0) {
113                         return roseAST->child(0);
114                     }
115                 }
116                 if (roseAST->child(1)->getID() == AST::V_RoseAST) {
117                     RoseAST::Ptr child1 = boost::static_pointer_cast<RoseAST>(roseAST->child(1));
118                     if (child1->val().op == ROSEOperation::ifOp) break;
119                 }
120                 return roseAST->child(0);
121             }
122             case ROSEOperation::addOp:
123                 // We simplify the addition as much as we can
124                 // Case 1: two constants
125                 if (roseAST->child(0)->getID() == AST::V_ConstantAST && roseAST->child(1)->getID() == AST::V_ConstantAST) {
126                     ConstantAST::Ptr child0 = boost::static_pointer_cast<ConstantAST>(roseAST->child(0));
127                     ConstantAST::Ptr child1 = boost::static_pointer_cast<ConstantAST>(roseAST->child(1));
128                     uint64_t val = child0->val().val + child1->val().val;
129                     size_t size;
130                     if (child0->val().size > child1->val().size)
131                         size = child0->val().size;
132                     else
133                         size = child1->val().size;
134                     return ConstantAST::create(Constant(val,size));
135                 }
136                 // Case 2: anything adding zero stays the same
137                 if (roseAST->child(0)->getID() == AST::V_ConstantAST) {
138                     ConstantAST::Ptr child = boost::static_pointer_cast<ConstantAST>(roseAST->child(0));
139                     if (child->val().val == 0) return roseAST->child(1);
140                 }
141                 if (roseAST->child(1)->getID() == AST::V_ConstantAST) {
142                     ConstantAST::Ptr child = boost::static_pointer_cast<ConstantAST>(roseAST->child(1));
143                     if (child->val().val == 0) return roseAST->child(0);
144                 }
145                 // Case 3: if v + v * c = v * (c+1), where v is a variable and c is a constant
146                 if (roseAST->child(0)->getID() == AST::V_VariableAST && roseAST->child(1)->getID() == AST::V_RoseAST) {
147                     RoseAST::Ptr rOp = boost::static_pointer_cast<RoseAST>(roseAST->child(1));
148                     if (rOp->val().op == ROSEOperation::uMultOp || rOp->val().op == ROSEOperation::sMultOp) {
149                         if (rOp->child(0)->getID() == AST::V_VariableAST && rOp->child(1)->getID() == AST::V_ConstantAST) {
150                             VariableAST::Ptr varAST1 = boost::static_pointer_cast<VariableAST>(roseAST->child(0));
151                             VariableAST::Ptr varAST2 = boost::static_pointer_cast<VariableAST>(rOp->child(0));
152                             if (varAST1->val().reg == varAST2->val().reg) {
153                                 ConstantAST::Ptr oldC = boost::static_pointer_cast<ConstantAST>(rOp->child(1));
154                                 ConstantAST::Ptr newC = ConstantAST::create(Constant(oldC->val().val + 1, oldC->val().size));
155                                 RoseAST::Ptr newRoot = RoseAST::create(ROSEOperation(rOp->val()), varAST1, newC);
156                                 return newRoot;
157                             }
158                         }
159                     }
160                 } 
161                 break;
162             case ROSEOperation::sMultOp:
163             case ROSEOperation::uMultOp:
164                 if (roseAST->child(0)->getID() == AST::V_ConstantAST && roseAST->child(1)->getID() == AST::V_ConstantAST) {
165                     ConstantAST::Ptr child0 = boost::static_pointer_cast<ConstantAST>(roseAST->child(0));
166                     ConstantAST::Ptr child1 = boost::static_pointer_cast<ConstantAST>(roseAST->child(1));
167                     return ConstantAST::create(Constant(child0->val().val * child1->val().val, 64));
168                 }
169                 if (roseAST->child(0)->getID() == AST::V_ConstantAST) {
170                     ConstantAST::Ptr child0 = boost::static_pointer_cast<ConstantAST>(roseAST->child(0));
171                     if (child0->val().val == 1 && !keepMultiOne) return roseAST->child(1);
172                 }
173
174                 if (roseAST->child(1)->getID() == AST::V_ConstantAST) {
175                     ConstantAST::Ptr child1 = boost::static_pointer_cast<ConstantAST>(roseAST->child(1));
176                     if (child1->val().val == 1 && !keepMultiOne) return roseAST->child(0);
177                 }
178                 break;
179             case ROSEOperation::xorOp:
180                 if (roseAST->child(0)->getID() == AST::V_VariableAST && roseAST->child(1)->getID() == AST::V_VariableAST) {
181                     VariableAST::Ptr child0 = boost::static_pointer_cast<VariableAST>(roseAST->child(0)); 
182                     VariableAST::Ptr child1 = boost::static_pointer_cast<VariableAST>(roseAST->child(1)); 
183                     if (child0->val() == child1->val()) {
184                         return ConstantAST::create(Constant(0 , 32));
185                     }
186                 }
187                 break;
188             case ROSEOperation::derefOp:
189                 // Any 8-bit value is bounded in [0,255].
190                 // Need to keep the length of the dereference if it is 8-bit.
191                 // However, dereference longer than 8-bit should be regarded the same.
192                 if (roseAST->child(0)->getID() == AST::V_ConstantAST) {
193                     uint64_t val = 0;
194                     ConstantAST::Ptr c = boost::static_pointer_cast<ConstantAST>(roseAST->child(0));
195                     Address addr = c->val().val;
196                     if (ReadMemory(addr, val, roseAST->val().size / 8)) {
197                         return ConstantAST::create(Constant(val, 64));
198                     }
199                 }
200                 if (roseAST->val().size == 8)
201                     return ast;
202                 else
203                     return RoseAST::create(ROSEOperation(ROSEOperation::derefOp), ast->child(0));
204                 break;
205             case ROSEOperation::shiftLOp:
206             case ROSEOperation::rotateLOp:
207                 if (roseAST->child(0)->getID() == AST::V_ConstantAST && roseAST->child(1)->getID() == AST::V_ConstantAST) {
208                     ConstantAST::Ptr child0 = boost::static_pointer_cast<ConstantAST>(roseAST->child(0));
209                     ConstantAST::Ptr child1 = boost::static_pointer_cast<ConstantAST>(roseAST->child(1));
210                     return ConstantAST::create(Constant(child0->val().val << child1->val().val, 64));
211                 }
212                 if (roseAST->child(1)->getID() == AST::V_ConstantAST) {
213                     parsing_printf("keep multi one %d\n", keepMultiOne);
214                     ConstantAST::Ptr child1 = boost::static_pointer_cast<ConstantAST>(roseAST->child(1));
215                     if (child1->val().val == 0 && !keepMultiOne) return roseAST->child(0);
216                 }
217                 break;
218             case ROSEOperation::andOp:
219                 if (roseAST->child(0)->getID() == AST::V_ConstantAST && roseAST->child(1)->getID() == AST::V_ConstantAST) {
220                     ConstantAST::Ptr child0 = boost::static_pointer_cast<ConstantAST>(roseAST->child(0));
221                     ConstantAST::Ptr child1 = boost::static_pointer_cast<ConstantAST>(roseAST->child(1));
222                     return ConstantAST::create(Constant(child0->val().val & child1->val().val, 64));
223                 }
224                 break;
225             case ROSEOperation::orOp:
226                 if (roseAST->child(0)->getID() == AST::V_ConstantAST && roseAST->child(1)->getID() == AST::V_ConstantAST) {
227                     ConstantAST::Ptr child0 = boost::static_pointer_cast<ConstantAST>(roseAST->child(0));
228                     ConstantAST::Ptr child1 = boost::static_pointer_cast<ConstantAST>(roseAST->child(1));
229                     return ConstantAST::create(Constant(child0->val().val | child1->val().val, 64));
230                 }
231                 break;
232             case ROSEOperation::ifOp:
233                 if (roseAST->child(0)->getID() == AST::V_ConstantAST) {
234                     ConstantAST::Ptr c = boost::static_pointer_cast<ConstantAST>(roseAST->child(0));
235                     if (c->val().val != 0) {
236                         return roseAST->child(1);
237                     } else {
238                         return roseAST->child(2);
239                     }
240
241                 }
242                 break;
243             default:
244                 break;
245
246         }
247     } else if (ast->getID() == AST::V_VariableAST) {
248         VariableAST::Ptr varAST = boost::static_pointer_cast<VariableAST>(ast);
249         if (varAST->val().reg.absloc().isPC()) {
250             MachRegister pc = varAST->val().reg.absloc().reg();     
251             return ConstantAST::create(Constant(addr, getArchAddressWidth(pc.getArchitecture()) * 8));
252         }
253         // We do not care about the address of the a-loc
254         // because we will keep tracking the changes of 
255         // each a-loc. Also, this brings a benefit that
256         // we can directly use ast->isStrictEqual() to 
257         // compare two ast.
258         return VariableAST::create(Variable(varAST->val().reg));
259     } else if (ast->getID() == AST::V_ConstantAST) {
260         ConstantAST::Ptr constAST = boost::static_pointer_cast<ConstantAST>(ast);
261         size_t size = constAST->val().size;
262         uint64_t val = constAST->val().val;     
263         if (size == 32)
264             if (!(val & (1ULL << (size - 1))))
265                 return ConstantAST::create(Constant(val, 64));
266     }
267
268     return ast;
269 }
270
271
272 AST::Ptr SymbolicExpression::SimplifyAnAST(AST::Ptr ast, Address addr, bool keepMultiOne) {
273     SimplifyVisitor sv(addr, keepMultiOne, *this);
274     ast->accept(&sv);
275     return SimplifyRoot(ast, addr, keepMultiOne);
276 }
277
278 bool SymbolicExpression::ContainAnAST(AST::Ptr root, AST::Ptr check) {
279     if (*root == *check) return true;
280     bool ret = false;
281     unsigned totalChildren = root->numChildren();
282     for (unsigned i = 0 ; i < totalChildren && !ret; ++i) {
283         ret |= ContainAnAST(root->child(i), check);
284     }
285     return ret;
286 }
287
288
289 AST::Ptr SymbolicExpression::DeepCopyAnAST(AST::Ptr ast) {
290     if (ast->getID() == AST::V_RoseAST) {
291         RoseAST::Ptr roseAST = boost::static_pointer_cast<RoseAST>(ast);
292         AST::Children kids;
293         unsigned totalChildren = ast->numChildren();
294         for (unsigned i = 0 ; i < totalChildren; ++i) {
295             kids.push_back(DeepCopyAnAST(ast->child(i)));
296         }
297         return RoseAST::create(ROSEOperation(roseAST->val()), kids);
298     } else if (ast->getID() == AST::V_VariableAST) {
299         VariableAST::Ptr varAST = boost::static_pointer_cast<VariableAST>(ast);
300         return VariableAST::create(Variable(varAST->val()));
301     } else if (ast->getID() == AST::V_ConstantAST) {
302         ConstantAST::Ptr constAST = boost::static_pointer_cast<ConstantAST>(ast);
303         return ConstantAST::create(Constant(constAST->val()));
304     } else if (ast->getID() == AST::V_BottomAST) {
305         BottomAST::Ptr bottomAST = boost::static_pointer_cast<BottomAST>(ast);
306         return BottomAST::create(bottomAST->val());
307     }
308     fprintf(stderr, "ast type %d, %s\n", ast->getID(), ast->format().c_str());
309     assert(0);
310         return AST::Ptr();
311 }
312
313 pair<AST::Ptr, bool> SymbolicExpression::ExpandAssignment(Assignment::Ptr assign, bool keepMultiOne) {
314     if (expandCache.find(assign) != expandCache.end()) {
315         AST::Ptr ast = expandCache[assign];
316         if (ast) {
317             if (!keepMultiOne) ast = SimplifyAnAST(ast, 0, keepMultiOne);
318             return make_pair(ast, true);
319         } 
320         else {
321             return make_pair(ast, false);
322         }
323     } else {
324         parsing_printf("\t\tExpanding instruction @ %x: %s, assignment %s\n",
325                                            assign->addr(), assign->insn().format().c_str(), assign->format().c_str());
326         pair<AST::Ptr, bool> expandRet = SymEval::expand(assign, false);
327         if (expandRet.second && expandRet.first) {
328             parsing_printf("Original expand: %s\n", expandRet.first->format().c_str());
329             AST::Ptr calculation = SimplifyAnAST(expandRet.first, 
330                                                  PCValue(assign->addr(),
331                                                          assign->insn().size(),
332                                                          assign->block()->obj()->cs()->getArch()),
333                                                  true);
334             expandCache[assign] = calculation;
335         } else {
336             if (expandRet.first == NULL) {
337                 parsing_printf("\t\t\t expansion returned null ast\n");
338             }
339             if (expandRet.second == false) {
340                 parsing_printf("\t\t\t expansion returned false\n");
341             }
342             expandCache[assign] = AST::Ptr();
343         }
344         AST::Ptr ast = expandCache[assign];
345         if (ast && !keepMultiOne) ast = SimplifyAnAST(ast, 0, keepMultiOne);
346         return make_pair( ast, expandRet.second );
347     }
348 }
349
350 AST::Ptr SymbolicExpression::SubstituteAnAST(AST::Ptr ast, const map<AST::Ptr, AST::Ptr> &aliasMap) {
351     for (auto ait = aliasMap.begin(); ait != aliasMap.end(); ++ait)
352         if (*ast == *(ait->first)) {
353             return ait->second;
354         }
355     unsigned totalChildren = ast->numChildren();
356     for (unsigned i = 0 ; i < totalChildren; ++i) {
357         ast->setChild(i, SubstituteAnAST(ast->child(i), aliasMap));
358     }
359     if (ast->getID() == AST::V_VariableAST) {
360         // If this variable is not in the aliasMap yet,
361         // this variable is from the input.
362         VariableAST::Ptr varAST = boost::static_pointer_cast<VariableAST>(ast);
363         return VariableAST::create(Variable(varAST->val().reg, 1));
364     }
365     return ast;
366 }
367
368 Address SymbolicExpression::PCValue(Address cur, size_t insnSize, Architecture a) {
369     switch (a) {
370         case Arch_x86:
371         case Arch_x86_64:
372             return cur + insnSize;
373         case Arch_aarch64:
374         case Arch_ppc32:
375         case Arch_ppc64:
376             return cur;
377         case Arch_aarch32:
378         case Arch_cuda:
379         case Arch_none:
380             assert(0);
381     }    
382     return cur + insnSize;
383 }