5

I am trying to generate a coarse-grained Call Graph based on some assembly code disassembled from binary on x86 32 bit platform.

It is very hard to generate a precise Call Graph based on asm code, thinking of various indirect control flow transfer, so right now I only consider direct control flow transfer.

So firstly I am trying to identify functions (begin and end addresses) in the disassembled assembly code from a stripped binary on x86, 32bit.

Right now, my plan is somehow like this:

As for the begin addresses, I might conservatively consider any assembly code looks like this

    push %ebp

indicates the beginning address of a function.

and also, I might scan the whole problem, identifying all the call instruction with the destination, the consider these function call's destinations as all the function begin address

The problems are:

  1. some of the functions defined in a binary might never be called.

  2. some of the call has been optimised as jump by compiler (thinking of tail recursive call)

As for the end address, things become more tricky because multiple ret could exist in one single function...

So I am thinking that I might conservatively consider the range between any nearest function begin addresses, as one function..

Am I right? Is there any better solution..?

2

2 Answers 2

8

Reversing the call graph or the control flow graph of a binary isn't for the faint of heart, and is still a hot topic for researchers.

Your approach looks promising; but, unfortunately for you, you'll stumble upon lots of barriers.

One, following call instructions is most likely to give great results, if analyzing statically the binary file. The only problem is that, sometimes, you'll have indirect calls/jumps. Meaning, the operand will be a register containing the target address. This will occur very often if the target binary file original source code was written in C++ (virtual functions) for example. One way to obtain the target address in this case is to emulate or run the chunk of code that computes it. Another is to assess its value heuristically (heuristics are hell).

Two, you can run your binary file with multiple input data sets and dynamically extract the call graphs (this can be performed through instrumentation). You can then cross reference all the obtained call graphs ...

Three, I would recommend a basic-block centric approach rather than a functional one. Mainly, because a function is a basic-block in itself and you'll have more luck finding functions this way than trying to match patterns which can change from one compiler to another, or from one version of a compiler to another.

The following publications are extremely interesting : [1], [2], [3], and also I would encourage you to check DynInst and callgrind if you want to learn more about the subject.

1
1

Generally, the solutions to this problem can be classified to:

  • Pattern matching heuristics. Just like what you are proposing. For example, searching for pushes in the binary can provide a (rather) rough approximation of function starts. Things are more difficult if you want to locate function ends though.

  • Machine learning. Pattern matching can be automated using machine learning. There are several proposals in the literature like [1], [2], and [3]. All of which attempt to learn byte-level features of function starts and ends. However, modern compiler optimizations make it challenging for such approaches to generalize to binaries beyond the training set.

  • CFG-based techniques. This is the most promising approach based on [4] (disclosure: first author here) and concurrently [5]. Basically, it proceeds with (1) direct call target analysis, (2) CFG traversal to locate function ends, and (3) tail-call target analysis.

  • Call frame information (CFI) records. Before doing anything fancy, checkout the CFI records in the .eh_frame section. There is a good chance that functions are defined there already. In order to dump CFI records, you can use something like readelf --debug-dump=frames /bin/ls.

I've recently revisited the problem of function identification in this blog post where I provide more details.

1
  • Cool. Thank you for summarizing the problem in a nice way. It's 2020 now and go solo to publish research papers on "identifying function boundaries" might not be as promising as when I posted this question five years ago. But yes, it's always nice to see binary hacking folks constantly explore and publish papers in this field. May 27, 2020 at 8:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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