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 22 of file Reachability.h.

#include <Rose/BinaryAnalysis/Reachability.h>

Collaboration diagram for Rose::BinaryAnalysis::Reachability:

[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::FunctionPtr, 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::PartitionerConstPtr &, MemoryMapPtr map=MemoryMap::Ptr())
	Mark starting points as intrinsically reachable according to settings. More...

size_t	markEntryFunctions (const Partitioner2::PartitionerConstPtr &, ReasonFlags how=PROGRAM_ENTRY_POINT)
	Mark entry points as intrinsically reachable. More...

size_t	markExportFunctions (const Partitioner2::PartitionerConstPtr &, ReasonFlags how=EXPORTED_FUNCTION)
	Mark exported functions as intrinsically reachable. More...

size_t	markExplicitInstructionReferents (const Partitioner2::PartitionerConstPtr &, const Partitioner2::BasicBlockPtr &, ReasonFlags how=EXPLICIT_INSN_CONSTANT)
	Mark vertices whose addresses appear in instructions. More...

size_t	markExplicitMemoryReferents (const Partitioner2::PartitionerConstPtr &, const MemoryMapPtr &, 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::PartitionerConstPtr &, const Partitioner2::FunctionPtr &, ReasonFlags how=IMPLICIT_FUNC_CONSTANT)
	Mark vertices whose addressses appear in a function. More...

size_t	markSpecifiedVas (const Partitioner2::PartitionerConstPtr &, 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::PartitionerConstPtr &partitioner)
	Iteratively propagate and mark. More...

std::set< size_t >	findExplicitMemoryReferents (const Partitioner2::PartitionerConstPtr &, const MemoryMapPtr &, size_t bytesPerWord=0, size_t alignment=0, ByteOrder::Endianness sex=ByteOrder::ORDER_UNSPECIFIED)
	Find all CFG vertices mentioned in memory. More...


const Settings &	settings () const
	Property: Settings that influence the analysis.

Settings &	settings ()
	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::PartitionerConstPtr &)
	Propagate intrinsic reachability through the graph. More...

size_t	propagate (const Partitioner2::PartitionerConstPtr &, 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::PartitionerConstPtr &, const Partitioner2::BasicBlockPtr &)
	Find all CFG vertices mentioned explicitly in a basic block. More...

static std::set< size_t >	findImplicitFunctionReferents (const Partitioner2::PartitionerConstPtr &, const Partitioner2::FunctionPtr &)
	Find all CFG vertices referenced from a function. More...

Static Public Attributes
static Diagnostics::Facility	mlog
	Facility for emitting diagnostics. More...

Member Typedef Documentation

typedef BitFlags<Reason, uint32_t> Rose::BinaryAnalysis::Reachability::ReasonFlags

Bit flags for reachability.

Definition at line 56 of file Reachability.h.

Member Enumeration Documentation

enum Rose::BinaryAnalysis::Reachability::Reason

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 25 of file Reachability.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 128 of file Reachability.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::PartitionerConstPtr &	,
		MemoryMapPtr	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::PartitionerConstPtr &	,
		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::PartitionerConstPtr &	,
		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::PartitionerConstPtr &	,
		const Partitioner2::BasicBlockPtr &	,
		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::PartitionerConstPtr &	,
		const MemoryMapPtr &	,
		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::PartitionerConstPtr &	,
		const Partitioner2::FunctionPtr &	,
		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::PartitionerConstPtr &	,
		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 276 of file Reachability.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::PartitionerConstPtr & )

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::PartitionerConstPtr &	,
		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::PartitionerConstPtr & 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::PartitionerConstPtr &	,
		const Partitioner2::BasicBlockPtr &
	)

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::PartitionerConstPtr &	,
		const MemoryMapPtr &	,
		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::PartitionerConstPtr &	,
		const Partitioner2::FunctionPtr &
	)

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 93 of file Reachability.h.

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

Reachability.h

Description

Classes

Public Types

Public Member Functions

Static Public Member Functions

Static Public Attributes

Member Typedef Documentation

Member Enumeration Documentation

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation