ROSE  0.11.101.0
PartialSymbolicSemantics.h
1 #ifndef ROSE_BinaryAnalysis_InstructionSemantics_PartialSymbolicSemantics_H
2 #define ROSE_BinaryAnalysis_InstructionSemantics_PartialSymbolicSemantics_H
3 #include <featureTests.h>
4 #ifdef ROSE_ENABLE_BINARY_ANALYSIS
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 <Rose/BinaryAnalysis/BasicTypes.h>
21 #include <Rose/BinaryAnalysis/InstructionSemantics/BaseSemantics.h>
22 #include "integerOps.h"
23 #include <Rose/BinaryAnalysis/MemoryMap.h>
24 #include <Rose/FormatRestorer.h>
25 
26 namespace Rose {
27 namespace BinaryAnalysis { // documented elsewhere
28 namespace InstructionSemantics { // documented elsewhere
29 
43 namespace PartialSymbolicSemantics {
44 
46 // Print formatter
48 
52 protected:
53  typedef std::map<uint64_t, uint64_t> Map;
54  Map renames;
55  size_t next_name;
56 public:
57  Formatter(): next_name(1) {}
58  uint64_t rename(uint64_t orig_name);
59 };
60 
61 
63 // Semantic values
65 
68 
72 public:
75 
77  using Ptr = SValuePtr;
78 
79 public:
80  uint64_t name;
81  uint64_t offset;
82  bool negate;
84  // Real constructors
86 protected:
87  explicit SValue(size_t nbits)
88  : BaseSemantics::SValue(nbits), name(nextName()), offset(0), negate(false) {}
89 
90  SValue(size_t nbits, uint64_t number)
91  : BaseSemantics::SValue(nbits), name(0), offset(number), negate(false) {
92  if (nbits <= 64) {
93  this->offset &= IntegerOps::genMask<uint64_t>(nbits);
94  } else {
95  name = nextName();
96  offset = 0;
97  }
98  }
99 
100  SValue(size_t nbits, uint64_t name, uint64_t offset, bool negate)
101  : BaseSemantics::SValue(nbits), name(name), offset(offset), negate(negate) {
102  this->offset &= IntegerOps::genMask<uint64_t>(nbits);
103  ASSERT_require(nbits <= 64 || name != 0);
104  }
105 
106 public:
112  static uint64_t nextName();
113 
115  // Static allocating constructors
116 public:
118  static SValuePtr instance() {
119  return SValuePtr(new SValue(1));
120  }
121 
123  static SValuePtr instance(size_t nbits) {
124  return SValuePtr(new SValue(nbits));
125  }
126 
128  static SValuePtr instance(size_t nbits, uint64_t value) {
129  return SValuePtr(new SValue(nbits, value));
130  }
131 
133  static SValuePtr instance(size_t nbits, uint64_t name, uint64_t offset, bool negate) {
134  return SValuePtr(new SValue(nbits, name, offset, negate));
135  }
136 
138  // Virtual constructors
139 public:
140  virtual BaseSemantics::SValuePtr bottom_(size_t nbits) const override {
141  return instance(nbits);
142  }
143  virtual BaseSemantics::SValuePtr undefined_(size_t nbits) const override {
144  return instance(nbits);
145  }
146  virtual BaseSemantics::SValuePtr unspecified_(size_t nbits) const override {
147  return instance(nbits);
148  }
149 
150  virtual BaseSemantics::SValuePtr number_(size_t nbits, uint64_t value) const override {
151  return instance(nbits, value);
152  }
153 
154  virtual BaseSemantics::SValuePtr copy(size_t new_width=0) const override {
155  SValuePtr retval(new SValue(*this));
156  if (new_width!=0 && new_width!=retval->nBits())
157  retval->set_width(new_width);
158  return retval;
159  }
160 
163  const SmtSolverPtr&) const override;
164 
166  virtual BaseSemantics::SValuePtr create(size_t nbits, uint64_t name, uint64_t offset, bool negate) const {
167  return instance(nbits, name, offset, negate);
168  }
169 
171  // Dynamic pointer casts
172 public:
175  static SValuePtr promote(const BaseSemantics::SValuePtr &v) {
176  SValuePtr retval = v.dynamicCast<SValue>();
177  ASSERT_not_null(retval);
178  return retval;
179  }
180 
182  // Other stuff we inherited from the super class
183 public:
184  virtual void hash(Combinatorics::Hasher&) const override;
185  virtual void print(std::ostream&, BaseSemantics::Formatter&) const override;
186 
187  virtual bool isBottom() const override {
188  return false;
189  }
190 
192  // Override legacy members. These have similar non-virtual camelCase names in the base class, and eventually we'll remoe
193  // these snake_case names and change the camelCase names to be the virtual functions. Therefore, be sure to use "override"
194  // in your own code so you know when we make this change.
195 public:
196  // See nBits
197  virtual void set_width(size_t nbits) override {
198  if (nbits > 64 && name == 0) {
199  *this = SValue(nbits);
200  } else {
201  ASSERT_require(nbits <= 64 || name != 0);
203  offset &= IntegerOps::genMask<uint64_t>(nbits);
204  }
205  }
206 
207  // See mayEqual
208  virtual bool may_equal(const BaseSemantics::SValuePtr &other,
209  const SmtSolverPtr &solver = SmtSolverPtr()) const override;
210 
211  // See mustEqual
212  virtual bool must_equal(const BaseSemantics::SValuePtr &other,
213  const SmtSolverPtr &solver = SmtSolverPtr()) const override;
214 
215  // See isConcrete
216  virtual bool is_number() const override {
217  return 0==name;
218  }
219 
220  // See toUnsigned and toSigned.
221  virtual uint64_t get_number() const override {
222  ASSERT_require(is_number());
223  return offset;
224  }
225 };
226 
227 
229 // Register state
231 
232 typedef BaseSemantics::RegisterStateGeneric RegisterState;
233 typedef BaseSemantics::RegisterStateGenericPtr RegisterStatePtr;
234 
235 
237 // Memory state
239 
240 // PartialSymbolicSemantics uses BaseSemantics::MemoryCellList (or subclass) as its memory state, and does not expect the
241 // MemoryCellList to be byte-restricted (i.e., the cells can store multi-byte values).
242 
243 typedef BaseSemantics::MemoryCellList MemoryState;
244 typedef BaseSemantics::MemoryCellListPtr MemoryStatePtr;
245 
246 
248 // Complete state
250 
252 typedef boost::shared_ptr<class State> StatePtr;
253 
257 public:
260 
262  using Ptr = StatePtr;
263 
265  // Real constructors
266 protected:
267  State(const BaseSemantics::RegisterStatePtr &registers,
268  const BaseSemantics::MemoryStatePtr &memory)
269  : BaseSemantics::State(registers, memory) {
270  // This state should use PartialSymbolicSemantics values (or subclasses thereof)
271  ASSERT_not_null(registers);
272  (void) SValue::promote(registers->protoval());
273  ASSERT_not_null(memory);
274  (void) SValue::promote(memory->get_addr_protoval());
275  (void) SValue::promote(memory->get_val_protoval());
276 
277  // This state should use a memory that is not byte restricted.
278  MemoryStatePtr mcl = MemoryState::promote(memory);
279  ASSERT_require(!mcl->byteRestricted());
280  }
281 
282  State(const State &other): BaseSemantics::State(other) {}
283 
285  // Static allocating constructors
286 public:
288  static StatePtr instance(const BaseSemantics::RegisterStatePtr &registers,
289  const BaseSemantics::MemoryStatePtr &memory) {
290  return StatePtr(new State(registers, memory));
291  }
292 
294  static StatePtr instance(const StatePtr &other) {
295  return StatePtr(new State(*other));
296  }
297 
299  // Virtual constructors
300 public:
302  const BaseSemantics::MemoryStatePtr &memory) const override {
303  return instance(registers, memory);
304  }
305 
306  virtual BaseSemantics::StatePtr clone() const override {
307  StatePtr self = promote(boost::const_pointer_cast<BaseSemantics::State>(shared_from_this()));
308  return instance(self);
309  }
310 
312  // Dynamic pointer casts
313 public:
314  static StatePtr promote(const BaseSemantics::StatePtr &x) {
315  StatePtr retval = boost::dynamic_pointer_cast<State>(x);
316  ASSERT_not_null(x);
317  return retval;
318  }
319 
321  // Methods first declared at this level of the class hierarchy
322 public:
325  virtual void print_diff_registers(std::ostream&, const StatePtr &other_state, Formatter&) const;
326 
328  virtual bool equal_registers(const StatePtr &other) const;
329 
332  virtual void discard_popped_memory();
333 };
334 
335 
337 // RISC operators
339 
341 typedef boost::shared_ptr<class RiscOperators> RiscOperatorsPtr;
342 
345 public:
348 
351 
352 protected:
353  MemoryMap::Ptr map;
354 
356  // Real constructors
357 protected:
358  explicit RiscOperators(const BaseSemantics::SValuePtr &protoval, const SmtSolverPtr&);
359 
360  explicit RiscOperators(const BaseSemantics::StatePtr&, const SmtSolverPtr&);
361 
363  // Static allocating constructors
364 public:
365  ~RiscOperators();
366 
369  static RiscOperatorsPtr instanceFromRegisters(const RegisterDictionaryPtr&);
370 
372  static RiscOperatorsPtr instanceFromProtoval(const BaseSemantics::SValuePtr &protoval,
373  const SmtSolverPtr &solver = SmtSolverPtr());
374 
376  static RiscOperatorsPtr instanceFromState(const BaseSemantics::StatePtr&, const SmtSolverPtr &solver = SmtSolverPtr());
377 
379  // Virtual constructors
380 public:
382  const SmtSolverPtr &solver = SmtSolverPtr()) const override;
383 
385  const SmtSolverPtr &solver = SmtSolverPtr()) const override;
386 
388  // Dynamic pointer casts
389 public:
392  static RiscOperatorsPtr promote(const BaseSemantics::RiscOperatorsPtr&);
393 
395  // Methods first declared at this level of the class hierarchy
396 public:
401  const MemoryMap::Ptr get_memory_map() const { return map; }
402  void set_memory_map(const MemoryMap::Ptr &m) { map = m; }
405  // Risc operators inherited
407 public:
408  virtual void interrupt(int majr, int minr) override;
410  const BaseSemantics::SValuePtr &b_) override;
412  const BaseSemantics::SValuePtr &b_) override;
414  const BaseSemantics::SValuePtr &b_) override;
415  virtual BaseSemantics::SValuePtr invert(const BaseSemantics::SValuePtr &a_) override;
417  size_t begin_bit, size_t end_bit) override;
419  const BaseSemantics::SValuePtr &b_) override;
423  const BaseSemantics::SValuePtr &sa_) override;
425  const BaseSemantics::SValuePtr &sa_) override;
427  const BaseSemantics::SValuePtr &sa_) override;
429  const BaseSemantics::SValuePtr &sa_) override;
431  const BaseSemantics::SValuePtr &sa_) override;
434  const BaseSemantics::SValuePtr &a_,
435  const BaseSemantics::SValuePtr &b_,
436  IteStatus&) override;
437  virtual BaseSemantics::SValuePtr signExtend(const BaseSemantics::SValuePtr &a_, size_t new_width) override;
439  const BaseSemantics::SValuePtr &b_) override;
441  const BaseSemantics::SValuePtr &b_,
442  const BaseSemantics::SValuePtr &c_,
443  BaseSemantics::SValuePtr &carry_out/*out*/) override;
444  virtual BaseSemantics::SValuePtr negate(const BaseSemantics::SValuePtr &a_) override;
446  const BaseSemantics::SValuePtr &b_) override;
448  const BaseSemantics::SValuePtr &b_) override;
450  const BaseSemantics::SValuePtr &b_) override;
452  const BaseSemantics::SValuePtr &b_) override;
454  const BaseSemantics::SValuePtr &b_) override;
456  const BaseSemantics::SValuePtr &b_) override;
458  const BaseSemantics::SValuePtr &addr,
459  const BaseSemantics::SValuePtr &dflt,
460  const BaseSemantics::SValuePtr &cond) override;
462  const BaseSemantics::SValuePtr &addr,
463  const BaseSemantics::SValuePtr &dflt) override;
464  virtual void writeMemory(RegisterDescriptor segreg,
465  const BaseSemantics::SValuePtr &addr,
466  const BaseSemantics::SValuePtr &data,
467  const BaseSemantics::SValuePtr &cond) override;
468 
469 protected:
470  BaseSemantics::SValuePtr readOrPeekMemory(RegisterDescriptor segreg, const BaseSemantics::SValuePtr &address,
471  const BaseSemantics::SValuePtr &dflt_, bool allowSideEffects);
472 };
473 
474 } // namespace
475 } // namespace
476 } // namespace
477 } // namespace
478 
479 #endif
480 #endif
virtual BaseSemantics::SValuePtr undefined_(size_t nbits) const override
Create a new undefined semantic value.
Base classes for instruction semantics.
Definition: Dispatcher.h:18
virtual void set_width(size_t nbits)
Virtual API.
Definition: SValue.h:309
virtual void discard_popped_memory()
Removes from memory those values at addresses below the current stack pointer.
boost::shared_ptr< class MemoryCellList > MemoryCellListPtr
Shared-ownership pointer to a list-based memory state.
Type of values manipulated by the PartialSymbolicSemantics domain.
boost::shared_ptr< RiscOperators > RiscOperatorsPtr
Shared-ownership pointer to a RISC operators object.
virtual BaseSemantics::SValuePtr signedModulo(const BaseSemantics::SValuePtr &a_, const BaseSemantics::SValuePtr &b_) override
Calculates modulo with signed values.
virtual BaseSemantics::SValuePtr concat(const BaseSemantics::SValuePtr &a_, const BaseSemantics::SValuePtr &b_) override
Concatenates the bits of two values.
virtual Sawyer::Optional< BaseSemantics::SValuePtr > createOptionalMerge(const BaseSemantics::SValuePtr &other, const BaseSemantics::MergerPtr &, const SmtSolverPtr &) const override
Possibly create a new value by merging two existing values.
static MemoryCellListPtr promote(const BaseSemantics::MemoryStatePtr &m)
Promote a base memory state pointer to a BaseSemantics::MemoryCellList pointer.
static SValuePtr promote(const BaseSemantics::SValuePtr &v)
Promote a base value to a PartialSymbolicSemantics value.
virtual BaseSemantics::StatePtr create(const BaseSemantics::RegisterStatePtr &registers, const BaseSemantics::MemoryStatePtr &memory) const override
Virtual constructor.
virtual BaseSemantics::SValuePtr create(size_t nbits, uint64_t name, uint64_t offset, bool negate) const
Virtual allocating constructor.
virtual BaseSemantics::SValuePtr negate(const BaseSemantics::SValuePtr &a_) override
Two's complement.
virtual BaseSemantics::SValuePtr rotateRight(const BaseSemantics::SValuePtr &a_, const BaseSemantics::SValuePtr &sa_) override
Rotate bits to the right.
virtual BaseSemantics::SValuePtr signExtend(const BaseSemantics::SValuePtr &a_, size_t new_width) override
Sign extends a value.
Holds a value or nothing.
Definition: Optional.h:49
virtual BaseSemantics::SValuePtr shiftRight(const BaseSemantics::SValuePtr &a_, const BaseSemantics::SValuePtr &sa_) override
Returns arg shifted right logically (no sign bit).
virtual BaseSemantics::SValuePtr bottom_(size_t nbits) const override
Data-flow bottom value.
virtual BaseSemantics::RiscOperatorsPtr create(const BaseSemantics::SValuePtr &protoval, const SmtSolverPtr &solver=SmtSolverPtr()) const override
Virtual allocating constructor.
boost::shared_ptr< RegisterState > RegisterStatePtr
Shared-ownership pointer to a register state.
bool negate
Switch between name+offset and (-name)+offset; should be false for constants.
virtual BaseSemantics::SValuePtr invert(const BaseSemantics::SValuePtr &a_) override
One's complement.
virtual BaseSemantics::SValuePtr or_(const BaseSemantics::SValuePtr &a_, const BaseSemantics::SValuePtr &b_) override
Computes bit-wise OR of two values.
virtual bool equal_registers(const StatePtr &other) const
Tests registers of two states for equality.
static StatePtr instance(const BaseSemantics::RegisterStatePtr &registers, const BaseSemantics::MemoryStatePtr &memory)
Instantiates a new instance of memory state with specified register and memory states.
Main namespace for the ROSE library.
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 BaseSemantics::SValuePtr addWithCarries(const BaseSemantics::SValuePtr &a_, const BaseSemantics::SValuePtr &b_, const BaseSemantics::SValuePtr &c_, BaseSemantics::SValuePtr &carry_out) override
Add two values of equal size and a carry bit.
virtual BaseSemantics::SValuePtr number_(size_t nbits, uint64_t value) const override
Create a new concrete semantic value.
boost::shared_ptr< class State > StatePtr
Shared-ownership pointer to partial symbolic semantics state.
static uint64_t nextName()
Returns the next available name.
Reference-counting intrusive smart pointer.
Definition: SharedPointer.h:68
boost::shared_ptr< State > StatePtr
Shared-ownership pointer to a semantic state.
virtual BaseSemantics::SValuePtr xor_(const BaseSemantics::SValuePtr &a_, const BaseSemantics::SValuePtr &b_) override
Computes bit-wise XOR of two values.
static RiscOperatorsPtr instanceFromProtoval(const BaseSemantics::SValuePtr &protoval, const SmtSolverPtr &solver=SmtSolverPtr())
Instantiates a new RiscOperators object with specified prototypical values.
static RiscOperatorsPtr promote(const BaseSemantics::RiscOperatorsPtr &)
Run-time promotion of a base RiscOperators pointer to partial symbolic operators. ...
virtual BaseSemantics::StatePtr clone() const override
Virtual copy constructor.
uint64_t name
Zero for constants; non-zero ID number for everything else.
static RiscOperatorsPtr instanceFromState(const BaseSemantics::StatePtr &, const SmtSolverPtr &solver=SmtSolverPtr())
Instantiates a new RiscOperators with specified state.
virtual void hash(Combinatorics::Hasher &) const override
Hash this semantic value.
boost::shared_ptr< class RegisterStateGeneric > RegisterStateGenericPtr
Shared-ownership pointer to generic register states.
boost::shared_ptr< MemoryState > MemoryStatePtr
Shared-ownership pointer to a memory state.
virtual void print_diff_registers(std::ostream &, const StatePtr &other_state, Formatter &) const
Print info about how registers differ.
virtual BaseSemantics::SValuePtr copy(size_t new_width=0) const override
Create a new value from an existing value, changing the width if new_width is non-zero.
virtual void writeMemory(RegisterDescriptor segreg, const BaseSemantics::SValuePtr &addr, const BaseSemantics::SValuePtr &data, const BaseSemantics::SValuePtr &cond) override
Writes a value to memory.
virtual BaseSemantics::SValuePtr unsignedModulo(const BaseSemantics::SValuePtr &a_, const BaseSemantics::SValuePtr &b_) override
Calculates modulo with unsigned values.
virtual BaseSemantics::SValuePtr signedDivide(const BaseSemantics::SValuePtr &a_, const BaseSemantics::SValuePtr &b_) override
Divides two signed values.
virtual BaseSemantics::SValuePtr add(const BaseSemantics::SValuePtr &a_, const BaseSemantics::SValuePtr &b_) override
Adds two integers of equal size.
Describes (part of) a physical CPU register.
virtual bool isBottom() const override
Determines whether a value is a data-flow bottom.
virtual void interrupt(int majr, int minr) override
Invoked for instructions that cause an interrupt.
static SValuePtr instance(size_t nbits, uint64_t value)
Instantiate a new concrete value.
virtual BaseSemantics::SValuePtr signedMultiply(const BaseSemantics::SValuePtr &a_, const BaseSemantics::SValuePtr &b_) override
Multiplies two signed values.
virtual BaseSemantics::SValuePtr leastSignificantSetBit(const BaseSemantics::SValuePtr &a_) override
Returns position of least significant set bit; zero when no bits are set.
static SValuePtr instance(size_t nbits, uint64_t name, uint64_t offset, bool negate)
Insantiate a new value with all the necessary parts.
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...
virtual BaseSemantics::SValuePtr extract(const BaseSemantics::SValuePtr &a_, size_t begin_bit, size_t end_bit) override
Extracts bits from a value.
virtual BaseSemantics::SValuePtr equalToZero(const BaseSemantics::SValuePtr &a_) override
Determines whether a value is equal to zero.
SharedPointer< U > dynamicCast() const
Dynamic cast.
Binary analysis.
virtual BaseSemantics::SValuePtr readMemory(RegisterDescriptor segreg, const BaseSemantics::SValuePtr &addr, const BaseSemantics::SValuePtr &dflt, const BaseSemantics::SValuePtr &cond) override
Reads a value from memory.
static SValuePtr instance(size_t nbits)
Instantiate a new undefined value of specified width.
static RiscOperatorsPtr instanceFromRegisters(const RegisterDictionaryPtr &)
Instantiates a new RiscOperators object and configures it to use semantic values and states that are ...
virtual BaseSemantics::SValuePtr peekMemory(RegisterDescriptor segreg, const BaseSemantics::SValuePtr &addr, const BaseSemantics::SValuePtr &dflt) override
Read memory without side effects.
virtual bool must_equal(const BaseSemantics::SValuePtr &other, const SmtSolverPtr &solver=SmtSolverPtr()) const override
Virtual API.
virtual BaseSemantics::SValuePtr rotateLeft(const BaseSemantics::SValuePtr &a_, const BaseSemantics::SValuePtr &sa_) override
Rotate bits to the left.
virtual SmtSolverPtr solver() const
Property: Satisfiability module theory (SMT) solver.
boost::shared_ptr< class RiscOperators > RiscOperatorsPtr
Shared-ownership pointer to partial symbolic semantics RISC operations.
virtual BaseSemantics::SValuePtr shiftLeft(const BaseSemantics::SValuePtr &a_, const BaseSemantics::SValuePtr &sa_) override
Returns arg shifted left.
virtual BaseSemantics::SValuePtr unsignedMultiply(const BaseSemantics::SValuePtr &a_, const BaseSemantics::SValuePtr &b_) override
Multiply two unsigned values.
static StatePtr instance(const StatePtr &other)
Instantiates a new copy of an existing state.
virtual bool may_equal(const BaseSemantics::SValuePtr &other, const SmtSolverPtr &solver=SmtSolverPtr()) const override
Virtual API.
virtual void print(std::ostream &, BaseSemantics::Formatter &) const override
Print a value to a stream using default format.
virtual BaseSemantics::SValuePtr mostSignificantSetBit(const BaseSemantics::SValuePtr &a_) override
Returns position of most significant set bit; zero when no bits are set.
virtual SValuePtr protoval() const
Property: Prototypical semantic value.
Base class for most instruction semantics RISC operators.
Definition: RiscOperators.h:48
virtual BaseSemantics::SValuePtr unsignedDivide(const BaseSemantics::SValuePtr &a_, const BaseSemantics::SValuePtr &b_) override
Divides two unsigned values.
virtual BaseSemantics::SValuePtr iteWithStatus(const BaseSemantics::SValuePtr &sel_, const BaseSemantics::SValuePtr &a_, const BaseSemantics::SValuePtr &b_, IteStatus &) override
If-then-else with status.
Sawyer::SharedPointer< class SValue > SValuePtr
Shared-ownership pointer to a partial-symbolic semantic value.
Base class for semantics machine states.
Definition: State.h:39
virtual BaseSemantics::SValuePtr unspecified_(size_t nbits) const override
Create a new unspecified semantic value.
virtual BaseSemantics::SValuePtr shiftRightArithmetic(const BaseSemantics::SValuePtr &a_, const BaseSemantics::SValuePtr &sa_) override
Returns arg shifted right arithmetically (with sign bit).
virtual BaseSemantics::SValuePtr and_(const BaseSemantics::SValuePtr &a_, const BaseSemantics::SValuePtr &b_) override
Computes bit-wise AND of two values.