原文标题:Reverse Compilation Techniques
作者:Cristina Cifuentes
译文标题:逆向编译技术
翻译:月中人

摘要
这篇论文介绍逆向编译器或反编译器的编写技术。这些技术以编译器和优化理论为基础,并且以独特的方式应用于反编译;这些技术以前从未被公开发布。
反编译器分为若干步骤,它们被组合成与语言特征或机器特征相关的几个模块。前端是一个机器依赖的模块,它对二进制程序进行语法分析、程序指令的语义分析、并且生成该程序的一个低级的中间表示法和每一个子程序的控制流图。通用的反编译机器是一个与语言和机器无关的模块,分析低级的中间代码,将它转换成一个适用于任何高级语言的高级表示法,并且分析控制流图的结构、把它们转换成用高级控制结构表示的图。最后,后端是一个目标语言依赖的模块,它生成目标语言代码。
反编译的过程包括一些工具的使用:把二进制程序装入内存,对这一程序进行语法分析或反汇编,以及反编译或者分析该程序以生成一个高级语言程序。这个过程利用编译器和库的签名的帮助来识别特定的编译器和库子程序。只要在二进制程序中识别出编译器签名,编译器启动代码(start-up)和库子程序都不做反编译:对于前者,从最后的目标程序去掉启动代码那些例程,反编译器从主程序入口分析;对于后者,那些子程序用它们的库函数名称代替。
所提出的技术在一个适用于Intel i80286体系结构的反编译器样机上实现,该样机名为dcc,在DOS操作系统上运行,为源的.exe文件或.com文件产生目标C程序。在第9章,把反编译输出的程序跟它最初的高级语言程序做了采样比较,并且对反编译结果做出一个分析。
第1章从一个编译器观点对反编译做了介绍,第2章从20世纪60年代早期反编译出现开始介绍它的历史概况,第3章介绍源二进制程序的静态二进制代码和在运行时实现程序的动作之间的关系,第4章描述前端模块这个阶段,第5章详细说明用于分析中间代码的数据优化技术,把中间代码转换成一个更高级的表示法,第6章详细说明用于分析控制流图结构的控制结构转换技术,把控制流图转换成一个高级控制结构的图,第7章描述后端模块,第8章介绍反编译工具程序,第9章综述dcc的实现以及取得的成果,第10章给出结论以及这项研究的工作前景。
这篇论文的有些部分已经公开发表或者提交给国际定期刊物。两篇文章在1993年出现在第19号《拉丁美洲信息会议》(XIX 'Conferencia Latinoamericana de Informatica'):“反编译的一种方法学”[CG93] 和“反编译的一个构成算法”[Cif93]。前一篇文章的内容有反编译的阶段(如第1章第1.3节所述)、前端(第4章)、控制流分析阶段的初始工作(第6章)、以及dcc工作实现的说明。后一篇文章的内容有控制流分析阶段使用的构成算法(第6章)。一篇刊物文章“二进制程序的反编译”[CG94] 已经被《软件-实践与经验》(Software - Practice & Experience)接受发表;这篇文章概述建立一个反编译器所使用的技术(第4,5,6,7章的摘要)、签名生成器工具如何帮助反编译进程(第8章第8.2节)、以及用dcc反编译的一个程序样本(第9章)。两篇文章目前正考虑在国际刊物上发表。“子过程之间数据流的反编译”[Cif94a]被提交给《程序语言杂志》(the Journal of Programming Languages),文中完整描述了数据流分析器的优化操作,把低级的中间代码转换成一个高级的表示法。“构成反编译图”[Cif94b] 被提交给《计算机杂志》(The Computer Journal),文中给出构成控制流图的最后改良方法,以及用dcc反编译的一个程序样本。
这篇论文中提出的技术更充分地拓展文献中前人的工作。关于为了确定寄存器参数和寄存器返回值所需要做的子过程寄存器分析、为了清除掉有关栈的指令(亦即push和pop)或者构成一个控制结构的类集所需要做的分析,过去没有相关的反编译研究文献。为这项研究所做的创新工作在第5,6,8章描述。第5章第5.2节和5.4节举例并描述了九种不同类型的优化,把低级的中间代码转换成一个高级表示法。这些优化考虑条件代码、子程序调用(亦即,子过程间的分析)和寄存器溢出,清除掉中间指令的所有低级特征(比如条件代码和寄存器),而且把表达式的高级概念引入中间表示法。第6章第6.2节和6.6节举例并描述了各种不同类型的循环和条件转移包括多分支条件(例如case语句)的构成算法。在这个领域中前人的工作成果主要集中在循环的构成,很少文章尝试两路(2-way)条件分支的构成,而对于多路条件分支则没有研究说明。这篇论文提出一个完整的方法,在一个预先确定的、高级控制结构的类集基础上构成各类结构。在第6章第6.4节给出确定控制结构类集的一个标准。第8章描述反编译程序使用的全部工具,最重要工具是签名生成器(第8.2节),它用于在操作系统不共享库的体系结构下确定编译器和库的签名,比如DOS操作系统。

