Disassembling binary code is a quite difficult topic, but for now only two (naive) algorithms seems to be broadly used in the tools.Linear Sweep: A basic algorithm taking all the section marked as code and disassembling it by reading the instructions one after each other.Recursive Traversal: Refine the linear sweep by remembering when (and where) a call has been taken and returning to the last call when encountering a ret.Yet, the description of these algorithms are quite vague. In real-life tools, they have been a bit refined to improve the accuracy of the disassembling. For example, objdump perform a linear sweep but will start from all the symbols (and not only the beginning of the sections marked as code.So, can somebody give a more realistic description of the recursive traversal algorithm (e.g. as it is coded in IDAPro) ?
What is the algorithm used in Recursive Traversal disassembly?
disassemblers
I have decided to post my answer not to overthrow Igor's answer, but to have an addition to it. I was not comfortable with editing his post either. I am pretty new to the forum and not sure how it is taken by other members. There is a little theory I have recently learned, which I would like to share. Anyways, what I have taken in about IDA Pro from The IDA Pro Book (Part I, Section 1) is that it uses Recursive Descent Disassembly, which is based on the concept of control flow. The key element to this approach is the analysis of each instruction in order to determine if it is referenced from any other location. Each instruction is classified according to how it interacts with EIP. There are several main classifications:Sequential Flow Instuctions. Those are instruction that pass execution to the next instruction to follow such as add, mov, push, pop, etc. Those instructions are disassembled with linear sweepConditional Branching Instructions. Those are True/False conditional instructions such as je and such. Conditional instructions only offer 2 possible branches of execution. If condition is False and jump is not taken disassembler proceeds with linear sweep, and adds jump target instruction to a list of deferred code to be disassembled at later time using recursive descent algorithmUnconditional Branching Instructions. Those instruction can cause particular problems for recursive descent disassemblers in case the jump target is calculated at runtime. Unconditional branches do not follow linear flow. If possible, disassembler will attempt to add the target of the unconditional jump for further analysis. If target is not determined, there is going to be no disassembly for the particular branch.Function Call Instructions. Call instructions are mostly treated as Unconditional Branching Instructions with expectation that execution would return to the instruction following the call as soon as function completes. The target address address of the call instruction is queued for deferred disassembly, and the instruction following the call is processed as linear sweep. However, it is not always possible to determine target of the call (e.g. call eax). Return Instructions Return instructions do not offer any information to disassembler about what to execute next. Disassemblers cannot pop the return address from the top of the stack. All of that brings disassembler to stop. At this point disassembler turns to the saved list of deferred targets to follow next. That is exactly why it is called recursive.To summarize, I would like to quote The IDA Pro Book:One of the principle advantages of the recursive descent algorithm is its superior ability to distinguish code from data. As a control flow-based algorithm, it is much less likely to incorrectly disassemble data values as code. The main disadvantage of recursive descent is the inability to follow indirect code paths, such as jumps or calls, which utilize tables of pointers to look up a target address. However, with the addition of some heuristics to identify pointers to code, recursive descent disassemblers can provide very complete code coverage and excellent recognition of code versus data.