Description

Binary function call analysis.

This class serves mostly to organize the functions that operate on function calls, but also provides a container for various settings that influence the function call analyses, such as vertex and edge filters.

Function call graphs can be computed over any subtree of the AST, although one usually does so over an entire binary interpretation (SgAsmInterpretation). The vertex and edge filters can restrict which functions and call edges are considered by the various methods of this class.

Definition at line 21 of file FunctionCall.h.

#include <Rose/BinaryAnalysis/FunctionCall.h>

Collaboration diagram for Rose::BinaryAnalysis::FunctionCall:

[legend]

Classes
class	EdgeFilter
	Filter for edges. 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, SgAsmFunction * > >	Graph
	The default function call graph type.

Public Member Functions
template<class FunctionCallGraph >
void	cache_vertex_descriptors (const FunctionCallGraph &)
	Cache vertex descriptors in AST.


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 (SgAsmFunction func, VertexFilter filter)
	Determines if a vertex is filtered out.

bool	is_vertex_filtered (SgAsmFunction *func)
	Determines if a vertex is filtered out.


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

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


template<class FunctionCallGraph , class ControlFlowGraph >
FunctionCallGraph	build_cg_from_cfg (const ControlFlowGraph &)
	Build a function call graph from a control flow graph.

template<class ControlFlowGraph , class FunctionCallGraph >
void	build_cg_from_cfg (const ControlFlowGraph &cfg, FunctionCallGraph &cg)
	Build a function call graph from a control flow graph.


template<class FunctionCallGraph >
FunctionCallGraph	build_cg_from_ast (SgNode *root)
	Build a function call graph from an AST.

template<class FunctionCallGraph >
void	build_cg_from_ast (SgNode *root, FunctionCallGraph &cg)
	Build a function call graph from an AST.


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

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

Protected Attributes
VertexFilter *	vertex_filter

EdgeFilter *	edge_filter

Member Typedef Documentation

◆ Graph

typedef boost::adjacency_list<boost::setS, boost::vecS, boost::bidirectionalS, boost::property<boost::vertex_name_t, SgAsmFunction*> > Rose::BinaryAnalysis::FunctionCall::Graph

The default function call graph type.

A function call graph is simply a Boost graph whose vertex descriptors are integers and whose vertices point to SgAsmFunction nodes in the AST (via the boost::vertex_name property). The graph edges represent function calls from one SgAsmFunction to another. Since this 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_cg() for specifics about what is included in such a graph.

Another way to represent function calls is to adapt a global control flow graph (Rose::BinaryAnalysis::ControlFlowGraph) to include only the edges (and their incident vertices) that flow from one function to another. The advantage of using a control flow graph to represent function call information is that each call site will be included in the function call graph due to the fact that the control flow graph vertices are blocks (SgAsmBlock) rather than functions (SgAsmFunction).

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<Graph>::vertex_descriptor Vertex;

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

Edge

Definition SgGraphTemplate.h:12

Vertex

Definition SgGraphTemplate.h:7

Definition at line 56 of file FunctionCall.h.

Constructor & Destructor Documentation

◆ FunctionCall()

Rose::BinaryAnalysis::FunctionCall::FunctionCall ( )

inline

Definition at line 24 of file FunctionCall.h.

Member Function Documentation

◆ set_vertex_filter()

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

inline

Manipulate the vertex filter.

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

Definition at line 91 of file FunctionCall.h.

◆ get_vertex_filter()

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

inline

Manipulate the vertex filter.

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

Definition at line 92 of file FunctionCall.h.

◆ set_edge_filter()

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

inline

Manipulate the edge filter.

When building a function call 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 101 of file FunctionCall.h.

◆ get_edge_filter()

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

inline

Manipulate the edge filter.

When building a function call 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 102 of file FunctionCall.h.

◆ is_vertex_filtered() [1/2]

