ROSE  0.11.145.0
Variables.h
1 #ifndef ROSE_BinaryAnalysis_Variables_H
2 #define ROSE_BinaryAnalysis_Variables_H
3 #include <featureTests.h>
4 #ifdef ROSE_ENABLE_BINARY_ANALYSIS
5 
6 #include <Rose/BinaryAnalysis/InstructionSemantics/BaseSemantics/BasicTypes.h>
7 #include <Rose/BinaryAnalysis/InstructionSemantics/BaseSemantics/MemoryCellState.h>
8 #include <Rose/BinaryAnalysis/Partitioner2/BasicTypes.h>
9 #include <Rose/BinaryAnalysis/SymbolicExpression.h>
10 
11 #include <Sawyer/IntervalMap.h>
12 #include <Sawyer/Message.h>
13 #include <Sawyer/Optional.h>
14 #include <Sawyer/Set.h>
15 
16 #include <boost/serialization/access.hpp>
17 #include <boost/serialization/split_member.hpp>
18 
19 #include <chrono>
20 #include <map>
21 #include <ostream>
22 #include <set>
23 #include <string>
24 #include <vector>
25 
26 namespace Rose {
27 namespace BinaryAnalysis {
28 
30 namespace Variables {
31 
33 // Basic types
35 
38 
40 typedef std::map<int64_t /*offset*/, AddressSet> OffsetToAddresses;
41 
43 typedef std::map<rose_addr_t /*globalVa*/, AddressSet /*insns*/> AddressToAddresses;
44 
47 
49 // Global variables
51 
54 
56 // Global utilities
58 
60 void initDiagnostics();
61 
63 std::string offsetStr(int64_t offset);
64 
66 std::string sizeStr(uint64_t size);
67 
69 // Base class for variable descriptors
71 
73 class BaseVariable {
74  rose_addr_t maxSizeBytes_ = 0; // maximum possible size of this variable in bytes
75  AddressSet insnVas_; // instructions where the variable was detected that reference the variable
77  std::string name_; // optional variable name
78 
79 #ifdef ROSE_HAVE_BOOST_SERIALIZATION_LIB
80 private:
81  friend class boost::serialization::access;
82 
83  template<class S>
84  void serialize(S &s, const unsigned /*version*/) {
85  s & BOOST_SERIALIZATION_NVP(maxSizeBytes_);
86  s & BOOST_SERIALIZATION_NVP(insnVas_);
87  s & BOOST_SERIALIZATION_NVP(ioProperties_);
88  s & BOOST_SERIALIZATION_NVP(name_);
89  }
90 #endif
91 
92 protected:
96  BaseVariable();
97 
99  BaseVariable(size_t maxSizeBytes, const AddressSet &definingInstructionVas, const std::string &name);
100 
101 public:
102  BaseVariable(const BaseVariable&);
103  ~BaseVariable();
104 
105 public:
112  rose_addr_t maxSizeBytes() const;
113  void maxSizeBytes(rose_addr_t size);
122  const AddressSet& definingInstructionVas() const;
123  AddressSet& definingInstructionVas();
124  void definingInstructionVas(const AddressSet &vas);
143  const std::string& name() const;
144  void name(const std::string &s);
146 };
147 
149 // Local variable descriptors
151 
154 public:
156  enum class Purpose {
158  FRAME_POINTER,
159  SPILL_AREA,
160  NORMAL,
161  UNKNOWN,
162  OTHER
163  };
164 
169  struct Boundary {
170  int64_t frameOffset = 0;
171  AddressSet definingInsns;
173  };
174 
176  using Boundaries = std::vector<Boundary>;
177 
178 private:
179  Partitioner2::FunctionPtr function_; // function in which local variable exists
180  int64_t frameOffset_ = 0; // offset where variable is located in the function's stack frame
181  Purpose purpose_ = Purpose::UNKNOWN;
182 
183 #ifdef ROSE_HAVE_BOOST_SERIALIZATION_LIB
184 private:
185  friend class boost::serialization::access;
186 
187  template<class S>
188  void serialize(S &s, const unsigned version) {
189  s & BOOST_SERIALIZATION_BASE_OBJECT_NVP(BaseVariable);
190  s & BOOST_SERIALIZATION_NVP(function_);
191  s & BOOST_SERIALIZATION_NVP(frameOffset_);
192  if (version >= 1)
193  s & BOOST_SERIALIZATION_NVP(purpose_);
194  }
195 #endif
196 
197 public:
201  StackVariable();
202 
205  const AddressSet &definingInstructionVas = AddressSet(), const std::string &name = "");
206 
208  ~StackVariable();
209 
215  Partitioner2::FunctionPtr function() const;
216  void function(const Partitioner2::FunctionPtr&);
226  int64_t frameOffset() const;
227  void frameOffset(int64_t offset);
235  Purpose purpose() const;
236  void purpose(Purpose p);
242  const std::string& setDefaultName();
243 
250  bool operator==(const StackVariable &other) const;
251  bool operator!=(const StackVariable &other) const;
255  OffsetInterval interval() const;
256 
260  static Boundary& insertBoundary(Boundaries& /*in,out*/, int64_t frameOffset, rose_addr_t insnVa);
261 
265  void print(std::ostream&) const;
266  std::string toString() const;
273  explicit operator bool() const {
274  return !interval().isEmpty();
275  }
276 
280  bool operator!() const {
281  return interval().isEmpty();
282  }
283 
285  friend std::ostream& operator<<(std::ostream&, const Rose::BinaryAnalysis::Variables::StackVariable&);
286 };
287 
290 
295 void print(const StackVariables&, const Partitioner2::PartitionerConstPtr&, std::ostream &out, const std::string &prefix = "");
296 
298 // Global variable descriptors
300 
303  rose_addr_t address_ = 0; // starting (lowest) virtual address
304 
305 #ifdef ROSE_HAVE_BOOST_SERIALIZATION_LIB
306 private:
307  friend class boost::serialization::access;
308 
309  template<class S>
310  void serialize(S &s, const unsigned /*version*/) {
311  s & BOOST_SERIALIZATION_BASE_OBJECT_NVP(BaseVariable);
312  s & BOOST_SERIALIZATION_NVP(address_);
313  }
314 #endif
315 
316 public:
320  GlobalVariable();
321 
327  GlobalVariable(rose_addr_t startingAddress, rose_addr_t maxSizeBytes,
328  const AddressSet &definingInstructionVas = AddressSet(), const std::string &name = "");
329 
330  ~GlobalVariable();
331 
337  rose_addr_t address() const;
338  void address(rose_addr_t va);
344  const std::string& setDefaultName();
345 
351  bool operator==(const GlobalVariable &other) const;
352  bool operator!=(const GlobalVariable &other) const;
356  AddressInterval interval() const;
357 
361  void print(std::ostream&) const;
362  std::string toString() const;
369  explicit operator bool() const {
370  return !interval().isEmpty();
371  }
372 
376  bool operator!() const {
377  return interval().isEmpty();
378  }
379 
381  friend std::ostream& operator<<(std::ostream&, const Rose::BinaryAnalysis::Variables::GlobalVariable&);
382 };
383 
390 
396 void erase(GlobalVariables&, const AddressInterval &toErase);
397 
402 void print(const GlobalVariables&,const Partitioner2::PartitionerConstPtr&, std::ostream &out, const std::string &prefix = "");
403 
412 AddressInterval isInconsistent(const GlobalVariables&, Sawyer::Message::Stream&);
413 
415 // StackFrame
417 
441 class StackFrame {
442 public:
443  enum Direction {
446  };
447 
453  std::string rule;
454 };
455 
457 // Analyzer
459 
462 public:
464  struct Settings {
466  std::chrono::seconds gvarMethod1MaxTimePerFunction;
467 
468  Settings()
469  : gvarMethod1MaxTimePerFunction(30) {}
470  };
471 
474 
475 private:
476  Settings settings_;
477 
478 protected:
479  explicit VariableFinder(const Settings&);
480 public:
481  ~VariableFinder();
482 
483 public:
485  static Ptr instance(const Settings &settings = Settings());
486 
490  const Settings& settings() const { return settings_; }
491  Settings& settings() { return settings_; }
528 
535  void evict(const Partitioner2::FunctionPtr&);
543  bool isCached(const Partitioner2::FunctionPtr&);
544 
547 
555  StackVariable::Boundaries &boundaries /*in,out*/);
556 
557 #if 0 // [Robb Matzke 2021-10-27]
558 
563  OffsetInterval referencedFrameArea(const Partitioner2::Partitioner&,
565  const SymbolicExpression::Ptr &address, size_t nBytes);
566 #endif
567 
573 
579 
615  AddressToAddresses findGlobalVariableVas(const Partitioner2::PartitionerConstPtr&);
616 
620  std::set<rose_addr_t> findConstants(const SymbolicExpression::Ptr&);
621 
623  std::set<rose_addr_t> findConstants(SgAsmInstruction*);
624 
628  std::set<SymbolicExpression::Ptr> getMemoryAddresses(const InstructionSemantics::BaseSemantics::MemoryCellStatePtr&);
629 
634 
635 #if 0 // [Robb Matzke 2021-10-27]
636 
640  symbolicAddress(const Partitioner2::Partitioner&, const StackVariable&,
642 #endif
643 
652  StackVariable::Boundaries &sortedBoundaries /*in,out*/);
653 
656 
659 
662 
663 private:
664  // Searches for global variables using a per-function data-flow analysis and distinguishing between global variable
665  // addresses based on which instructions wrote to those addresses. The data-flow is inter-procedural only for calls to
666  // certain functions (such as the x86 get_pc_thunk variety of functions).
667  //
668  // The return value is a list of global variable addresses and the instructions at which each global variable address
669  // was detected.
670  AddressToAddresses findGlobalVariableVasMethod1(const Partitioner2::PartitionerConstPtr&);
671 
672  // Searches for global variables by running each instruction individually in symbolic semantics and then searching
673  // the memory state addresses. All constants found in address expressions are gathered together.
674  //
675  // The return value is a list of global variable addresses and the instructions at which each global address was detected.
676  AddressToAddresses findGlobalVariableVasMethod2(const Partitioner2::PartitionerConstPtr&);
677 
678  // Searches for global variables by looking for constants in instruction ASTs.
679  //
680  // The retun value is the list of constants and the instructions in which each constant appeared.
681  AddressToAddresses findGlobalVariableVasMethod3(const Partitioner2::PartitionerConstPtr&);
682 
683  // Merge one set of addresses and their defining instructions into another.
684  static void merge(AddressToAddresses&, const AddressToAddresses&);
685 };
686 
687 } // namespace
688 } // namespace
689 } // namespace
690 
691 // Class versions must be at global scope
692 BOOST_CLASS_VERSION(Rose::BinaryAnalysis::Variables::StackVariable, 1);
693 
694 #endif
695 #endif
Information about a stack frame.
Definition: Variables.h:441
std::string toString() const
Printing global variable.
New frames are added at lower addresses than old frames.
Definition: Variables.h:445
static bool regionIsFullyReadWrite(const Partitioner2::PartitionerConstPtr &, const AddressInterval &)
True if memory region is fully mapped with read and write access.
friend std::ostream & operator<<(std::ostream &, const Rose::BinaryAnalysis::Variables::StackVariable &)
Print local variable descriptor.
const Settings & settings() const
Settings for this analysis.
Definition: Variables.h:490
const AddressSet & definingInstructionVas() const
Property: Addresses of instructions related to this variable.
Direction growthDirection
Direction that the stack grows when pushing a new frame.
Definition: Variables.h:448
Description of a global variable.
Definition: Variables.h:302
RegisterDescriptor framePointerRegister
Optional descriptor for register pointing to latest frame.
Definition: Variables.h:449
Sawyer::Message::Facility mlog
Diagnostic facility.
bool isEmpty() const
True if interval is empty.
Definition: Interval.h:219
int64_t frameOffset
Address of boundary with respect to frame pointer.
Definition: Variables.h:170
boost::shared_ptr< class MemoryCellState > MemoryCellStatePtr
Shared-ownership pointer to a cell-based memory state.
boost::shared_ptr< RiscOperators > RiscOperatorsPtr
Shared-ownership pointer to a RISC operators object.
Base class for machine instructions.
bool operator!() const
Predicate to test whether variable is invalid.
Definition: Variables.h:280
Collection of streams.
Definition: Message.h:1606
std::string rule
Informal rule name used to detect frame characteristics.
Definition: Variables.h:453
AddressInterval interval() const
Location of variable in memory.
Analysis to find variable locations.
Definition: Variables.h:461
Sawyer::SharedPointer< VariableFinder > VariableFinderPtr
Reference counting pointer.
std::vector< Boundary > Boundaries
List of boundaries.
Definition: Variables.h:176
Describes a local or global variable.
Definition: Variables.h:73
const std::string & name() const
Property: Optional variable name.
const std::string & setDefaultName()
Give variable a defult name.
std::set< SymbolicExpression::Ptr > getMemoryAddresses(const InstructionSemantics::BaseSemantics::MemoryCellStatePtr &)
Find addresses in memory state.
void evict(const Partitioner2::FunctionPtr &)
Removed cached information.
const InstructionSemantics::BaseSemantics::InputOutputPropertySet & ioProperties() const
Property: I/O properties.
friend std::ostream & operator<<(std::ostream &, const Rose::BinaryAnalysis::Variables::GlobalVariable &)
Print global variable descriptor.
bool operator==(const StackVariable &other) const
Compare two local variables.
void initDiagnostics()
Initialize diagnostic output.
Main namespace for the ROSE library.
std::map< rose_addr_t, AddressSet > AddressToAddresses
Mapping from addresses to address sets.
Definition: Variables.h:43
AddressInterval isInconsistent(const GlobalVariables &, Sawyer::Message::Stream &)
Check that the map is consistent.
static Ptr instance(const Settings &settings=Settings())
Allocating constructor.
rose_addr_t address() const
Property: Starting address.
StackFrame detectFrameAttributes(const Partitioner2::PartitionerConstPtr &, const Partitioner2::FunctionPtr &)
Figure out attributes describing the stack frame for the specified function.
std::set< int64_t > findFrameOffsets(const StackFrame &, const Partitioner2::PartitionerConstPtr &, SgAsmInstruction *)
Find stack variable addresses.
OffsetInterval interval() const
Location within the function stack frame.
std::string sizeStr(uint64_t size)
Format size as a string.
Purpose purpose() const
Property: Purpose.
Sawyer::Optional< int64_t > minOffset
Minimum frame offset w.r.t.
Definition: Variables.h:451
Sawyer::Optional< int64_t > maxOffset
Maximum frame offset w.r.t.
Definition: Variables.h:450
bool operator!() const
Predicate to test whether variable is invalid.
Definition: Variables.h:376
StackVariables findStackVariables(const Partitioner2::PartitionerConstPtr &, const Partitioner2::FunctionPtr &)
Find local variables in a function.
std::chrono::seconds gvarMethod1MaxTimePerFunction
Max time to spend in Method 1 global variable analysis per function.
Definition: Variables.h:466
void print(std::ostream &) const
Printing global variable.
void print(const StackVariables &, const Partitioner2::PartitionerConstPtr &, std::ostream &out, const std::string &prefix="")
Print info about multiple local variables.
std::map< int64_t, AddressSet > OffsetToAddresses
Mapping from stack offsets to address sets.
Definition: Variables.h:40
static bool regionIsFullyMapped(const Partitioner2::PartitionerConstPtr &, const AddressInterval &)
True if memory region is fully mapped.
Describes (part of) a physical CPU register.
GlobalVariables findGlobalVariables(const Partitioner2::PartitionerConstPtr &)
Find global variables.
bool isCached(const Partitioner2::FunctionPtr &)
Test whether local variable information is cached.
static Boundary & insertBoundary(Boundaries &, int64_t frameOffset, rose_addr_t insnVa)
Insert a new boundary or adjust an existing boundary.
rose_addr_t maxSizeBytes() const
Property: Maximum variable size in bytes.
std::string offsetStr(int64_t offset)
Format a stack offset as a string.
Purpose purpose
Purpose of addresses above this boundary.
Definition: Variables.h:172
Settings that control this analysis.
Definition: Variables.h:464
const std::string & setDefaultName()
Give variable a defult name.
New frames are added at higher addresses than old frames.
Definition: Variables.h:444
bool operator!=(const StackVariable &other) const
Compare two local variables.
AddressSet definingInsns
Instructions that define this boundary.
Definition: Variables.h:171
Sawyer::Container::Set< rose_addr_t > AddressSet
Set of addresses.
Definition: Variables.h:37
static bool regionContainsInstructions(const Partitioner2::PartitionerConstPtr &, const AddressInterval &)
True if memory region contains any decoded instructions.
std::set< rose_addr_t > findConstants(const SymbolicExpression::Ptr &)
Find address constants in an expression.
Base class for reference counted objects.
Definition: SharedObject.h:64
std::string toString() const
Printing local variable.
Range of values delimited by endpoints.
Definition: Interval.h:33
AddressToAddresses findGlobalVariableVas(const Partitioner2::PartitionerConstPtr &)
Find global variable addresses.
int64_t frameOffset() const
Property: Frame offset.
void print(std::ostream &) const
Printing local variable.
Converts text to messages.
Definition: Message.h:1396
Partitioner2::FunctionPtr functionForInstruction(const Partitioner2::PartitionerConstPtr &, SgAsmInstruction *)
Function that owns an instruction.
std::set< rose_addr_t > findAddressConstants(const InstructionSemantics::BaseSemantics::MemoryCellStatePtr &)
Find constants in memory.
Partitions instructions into basic blocks and functions.
Definition: Partitioner.h:293
Sawyer::Container::IntervalMap< AddressInterval, GlobalVariable > GlobalVariables
Maps virtual addresses to global variables.
Definition: Variables.h:389
void erase(GlobalVariables &, const AddressInterval &toErase)
Erase some global variables.
void initializeFrameBoundaries(const StackFrame &, const Partitioner2::PartitionerConstPtr &, const Partitioner2::FunctionPtr &, StackVariable::Boundaries &boundaries)
Initilialize offsets for function prologue.
void removeOutliers(const StackFrame &, const Partitioner2::PartitionerConstPtr &, const Partitioner2::FunctionPtr &, StackVariable::Boundaries &sortedBoundaries)
Remove boundaries that are outside a stack frame.
Sawyer::Container::Interval< int64_t > OffsetInterval
Interval of signed offsets.
Definition: Variables.h:46
Sawyer::Optional< uint64_t > size
Size of the frame in bytes if known.
Definition: Variables.h:452
Description of a local stack variable within a function.
Definition: Variables.h:153
Settings & settings()
Settings for this analysis.
Definition: Variables.h:491
bool operator!=(const GlobalVariable &other) const
Compare two global variable descriptors.
bool operator==(const GlobalVariable &other) const
Compare two global variable descriptors.