I'm writing a tool and I need to generate the callgraph for assembly instructions. But I do not know how to exactly generate call graph from assembly instruction. Do you have any idea? To clarify, I run a binary sample in sandbox environment and extract its trace in assembly language. So now I want to generate call graph for that? I know it is possible to generate callgraph by static analysis using IDA pro but my problem is that how can I generate call graph from Dynamic analysis?
With a trace this is very easy. Follow the trace sequentially and:
- For the very 1st instruction, create a function object at the address of that very 1st instruction.
- For each call statement or push + ret, create a function object and add an edge from the current function to this function object.
- For each new call statement, create or reuse a function object and add an edge from the current function to the new or already known function object.
- After a RET* instruction, change the current function to the previous one. Use a stack and push/pop elements to/from it.
The only corner case I can see from what you want is if you have library functions and the trace doesn't contain the corresponding code or syscalls. But is as easy as not changing the current function for such calls.
After following all these steps, you will have a graph structure with the call graph.
NOTE: The function object can be, simply, an address.
One way to distinguish between calls is to parse the process's address space and establish memory ranges for various libraries. Thus when parsing the trace, you should be able to tell what's a "local" call vs a call into a lib. I'd also parse the various libraries export tables, to establish the various entry points and make the trace analysis a bit easier. You, of course would need to track dynamic loads etc. Dealing with calls in the kernel should also be trivial to distinguish from user-level. Of course, this is assuming, you have the memory information when you're analyzing the trace. I don't know if you're analyzing a Windows or Linux trace, but here's a good article for finding and parsing the export table on Windows
If you're tracing the entire process from create to finish, you should also be able to determine at the very least load addresses (and probably size) for various DLLs. That should give you a good idea about the memory layout, if you don't have external memory information as mentioned above. That should be enough to distinguish a local call vs library calls. If you're not interested in which library it's calling into, it's even easier. You know the address that the image loaded at, so given the size of the binary, and knowledge of the loader, you can calculate(or estimate closely) the size of the loaded executable. Anything outside of this range, you can consider "external".