## Introduction to Control-flow Graph Analysis

• by Tim Blazytko
• 15 March, 2021

Following my last blog post, I got a lot of questions about additional material on control-flow analysis. While most compiler books (such as the Dragon Book) cover related topics in-depth, I decided to publish my own presentation. The slide deck illustrates the theory of control-flow graph construction, dominance relations and loop analysis. In the second part of this post, I would like to show you how to play around with these concepts using the reverse engineering framework Miasm.

## Graph Analysis in Miasm

For playing around with control-flow graphs, dominance relations and loop detection, we take the following graph as an example: As described in my previous blog post on automated detection of control-flow flattening, this graph has an entry node `a` and a loop between `c`, `e` and `g`. To automatically determine all entries, dominance relations and loops, we can use Miasm’s `DiGraph` class:

``````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()

for x, y in edges:

# walk over graph entries
# dominators
dominators = g.compute_dominators(entry)

# dominator tree
dominator_tree = g.compute_dominator_tree(entry)

# natural loops
loops = g.compute_natural_loops(entry)

``````

First, we initialize a `DiGraph` instance and add all edges to the graph. Then, we walk over all graph entry nodes and compute the dominance relations, the dominator tree and all loops in the graph. With some additional code for pretty printing (omitted here due to readability), we get the following output:

``````Graph entry: a

Dominators:
a: a
b: a, b
c: a, c
d: a, d
e: a, c, e
f: a, f
g: a, c, e, g

Dominator Tree:
a -> b
a -> c
a -> d
a -> f
c -> e
e -> g

Natural Loops
g -> c: {a, c, e, g}
``````

To apply these techniques to real-world binaries, we just wrap around some disassembling logic:

``````# init symbol table
loc_db = LocationDB()

# open the binary for analysis
container = Container.from_stream(open(file_path, 'rb'), loc_db)

# cpu abstraction
machine = Machine(container.arch)

# init disassemble engine
mdis = machine.dis_engine(container.bin_stream, loc_db=loc_db)

# disassemble the function at address and get CFG
The code takes a binary as input (provided via `file_path`), initializes the disassembly engine and disassembles a function at `start_address`. Then, the resulting `asm_cfg` is a `DiGraph` instance holding the function’s control-flow graph. The entire script that re-implements the heuristic to detect control-flow flattening in Miasm can be found here.