Using symEval in ParseAPI for slicing, added hybrid analysis code
[dyninst.git] / parseAPI / src / StackTamperVisitor.C
1 /*
2  * Copyright (c) 1996-2009 Barton P. Miller
3  * 
4  * We provide the Paradyn Parallel Performance Tools (below
5  * described as "Paradyn") on an AS IS basis, and do not warrant its
6  * validity or performance.  We reserve the right to update, modify,
7  * or discontinue this software at any time.  We shall have no
8  * obligation to supply such updates or modifications or any other
9  * form of support to you.
10  * 
11  * By your use of Paradyn, you understand and agree that we (or any
12  * other person or entity with proprietary rights in Paradyn) are
13  * under no obligation to provide either maintenance services,
14  * update services, notices of latent defects, or correction of
15  * defects for Paradyn.
16  * 
17  * This library is free software; you can redistribute it and/or
18  * modify it under the terms of the GNU Lesser General Public
19  * License as published by the Free Software Foundation; either
20  * version 2.1 of the License, or (at your option) any later version.
21  * 
22  * This library is distributed in the hope that it will be useful,
23  * but WITHOUT ANY WARRANTY; without even the implied warranty of
24  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
25  * Lesser General Public License for more details.
26  * 
27  * You should have received a copy of the GNU Lesser General Public
28  * License along with this library; if not, write to the Free Software
29  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
30  */
31
32 #include "StackTamperVisitor.h"
33 #include "symEval/h/slicing.h"
34 #include "symEval/h/stackanalysis.h"
35 #include "instructionAPI/h/Instruction.h"
36 #include "CFG.h"
37
38 using namespace std;
39 using namespace Dyninst;
40 using namespace SymbolicEvaluation;
41 using namespace ParseAPI;
42
43 StackTamperVisitor::StackTamperVisitor(const AbsRegion &a) :
44   tamper_(TAMPER_NONE),
45   modpc_(0)
46 {
47 }
48
49 AST::Ptr StackTamperVisitor::visit(AST *a) {
50   // Should never be able to get this
51   tamper_ = TAMPER_NONZERO;
52   return a->ptr();
53 }
54
55 AST::Ptr StackTamperVisitor::visit(BottomAST *b) {
56   tamper_ = TAMPER_NONZERO;
57   return b->ptr();
58 }
59
60 AST::Ptr StackTamperVisitor::visit(ConstantAST *c) {
61   diffs_.push(DiffVar((int)c->val().val, 0));
62   return c->ptr();
63 }
64
65 AST::Ptr StackTamperVisitor::visit(VariableAST *v) {
66   const AbsRegion &reg = v->val().reg;
67   const Absloc &aloc = reg.absloc();
68   if (Absloc::Stack == aloc.type()) {
69     // Right on!
70     diffs_.push(DiffVar(0, 1));
71   }
72   else {
73     diffs_.push(DiffVar(v->val(), 0));
74   }
75   return v->ptr();
76 }
77
78 AST::Ptr StackTamperVisitor::visit(StackAST *s) {
79   // If we see one of these we're getting a weird "pc + esp", 
80   // so we can consider it a constant.
81   if (s->val().isBottom()) {
82     tamper_ = TAMPER_NONZERO;
83   }
84   else {
85     diffs_.push(DiffVar(s->val().height(), 0));
86   }
87   return s->ptr();
88 }
89
90 AST::Ptr StackTamperVisitor::visit(RoseAST *r) {
91   // Abort (ish) if we're done
92   if (tamper_ != TAMPER_UNSET) return r->ptr();
93   
94   // Simplify children to the stack. 
95   // Discard the pointers because we really don't care.
96   // Go backwards so that the stack order matches the child order.
97   // (that is, child 1 on top)
98   for (unsigned i = r->numChildren(); i > 0; --i) {
99     r->child(i-1)->accept(this);
100   }
101   // return immediately if we're done
102   if (tamper_ != TAMPER_UNSET) return r->ptr();
103
104   // Okay, let's see what's goin' on...
105   switch(r->val().op) {
106   case ROSEOperation::derefOp: {
107     // A dereference is a decision point: either we're externally
108     // sensitive (if the calculated difference depends on the PC at all)
109     // or we reset the difference to 0.
110     if (diffs_.top().b != 0) {
111       tamper_ = TAMPER_NONZERO;
112     }
113     // Ignore the other entries... might be conditional loads, etc.
114     for (unsigned i = 0; i < r->numChildren(); i++) {
115       diffs_.pop();
116     }
117     // A non-modified dereference resets our "what's the difference" to 0. 
118     diffs_.push(DiffVar(0, 0));
119     break;
120   }
121   case ROSEOperation::addOp: {
122     DiffVar sum(0,0);
123     for (unsigned i = 0; i < r->numChildren(); ++i) {
124       sum += diffs_.top(); diffs_.pop();
125     }
126     diffs_.push(sum);
127     break;
128   }
129   case ROSEOperation::invertOp: {
130     diffs_.top() *= -1;
131     break;
132   }
133   case ROSEOperation::extendMSBOp:
134   case ROSEOperation::extractOp: {
135     DiffVar tmp = diffs_.top();
136     for (unsigned i = 0; i < r->numChildren(); ++i) {
137       diffs_.pop();
138     }
139     diffs_.push(tmp);
140     break;
141   }
142   default:
143     for (unsigned i = 0; i < r->numChildren(); i++) {
144       if (diffs_.top().b != 0) {
145         tamper_ = TAMPER_NONZERO;
146       }
147       diffs_.pop();
148     }
149     diffs_.push(DiffVar(0, 0));
150     break;
151   }
152   return r->ptr();
153 }
154
155 StackTamper StackTamperVisitor::tampersStack(AST::Ptr a, Address &newAddr) {
156
157     a->accept(this);
158
159     if(tamper_ != TAMPER_UNSET) {
160         newAddr = modpc_;
161         return tamper_;
162     }
163
164     assert(diffs_.size() == 1);
165
166     modpc_ = diffs_.top().b.x;
167
168     switch(diffs_.top().a.x) {
169     case 0:
170         tamper_ = TAMPER_ABS;
171         break;
172     case 1:
173         if (modpc_) {
174             tamper_ = TAMPER_REL;
175         } else {
176             tamper_ = TAMPER_NONE;
177         }
178         break;
179     default:
180         tamper_ = TAMPER_NONZERO;
181         break;
182     }
183     return tamper_;
184 }
185