Question

在编写一个反编译器的时候，反编译器作者必须面对一些理论上和实际的问题。有些问题能够通过使用启发式（试探方法) 解决，而另一些则不能被完全确定。由于这些限制，反编译器能够对某些源程序进行全自动的程序翻译，而对于另一些源程序只能进行半自动的程序翻译。编译器是不同的，它对所有源程序都进行全自动程序翻译。这一节讨论反编译器涉及的一些问题。

1.2.1 递归的不确定性

可计算性的一般理论试图解决判定问题，即，研究对于某一个完全的陈述类是否存在判定其对错的算法。如果问题有肯定的答案，那么必须给出一个算法；否则，就要证明这样的算法不存在。对于后者，我们称之为问题是不可解决的、不可判定的、或不可计算的。对于不可解决的问题，如果能给出这样一个算法——无穷循环的程序能够在任何时候停机，那么问题可能是部分可计算的。

在数学世界里，一个抽象的概念必须用数学定义描述和建模。算法的抽象化必须用图灵机 (一种可不受储存容量限制的假想计算机) 描述。图灵机是一个计算机器，它在一个两个方向都无限长的线性磁带上打印符号，拥有有限个数的状态，并基于它的当前内部配置和磁带上的当前符号、执行由四元组的含义指定的动作。图 1-2 显示一个图灵机表示法。

图 1-2: 图灵机表示法

图灵机 Z 的停机问题包括，对于任一给定的瞬间描述α，确定是否存在一个由α开始的 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		add ax, [bp-4] adc dx, [bp-2]
	↓
mul ax, 4		add dx:ax, [bp-2]:[bp-4]

图 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: 体系结构依赖的问题