ROSE  0.9.11.56
Classes | Public Types | Public Member Functions | Static Public Member Functions | Static Public Attributes | List of all members
Rose::BinaryAnalysis::Reachability Class Reference

Description

Analysis that computes reachability of CFG vertices.

Certain CFG vertices are marked as intrinsically reachable, such as program entry points, exported functions, signal handlers, etc., and then reachability is propagated through the graph.

Definition at line 20 of file BinaryReachability.h.

#include <BinaryReachability.h>

Collaboration diagram for Rose::BinaryAnalysis::Reachability:
Collaboration graph
[legend]

Classes

struct  Settings
 Settings controlling the analysis. More...
 

Public Types

enum  Reason {
  NOT_REACHABLE = 0,
  PROGRAM_ENTRY_POINT = 0x00000001,
  EXPORTED_FUNCTION = 0x00000002,
  SIGNAL_HANDLER = 0x00000004,
  ASSUMED = 0x00000080,
  EXPLICIT_MEM_CONSTANT = 0x00000100,
  EXPLICIT_INSN_CONSTANT = 0x00000200,
  IMPLICIT_FUNC_CONSTANT = 0x00000400,
  USER_DEFINED_0 = 0x00010000,
  USER_DEFINED_1 = 0x00020000,
  USER_DEFINED_2 = 0x00040000,
  USER_DEFINED_3 = 0x00080000,
  USER_DEFINED_4 = 0x00100000,
  USER_DEFINED_5 = 0x00200000,
  USER_DEFINED_6 = 0x00400000,
  USER_DEFINED_7 = 0x00800000,
  USER_DEFINED_8 = 0x01000000,
  USER_DEFINED_9 = 0x02000000,
  USER_DEFINED_10 = 0x04000000,
  USER_DEFINED_11 = 0x08000000,
  USER_DEFINED_12 = 0x10000000,
  USER_DEFINED_13 = 0x20000000,
  USER_DEFINED_14 = 0x40000000,
  USER_DEFINED_15 = 0x80000000
}
 Predefined bit flags for why something is reachable. More...
 
typedef BitFlags< Reason, uint32_t > ReasonFlags
 Bit flags for reachability. More...
 
typedef Sawyer::Container::Map< Partitioner2::Function::Ptr, std::set< size_t > > FunctionToVertexMap
 

Public Member Functions

 Reachability ()
 Default constructor. More...
 
void clear ()
 Clear previous results. More...
 
void clearReachability ()
 Clear all reachability. More...
 
size_t markStartingPoints (const Partitioner2::Partitioner &, MemoryMap::Ptr map=MemoryMap::Ptr())
 Mark starting points as intrinsically reachable according to settings. More...
 
size_t markEntryFunctions (const Partitioner2::Partitioner &, ReasonFlags how=PROGRAM_ENTRY_POINT)
 Mark entry points as intrinsically reachable. More...
 
size_t markExportFunctions (const Partitioner2::Partitioner &, ReasonFlags how=EXPORTED_FUNCTION)
 Mark exported functions as intrinsically reachable. More...
 
size_t markExplicitInstructionReferents (const Partitioner2::Partitioner &, const Partitioner2::BasicBlock::Ptr &, ReasonFlags how=EXPLICIT_INSN_CONSTANT)
 Mark vertices whose addresses appear in instructions. More...
 
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. More...
 
size_t markImplicitFunctionReferents (const Partitioner2::Partitioner &, const Partitioner2::Function::Ptr &, ReasonFlags how=IMPLICIT_FUNC_CONSTANT)
 Mark vertices whose addressses appear in a function. More...
 
size_t markSpecifiedVas (const Partitioner2::Partitioner &, const std::vector< AddressInterval > &, ReasonFlags)
 Mark all basic blocks with in the specified ranges. More...
 
size_t intrinsicallyReachable (size_t vertexId, ReasonFlags how)
 Change intrinsic reachability for one vertex. More...
 
template<class ForwardIterator >
size_t intrinsicallyReachable (ForwardIterator begin, ForwardIterator end, ReasonFlags how)
 Change intrinsic reachabability for multiple vertices. More...
 
bool isIntrinsicallyReachable (size_t vertexId, ReasonFlags any=ReasonFlags(), ReasonFlags all=ReasonFlags(), ReasonFlags none=ReasonFlags()) const
 Query whether a vertex is intrinsic reachable. More...
 
