Control-flow graph analysis using Miasm

graph_analysis.py

# (c) Tim Blazytko 2021
# implementation used in the blog post "Introduction to Control-flow Graph Analysis"
# https://synthesis.to/2021/03/15/control_flow_analysis.html
from miasm.core.graph import DiGraph

# define edges
edges = [
    ("a", "b"),
    ("a", "c"),
    ("b", "d"),
    ("c", "d"),
    ("c", "e"),
    ("d", "f"),
    ("e", "f"),
    ("e", "g"),
    ("g", "c"),
]

# init graph
g = DiGraph()

# add edges
for x, y in edges:
    g.add_edge(x, y)

# walk over graph entries
for entry in g.heads():
    # dominators
    dominators = g.compute_dominators(entry)

    # dominator tree
    dominator_tree = g.compute_dominator_tree(entry)

    # natural loops
    loops = g.compute_natural_loops(entry)

    # pretty print entry
    print(f"Graph entry: {entry}")

    print("\n")

    # pretty print dominators
    print("Dominators:")
    for node, dominated in sorted(dominators.items()):
        print(f"{node}: {', '.join(sorted(dominated))}")

    print("\n")

    # pretty print dominator tree
    print("Dominator Tree:")
    for x, y in sorted(dominator_tree.edges()):
        print(f"{x} -> {y}")

    print("\n")

    # pretty print natural loops
    print("Natural Loops")
    for edge, body in g.compute_natural_loops(entry):
        edge_string = f"{edge[0]} -> {edge[1]}"
        body_string = f"{', '.join(sorted(dominated))}"
        print(f"{edge_string}: {{{body_string}}}")