Control flow graph reconstruction projects

Question

I'm looking for projects providing reconstructed Control Flow Graphs from binaries while supporting more than one platform (e.g. x86, x64, arm). For example, considering this short assembler program:

.global main
.intel_syntax noprefix

.extern getchar
.extern printf

.section .data
jmpTable:
    .long _stub0
    .long _stub1
    .long _stub2
fmt: .asciz "%x\n"


.section .text

main:
    call getchar
    mov dl, 4
    imul dl
    add eax, offset jmpTable
    jmp [eax]
    .long 3851
_stub0:
    mov eax, 0
    jmp end
    .long 3851
_stub1:
    mov eax, 1
    jmp end
    .long 3851
_stub2:
    mov eax, 2
    jmp end
    .long 3851
end:
    push eax
    push offset fmt
    call printf
    add esp, 8
    ret

Projects I've considered:

• IDA (best so far, extraction painful)
• BARF (naive, limited approach)
• Angr (breaks easily or computes forever)
• Radare2 (is there any api to export cfg data?)
• JakStab (limited to x86)

rather obvious choice, still, exporting a interprocedural CFG is still a pain. Also, although it is able to find all basic blocks of this example, it misses all indirect edges.

The projects should offer come kind of API to provide the cfg. I know solving this problem with static-analysis alone may be infeasible. I'm looking for a best-effort approach.

Answer 1

For now, the most efficient approaches in practice seems to follow the principle of symbolic execution. This technique, originally developed to automatically build-up a set of test cases based on a given source code, has been recently used in binary analysis to discover and (partially) recover the CFG of the analyzed binary program.

Most of the time, if you want to deal with several assembly languages, you need to use an intermediate representation for the programs. For now, there have been a lot of these generic models and none did really got the supremacy over the others. Yet, the most populars seems to be the intermediate representation of LLVM (many tools use it), the second most popular seems to be VEX, the intermediate representation used in Valgrind (as used in Angr). The one from QEMU or the language RREIL might also be an option, but they are less commonly used. But, most of the projects come with their own intermediate representation.

Then, what you need to build up a CFG-recovery program based on symbolic execution are the following modules:

• Loader: This module is in charge to take your binary program (it may be an executable or a library) and simulate the work of the native loader to build a realistic memory image of what you get after the loading process has been achieved.

• Decoder: This module is in charge of translating the native hexadecimal opcodes encountered while symbolically executing the program into some mnemonics or simplified instructions (the Capstone library is usually perfect for that).

• Lifter: It is in charge of lifting the result of the decoder into your own intermediate representation which hold the semantics of the execution path. It might be expressed in a different format (eg SMT-LIB fomula). It is a quite lengthy (and painful) piece of code to implement! So, be prepared to suffer while doing this.

• Symbolic execution engine: Usually based on an SMT-solver using the logic QF_AUFBV (Quantifier Free / Arrays / Uninterpreted Function / Bitvectors), the symbolic execution engine can really be a performance bottleneck if you code it naively because the recovery of the CFG will use it a lot. Here, having a good formula simplification (or slicing) module is really the key.

Apart from these modules, you might also improve your tools by adding more advanced analysis and start coding an abstract interpretation framework that can be added on the top of your intermediate representation, just to have chance to unveil some parts of the CFG that cannot be discovered just through the power of the SMT-solvers.

Also, performance is really the key to make your tools really usable. So, be able to capture the exact scope of a variable or the ability to detect a function or a module/object in the binary code helps a lot to reduce the size of the code you have to consider at once.

Now, I could give you a lot of pointers and articles about this topic, but I lack a bit of time. I might come back to finish writing an extensive list later on, but the general idea has been, hopefully, given above. Hope this might help you.

Answer 2

Extracting control flow graph in JSON with radare2:

$> python
import r2pipe
r2 = r2pipe.open("/bin/ls")
r2.cmd("aaa") # See radare.today/posts/analysis-by-default/
cfg = r2.cmdj("agj")

https://github.com/radare/radare2-bindings/tree/master/r2pipe/python

Answer 3

Angr (breaks easily or computes forever)

If you are still interested in finding a solution, you might want to give angr another try. You should hop on our slack channel (angr.slack.com, please get an invite from http://angr.io) so we can solve any CFG recovery issues together.

I believe angr gives you the best flexibility out of all solutions you have mentioned, without going into the symbolic execution hell.

Disclaimer: I'm a core angr developer.

Answer 4

I think Radare2's 'agj' command only extract function call graph, which is different from CFG(control flow graph where a node represent a basic block).