bool isReachable (size_t vertexId, ReasonFlags any=ReasonFlags(), ReasonFlags all=ReasonFlags(), ReasonFlags none=ReasonFlags()) const
 Query whether a vertex is reachable. More...
 
std::vector< size_t > reachableVertices (ReasonFlags any=ReasonFlags(), ReasonFlags all=ReasonFlags(), ReasonFlags none=ReasonFlags()) const
 Return a list of reachable vertex IDs. More...
 
void iterate (const Partitioner2::Partitioner &partitioner)
 Iteratively propagate and mark. More...
 
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. More...
 
const Settingssettings () const
 Property: Settings that influence the analysis.
 
Settingssettings ()
 Property: Settings that influence the analysis.
 
void settings (const Settings &s)
 Property: Settings that influence the analysis.
 
ReasonFlags intrinsicReachability (size_t vertexId) const
 Query intrinsic reachability. More...
 
const std::vector< ReasonFlags > & intrinsicReachability () const
 Query intrinsic reachability. More...
 
ReasonFlags reachability (size_t vertexId) const
 Query computed reachability. More...
 
const std::vector< ReasonFlags > & reachability () const
 Query computed reachability. More...
 
size_t propagate (const Partitioner2::Partitioner &)
 Propagate intrinsic reachability through the graph. More...
 
size_t propagate (const Partitioner2::Partitioner &, std::vector< size_t > &changedVertexIds)
 Propagate intrinsic reachability through the graph. More...
 

Static Public Member Functions

static void initDiagnostics ()
 Initialize diagnostic streams. More...
 
static Sawyer::CommandLine::SwitchGroup commandLineSwitches (Settings &settings)
 Describes how to parse switches related to reachability. More...
 
static std::string reasonArgument (Reason)
 Convert a reachability reason enum constant to a parsable reason name. More...
 
static Sawyer::CommandLine::ValueParser::Ptr reasonParser (ReasonFlags &storage)
 Creates a command-line parser for reachability reason names. More...
 
static std::string reasonArgumentDocumentation ()
 Documentation for the possible reason arguments. More...
 
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. More...
 
static std::string reasonDocumentation (Reason dflt)
 Generate documentation for the command-line switches. More...
 
static bool hasReasons (ReasonFlags reasons, ReasonFlags any=ReasonFlags(), ReasonFlags all=ReasonFlags(), ReasonFlags none=ReasonFlags())
 Predicate to match reason flags. More...
 
static std::set< size_t > findExplicitInstructionReferents (const Partitioner2::Partitioner &, const Partitioner2::BasicBlock::Ptr &)
 Find all CFG vertices mentioned explicitly in a basic block. More...
 
static std::set< size_t > findImplicitFunctionReferents (const Partitioner2::Partitioner &, const Partitioner2::Function::Ptr &)
 Find all CFG vertices referenced from a function. More...
 

Static Public Attributes

static Diagnostics::Facility mlog
 Facility for emitting diagnostics. More...
 

Member Typedef Documentation

Bit flags for reachability.

Definition at line 54 of file BinaryReachability.h.

Member Enumeration Documentation

Predefined bit flags for why something is reachable.

Enumerator
NOT_REACHABLE 

Vertex is not reachable.

PROGRAM_ENTRY_POINT 

Vertex is a program entry point.

EXPORTED_FUNCTION 

Vertex is an exported function.

SIGNAL_HANDLER 

Vertex is a signal handler.

ASSUMED 

Assumed reachable for cases when the analysis wasn't run.

EXPLICIT_MEM_CONSTANT 

Address appears in memory.

EXPLICIT_INSN_CONSTANT 

Address appears as a constant in some reachable instruction.

IMPLICIT_FUNC_CONSTANT 

Address appears during data-flow in some reachable function.

USER_DEFINED_0 

User-defined reason.

USER_DEFINED_1 

User-defined reason.

USER_DEFINED_2 

User-defined reason.

USER_DEFINED_3 

User-defined reason.

USER_DEFINED_4 

User-defined reason.

USER_DEFINED_5 

User-defined reason.

USER_DEFINED_6 

User-defined reason.

USER_DEFINED_7 

User-defined reason.

USER_DEFINED_8 

User-defined reason.

USER_DEFINED_9 

User-defined reason.

USER_DEFINED_10 

User-defined reason.

USER_DEFINED_11 

