11

I'm attempting to build a control-flow graph of the assembly results that are returned via a call to objdump -d . Currently the best method I've come up with is to put each line of the result into a linked list, and separate out the memory address, opcode, and operands for each line. I'm separating them out by relying on the regular nature of objdump results (the memory address is from character 2 to character 7 in the string that represents each line) .

Once this is done I start the actual CFG instruction. Each node in the CFG holds a starting and ending memory address, a pointer to the previous basic block, and pointers to any child basic blocks. I'm then going through the objdump results and comparing the opcode against an array of all control-flow opcodes in x86_64. If the opcode is a control-flow one, I record the address as the end of the basic block, and depending on the opcode either add two child pointers (conditional opcode) or one (call or return ) .

I'm in the process of implementing this in C, and it seems like it will work but feels very tenuous. Does anyone have any suggestions, or anything that I'm not taking into account?

Thanks for taking the time to read this!

edit:

The idea is to use it to compare stack traces of system calls generated by DynamoRIO against the expected CFG for a target binary, I'm hoping that building it like this will facilitate that. I haven't re-used what's available because A) I hadn't really though about it and B) I need to get the graph into a usable data structure so I can do path comparisons. I'm going to take a look at some of the utilities on the page you lined to, thanks for pointing me in the right direction. Thanks for your comments, I really appreciate it!

Jonathan Leffler
  • 730,956
  • 141
  • 904
  • 1,278
Sam
  • 278
  • 3
  • 9
  • Sounds like a plausible overall approach. You might want to think about what to do when you see an indirect call. Also, you say that return instructions will have one successor -- what would that be, exactly, for a function with multiple callers? Calls and returns are often not included in CFGs (such as LLVM IR). The "right" answer depends on what you plan to do with the CFG after you've built it. – Ben Karel Nov 25 '10 at 05:01
  • Interesting approach. There are several tools (See http://en.wikipedia.org/wiki/Call_graph) which can be used to create CFGs from source code. Is there a specific reason why you want to take this approach instead of reusing what's available? – Sudhanshu Nov 25 '10 at 07:16
  • how are you resolving function pointers? I am also writing similar kind of program but still wondering how i will resolve function pointers? – prap19 Dec 04 '10 at 23:41
  • Essentially, I'm not. Right now I'm treating function pointers as a 'black box' basic block, and starting the next basic block on the next address after the function pointer call, where the function pointer call will return to. It's not ideal, but I haven't come up with a way to find the register address. – Sam Dec 11 '10 at 13:43

3 Answers3

5

You should use an IL that was designed for program analysis. There are a few.

The DynInst project (dyninst.org) has a lifter that can translate from ELF binaries into CFGs for functions/programs (or it did the last time I looked). DynInst is written in C++.

BinNavi uses the ouput from IDA (the Interactive Disassembler) to build an IL out of control flow graphs that IDA identifies. I would also recommend a copy of IDA, it will let you spot check CFGs visually. Once you have a program in BinNavi you can get its IL representation of a function/CFG.

Function pointers are just the start of your troubles for statically identifying the control flow graph. Jump tables (the kinds generated for switch case statements in certain cases, by hand in others) throw a wrench in as well. Every code analysis framework I know of deals with those in a very heuristics-heavy approach. Then you have exceptions and exception handling, and also self-modifying code.

Good luck! You're getting a lot of information out of the DynamoRIO trace already, I suggest you utilize as much information as you can from that trace...

munin
  • 503
  • 4
  • 8
2

I found your question since I was interested in looking for the same thing. I found nothing and wrote a simple python script for this and threw it on github: https://github.com/zestrada/playground/blob/master/objdump_cfg/objdump_to_cfg.py

Note that I have some heuristics to deal with functions that never return, the gcc stack protector on 32bit x86, etc... You may or may not want such things.

I treat indirect calls similar to how you do (basically have a node in the graph that is a source when returning from an indirect).

Hopefully this is helpful for anyone looking to do similar analysis with similar restrictions.

zje
  • 3,824
  • 4
  • 25
  • 31
1

I was also facing a similar issue in the past and wrote asm2cfg tool for this purpose: https://github.com/Kazhuu/asm2cfg. Tool has support for GDB disassembly and objdump inputs and spits out CFG as a dot or pdf.

Hopefully someone finds this helpful!

Kazooie
  • 525
  • 1
  • 4
  • 15