# What is the algorithm used in Recursive Traversal disassembly?

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

• IIRC in recursive traversal the disassembler tries to follow all control transfer instructions -- i.e., identify and continue disassembly at the various possible control flow targets of the instruction -- not just `call` instructions. Jun 26 '13 at 16:22
• Lida which is based on Bastard's libdisasm, diStorm3 and beaengine are some open source disassembly engines that use recursive disassembly.Also a paper: Obfuscation of executable code to improve resistance to static disassembly by Cullen and Saumya gives a rough algorithm for recursive sweep disassembly.
– viv
Jun 27 '13 at 11:53

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.

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.
//      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
``````
• Am I wrong if I say that you are using a work-list approach of the algorithm. Like in data-flow analysis ? (It is quite nice indeed) Jun 26 '13 at 17:04