bool Rose::BinaryAnalysis::FunctionCall::is_vertex_filtered	(	SgAsmFunction *	func,
		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 110 of file FunctionCall.h.

Referenced by build_cg_from_ast(), build_cg_from_cfg(), cache_vertex_descriptors(), copy(), and is_vertex_filtered().

◆ is_vertex_filtered() [2/2]

bool Rose::BinaryAnalysis::FunctionCall::is_vertex_filtered ( SgAsmFunction * func )

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 113 of file FunctionCall.h.

References is_vertex_filtered().

◆ is_edge_filtered() [1/2]

bool Rose::BinaryAnalysis::FunctionCall::is_edge_filtered	(	SgAsmFunction *	src,
		SgAsmFunction *	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.

Definition at line 123 of file FunctionCall.h.

Referenced by build_cg_from_ast(), build_cg_from_cfg(), copy(), and is_edge_filtered().

◆ is_edge_filtered() [2/2]

bool Rose::BinaryAnalysis::FunctionCall::is_edge_filtered	(	SgAsmFunction *	src,
		SgAsmFunction *	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.

Definition at line 126 of file FunctionCall.h.

References is_edge_filtered().

◆ cache_vertex_descriptors()

template<class FunctionCallGraph >

void Rose::BinaryAnalysis::FunctionCall::cache_vertex_descriptors ( const FunctionCallGraph & cg )

Cache vertex descriptors in AST.

The vertices of a function call graph are of type Vertex, and point at the functions (SgAsmFunction) of the AST. Although most graph algorithms will only need to map Vertex to SgAsmFunction, 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 SgAsmFunction. Using an std::map requires an O(log N) lookup each time we need to get the vertex descriptor for a function, while storing the vertex descriptor in the AST requires O(1) lookup time.

The vertex descriptors are available via SgAsmFunction::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 function call graph vertices.

The current vertex filter determines which function nodes are modified.

Definition at line 238 of file FunctionCall.h.

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

◆ build_cg_from_cfg() [1/2]

template<class FunctionCallGraph , class ControlFlowGraph >

FunctionCallGraph Rose::BinaryAnalysis::FunctionCall::build_cg_from_cfg ( const ControlFlowGraph & cfg )

Build a function call graph from a control flow graph.

Given a control flow graph (CFG) spanning multiple functions, create a function call graph (CG) by collapsing vertices in the CFG that belong to a common function. Any resulting self-loop edges will be removed unless the target of the corresponding edge in the CFG was the function entry block (i.e., intra-function CFG edges whose target is the function's entry block are assumed to be recursive calls, while all other intra-function CFG edges are omitted from the CG).

The current vertex and edge filters are used to restrict which functions and calls make it into the graph.

Definition at line 297 of file FunctionCall.h.

References build_cg_from_cfg().

Referenced by build_cg_from_cfg().

◆ build_cg_from_cfg() [2/2]

template<class ControlFlowGraph , class FunctionCallGraph >

void Rose::BinaryAnalysis::FunctionCall::build_cg_from_cfg	(	const ControlFlowGraph &	cfg,
		FunctionCallGraph &	cg
	)

Build a function call graph from a control flow graph.

Given a control flow graph (CFG) spanning multiple functions, create a function call graph (CG) by collapsing vertices in the CFG that belong to a common function. Any resulting self-loop edges will be removed unless the target of the corresponding edge in the CFG was the function entry block (i.e., intra-function CFG edges whose target is the function's entry block are assumed to be recursive calls, while all other intra-function CFG edges are omitted from the CG).

The current vertex and edge filters are used to restrict which functions and calls make it into the graph.

Definition at line 250 of file FunctionCall.h.

References Rose::BinaryAnalysis::get_ast_node(), SgAsmBlock::get_enclosingFunction(), SgAsmFunction::get_entryBlock(), is_edge_filtered(), is_vertex_filtered(), and Rose::BinaryAnalysis::put_ast_node().

◆ build_cg_from_ast() [1/2]

template<class FunctionCallGraph >

FunctionCallGraph Rose::BinaryAnalysis::FunctionCall::build_cg_from_ast ( SgNode * root )

Build a function call graph from an AST.

Given an AST, traverse the AST beginning at root and build a function call graph (CG). The function call graph will contain only SgAsmFunction vertices that are in the specified subtree and which are not filtered out by the current vertex filter. Edges also must pass the edge filter to be included in the graph.

The following two methods of constructing a CG should result in identical graphs (although vertex and edge order may be different):

using namespace Rose::BinaryAnalysis;
typedef FunctionCall::Graph CG;
typedef ControlFlow::Graph  CFG;
SgAsmNode *node = ...;
 
// Method 1
CG cg1 = FunctionCall().build_cg_from_ast(node);
 
// Method 2
CFG cfg = ControlFlow().build_block_cfg_from_ast<CFG>(node);
CG cg2 = FunctionCall().build_cg_from_cfg<CG>(cfg);

In general, building the function call graph directly from the AST will be faster than first building the control flow graph.

Definition at line 377 of file FunctionCall.h.

References build_cg_from_ast().

Referenced by build_cg_from_ast().

◆ build_cg_from_ast() [2/2]

template<class FunctionCallGraph >

void Rose::BinaryAnalysis::FunctionCall::build_cg_from_ast	(	SgNode *	root,
		FunctionCallGraph &	cg
	)

Build a function call graph from an AST.

Given an AST, traverse the AST beginning at root and build a function call graph (CG). The function call graph will contain only SgAsmFunction vertices that are in the specified subtree and which are not filtered out by the current vertex filter. Edges also must pass the edge filter to be included in the graph.

The following two methods of constructing a CG should result in identical graphs (although vertex and edge order may be different):

using namespace Rose::BinaryAnalysis;
typedef FunctionCall::Graph CG;
typedef ControlFlow::Graph  CFG;
SgAsmNode *node = ...;
 
// Method 1
CG cg1 = FunctionCall().build_cg_from_ast(node);
 
// Method 2
CFG cfg = ControlFlow().build_block_cfg_from_ast<CFG>(node);
CG cg2 = FunctionCall().build_cg_from_cfg<CG>(cfg);

In general, building the function call graph directly from the AST will be faster than first building the control flow graph.

Definition at line 306 of file FunctionCall.h.

References SgAsmStatement::get_address(), Rose::BinaryAnalysis::get_ast_node(), SgAsmBlock::get_enclosingFunction(), SgAsmFunction::get_entryVa(), SgAsmBlock::get_successors(), is_edge_filtered(), is_vertex_filtered(), and Rose::BinaryAnalysis::put_ast_node().

◆ copy() [1/2]

template<class FunctionCallGraph >

FunctionCallGraph Rose::BinaryAnalysis::FunctionCall::copy ( const FunctionCallGraph & 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 416 of file FunctionCall.h.

References copy().

Referenced by copy().

◆ copy() [2/2]

template<class FunctionCallGraph >

void Rose::BinaryAnalysis::FunctionCall::copy	(	const FunctionCallGraph &	src,
		FunctionCallGraph &	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 386 of file FunctionCall.h.

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

Member Data Documentation

◆ vertex_filter

VertexFilter* Rose::BinaryAnalysis::FunctionCall::vertex_filter

protected

Definition at line 132 of file FunctionCall.h.

◆ edge_filter

EdgeFilter* Rose::BinaryAnalysis::FunctionCall::edge_filter

protected

Definition at line 133 of file FunctionCall.h.

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

FunctionCall.h

Description

Classes

Public Types

Public Member Functions

Protected Attributes

Member Typedef Documentation

◆ Graph

Constructor & Destructor Documentation

◆ FunctionCall()

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]

◆ cache_vertex_descriptors()

◆ build_cg_from_cfg() [1/2]

◆ build_cg_from_cfg() [2/2]

◆ build_cg_from_ast() [1/2]

◆ build_cg_from_ast() [2/2]

◆ copy() [1/2]

◆ copy() [2/2]

Member Data Documentation

◆ vertex_filter

◆ edge_filter