ROSE  0.11.31.0
BinaryReachability.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 <BitFlags.h>
7 #include <boost/serialization/access.hpp>
8 #include <boost/serialization/split_member.hpp>
9 #include <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.
ByteOrder::Endianness byteOrder
Byte order to use when reading constants from virtual memory.
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.
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.
const std::vector< ReasonFlags > & reachability() const
Query computed reachability.
rose_addr_t addressAlignment
Alignment when reading constants from virtual memory.
ReasonFlags markingExplicitInstructionReferents
If not empty, run markExplicitInstructionReferents during iteration.
Settings & settings()
Property: Settings that influence the analysis.
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.
Settings controlling the analysis.
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.
Sawyer::Optional< size_t > nThreads
Parallelism; 0 means system; unset means use global value.
bool precomputeImplicitFunctionReferents
Implicit function referents are precomputed in parallel.
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.
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.
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.
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.
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.
ReasonFlags markingEntryFunctions
If not empty, run markEntryFunctions at startup.
ReasonFlags markingExplicitMemoryReferents
If not empty, run markExplicitMemoryReferents at startup.
size_t propagate(const Partitioner2::Partitioner &)
Propagate intrinsic reachability through the graph.
static Diagnostics::Facility mlog
Facility for emitting diagnostics.
Address appears during data-flow in some reachable function.
ReasonFlags markingExportFunctions
If not empty, run markExportFunctions at startup.
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:323
FunctionPtr Ptr
Shared-ownership pointer for function.
Definition: Function.h:52
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.