8

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.

  • What part of extracting the information from IDA is particularly painful? to me it looks like writing an IDAPython script for that is rather easy. Then, you could structure your own interface if IDA's raw API is cumbersome for you. – NirIzr Sep 2 '16 at 18:21
  • IDA exposes lots of internal structures and has a own understanding of controll flow graphs. Main critique is the focus on functions and the treatment (and labeling) of edges. – Nordwald Sep 5 '16 at 5:38
  • McSema and CMU BAP seem promising. – viv May 7 '18 at 2:40
6

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 assembly found while symbolically executing the program into your own intermediate representation. 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 three 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.

  • Thanks for your explanation. I hoped this has been done before in a more reliable manner than the hacky implementation in angr. Do you know any other projects offering this kind of functionality? – Nordwald Sep 2 '16 at 7:36
  • 1
    Some time ago, I wrote this list of tools that perform symbolic execution (or that can be used as a module helping to do it). Maybe you can find some hints there. – perror Sep 2 '16 at 11:57
8

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

  • doesn't radare have some kind of 'real' api? – Nordwald Sep 30 '16 at 6:22
  • 2
    It does and not just one: github.com/radare/radare2-bindings. r2pipe is just a wrapper for r_core_cmd(), it spawns or connects to an r2 session and runs commands and returns the output. As long as many commands have json output you can use cmdj() that will return a native object for the langauge you use. from my tests, this is way faster than using the swig bindings because the data serialization and ffi are really expensive. and json parsers are WAY faster. r2pipe requires no maintainance, and it will help you in most of the usecases you want. – Maijin Oct 1 '16 at 12:49
1

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.