第 1 章 反编译导言
编译器的编写技术在计算机界广为人知;而反编译器的编写技术还不这么被人熟悉。有趣的是,反编译器的编写技术是以编译器的编写技术为基础,本论文将一一说明。这一章通过描述一个反编译器的组成部分和一个二进制程序的反编译环境,先对反编译这个主题做一初步介绍。

1.1 反编译器
反编译器是这样一个程序,它读入一个机器语言的程序 - 源语言 - 并把它翻译为一个等价的高级语言程序 - 目标语言 (见表1-1)。反编译器或反向编译器,试图逆向一个编译器的过程:将一个高级语言程序翻译成一个二进制程序或可运行程序。
源程序(机器语言) ----> 反编译器 ----> 目标程序(高级语言)
表 1-1: 反编译器
把二进制程序从各种各样的机器语言反编译为多种多样的高级语言,都要用到基本的反编译器技术。反编译器的结构是以编译器的结构为基础,采用与之相似的原理和技术来进行程序分析。第一代反编译器诞生于20世纪60年代早期,比它们的姐姐编译器小十岁。对于第一代编译器,反编译大量地被用来翻译科学程序。第2章描述反编译的历史。

1.2 问题
在编写一个反编译器的时候,反编译器作者必须面对一些理论上和实际的问题。有些问题能够通过使用试探方法(启发式)解决,而另一些则不能被完全确定。由于这些限制,反编译器对某些源程序能够进行全自动的程序翻译,而对其它一些源程序则需要进行半自动的程序翻译。这与编译器它对所有源程序都进行全自动程序翻译是不同的。这一节讨论它涉及的一些问题。
1.2.1 递归的不确定性
可计算性的一般理论试图解决判定问题,即探究,对于某一类陈述的对错是否存在判定算法的问题。如果问题有肯定的答案,那么必须给出一个算法;否则,就要证明这样的算法不存在。对于后者,我们称之为问题是不可解决的、不可判定的、或不可计算的。对于不可解决的问题,如果能给出这样一个算法无穷循环的程序能够在任何时候停机,那么问题可能是部分可计算的。
在数学世界里,一个抽象的概念必须用数学定义描述和建模。算法的抽象化必须用图灵机(一种可不受储存容量限制的假想计算机)描述。图灵机是一个计算机器,它在一个两个方向都有无限长度的线性磁带上打印符号,拥有有限个数的状态,并基于它的当前内部配置和磁带上的当前符号、执行由四元组含义指定的动作。
表1-2是一个图灵机表示法。

表 1-2: 图灵机表示法

图灵机Z的停机问题包括,对于任一给定的瞬间描述{alpha},确定是否存在一个由{alpha}开始的Z计算。换句话说,我们正在尝试确定,如果把Z放在某一个初始状态中它是否会停机。已经证明这个问题是递归地不可解决的和部分可计算的 [Dav58,GL82]。
给定一个二进制程序,甚至可以假定在程序中不允许自修改代码之类的行为,从代码中区分出数据的问题等价于停机问题,因为一条特定指令是否会被运行一般来说是未知的(例如,关于一个循环之后的代码)。这意味着该问题是部分可计算的,因而有些情况下能够写出一个从代码中区分出数据的算法,但不是所有情况下都能够做到。

1.2.2 冯诺依曼体系结构
在冯诺依曼机器中,内存里的数据和指令以同样的方式表现。这意味着,只有当一个给定字节从内存被读出放入一个寄存器作为数据或指令使用的时候,我们才知道它是数据还是指令(或两者都是)。即使是在分段的体系结构上,其中数据段里只有数据信息、代码段只有指令,数据仍然能够以表的形式被储存在一个代码段中(例如,Intel架构的case表),指令也能够以数据的形式被储存然后通过解释这些指令而运行。PC机的Modula-2编译器用这后一个方法解释一个抽象栈机器的中间代码。中间代码被储存为数据,es:di持有的偏移量指向特定的子程序 [GCC+92]。

