How to identify functions in a stripped binary on x86 32bit?

Question

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..?

Answer 1

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.

Answer 2

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.