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>
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. More... | |
Public Member Functions | |
| template<class FunctionCallGraph > | |
| void | cache_vertex_descriptors (const FunctionCallGraph &) |
| Cache vertex descriptors in AST. More... | |
| void | set_vertex_filter (VertexFilter *filter) |
| Manipulate the vertex filter. More... | |
| VertexFilter * | get_vertex_filter () const |
| Manipulate the vertex filter. More... | |
| void | set_edge_filter (EdgeFilter *filter) |
| Manipulate the edge filter. More... | |
| EdgeFilter * | get_edge_filter () const |
| Manipulate the edge filter. More... | |
| bool | is_vertex_filtered (SgAsmFunction *func, VertexFilter *filter) |
| Determines if a vertex is filtered out. More... | |
| bool | is_vertex_filtered (SgAsmFunction *func) |
| Determines if a vertex is filtered out. More... | |
| bool | is_edge_filtered (SgAsmFunction *src, SgAsmFunction *dst, EdgeFilter *filter) |
| Determines if an edge is filtered out. More... | |
| bool | is_edge_filtered (SgAsmFunction *src, SgAsmFunction *dst) |
| Determines if an edge is filtered out. More... | |
| template<class FunctionCallGraph , class ControlFlowGraph > | |
| FunctionCallGraph | build_cg_from_cfg (const ControlFlowGraph &) |
| Build a function call graph from a control flow graph. More... | |
| 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. More... | |
| template<class FunctionCallGraph > | |
| FunctionCallGraph | build_cg_from_ast (SgNode *root) |
| Build a function call graph from an AST. More... | |
| template<class FunctionCallGraph > | |
| void | build_cg_from_ast (SgNode *root, FunctionCallGraph &cg) |
| Build a function call graph from an AST. More... | |
| template<class FunctionCallGraph > | |
| FunctionCallGraph | copy (const FunctionCallGraph &src) |
| Copies a graph while filtering. More... | |
| template<class FunctionCallGraph > | |
| void | copy (const FunctionCallGraph &src, FunctionCallGraph &dst) |
| Copies a graph while filtering. More... | |
Protected Attributes | |
| VertexFilter * | vertex_filter |
| EdgeFilter * | edge_filter |
Member Typedef Documentation
| 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:
Definition at line 56 of file FunctionCall.h.
Member Function Documentation
|
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.
|
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.
|
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.
|
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.
|
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().
|
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().
|
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().
|
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().
| 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().
| 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.
| 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_enclosing_function(), SgAsmFunction::get_entry_block(), is_edge_filtered(), is_vertex_filtered(), and Rose::BinaryAnalysis::put_ast_node().
| 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):
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.
| 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):
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_enclosing_function(), SgAsmBlock::get_successors(), is_edge_filtered(), is_vertex_filtered(), and Rose::BinaryAnalysis::put_ast_node().
| 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.
| 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().
The documentation for this class was generated from the following file:
