ROSE  0.11.2.0
PartialSymbolicSemantics2.h
1 #ifndef Rose_PartialSymbolicSemantics2_H
2 #define Rose_PartialSymbolicSemantics2_H
3 #include <rosePublicConfig.h>
4 #ifdef ROSE_BUILD_BINARY_ANALYSIS_SUPPORT
5 
6 #ifndef __STDC_FORMAT_MACROS
7 #define __STDC_FORMAT_MACROS
8 #endif
9 #include <inttypes.h>
10 
11 #include <map>
12 #include <stdint.h>
13 #include <vector>
14 
15 #include "rosePublicConfig.h"
16 #ifdef ROSE_HAVE_LIBGCRYPT
17 #include <gcrypt.h>
18 #endif
19 
20 #include "BaseSemantics2.h"
21 #include "integerOps.h"
22 #include "MemoryMap.h"
23 #include "FormatRestorer.h"
24 #include "RegisterStateGeneric.h"
25 #include "MemoryCellList.h"
26 
27 namespace Rose {
28 namespace BinaryAnalysis { // documented elsewhere
29 namespace InstructionSemantics2 { // documented elsewhere
30 
44 namespace PartialSymbolicSemantics {
45 
47 // Print formatter
49 
53 protected:
54  typedef std::map<uint64_t, uint64_t> Map;
55  Map renames;
56  size_t next_name;
57 public:
58  Formatter(): next_name(1) {}
59  uint64_t rename(uint64_t orig_name);
60 };
61 
62 
64 // Semantic values
66 
69 
73 public:
74  uint64_t name;
75  uint64_t offset;
76  bool negate;
78  // Real constructors
80 protected:
81  explicit SValue(size_t nbits)
82  : BaseSemantics::SValue(nbits), name(nextName()), offset(0), negate(false) {}
83 
84  SValue(size_t nbits, uint64_t number)
85  : BaseSemantics::SValue(nbits), name(0), offset(number), negate(false) {
86  if (nbits <= 64) {
87  this->offset &= IntegerOps::genMask<uint64_t>(nbits);
88  } else {
89  name = nextName();
90  offset = 0;
91  }
92  }
93 
94  SValue(size_t nbits, uint64_t name, uint64_t offset, bool negate)
95  : BaseSemantics::SValue(nbits), name(name), offset(offset), negate(negate) {
96  this->offset &= IntegerOps::genMask<uint64_t>(nbits);
97  ASSERT_require(nbits <= 64 || name != 0);
98  }
99 
100 public:
106  static uint64_t nextName();
107 
109  // Static allocating constructors
110 public:
112  static SValuePtr instance() {
113  return SValuePtr(new SValue(1));
114  }
115 
117  static SValuePtr instance(size_t nbits) {
118  return SValuePtr(new SValue(nbits));
119  }
120 
122  static SValuePtr instance(size_t nbits, uint64_t value) {
123  return SValuePtr(new SValue(nbits, value));
124  }
125 
127  static SValuePtr instance(size_t nbits, uint64_t name, uint64_t offset, bool negate) {
128  return SValuePtr(new SValue(nbits, name, offset, negate));
129  }
130 
132  // Virtual constructors
133 public:
134  virtual BaseSemantics::SValuePtr bottom_(size_t nbits) const ROSE_OVERRIDE {
135  return instance(nbits);
136  }
137  virtual BaseSemantics::SValuePtr undefined_(size_t nbits) const ROSE_OVERRIDE {
138  return instance(nbits);
139  }
140  virtual BaseSemantics::SValuePtr unspecified_(size_t nbits) const ROSE_OVERRIDE {
141  return instance(nbits);
142  }
143 
144  virtual BaseSemantics::SValuePtr number_(size_t nbits, uint64_t value) const ROSE_OVERRIDE {
145  return instance(nbits, value);
146  }
147 
148  virtual BaseSemantics::SValuePtr copy(size_t new_width=0) const ROSE_OVERRIDE {
149  SValuePtr retval(new SValue(*this));
150  if (new_width!=0 && new_width!=retval->get_width())
151  retval->set_width(new_width);
152  return retval;
153  }
154 
157  const SmtSolverPtr&) const ROSE_OVERRIDE;
158 
160  virtual BaseSemantics::SValuePtr create(size_t nbits, uint64_t name, uint64_t offset, bool negate) const {
161  return instance(nbits, name, offset, negate);
162  }
163 
165  // Dynamic pointer casts
166 public:
169  static SValuePtr promote(const BaseSemantics::SValuePtr &v) {
170  SValuePtr retval = v.dynamicCast<SValue>();
171  ASSERT_not_null(retval);
172  return retval;
173  }
174 
176  // Other stuff we inherited from the super class
177 public:
178  virtual void set_width(size_t nbits) ROSE_OVERRIDE {
179  if (nbits > 64 && name == 0) {
180  *this = SValue(nbits);
181  } else {
182  ASSERT_require(nbits <= 64 || name != 0);
184  offset &= IntegerOps::genMask<uint64_t>(nbits);
185  }
186  }
187 
188  virtual bool may_equal(const BaseSemantics::SValuePtr &other,
189  const SmtSolverPtr &solver = SmtSolverPtr()) const ROSE_OVERRIDE;
190  virtual bool must_equal(const BaseSemantics::SValuePtr &other,
191  const SmtSolverPtr &solver = SmtSolverPtr()) const ROSE_OVERRIDE;
192 
193  virtual void print(std::ostream&, BaseSemantics::Formatter&) const ROSE_OVERRIDE;
194 
195  virtual bool isBottom() const ROSE_OVERRIDE {
196  return false;
197  }
198 
199  virtual bool is_number() const ROSE_OVERRIDE {
200  return 0==name;
201  }
202 
203  virtual uint64_t get_number() const ROSE_OVERRIDE {
204  ASSERT_require(is_number());
205  return offset;
206  }
207 };
208 
209 
211 // Register state
213 
214 typedef BaseSemantics::RegisterStateGeneric RegisterState;
215 typedef BaseSemantics::RegisterStateGenericPtr RegisterStatePtr;
216 
217 
219 // Memory state
221 
222 // PartialSymbolicSemantics uses BaseSemantics::MemoryCellList (or subclass) as its memory state, and does not expect the
223 // MemoryCellList to be byte-restricted (i.e., the cells can store multi-byte values).
224 
225 typedef BaseSemantics::MemoryCellList MemoryState;
226 typedef BaseSemantics::MemoryCellListPtr MemoryStatePtr;
227 
228 
230 // Complete state
232 
234 typedef boost::shared_ptr<class State> StatePtr;
235 
238 class State: public BaseSemantics::State {
239 
241  // Real constructors
242 protected:
243  State(const BaseSemantics::RegisterStatePtr &registers,
244  const BaseSemantics::MemoryStatePtr &memory)
245  : BaseSemantics::State(registers, memory) {
246  // This state should use PartialSymbolicSemantics values (or subclasses thereof)
247  ASSERT_not_null(registers);
248  (void) SValue::promote(registers->protoval());
249  ASSERT_not_null(memory);
250  (void) SValue::promote(memory->get_addr_protoval());
251  (void) SValue::promote(memory->get_val_protoval());
252 
253  // This state should use a memory that is not byte restricted.
254  MemoryStatePtr mcl = MemoryState::promote(memory);
255  ASSERT_require(!mcl->byteRestricted());
256  }
257 
258  State(const State &other): BaseSemantics::State(other) {}
259 
261  // Static allocating constructors
262 public:
264  static StatePtr instance(const BaseSemantics::RegisterStatePtr &registers,
265  const BaseSemantics::MemoryStatePtr &memory) {
266  return StatePtr(new State(registers, memory));
267  }
268 
270  static StatePtr instance(const StatePtr &other) {
271  return StatePtr(new State(*other));
272  }
273 
275  // Virtual constructors
276 public:
277  virtual BaseSemantics::StatePtr create(const BaseSemantics::RegisterStatePtr &registers,
278  const BaseSemantics::MemoryStatePtr &memory) const ROSE_OVERRIDE {
279  return instance(registers, memory);
280  }
281 
282  virtual BaseSemantics::StatePtr clone() const ROSE_OVERRIDE {
283  StatePtr self = promote(boost::const_pointer_cast<BaseSemantics::State>(shared_from_this()));
284  return instance(self);
285  }
286 
288  // Dynamic pointer casts
289 public:
290  static StatePtr promote(const BaseSemantics::StatePtr &x) {
291  StatePtr retval = boost::dynamic_pointer_cast<State>(x);
292  ASSERT_not_null(x);
293  return retval;
294  }
295 
297  // Methods first declared at this level of the class hierarchy
298 public:
301  virtual void print_diff_registers(std::ostream&, const StatePtr &other_state, Formatter&) const;
302 
304  virtual bool equal_registers(const StatePtr &other) const;
305 
308  virtual void discard_popped_memory();
309 };
310 
311 
313 // RISC operators
315 
317 typedef boost::shared_ptr<class RiscOperators> RiscOperatorsPtr;
318 
321 protected:
322  MemoryMap::Ptr map;
323 
325  // Real constructors
326 protected:
328  : BaseSemantics::RiscOperators(protoval, solver) {
329  name("PartialSymbolic");
330  }
331  explicit RiscOperators(const BaseSemantics::StatePtr &state, const SmtSolverPtr &solver = SmtSolverPtr())
333  name("PartialSymbolic");
334  }
335 
337  // Static allocating constructors
338 public:
341  static RiscOperatorsPtr instance(const RegisterDictionary *regdict);
342 
344  static RiscOperatorsPtr instance(const BaseSemantics::SValuePtr &protoval, const SmtSolverPtr &solver = SmtSolverPtr()) {
345  return RiscOperatorsPtr(new RiscOperators(protoval, solver));
346  }
347 
349  static RiscOperatorsPtr instance(const BaseSemantics::StatePtr &state, const SmtSolverPtr &solver = SmtSolverPtr()) {
350  return RiscOperatorsPtr(new RiscOperators(state, solver));
351  }
352 
354  // Virtual constructors
355 public:
357  const SmtSolverPtr &solver = SmtSolverPtr()) const ROSE_OVERRIDE {
358  return instance(protoval, solver);
359  }
360 
362  const SmtSolverPtr &solver = SmtSolverPtr()) const ROSE_OVERRIDE {
363  return instance(state, solver);
364  }
365 
367  // Dynamic pointer casts
368 public:
371  static RiscOperatorsPtr promote(const BaseSemantics::RiscOperatorsPtr &x) {
372  RiscOperatorsPtr retval = boost::dynamic_pointer_cast<RiscOperators>(x);
373  ASSERT_not_null(retval);
374  return retval;
375  }
376 
378  // Methods first declared at this level of the class hierarchy
379 public:
384  const MemoryMap::Ptr get_memory_map() const { return map; }
385  void set_memory_map(const MemoryMap::Ptr &m) { map = m; }
388  // Risc operators inherited
390 public:
391  virtual void interrupt(int majr, int minr) ROSE_OVERRIDE;
392  virtual BaseSemantics::SValuePtr and_(const BaseSemantics::SValuePtr &a_,
393  const BaseSemantics::SValuePtr &b_) ROSE_OVERRIDE;
395  const BaseSemantics::SValuePtr &b_) ROSE_OVERRIDE;
396  virtual BaseSemantics::SValuePtr xor_(const BaseSemantics::SValuePtr &a_,
397  const BaseSemantics::SValuePtr &b_) ROSE_OVERRIDE;
398  virtual BaseSemantics::SValuePtr invert(const BaseSemantics::SValuePtr &a_) ROSE_OVERRIDE;
399  virtual BaseSemantics::SValuePtr extract(const BaseSemantics::SValuePtr &a_,
400  size_t begin_bit, size_t end_bit) ROSE_OVERRIDE;
401  virtual BaseSemantics::SValuePtr concat(const BaseSemantics::SValuePtr &a_,
402  const BaseSemantics::SValuePtr &b_) ROSE_OVERRIDE;
403  virtual BaseSemantics::SValuePtr leastSignificantSetBit(const BaseSemantics::SValuePtr &a_) ROSE_OVERRIDE;
404  virtual BaseSemantics::SValuePtr mostSignificantSetBit(const BaseSemantics::SValuePtr &a_) ROSE_OVERRIDE;
405  virtual BaseSemantics::SValuePtr rotateLeft(const BaseSemantics::SValuePtr &a_,
406  const BaseSemantics::SValuePtr &sa_) ROSE_OVERRIDE;
407  virtual BaseSemantics::SValuePtr rotateRight(const BaseSemantics::SValuePtr &a_,
408  const BaseSemantics::SValuePtr &sa_) ROSE_OVERRIDE;
409  virtual BaseSemantics::SValuePtr shiftLeft(const BaseSemantics::SValuePtr &a_,
410  const BaseSemantics::SValuePtr &sa_) ROSE_OVERRIDE;
411  virtual BaseSemantics::SValuePtr shiftRight(const BaseSemantics::SValuePtr &a_,
412  const BaseSemantics::SValuePtr &sa_) ROSE_OVERRIDE;
413  virtual BaseSemantics::SValuePtr shiftRightArithmetic(const BaseSemantics::SValuePtr &a_,
414  const BaseSemantics::SValuePtr &sa_) ROSE_OVERRIDE;
415  virtual BaseSemantics::SValuePtr equalToZero(const BaseSemantics::SValuePtr &a_) ROSE_OVERRIDE;
416  virtual BaseSemantics::SValuePtr ite(const BaseSemantics::SValuePtr &sel_,
417  const BaseSemantics::SValuePtr &a_,
418  const BaseSemantics::SValuePtr &b_) ROSE_OVERRIDE;
419  virtual BaseSemantics::SValuePtr signExtend(const BaseSemantics::SValuePtr &a_, size_t new_width) ROSE_OVERRIDE;
421  const BaseSemantics::SValuePtr &b_) ROSE_OVERRIDE;
423  const BaseSemantics::SValuePtr &b_,
424  const BaseSemantics::SValuePtr &c_,
425  BaseSemantics::SValuePtr &carry_out/*out*/) ROSE_OVERRIDE;
426  virtual BaseSemantics::SValuePtr negate(const BaseSemantics::SValuePtr &a_) ROSE_OVERRIDE;
428  const BaseSemantics::SValuePtr &b_) ROSE_OVERRIDE;
430  const BaseSemantics::SValuePtr &b_) ROSE_OVERRIDE;
432  const BaseSemantics::SValuePtr &b_) ROSE_OVERRIDE;
434  const BaseSemantics::SValuePtr &b_) ROSE_OVERRIDE;
436  const BaseSemantics::SValuePtr &b_) ROSE_OVERRIDE;
438  const BaseSemantics::SValuePtr &b_) ROSE_OVERRIDE;
440  const BaseSemantics::SValuePtr &addr,
441  const BaseSemantics::SValuePtr &dflt,
442  const BaseSemantics::SValuePtr &cond) ROSE_OVERRIDE;
444  const BaseSemantics::SValuePtr &addr,
445  const BaseSemantics::SValuePtr &dflt) ROSE_OVERRIDE;
446  virtual void writeMemory(RegisterDescriptor segreg,
447  const BaseSemantics::SValuePtr &addr,
448  const BaseSemantics::SValuePtr &data,
449  const BaseSemantics::SValuePtr &cond) ROSE_OVERRIDE;
450 
451 protected:
452  BaseSemantics::SValuePtr readOrPeekMemory(RegisterDescriptor segreg, const BaseSemantics::SValuePtr &address,
453  const BaseSemantics::SValuePtr &dflt_, bool allowSideEffects);
454 };
455 
456 } // namespace
457 } // namespace
458 } // namespace
459 } // namespace
460 
461 #endif
462 #endif
virtual BaseSemantics::SValuePtr signedModulo(const BaseSemantics::SValuePtr &a_, const BaseSemantics::SValuePtr &b_) ROSE_OVERRIDE
Calculates modulo with signed values.
boost::shared_ptr< RiscOperators > RiscOperatorsPtr
Shared-ownership pointer to a RISC operators object.
virtual BaseSemantics::SValuePtr bottom_(size_t nbits) const ROSE_OVERRIDE
Data-flow bottom value.
static RiscOperatorsPtr instance(const RegisterDictionary *regdict)
Instantiates a new RiscOperators object and configures it to use semantic values and states that are ...
boost::shared_ptr< class RegisterStateGeneric > RegisterStateGenericPtr
Shared-ownership pointer to generic register states.
virtual void set_width(size_t nbits)
Accessor for value width.
virtual BaseSemantics::SValuePtr signedDivide(const BaseSemantics::SValuePtr &a_, const BaseSemantics::SValuePtr &b_) ROSE_OVERRIDE
Divides two signed values.
virtual bool may_equal(const BaseSemantics::SValuePtr &other, const SmtSolverPtr &solver=SmtSolverPtr()) const ROSE_OVERRIDE
Returns true if two values could be equal.
boost::shared_ptr< MemoryState > MemoryStatePtr
Shared-ownership pointer to a memory state.
boost::shared_ptr< State > StatePtr
Shared-ownership pointer to a semantic state.
virtual BaseSemantics::SValuePtr unspecified_(size_t nbits) const ROSE_OVERRIDE
Create a new unspecified semantic value.
virtual BaseSemantics::SValuePtr undefined_(size_t nbits) const ROSE_OVERRIDE
Create a new undefined semantic value.
virtual BaseSemantics::SValuePtr peekMemory(RegisterDescriptor segreg, const BaseSemantics::SValuePtr &addr, const BaseSemantics::SValuePtr &dflt) ROSE_OVERRIDE
Read memory without side effects.
virtual uint64_t get_number() const ROSE_OVERRIDE
Return the concrete number for this value.
STL namespace.
Holds a value or nothing.
Definition: Optional.h:49
Sawyer::SharedPointer< class SValue > SValuePtr
Shared-ownership pointer to a partial-symbolic semantic value.
virtual BaseSemantics::SValuePtr signedMultiply(const BaseSemantics::SValuePtr &a_, const BaseSemantics::SValuePtr &b_) ROSE_OVERRIDE
Multiplies two signed values.
virtual SValuePtr protoval() const
Property: Prototypical semantic value.
Main namespace for the ROSE library.
virtual Sawyer::Optional< BaseSemantics::SValuePtr > createOptionalMerge(const BaseSemantics::SValuePtr &other, const BaseSemantics::MergerPtr &, const SmtSolverPtr &) const ROSE_OVERRIDE
Possibly create a new value by merging two existing values.
uint64_t name
Zero for constants; non-zero ID number for everything else.
virtual BaseSemantics::SValuePtr create(size_t nbits, uint64_t name, uint64_t offset, bool negate) const
Virtual allocating constructor.
static SValuePtr instance(size_t nbits)
Instantiate a new undefined value of specified width.
Reference-counting intrusive smart pointer.
Definition: SharedPointer.h:68
virtual BaseSemantics::SValuePtr negate(const BaseSemantics::SValuePtr &a_) ROSE_OVERRIDE
Two's complement.
virtual BaseSemantics::SValuePtr unsignedMultiply(const BaseSemantics::SValuePtr &a_, const BaseSemantics::SValuePtr &b_) ROSE_OVERRIDE
Multiply two unsigned values.
virtual BaseSemantics::SValuePtr unsignedModulo(const BaseSemantics::SValuePtr &a_, const BaseSemantics::SValuePtr &b_) ROSE_OVERRIDE
Calculates modulo with unsigned values.
virtual BaseSemantics::SValuePtr readMemory(RegisterDescriptor segreg, const BaseSemantics::SValuePtr &addr, const BaseSemantics::SValuePtr &dflt, const BaseSemantics::SValuePtr &cond) ROSE_OVERRIDE
Reads a value from memory.
Sawyer::SharedPointer< class SmtSolver > SmtSolverPtr
Reference-counting pointer for SMT solvers.
bool negate
Switch between name+offset and (-name)+offset; should be false for constants.
virtual void set_width(size_t nbits) ROSE_OVERRIDE
Accessor for value width.
Type of values manipulated by the PartialSymbolicSemantics domain.
virtual void interrupt(int majr, int minr) ROSE_OVERRIDE
Invoked for instructions that cause an interrupt.
boost::shared_ptr< class MemoryCellList > MemoryCellListPtr
Shared-ownership pointer to a list-based memory state.
void set_memory_map(const MemoryMap::Ptr &m)
A memory map can be used to provide default values for memory cells that are read before being writte...
static StatePtr instance(const BaseSemantics::RegisterStatePtr &registers, const BaseSemantics::MemoryStatePtr &memory)
Instantiates a new instance of memory state with specified register and memory states.
Describes (part of) a physical CPU register.
static RiscOperatorsPtr promote(const BaseSemantics::RiscOperatorsPtr &x)
Run-time promotion of a base RiscOperators pointer to partial symbolic operators. ...
virtual BaseSemantics::SValuePtr copy(size_t new_width=0) const ROSE_OVERRIDE
Create a new value from an existing value, changing the width if new_width is non-zero.
virtual BaseSemantics::SValuePtr addWithCarries(const BaseSemantics::SValuePtr &a_, const BaseSemantics::SValuePtr &b_, const BaseSemantics::SValuePtr &c_, BaseSemantics::SValuePtr &carry_out) ROSE_OVERRIDE
Used for printing RISC operators with formatting.
virtual BaseSemantics::RiscOperatorsPtr create(const BaseSemantics::StatePtr &state, const SmtSolverPtr &solver=SmtSolverPtr()) const ROSE_OVERRIDE
Virtual allocating constructor.
SharedPointer< U > dynamicCast() const
Dynamic cast.
Base class for most instruction semantics RISC operators.
const MemoryMap::Ptr get_memory_map() const
A memory map can be used to provide default values for memory cells that are read before being writte...
virtual bool isBottom() const ROSE_OVERRIDE
Determines whether a value is a data-flow bottom.
static SValuePtr instance(size_t nbits, uint64_t name, uint64_t offset, bool negate)
Insantiate a new value with all the necessary parts.
boost::shared_ptr< class State > StatePtr
Shared-ownership pointer to partial symbolic semantics state.
virtual void writeMemory(RegisterDescriptor segreg, const BaseSemantics::SValuePtr &addr, const BaseSemantics::SValuePtr &data, const BaseSemantics::SValuePtr &cond) ROSE_OVERRIDE
Writes a value to memory.
virtual bool equal_registers(const StatePtr &other) const
Tests registers of two states for equality.
virtual bool is_number() const ROSE_OVERRIDE
Determines if the value is a concrete number.
virtual BaseSemantics::SValuePtr number_(size_t nbits, uint64_t value) const ROSE_OVERRIDE
Create a new concrete semantic value.
static RiscOperatorsPtr instance(const BaseSemantics::StatePtr &state, const SmtSolverPtr &solver=SmtSolverPtr())
Instantiates a new RiscOperators with specified state.
boost::shared_ptr< class RiscOperators > RiscOperatorsPtr
Shared-ownership pointer to partial symbolic semantics RISC operations.
virtual BaseSemantics::RiscOperatorsPtr create(const BaseSemantics::SValuePtr &protoval, const SmtSolverPtr &solver=SmtSolverPtr()) const ROSE_OVERRIDE
Virtual allocating constructor.
virtual bool must_equal(const BaseSemantics::SValuePtr &other, const SmtSolverPtr &solver=SmtSolverPtr()) const ROSE_OVERRIDE
Returns true if two values must be equal.
static MemoryCellListPtr promote(const BaseSemantics::MemoryStatePtr &m)
Promote a base memory state pointer to a BaseSemantics::MemoryCellList pointer.
virtual BaseSemantics::SValuePtr unsignedDivide(const BaseSemantics::SValuePtr &a_, const BaseSemantics::SValuePtr &b_) ROSE_OVERRIDE
Divides two unsigned values.
virtual void print_diff_registers(std::ostream &, const StatePtr &other_state, Formatter &) const
Print info about how registers differ.
static RiscOperatorsPtr instance(const BaseSemantics::SValuePtr &protoval, const SmtSolverPtr &solver=SmtSolverPtr())
Instantiates a new RiscOperators object with specified prototypical values.
Defines registers available for a particular architecture.
Definition: Registers.h:38
virtual SmtSolverPtr solver() const
Property: Satisfiability module theory (SMT) solver.
virtual const std::string & name() const
Property: Name used for debugging.
static StatePtr instance(const StatePtr &other)
Instantiates a new copy of an existing state.
virtual void print(std::ostream &, BaseSemantics::Formatter &) const ROSE_OVERRIDE
Print a value to a stream using default format.
virtual void discard_popped_memory()
Removes from memory those values at addresses below the current stack pointer.
static SValuePtr instance(size_t nbits, uint64_t value)
Instantiate a new concrete value.
boost::shared_ptr< RegisterState > RegisterStatePtr
Shared-ownership pointer to a register state.
static uint64_t nextName()
Returns the next available name.
static SValuePtr promote(const BaseSemantics::SValuePtr &v)
Promote a base value to a PartialSymbolicSemantics value.