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 dfs_postorder_nodes_deterministic_multi(graph, sources)¶

Deterministic post-order DFS covering multiple source nodes with a single shared visited set. Equivalent to dfs_postorder_nodes_deterministic over a synthetic super-source connected to every node in sources (sources are traversed in _sort_node order), but without mutating the graph – so it works directly on a zero-copy overlay view. Use it for multi-entry acyclic graphs.

Parameters:

graph (networkx.DiGraph[T])
sources (Iterable[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.

class angr.utils.graph.LinkedListNode¶

Bases: Generic

A node in a linked list.

__init__(v)¶

Parameters:: v (T)

v: T

next: LinkedListNode | None

prev: LinkedListNode | None

class angr.utils.graph.DirectedGraphHelper¶

Bases: Generic

A helper class for accelerating some graph algorithms on directed graphs.

_node_order keeps a dictionary of nodes and their order in a quasi-topological sort of the region full graph (graph_with_successors). _generate_node_order() initializes this dictionary. we then update this dictionary when new nodes are created.

We do not populate _node_order when working on acyclic graphs because it’s not used for acyclic graphs.

__init__(graph, cyclic_graph, head)¶

reset()¶

dfs_postorder_nodes_deterministic(source)¶

Post-order DFS traversal of the directed graph using cache. Avoids acyclic-graph conversion or full-graph traversal when cache is available.

Return type:: Iterator[TypeVar(T)]
Parameters:: source (T)

replace_node(old_node, new_node)¶

Update cache when a node is replaced in the graph.

Parameters:

old_node (T)
new_node (T)

replace_nodes(old_node_0, old_node_1, new_node)¶

Update cache when multiple nodes are replaced by a single node in the graph.

Return type:

None

Parameters:

old_node_0 (T)
old_node_1 (T)
new_node (T)

remove_node(node)¶

Update cache when a node is removed from the graph.

Parameters:: node (T)

add_node_successor(node, successor)¶

Return type:

None

Parameters:

node (T)
successor (T)

to_acyclic_by_order(graph)¶

Parameters:: graph (RegionOverlayGraph[T])
Return type:: networkx.DiGraph[T]

sort_nodes_by_order(nodes)¶

Return type:: list[TypeVar(T)]
Parameters:: nodes (list[T])

loop_heads()¶

Return type:: set[TypeVar(T)]