1.2.3 自修改的代码
自修改代码指的是指令或者预置数据在程序运行期间被修改。一条指令的一个内存字节位置能够在程序运行期间被修改、表现成另一条指令或数据。这个方法曾经很长时间用于实现各种目的。在60年代和70年代,计算机内存很小,难以运行大程序。那时,计算机内存最多有32Kb和64Kb可用。由于空间有约束,所以必须尽量充分利用。其中一个办法就是在可运行程序中节省字节,重复使用数据位置作为指令或反之。这样,一个内存单元在一时间持有指令,而在另一时间变成持有数据或别的指令。而且,当指令不被需要时其它指令就修改它们,因而程序下次执行那部分代码的时候就执行了不同的代码。
现在的计算机在内存方面的限制少了,因此自修改代码不再经常使用。但是在编写加密程序或病毒代码的时候仍然有用(见第1.2.5节)。表1-3给出一个Intel架构的自修改代码样例。inst定义的数据字节被mov指令修改成E920。动作之后,inst被当作另一条指令,它现在是0E9h 20h;即,一条跳转偏移20h的无条件跳转指令。动作之前,inst内存位置上是9090,被作为两条nop指令来执行。

  ...       ; other code
  mov [inst], E920   ; E9 == jmp, 20 == offset
inst   db 9090     ; 90 == nop

表 1-3: 自修改代码的样例

1.2.4 成语
成语或成语性词语是一序列指令,它形成一个逻辑实体,作为整体表示一个含义,而这个含义是不能够从各组成指令的基本含义推导出来的 [Gai65]。
例如,乘以或除以2的N次方是一个普遍已知的成语:乘法是通过左移来执行,而除法是通过右移来执行。另一个成语是long变量相加的方式。如果机器的字长是2字节,则一个long变量有4字节。若要相加两个long变量,先相加低两字节,然后相加高两字节时计入第一次相加的进位。这些成语及其含义在表1-4举例说明。大多数成语在计算机界已知,但遗憾的是,并非所有的成语都被普遍了解。

shl ax, 2                  mul ax, 4
add ax, [bp-4]             add dx:ax, [bp-2]:[bp-4] 
adc dx, [bp-2]

表 1-4: 成语样例

1.2.5 病毒和木马的“诡计”
病毒程序不只有产生不良后果的代码,还设法隐藏这个代码。病毒使用各种方法隐藏其恶意代码,包括自修改和加密技术。表1-5以Azusa病毒为例说明,它在栈里存放一个新值作为一个子程序的返回地址。如图示,病毒代码的段和偏移地址被入栈,随后有一条远返回指令将控制交给病毒代码。当反汇编代码的时候,大多数反汇编器会认为子程序已经结束了,因而在远返回指令上停止对该子程序的反汇编;然而事实并非如此。

    ...     ; other code, ax holds segment SEG value
SEG:00C4   push ax   ; set up segment
SEG:00C5   mov ax, 0CAh   ; ax holds an offset
SEG:00C8   push ax   ; set up offset
SEG:00C9   retf     ; jump to virus code at SEG:00CA
SEG:00CA   ...     ; virus code is here

表 1-5: 修改返回地址

使用自修改代码来修改一条无条件跳转指令的目标地址偏移是一个常用技巧,该偏移量事先已定义为数据。表1-6举例说明Cia病毒在运行前的有关代码。如图示,cont和conta分别定义数据项0E9h和0h。在这个程序的运行期间,procX用病毒代码的偏移修改conta的内容,并在子过程返回后,数据当作指令,执行 jmp virusOffset (0E9h virusOffset) 指令。

start:
  call procX   ; invoke procedure
cont   db 0E9h   ; opcode for jmp
conta   dw 0
procX:
  mov cs:[conta],virusOffset
  ret
virus:  ...     ; virus code
end.

表 1-6: 自修改代码的病毒

