Question

这篇论文论述了二进制程序的逆向编译或反编译技术，并且给出反编译器各个不同阶段的实现算法。而且，在 DOS 和 Unix 下运行测试用该方法学实现的一个反编译器样机 dcc。

反编译器应用和编译器相似的原理和技术。一个反编译器有七个不同阶段，相当于混合编译器和优化阶段。由于源机器语言的简单性，它没有词汇分析阶段。语法分析阶段解析做为源输入的二进制程序，区分代码和数据，并且把数据引用存放在符号表。区分代码和数据的主要困难是它们在冯·诺依曼机器中以相同的方式表现。中间代码生成阶段产生该程序的低级中间表示法。语义分析阶段检查低级指令组（成语) 的语义含义，收集类型信息，并且向整个中间表示法传播这些信息。控制流向图生成阶段产生该程序每个子程序的控制流向图，并且把中间表示法信息附加到图的结点上。数据流分析阶段分析低级中间代码，并且把它转换成一个任何高级语言均可接受的高级中间表示法。指令转换清除掉所有低级引用之条件码和寄存器，并且引进高级的表达式概念。标示出无法用高级语言表现的子程序。在控制流分析阶段分析程序的结构，这个阶段把程序中每个子程序的控制流图结构化。最后，代码生成阶段在高级中间表示法和每个子程序的结构化图的基础上生成高级代码。

若要完整地反编译一个程序，不仅要使用反编译器也要使用其它有关工具：装载器、签名生成器、原型生成器、反汇编器和后期处理器。装载器把做为源输入的二进制程序装入内存，签名生成器为已知的编译器和它们的库生成签名（如果需要的话)，原型生成器确定库子程序形式参数的类型，反汇编器语法分析该程序并且产生一个汇编输出文件，反编译器利用签名信息以减少需要反编译的子程序数目 (即，反编译器不尝试反编译已通过签名或装载器得到识别的库例程)，后期处理器把反编译输出的高级程序转换成一个语义等价的程序——使用目标语言明确的控制结构。实际上，反编译器可以把一个二进制程序或者一个汇编程序作为输入，并产生一个高级语言程序输出。大多数反编译器文献使用后一种方法：用一个汇编语言源程序。这篇论文专注于把二进制程序作为源输入，而它提供的信息远比汇编程序少得多。

在这篇论文中所描述的技术一般来讲足够为不同的机器体系结构建造反编译器。几个阶段被组合成 3 个不同模块，将机器和语言依赖的特征分离：前端是机器依赖的模块，它对作为源输入的二进制程序做语法分析，并且产生该程序的低级中间表示法以及每个子程序的控制流图；通用的反编译机器是一个机器和语言独立的模块，它分析中间代码和图的结构，并且生成该程序的一个高级中间表示法和结构化的图；后端是目标语言依赖的模块，它从中间表示法和图的结构生成高级目标代码。这样，如果要给一个不同的机器建造一个反编译器只须为该机器编写一个新的前端即可，而如果要为一个不同的目标高级语言做一个反编译器也可以通过为该目标语言编写一个新的后端来实现。这个方法实际上会由于所选择的低级中间语言表示法而受到一定限制。

这篇论文的重要贡献是在通用的反编译机器中所进行的两类分析：数据流分析和控制流分析，它们把低级中间代码（类似机器码) 转换成一个高级中间表示法（类似 HLL)。数据流分析程序描述了基于编译器优化原理的优化技术——清除低级概念之条件码和寄存器，而且引进高级概念之表达式。这些技术包括有子过程间分析、寄存器泄漏和类型传播。控制流分析程序描述了用于确定程序隐含的高级控制结构的结构化算法。这些算法根据一组预先定义的、一般化的控制结构 (适用于大多数常用语言) 把图结构化。

本文所提出的这些技术在反编译器样机 dcc 中的实现充分说明其可行性。dcc 是一个以 DOS 操作系统和 Intel i80286 机器体系结构为目标的反编译器，它生成目标 C 语言程序。这个反编译器在 Unix 操作系统下的 DecStation 3100 机器上以及在 DOS 下的 Intel 机器上运行。dcc 利用编译器和库的签名识别，只反编译用户例程（如果可以反编译的话)，不反编译那些编译器启动例程和库例程。如果编译器签名没有得到确定，那么在源二进制程序中所有的子程序都要被反编译；有一些库例程和编译器启动例程无法被翻译成高级语言表示法，故而仅仅被反汇编。dcc 为每个子程序提供注解，而且可以通过命令开关让它生成该程序的位映像图、调用图、汇编文件输出、在每个子程序中高级指令和低级指令的数目统计、以及关于每个子程序的控制流图的信息。

反编译主要在计算机科学的两个领域中使用：软件维护与安全。在软件维护方面，反编译器被用来重新获得丢失的或无法获取的源程序代码，把用陈旧过时语言编写的一个代码翻译成一个更新的语言，把一个非结构化方式编写的旧代码 (即 spaghetti code) 转化成结构化方式，把应用程序移植到一个新的硬件平台，以及调试已知有 bug 的二进制程序。在安全性方面，反编译器被用来为安全关键的系统验证二进制程序和编译器生成的代码的正确性；这里不能完全信赖编译器一定会为你生成正确的代码；以及检查有无恶意代码，比如病毒。

反编译研究的未来工作可以在两个领域中进行：代码与数据的区分，和数据类型的确定，比如数组、记录和指针。前一领域需要一个强健的方法来确定 n 路分支语句（即，变址的跳转) 和间接子程序调用。后一领域需要用启发式方法来识别不同的复合数据类型并且传播它们的数值。这些算法的有效实现将会让我们的反编译器跑得更快，尽管在通常情况下一个程序只须被反编译一次，因此对反编译速度的要求并不是十分关键。