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

逆向编译技术

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

作者: 月中人
时间: 2007-04-08,17:39
链接: http://bbs.pediy.com/showthread.php?threadid=42346

原文标题：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: 体系结构依赖的问题