angr.utils.graph

angr.utils.graph.shallow_reverse(g)

Make a shallow copy of a directional graph and reverse the edges. This is a workaround to solve the issue that one cannot easily make a shallow reversed copy of a graph in NetworkX 2, since networkx.reverse(copy=False) now returns a GraphView, and GraphViews are always read-only.

Parameters:

g (networkx.DiGraph) – The graph to reverse.

Returns:

A new networkx.DiGraph that has all nodes and all edges of the original graph, with edges reversed.

angr.utils.graph.inverted_idoms(graph, end_node=None)

Invert the given graph and generate the immediate dominator tree on the inverted graph. This is useful for computing post-dominators.

Parameters:

graph – The graph to invert and generate immediate dominator tree for.

Returns:

A tuple of the inverted graph and the immediate dominator tree.

angr.utils.graph.to_acyclic_graph(graph, node_order=None, loop_heads=None)

Convert a given DiGraph into an acyclic graph.

Parameters:

  • graph – The graph to convert.

  • ordered_nodes – A list of nodes sorted in a topological order.

  • loop_heads – A list of known loop head nodes.

Returns:

The converted acyclic graph.

angr.utils.graph.dfs_back_edges(graph, start_node, *, visit_all_nodes=False, visited=None)

Perform an iterative DFS traversal of the graph, returning back edges.

Parameters:

  • graph – The graph to traverse.

  • start_node – The node where to start the traversal.

Returns:

An iterator of ‘backward’ edges.

angr.utils.graph.subgraph_between_nodes(graph, source, frontier, include_frontier=False)

For a directed graph, return a subgraph that includes all nodes going from a source node to a target node.

Parameters:

  • graph (networkx.DiGraph) – The directed graph.

  • source – The source node.

  • frontier (list) – A collection of target nodes.

  • include_frontier (bool) – Should nodes in frontier be included in the subgraph.

Returns:

A subgraph.

Return type:

networkx.DiGraph

angr.utils.graph.dominates(idom, dominator_node, node)
Return type:

bool

Parameters:

  • idom (dict[T, T])

  • dominator_node (T)

  • node (T)

angr.utils.graph.compute_dominance_frontier(graph, domtree)

Compute a dominance frontier based on the given post-dominator tree.

This implementation is based on figure 2 of paper An Efficient Method of Computing Static Single Assignment Form by Ron Cytron, etc.

Parameters:

  • graph – The graph where we want to compute the dominance frontier.

  • domtree – The dominator tree

Returns:

A dict of dominance frontier

class angr.utils.graph.TemporaryNode

Bases: object

A temporary node.

Used as the start node and end node in post-dominator tree generation. Also used in some test cases.

__init__(label)
class angr.utils.graph.ContainerNode

Bases: Generic

A container node.

Only used in dominator tree generation. We did this so we can set the index property without modifying the original object.

__init__(obj)
Parameters:

obj (T)

index: int | None
property obj: T
class angr.utils.graph.Dominators

Bases: Generic

Describes dominators in a graph.

__init__(graph, entry_node, successors_func=None, reverse=False)
dom: networkx.DiGraph[T]
class angr.utils.graph.PostDominators

Bases: Dominators, Generic

Describe post-dominators in a graph.

__init__(graph, entry_node, successors_func=None)
property post_dom: networkx.DiGraph[T]
class angr.utils.graph.SCCPlaceholder

Bases: object

Describes a placeholder for strongly-connected-components in a graph.

__init__(scc_id, addr)
scc_id
addr
class angr.utils.graph.GraphUtils

Bases: object

A helper class with some static methods and algorithms implemented, that in fact, might take more than just normal CFGs.

static find_merge_points(function_addr, function_endpoints, graph)

Given a local transition graph of a function, find all merge points inside, and then perform a quasi-topological sort of those merge points.

A merge point might be one of the following cases: - two or more paths come together, and ends at the same address. - end of the current function

Parameters:

  • function_addr (int) – Address of the function.

  • function_endpoints (list) – Endpoints of the function. They typically come from Function.endpoints.

  • graph (networkx.DiGraph) – A local transition graph of a function. Normally it comes from Function.graph.

Returns:

A list of ordered addresses of merge points.

Return type:

list

static find_widening_points(function_addr, function_endpoints, graph)

Given a local transition graph of a function, find all widening points inside.

Correctly choosing widening points is very important in order to not lose too much information during static analysis. We mainly consider merge points that has at least one loop back edges coming in as widening points.

Parameters:

  • function_addr (int) – Address of the function.

  • function_endpoints (list) – Endpoints of the function, typically coming from Function.endpoints.

  • graph (networkx.DiGraph) – A local transition graph of a function, normally Function.graph.

Returns:

A list of addresses of widening points.

Return type:

list

static dfs_postorder_nodes_deterministic(graph, source)
Parameters:

  • graph (networkx.DiGraph[T])

  • source (T)

Return type:

Iterator[T]

static reverse_post_order_sort_nodes(graph, nodes=None)

Sort a given set of nodes in reverse post ordering.

Parameters:

  • graph (networkx.DiGraph) – A local transition graph of a function.

  • nodes (iterable) – A collection of nodes to sort.

Returns:

A list of sorted nodes.

Return type:

list

static quasi_topological_sort_nodes(graph, nodes=None, loop_heads=None, panic_mode_threshold=3000)

Sort a given set of nodes from a graph based on the following rules:

# - if A -> B and not B -> A, then we have A < B # - if A -> B and B -> A, then the ordering is undefined

Following the above rules gives us a quasi-topological sorting of nodes in the graph. It also works for cyclic graphs.

Parameters:

  • graph (DiGraph) – A local transition graph of the function.

  • nodes (list | None) – A list of nodes to sort. None if you want to sort all nodes inside the graph.

  • loop_heads (list | None) – A list of nodes that should be treated loop heads.

  • panic_mode_threshold (int) – Threshold of nodes in an SCC to begin aggressively removing edges.

Return type:

list

Returns:

A list of ordered nodes.

static loop_nesting_forest(graph, start_node)

Generates the loop-nesting forest for the provided directional graph. This is not the algorithm proposed by Ramalingam.

Parameters:

  • graph (DiGraph) – the graph to generate the loop-nesting forest for.

  • start_node – the node to start traversing the graph from.

Return type:

OrderedDict[Any, DiGraph]

Returns:

An ordered dict of loop heads to their corresponding loop nodes.