# Building a control flow graph from machine code

I want to write my own soft, that can disassemble code, and turn it into conrol flow graph. Now i know the basics of graph theory, but i don't get where i should start, do i need to basically keep the tracing of all call,jmp,ret,jxx instructions to detect individual blocks of instructions to make blocks of code into graph nodes? Can someone give me kick where to start?

• did you try at least with this approach and stumbled upon some issues? I think with such formulated question this is too broad – Paweł Łukasik Oct 16 '17 at 2:28

This could go serveral ways depending on whatever you want to use third party software. For example, you could use the stream-disassembler diStorm to implement linear disassembly. When you have to keep track of all branch targets and progress then one after another starting at the entry point.

If you want to do this cross-platform, you could even pitch in an intermediate language like VEX or REIL.

Remember though, that finding the next branch to disassemble isn't always easy: You will encounter problems with opaque predicates and indirect branches... you could implement and evaluate data-flow analysis at this point, but this would go to far.

Some concepts:

Linear disassembly: Start at the given offset and go. You can get the start of the next address from the length of the instruction before.

Recursive disassembly: Start linear disassembly at each branch target starting from the entry point.

Heuristic disassembly: This term often describes everything improving on the recursive disassembly for example by detecting jump tables, opque prediates or speculative disassembly of code sections to discover more code.

Good luck

The techniques already described by the others are quite well known and, unfortunately incorrect in many cases. The current state-of-the-art in matter of disassembly is using what we call 'symbolic execution'.

Basically, you will need to collect the semantics of each assembly instruction and explore each branch of the possible execution of the program and, when you encounter a choice (an if statement), you will ask the formula built from the stacking of all these instruction what are the conditions to get a true and a false. It will give you the feasible paths and the associated inputs you need to feed the program with to reach the true branch or the false branch of this test.

This technique is quite painful to set up because you need to grab the entire semantics of each instruction of the assembly you are considering. But, it turns out that it is quite trustable and quite efficient on average programs.

Here are a few links:

• Thanks for answer and resources, maybe I can continue my research if it is feasible to use for my purpose. – de6f Oct 17 '17 at 10:11
• Symbolic execution was what i was referring to as dataflow analysis. Honestly, non of these projects is realiable at all (if you consider real world software). There is a sound reason, why this techniques are not used in state-of-the-art analysis software – Nordwald Oct 17 '17 at 10:13
• @Norwald: First, dataflow analysis and symbolic execution are two very different things. Mostly because dataflow analysis accept to abstract some semantics away in order to terminate (this is close to abstract interpretation). Which is absolutely not the case in symbolic execution. Now, about the fact that none of the projects are reliable... your are right. But, the method is not really in cause for that, it is because either implementation issues or the fact that they do not symbolically cover all the environment (e.g. floating point ops). But, this method is very difficult to achieve. – perror Oct 17 '17 at 10:23

Norwald's answer better at explaining default disassembly strategies. But, I want to share my experience on my discontinued project about a metamorphic virus which disassembles binary code and finds ROP chains to make the same virus semantically.

You can use Capstone Framework to disassemble and GraphViz for visualization.

For semantic analysis strategy, you can check code backward after disassembled all .text section and find branch instructions. After that, you can trace branching with tracing data associated with the branch instruction. For example:

I hope it works for you.