反编译技术

1. 什么是反编译

1.1 反编译的概念

反编译技术是通过对低级语言代码（二进制代码或者汇编代码等）进行分析转化，得到等价的高级语言（不限制语言类型）代码的过程。它涉及指令系统，可执行文件格式，反汇编技术，数据类型分析技术，控制流分析技术和高级代码生成技术等。编译与反编译之间的相同点是它们都是将程序从一种形式转换到另一种形式，而且在转换中都利用到了中间表示。不同点是编译过程是将高级语言的功能用机器实现，为高级语言加上特定机器的属性，比如指令格式、寄存器分配、寻址方式等；而反编译则是要将程序中的机器属性剥离，生成机器无关代码，重建高级语言的数据类型和结构（二进制翻译是要将源程序转化为目标程序在目标机器上执行，反编译是二进制翻译的一个子过程）。

1.2 反编译器

反编译器是利用反编译技术实现的具体软件系统。它读入一个机器语言的程序（被编译器编译生成的二进制编码，即源语言），并把它翻译为一个等价的高级语言程序（即目标语言）。反编译器的结构是基于编译器的结构，而且应用类似的原理和技术进行程序分析。

2. 反编译的基本过程

如果按照反编译技术实施的顺序划分，则可以分为 7 个阶段，它们是：句法分析、语义分析、中间代码生成、控制流图生成、控制流分析、代码生成。

如果按照实践中的具体操作划分，一般也可以分为 7 个不同的步骤，分别是：文件装载，指令解码，语义映射，相关图构造，过程分析，类型分析和结果输出等。

3. 反编译技术的发展

3.1 理论研究

1973 年，Doctor Hollander 首次针对反编译方式生成的代码，使用控制流与数据流分析相结合的技术手段来进行优化。此外，他还基于元语言描述定义了一个反编译过程的五级模型，并且实现了从 IBM System360 汇编子集到类 ALGOL 语言的反编译。该反编译器虽然引入了一些新的技术，即综合利用数据流和控制流分析技术来改善反编译器的输出代码，并使用形式化方法来分析代码，但其核心依然是构筑在模式匹配技术基础之上。

几乎在同时，Doctor Housel 的博士论文对反编译进行了较系统的论述，文中描述了一种可行的反编译方法，并通过实验验证了部分理论。Housel 的反编译方法借用编译器、图、和优化理论的概念，并据此设计了一种包括部分汇编、分析器、代码生成等三个主要步骤的反编译器。然而受限于当时实验平台和目标程序，Housel 仅仅测试了 6 个程序。实验中，有 88%的指令可以通过反编译器自动生成，剩余的指令则需要程序员进行手工干预。这个反编译器证明，通过使用已知的编译器和图的方法，可以实现生成良好高级代码的反编译器。中间表示法的使用使得分析完全不依赖机器。这个方法学的主要缺陷在于源语言的选择，MIX 汇编语言，在这些程序中不仅带有大量可用信息，而且它是一个简单化的、非现实的汇编语言。

1974 年，Doctor Friedman 在他的博士学位论文中描述了一个反编译器，用于在相同体系结构等级内的小型计算机操作系统的迁移。该编译器包含四个主要部分：前期处理器、反编译器、代码生成器、和编译器，它是 Housel 反编译器的一个改写版。Friedman 在反编译操作系统代码的方向上迈出了第一步，而且它例证了在反编译机器依赖的代码时反编译器面对的困难。不足的是，该迁移系统对输入程序有所要求，即需要对输入程序做大量格式化工作；同时，该系统最后产生的程序代码具有较大的空间膨胀率，而代码膨胀率高又带来了执行时间和效率的低下。

1978 年，Doctor Hopwood 所做的工作实现了从汇编语言程序到 MOL620 语言程序的翻译功能。他引入了控制流图的概念，即指定一条指令作为控制流图的一个节点。与现在广为采用的以基本块为节点的方式相比，Hopwood 的方案对内存的要求会更高一些。Hopwood 的博士学位论文描述了有关其设计的一个包含七个步骤的反编译器的内容，他的研究的主要缺点是控制流向图的粒度和在最后的目标程序中寄存器的使用。其中控制流向图的粒度的使用，导致该反编译器处理大规模程序的时候开销太大；而在其所生成的目标高级语言代码中使用了寄存器，导致反编译结果并非纯正的高级代码。

3.2 反编译在工程上的应用

20 世纪 70 年代的十年是反编译技术发展的一个黄金时期，当时的反编译器并未局限在对高级编程语言的恢复上，而是引入了“翻译”的特征。在这个时期，除了一些以理论研究为主的反编译器模型被提出以外，还有一些具有代表性的实用系统被开发出来。

