Question

在概念上，一个反编译器的构成与编译器是相似的，通过一系列阶段把源机器程序从一个表示法转换成另一个表示法。反编译器的典型阶段见图 1-10 所示。这些阶段反映了反编译器的逻辑组织。实际上有些阶段可以结合，见第 1.4 节。

请注意的一点是，在反编译器中没有词汇分析阶段或扫描阶段。这是因为机器语言太简单：所有的语言符号（记号) 都用一些字节或一字节的位来表示。任给一字节，不可能确定该字节是不是一个新记号的开始；例如，字节 50 可能表示一条 push ax 指令操作码，也可能表示一个立即常数或者一个数据单元的偏移量。

图 1-10: 反编译器的阶段

1.3.1 句法分析

语法分析器或句法分析程序把源程序的字节组织成源机器语言的语法短语（或语句)。这些短语用一个语法分析树表示。表达式 sub cx, 50 在语义上等价于 cx := cx- 50。后一种表达可以用如图 1-11 所示的一个语法分析树表现。这个表达式有两个短语：cx-50 和 cx:=<exp>。这些短语形成一个层次结构，但是由于机器语言的单纯天性，因此总是最多两层。

图 1-11: cx := cx- 50 语法分析树

句法分析程序的主要问题是确定哪些是数据和哪些是指令。例如，由于冯·诺依曼机器的体系结构，一个 case 表可以放在代码段，而反编译器并不知道这个表是数据而非指令。象这样的情况，我们不能想当然地认为下一字节总是一条指令从而循序地分析指令。确定指令的正确顺序需要使用机器依赖的启发式。句法分析在第 4 章讨论。

1.3.2 语义分析

语义分析阶段检查源程序一组指令的语义含义，收集类型信息并且向整个子程序传递这个类型。对于任何一个编译器生成的二进制程序，只要程序能够运行，其机器语言语义一定是正确的。一般来说，编译器不会生成错误的代码导致二进制程序不能运行。因此，在源程序中不会有语义错误，除非句法分析程序对某一条指令做了不正确的分析或者把指令当作数据分析。

为了检查一组指令的语义含义，就要寻找成语。图 1-4 的成语可以被转换成语义等价的指令如：第一例 ax 乘以 4，和第二例 long 变量的加法。在那个特定的子程序中，[bp-2]:[bp-4]表示一个 long 变量，而 dx:ax 在这个子程序中临时保存一个 long 变量。dx:ax 这两个寄存器不必在整个子程序中都被当作一个 long 寄存器使用，只有在需要的时候才这样。

通过短语表达式新发现的类型被类型传播到整个图。例如，在图 1-4 中，子程序的两个栈存储单元已知作为一个 long 变量使用。因此，无论这两个单元在哪里被独立地使用或定义都必须被转换成一个 long 变量的使用或定义。如果下面两个语句是该子程序代码的一部分

asgn [bp-2], 0 asgn [bp-4], 14h

那么，[bp-2]和[bp-4]的 long 类型传递会将这两个语句合并成一个语句来表示那些标识符为 long 变量，如下

asgn [bp-2]:[bp-4 ], 14h

最后，语义错误通常不是由编译器生成代码的时候造成的，但是当可执行程序在一个更先进的体系结构上运行的时候会发现语义错误。例如，假设我们要反编译 i80286 体系结构的二进制程序。新的 i80386 和 i80486 体系结构是以这个 i80286 体系结构为基础，而且它们的二进制程序储存方式是相同的。这些新的体系结构在机器语言方面不同的是，使用更多的寄存器和指令。如果给我们一条指令

add ebx, 20

寄存器识别符 ebx 是一个 32 位寄存器，这在旧的体系结构是没有的。因此，尽管该指令在语法上是正确的，但是对于我们正在反编译的机器语言而言它在语义上是错误的，因而就要报告一个错误。第 4 章在这方面做了一些分析。

1.3.3 中间代码生成

反编译器分析程序需要一个中间表示法来明确地表示源程序。它必须容易从源程序中生成，而且还必须适合用来表示目标语言。第 1.3.1 节举例的语义等价表示法用来实现这个目标是很理想的：它是一个三地址代码表示法，一条指令最多能有三个操作元。这些操作元全部都是机器语言的标识符，但是能够容易地把它展开成表达式以表现高级语言表达式 (亦即，一个标识符就是一个表达式)。这样，使用一个三地址的表示法，则一条指令最多能有三个表达式。第 4 章描述反编译器使用的中间代码。

1.3.4 控制流向图生成

源程序中每个子程序的控制流向图也是反编译器分析程序所必需的。这个表示法适合用于确定程序里的高级控制结构。它也用于清除由于机器语言的条件跳转有偏移量限制因而由编译器产生的中间跳转(intermediate jump)。在下面的代码中

	...	; other code
	jne x	; x <= maximum offset allowed for jne
	...	; other code
x:	jmp y	; intermediate jump
	...	; other code
y:	...	; final target address

标签 x 是条件跳转 jne x 的目标地址。这条指令受到该机器体系结构最大允许偏移量的限制，因此不能够只用一条指令执行到 y 的一个条件跳转；只得使用一条中间跳转指令。在控制流向图中，到 x 的条件跳转直接使用到 y 的最后目标跳转替换。

1.3.5 数据流分析

数据流分析阶段试图改善中间代码，以便能够得到高级语言表达式。在这个分析期间，临时寄存器的使用和条件标志被清除掉，因为在高级语言里面没有这些概念。如下一系列的中间语言指令

asgn ax, [bp-0Eh] asgn bx, [bp-0Ch] asgn bx, bx * 2 asgn ax, ax + bx asgn [bp-0Eh], ax

最后的输出应该是一个高级表达式的形式

asgn [bp-0Eh], [bp-0Eh] + [bp-0Ch] * 2

第一组指令使用寄存器、栈变量和常数；表达式用标识符组成，而且表达式树最多 2 层次。在分析之后，最后输出的指令使用栈变量标识符，[bp-0Eh]、[bp-0Ch]、和一个 3 层的表达式树，[bp-0Eh] := [bp-0Eh] + [bp-0Ch] * 2。被机器语言用来计算这个高级表达式的临时寄存器，ax 和 bx，连同对这些寄存器的读取和写入，都已经被清除掉。第 5 章给出一个算法实现这个分析，以及清除其它中间语言指令，比如 push 和 pop。

1.3.6 控制流分析

控制流分析器阶段试图将程序每个子程序的控制流向图结构化成一个一般化的高级语言构造集合。这个一般化的结构集必须包含大多数语言适用的控制指令；比如控制的循环和条件转移。不应允许使用语言特定的构造。图 1-12 展示了两个控制流向图样例：一个 if..then..else 和一个 while()。第 6 章给出把任意的控制流向图结构化的算法。

图 1-12: 一般化的构造

1.3.7 代码生成

反编译器的最后阶段是在每个子程序的中间代码和控制流向图的基础上生成目标高级语言代码。为所有的局部栈、参数和寄存器变量标识符选择变量名称。也为在程序中出现的各个例程指定各自的子程序名称。控制结构和中间指令被翻译成高级语言语句。

以第 1.3.5 节的例子来说，局部栈标识符[bp-0Eh]和[bp-0Ch]分别被赋予任意的名称 loc2 和 loc1，然后那条指令被翻译成 C 语言如下

loc2 = loc2 + (loc1 * 2);

代码生成在第 7 章讨论。