User-defined reason.

USER_DEFINED_12 

User-defined reason.

USER_DEFINED_13 

User-defined reason.

USER_DEFINED_14 

User-defined reason.

USER_DEFINED_15 

User-defined reason.

Definition at line 23 of file BinaryReachability.h.

Constructor & Destructor Documentation

Rose::BinaryAnalysis::Reachability::Reachability ( )
inline

Default constructor.

Constructs a new analysis object with an empty control flow graph.

Definition at line 126 of file BinaryReachability.h.

Member Function Documentation

static void Rose::BinaryAnalysis::Reachability::initDiagnostics ( )
static

Initialize diagnostic streams.

This is called automatically by Rose::Diagnostics::initialize.

static Sawyer::CommandLine::SwitchGroup Rose::BinaryAnalysis::Reachability::commandLineSwitches ( Settings settings)
static

Describes how to parse switches related to reachability.

The returned switch group is intended to be inserted into a command-line parser. The input values of the settings are documented as the defaults, and after applying the parse resuts will contain the arguments of the corresponding switches.

static std::string Rose::BinaryAnalysis::Reachability::reasonArgument ( Reason  )
static

Convert a reachability reason enum constant to a parsable reason name.

This is used for building command-line parsers. The returned string is the same as what would be recognized by the command-line parser for the specified enum constant.

static Sawyer::CommandLine::ValueParser::Ptr Rose::BinaryAnalysis::Reachability::reasonParser ( ReasonFlags storage)
static

Creates a command-line parser for reachability reason names.

The parser accepts a list of reason names (those strings returned by reasonArgument) separated by commas. It parses each string of the list, converts it to a Reason enum constant, and sets that flag in the provided storage variable (but not until the parsed command-line is applied). If the string is that corresponding to NOT_REACHABLE, then the storage is cleared.

static std::string Rose::BinaryAnalysis::Reachability::reasonArgumentDocumentation ( )
static

Documentation for the possible reason arguments.

This returns a documentation string describing all possible strings accepted by the reasonParser.

static void Rose::BinaryAnalysis::Reachability::insertReasonSwitch ( Sawyer::CommandLine::SwitchGroup ,
const std::string &  switchName,
ReasonFlags storage,
Reason  dfltArg,
const std::string &  doc 
)
static

Insert a switch that takes a reason argument.

Inserts the specified switch into the switch group, and also inserts a "no-*" version of the switch that behaves as if the primary switch were given the reason string corresponding to NOT_REACHABLE. The storage should already be initialized with a default set of flags. The dfltArg is the argument used for the switch if none is given on the command-line. In other words, the initial value of storage are the reasons that will result if the user doesn't specify the switch, and the dfltArg value is used if the user specifies the switch but no argument.

static std::string Rose::BinaryAnalysis::Reachability::reasonDocumentation ( Reason  dflt)
static

Generate documentation for the command-line switches.

The return value is a string suitable for incorporation into the documentation strings for the command-line parser. If the dflt is something other than NOT_REACHABLE, then it's used to indicate a default argument for the command-line switch.

void Rose::BinaryAnalysis::Reachability::clear ( )

Clear previous results.

This does not clear the settings, only the results.

void Rose::BinaryAnalysis::Reachability::clearReachability ( )

Clear all reachability.

This clears all reachability (marking all vertices as not reachable) without throwing away any other data.

size_t Rose::BinaryAnalysis::Reachability::markStartingPoints ( const Partitioner2::Partitioner ,
MemoryMap::Ptr  map = MemoryMap::Ptr() 
)

Mark starting points as intrinsically reachable according to settings.

Marks the initial, intrinsically reachable starting points in the graph according the the analysis settings. These are starting points whose reachability doesn't depend directly or indirectly on any other vertices. For example, the entry points of exported functions are intrinsically reachable regardless of what other vertices are reachable because these functions can be presumably called from other specimens.

If the analysis settings specify that memory should be scanned to find addresses of basic blocks to mark as being intrinsically reachable, then the supplied memory map is used for this purpose. If the map is a null pointer, then the map from the partitioner is used instead.

Returns number of affected vertices.

See also, markEntryFunctions, markExportFunctions, markMemoryConstants.

size_t Rose::BinaryAnalysis::Reachability::markEntryFunctions ( const Partitioner2::Partitioner ,
ReasonFlags  how = PROGRAM_ENTRY_POINT 
)