1974 年，由 Barbe 开发的 Piler 系统是第一个实现的 X 型通用反编译器架构，它的设计目标是实现从多种机器级代码到与其各自对应的高级语言程序的反编译。但是这种多源到多目标的反编译实现起来具有极高的难度，直接导致 Piler 系统最终实现时，仅能支持从通用公司的 Honeywell 600 机器代码到 Fortran 和 COBOL 两种高级语言程序的反编译。可见，当时的反编译器如果能够实现对“翻译”输出的高级语言再次编译，并且编译后程序的运行结果与反编译前一致的话，就几乎相当于一个二进制翻译器了。

4. 反编译的局限性

4.1 反编译技术面临的宏观问题

问题：同一机器上，同一语言的不同编译版本存在目标代码结构上的差异，即多编译版本问题；同一机器上，不同语言编译存在目标代码结构上的差异，即多语言问题；不同机器上，同一语言编译存在目标代码上的差异，即多机种(CPU，也就是多体系结构)问题。

解决方案：对于不同的机型和同一种语言，可以设计抽象的中间代码，也就是与体系结构不相关的，寄存器数量不限，采用目标代码预处理方法分别转换到抽象的中间代码，接下来根据不同的后端，进行中间 代码的提升。

4.2 反编译技术面临的技术性问题

4.2.1 区分代码和数据

受冯•诺伊曼结构的制约，绝大多数计算机使用的数据和代码是存储在同一段内存空间中的，因此，区分数据和代码的一般解决办法已经被证明等价于停机问题（NPC 问题，不可解）。虽然，多种格式的可执行文件都定义了代码段.text 和数据段.data，但这样并不能阻止编译器或程序员把常量数据（如：字符串、switch 跳转表）放入代码段中，也无法阻止将可执行代码放入数据段中。因此，代码和数据的区分仍然是一个亟需解决的重要问题。

针对代码和数据的区分问题，对静态反编译而言效果最好的一个方法是数据流制导的递归遍历。此技术根据机器代码从程序的入口点搜索所有可能的程序路径，它依赖于程序的所有路径都是有效的，且入口点是可发现的。最终，它同样依赖于分析间接转移指令以获得其目标地址的能力，间接转移指令包括间接跳转和间接调用指令。

4.2.2 处理间接跳转和间接调用指令

对于指令中的每个立即数操作数，都需要选择将这个数值作为常量的值来表示还是作为指向内存中地址的指针来表示。对间接跳转和间接调用的分析面临着一个共同的问题——目标地址的确定。

程序切片、表达式复制传播和值域分析等是最有希望解决这一问题的技术，但是这些技术严重依赖于数据流分析，而数据流分析又依赖于完整的控制流图。间接跳转和间接调用问题未得到解决之前，是不可能拥有一个完整的控制流图的。因此，初看起来它就如“鸡跟蛋”问题一样是无法解决的。

4.2.3 自修改代码

自修改代码指的是指令或者预先设定的数据在程序执行中被修改。如用于储存指令的内存空间可能会在程序执行过程中被修改成为了另外的指令或者数据。

5. 常见的反编译器框架

5.1 “I 型”反编译器的框架

5.2 经典多源反编译器框架

目前支持多源的反编译框架主要有三种，分别是：基于语义描述和过程抽象描述的可变源、可变目标框架；以商用反汇编软件 IDA Pro 为前端的、支持可扩展的反编译框架；以及基于第三方代码转换库的多源反编译框架。下面分别以三种框架的典型系统为例，简单介绍和分析一下各种框架的特点。

5.2.1 UQBT

（1）框架结构

UQBT 框架可以大致被分为三部分：前端、分析和翻译部分、后端。Ms 表示给定的源机器，Md 表示目标机器，前端负责对源机器 Ms 上的二进制文件解码，并将其转换为与机器无关的中间语言形式，即 RTLs 的形式；分析部分负责将源机器上的地址映射为目标机上的地址并完成相关的优化；后端负责将优化过的中间语言形式转换为对应目标机上的可执行文件。由此可见 UQBT 框架中的前端和分析部分相当于反编译的部分，后端则是代码生成部分，即将反编译后的代码再编译或转换为目标机上的可执行代码。

UQBT 是可变源、可变目标的，对于反编译来说只是为了实现从低级代码到高级代码的转换，不需要再转变为目标机器上的可执行代码，因此可以不考虑多目标的问题。UQBT 的可变源和目标的特性通过描述语言、API 和可插入模块支持。其中几个形式化的描述语言成为 UQBT 的亮点和精髓，分别是：编解码描述语言 SLED、语义描述语言 SSL、过程描述语言 PAL 等。

• SLED 语言

  SLED 语言是专门用来描述汇编指令与二进制编码之间映射关系的语言，支持 RISC 和 CISC 指令架构，已实现对 MIPS、SPARC 和 Pentium 的编解码描述。基于 SLED 描述的指令解析，由 NJMC(New JerseyMachine Code)工具集通过匹配语句来驱动，但对于一个特定的 SLED 描述文件，要为其生成专门的匹配语句，而这个过程要实现自动化非常困难。

