Skip to content

Instantly share code, notes, and snippets.

@mrphrazer
Created March 15, 2021 19:44
Show Gist options
  • Save mrphrazer/ee0edd2bd0c6a121011bd86ae11d5567 to your computer and use it in GitHub Desktop.
Save mrphrazer/ee0edd2bd0c6a121011bd86ae11d5567 to your computer and use it in GitHub Desktop.
Control-flow graph analysis using Miasm
# (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}}}")
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment