递归遍历反汇编中使用的算法是什么？

#1 楼

我已决定发布我的答案，而不是推翻Igor的答案，而是增加一个答案。我也不满意编辑他的帖子。我是该论坛的新手，不确定其他成员如何使用它。

我最近分享了一些理论，我想与大家分享。无论如何，我从IDA Pro Book（第一部分，第1节）中获得的关于IDA Pro的信息是，它使用Recursive Descent Disassembly，它基于控制流的概念。这种方法的关键要素是对每条指令的分析，以确定是否从任何其他位置引用了该指令。每个指令根据其与EIP的交互方式进行分类。主要有以下几种分类：




顺序流动指令。那些是将执行传递到下一条指令的指令，例如add，mov，push，pop等。这些指令通过线性扫描反汇编。
这些是对/错条件指令，例如je等。条件指令仅提供2个可能的执行分支。如果条件为False且未采用跳转，则反汇编程序继续进行线性扫描，并将跳转目标指令添加到递归代码列表中，以便稍后使用递归下降算法进行反汇编。


说明。如果在运行时计算跳转目标，则这些指令可能会对递归下降反汇编程序造成特殊问题。无条件分支不遵循线性流。如果可能，反汇编程序将尝试添加无条件跳转的目标以进行进一步分析。如果未确定目标，则特定分支将不会进行拆卸。

功能调用说明。调用指令通常被视为无条件分支指令，期望函数完成后，执行将返回到调用后的指令。调用指令的目标地址地址排队等待延迟反汇编，而调用之后的指令则作为线性扫描处理。但是，并非总是可以确定呼叫目标（例如call eax）。

返回指令返回指令不向反汇编程序提供任何有关下一步执行的信息。反汇编程序无法从堆栈顶部弹出返回地址。所有这些使反汇编程序停止。此时，反汇编程序将转到保存的递延目标列表，然后继续执行。这就是为什么它称为递归的原因。
总而言之，我想引用IDA Pro书：


递归的主要优点之一下降算法是其区分代码和数据的卓越能力。作为基于控制流的算法，将数据值错误地反汇编为代码的可能性要小得多。递归下降的主要缺点是无法遵循间接代码路径，例如跳转或调用，它们使用指针表来查找目标地址。但是，通过添加一些启发式方法来识别代码指针，递归下降反汇编程序可以提供非常完整的代码覆盖范围以及对代码和数据的出色识别。

#2 楼

这是IDA的工作方式的非常简化的概述：


将所有已知的入口点或用户指定的地址添加到分析队列中，而队列不为空时，弹出下一个地址
询问处理器模块以分解指令
询问处理器模块以分析指令
处理器模块为所有可能的目标添加代码交叉引用
在最简单的情况下，这是下一个指令
用于条件跳转和调用，是下一条指令，目标
用于间接跳转-未知，除非它是公认的切换模式
尚未对所有这些交叉引用的目标进行分析进入队列
进入第2步

当然，实际上情况要复杂得多。首先，没有一个队列，而是几个。通过SDK的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