Control flow analysis and graphing27 Jul 2016, by mrexodia
Today’s post will be about control flow analysis and graphing, so read on if you are interested!
This blog is still looking for writers! See here for more information…
At the moment x64dbg is only capable of showing disassembly in a linear fashion. Control flow can be somewhat inferred from jump arrows, but this can be a tedious and overwhelming process. This is one of the reasons we are interested in representing disassembly as a control flow graph. Another good reason is that x86 instructions can overlap and sometimes linear disassembly cannot show the full picture.
The first thing to look at is analysis of a function. We represent the function as a directed graph. The graph nodes are so-called basic blocks and the graph’s edges (arrows) are jumps in the disassembly. The function we will be looking at is shown below:
In this case a basic block is a block of instructions, that do not alter the control flow within the current function. We (falsely) assume that
call instructions always return to the instruction after said
call instruction so the control flow of the block is not interrupted. Additionally a basic block ends at a
ret instruction (since that marks the end of the current function).
Since the function is (implicitly) represented as a graph we can use breadth first search (BFS) to traverse it. The algorithm implemented here combines the BFS with building the graph, which makes it quite compact and easy to understand (pseudocode):
analyze(entryPoint): graph = new Graph(entryPoint) queue = new Queue() visited = new Set() # Start at the entry point queue.enqueue(graph.entryPoint) # Traverse the graph while not queue.empty(): # Check if we already visited this node start = queue.dequeue() if start == 0 || visited.contains(start): continue visited.insert(start) # Create a new node node = new Node() node.start = node.end = start # Disassemble the current basic block while true: instr = disassemble(node.end) if isBranch(instr) || isRet(instr): # Enqueue queue.enqueue(brtrue(instr)) queue.enqueue(brfalse(instr)) graph.AddNode(node) break node.end += instr.size
brfalse return the addresses of the destination blocks or zero. After running this analysis on the function the result looks something like this:
At the moment analysis is not working correctly. The analysis will have overlapping blocks if there are branches inside an existing block. It looks something like this (function is totally made up, don’t read too much into it):
The first block should be split and a second pass easily solves this problem:
for node in nodes: addr = node.start size = disassemble(addr).size if graph.contains(addr + size): node.end = addr node.brtrue = addr + size node.brfalse = 0 break addr += size
This splits the block correctly and inserts an extra edge between the nodes:
Now there are some remaining problems, like overlapping instructions, but those are fine the way it is in my opinion:
You can find the full code here if you are interested in the details.
Now the next part was showing the function graph in the GUI, there was quite an effort before doing this using OGDF, but this created various problems. Recently someone mentioned the Binary Ninja Prototype to me, so I decided to port that instead.
After about 7 hours of struggling with porting Python to C++, I ported the code and people seem to like the results :)
The details of the layout algorithm are beyond me and if you have any fixes, feel free to create a pull request!