反汇编算法

线性扫描（ linear sweep）和递归下降（ recursive descent）是两种最主要的反汇编算法。

线性扫描反汇编

线性扫描反汇编算法采用一种非常简单的方法来确定需要反汇编的指令的位置：一条指令结束、另一条指令开始的地方。

因此，确定起始位置最为困难。常用的解决办法是，假设程序中标注为代码（通常由程序文件的头部指定）的节所包含的全部是机器语言指令。反汇编从一个代码段的第一个字节开始，以线性模式扫描整个代码段，逐条反汇编每条指令，直到完成整个代码段。这种算法并不会通过识别分支等非线性指令来了解程序的控制流。

进行反汇编时，可以维护一个指针来标注当前正在反汇编的指令的起始位置。在反汇编过程中，每一条指令的长度都被计算出来，并用来确定下一条将要反汇编的指令的位置。为此，对由长度固定的指令构成的指令集（如 MIPS）进行反汇编有时会更加容易，因为这时可轻松定位随后的指令。

线性扫描算法的主要优点，在于它能够完全覆盖程序的所有代码段。线性扫描方法的一个主要缺点，是它没有考虑到代码中可能混有数据。

GNU 调试器（ gdb）、微软公司的 WinDbg 调试器和 objdump 实用工具的反汇编引擎均采用线性扫描算法。

递归下降反汇编

递归下降采用另外一种不同的方法来定位指令。递归下降算法强调控制流的概念。控制流根据一条指令是否被另一条指令引用来决定是否对其进行反汇编。

  1. 顺序流指令

**顺序流指令将执行权传递给紧随其后的下一条指令。**顺序流指令的例子包括简单算术指令，如 add；寄存器与内存之间的传输指令，如 mov；栈操作指令，如 push 和 pop。这些指令的反汇编过程以线性扫描方式进行。

  1. 条件分支指令

**条件分支指令（如 x86 jnz）提供两条可能的执行路径。**如果条件为真，则执行分支，并且必须修改指令指针，使其指向分支的目标。但是，如果条件为假，则继续以线性模式执行指令，并使用线性扫描方法反汇编下一条指令。因为不可能在静态环境中确定条件测试的结果，递归下降算法会反汇编上述两条路径。同时，它将分支目标指令的地址添加到稍后才进行反汇编的地址列表中，从而推迟分支目标指令的反汇编过程。

  1. 无条件分支指令

**无条件分支并不遵循线性流模式，因此，它由递归下降算法以不同的方式处理。**与顺序流指令一样，执行权只能传递给一条指令，但那条指令不需要紧接在分支指令后面。递归下降反汇编器将尝试确定无条件跳转的目标，并将目标地址添加到要反汇编的地址列表中。遗憾的是，某些无条件分支可能会给递归下降反汇编器造成麻烦。如果跳转指令的目标取决于一个运行时值，这时使用静态分析就无法确定跳转目标。 x86 的 jmp eax 指令就证实了这个问题。只有程序确实正在运行时， eax 寄存器中才会包含一个值。由于寄存器在静态分析过程中不包含任何值，因此无法确定跳转指令的目标，也就无法确定该从什么地方继续反汇编过程。

  1. 函数调用指令

函数调用指令的运行方式与无条件跳转指令非常相似（包括反汇编器无法确定 call eax 等指令的目标），唯一的不同在于，一旦函数完成，执行权将返回给紧跟在调用指令后面的指令。在这方面，它们与条件分支指令类似，因为它们都生成两条执行路径。调用指令的目标地址被添加到推迟进行反汇编的地址列表中，而紧跟在调用后面的指令则以类似于线性扫描的方式进行反汇编。

  1. 返回指令

有时，递归下降算法访问了所有的路径。而且，函数返回指令（如 x86 ret）没有提供接下来将要执行的指令的信息。这时，如果程序确实正在运行，则可以从运行时栈顶部获得一个地址，并从这个地址开始恢复执行指令。但是，反汇编器并不具备访问栈的能力，因此反汇编过程会突然终止。这时，递归下降反汇编器会转而处理前面搁置在一旁的延迟反汇编地址列表。反汇编器从这个列表中取出一个地址，并从这个地址开始继续反汇编过程。递归下降反汇编算法正是因此而得名。

==递归下降算法的一个主要优点在于，它具有区分代码与数据的强大能力。==作为一种基于控制流的算法，它很少会在反汇编过程中错误地将数据值作为代码处理。递归下降算法的主要缺点在于，它无法处理间接代码路径，如利用指针表来查找目标地址的跳转或调用。然而，通过采用一些用于识别指向代码的指针的启发（ heuristics）式方法，递归下降反汇编器能够提供所有代码，并清楚地区分代码与数据。