What is the algorithm used in Recursive Traversal disassembly?

Question

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

Answer 1

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:

1. 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 sweep
2. Conditional 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 algorithm
3. Unconditional 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.
4. 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).
5. 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.

Answer 2

Here's a very simplified overview of how IDA does it:

1. add to the analysis queue all known entrypoints, or addresses specified by the user
2. while queue not empty, pop the next address
3. ask processor module to disassemble the instruction
4. ask processor module to analyze the instruction
5. processor module adds code cross-references to all possible targets
   in the simplest case, it's the next instruction
   for conditional jumps and calls, it's the next instruction and the target
   for indirect jumps - unknown, unless it's a recognized switch pattern
6. put not-yet analyzed targets of all those cross-references into the queue
7. go to step 2

Of course, in reality things are more complex. To start with, there's not a single queue but several. From the SDK's auto.hpp:

//
//      This file contains functions that work with the autoanalyzer
//      queue. The autoanalyzer works when IDA is not busy processing
//      the user keystrokes.
//      The autoanalyzer has several queues. Each queue has its priority.
//      A queue contains addresses or address ranges.
//      The addresses are kept sorted by their values.
//      The analyzer will process all addresses from the first queue, then
//      switch to the second queue and so on.
//      There are no limitations on the size of the queues.
//      The analyzer stops when all queues are empty.
//
//      Also this file contains functions that deal with the IDA status
//      indicator and the autoanalysis indicator.
//      You may use these functions to change the indicator value.
//

// Names and priorities of the analyzer queues

typedef int atype_t;
const atype_t           // priority,  description
  AU_NONE = 00,         //    placeholder, not used
  AU_UNK  = 10,         //  0 convert to unexplored
  AU_CODE = 20,         //  1 convert to instruction
  AU_WEAK = 25,         //  2 convert to instruction (ida decision)
  AU_PROC = 30,         //  3 convert to procedure start
  AU_TAIL = 35,         //  4 add a procedure tail
  AU_TRSP = 38,         //  5 trace stack pointer (not used yet)
  AU_USED = 40,         //  6 reanalyze
  AU_TYPE = 50,         //  7 apply type information
  AU_LIBF = 60,         //  8 apply signature to address
  AU_LBF2 = 70,         //  9 the same, second pass
  AU_LBF3 = 80,         // 10 the same, third pass
  AU_CHLB = 90,         // 11 load signature file (file name is kept separately)
  AU_FINAL=200;         // 12 final pass