Using symEval in ParseAPI for slicing, added hybrid analysis code
[dyninst.git] / parseAPI / src / StackTamperVisitor.h
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
33
34 #if !defined(_STACK_TAMPER_VISITOR_H_)
35 #define _STACK_TAMPER_VISITOR_H_
36
37 #include <map>
38 #include <stack>
39 #include "symEval/h/Absloc.h" // MemEmulator analysis
40 #include "symEval/h/AbslocInterface.h" // And more of the same
41 #include "symEval/h/SymEval.h" // Variable class
42 #include "dynutil/h/AST.h"
43 #include "parseAPI/h/CFG.h"
44
45
46 // A representation of a variable x = x + var1 + var2 + var3 + ...
47 // where int is an integer and var1...varN are unknown variables.
48
49 namespace Dyninst {
50
51 template <typename T>
52 struct Var {
53   typedef typename std::map<T, int> Unknowns;
54   Var<T> &operator+=(const Var<T> &rhs) {
55     x += rhs.x;
56     for (typename Unknowns::const_iterator i = rhs.unknowns.begin();
57          i != rhs.unknowns.end(); ++i) {
58       unknowns[i->first] += i->second;
59     }
60     return *this;
61   }
62
63   Var<T> &operator+=(const int &rhs) {
64     x += rhs;
65     return *this;
66   }
67
68   Var<T> operator+(const Var<T> &rhs) const {
69     Var<T> tmp = *this;
70     tmp += rhs;
71     return tmp;
72   }
73
74   Var<T> operator+(const int &rhs) const {
75     Var<T> tmp = *this;
76     tmp += rhs;
77     return tmp;
78   }
79
80   Var<T> operator*=(const int &rhs) {
81     if (rhs == 0) { 
82       unknowns.clear();
83       x = 0;
84     } 
85     else if (rhs != 1) {
86       x *= rhs;
87       for (typename Unknowns::iterator i = unknowns.begin();
88            i != unknowns.end(); ++i) {
89         i->second *= rhs;
90       }
91     }
92     return *this;
93   }
94
95   Var<T> operator*(const int &rhs) const {
96     if (rhs == 0) { return Var<T>(0); }
97     if (rhs == 1) return *this;
98     else {
99       Var<T> tmp = *this;
100       tmp *= rhs;
101       return tmp;
102     }
103   }
104
105
106   bool operator==(const Var<T> &rhs) const {
107     if (x != rhs.x) return false;
108     if (unknowns != rhs.unknowns) return false;
109     return true;
110   }
111   
112   bool operator!=(const Var<T> &rhs) const {
113     return !(*this == rhs);
114   }
115
116   bool operator!=(const int &rhs) const {
117     if (x != rhs) return true;
118     if (!unknowns.empty()) return true;
119     return false;
120   }
121
122 Var() : x(0) {};
123 Var(int a) : x(a) {};
124 Var(T a) : x(0) { unknowns[a] = 1; };
125
126   int x;
127   Unknowns unknowns;
128 };
129
130 template <typename T> 
131 struct linVar {
132   linVar<T> &operator+=(const linVar<T> &rhs) {
133     if (bottom) return *this;
134     if (rhs.bottom) {
135       bottom = true;
136     }
137     else {
138       a += rhs.a;
139       b += rhs.b;
140     }
141     return *this;
142   }
143   const linVar<T> operator+(const linVar<T> &rhs) const {
144     if (bottom) return *this;
145     if (rhs.bottom) return rhs;
146     return linVar(a + rhs.a, b + rhs.b);
147   }
148   const linVar<T> operator*=(const int &rhs) {
149     a *= rhs;
150     b *= rhs;
151     return *this;
152   }
153
154   const linVar<T> operator*=(const linVar<T> &rhs) {
155     if (bottom) return *this;
156     if (rhs.bottom) {
157       bottom = true;
158     }
159     else {
160       if (b && rhs.b) {
161         // Can't go quadratic
162         bottom = true;
163       }
164       else {
165         a *= rhs.a;
166         b = a*rhs.b + b*rhs.a;
167       }
168     }
169     return *this;
170   }
171   const linVar<T> operator*(const linVar<T> &rhs) const {
172     if (bottom) return *this;
173     if (rhs.bottom) return rhs;
174     if ((b != 0) && (rhs.b != 0)) {
175       return linVar<T>();
176     }
177     // Okay, I'm going to be lazy here because I don't believe it
178     // matters...
179     // Not sure how to multiply two sets of registers, so we'll force
180     // one side to be numeric.
181     if (b == 0) {
182       // Just have a * rhs.b to worry about
183       if (a.unknowns.empty()) {
184         return linVar<T>(a + rhs.a, rhs.b*a.x);
185       }
186       else if (rhs.b.unknowns.empty()) {
187         return linVar<T>(a + rhs.a, a*rhs.b.x);
188       }
189       else { 
190         return linVar<T>();
191       }
192     }
193     else if (rhs.b == 0) {
194       if (b.unknowns.empty()) {
195         return linVar<T>(a + rhs.a, rhs.a*b.x);
196       }
197       else if (rhs.a.unknowns.empty()) {
198         return linVar<T>(a + rhs.a, b*rhs.a.x);
199       }
200       else { 
201         return linVar<T>();
202       }
203     }
204     return linVar<T>();
205   }
206   
207 linVar() : bottom(true) {};
208 linVar(T x, T y) : bottom(false), a(x), b(y) {};
209 linVar(int x, int y) : bottom(false), a(x), b(y) {};
210 linVar(T x, int y): bottom(false), a(x), b(y) {};
211 linVar(Var<T> x, Var<T> y) : bottom(false), a(x), b(y) {};
212   bool bottom;
213   Var<T> a;
214   Var<T> b;
215 };
216
217
218 typedef enum {
219   NotRequired,
220   Suggested,
221   Required,
222   OffLimits,
223   MaxPriority } Priority;
224  
225
226 // ROSE symeval AST types
227 namespace SymbolicEvaluation {
228  class BottomAST;
229  class ConstantAST;
230  class AbsRegionAST;
231  class RoseAST;
232  };
233
234 class StackTamperVisitor : public ASTVisitor {
235  public:
236   StackTamperVisitor(const AbsRegion &a);
237
238   virtual AST::Ptr visit(AST *);
239   virtual AST::Ptr visit(SymbolicEvaluation::BottomAST *);
240   virtual AST::Ptr visit(SymbolicEvaluation::ConstantAST *);
241   virtual AST::Ptr visit(SymbolicEvaluation::VariableAST *);
242   virtual AST::Ptr visit(SymbolicEvaluation::RoseAST *);
243   virtual AST::Ptr visit(StackAST *);
244   virtual ASTVisitor::ASTPtr visit(InputVariableAST *x) { return ASTVisitor::visit(x); }
245   virtual ASTVisitor::ASTPtr visit(ReferenceAST *x) { return ASTVisitor::visit(x); }
246   virtual ASTVisitor::ASTPtr visit(StpAST *x) { return ASTVisitor::visit(x); }
247   virtual ASTVisitor::ASTPtr visit(YicesAST *x) { return ASTVisitor::visit(x); }
248   virtual ~StackTamperVisitor() {};
249   
250   ParseAPI::StackTamper tampersStack(AST::Ptr a, Address &modAddr);
251
252  private:
253   ParseAPI::StackTamper tamper_;
254   Address modpc_;
255
256   typedef linVar<SymbolicEvaluation::Variable> DiffVar;
257
258   std::stack<DiffVar > diffs_;
259 };
260
261 }
262 #endif
263