当前位置: 首页 >> 程序设计 >> 逆向编译技术

逆向编译技术

作者：来源：zz 发表时间：2007-04-16 浏览次数：字号：大 中 小

1.3 反编译器的阶段
从概念上，一个反编译器的构成与编译器是相似的，通过一序列阶段将源机器程序从一个表示法转换成另一个表示法。反编译器典型的几个阶段见表1-10所示。这些阶段反映了反编译器的逻辑组织。实践中会把一些阶段组合在一起，见第1.4节。
请注意的一点是，在反编译器中没有语句分析阶段或扫描阶段。这是因为机器语言太简单：所有的记号都用一些字节或一字节的位来表示。任给一字节，不可能确定该字节是不是一个新记号的开始；例如，字节50可能表示一条push ax指令操作码，也可能表示一个立即常数或者一个数据单元的偏移量。

    二进制程序
_______|________
|   语法分析器   |
|       |        |
|   语义分析器   |
|       |        |
| 中间代码生成器 |
|       |        |
| 控制流图生成器 |
|       |        |
|  数据流分析器  |
|       |        |
|  控制流分析器  |
|       |        |
|   代码生成器   |
|_______|________|
        |
  高级语言程序

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

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

    assignment statement
    |         |        |
identifier   :=    expression
    |              |     |  |
   cx        identifier  -  constant
                  |             |
                 cx            50

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

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

1.3.2 语义分析
语义分析阶段检查源程序一组指令的语义含义，收集类型信息并且向整个子程序传递这个类型。对于任何一个编译器生成的二进制程序，只要程序能运行，其机器语言的语义一定是正确的。没见过哪一个二进制程序是因为编译器生成代码的错误而不能运行。因此，除非语法分析器对某一条指令做了不正确的分析或者把指令当作数据分析，否则，在源程序中是不会有语义错误的。
为了检查一组指令的语义含义，则要寻找成语。表1-4的成语可以被转换成语义等价的指令如：第一例ax乘以4，和第二例long变量的加法。在那个特定的子程序中，[bp-2]:[bp-4]表示一个long变量，而dx:ax在这个子程序中临时持有一个long变量。后者这些寄存器不必在整个子程序中都被当作一个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 控制流图生成
源程序中每一个子程序的控制流图也是为反编译器分析程序所必需的。这个表示法适合用来确定在程序中的高级控制结构。它也被用来清除掉由于机器语言的条件跳转有偏移量限制因而被编译器产生的中间跳转。在下面的代码中

  ...   ; 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章给出一个构成任意控制流图的算法。

if..then..else

while()

表 1-12: 通有构造

1.3.7 代码生成
反编译器的最后阶段是在控制流图和每一个子程序中间代码的基础上生成目标高级语言代码。为所有的局部栈、参数和寄存器变量标识符选择变量名称。也为在程序中出现的各个例程指定各自的子程序名称。控制结构和中间指令被翻译成高级语言语句。
以第1.3.5节的例子来说，局部栈标识符 [bp-0Eh] 和 [bp-0Ch] 分别被赋予任意的名称loc2和loc1，而那条指令被翻译成C语言如下

loc2 = loc2 + (loc1 * 2);

代码生成在第7章讨论。

1.4 阶段的组合
在反编译器的实际实现通常把第1.3节列出的几个反编译器阶段组合在一起。正如表1-13所示，分成三个不同的模块：前端、UDM和后端。

表 1-13: 反编译器的模块

前端由那些机器依赖的和机器语言依赖的阶段组成。这些阶段包括词汇的、语法的和语义的分析，以及中间代码生成和控制流图生成。总而言之，这些阶段产生一个中间的、与机器无关的程序表示法。
UDM即universal decompiling machine（通用反编译机器）；它是一个完全独立于机器和语言的中间模块，而且它是执行反编译分析的核心。这个模块包括两个方面：数据流分析器和控制流分析器。
最后，后端由那些高级语言依赖的或目标语言依赖的阶段组成。这个模块是代码生成器。
在编译器理论中，阶段的组合是编译器作者为不同机器、不同语言创造编译器的一个机制。如果为不同的机器重新编写一个编译器后端，那么该机器的新编译器使用原来的前端构成。类似地，可以为别的高级语言定义编写一个新前端，然后跟原来的后端一起使用。实际上，这个方法受限于它内在选择的中间代码表示法。
理论上，反编译器的阶段组合使得为各种不同机器和语言编写反编译器变得容易些：为不同机器编写不同的前端，为不同的目标语言编写不同的后端。在实际应用中，其成效始终受限于它所采用的中间语言的普遍适用程度。