• SSL 语言

  SSL 语言包括两类语义的描述，一类是描述每条汇编指令的语义，另一类则是描述硬件体系架构相关的特征。通过定义 constants、registers、flag_fnc、operands、tables、instr 等关键词来进行描述。其中 constants 用来描述常量、registers 用来描述寄存器、flag_fnc 用来描述标志副作用、operands 用来描述复杂操作数、tables 用来描述一组指令名称、instr 则用来描述一条 SSL 语句。而一条 SSL 语句由左部 LHS 和右部 RHS 两部分组成，左部对应的是汇编指令的名称，或一组汇编指令对应的表的名称，右部则是表示寄存器转换的语句序列。对 SSL 语言的解析是由语义描述解码器 SRD 来完成。由于 SSL 语言的语法比较复杂，要实现对各种 SSL 描述的正确解析也是很困难的。

• PAL 语言

  PAL 语言分别利用 FRAME ABSTRACTION、LOCALS、PARAMETERS、RETURNS 四种关键字对内存栈的抽象、本地变量的抽象、参数的抽象、返回值的抽象进行描述。其中内存栈的抽象主要描述用于存放内存栈指针的寄存器名称；本地变量抽象主要描述栈帧分配的大小；参数的抽象主要从调用者和被调用者两个角度描述实参和形参所在的可能位置；返回值的抽象则主要描述返回值与存放返回值的寄存器或内存单元之间的对应关系。

• APIs

  UQBT 提供了二进制文件格式和控制转移 APIs。二进制文件格式有多种（如：Elf，PE 等），但是这些表示都有方法可以从可执行程序中提取代码和数据——这种类型的信息可以通过 API 获得。

（2）中间表示

UQBT 应用两种中间表示，低级 RTL（Register TransferLists）直接与机器指令映射，高级 HRTL（High LevelRegister Transfer Lists）形式与编译器中间代码类似，它应用了控制流的高一级抽象（不懂）。

RTL 是一种基于寄存器的中间语言，它针对机器的汇编指令进行描述，代表了指令间的信息传递。该语言提供了无限个寄存器和内存单元可供使用，不会受限于某种特殊的机器结构。近年来，RTL 已经被广泛的应用到各种系统中作为中间表示，例如 GNU 编译器、编译连接优化器 OM、编辑库 EEL 等等。

在 UQBT 中，源机器体系结构每一条指令对应一个寄存器传送列表或 RTL 语句。这种语言能够通过对某一位置的一系列执行效果来捕获机器指令的语义信息。

HRTL 是从过程调用、过程内控制流等与机器特性相关的细节中抽象出来的一种高级中间表示语言，由指令和操作符组成。它提供了所有基本控制流指令，例如无条件跳转（JUMP）和条件跳转(JCOND)、应用 CALL 和 RETURN 指令的过程调用、N—way 分支指令等，为了给内存单元赋值，HRTL 定义了 ASGN 指令。

（3）前端模块

前端模块的工作由一系列阶段完成，每一个阶段将源输入文本流变换成高一级的表示形式。

• 二进制文件的解码器

  将源二进制文件解码到一种中间表示，该中间表示支持二进制文件格式 API。所有的文本段和代码段被拷贝，并将得到的二进制文件信息存放在中间表示中。

• 指令的解码

  将文件解码器得到的指令流进行反汇编。在 UQBT 中主要应用 NJMCT 提供的匹配文件，结合指令的 SLED 描述文件完成指令的解码。

• 语义映射模块

  将汇编指令映射成与源机器文件代码段相对应的 RTL 表示，RTL 由机器的 SSL 描述语言提供。这一步在汇编指令匹配之后执行，指令被转换成寄存器传送列表（RTL）。

• Ms－RTL 到 HRTL 翻译器

  这是二进制翻译中的一个关键阶段，以机器无关性来表示程序代码。该模块将 RTL 指令转换成 HRTL 指令，处理控制转移指令，基于 PAL 描述分析过程信息，添加额外的代码处理源机器指令集的特性，其中机器特定的分析用于将机器相关性进行消除。在 UQBT 中这部分工作包括 SPARC 中控制的延迟转移消除，Pentium 中将基于栈的浮点代码变换成基于寄存器的代码。

（4）后端模块

UQBT 框架应用多种后端产生代码，其中比较成功的方法是依赖 C 编译器作为目标机的优化器和代码产生器。在这种方法中，HRTL 代码被翻译到低级 C，应用 C 编译器作为宏汇编器。后来的 UQBT 版本应用公共域或特性优化器后端，并集成在 RTL 级。