Mark entry points as intrinsically reachable.

Mark all specimen entry points as intrinsically reachable. For example, ELF files will likely have their "_start" functions marked this way (although the marking is based on the ELF header, not the name of the function).

Returns number of affected vertices.

size_t Rose::BinaryAnalysis::Reachability::markExportFunctions ( const Partitioner2::Partitioner ,
ReasonFlags  how = EXPORTED_FUNCTION 
)

Mark exported functions as intrinsically reachable.

Marks all entry vertices of exported functions as intrinsically reachable.

Returns number of affected vertices.

size_t Rose::BinaryAnalysis::Reachability::markExplicitInstructionReferents ( const Partitioner2::Partitioner ,
const Partitioner2::BasicBlock::Ptr ,
ReasonFlags  how = EXPLICIT_INSN_CONSTANT 
)

Mark vertices whose addresses appear in instructions.

Traverses the specified basic block to find all explicit constants. For each constant which is the address of a basic block, mark that block as intrinsically reachable.

size_t Rose::BinaryAnalysis::Reachability::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.

Scans all bytes of the supplied memory map to find integer constants of the specified size, alignment, and byte order. If the integer is the starting address of a basic block, then that CFG vertex is marked as reachable with the specified how flags.

If bytesPerWord, alignment, or sex are default values, then the analysis settings are used, or else if those are defaults, the values are obtained from the specimen architecture definition.

Returns number of affected vertices.

size_t Rose::BinaryAnalysis::Reachability::markImplicitFunctionReferents ( const Partitioner2::Partitioner ,
const Partitioner2::Function::Ptr ,
ReasonFlags  how = IMPLICIT_FUNC_CONSTANT 
)

Mark vertices whose addressses appear in a function.

This looks for implicit values in the function by performing a symbolic data-flow analysis and then examining the state after each basic block in order to find concrete values. Any concrete value that's the start of some basic block causes that basic block to become intrinsically reachable.

size_t Rose::BinaryAnalysis::Reachability::markSpecifiedVas ( const Partitioner2::Partitioner ,
const std::vector< AddressInterval > &  ,
ReasonFlags   
)

Mark all basic blocks with in the specified ranges.

Any basic block that has an instruction beginning in any of the address intervals is marked with the given reason.

Returns number of affected vertices.

size_t Rose::BinaryAnalysis::Reachability::intrinsicallyReachable ( size_t  vertexId,
ReasonFlags  how 
)

Change intrinsic reachability for one vertex.

The intrinsic reachability of the specified vertex is changed to how, which is a bit vector of Reason bits. Changing the intrinsic reachability of a vertex to NOT_REACHABLE does not necessarily mark the vertex as unreachable since it might be reachable from other reachable vertices.

Returns number of affected vertices (0 or 1).

Referenced by intrinsicallyReachable().

template<class ForwardIterator >
size_t Rose::BinaryAnalysis::Reachability::intrinsicallyReachable ( ForwardIterator  begin,
ForwardIterator  end,
ReasonFlags  how 
)
inline

Change intrinsic reachabability for multiple vertices.

Returns number of affected vertices.

Definition at line 274 of file BinaryReachability.h.

References intrinsicallyReachable().

static bool Rose::BinaryAnalysis::Reachability::hasReasons ( ReasonFlags  reasons,
ReasonFlags  any = ReasonFlags(),
ReasonFlags  all = ReasonFlags(),
ReasonFlags  none = ReasonFlags() 
)
static

Predicate to match reason flags.

Returns true if the reasons matches the other arguments. Returns true if all of the following are true:

  • any is non-empty and reasons contains at least one of those bits, or any is empty and reasons contains any bit.
  • reasons contains all the bits that are set in all.
  • reasons contains none of the bits that are set in none.
bool Rose::BinaryAnalysis::Reachability::isIntrinsicallyReachable ( size_t  vertexId,
ReasonFlags  any = ReasonFlags(),
ReasonFlags  all = ReasonFlags(),
ReasonFlags  none = ReasonFlags() 
) const

Query whether a vertex is intrinsic reachable.

Returns true if the specified vertex's intrinsic reachability matches according to hasReasons.

bool Rose::BinaryAnalysis::Reachability::isReachable ( size_t  vertexId,
ReasonFlags  any = ReasonFlags(),
ReasonFlags  all = ReasonFlags(),
ReasonFlags  none = ReasonFlags() 
) const

