ROSE  0.11.51.0
Reachability.h
1 #ifndef ROSE_BinaryAnalysis_Reachability_H
2 #define ROSE_BinaryAnalysis_Reachability_H
3 #include <featureTests.h>
4 #ifdef ROSE_ENABLE_BINARY_ANALYSIS
5 
6 #include <Rose/BitFlags.h>
7 #include <boost/serialization/access.hpp>
8 #include <boost/serialization/split_member.hpp>
9 #include <Rose/BinaryAnalysis/Partitioner2/ControlFlowGraph.h>
10 #include <Sawyer/Map.h>
11 #include <Sawyer/Tracker.h>
12 #include <set>
13 #include <vector>
14 
15 namespace Rose {
16 namespace BinaryAnalysis {
17 
22 class Reachability {
23 public:
25  enum Reason {
26  // Predefined reasons
28  PROGRAM_ENTRY_POINT = 0x00000001,
29  EXPORTED_FUNCTION = 0x00000002,
30  SIGNAL_HANDLER = 0x00000004,
31  ASSUMED = 0x00000080,
32  EXPLICIT_MEM_CONSTANT = 0x00000100,
33  EXPLICIT_INSN_CONSTANT = 0x00000200,
34  IMPLICIT_FUNC_CONSTANT = 0x00000400,
36  // User-defined reasons
37  USER_DEFINED_0 = 0x00010000,
38  USER_DEFINED_1 = 0x00020000,
39  USER_DEFINED_2 = 0x00040000,
40  USER_DEFINED_3 = 0x00080000,
41  USER_DEFINED_4 = 0x00100000,
42  USER_DEFINED_5 = 0x00200000,
43  USER_DEFINED_6 = 0x00400000,
44  USER_DEFINED_7 = 0x00800000,
45  USER_DEFINED_8 = 0x01000000,
46  USER_DEFINED_9 = 0x02000000,
47  USER_DEFINED_10 = 0x04000000,
48  USER_DEFINED_11 = 0x08000000,
49  USER_DEFINED_12 = 0x10000000,
50  USER_DEFINED_13 = 0x20000000,
51  USER_DEFINED_14 = 0x40000000,
52  USER_DEFINED_15 = 0x80000000
53  };
54 
57 
62  struct Settings {
63  ReasonFlags markingEntryFunctions;
64  ReasonFlags markingExportFunctions;
69  rose_addr_t addressAlignment;
70  size_t addressNBytes;
71  ByteOrder::Endianness byteOrder;
77  Settings()
78  : markingEntryFunctions(PROGRAM_ENTRY_POINT),
79  markingExportFunctions(EXPORTED_FUNCTION),
80  markingExplicitMemoryReferents(EXPLICIT_MEM_CONSTANT),
81  markingExplicitInstructionReferents(EXPLICIT_INSN_CONSTANT),
82  markingImplicitFunctionReferents(NOT_REACHABLE), // disabled by default because it's slow
83  addressAlignment(0), addressNBytes(0), byteOrder(ByteOrder::ORDER_UNSPECIFIED),
84  precomputeImplicitFunctionReferents(true)
85  {}
86  };
87 
88  /* Mapping from functions to sets of CFG vertex IDs. */
89  typedef Sawyer::Container::Map<Partitioner2::Function::Ptr, std::set<size_t/*vertexId*/> > FunctionToVertexMap;
90 
91 public:
94 
95 private:
96  Settings settings_; // settings that affect behavior
97  std::vector<ReasonFlags> intrinsicReachability_; // intrinsic reachability of each vertex in the CFG
98  std::vector<ReasonFlags> reachability_; // computed reachability of each vertex in the CFG
99  FunctionToVertexMap dfReferents_; // results from findImplicitFunctionReferents
100  Sawyer::Container::Tracker<size_t> scannedVertexIds_; // vertex IDs that have been used for marking intrinsic reachability
101 
102 #ifdef ROSE_HAVE_BOOST_SERIALIZATION_LIB
103 private:
104  friend class boost::serialization::access;
105 
106  template<class S>
107  void serialize(S &s, const unsigned version) {
108  // Version zero files are no longer supported. I don't think there are two many of these around anyway and supporting
109  // backward compatibility for version 0 is not trivial.
110  if (version < 1) {
111  mlog[Sawyer::Message::FATAL] <<"cannot de-serialized version " <<version <<" object\n";
112  ASSERT_not_reachable("aborting due to unsupported old serialization file format");
113  }
114  s & BOOST_SERIALIZATION_NVP(intrinsicReachability_);
115  s & BOOST_SERIALIZATION_NVP(reachability_);
116  s & BOOST_SERIALIZATION_NVP(intrinsicReachability_);
117  s & BOOST_SERIALIZATION_NVP(reachability_);
118  // s & BOOST_SERIALIZATION_NVP(settings_); -- not serialized
119  // s & BOOST_SERIALIZATION_NVP(dfReferents_); -- not serialized
120  // s & BOOST_SERIALIZATION_NVP(scannedVertexIds_); -- not serialized
121  }
122 #endif
123 
124 public:
129 
133  static void initDiagnostics();
134 
138  const Settings& settings() const { return settings_; }
139  Settings& settings() { return settings_; }
140  void settings(const Settings &s) { settings_ = s; }
149 
154  static std::string reasonArgument(Reason);
155 
162  static Sawyer::CommandLine::ValueParser::Ptr reasonParser(ReasonFlags &storage);
163 
167  static std::string reasonArgumentDocumentation();
168 
176  static void insertReasonSwitch(Sawyer::CommandLine::SwitchGroup&, const std::string &switchName, ReasonFlags &storage,
177  Reason dfltArg, const std::string &doc);
178 
184  static std::string reasonDocumentation(Reason dflt);
185 
189  void clear();
190 
194  void clearReachability();
195 
211 
218  size_t markEntryFunctions(const Partitioner2::Partitioner&, ReasonFlags how = PROGRAM_ENTRY_POINT);
219 
225  size_t markExportFunctions(const Partitioner2::Partitioner&, ReasonFlags how = EXPORTED_FUNCTION);
226 
232  ReasonFlags how = EXPLICIT_INSN_CONSTANT);
233 
244  size_t markExplicitMemoryReferents(const Partitioner2::Partitioner&, const MemoryMap::Ptr&, size_t bytesPerWord = 0,
245  size_t alignment = 0, ByteOrder::Endianness sex = ByteOrder::ORDER_UNSPECIFIED,
246  ReasonFlags how = EXPLICIT_MEM_CONSTANT);
247 
253  size_t markImplicitFunctionReferents(const Partitioner2::Partitioner&, const Partitioner2::Function::Ptr&,
254  ReasonFlags how = IMPLICIT_FUNC_CONSTANT);
255 
261  size_t markSpecifiedVas(const Partitioner2::Partitioner&, const std::vector<AddressInterval>&, ReasonFlags);
262 
270  size_t intrinsicallyReachable(size_t vertexId, ReasonFlags how);
271 
275  template<class ForwardIterator>
276  size_t intrinsicallyReachable(ForwardIterator begin, ForwardIterator end, ReasonFlags how) {
277  size_t nChanged = 0;
278  while (begin != end)
279  nChanged += intrinsicallyReachable(*begin++, how);
280  return nChanged;
281  }
282 
293  static bool hasReasons(ReasonFlags reasons,
294  ReasonFlags any = ReasonFlags(), ReasonFlags all = ReasonFlags(), ReasonFlags none = ReasonFlags());
295 
299  bool isIntrinsicallyReachable(size_t vertexId,
300  ReasonFlags any = ReasonFlags(), ReasonFlags all = ReasonFlags(),
301  ReasonFlags none = ReasonFlags()) const;
302 
306  bool isReachable(size_t vertexId,
307  ReasonFlags any = ReasonFlags(), ReasonFlags all = ReasonFlags(),
308  ReasonFlags none = ReasonFlags()) const;
309 
318  ReasonFlags intrinsicReachability(size_t vertexId) const;
319  const std::vector<ReasonFlags>& intrinsicReachability() const;
330  ReasonFlags reachability(size_t vertexId) const;
331  const std::vector<ReasonFlags>& reachability() const;
339  std::vector<size_t> reachableVertices(ReasonFlags any = ReasonFlags(), ReasonFlags all = ReasonFlags(),
340  ReasonFlags none = ReasonFlags()) const;
341 
350  size_t propagate(const Partitioner2::Partitioner&);
351  size_t propagate(const Partitioner2::Partitioner&, std::vector<size_t> &changedVertexIds /*in,out*/);
359  void iterate(const Partitioner2::Partitioner &partitioner);
360 
365  static std::set<size_t>
367 
374  std::set<size_t>
375  findExplicitMemoryReferents(const Partitioner2::Partitioner&, const MemoryMap::Ptr&, size_t bytesPerWord = 0,
376  size_t alignment = 0, ByteOrder::Endianness sex = ByteOrder::ORDER_UNSPECIFIED);
377 
382  static std::set<size_t>
383  findImplicitFunctionReferents(const Partitioner2::Partitioner&, const Partitioner2::Function::Ptr&);
384 
385 private:
386  // Implementation of the "propagate" functions
387  size_t propagateImpl(const Partitioner2::Partitioner&, std::vector<size_t>*);
388 
389  // Resize vectors based on partitioner CFG size
390  void resize(const Partitioner2::Partitioner&);
391 
392  // Run findImplicitFunctionReferents on all (or specified) functions in parallel and cache the results
393  void cacheAllImplicitFunctionReferents(const Partitioner2::Partitioner&);
394  void cacheImplicitFunctionReferents(const Partitioner2::Partitioner&, const std::set<Partitioner2::Function::Ptr>&);
395 
396  // Do the marking part of the "iterate" function.
397  size_t iterationMarking(const Partitioner2::Partitioner&, const std::vector<size_t> &vertexIds);
398 };
399 
400 } // namespace
401 } // namespace
402 
403 // Class versions must be at global scope
404 BOOST_CLASS_VERSION(Rose::BinaryAnalysis::Reachability, 1);
405 
406 #endif
407 #endif
void settings(const Settings &s)
Property: Settings that influence the analysis.
Definition: Reachability.h:140
ByteOrder::Endianness byteOrder
Byte order to use when reading constants from virtual memory.
Definition: Reachability.h:71
std::vector< size_t > reachableVertices(ReasonFlags any=ReasonFlags(), ReasonFlags all=ReasonFlags(), ReasonFlags none=ReasonFlags()) const
Return a list of reachable vertex IDs.
const std::vector< ReasonFlags > & intrinsicReachability() const
Query intrinsic reachability.
Address appears as a constant in some reachable instruction.
Definition: Reachability.h:33
static std::string reasonArgument(Reason)
Convert a reachability reason enum constant to a parsable reason name.
size_t markEntryFunctions(const Partitioner2::Partitioner &, ReasonFlags how=PROGRAM_ENTRY_POINT)
Mark entry points as intrinsically reachable.
Reachability()
Default constructor.
Definition: Reachability.h:128
const std::vector< ReasonFlags > & reachability() const
Query computed reachability.
rose_addr_t addressAlignment
Alignment when reading constants from virtual memory.
Definition: Reachability.h:69
ReasonFlags markingExplicitInstructionReferents
If not empty, run markExplicitInstructionReferents during iteration.
Definition: Reachability.h:66
Settings & settings()
Property: Settings that influence the analysis.
Definition: Reachability.h:139
Collection of streams.
Definition: Message.h:1606
static bool hasReasons(ReasonFlags reasons, ReasonFlags any=ReasonFlags(), ReasonFlags all=ReasonFlags(), ReasonFlags none=ReasonFlags())
Predicate to match reason flags.
size_t intrinsicallyReachable(size_t vertexId, ReasonFlags how)
Change intrinsic reachability for one vertex.
static std::string reasonArgumentDocumentation()
Documentation for the possible reason arguments.
size_t intrinsicallyReachable(ForwardIterator begin, ForwardIterator end, ReasonFlags how)
Change intrinsic reachabability for multiple vertices.
Definition: Reachability.h:276
Settings controlling the analysis.
Definition: Reachability.h:62
void iterate(const Partitioner2::Partitioner &partitioner)
Iteratively propagate and mark.
A collection of related switch declarations.
void clear()
Clear previous results.
Assumed reachable for cases when the analysis wasn't run.
Definition: Reachability.h:31
Sawyer::Optional< size_t > nThreads
Parallelism; 0 means system; unset means use global value.
Definition: Reachability.h:74
bool precomputeImplicitFunctionReferents
Implicit function referents are precomputed in parallel.
Definition: Reachability.h:73
Main namespace for the ROSE library.
std::set< size_t > findExplicitMemoryReferents(const Partitioner2::Partitioner &, const MemoryMap::Ptr &, size_t bytesPerWord=0, size_t alignment=0, ByteOrder::Endianness sex=ByteOrder::ORDER_UNSPECIFIED)
Find all CFG vertices mentioned in memory.
Reason
Predefined bit flags for why something is reachable.
Definition: Reachability.h:25
Messages that indicate an abnormal situation from which the program was unable to recover...
Definition: Message.h:332
const Settings & settings() const
Property: Settings that influence the analysis.
Definition: Reachability.h:138
void clearReachability()
Clear all reachability.
static void insertReasonSwitch(Sawyer::CommandLine::SwitchGroup &, const std::string &switchName, ReasonFlags &storage, Reason dfltArg, const std::string &doc)
Insert a switch that takes a reason argument.
static std::string reasonDocumentation(Reason dflt)
Generate documentation for the command-line switches.
static Sawyer::CommandLine::ValueParser::Ptr reasonParser(ReasonFlags &storage)
Creates a command-line parser for reachability reason names.
static std::set< size_t > findImplicitFunctionReferents(const Partitioner2::Partitioner &, const Partitioner2::Function::Ptr &)
Find all CFG vertices referenced from a function.
size_t markImplicitFunctionReferents(const Partitioner2::Partitioner &, const Partitioner2::Function::Ptr &, ReasonFlags how=IMPLICIT_FUNC_CONSTANT)
Mark vertices whose addressses appear in a function.
BitFlags< Reason, uint32_t > ReasonFlags
Bit flags for reachability.
Definition: Reachability.h:56
size_t markExplicitInstructionReferents(const Partitioner2::Partitioner &, const Partitioner2::BasicBlock::Ptr &, ReasonFlags how=EXPLICIT_INSN_CONSTANT)
Mark vertices whose addresses appear in instructions.
size_t markExplicitMemoryReferents(const Partitioner2::Partitioner &, const MemoryMap::Ptr &, size_t bytesPerWord=0, size_t alignment=0, ByteOrder::Endianness sex=ByteOrder::ORDER_UNSPECIFIED, ReasonFlags how=EXPLICIT_MEM_CONSTANT)
Mark vertices whose addresses appear in memory.
size_t addressNBytes
Size of addresses when reading constants from virtual memory.
Definition: Reachability.h:70
static Sawyer::CommandLine::SwitchGroup commandLineSwitches(Settings &settings)
Describes how to parse switches related to reachability.
size_t markExportFunctions(const Partitioner2::Partitioner &, ReasonFlags how=EXPORTED_FUNCTION)
Mark exported functions as intrinsically reachable.
static std::set< size_t > findExplicitInstructionReferents(const Partitioner2::Partitioner &, const Partitioner2::BasicBlock::Ptr &)
Find all CFG vertices mentioned explicitly in a basic block.
static void initDiagnostics()
Initialize diagnostic streams.
size_t markStartingPoints(const Partitioner2::Partitioner &, MemoryMap::Ptr map=MemoryMap::Ptr())
Mark starting points as intrinsically reachable according to settings.
bool isReachable(size_t vertexId, ReasonFlags any=ReasonFlags(), ReasonFlags all=ReasonFlags(), ReasonFlags none=ReasonFlags()) const
Query whether a vertex is reachable.
Analysis that computes reachability of CFG vertices.
Definition: Reachability.h:22
ReasonFlags markingEntryFunctions
If not empty, run markEntryFunctions at startup.
Definition: Reachability.h:63
ReasonFlags markingExplicitMemoryReferents
If not empty, run markExplicitMemoryReferents at startup.
Definition: Reachability.h:65
size_t propagate(const Partitioner2::Partitioner &)
Propagate intrinsic reachability through the graph.
static Diagnostics::Facility mlog
Facility for emitting diagnostics.
Definition: Reachability.h:93
Address appears during data-flow in some reachable function.
Definition: Reachability.h:34
ReasonFlags markingExportFunctions
If not empty, run markExportFunctions at startup.
Definition: Reachability.h:64
size_t markSpecifiedVas(const Partitioner2::Partitioner &, const std::vector< AddressInterval > &, ReasonFlags)
Mark all basic blocks with in the specified ranges.
Partitions instructions into basic blocks and functions.
Definition: Partitioner.h:290
FunctionPtr Ptr
Shared-ownership pointer for function.
Definition: Function.h:51
Container associating values with keys.
Definition: Sawyer/Map.h:66
bool isIntrinsicallyReachable(size_t vertexId, ReasonFlags any=ReasonFlags(), ReasonFlags all=ReasonFlags(), ReasonFlags none=ReasonFlags()) const
Query whether a vertex is intrinsic reachable.
ReasonFlags markingImplicitFunctionReferents
If not empty, run markImplicitFunctionReferents during iteration.
Definition: Reachability.h:67