ROSE  0.9.10.220
BinaryReachability.h
1 #ifndef ROSE_BinaryAnalysis_Reachability_H
2 #define ROSE_BinaryAnalysis_Reachability_H
3 
4 #include <BitFlags.h>
5 #include <boost/serialization/access.hpp>
6 #include <boost/serialization/split_member.hpp>
7 #include <Partitioner2/ControlFlowGraph.h>
8 #include <Sawyer/Map.h>
9 #include <Sawyer/Tracker.h>
10 #include <set>
11 #include <vector>
12 
13 namespace Rose {
14 namespace BinaryAnalysis {
15 
20 class Reachability {
21 public:
23  enum Reason {
24  // Predefined reasons
26  PROGRAM_ENTRY_POINT = 0x00000001,
27  EXPORTED_FUNCTION = 0x00000002,
28  SIGNAL_HANDLER = 0x00000004,
29  ASSUMED = 0x00000080,
30  EXPLICIT_MEM_CONSTANT = 0x00000100,
31  EXPLICIT_INSN_CONSTANT = 0x00000200,
32  IMPLICIT_FUNC_CONSTANT = 0x00000400,
34  // User-defined reasons
35  USER_DEFINED_0 = 0x00010000,
36  USER_DEFINED_1 = 0x00020000,
37  USER_DEFINED_2 = 0x00040000,
38  USER_DEFINED_3 = 0x00080000,
39  USER_DEFINED_4 = 0x00100000,
40  USER_DEFINED_5 = 0x00200000,
41  USER_DEFINED_6 = 0x00400000,
42  USER_DEFINED_7 = 0x00800000,
43  USER_DEFINED_8 = 0x01000000,
44  USER_DEFINED_9 = 0x02000000,
45  USER_DEFINED_10 = 0x04000000,
46  USER_DEFINED_11 = 0x08000000,
47  USER_DEFINED_12 = 0x10000000,
48  USER_DEFINED_13 = 0x20000000,
49  USER_DEFINED_14 = 0x40000000,
50  USER_DEFINED_15 = 0x80000000
51  };
52 
55 
60  struct Settings {
61  ReasonFlags markingEntryFunctions;
62  ReasonFlags markingExportFunctions;
67  rose_addr_t addressAlignment;
68  size_t addressNBytes;
69  ByteOrder::Endianness byteOrder;
75  Settings()
76  : markingEntryFunctions(PROGRAM_ENTRY_POINT),
77  markingExportFunctions(EXPORTED_FUNCTION),
78  markingExplicitMemoryReferents(EXPLICIT_MEM_CONSTANT),
79  markingExplicitInstructionReferents(EXPLICIT_INSN_CONSTANT),
80  markingImplicitFunctionReferents(NOT_REACHABLE), // disabled by default because it's slow
81  addressAlignment(0), addressNBytes(0), byteOrder(ByteOrder::ORDER_UNSPECIFIED),
82  precomputeImplicitFunctionReferents(true)
83  {}
84  };
85 
86  /* Mapping from functions to sets of CFG vertex IDs. */
87  typedef Sawyer::Container::Map<Partitioner2::Function::Ptr, std::set<size_t/*vertexId*/> > FunctionToVertexMap;
88 
89 public:
92 
93 private:
94  Settings settings_; // settings that affect behavior
95  std::vector<ReasonFlags> intrinsicReachability_; // intrinsic reachability of each vertex in the CFG
96  std::vector<ReasonFlags> reachability_; // computed reachability of each vertex in the CFG
97  FunctionToVertexMap dfReferents_; // results from findImplicitFunctionReferents
98  Sawyer::Container::Tracker<size_t> scannedVertexIds_; // vertex IDs that have been used for marking intrinsic reachability
99 
100 #ifdef ROSE_HAVE_BOOST_SERIALIZATION_LIB
101 private:
102  friend class boost::serialization::access;
103 
104  template<class S>
105  void serialize(S &s, const unsigned version) {
106  // Version zero files are no longer supported. I don't think there are two many of these around anyway and supporting
107  // backward compatibility for version 0 is not trivial.
108  if (version < 1) {
109  mlog[Sawyer::Message::FATAL] <<"cannot de-serialized version " <<version <<" object\n";
110  ASSERT_not_reachable("aborting due to unsupported old serialization file format");
111  }
112  s & BOOST_SERIALIZATION_NVP(intrinsicReachability_);
113  s & BOOST_SERIALIZATION_NVP(reachability_);
114  s & BOOST_SERIALIZATION_NVP(intrinsicReachability_);
115  s & BOOST_SERIALIZATION_NVP(reachability_);
116  // s & BOOST_SERIALIZATION_NVP(settings_); -- not serialized
117  // s & BOOST_SERIALIZATION_NVP(dfReferents_); -- not serialized
118  // s & BOOST_SERIALIZATION_NVP(scannedVertexIds_); -- not serialized
119  }
120 #endif
121 
122 public:
127 
131  static void initDiagnostics();
132 
136  const Settings& settings() const { return settings_; }
137  Settings& settings() { return settings_; }
138  void settings(const Settings &s) { settings_ = s; }
147 
152  static std::string reasonArgument(Reason);
153 
160  static Sawyer::CommandLine::ValueParser::Ptr reasonParser(ReasonFlags &storage);
161 
165  static std::string reasonArgumentDocumentation();
166 
174  static void insertReasonSwitch(Sawyer::CommandLine::SwitchGroup&, const std::string &switchName, ReasonFlags &storage,
175  Reason dfltArg, const std::string &doc);
176 
182  static std::string reasonDocumentation(Reason dflt);
183 
187  void clear();
188 
192  void clearReachability();
193 
209 
216  size_t markEntryFunctions(const Partitioner2::Partitioner&, ReasonFlags how = PROGRAM_ENTRY_POINT);
217 
223  size_t markExportFunctions(const Partitioner2::Partitioner&, ReasonFlags how = EXPORTED_FUNCTION);
224 
230  ReasonFlags how = EXPLICIT_INSN_CONSTANT);
231 
242  size_t markExplicitMemoryReferents(const Partitioner2::Partitioner&, const MemoryMap::Ptr&, size_t bytesPerWord = 0,
243  size_t alignment = 0, ByteOrder::Endianness sex = ByteOrder::ORDER_UNSPECIFIED,
244  ReasonFlags how = EXPLICIT_MEM_CONSTANT);
245 
251  size_t markImplicitFunctionReferents(const Partitioner2::Partitioner&, const Partitioner2::Function::Ptr&,
252  ReasonFlags how = IMPLICIT_FUNC_CONSTANT);
253 
259  size_t markSpecifiedVas(const Partitioner2::Partitioner&, const std::vector<AddressInterval>&, ReasonFlags);
260 
268  size_t intrinsicallyReachable(size_t vertexId, ReasonFlags how);
269 
273  template<class ForwardIterator>
274  size_t intrinsicallyReachable(ForwardIterator begin, ForwardIterator end, ReasonFlags how) {
275  size_t nChanged = 0;
276  while (begin != end)
277  nChanged += intrinsicallyReachable(*begin++, how);
278  return nChanged;
279  }
280 
291  static bool hasReasons(ReasonFlags reasons,
292  ReasonFlags any = ReasonFlags(), ReasonFlags all = ReasonFlags(), ReasonFlags none = ReasonFlags());
293 
297  bool isIntrinsicallyReachable(size_t vertexId,
298  ReasonFlags any = ReasonFlags(), ReasonFlags all = ReasonFlags(),
299  ReasonFlags none = ReasonFlags()) const;
300 
304  bool isReachable(size_t vertexId,
305  ReasonFlags any = ReasonFlags(), ReasonFlags all = ReasonFlags(),
306  ReasonFlags none = ReasonFlags()) const;
307 
316  ReasonFlags intrinsicReachability(size_t vertexId) const;
317  const std::vector<ReasonFlags>& intrinsicReachability() const;
328  ReasonFlags reachability(size_t vertexId) const;
329  const std::vector<ReasonFlags>& reachability() const;
337  std::vector<size_t> reachableVertices(ReasonFlags any = ReasonFlags(), ReasonFlags all = ReasonFlags(),
338  ReasonFlags none = ReasonFlags()) const;
339 
348  size_t propagate(const Partitioner2::Partitioner&);
349  size_t propagate(const Partitioner2::Partitioner&, std::vector<size_t> &changedVertexIds /*in,out*/);
357  void iterate(const Partitioner2::Partitioner &partitioner);
358 
363  static std::set<size_t>
365 
372  std::set<size_t>
373  findExplicitMemoryReferents(const Partitioner2::Partitioner&, const MemoryMap::Ptr&, size_t bytesPerWord = 0,
374  size_t alignment = 0, ByteOrder::Endianness sex = ByteOrder::ORDER_UNSPECIFIED);
375 
380  static std::set<size_t>
381  findImplicitFunctionReferents(const Partitioner2::Partitioner&, const Partitioner2::Function::Ptr&);
382 
383 private:
384  // Implementation of the "propagate" functions
385  size_t propagateImpl(const Partitioner2::Partitioner&, std::vector<size_t>*);
386 
387  // Resize vectors based on partitioner CFG size
388  void resize(const Partitioner2::Partitioner&);
389 
390  // Run findImplicitFunctionReferents on all (or specified) functions in parallel and cache the results
391  void cacheAllImplicitFunctionReferents(const Partitioner2::Partitioner&);
392  void cacheImplicitFunctionReferents(const Partitioner2::Partitioner&, const std::set<Partitioner2::Function::Ptr>&);
393 
394  // Do the marking part of the "iterate" function.
395  size_t iterationMarking(const Partitioner2::Partitioner&, const std::vector<size_t> &vertexIds);
396 };
397 
398 } // namespace
399 } // namespace
400 
401 // Class versions must be at global scope
402 BOOST_CLASS_VERSION(Rose::BinaryAnalysis::Reachability, 1);
403 
404 #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:1579
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:329
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:293
FunctionPtr Ptr
Shared-ownership pointer for function.
Definition: Function.h:48
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.