ROSE  0.9.9.109
PartialSymbolicSemantics2.h
1 #ifndef Rose_PartialSymbolicSemantics2_H
2 #define Rose_PartialSymbolicSemantics2_H
3 
4 
5 #ifndef __STDC_FORMAT_MACROS
6 #define __STDC_FORMAT_MACROS
7 #endif
8 #include <inttypes.h>
9 
10 #include <map>
11 #include <stdint.h>
12 #include <vector>
13 
14 #include "rosePublicConfig.h"
15 #ifdef ROSE_HAVE_LIBGCRYPT
16 #include <gcrypt.h>
17 #endif
18 
19 #include "BaseSemantics2.h"
20 #include "integerOps.h"
21 #include "MemoryMap.h"
22 #include "FormatRestorer.h"
23 #include "RegisterStateGeneric.h"
24 #include "MemoryCellList.h"
25 
26 namespace Rose {
27 namespace BinaryAnalysis { // documented elsewhere
28 namespace InstructionSemantics2 { // documented elsewhere
29 
43 namespace PartialSymbolicSemantics {
44 
45 extern uint64_t name_counter;
46 
48 // Print formatter
50 
54 protected:
55  typedef std::map<uint64_t, uint64_t> Map;
56  Map renames;
57  size_t next_name;
58 public:
59  Formatter(): next_name(1) {}
60  uint64_t rename(uint64_t orig_name);
61 };
62 
63 
65 // Semantic values
67 
70 
74 public:
75  uint64_t name;
76  uint64_t offset;
77  bool negate;
79  // Real constructors
81 protected:
82  explicit SValue(size_t nbits)
83  : BaseSemantics::SValue(nbits), name(++name_counter), offset(0), negate(false) {}
84 
85  SValue(size_t nbits, uint64_t number)
86  : BaseSemantics::SValue(nbits), name(0), offset(number), negate(false) {
87  if (nbits <= 64) {
88  this->offset &= IntegerOps::genMask<uint64_t>(nbits);
89  } else {
90  name = ++name_counter;
91  offset = 0;
92  }
93  }
94 
95  SValue(size_t nbits, uint64_t name, uint64_t offset, bool negate)
96  : BaseSemantics::SValue(nbits), name(name), offset(offset), negate(negate) {
97  this->offset &= IntegerOps::genMask<uint64_t>(nbits);
98  }
99 
101  // Static allocating constructors
102 public:
104  static SValuePtr instance() {
105  return SValuePtr(new SValue(1));
106  }
107 
109  static SValuePtr instance(size_t nbits) {
110  return SValuePtr(new SValue(nbits));
111  }
112 
114  static SValuePtr instance(size_t nbits, uint64_t value) {
115  return SValuePtr(new SValue(nbits, value));
116  }
117 
119  static SValuePtr instance(size_t nbits, uint64_t name, uint64_t offset, bool negate) {
120  return SValuePtr(new SValue(nbits, name, offset, negate));
121  }
122 
124  // Virtual constructors
125 public:
126  virtual BaseSemantics::SValuePtr bottom_(size_t nbits) const ROSE_OVERRIDE {
127  return instance(nbits);
128  }
129  virtual BaseSemantics::SValuePtr undefined_(size_t nbits) const ROSE_OVERRIDE {
130  return instance(nbits);
131  }
132  virtual BaseSemantics::SValuePtr unspecified_(size_t nbits) const ROSE_OVERRIDE {
133  return instance(nbits);
134  }
135 
136  virtual BaseSemantics::SValuePtr number_(size_t nbits, uint64_t value) const ROSE_OVERRIDE {
137  return instance(nbits, value);
138  }
139 
140  virtual BaseSemantics::SValuePtr copy(size_t new_width=0) const ROSE_OVERRIDE {
141  SValuePtr retval(new SValue(*this));
142  if (new_width!=0 && new_width!=retval->get_width())
143  retval->set_width(new_width);
144  return retval;
145  }
146 
148  createOptionalMerge(const BaseSemantics::SValuePtr &other,const BaseSemantics::MergerPtr&, SMTSolver*) const ROSE_OVERRIDE;
149 
151  virtual BaseSemantics::SValuePtr create(size_t nbits, uint64_t name, uint64_t offset, bool negate) const {
152  return instance(nbits, name, offset, negate);
153  }
154 
156  // Dynamic pointer casts
157 public:
160  static SValuePtr promote(const BaseSemantics::SValuePtr &v) {
161  SValuePtr retval = v.dynamicCast<SValue>();
162  ASSERT_not_null(retval);
163  return retval;
164  }
165 
167  // Other stuff we inherited from the super class
168 public:
169  virtual void set_width(size_t nbits) ROSE_OVERRIDE {
171  offset &= IntegerOps::genMask<uint64_t>(nbits);
172  }
173 
174  virtual bool may_equal(const BaseSemantics::SValuePtr &other, SMTSolver *solver=NULL) const ROSE_OVERRIDE;
175  virtual bool must_equal(const BaseSemantics::SValuePtr &other, SMTSolver *solver=NULL) const ROSE_OVERRIDE;
176 
177  virtual void print(std::ostream&, BaseSemantics::Formatter&) const ROSE_OVERRIDE;
178 
179  virtual bool isBottom() const ROSE_OVERRIDE {
180  return false;
181  }
182 
183  virtual bool is_number() const ROSE_OVERRIDE {
184  return 0==name;
185  }
186 
187  virtual uint64_t get_number() const ROSE_OVERRIDE {
188  ASSERT_require(is_number());
189  return offset;
190  }
191 };
192 
193 
195 // Register state
197 
198 typedef BaseSemantics::RegisterStateGeneric RegisterState;
199 typedef BaseSemantics::RegisterStateGenericPtr RegisterStatePtr;
200 
201 
203 // Memory state
205 
206 // PartialSymbolicSemantics uses BaseSemantics::MemoryCellList (or subclass) as its memory state, and does not expect the
207 // MemoryCellList to be byte-restricted (i.e., the cells can store multi-byte values).
208 
209 typedef BaseSemantics::MemoryCellList MemoryState;
210 typedef BaseSemantics::MemoryCellListPtr MemoryStatePtr;
211 
212 
214 // Complete state
216 
218 typedef boost::shared_ptr<class State> StatePtr;
219 
223 
225  // Real constructors
226 protected:
227  State(const BaseSemantics::RegisterStatePtr &registers,
228  const BaseSemantics::MemoryStatePtr &memory)
229  : BaseSemantics::State(registers, memory) {
230  // This state should use PartialSymbolicSemantics values (or subclasses thereof)
231  ASSERT_not_null(registers);
232  (void) SValue::promote(registers->protoval());
233  ASSERT_not_null(memory);
234  (void) SValue::promote(memory->get_addr_protoval());
235  (void) SValue::promote(memory->get_val_protoval());
236 
237  // This state should use a memory that is not byte restricted.
238  MemoryStatePtr mcl = MemoryState::promote(memory);
239  ASSERT_require(!mcl->byteRestricted());
240  }
241 
242  State(const State &other): BaseSemantics::State(other) {}
243 
245  // Static allocating constructors
246 public:
248  static StatePtr instance(const BaseSemantics::RegisterStatePtr &registers,
249  const BaseSemantics::MemoryStatePtr &memory) {
250  return StatePtr(new State(registers, memory));
251  }
252 
254  static StatePtr instance(const StatePtr &other) {
255  return StatePtr(new State(*other));
256  }
257 
259  // Virtual constructors
260 public:
262  const BaseSemantics::MemoryStatePtr &memory) const ROSE_OVERRIDE {
263  return instance(registers, memory);
264  }
265 
266  virtual BaseSemantics::StatePtr clone() const ROSE_OVERRIDE {
267  StatePtr self = promote(boost::const_pointer_cast<BaseSemantics::State>(shared_from_this()));
268  return instance(self);
269  }
270 
272  // Dynamic pointer casts
273 public:
274  static StatePtr promote(const BaseSemantics::StatePtr &x) {
275  StatePtr retval = boost::dynamic_pointer_cast<State>(x);
276  ASSERT_not_null(x);
277  return retval;
278  }
279 
281  // Methods first declared at this level of the class hierarchy
282 public:
285  virtual void print_diff_registers(std::ostream&, const StatePtr &other_state, Formatter&) const;
286 
288  virtual bool equal_registers(const StatePtr &other) const;
289 
292  virtual void discard_popped_memory();
293 };
294 
295 
297 // RISC operators
299 
301 typedef boost::shared_ptr<class RiscOperators> RiscOperatorsPtr;
302 
305 protected:
306  MemoryMap::Ptr map;
307 
309  // Real constructors
310 protected:
312  : BaseSemantics::RiscOperators(protoval, solver) {
313  name("PartialSymbolic");
314  }
315  explicit RiscOperators(const BaseSemantics::StatePtr &state, SMTSolver *solver=NULL)
317  name("PartialSymbolic");
318  }
319 
321  // Static allocating constructors
322 public:
325  static RiscOperatorsPtr instance(const RegisterDictionary *regdict);
326 
328  static RiscOperatorsPtr instance(const BaseSemantics::SValuePtr &protoval, SMTSolver *solver=NULL) {
329  return RiscOperatorsPtr(new RiscOperators(protoval, solver));
330  }
331 
333  static RiscOperatorsPtr instance(const BaseSemantics::StatePtr &state, SMTSolver *solver=NULL) {
334  return RiscOperatorsPtr(new RiscOperators(state, solver));
335  }
336 
338  // Virtual constructors
339 public:
341  SMTSolver *solver=NULL) const ROSE_OVERRIDE {
342  return instance(protoval, solver);
343  }
344 
346  SMTSolver *solver=NULL) const ROSE_OVERRIDE {
347  return instance(state, solver);
348  }
349 
351  // Dynamic pointer casts
352 public:
355  static RiscOperatorsPtr promote(const BaseSemantics::RiscOperatorsPtr &x) {
356  RiscOperatorsPtr retval = boost::dynamic_pointer_cast<RiscOperators>(x);
357  ASSERT_not_null(retval);
358  return retval;
359  }
360 
362  // Methods first declared at this level of the class hierarchy
363 public:
368  const MemoryMap::Ptr get_memory_map() const { return map; }
369  void set_memory_map(const MemoryMap::Ptr &m) { map = m; }
372  // Risc operators inherited
374 public:
375  virtual void interrupt(int majr, int minr) ROSE_OVERRIDE;
377  const BaseSemantics::SValuePtr &b_) ROSE_OVERRIDE;
379  const BaseSemantics::SValuePtr &b_) ROSE_OVERRIDE;
381  const BaseSemantics::SValuePtr &b_) ROSE_OVERRIDE;
382  virtual BaseSemantics::SValuePtr invert(const BaseSemantics::SValuePtr &a_) ROSE_OVERRIDE;
384  size_t begin_bit, size_t end_bit) ROSE_OVERRIDE;
386  const BaseSemantics::SValuePtr &b_) ROSE_OVERRIDE;
390  const BaseSemantics::SValuePtr &sa_) ROSE_OVERRIDE;
392  const BaseSemantics::SValuePtr &sa_) ROSE_OVERRIDE;
394  const BaseSemantics::SValuePtr &sa_) ROSE_OVERRIDE;
396  const BaseSemantics::SValuePtr &sa_) ROSE_OVERRIDE;
398  const BaseSemantics::SValuePtr &sa_) ROSE_OVERRIDE;
399  virtual BaseSemantics::SValuePtr equalToZero(const BaseSemantics::SValuePtr &a_) ROSE_OVERRIDE;
401  const BaseSemantics::SValuePtr &a_,
402  const BaseSemantics::SValuePtr &b_) ROSE_OVERRIDE;
403  virtual BaseSemantics::SValuePtr signExtend(const BaseSemantics::SValuePtr &a_, size_t new_width) ROSE_OVERRIDE;
405  const BaseSemantics::SValuePtr &b_) ROSE_OVERRIDE;
407  const BaseSemantics::SValuePtr &b_,
408  const BaseSemantics::SValuePtr &c_,
409  BaseSemantics::SValuePtr &carry_out/*out*/) ROSE_OVERRIDE;
410  virtual BaseSemantics::SValuePtr negate(const BaseSemantics::SValuePtr &a_) ROSE_OVERRIDE;
412  const BaseSemantics::SValuePtr &b_) ROSE_OVERRIDE;
414  const BaseSemantics::SValuePtr &b_) ROSE_OVERRIDE;
416  const BaseSemantics::SValuePtr &b_) ROSE_OVERRIDE;
418  const BaseSemantics::SValuePtr &b_) ROSE_OVERRIDE;
420  const BaseSemantics::SValuePtr &b_) ROSE_OVERRIDE;
422  const BaseSemantics::SValuePtr &b_) ROSE_OVERRIDE;
424  const BaseSemantics::SValuePtr &addr,
425  const BaseSemantics::SValuePtr &dflt,
426  const BaseSemantics::SValuePtr &cond) ROSE_OVERRIDE;
427  virtual void writeMemory(RegisterDescriptor segreg,
428  const BaseSemantics::SValuePtr &addr,
429  const BaseSemantics::SValuePtr &data,
430  const BaseSemantics::SValuePtr &cond) ROSE_OVERRIDE;
431 
432 
433 #if 0
434 
435 protected:
436  mutable State<SValue> orig_state;
447  bool p_discard_popped_memory;
452  MemoryMap *map;
454  public:
455  typedef State<SValue> StateType;
456 
457  Policy(): cur_insn(NULL), p_discard_popped_memory(false), ninsns(0), map(NULL) {
458  /* So that named values are identical in both; reinitialized by first call to startInstruction(). */
459  set_register_dictionary(RegisterDictionary::dictionary_pentium4());
460  orig_state = cur_state;
461  }
462 
465  const State<SValue>& get_orig_state() const { return orig_state; }
466  State<SValue>& get_orig_state() { return orig_state; }
467 
469  typename State<SValue>::Memory memory_for_equality(const State<SValue>&) const;
470 
473  typename State<SValue>::Memory memory_for_equality() const { return memory_for_equality(cur_state); }
474 
478  bool equal_states(const State<SValue>&, const State<SValue>&) const;
479 
482  bool on_stack(const SValue<32> &value) const;
483 
486  void set_discard_popped_memory(bool b) {
487  p_discard_popped_memory = b;
488  }
489 
492  bool get_discard_popped_memory() const {
493  return p_discard_popped_memory;
494  }
495 
498  void print_diff(std::ostream&, const State<SValue>&, const State<SValue>&, RenameMap *rmap=NULL) const ;
499 
502  void print_diff(std::ostream &o, const State<SValue> &state, RenameMap *rmap=NULL) const {
503  print_diff(o, orig_state, state, rmap);
504  }
505 
508  void print_diff(std::ostream &o, RenameMap *rmap=NULL) const {
509  print_diff(o, orig_state, cur_state, rmap);
510  }
511 
514  std::string SHA1() const;
515 
520  bool SHA1(unsigned char *digest) const;
521 
523  enum MemRefType { MRT_STACK_PTR, MRT_FRAME_PTR, MRT_OTHER_PTR };
524 
529  MemRefType memory_reference_type(const State<SValue> &state, const SValue<32> &addr) const {
530  if (addr.name) {
531  if (addr.name==state.registers.gpr[x86_gpr_sp].name) return MRT_STACK_PTR;
532  if (addr.name==state.registers.gpr[x86_gpr_bp].name) return MRT_FRAME_PTR;
533  return MRT_OTHER_PTR;
534  }
535  if (addr==state.registers.gpr[x86_gpr_sp]) return MRT_STACK_PTR;
536  if (addr==state.registers.gpr[x86_gpr_bp]) return MRT_FRAME_PTR;
537  return MRT_OTHER_PTR;
538  }
539 
540 
541 
542 
543  /*************************************************************************************************************
544  * Functions invoked by the X86InstructionSemantics class for data access operations
545  *************************************************************************************************************/
546 
547 #include "ReadWriteRegisterFragment.h"
548 
550  template <size_t Len> SValue<Len>
551  readMemory(X86SegmentRegister segreg, const SValue<32> &addr, const SValue<1> &cond) const {
552  return mem_read<Len>(cur_state, addr);
553  }
554 
556  template <size_t Len> void
557  writeMemory(X86SegmentRegister segreg, const SValue<32> &addr, const SValue<Len> &data,
558  const SValue<1> &cond) {
559  mem_write<Len>(cur_state, addr, data);
560  }
561 #endif
562 
563  };
564 
565 
566 #if 0
567  /*************************************************************************************************************
568  * MemoryCell template functions
569  *************************************************************************************************************/
570 
571  template<template <size_t> class SValue>
572  bool
573  MemoryCell<SValue>::may_alias(const MemoryCell &other) const {
574  const SValue<32> &addr1 = this->address;
575  const SValue<32> &addr2 = other.address;
576  if (addr1.name != addr2.name) return true;
577 
578  /* Same unknown values but inverses (any offset). */
579  if (addr1.name && addr1.negate!=addr2.negate) return true;
580 
581  /* If they have the same base values (or are both constant) then check the offsets. The 32-bit casts are
582  * purportedly necessary to wrap propertly, but I'm not sure this will work for addresses (LatticeElements)
583  * that have a length other than 32 bits. [FIXME RPM 2009-02-03]. */
584  uint32_t offsetDiff = (uint32_t)(addr1.offset - addr2.offset);
585  if (offsetDiff < this->nbytes || offsetDiff > (uint32_t)(-other.nbytes))
586  return true;
587  return false;
588  }
589 
590  template<template<size_t> class SValue>
591  bool
592  MemoryCell<SValue>::must_alias(const MemoryCell<SValue> &other) const {
593  return this->address == other.address;
594  }
595 #endif
596 
597 #if 0
598  /*****************************************************************************************************************
599  * State template functions
600  *****************************************************************************************************************/
601 
602  template<template<size_t> class SValue>
603  void
604  State<SValue>::print_diff_registers(std::ostream &o, const State &other, RenameMap *rmap/*=NULL*/) const
605  {
606 #ifndef CXX_IS_ROSE_ANALYSIS
607  // DQ (5/22/2010): This code does not compile using ROSE, it needs to be investigated to be reduced to an bug
608  // report.
609 
610  std::string prefix = " ";
611 
612  for (size_t i=0; i<this->registers.n_gprs; ++i) {
613  if (this->registers.gpr[i]!=other.registers.gpr[i]) {
614  o <<prefix <<gprToString((X86GeneralPurposeRegister)i) <<": "
615  <<this->registers.gpr[i].rename(rmap) <<" -> " <<other.registers.gpr[i].rename(rmap) <<"\n";
616  }
617  }
618  for (size_t i=0; i<this->registers.n_segregs; ++i) {
619  if (this->registers.segreg[i]!=other.registers.segreg[i]) {
620  o <<prefix <<segregToString((X86SegmentRegister)i) <<": "
621  <<this->registers.segreg[i].rename(rmap) <<" -> " <<other.registers.segreg[i].rename(rmap) <<"\n";
622  }
623  }
624  for (size_t i=0; i<this->registers.n_flags; ++i) {
625  if (this->registers.flag[i]!=other.registers.flag[i]) {
626  o <<prefix <<flagToString((X86Flag)i) <<": "
627  <<this->registers.flag[i].rename(rmap) <<" -> " <<other.registers.flag[i].rename(rmap) <<"\n";
628  }
629  }
630  if (this->registers.ip!=other.registers.ip) {
631  o <<prefix <<"ip: " <<this->registers.ip.rename(rmap) <<" -> " <<other.registers.ip.rename(rmap) <<"\n";
632  }
633 #endif
634  }
635 
636  template<template<size_t> class SValue>
637  bool
638  State<SValue>::equal_registers(const State &other) const
639  {
640 #ifndef CXX_IS_ROSE_ANALYSIS
641  for (size_t i=0; i<this->registers.n_gprs; ++i)
642  if (this->registers.gpr[i]!=other.registers.gpr[i]) return false;
643  for (size_t i=0; i<this->registers.n_segregs; ++i)
644  if (this->registers.segreg[i]!=other.registers.segreg[i]) return false;
645  for (size_t i=0; i<this->registers.n_flags; ++i)
646  if (this->registers.flag[i]!=other.registers.flag[i]) return false;
647  if (this->registers.ip!=other.registers.ip) return false;
648 #endif
649  return true;
650  }
651 
652  template<template<size_t> class SValue>
653  void
655  {
656  Memory new_mem;
657  const SValue<32> &sp = this->registers.gpr[x86_gpr_sp];
658  for (typename Memory::const_iterator mi=this->memory.begin(); mi!=this->memory.end(); ++mi) {
659  const SValue<32> &addr = mi->get_address();
660  if (addr.name!=sp.name || addr.negate!=sp.negate || (int32_t)addr.offset>=(int32_t)sp.offset)
661  new_mem.push_back(*mi);
662  }
663  this->memory = new_mem;
664  }
665 #endif
666 
667 #if 0
668  /*****************************************************************************************************************
669  * Policy template functions
670  *****************************************************************************************************************/
671 
672  /* Returns memory that needs to be compared by equal_states() */
673  template<
674  template <template <size_t> class SValue> class State,
675  template<size_t> class SValue>
676  typename State<SValue>::Memory
677  Policy<State, SValue>::memory_for_equality(const State<SValue> &state) const
678  {
679  State<SValue> tmp_state = state;
680  typename State<SValue>::Memory retval;
681 #ifndef CXX_IS_ROSE_ANALYSIS
682  for (typename State<SValue>::Memory::const_iterator mi=state.memory.begin(); mi!=state.memory.end(); ++mi) {
683  if (mi->is_written() && mi->get_data()!=mem_read<32>(orig_state, mi->get_address()))
684  retval.push_back(*mi);
685  }
686 #endif
687  return retval;
688  }
689 
690  template<
691  template <template <size_t> class SValue> class State,
692  template<size_t> class SValue>
693  bool
694  Policy<State, SValue>::equal_states(const State<SValue> &s1, const State<SValue> &s2) const
695  {
696 #ifndef CXX_IS_ROSE_ANALYSIS
697  if (!s1.equal_registers(s2))
698  return false;
699  typename State<SValue>::Memory m1 = memory_for_equality(s1);
700  typename State<SValue>::Memory m2 = memory_for_equality(s2);
701  std::vector<typename State<SValue>::Memory::value_type> v1(m1.begin(), m1.end());
702  std::vector<typename State<SValue>::Memory::value_type> v2(m1.begin(), m1.end());
703  if (v1.size()!=v2.size())
704  return false;
705  std::sort(v1.begin(), v1.end());
706  std::sort(v2.begin(), v2.end());
707  for (size_t i=0; i<v1.size(); ++i) {
708  if (v1[i].get_nbytes() != v2[i].get_nbytes() ||
709  v1[i].get_address()!= v2[i].get_address() ||
710  v1[i].get_data() != v2[i].get_data())
711  return false;
712  }
713 #endif
714  return true;
715  }
716 
717  template<
718  template <template <size_t> class SValue> class State,
719  template<size_t> class SValue>
720  void
721  Policy<State, SValue>::print(std::ostream &o, RenameMap *rmap/*=NULL*/) const
722  {
723  cur_state.print(o, "", rmap);
724  }
725 
726  template<
727  template <template <size_t> class SValue> class State,
728  template<size_t> class SValue>
729  void
730  Policy<State, SValue>::print_diff(std::ostream &o, const State<SValue> &s1,
731  const State<SValue> &s2, RenameMap *rmap/*=NULL*/) const
732  {
733 #ifndef CXX_IS_ROSE_ANALYSIS
734  s1.print_diff_registers(o, s2, rmap);
735 
736  /* Get all addresses that have been written and are not currently clobbered. */
737  std::set<SValue<32> > addresses;
738  for (typename State<SValue>::Memory::const_iterator mi=s1.memory.begin(); mi!=s1.memory.end(); ++mi) {
739  if (!mi->is_clobbered() && mi->is_written())
740  addresses.insert(mi->get_address());
741  }
742  for (typename State<SValue>::Memory::const_iterator mi=s2.memory.begin(); mi!=s2.memory.end(); ++mi) {
743  if (!mi->is_clobbered() && mi->is_written())
744  addresses.insert(mi->get_address());
745  }
746 
747  State<SValue> tmp_s1 = s1;
748  State<SValue> tmp_s2 = s2;
749  size_t nmemdiff = 0;
750  for (typename std::set<SValue<32> >::const_iterator ai=addresses.begin(); ai!=addresses.end(); ++ai) {
751  SValue<32> v1 = mem_read<32>(tmp_s1, *ai);
752  SValue<32> v2 = mem_read<32>(tmp_s2, *ai);
753  if (v1 != v2) {
754  if (0==nmemdiff++) o <<" memory:\n";
755  o <<" " <<(*ai).rename(rmap) <<": " <<v1.rename(rmap) <<" -> " <<v2.rename(rmap) <<"\n";
756  }
757  }
758 #endif
759  }
760 
761  template<
762  template <template <size_t> class SValue> class State,
763  template<size_t> class SValue>
764  bool
765  Policy<State, SValue>::on_stack(const SValue<32> &value) const
766  {
767 #ifndef CXX_IS_ROSE_ANALYSIS
768  const SValue<32> sp_inverted = invert(cur_state.registers.gpr[x86_gpr_sp]);
769  for (typename State<SValue>::Memory::const_iterator mi=cur_state.memory.begin();
770  mi!=cur_state.memory.end();
771  ++mi) {
772  if (mi->get_nbytes()!=4 || !(mi->get_data()==value)) continue;
773  const SValue<32> &addr = mi->get_address();
774 
775  /* Is addr >= sp? */
776  SValue<32> carries = 0;
777  SValue<32> diff = addWithCarries(addr, sp_inverted, true_(), carries/*out*/);
778  SValue<1> sf = extract<31,32>(diff);
779  SValue<1> of = xor_(extract<31,32>(carries), extract<30,31>(carries));
780  if (sf==of) return true;
781  }
782 #endif
783  return false;
784  }
785 
786  template<
787  template <template <size_t> class SValue> class State,
788  template<size_t> class SValue>
789  bool
790  Policy<State, SValue>::SHA1(unsigned char digest[20]) const
791  {
792 #ifdef ROSE_HAVE_LIBGCRYPT
793  // libgcrypt should have been initialized by Rose::initialize already.
794  std::stringstream s;
795  RenameMap rmap;
796  print_diff(s, &rmap);
797  ROSE_ASSERT(gcry_md_get_algo_dlen(GCRY_MD_SHA1)==20);
798  gcry_md_hash_buffer(GCRY_MD_SHA1, digest, s.str().c_str(), s.str().size());
799  return true;
800 #else
801  memset(digest, 0, 20);
802  return false;
803 #endif
804  }
805 
806  template<
807  template <template <size_t> class SValue> class State,
808  template<size_t> class SValue>
809  std::string
810  Policy<State, SValue>::SHA1() const
811  {
812  std::string digest_str;
813  unsigned char digest[20];
814  if (SHA1(digest)) {
815  for (size_t i=sizeof digest; i>0; --i) {
816  digest_str += "0123456789abcdef"[(digest[i-1] >> 4) & 0xf];
817  digest_str += "0123456789abcdef"[digest[i-1] & 0xf];
818  }
819  }
820  return digest_str;
821  }
822 #endif
823 
824 } // namespace
825 } // namespace
826 } // namespace
827 } // namespace
828 
829 #endif
virtual BaseSemantics::StatePtr clone() const ROSE_OVERRIDE
Virtual copy constructor.
virtual void print(std::ostream &, BaseSemantics::Formatter &) const ROSE_OVERRIDE
Print a value to a stream using default format.
virtual BaseSemantics::SValuePtr signedModulo(const BaseSemantics::SValuePtr &a_, const BaseSemantics::SValuePtr &b_) ROSE_OVERRIDE
Calculates modulo with signed values.
virtual BaseSemantics::SValuePtr and_(const BaseSemantics::SValuePtr &a_, const BaseSemantics::SValuePtr &b_) ROSE_OVERRIDE
Computes bit-wise AND of two values.
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 BaseSemantics::SValuePtr or_(const BaseSemantics::SValuePtr &a_, const BaseSemantics::SValuePtr &b_) ROSE_OVERRIDE
Computes bit-wise OR of two values.
virtual BaseSemantics::SValuePtr rotateRight(const BaseSemantics::SValuePtr &a_, const BaseSemantics::SValuePtr &sa_) ROSE_OVERRIDE
Rotate bits to the right.
virtual BaseSemantics::SValuePtr concat(const BaseSemantics::SValuePtr &a_, const BaseSemantics::SValuePtr &b_) ROSE_OVERRIDE
Concatenates the bits of two values.
virtual BaseSemantics::SValuePtr unspecified_(size_t nbits) const ROSE_OVERRIDE
Create a new unspecified semantic value.
void invert(Word *words, const BitRange &range)
Invert bits.
virtual BaseSemantics::SValuePtr xor_(const BaseSemantics::SValuePtr &a_, const BaseSemantics::SValuePtr &b_) ROSE_OVERRIDE
Computes bit-wise XOR of two values.
virtual BaseSemantics::SValuePtr undefined_(size_t nbits) const ROSE_OVERRIDE
Create a new undefined semantic value.
virtual BaseSemantics::SValuePtr leastSignificantSetBit(const BaseSemantics::SValuePtr &a_) ROSE_OVERRIDE
Returns position of least significant set bit; zero when no bits are set.
virtual uint64_t get_number() const ROSE_OVERRIDE
Return the concrete number for this value.
STL namespace.
virtual BaseSemantics::SValuePtr ite(const BaseSemantics::SValuePtr &sel_, const BaseSemantics::SValuePtr &a_, const BaseSemantics::SValuePtr &b_) ROSE_OVERRIDE
If-then-else.
static RiscOperatorsPtr instance(const BaseSemantics::StatePtr &state, SMTSolver *solver=NULL)
Instantiates a new RiscOperators with specified state.
Holds a value or nothing.
Definition: Optional.h:49
virtual BaseSemantics::SValuePtr mostSignificantSetBit(const BaseSemantics::SValuePtr &a_) ROSE_OVERRIDE
Returns position of most significant set bit; zero when no bits are set.
Sawyer::SharedPointer< class SValue > SValuePtr
Shared-ownership pointer to a partial-symbolic semantic value.
virtual BaseSemantics::SValuePtr shiftLeft(const BaseSemantics::SValuePtr &a_, const BaseSemantics::SValuePtr &sa_) ROSE_OVERRIDE
Returns arg shifted left.
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.
virtual Sawyer::Optional< BaseSemantics::SValuePtr > createOptionalMerge(const BaseSemantics::SValuePtr &other, const BaseSemantics::MergerPtr &, SMTSolver *) const ROSE_OVERRIDE
Possibly create a new value by merging two existing values.
Main namespace for the ROSE library.
virtual BaseSemantics::SValuePtr add(const BaseSemantics::SValuePtr &a_, const BaseSemantics::SValuePtr &b_) ROSE_OVERRIDE
Adds two integers of equal size.
virtual BaseSemantics::SValuePtr extract(const BaseSemantics::SValuePtr &a_, size_t begin_bit, size_t end_bit) ROSE_OVERRIDE
Extracts bits from a value.
Describes (part of) a physical CPU register.
virtual BaseSemantics::SValuePtr invert(const BaseSemantics::SValuePtr &a_) ROSE_OVERRIDE
One's complement.
uint64_t name
Zero for constants; non-zero ID number for everything else.
virtual BaseSemantics::SValuePtr equalToZero(const BaseSemantics::SValuePtr &a_) ROSE_OVERRIDE
Determines whether a value is equal to zero.
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.
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.
bool negate
Switch between name+offset and (-name)+offset; should be false for constants.
virtual bool must_equal(const BaseSemantics::SValuePtr &other, SMTSolver *solver=NULL) const ROSE_OVERRIDE
Returns true if two values must be equal.
boost::shared_ptr< class RegisterState > RegisterStatePtr
Shared-ownership pointer to a register state.
boost::shared_ptr< class State > StatePtr
Shared-ownership pointer to a semantic state.
virtual void set_width(size_t nbits) ROSE_OVERRIDE
Accessor for value width.
virtual BaseSemantics::SValuePtr signExtend(const BaseSemantics::SValuePtr &a_, size_t new_width) ROSE_OVERRIDE
Sign extends a value.
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.
Base classes for instruction semantics.
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.
boost::shared_ptr< class RiscOperators > RiscOperatorsPtr
Shared-ownership pointer to a RISC operators object.
virtual BaseSemantics::SValuePtr rotateLeft(const BaseSemantics::SValuePtr &a_, const BaseSemantics::SValuePtr &sa_) ROSE_OVERRIDE
Rotate bits to the left.
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
Add two values of equal size and a carry bit.
virtual BaseSemantics::StatePtr create(const BaseSemantics::RegisterStatePtr &registers, const BaseSemantics::MemoryStatePtr &memory) const ROSE_OVERRIDE
Virtual constructor.
An efficient mapping from an address space to stored data.
Definition: MemoryMap.h:96
Defines registers available for a particular architecture.
Definition: Registers.h:32
virtual BaseSemantics::SValuePtr shiftRightArithmetic(const BaseSemantics::SValuePtr &a_, const BaseSemantics::SValuePtr &sa_) ROSE_OVERRIDE
Returns arg shifted right arithmetically (with sign bit).
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.
virtual BaseSemantics::RiscOperatorsPtr create(const BaseSemantics::SValuePtr &protoval, SMTSolver *solver=NULL) const ROSE_OVERRIDE
Virtual allocating constructor.
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.
static const RegisterDictionary * dictionary_pentium4()
Intel Pentium 4 registers.
boost::shared_ptr< class MemoryState > MemoryStatePtr
Shared-ownership pointer to a memory state.
virtual bool is_number() const ROSE_OVERRIDE
Determines if the value is a concrete number.
virtual BaseSemantics::SValuePtr shiftRight(const BaseSemantics::SValuePtr &a_, const BaseSemantics::SValuePtr &sa_) ROSE_OVERRIDE
Returns arg shifted right logically (no sign bit).
virtual BaseSemantics::SValuePtr number_(size_t nbits, uint64_t value) const ROSE_OVERRIDE
Create a new concrete semantic value.
boost::shared_ptr< class RiscOperators > RiscOperatorsPtr
Shared-ownership pointer to partial symbolic semantics RISC operations.
static RiscOperatorsPtr instance(const BaseSemantics::SValuePtr &protoval, SMTSolver *solver=NULL)
Instantiates a new RiscOperators object with specified prototypical values.
virtual BaseSemantics::RiscOperatorsPtr create(const BaseSemantics::StatePtr &state, SMTSolver *solver=NULL) const ROSE_OVERRIDE
Virtual allocating constructor.
virtual bool may_equal(const BaseSemantics::SValuePtr &other, SMTSolver *solver=NULL) const ROSE_OVERRIDE
Returns true if two values could 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.
virtual SMTSolver * 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.
Interface to Satisfiability Modulo Theory (SMT) solvers.
Definition: SMTSolver.h:19
static SValuePtr promote(const BaseSemantics::SValuePtr &v)
Promote a base value to a PartialSymbolicSemantics value.