Query whether a vertex is reachable.

Returns true if the specified vertex's computed reachability matches according to hasReasons.

ReasonFlags Rose::BinaryAnalysis::Reachability::intrinsicReachability ( size_t  vertexId) const

Query intrinsic reachability.

When a vertex ID is specified, then return the reachability reasons for that one vertex, or an empty set of reasons if the ID is out of range.

When no arguments are specified, return all intrinsic reachability information.

const std::vector<ReasonFlags>& Rose::BinaryAnalysis::Reachability::intrinsicReachability ( ) const

Query intrinsic reachability.

When a vertex ID is specified, then return the reachability reasons for that one vertex, or an empty set of reasons if the ID is out of range.

When no arguments are specified, return all intrinsic reachability information.

ReasonFlags Rose::BinaryAnalysis::Reachability::reachability ( size_t  vertexId) const

Query computed reachability.

When a vertex ID is specified, then return the reachability reasons for that one vertex, or an empty set of reasons if the ID is out of range.

When no arguments are specified, return all computed reachability information.

const std::vector<ReasonFlags>& Rose::BinaryAnalysis::Reachability::reachability ( ) const

Query computed reachability.

When a vertex ID is specified, then return the reachability reasons for that one vertex, or an empty set of reasons if the ID is out of range.

When no arguments are specified, return all computed reachability information.

std::vector<size_t> Rose::BinaryAnalysis::Reachability::reachableVertices ( ReasonFlags  any = ReasonFlags(),
ReasonFlags  all = ReasonFlags(),
ReasonFlags  none = ReasonFlags() 
) const

Return a list of reachable vertex IDs.

Returns the sorted list of vertex IDs that have at least one of the any flags (or at least one flag if any is empty), all of the all flags, and none of the none flags. The return value is sorted by increasing vertex ID.

size_t Rose::BinaryAnalysis::Reachability::propagate ( const Partitioner2::Partitioner )

Propagate intrinsic reachability through the graph.

This runs a data-flow analysis to propagate the intrinsic reachability bits through the graph.

Returns the number of affected vertices. If a vector of vertex ID is supplied as an argument, then any vertex whose reachability has changed will be appended to that vector.

size_t Rose::BinaryAnalysis::Reachability::propagate ( const Partitioner2::Partitioner ,
std::vector< size_t > &  changedVertexIds 
)

Propagate intrinsic reachability through the graph.

This runs a data-flow analysis to propagate the intrinsic reachability bits through the graph.

Returns the number of affected vertices. If a vector of vertex ID is supplied as an argument, then any vertex whose reachability has changed will be appended to that vector.

void Rose::BinaryAnalysis::Reachability::iterate ( const Partitioner2::Partitioner partitioner)

Iteratively propagate and mark.

This function calls runs a propagate step and a marking step in a loop until a steady state is reached. The marking step looks for new basic blocks that can be marked as intrinsically reachable based on the newly reachable blocks from the previous propagate step.

static std::set<size_t> Rose::BinaryAnalysis::Reachability::findExplicitInstructionReferents ( const Partitioner2::Partitioner ,
const Partitioner2::BasicBlock::Ptr  
)
static

Find all CFG vertices mentioned explicitly in a basic block.

Scans the instructions of the specified basic block to look for explicit constants (i.e., "immediates") that are addresses of other basic blocks, and return the CFG vertex ID numbers for those other blocks.

std::set<size_t> Rose::BinaryAnalysis::Reachability::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.

Scans the specified memory and reads values that satisfy the size, alignment, and byte order and returns the set of CFG vertices (by ID) for which starting addresses were found. If bytesPerWord, alignment, or sex are default values, then the analysis settings are used, or else if those are defaults, the values are obtained from the specimen architecture definition.

static std::set<size_t> Rose::BinaryAnalysis::Reachability::findImplicitFunctionReferents ( const Partitioner2::Partitioner ,
const Partitioner2::Function::Ptr  
)
static

Find all CFG vertices referenced from a function.

Performs a symbolic data-flow analysis on the specified function in order to find all CFG vertices that are mentioned in the semantic state.

Member Data Documentation

Diagnostics::Facility Rose::BinaryAnalysis::Reachability::mlog
static

Facility for emitting diagnostics.

Definition at line 91 of file BinaryReachability.h.


The documentation for this class was generated from the following file: