Description

Binary control flow analysis.

This class serves mostly to organize the functions that operate on control flow graphs, but also provides a container for various settings that influence the control flow analyses, such as the vertex and edge filters. The features described here are one form of control flow graph; see also the control flow graph used by functiondetection", which is easier to work with and has more features. The AST contains an implied CFG by virtue of storing control flow successor addresses in each basic block (SgAsmBlock). The successor information is initialized by the Partitioner class when the AST is built (see Partitioner::build_ast()) and is available with SgAsmBlock::get_successors(). The SgAsmBlock::get_successors_complete() returns a Boolean indicating whether the set of successors is completely known. Successors would be incomplete, for instance, for a block that ends with a computed branch whose targets could not be statically determined. The AST-stored implied graph can be turned into an explicit Boost graph with various "build" methods defined in this class. Explicit CFGs use the Boost Graph Library API and come in two flavors: graphs whose vertices are basic blocks, and graphs whose vertices are instructions. Although the AST is optimized to store control flow information over basic blocks, an instruction-based CFG can always be created from a basic block CFG since flow of control within a basic block is trivial. It is often easier to work with instruction-based CFGs even though they can be much larger. Most of the following documentation describes these explicit Boost CFG graphs. The CFGs on which this class operates must follow the Boost Graph Library (BGL) API, although not necessarily a BGL implementation. The graph type is normally a template parameter for the methods herein. This class provides two typedefs for graphs implemented in BGL: BlockGraph is for basic-block CFGs and InsnGraph is for instruction CFGs. The graph must support the BGL adjacency_list graph API with the following features: <ul> <li>the graph vertices are stored as a vector ("vecS" as the second template argument of adjacency_list)</li> <li>the graph is bidirectional ("bidrectionalS" as the third template argument),</li> <li>the boost::vertex_name property is a SgAsmBlock pointer.</li> </ul> The wikipedia entry for "Control Flow Graph" [1] has many useful definitions. The BGL documentation is located at the http://www.boost.org web site. Control flow graphs can be calculated over any subtree of the AST rooted below a SgAsmInterpretation. It doesn't make sense to compute inter-interpretation CFGs since the OS only ever loads one interpretation at a time (instructions from two different interpretations might share the same virtual address). Usually one creates CFGs that span a single function or a whole interpretation. The vertex and edge filtes can restrict which vertices and edges are considered by the various methods of this class. For instance, to create a global CFG that has no inter-function edges one could do the following (see also, Rose::BinaryAnalysis::FunctionCall): @code // Create a filter that rejects all inter-function edges struct NoCallEdges: public ControlFlow::EdgeFilter { bool operator()(ControlFlow *analyzer, SgAsmNode *src, SgAsmNode *dst) { SgAsmFunction *src_func = SageInterface::getEnclosingNode<SgAsmFunction>(src); SgAsmFunction *dst_func = SageInterface::getEnclosingNode<SgAsmFunction>(dst); return dst_func != src_func; } } edge_filter; // Create the control flow analyzer and set its edge filter. ControlFlow analyzer; analyzer.set_edge_filter(&edge_filter); // Generate a block-based CFG over an entire interpretation. It will include // all basic blocks, but only intra-function edges. typedef ControlFlow::BlockGraph CFG_B; SgAsmInterpretation *interp = ...; CFG_B cfg1 = analyzer.build_block_cfg_from_ast<CFG_B>(interp); // Generate an instruction-based CFG over an entire interpretation. It will // include all instructions, but only intra-function edges. typedef ControlFlow::InsnGraph CFG_I; CFG_I cfg2 = analyzer.build_insn_cfg_from_ast<CFG_I>(interp); @endcode Another way to exclude vertices and/or edges from a graph is to first build a complete graph and then do a filtered copy to obtain a second graph with only the desired vertices and edges. @code // Build a complete CFG graph using a default control flow analyzer. CFG_I cfg3 = ControlFlow().build_insn_cfg_from_ast<CFG_I>(interp); // Using the same analyzer as the previous example, one that // filters out all but the function call edges, create a call // graph. CFG_I cfg4 = analyzer.copy(cfg3); @endcode See also, Rose::BinaryAnalysis::FunctionCall, which computes a function call graph whose vertices are functions rather than the basic blocks or instructions used in a CFG. Since binary control flow graphs follow the BGL API they can be easily printed as GraphViz graphs using boost::write_graphviz(). If you want something other than vertex descriptors in the graphs, you could use a PropertyWriter class, like this one, which labels the vertices with the basic block address. Ideally, one would use a class template, but we keep this example simple: @code // Label the graphviz vertices with basic block addresses. // Boost requires this to be declared at file scope. struct GraphvizVertexWriter { const Rose::BinaryAnalysis::ControlFlow::Graph &cfg; GraphvizVertexWriter(Rose::BinaryAnalysis::ControlFlow::Graph &cfg): cfg(cfg) {} typedef boost::graph_traits<Rose::BinaryAnalysis::ControlFlow::Graph>::vertex_descriptor Vertex; void operator()(std::ostream &output, const Vertex &v) { SgAsmBlock *block = get_ast_node(cfg, v); output <<"[ label="" <<StringUtility::addrToString(block->get_address()) <<"" ]"; } };

// Write the graph boost::write_graphviz(std::cout, cfg, GraphvizVertexWriter(cfg));

We also define a similar write_graphviz method within this class that differs from the Boost implementation in two ways. First, the GraphViz file that it produces has the vertices organized into clusters based on the function in which they appear. Second, the vertex and edge property writers are passed as const references to avoid unnecessary copying.

[1] https://secure.wikimedia.org/wikipedia/en/wiki/Control_flow_graph

Definition at line 135 of file ControlFlow.h.

#include <Rose/BinaryAnalysis/ControlFlow.h>

Collaboration diagram for Rose::BinaryAnalysis::ControlFlow:

[legend]

Classes
struct	DefaultEdgePropertyWriter
	Default edge property writer is a no-op. More...

struct	DefaultVertexPropertyWriter
	Default vertex property writer is a no-op. More...

class	EdgeFilter
	Filter for edges. More...

struct	FunctionSubgraphInfo
	List of vertices and intra-function edges for one function. More...

class	VertexFilter
	Filter for vertices. More...

Public Types
typedef boost::adjacency_list< boost::setS, boost::vecS, boost::bidirectionalS, boost::property< boost::vertex_name_t, SgAsmBlock * > >	BlockGraph
	Default basic block control flow graph type.

typedef boost::adjacency_list< boost::setS, boost::vecS, boost::bidirectionalS, boost::property< boost::vertex_name_t, SgAsmInstruction * > >	InsnGraph
	Default instruction-based control flow graph.

typedef BlockGraph	Graph
	Default control flow graph.

Public Member Functions
void	clear_ast (SgNode *ast)
	Clears successor information from the AST.

template<class ControlFlowGraph >
void	apply_to_ast (const ControlFlowGraph &)
	Applies graph to AST.

template<class ControlFlowGraph >
void	cache_vertex_descriptors (const ControlFlowGraph &)
	Cache basic block vertex descriptors in AST.

template<class InsnCFG >
void	fixup_fcall_fret (InsnCFG &cfg, bool preserve_call_fallthrough_edges)
	Fix up a CFG by changing function call and return edges.

template<class ControlFlowGraph >
std::vector< typename boost::graph_traits< ControlFlowGraph >::vertex_descriptor >	flow_order (const ControlFlowGraph &, typename boost::graph_traits< ControlFlowGraph >::vertex_descriptor start, std::vector< size_t > *reverse_order=NULL)
	Orders nodes by depth first search reverse post order.

template<class ControlFlowGraph >
std::vector< typename boost::graph_traits< ControlFlowGraph >::vertex_descriptor >	return_blocks (const ControlFlowGraph &cfg, typename boost::graph_traits< ControlFlowGraph >::vertex_descriptor start)
	Returns list of function return blocks.


void	set_vertex_filter (VertexFilter *filter)
	Manipulate the vertex filter.

VertexFilter *	get_vertex_filter () const
	Manipulate the vertex filter.


void	set_edge_filter (EdgeFilter *filter)
	Manipulate the edge filter.

EdgeFilter *	get_edge_filter () const
	Manipulate the edge filter.


bool	is_vertex_filtered (SgAsmNode bb_or_insn, VertexFilter filter)
	Determines if a vertex is filtered out.

bool	is_vertex_filtered (SgAsmNode *bb_or_insn)
	Determines if a vertex is filtered out.


bool	is_edge_filtered (SgAsmNode src, SgAsmNode dst, EdgeFilter *filter)
	Determines if an edge is filtered out.

bool	is_edge_filtered (SgAsmNode src, SgAsmNode dst)
	Determines if an edge is filtered out.


template<class ControlFlowGraph >
ControlFlowGraph	build_block_cfg_from_ast (SgNode *root)
	Builds a control flow graph for part of an AST.

template<class ControlFlowGraph >
void	build_block_cfg_from_ast (SgNode *root, ControlFlowGraph &cfg)
	Builds a control flow graph for part of an AST.

template<class ControlFlowGraph >
ControlFlowGraph	build_insn_cfg_from_ast (SgNode *root)
	Builds a control flow graph for part of an AST.

template<class ControlFlowGraph >
void	build_insn_cfg_from_ast (SgNode *root, ControlFlowGraph &cfg)
	Builds a control flow graph for part of an AST.


template<class BlockCFG , class InsnCFG >
void	explode_blocks (const BlockCFG &cfgb, InsnCFG &cfgi)
	Create an instruction control flow graph from a basic block control flow graph.


template<class ControlFlowGraph >
ControlFlowGraph	build_cg_from_ast (SgNode *root)
	Builds a control flow graph with only function call edges.

template<class ControlFlowGraph >
void	build_cg_from_ast (SgNode *root, ControlFlowGraph &cfg)
	Builds a control flow graph with only function call edges.


template<class ControlFlowGraph >
ControlFlowGraph	copy (const ControlFlowGraph &src)
	Copies a graph while filtering.

template<class ControlFlowGraph >
void	copy (const ControlFlowGraph &src, ControlFlowGraph &dst)
	Copies a graph while filtering.


template<typename CFG , class VertexPropertyWriter , class EdgePropertyWriter >
void	write_graphviz (std::ostream &, const CFG &, const VertexPropertyWriter &, const EdgePropertyWriter &)
	Write a CFG to a graphviz file, creating a cluster subgraph for each function.

template<typename CFG >
void	write_graphviz (std::ostream &out, const CFG &cfg)
	Write a CFG to a graphviz file, creating a cluster subgraph for each function.

template<typename CFG , class VertexPropertyWriter >
void	write_graphviz (std::ostream &out, const CFG &cfg, const VertexPropertyWriter &vpw)
	Write a CFG to a graphviz file, creating a cluster subgraph for each function.

Protected Attributes
VertexFilter *	vertex_filter

EdgeFilter *	edge_filter

Member Typedef Documentation

◆ BlockGraph

typedef boost::adjacency_list<boost::setS, boost::vecS, boost::bidirectionalS, boost::property<boost::vertex_name_t, SgAsmBlock*> > Rose::BinaryAnalysis::ControlFlow::BlockGraph

Default basic block control flow graph type.

A control flow graph is has a Boost graph interface whose vertex descriptors are integers and whose vertices point to SgAsmBlock nodes in the AST (via the boost::vertex_name property). The graph edges represent flow of control from one basic block to another. Since the control flow graph is a Boost graph, it is endowed with all the features of a Boost graph and can be the operand of the various Boost graph algorithms. See build_block_cfg_from_ast() for specifics about what is included in such a graph.

It is common to need a type for the vertices and edges. Boost graphs store this information in graph_traits and users should use that to obtain those types. Doing so will, in the long run, make your code more extensible since the only datatype you're depending on is the graph itself–change the graph type and the vertex and edge types will automatically adjust. See Boost Graph Library documentation for all the available types. The most common are:

typedef boost::graph_traits<BlockGraph>::vertex_descriptor Vertex;

typedef boost::graph_traits<BlockGraph>::edge_descriptor Edge;

Edge

Definition SgGraphTemplate.h:12

Vertex

Definition SgGraphTemplate.h:7

Definition at line 163 of file ControlFlow.h.

◆ InsnGraph

typedef boost::adjacency_list<boost::setS, boost::vecS, boost::bidirectionalS, boost::property<boost::vertex_name_t, SgAsmInstruction*> > Rose::BinaryAnalysis::ControlFlow::InsnGraph

Default instruction-based control flow graph.

A control flow graph has a Boost graph interface whose vertex descriptors are integers and whose vertices point to SgAsmInstruction nodes in the AST (via the boost::vertex_name property). The graph edges represent flow of control from one instruction to another. Since the control flow graph is a Boost graph, it is endowed with all the features of a Boost graph and can be the operand of the various Boost graph algorithms. See build_insn_cfg_from_ast() for specifics about what is included in such a graph.

It is common to need a type for the vertices and edges. Boost graphs store this information in graph_traits and users should use that to obtain those types. Doing so will, in the long run, make your code more extensible since the only datatype you're depending on is the graph itself–change the graph type and the vertex and edge types will automatically adjust. See Boost Graph Library documentation for all the available types. The most common are:

typedef boost::graph_traits<InsnGraph>::vertex_descriptor Vertex;

typedef boost::graph_traits<InsnGraph>::edge_descriptor Edge;

Definition at line 186 of file ControlFlow.h.

◆ Graph

typedef BlockGraph Rose::BinaryAnalysis::ControlFlow::Graph

Default control flow graph.

The original Rose::BinaryAnalysis::ControlFlow API defined only "Graph", which was a basic-block control flow graph. We continue to define that type for backward compatibility.

Definition at line 190 of file ControlFlow.h.

Constructor & Destructor Documentation

◆ ControlFlow()

Rose::BinaryAnalysis::ControlFlow::ControlFlow ( )

inline

Definition at line 137 of file ControlFlow.h.

Member Function Documentation

◆ set_vertex_filter()

void Rose::BinaryAnalysis::ControlFlow::set_vertex_filter ( VertexFilter * filter )

inline

Manipulate the vertex filter.

When building a control flow graph, the vertex filter is invoked on each vertex which is about to be added. If the filter returns false then that block is not added to the graph. A null filter accepts all vertices.

Definition at line 224 of file ControlFlow.h.

◆ get_vertex_filter()

VertexFilter * Rose::BinaryAnalysis::ControlFlow::get_vertex_filter ( ) const

inline

Manipulate the vertex filter.

When building a control flow graph, the vertex filter is invoked on each vertex which is about to be added. If the filter returns false then that block is not added to the graph. A null filter accepts all vertices.

Definition at line 225 of file ControlFlow.h.

◆ set_edge_filter()

void Rose::BinaryAnalysis::ControlFlow::set_edge_filter ( EdgeFilter * filter )

inline

Manipulate the edge filter.

When building a control flow graph, the edge filter is invoked for each edge which is about to be added to the graph. If the filter returns false then that edge is not added to the graph. A null filter accepts all edges.

Definition at line 234 of file ControlFlow.h.

Referenced by build_cg_from_ast().

◆ get_edge_filter()

EdgeFilter * Rose::BinaryAnalysis::ControlFlow::get_edge_filter ( ) const

inline

Manipulate the edge filter.

When building a control flow graph, the edge filter is invoked for each edge which is about to be added to the graph. If the filter returns false then that edge is not added to the graph. A null filter accepts all edges.

Definition at line 235 of file ControlFlow.h.

Referenced by build_cg_from_ast().

◆ is_vertex_filtered() [1/2]

bool Rose::BinaryAnalysis::ControlFlow::is_vertex_filtered	(	SgAsmNode *	bb_or_insn,
		VertexFilter *	filter
	)

inline

Determines if a vertex is filtered out.

Returns true if the vertex would be filtered out by being rejected by the current vertex filter.

Definition at line 243 of file ControlFlow.h.

Referenced by apply_to_ast(), cache_vertex_descriptors(), and copy().

◆ is_vertex_filtered() [2/2]

bool Rose::BinaryAnalysis::ControlFlow::is_vertex_filtered ( SgAsmNode * bb_or_insn )

inline

Determines if a vertex is filtered out.

Returns true if the vertex would be filtered out by being rejected by the current vertex filter.

Definition at line 244 of file ControlFlow.h.

References is_vertex_filtered().

Referenced by is_vertex_filtered().

◆ is_edge_filtered() [1/2]

bool Rose::BinaryAnalysis::ControlFlow::is_edge_filtered	(	SgAsmNode *	src,
		SgAsmNode *	dst,
		EdgeFilter *	filter
	)

inline

Determines if an edge is filtered out.

Returns true if the edge would be filtered out by being rejected by the current edge filter. The src and dst are the source and destination vertex nodes, either basic blocks or instructions depending on the graph type.

Definition at line 253 of file ControlFlow.h.

Referenced by apply_to_ast(), build_block_cfg_from_ast(), copy(), and is_edge_filtered().

◆ is_edge_filtered() [2/2]

bool Rose::BinaryAnalysis::ControlFlow::is_edge_filtered	(	SgAsmNode *	src,
		SgAsmNode *	dst
	)

inline

Determines if an edge is filtered out.

Returns true if the edge would be filtered out by being rejected by the current edge filter. The src and dst are the source and destination vertex nodes, either basic blocks or instructions depending on the graph type.

Definition at line 256 of file ControlFlow.h.

References is_edge_filtered().

◆ clear_ast()

void Rose::BinaryAnalysis::ControlFlow::clear_ast ( SgNode * ast )

Clears successor information from the AST.

Traverses the specified AST and clears the successor lists for all basic blocks. The blocks are visited by an AST traversal, not by following successor pointers.

The current vertex filter determines which edges are filtered.

◆ apply_to_ast()

template<class ControlFlowGraph >

void Rose::BinaryAnalysis::ControlFlow::apply_to_ast ( const ControlFlowGraph & cfg )

Applies graph to AST.

Just as a control flow graph can be built from the successor lists stored in the AST (see build_block_cfg_from_ast() or build_insn_cfg_from_ast()), a graph can be used to initialize the successor information in an AST. This function does that. Only the blocks which are vertices of the graph and which pass the current vertex filter are affected. Only edges that pass the current edge filter are added as successors to the (cleared) block successor list.

Not all instruction-based graphs can be written back to the AST because the implied basic block structure of the graph might not match the explicit basic block structure in the AST. Perhaps a future version will allow the AST to be restructured by this operation.

At this time [2011-05-19] the successor_complete property of each affected block is set to true, but this may change in the future.

Definition at line 600 of file ControlFlow.h.

References SgAsmStatement::get_address(), Rose::BinaryAnalysis::get_ast_node(), SgAsmBlock::get_successors(), is_edge_filtered(), is_vertex_filtered(), and SgAsmBlock::set_successorsComplete().

◆ cache_vertex_descriptors()

template<class ControlFlowGraph >

void Rose::BinaryAnalysis::ControlFlow::cache_vertex_descriptors ( const ControlFlowGraph & cfg )

Cache basic block vertex descriptors in AST.

The vertices of a control flow graph are of type Vertex, and point at the basic blocks (SgAsmBlock) of the AST. Although most graph algorithms will only need to map Vertex to SgAsmBlock, the inverse mapping is also sometimes useful. That mapping can be stored into an std::map via graph traversal, or stored in the AST itself attached to each SgAsmBlock. Using an std::map requires an O(log N) lookup each time we need to get the vertex descriptor from a block, while storing the vertex descriptor in the AST requires O(1) lookup time.

The vertex descriptors are available via SgAsmBlock::get_cached_vertex(). Other graph types (e.g., dominance graphs) might also use the same cache line. The cached vertex is stored as a size_t, which is the same underlying type for CFG vertices.

The current vertex filter determines which blocks are modified.

Definition at line 631 of file ControlFlow.h.

References Rose::BinaryAnalysis::get_ast_node(), is_vertex_filtered(), and SgAsmBlock::set_cachedVertex().

◆ build_block_cfg_from_ast() [1/2]

template<class ControlFlowGraph >

ControlFlowGraph Rose::BinaryAnalysis::ControlFlow::build_block_cfg_from_ast ( SgNode * root )

Builds a control flow graph for part of an AST.

Builds a control flow graph for the part of the abstract syntax tree rooted at root by traversing the AST to find all basic blocks and using the successors of those blocks to define the edges of the control flow graph. Successors are retrieved via SgAsmBlock::get_successors() and are of type SgAsmIntegerValueExpression. The specified root for the AST should generally not include multiple interpretations (SgAsmInterpretation) since the OS never loads more than one interpretation at a time.

The current vertex and edge filters are used to determine which blocks and flow edges are added to the graph. However, the following types of successors are never added (and don't trigger a call to the filter):

Successors that have no block pointer, but only an address. This can happen when we didn't disassemble any instruction at the successor address, and thus don't have a block at which to point.
Successors that point to a block outside the specified AST subtree. For instance, when considering the control flow graph of an individual function, successors for function calls will point outside the calling function (unless the call is recursive).
Successors that are not known. Some basic blocks, such as function return blocks or blocks ending with computed branches, usually only have unknown successors. Such edges are not added to the graph.

The build_block_cfg_from_ast() builds a CFG whose vertices are basic blocks, while the build_insn_cfg_from_ast() builds a CFG whose vertices are instructions. Furthermore, the instruction-based CFG makes some adjustments to function call and function return nodes by invoking fixup_fcall_fret().

Definition at line 988 of file ControlFlow.h.

References build_block_cfg_from_ast().

Referenced by build_block_cfg_from_ast(), build_cg_from_ast(), and build_insn_cfg_from_ast().

◆ build_block_cfg_from_ast() [2/2]

template<class ControlFlowGraph >

void Rose::BinaryAnalysis::ControlFlow::build_block_cfg_from_ast	(	SgNode *	root,
		ControlFlowGraph &	cfg
	)

Builds a control flow graph for part of an AST.

Builds a control flow graph for the part of the abstract syntax tree rooted at root by traversing the AST to find all basic blocks and using the successors of those blocks to define the edges of the control flow graph. Successors are retrieved via SgAsmBlock::get_successors() and are of type SgAsmIntegerValueExpression. The specified root for the AST should generally not include multiple interpretations (SgAsmInterpretation) since the OS never loads more than one interpretation at a time.

The current vertex and edge filters are used to determine which blocks and flow edges are added to the graph. However, the following types of successors are never added (and don't trigger a call to the filter):

Successors that have no block pointer, but only an address. This can happen when we didn't disassemble any instruction at the successor address, and thus don't have a block at which to point.
Successors that point to a block outside the specified AST subtree. For instance, when considering the control flow graph of an individual function, successors for function calls will point outside the calling function (unless the call is recursive).
Successors that are not known. Some basic blocks, such as function return blocks or blocks ending with computed branches, usually only have unknown successors. Such edges are not added to the graph.

The build_block_cfg_from_ast() builds a CFG whose vertices are basic blocks, while the build_insn_cfg_from_ast() builds a CFG whose vertices are instructions. Furthermore, the instruction-based CFG makes some adjustments to function call and function return nodes by invoking fixup_fcall_fret().

Definition at line 654 of file ControlFlow.h.

References Rose::BinaryAnalysis::get_ast_node(), SgAsmBlock::get_successors(), Map< Key, T, Compare, Alloc >::get_value_or(), and is_edge_filtered().

◆ build_insn_cfg_from_ast() [1/2]

template<class ControlFlowGraph >

ControlFlowGraph Rose::BinaryAnalysis::ControlFlow::build_insn_cfg_from_ast ( SgNode * root )

Builds a control flow graph for part of an AST.

Builds a control flow graph for the part of the abstract syntax tree rooted at root by traversing the AST to find all basic blocks and using the successors of those blocks to define the edges of the control flow graph. Successors are retrieved via SgAsmBlock::get_successors() and are of type SgAsmIntegerValueExpression. The specified root for the AST should generally not include multiple interpretations (SgAsmInterpretation) since the OS never loads more than one interpretation at a time.

The current vertex and edge filters are used to determine which blocks and flow edges are added to the graph. However, the following types of successors are never added (and don't trigger a call to the filter):

Successors that have no block pointer, but only an address. This can happen when we didn't disassemble any instruction at the successor address, and thus don't have a block at which to point.
Successors that point to a block outside the specified AST subtree. For instance, when considering the control flow graph of an individual function, successors for function calls will point outside the calling function (unless the call is recursive).
Successors that are not known. Some basic blocks, such as function return blocks or blocks ending with computed branches, usually only have unknown successors. Such edges are not added to the graph.

The build_block_cfg_from_ast() builds a CFG whose vertices are basic blocks, while the build_insn_cfg_from_ast() builds a CFG whose vertices are instructions. Furthermore, the instruction-based CFG makes some adjustments to function call and function return nodes by invoking fixup_fcall_fret().

Definition at line 997 of file ControlFlow.h.

References build_insn_cfg_from_ast().

Referenced by build_insn_cfg_from_ast().

◆ build_insn_cfg_from_ast() [2/2]

template<class ControlFlowGraph >

void Rose::BinaryAnalysis::ControlFlow::build_insn_cfg_from_ast	(	SgNode *	root,
		ControlFlowGraph &	cfg
	)

Builds a control flow graph for part of an AST.

Builds a control flow graph for the part of the abstract syntax tree rooted at root by traversing the AST to find all basic blocks and using the successors of those blocks to define the edges of the control flow graph. Successors are retrieved via SgAsmBlock::get_successors() and are of type SgAsmIntegerValueExpression. The specified root for the AST should generally not include multiple interpretations (SgAsmInterpretation) since the OS never loads more than one interpretation at a time.

The current vertex and edge filters are used to determine which blocks and flow edges are added to the graph. However, the following types of successors are never added (and don't trigger a call to the filter):

Successors that have no block pointer, but only an address. This can happen when we didn't disassemble any instruction at the successor address, and thus don't have a block at which to point.
Successors that point to a block outside the specified AST subtree. For instance, when considering the control flow graph of an individual function, successors for function calls will point outside the calling function (unless the call is recursive).
Successors that are not known. Some basic blocks, such as function return blocks or blocks ending with computed branches, usually only have unknown successors. Such edges are not added to the graph.

The build_block_cfg_from_ast() builds a CFG whose vertices are basic blocks, while the build_insn_cfg_from_ast() builds a CFG whose vertices are instructions. Furthermore, the instruction-based CFG makes some adjustments to function call and function return nodes by invoking fixup_fcall_fret().

Definition at line 687 of file ControlFlow.h.

References build_block_cfg_from_ast(), explode_blocks(), and fixup_fcall_fret().

◆ explode_blocks()

template<class BlockCFG , class InsnCFG >

void Rose::BinaryAnalysis::ControlFlow::explode_blocks	(	const BlockCFG &	cfgb,
		InsnCFG &	cfgi
	)

Create an instruction control flow graph from a basic block control flow graph.

Definition at line 771 of file ControlFlow.h.

References Rose::BinaryAnalysis::get_ast_node(), Map< Key, T, Compare, Alloc >::get_one(), SgAsmBlock::get_statementList(), and Rose::BinaryAnalysis::put_ast_node().

Referenced by build_insn_cfg_from_ast().

◆ fixup_fcall_fret()

template<class InsnCFG >

void Rose::BinaryAnalysis::ControlFlow::fixup_fcall_fret	(	InsnCFG &	cfg,
		bool	preserve_call_fallthrough_edges
	)

Fix up a CFG by changing function call and return edges.

The AST does not store function return edges (which this method adds), and the AST stores a fall-through edge for function call nodes for callees that may return (which this method removes).

Definition at line 827 of file ControlFlow.h.

References WorkList< T, Compare >::empty(), SgAsmStatement::get_address(), Rose::BinaryAnalysis::get_ast_node(), SgAsmFunction::get_entryVa(), Map< Key, T, Compare, Alloc >::get_one(), Map< Key, T, Compare, Alloc >::get_value_or(), SgAsmBlock::isFunctionCall(), WorkList< T, Compare >::push(), and WorkList< T, Compare >::shift().

Referenced by build_insn_cfg_from_ast().

◆ build_cg_from_ast() [1/2]

template<class ControlFlowGraph >

ControlFlowGraph Rose::BinaryAnalysis::ControlFlow::build_cg_from_ast ( SgNode * root )

Builds a control flow graph with only function call edges.

This differs from a true FunctionCall::Graph in that the vertices of the returned graph point to basic blocks, while the vertices of a FunctionCall::Graph point to functions (SgAsmFunction nodes).

The graph is built by applying an edge filter (in addition to the edge filter that might be set by the user) that only accepts edges whose target is a function entry block.

Definition at line 1006 of file ControlFlow.h.

References build_cg_from_ast().

Referenced by build_cg_from_ast().

◆ build_cg_from_ast() [2/2]

template<class ControlFlowGraph >

void Rose::BinaryAnalysis::ControlFlow::build_cg_from_ast	(	SgNode *	root,
		ControlFlowGraph &	cfg
	)

Builds a control flow graph with only function call edges.

This differs from a true FunctionCall::Graph in that the vertices of the returned graph point to basic blocks, while the vertices of a FunctionCall::Graph point to functions (SgAsmFunction nodes).

The graph is built by applying an edge filter (in addition to the edge filter that might be set by the user) that only accepts edges whose target is a function entry block.

Definition at line 698 of file ControlFlow.h.

References build_block_cfg_from_ast(), get_edge_filter(), SgAsmFunction::get_entryBlock(), and set_edge_filter().

◆ copy() [1/2]

template<class ControlFlowGraph >

ControlFlowGraph Rose::BinaryAnalysis::ControlFlow::copy ( const ControlFlowGraph & src )

Copies a graph while filtering.

Copies a graph while applying the current source and destination vertex and edge filters. If all vertices are selected by the vertex filter, then the desintation graph's vertex descriptors will correspond to the same vertices in the source graph (i.e., vertex V in the source will be the same basic block as vertex V in the destination).

If an edge is unfiltered but one of its vertices is filtered, then the edge will not be included in the result.

Definition at line 762 of file ControlFlow.h.

References copy().

Referenced by copy().

◆ copy() [2/2]

template<class ControlFlowGraph >

void Rose::BinaryAnalysis::ControlFlow::copy	(	const ControlFlowGraph &	src,
		ControlFlowGraph &	dst
	)

Copies a graph while filtering.

Copies a graph while applying the current source and destination vertex and edge filters. If all vertices are selected by the vertex filter, then the desintation graph's vertex descriptors will correspond to the same vertices in the source graph (i.e., vertex V in the source will be the same basic block as vertex V in the destination).

If an edge is unfiltered but one of its vertices is filtered, then the edge will not be included in the result.

Definition at line 732 of file ControlFlow.h.

References Rose::BinaryAnalysis::get_ast_node(), is_edge_filtered(), is_vertex_filtered(), and Rose::BinaryAnalysis::put_ast_node().

◆ write_graphviz() [1/3]

template<typename CFG , class VertexPropertyWriter , class EdgePropertyWriter >

void Rose::BinaryAnalysis::ControlFlow::write_graphviz	(	std::ostream &	out,
		const CFG &	cfg,
		const VertexPropertyWriter &	vpw,
		const EdgePropertyWriter &	epw
	)

Write a CFG to a graphviz file, creating a cluster subgraph for each function.

Write a control flow graph to a graphviz file, creating a cluster subgraph for each function.

Definition at line 1016 of file ControlFlow.h.

References Rose::StringUtility::addrToString(), Rose::BinaryAnalysis::get_ast_node(), SgAsmFunction::get_entryVa(), and SgAsmFunction::get_name().

Referenced by write_graphviz(), and write_graphviz().

◆ write_graphviz() [2/3]

template<typename CFG >

void Rose::BinaryAnalysis::ControlFlow::write_graphviz	(	std::ostream &	out,
		const CFG &	cfg
	)

inline

Write a CFG to a graphviz file, creating a cluster subgraph for each function.

Write a control flow graph to a graphviz file, creating a cluster subgraph for each function.

Definition at line 428 of file ControlFlow.h.

References write_graphviz().

◆ write_graphviz() [3/3]

template<typename CFG , class VertexPropertyWriter >

void Rose::BinaryAnalysis::ControlFlow::write_graphviz	(	std::ostream &	out,
		const CFG &	cfg,
		const VertexPropertyWriter &	vpw
	)

inline

Write a CFG to a graphviz file, creating a cluster subgraph for each function.

Write a control flow graph to a graphviz file, creating a cluster subgraph for each function.

Definition at line 433 of file ControlFlow.h.

References write_graphviz().

◆ flow_order()

template<class ControlFlowGraph >

std::vector< typename boost::graph_traits< ControlFlowGraph >::vertex_descriptor > Rose::BinaryAnalysis::ControlFlow::flow_order	(	const ControlFlowGraph &	cfg,
		typename boost::graph_traits< ControlFlowGraph >::vertex_descriptor	start,
		std::vector< size_t > *	reverse_order = `NULL`
	)

Orders nodes by depth first search reverse post order.

Reversed, depth-first-search, post-order is a common node order needed for solving flow equations, and this method returns a vector whose elements are graph vertices. The algorithm is to allocate the vector to be the same length as the total number of vertices in the graph, and then do a depth-first-search starting with the specified node. Each node is visited after all its children (post-order). Each node visit adds the node to the vector starting at the end of the vector and working forward.

If reverse_order is non-null then it will be the inverse mapping from the returned vector. In other words, if the return value is named forward_order, then

forward_order[i] == v implies reverse_order[v] == i

Here's an example of how this would typically be used.

std::vector<size_t> rflowlist; // reverse mapping
std::vector<ControlFlow::Vector> flowlist;
flowlist = ControlFlow().flow_order(cfg, start, &rflowlist);
 
bool changed;
do {
    changed = false;
    for (size_t i=0; i<flowlist.size(); ++i) {
        ControlFlow::Vertex vertex = flowlist[i];
        // solve flow equation for vertex...
        if (result_at_vertex_changed)
            changed = true;
    }
} while (changed);

Definition at line 955 of file ControlFlow.h.

◆ return_blocks()

template<class ControlFlowGraph >

std::vector< typename boost::graph_traits< ControlFlowGraph >::vertex_descriptor > Rose::BinaryAnalysis::ControlFlow::return_blocks	(	const ControlFlowGraph &	cfg,
		typename boost::graph_traits< ControlFlowGraph >::vertex_descriptor	start
	)

Returns list of function return blocks.

More specifically, this method traverses the control flow graph (CFG) beginning at the specified node and returns a list (in depth first search order) of all vertices which are in the connected subgraph and which do not have any known successors, but at least one unknown successor.

Currently works only for basic block CFGs.

Definition at line 976 of file ControlFlow.h.

Member Data Documentation

◆ vertex_filter

VertexFilter* Rose::BinaryAnalysis::ControlFlow::vertex_filter

protected

Definition at line 262 of file ControlFlow.h.

◆ edge_filter

EdgeFilter* Rose::BinaryAnalysis::ControlFlow::edge_filter

protected

Definition at line 263 of file ControlFlow.h.

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

ControlFlow.h

Description

Classes

Public Types

Public Member Functions

Protected Attributes

Member Typedef Documentation

◆ BlockGraph

◆ InsnGraph

◆ Graph

Constructor & Destructor Documentation

◆ ControlFlow()

Member Function Documentation

◆ set_vertex_filter()

◆ get_vertex_filter()

◆ set_edge_filter()

◆ get_edge_filter()

◆ is_vertex_filtered() [1/2]

◆ is_vertex_filtered() [2/2]

◆ is_edge_filtered() [1/2]

◆ is_edge_filtered() [2/2]

◆ clear_ast()

◆ apply_to_ast()

◆ cache_vertex_descriptors()

◆ build_block_cfg_from_ast() [1/2]

◆ build_block_cfg_from_ast() [2/2]

◆ build_insn_cfg_from_ast() [1/2]

◆ build_insn_cfg_from_ast() [2/2]

◆ explode_blocks()

◆ fixup_fcall_fret()

◆ build_cg_from_ast() [1/2]

◆ build_cg_from_ast() [2/2]

◆ copy() [1/2]

◆ copy() [2/2]

◆ write_graphviz() [1/3]

◆ write_graphviz() [2/3]

◆ write_graphviz() [3/3]

◆ flow_order()

◆ return_blocks()

Member Data Documentation

◆ vertex_filter

◆ edge_filter