1.5 反编译器的上下文环境
在实践中，有一些程序可以配合反编译器一起创建目标高级语言程序。一般来说，源的二进制程序有一个重定位地址表，当程序被装入内存的时候，在那些地址上将进行重定位。这个任务由装载程序完成。然后，重定位的或绝对的机器码被反汇编以产生程序的一个汇编表示法。反汇编器可以利用编译器和库的签名的辅助来清除掉编译器启动代码(start-up)和库例程的反汇编。然后，汇编语言程序作为反编译器的输入，它产生一个高级语言目标程序。需要对目标程序做进一步的处理，比如把while()循环转换成可以被后续处理程序使用的循环。表1-14展示了“反编译过程”的几个典型步骤。使用者也可能作为一个信息提供者，尤其是在确定库例程以及区分数据和指令的时候。只要有可能，这会比使用自动工具更加可靠。反编译器辅助工具在第8章讨论。这一节简单说明它们的任务。

表 1-14: 反编译系统

装载器
装载器是一个程序，它把二进制程序装入内存、并且如果程序是可重定位的则重定位机器码。在重定位期间，指令被改变然后放回内存。

签名生成器
签名生成器是一个自动确定编译器和库的签名的程序：唯一地标识每个编译器和库子程序的二进制标本。这些签名的使用试图反向进行链接器的工作——链接器把库和编译器启动代码链接到程序。这样，被分析的程序只包括用户子程序：从用户最初的高级语言程序编译那些。
例如，显示“hello world”的C程序编译以后，在二进制程序中有超过25个不同子程序，其中16个子程序是由编译器增加来设置它的环境，9个例程由链接器增加来实现printf()，1个子程序来自最初的C程序。
签名生成器的使用不仅减少了需要分析的子程序个数，也由于使用库函数名称代替任意的子程序名称从而增加了目标程序的可读性。

原型生成器
原型生成器是一个自动确定库子程序参数类型以及函数返回值类型的程序。这些原型来自于函数库的头文件，被反编译器用来确定库子程序的参数及其个数。

反汇编器
反汇编器是一个把机器语言转换成汇编语言的程序。有些反编译器把汇编语言程序转换成一个更高级的表示法(见第2章)。在这些情况下，已经由反汇编器产生的汇编程序是用汇编器写的或者是用编译器编译汇编程序。

库联编
如果所生成的目标代码使用了库函数名称(亦即，能检测到库签名)，只要反编译器的目标语言不同于最初用来编译二进制源程序的语言，因为两种语言使用不同的库例程，所以即使这个程序是正确的也不能以目标语言再编译了。使用库联编——把一种语言的子程序绑定到另一种语言——解决了这个问题。

后处理器
后处理器是一个程序，它把一个高级语言程序转换成同种语言的一个语义等价的高级程序。例如，假如目标语言是C语言，以下代码

loc1 = 1;
while (loc1 < 50) {
  /* some code in C */
  loc1 = loc1 + 1;
}

可能被后处理器转换成

for (loc1 = 1; loc1 < 50; loc1++) {
  /* some code in C */
}

这是一个语义等价的程序，使用C语言可用的控制结构，并非反编译器反编译出来的通有构造。

1.6 反编译的用途
反编译是计算机专业人士的一个工具。反编译主要使用在两个领域：软件维护与安全性。在前一个领域，反编译被用来恢复丢失的或者不能见到的源程序代码，将一个使用过时的语言编写的代码翻译成一个较新的语言，将一个以非结构化方式编写的旧程序(亦即，多层式代码)构成一个结构化程序，将应用程序移植到一个新的硬件平台，以及调试已知有缺陷但是源代码不可得的二进制程序。在后一领域，反编译在软件关键系统中被用来验证一个编译器产生的目标代码，因为在这些系统中编译器不足以信赖，另外，反编译也被用来检查是否存在恶意代码比如病毒。

1.6.1 法律方面
关于反编译的合法性问题去年已经被提出来了。反编译支持者和反对者之间的争论目前正在进行，支持方主张反编译工具的使用有利于公平竞争，反对方主张反编译侵犯了版权。各个不同国家正在修改法律以确定在哪些情况下反编译是法律许可的。目前，商业软件的销售随同软件协议书禁止用户反汇编或反编译其产品。例如，Lotus软件协议部分这样写道：

You may not alter, merge, modify or adapt this Sofware in any way including disassembling or decompiling.

探讨反编译的合法性相关问题不是本论文的目的。本论文不对该主题做更进一步讨论。