病毒代码会以加密的形式出现,而且这个代码仅在需要的时候才进行解密。一个简单的加密/解密机制是用异或函数做的,因为一个字节与同样的常数两次异或的结果等于原字节。因此,加密过程是对其代码运用一次异或操作,解密过程则是将代码异或相同的常数值。表1-7举例说明这个病毒,它是LeprosyB病毒的一部分。

encrypt_decrypt:
  mov bx, offset virus_code   ; get address of start encrypt/decrypt
xor_loop:
  mov ah, [bx]       ; get the current byte
  xor ah, encrypt_val     ; encrypt/decrypt with xor
  mov [bx], ah       ; put it back where we got it from
  inc bx         ; bx points to the next byte
  cmp bx, offset virus_code+virus_size ; are we at the end?
  jle xor_loop       ; if not, do another cycle
  ret

表 1-7: 自加密的病毒

最近,多态变形被用来加密病毒。这类病毒主要关键是基于指令集的规则性自己生成代码段。表1-8举例说明Nuke病毒的加密引擎。这里,加密循环中每轮使用一个不同的键(ax),并使用一条异或指令加密。

  Encryption_Engine:
07AB   mov cx,770h
07AE   mov ax,7E2Ch
07B1 encryption_loop:
07B1   xor cs:[si],ax
07B4   inc si
07B5   dec ah
07B7   inc ax
07B8   loop encryption_loop
07BA   retn

表 1-8: 自生成的病毒

总之,病毒程序利用机器语言集的任何缺陷、自修改代码、自加密代码和无文档操作系统函数。这类代码难以自动反汇编,因为对指令/数据的修改大部分在程序运行期间进行。在这些情况下,需要人工介入。

1.2.6 体系结构依赖的限制
大多数现代计算机体系结构当处理器执行指令的时候使用一个预取缓冲区取指令。这意味着所预取的指令被存放在一个跟指令在主存中原先位置不同的地方。当一个程序利用自修改代码试图修改一条在内存里的指令的时候,如果指令已经被预取,那么它的内存副本被修改而在流水线缓冲区里的指令并没有得到修改;因此,所执行的是原始未修改的指令。这个例子可以见表1-9。在该例中,jmpDef数据定义的确是一条指令,jmp codeExecuted。这一定义看起来似乎被前面的指令‘mov[jumpDef],ax’修改了,它把jmpDef的定义换成两条nop指令。这就意味着codeNotExecuted处的代码被执行,显示“Hello world!”然后退出。而在i80386机器上运行这个程序的时候,它显示“Share and Enjoy!”。因为i80386有一个4字节的预取缓冲区,jmpDef定义已经被预取,因而没有被修改,所以执行的是跳转到codeExecuted处,亦即显示“Share and Enjoy!”。使用一般的直线单步调试器我们无法确定这类代码的执行情况,除非对机器做一个完全的仿真。

1.2.7 被编译器和链接器引用的子程序
另一个反编译问题来自由编译器引进的大量子程序和由链接器链接的一些例程。编译器将总是引入启动子程序(start-up)建立它的环境、以及所需要的运行时支持例程。这些例程通常是用汇编语言编写的,而且大多数情况下无法翻译成高级表示法。另外,大多数操作系统不提供共享库机制,因此,二进制程序是自我包含的,库例程被封装入每一个二进制映像之内。库例程或是用编译器的编写语言或是用汇编语言编写。这意味着一个二进制程序不仅包含由程序设计者编写的例程,也通过链接器链接了很多其它例程。例如,一个显示“hello world”的C程序在PC机上编译成二进制程序以后有25个以上不同的子程序。而使用Pascal语言编写类似的程序在PC上编译会在可执行程序中产生40个以上子程序。逆向工程师通常只对所有这些例程中的一个初始子程序感兴趣:主程序。

  mov ax, 9090   ; 90 == nop
  mov [jumpDef], ax
jmpDef db 0EBh 09h   ; jmp codeExecuted
codeNotExecuted:
  mov dx, helloStr
  mov ah,09
  int 21     ; display string
  int 20     ; exit
codeExecuted:
  mov dx, shareStr
  mov ah, 09
  int 21     ; display string
  int 20     ; exit
shareStr db "Share and Enjoy!", 0Dh, 0Ah, "$"
helloStr db "Hello World!", 0Dh, 0Ah, "$"

表 1-9: 体系结构依赖的问题

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.
 
探讨反编译的合法性相关问题不是本论文的目的。本论文不对该主题做更进一步讨论。