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


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.

|improve this answer|||||

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.