Question

在过去 20 年中已经为编写反编译器做过各种不同的尝试。由于在编译过程中丢失了大量信息，为了能够再生成高级语言代码，所有这些实验的反编译器需要做一些限制，包括——汇编文件的反编译[Hou73, Fri74, Wor78, Hop78, Bri81]，有或没有符号调试信息的目标文件的反编译[Reu88, PW93]，简单化的高级语言[Hou73]，以及对编译器规约(compiler specification) 的要求 [BB91,BB93]。汇编程序有符号化文本形式的有用信息，比如数据段、数据和类型信息、子程序入口点、和子程序出口语句。所有的这些信息能够从符号表中收集，如此反编译器便不需要处理区分指令和数据，或者变量和子程序的命名问题。带有调试信息的目标文件包含编译器构造的程序符号表。假如有符号表，因为存放数据的内存单元确定以后，就很容易确定哪些内存单元是指令了。一般来说，目标文件包含的信息比二进制文件更多。最后，利用编译器规约是不实际的，因为编译器厂商通常不公开这些规约。

2.1 前人的工作

自从在 1960 年代首次使用以后，反编译器一直被认为是一个有用的软件工具。那时，反编译器被用来帮助从第二代计算机到第三代计算机的程序转换；如此免除了费时费力的为第三代机器重写程序的任务。在 70 年代和 80 年代期间，反编译器在程序的可移植性、文档编写、调试、遗失的源程序代码的重建、和现有二进制程序的修改等领域得到应用。在 90 年代，反编译器已经成为一个逆向工程工具，能够帮助使用者完成许多任务，诸如检查软件有没有非法代码、检验编译器是否生成正确的代码、以及把一个机器上二进制程序翻译成另一个机器上的。注意，反编译并没有被用于软件盗版或侵犯版权，因为这个方法还没有彻底成功，只能在一个具体任务中充当辅助工具。

下列描述举例说明最著名的反编译器以及个人或公司在反编译器方面的研究：

D-Neliac decompiler, 1960.

正如 Halstead 在[Hal62]中所言，Donnelly-Neliac (D-Neliac) 反编译器是在 1960 年由 J.K.Donnelly 和 H.Englander 在海军电子实验室(NEL) 制造。Neliac 是 NEL 在 1955 年开发的一个 Algol 类型语言。D-Neliac 反编译器从机器代码程序产生 Neliac 代码；为雷明顿兰德公司的 Univac M-460 伯爵夫人计算机和控制数据公司的 1604 计算机编写了不同版本。

事实证明，D-Neliac 可应用于把非 Neliac 编译的程序转换为 Neliac 程序，以及在原来的高级程序中检测逻辑错误。这个反编译器证明了编写反编译器的可行性。

W.Sassaman, 1966.

Sassaman 在 TRW 公司开发了一个反编译器，帮助从第二代计算机到第三代计算机的程序转换过程。这个反编译器以 IBM 7000 序列的符号化汇编程序做为输入并产生 Fortran 程序。因为符号化汇编程序中的信息更有用，所以不选择二进制代码作为输入语言。Fortran 在 1960 年代是一个标准语言，而且第二代和第三代计算机上都在使用它。被编译的程序类型是涉及代数运算的工程应用。使用者需要为子程序的识别定义规则。反编译器达到 90%正确率，需要一些人工干预 [Sas66]。

这是第一个使用汇编程序而非纯二进制代码作为输入的反编译器。汇编程序包含名字、宏、数据和指令形式的有用信息，在二进制程序或者可运行程序中是没有这些信息的，因此避免了在反编译器的语法分析阶段区分数据和指令的问题。

M.Halstead, 1967.

洛克希德导弹与空间公司(LMSC) 在海军电子实验室开发的 Neliac 编译器上做了一些增强，以照顾反编译的需要 [Hal67]。LMSC Neliac 反编译器以 IBM 7094 上的机器代码作为输入，产生 Univac 1108 机器的 Neliac 语言代码。它证明成功地反编译 90%以上的指令，让程序员去反编译剩下的 10%。这个反编译器在 LMSC 使用，遵守美国和加拿大的消费者合同 [Hal70]。

Halstead 分析，如果要把正确反编译的指令比例从一半提高到 100%则需要在实现上做更多工作，而且发现它和已经付出的努力近乎相等 [Hal70]。这是因为那里的反编译器只处理直接明了的情况，而较难的情况被留给程序员去考虑。为了处理更多的情况，需要花更多的时间为这些特殊情况编写编译器代码，而且跟简单情况相比编写代码所需时间也成比例地增加。

Autocoder to Cobol Conversion Aid Program, 1967.

Housel 详细描述了在 IBM 上开发的一套商业反编译器，把自动编码语言(Autocoder) 的程序——定位于商业数据处理——翻译成 Cobol。其转化是一对一映射，因而需要手工优化。最后程序的尺寸是原来程序核心存储的 2.1%倍。

这个反编译器确实是一种语言到另一种语言的翻译工具。没有尝试分析程序和减少生成的指令数。一般来说生成的代码执行效率比较低。

C.R.Hollander, 1973.

Hollander 的博士学位论文 [Hol73] 描述一个反编译器，它的设计围绕一个规则化的面向语法的元语言，而且有 5 个相互合作的顺序过程；初始化器、扫描器、语法分析器、构造器和生成器；各自实现为一个元规则组的解释程序。该反编译器是一个元系统，通过实现解释程序来定义它的操作。

初始化器把程序装入而且把它转换成一个内部表示法。当发现一个指令区域的时候，扫描器跟初始化器交互；当匹配源程序代码模板与指令的时候，扫描器跟语法分析器交互。语法分析器在源语言的语法短语和它们语义对等的目标语言之间建立对应。最后，构造器和生成器生成最后的程序代码。

实现了一个实验的反编译器将一个 IBM 的 System/360 汇编子集翻译为一个类 Algol 的目标语言。这个反编译器用斯坦福大学开发的一个编译器 Algol-W 编写，而且在 10 个测试程序上正确地工作。

这个工作提出一个新奇的反编译方式，使用一个拘泥规则的面向语法的元语言，但它的主要缺点也正是这个方法学，相当于从汇编指令到高级指令的模式匹配操作。因为需要按照特定的顺序识别一个指令是否属于某一个模式，所以限制了能够被反编译的汇编指令数量；没有考虑中间指令、各种不同的控制流模式或者优化代码。为了使面向语法的反编译器能够工作，需要列举每个不同编译器每一个高级指令的所有可能模式集合。另一方法是为一个特定的编译器编写一个反编译器，而且利用其编译器规约；仅当编译器作者愿意公开他的编译器规约的时候，这个方法才有可能实现。显然，Hollander 的反编译器可以这样做，因为 Algol-W 编译器是在他做这项研究时所在的大学研制的，他知道这个编译器规约。这样，由任何一个 Algol-W 指令生成的汇编指令组是已知的。

B.C.Housel, 1973.

Housel 的博士学位论文 [Hou73] 描述一个有条理的反编译方法，它借用编译器、图、和优化理论的概念。他的反编译器包括三个主要的步骤：部分汇编，分析器和代码生成。

部分汇编阶段从指令中区分数据，建立一个控制流向图，而且产生一个程序的中间表示法。分析器分析该程序以便发现程序循环并且清除掉不必要的中间指令。最后，代码生成器优化算术表达式的翻译，而且为目标语言生成代码。

编写了一个实验的反编译器，针对 Knuth 的 MIX 汇编器(MIXAL)，产生 IBM 370 机器适用的 PL/1 代码。测试了 6 个程序，88%的指令是正确的，而其余 12%的指令需要人工干预 [HH73]。

这个反编译器证明，通过使用已知的编译器和图的方法，可以实现生成良好高级代码的反编译器。中间表示法的使用使得分析完全不依赖机器。这个方法学的主要缺陷在于源语言的选择，MIX 汇编语言，在这些程序中不仅带有大量可用信息，而且它是一个简单化的、非现实的汇编语言。

The Piler System, 1974.

Barbe 的 Piler 系统尝试成为一个通用的反编译器，在许多不同类别的源-目标语言对之间进行翻译，以帮助计算机程序的自动化转换。Piler 系统由三部分组成：解释、分析和转换。这样，可以为不同的源机器语言编写不同的解释程序，而且可以为不同的目标高级语言编写不同的转换器，使得编写不同的源-目标语言对的反编译器比较容易。这个反编译器也被用于文档编写、调试辅助以及评估编译器生成的代码。

在解释期间，源的机器程序被装入内存储器，经过语法分析，转换成一个三地址微型表示法。也就是说，每一个机器指令需要一个或多个微型指令。分析器使用数据流分析确定程序的逻辑结构，而且修改其微型表示法成为一个中间表示法。经过这一分析以后使用者得到该程序的一个流程图，而且如果其中有什么错误，他们甚至能代表反编译器修改流程图。最后，转换器生成目标高级语言的代码 [Bar74]。

虽然 Piler 系统尝试成为一个一般化的反编译器，但是只编写了一个用于 GE/Honeywell 600 计算机机器语言的解释程序，以及 Univac 1108 机器 Fortran 和 Cobol 语言的程序轮廓转换器。这个项目主要致力于分析器。

Piler 系统为较多类别的源和目标语言编写通用反编译器的第一个尝试。它的主要问题是尝试使用一个甚至比一个汇编类型表示法更低级的微型表示法实现相当程度的一般化。

F.L.Friedman, 1974.

Friedman 的博士学位论文描述一个反编译器，用于在相同体系结构等级内的小型计算机操作系统的迁移 [Fri74]。描述了四个主要部分：前期处理器、反编译器、代码生成器、和编译器。

前期处理器把汇编代码转换成一个标准形式 (描述的汇编语言)。反编译器读入标准的汇编语言形式进行分析，并且把它反编译成一个内部表示法，然后由代码生成器从中产生 FRECL 代码。最后，一个 FRECL 编译器把这个程序编译成另一个机器上的机器代码。FRECL 是一个用于程序迁移和开发的高级语言；它是 Friedman 开发的，而且也为它编写了一个编译器。在这个工程中使用的反编译器是 Housel 反编译器的一个改写版 [Hou73]。

进行过两个实验；第一个实验把 IBM 1130 Disk Monitor System 一个自包含的小部分迁移到 Microdata 1600/21；在输入的汇编程序上需要最高达到 33%的人工干涉。总体来说，为迁移系统准备输入代码需要做太多的工作，无法在合理的时间量上完成；因此，做了第二个实验。第二实验反编译 Microdata 1621 操作系统程序成 FRECL 程序，并且把它们再编译成 Microdata 1621 机器代码。产生的一些程序被重新插入操作系统内并进行测试。平均上，只有 2%的输入汇编指令需要人工干预，但是最后机器程序的机器指令数有 194%的增长。

这个论文是反编译操作系统代码的第一个尝试，而且它例证了在反编译机器依赖的代码时反编译器面对的困难。这个迁移系统需要对输入程序做大量格式化工作，而且看起来，最后产生的程序由于包含更多机器指令造成在空间利用和执行时间上效率都很低。

Ultrasystems, 1974.

Hopwood 详细描述了 Ultrasystems 公司的一个反编译工程，他是该公司的一个系统设计顾问 [Hop78]。这个反编译器作为 Trident(三叉戟) 潜艇射击控制软件系统的一个文档编写工具。它以 Trident 汇编程序作为输入，而且产生这个公司开发的 Trident 高级语言(THLL) 程序。分成四个主要阶段：规格化、分析、表达式凝聚(expression condensation) 和代码生成。

输入的汇编程序经过规格化以便区别数据区域和伪指令。产生一个中间表示法，并分析数据。在表达式凝聚过程期间建立算术表达式和逻辑表达式，最后通过和 THLL 匹配控制结构生成输出的高级语言程序。

这个工程尝试通过把汇编程序转换成高级语言来为其编写文档。事实上，由于该工程的时间原因，没有为表达式凝聚阶段编写代码，因而一个单一的表达式需要几个指令，以致输出的程序很难读懂。

V.Schneider and G.Winiger, 1974.

Schneider 和 Winiger 提出指定高级语言的编译与反编译规格这样一个观念。通过为编译过程定义一个无语境(context-free) 语法 (即，描述从表达式和赋值产生的所有可能的二地址目标代码(2-address object code))，文章说明怎样通过反转这个语法来把目标代码反编译成最初的源程序 [SW74]。甚至，一个语义含糊的编译语法会产生最理想的目标代码，而且会产生一个语义不含糊的反编译语法。一个案例研究说明，用 Algol 60 构造产生的目标代码无法被反编译出确定的结果。这个工作是一个未最终完成的反编译器，但是在文献中没有发现关于它的更多信息。

这个工作提出以另一种方式实现的一个面向语法的反编译器 [Hol73]；亦即，反编译器使用一系列目标指令的模式匹配来重建最初的源程序。在这个方式中，为了反转语法并产生一个反编译语法，必须已经了解编译语法。注意，除非已把它定义为编译语法，否则不可能做最优化。

Decompilation of Polish code, 1977, 1981, 1988.

在这个文献中发现两篇反编译领域的文章，是关于波兰代码(Polish code) 转化成 Basic 代码。问题的出现与高度交互式系统有关，这类系统要求快速响应用户的每个输入。用户的程序保存为一个中间形式，然后要每次“反编译”一个命令。它给出一个从逆波兰表示法到表达式的翻译算法 [BP79]。

第二篇文章提出反编译过程分两步骤：需要将机器码转换成波兰表示法，和波兰代码到源形式的转换。该文专注于在反编译问题的第二个步骤，但还是声称使用一个波兰表示法的无语境语法和一个左到右或者右到左的语法分析模式，把波兰代码反编译成 Basic 代码 [BP81]。

这个技术最近被用于一个把逆波兰代码转换成电子表格表达式的反编译器 [May88]。在这个例子中，一个含有类似电子表格组件的产品的程序员为了让他的产品提速，希望把用户的表达式储存为一个编译的形式——在这个例子中就是逆波兰表示法，并且每当用户想看或修改它们的时候它就反编译这些表达式。圆括号被留下作为逆波兰表示法的一部分以便重建与用户输入系统的精确相同的表达式。

从这个意义上讲，用反编译这个词是不正确地使用术语了。在这些文章中提到的一切是重建或逆语法分析最初的表示 (用 Basic 编写或电子表格表达式)——提供一个程序的中间波兰表示法——的一个方法。在波兰到 Basic 翻译器这个例子中，没有说明关于如何得到这样一个提供一个机器程序的中间表示法。

G.L.Hopwood, 1978.

Hopwood 的博士学位论文 [Hop78] 描述了为可迁移性和文档编写设计的一个 7 步反编译器。它宣称反编译过程可以借助人工干涉或其他外部信息。

反编译器的输入程序用一个预处理程序格式化，然后装入内存，而且建立该程序的一个控制流向图。这个图的结点代表一条指令。在构造该图之后，控制模式被识别，而且通过结点分割法或人造变量的引入把产生 goto 语句的指令清除掉。然后源程序被翻译为一个中间机器独立代码，而且为了寻找表达式并通过一个向前代入的方法清除不必要的变量，在这个表示法上做变量使用(variable usage) 分析。最后，为每一个中间指令生成代码，目标语言不支持的操作则用函数实现，而且提供注解。需要人工介入准备输入数据，在翻译过程当中给反编译器提供它需要的额外信息，和对目标程序做修改。

为 Varian Data 机器 620/i 编写了一个实验的反编译器。它把汇编程序反编译成 MOL620，这是 M.D.Hopwood 和该作者在 Irvine 市的加州大学开发的一个面向机器的语言。反编译器用一个大的调试器程序 Isadora 进行测试，该程序是用汇编语言编写的。所生成的反编译程序被手工修改以再编译成机器代码，因为其中有调用中断服务例程、自修改代码、和为了子程序调用而使用的额外寄存器。最后的程序比原来的汇编程序有更好的文档说明。

这项研究的主要缺点是控制流向图的粒度和在最后的目标程序中寄存器的使用。关于前者，是指 Hopwood 选择了建立每个指令一个结点的控制流向图；这就是说，大程序的控制流向图尺寸相当大，而且跟使用基本块结点 (即，结点的大小依赖控制流改变的次数) 相比没有任何优越性。关于后者，MOL620 语言允许机器寄存器的使用，而且在 Hopwood 的论文中举例的样本代码显示，寄存器被用作表达式的一部分和子程序调用参数。寄存器的概念并非在高级语言中可用的高级概念，而且如果想要生成高级的代码的话不应该使用它。

D.A.Workman, 1978.

这项成果描述了在为实时训练装置系统设计适用的高级语言时反编译的应用，尤其在 F4 教练机 [Wor78]。F4 的操作系统是用汇编语言编写的，因此这个反编译器的输入语言是汇编语言。由于这个工程的目标是用于设计，因此没有确定输出语言，没有实现代码生成。

反编译器的两个阶段被实现：第一个阶段，把汇编程序映射为一个中间语言并收集关于源程序的统计信息，而第二个阶段产生基本块的控制流向图，依据它们的可能类型来划分指令，并且分析控制流以确定高级控制结构。结果表明高级语言需要能够处理位元串，支持循环和条件控制结构，而且不需要动态的数据结构或递归。

这项成果提出一种新奇的反编译技术应用，尽管输入语言是汇编语言而非机器码。通过把指令分类来做简单的数据分析，但是没有尝试完全地分析它们，因为这里不需要生成高级代码。控制流分析是完全的而且考虑 8 个不同的循环类别和二路条件语句。

Zebra, 1981.

在海军水下系统中心开发的 Zebra 样机试图实现汇编程序的可移植性。Zebra 把 ULTRA/32 汇编语言一个名叫 AN/UYK-7 的子集作为输入语言，而且产生 PDP11/70 的汇编程序。D.L.Brinkley 在[Bri81]中描述了这一工程。

Zebra 反编译器由 3 趟组成：词汇和流分析，这一趟解析程序而且在基本块的图中做控制流分析。第二趟是关于把程序翻译为中间形式，而第三趟通过清除多余的读写(loads and stores) 使中间表示法简单化，跟 Housel 描述的方法大同小异 [Hou73,HH73]。

总的来说，获取程序的语义很难，而且这个反编译不经济实用，不过在迁移过程中它能提供一定的帮助。

这个工程利用已知技术来开发一个汇编程序反编译器。这项研究没有引入新的概念，但是它提出一个观点，认为反编译应该作为一个工具帮助解决某个问题，而不是完全解决该问题的工具，因为假如反编译器不可能达到 100%正确。

Decompilation of DML programs, 1982.

数据库代码的反编译器被设计用来把 Codasyl DML 程序的一个子集——用程序性操作编写——转换成一个带有非程序性查询规格(nonprocedural query specification) 的关系系统。一个存取路径模型(Access Path Model) 被引进来解释该程序所执行的语义上的存取。为了确定 FIND 操作如何实现语义上的存取，在控制流向图上做一个全局数据流延伸分析，而且把操作匹配到模板。最后的图结构被再映射成一个关系结构。这个方法依赖对象的逻辑顺序和 DML 语句的一个标准顺序 [KW82]。

在参考文献[DS82]中提议另一个数据库代码反编译器，把精心编码的应用程序反编译成该文中提议的一个语义表示法。这项成果主要是通过改变一个数据库管理系统(DBMS) 的应用需求，其中应用程序用 Cobol-DML 语言编写。一个 Cobol-DML 程序反编译器用来分析和把应用程序转换成一个与模型和（数据库) 模式无关的表示法。这个表示法稍后被修改或重新结构化以说明数据库改变。语言模板被用来匹配一个 Cobol-DML 程序的关键指令。

对于数据库环境而言，反编译是组织一系列语句的过程，将一个查询用另一个 (非程序性的) 规格来表现。需要数据流分析，但是没有为这个类型的应用实现反编译器的所有其它阶段。

Forth Decompiler, 1982, 1984.

一个递归的 Forth 语言反编译器是扫描一个编译字典条目而且把单词反编译成原语和地址的一个工具 [Dud82]。这样的反编译器被认为 Forth 语言工具箱中最有用的工具之一 [HM84]。该反编译器实现一个递归降序的语法分析器以便反编译的单词能够以一个递归方式被反编译。

这些成果提出一个逆语法分析工具而不是一个真正的反编译器。该工具递归地扫描一个字典表并且返回与给定单词有关的原语或地址。

Software Transport System, 1985.

C.W.Yoo 描述了一个自动化软件迁移系统(STS)，它把汇编语言代码从一个机器移到另一个机器。该过程包括把机器 m₁的一个汇编程序反编译成一个高级语言，和在机器 m₂上把这个程序编译成汇编程序。一个实验的反编译器在 Intel 8080 体系结构上开发；它以汇编程序作为输入并且产生 PL/M 程序。再编译的 PL/M 程序比它们原来的汇编程序提高效率达 23%。一个实验的 STS 被用于为 Z-80 处理器开发一个 C 语言交叉编译器(C cross-compiler)。该工程遇到在 STS 中缺乏数据类型的问题 [Yoo85]。

STS 把机器 m₁的一个汇编程序和机器 m₂的一个汇编语法作为输入，而且为机器 m₂产生一个汇编程序。输入语法经过语法分析所产生的表被抽象语法树语法分析器用来解析该输入汇编程序，而且生成该程序的一个抽象语法树(AST)。这个 AST 是反编译器的输入，然后执行控制流分析和数据流分析，跟 Hollander [Hol73]、Friedman [Fri74] 和 Barbe [Bar74] 描述的方法大同小异，而且最后生成高级代码。然后为机器 m₂编译该高级语言。

这项成果没有提出任何新的反编译领域研究，但是提出一个新颖的汇编程序迁移方法——它使用一个描述目标体系结构汇编指令的语法。

Decomp, 1988.J.

Reuter 编写 decomp，一个用于 Vax BSD 4.2 的反编译器，把带有符号信息的目标文件作为输入并且产生类似 C 的程序。这个反编译器的性质是在没有可用源代码的情况下把帝国游戏(Empire) 移植到 VMS 环境。该反编译器可从因特网上免费获取 [Reu88]。

Decomp 使用符号表来寻找函数的入口点，确定在程序中被使用的数据，和那个数据的名字。按以下方式，一次反编译一个子程序：基本块的一个控制流向图被建立并且最优化——去掉通向中间无条件分支的弧。在该图中做控制流分析，寻找高级控制构造，把控制流向图转换成一个一般化构造的树。这个分析使用的算法来自 struct 程序，这是一个把从 Fortran 程序产生的图进行结构化的程序，该算法是基于 B.Baker 在[Bak77]中描述的结构化算法。最后，在树里的一般化构造被转换成 C 语言特有的构造，而且产生代码。最后的输出程序需要手工修改，把参数放在子过程的参数列表上，以及确定一个子程序是否返回一个数值（亦即，一个函数)。这个反编译器大约花了 5 人月编写完成的 [Reu91]。

样本程序是在一个 Vax BSD 4.2 机器上用 C 编写并编译的，感谢 Pete French 的协作 [Fre91]，他给我提供了在一台 Vax BSD 4.2 机器上的一个账户。产生的 C 语言程序需要经过一些手工编辑才可以再编译。该程序有正确的控制结构——归功于他实现的结构化算法，也有变量的正确数据类型——归功于在目标代码中有嵌入的符号表。库例程和子过程的名字，以及用户程序入口点也都从符号表可知；因此，没有反编译外来的子过程 (例如，编译器启动代码、库例程)。数据流分析阶段是十分必要的，即使，既没有表达式和实际参数也没有函数返回值被确定。子过程间的数据流分析可以为再编译输出程序节省许多必需的手工编辑。

exe2c, 1990.

Austin Code Works 赞助 exe2c 反编译器的开发，目标是运行 DOS 操作系统的 PC 兼容系列计算机 [Wor91]。该工程在 1990 年 4 月正式公告 [Gut90]，经过大约 20 人测试，并决定它在反编译成 C 语言代码上需要做更多工作。一年后，该工程达到一个β操作级[Gut91a]，但是再没有完成 [Gut91b]。我是它的一个 beta 版测试者。

exe2c 是一个多趟反编译器，由三个程序组成：e2a、a2aparse 和 e2c。e2a 是反汇编器。它将可运行文件转换成汇编程序，而且也产生一个有注解的汇编列表。a2aparse 是汇编语言到 C 语言的前端处理器，它分析由 e2a 产生的汇编程序文件，而且生成.cod 文件和.glb 文件。最后，e2c 程序翻译由 a2aparse 准备的文件并且生成伪 C 语言程序(pseudo-C)。还提供一个集成环境 envmnu。

exe2c 反编译的程序使用一个定义寄存器、类型和宏的头文件。输出的 C 程序依靠寄存器和条件码 (表现为布尔变量)，所以不易理解。通常，一个机器指令被反编译成一个或多个需要对寄存器进行操作和设置条件码（如果指令需要的话) 的 C 指令。没有确定表达式和子程序参数，而且最后的 C 程序使用一个局部栈。从这个输出代码看出，显然在 exe2c 中没有实现数据流分析。这个反编译器已经实现一个控制流分析阶段；可以应用循环构造和条件构造。尽管 case 表没有被正确地检测，控制结构的选择一般来说还可以的。被反编译的子过程的类型和数目说明，在程序中发现的所有库例程以及编译器启动代码和运行时支持例程都被反编译。这些例程的性质通常是低级的，因为它们通常是用汇编语言编写的。大多数情况下，这些例程很难被反编译成对应的高级代码 (除非低级类型的 C 代码)。

这个反编译器是在许多年中反编译可运行文件的第一个努力。其成果说明，为了产生更好的 C 代码需要做一个数据流分析和启发式。而且，建立一个忽略所有由编译器引进的外来代码和发现库子程序的机制会很有帮助。

PLM-80 Decompiler, 1991.

澳大利亚国防部的信息技术司研究反编译的国防应用，比如废弃代码的维护、科技情报产品、以及安全或保密风险的系统评估。S.T. Hood 在[Hoo91]中描述了这个工作。

它描述了建造反编译器的技术，在一个 Prolog 环境中使用有限子句语法(definite-clause grammar)——一个扩展的无语境语法。一个 Prolog 数据库被用来储存最初的汇编代码和该语法的公开句法结构。反编译器样机是用 Prolog 语言编写的，它适用于由 PLM-80 编译器编译的 Intel 8085 汇编程序。该反编译器产生 Small-C 语言的目标程序，它是 C 语言的一个子集。在这个报告中给出的有限子句语法能够识别 if..then 类型结构，和 while() 循环，以及简单类型 (即，字符型、整型和长整型) 的静态 (全局) 变量和自动 (局部) 变量。有一个图形化用户界面用于显示汇编程序和伪 C 程序，而且让使用者能够赋予变量名字和加注解。这个界面也向使用者询问主程序的入口点，并且允许他选择要识别的控制构造。

这个反编译器所做的分析局限于控制结构和简单数据类型的识别。没有对寄存器的使用做分析或提及。自动变量用一个索引变量表示——它表现栈。图形化界面帮助用户以注解和有意的变量名字的形式给反编译的程序增加说明。这个分析不支持被最优化的代码。

Decompiler compiler, 1991-1994.

反编译器编译器是一个工具，以一个编译器规约和目标代码的相应部分作为输入，并且返回一个反编译器的代码；即，它是一个制造反编译器的自动方法，跟 yacc 制造编译器的方法有很多相同之处 [BBL91, BB91, BB94]。

描述了产生这个反编译器编译器的两种方法：一个逻辑程序设计方式和一个函数型程序设计方式。前一方式利用逻辑程序设计语言比如 Prolog 语言的双向性，而且逆推编译器规约以获得一个反编译器 [BBL91, BB91, BBL93]。理论上，这是正确的，但是在实践中这个方法中受制于 Prolog 解释程序的实现，因而遇到严密性和可反转性问题 [BB92,BB93]。后一方式基于逻辑方式但是 lazy 函数型程序设计语言如 Haskell 语言，产生一个比较有效率的反编译器 [BBL91, BB91, BBL93]。即便使用一个 non-lazy 函数型语言，也可以用对象的形式模拟 lazy 而不是用列表的形式。

由一个反编译器编译器产生的反编译器将以目标代码作为输入，并且返回可以被编译成给定目标代码的一个源代码列表。为了实现它，需要针对一个任意的遗传属性语法 (inherited attribute grammar) 枚举所有可能的源代码。事实证明，这样的一个枚举等价于停机问题 [BB92, BB93]，因而是不可计算的。更有甚者，没有一个可计算的方法读入一个属性语法描述并且决定，对于该属性的一个给定值，被编译的代码是否将给出一个有尽的枚举 [BB92, BB93]，所以关于哪些语法可以使用并不是直接明了的。因此，这个方法可接受的语法类别必须局限于那些能够产生一个完全枚举的语法，比如非左递归的语法。

这个方法的首次实现是使用一个函数型程序设计语言、为一个类似 Occam 语言的子集。反编译器语法是一个遗传属性语法，把有意选择的目标代码作为一个参数 [BB92,BB93]。也基于编译器规约描述了一个 Prolog 语言反编译器。这个反编译器以一个选择性的和顺序的方式应用编译器的条款(clause)，以免遭遇不终止的问题，而且只返回源代码程序的一个子集 (而非一个无穷的列表) [Bow91, Bow93]。由于函数型方式和逻辑方式的低效率，这个方法最近使用命令式程序设计语言 C++了。在这个样机中，C++对象被当作 lazy 列表使用，而且编写了一组库函数来实现所使用的中间表示法的操作码 [BB94]。关于优化代码的问题已经被检测。

正如这项研究举例说明的，只要知道编译器规约集合和为规约的每个条款产生的目标代码，反编译器编译器就能够自动地被建造。一般来说事情没这么简单，因为编译器作者不公开他们的编译器规约。只有用户定义的编译器和反编译器可以用这个方法建造。也要注意，这个方法不处理被编译器最优化阶段产生的最优化，而且用这个方法建造的反编译器不能反编译真实的可执行程序。没有解决数据和指令的区分问题，以及确定在可运行程序中所使用的变量的数据类型的问题。总之，如果已经了解某个编译器产生的目标代码，那么就能够自动生成它的反编译器编译器，但是所生成的反编译器不能反编译任意的可执行程序。

8086 C Decompiling System, 1991-1993.

这个反编译器以来自 DOS 环境的可运行文件作为输入，而且产生 C 语言程序。输入文件必须是用 Microsoft C 5.0 版本小存储器模型编译的 [FZL93]。描述了五个阶段：库函数的识别、符号执行、数据类型识别、程序转换和 C 语言代码生成。库函数的识别和中间语言在[FZ91,HZY91]中有更多描述。

Microsoft C 的库函数的识别用来清除属于库的子程序，如此只为使用者例程产生 C 语言代码。反编译系统有一个内建的 C 语言库函数表。为每一个库函数，储存它的名字、特征代码 (该函数中区别于其它函数的指令序列)、在特征代码中的指令数目，以及识别该函数的方法。这是反编译器作者手工制作的。符号执行将机器指令翻译成中间指令，而且用它的符号内容表示每个指令。数据类型的识别是通过一组对于不同数据类型的信息收集规则和用于确定数据类型的分析规则完成的。程序转换把存储计算转变成地址表达式，例如数组寻址。最后，C 语言代码生成器通过发现控制结构而转换程序结构，并且生成 C 语言代码。

这个反编译系统利用库函数识别产生更可读的 C 语言程序。库函数通过手工识别，因此，如果用编译器的其它版本、其它存储器模型或其它编译器编译最初的程序，识别工作效率较低。数据类型的识别是对数组、指针和结构类型识别的第一次尝试，但是这篇文章里没有详细说明。没有描述如何在中间代码中构成一个地址表达式，而且没有举例说明最后 C 程序的质量。

Alpha AXP Migration Tools, 1993.

在数字装备公司(Digital Equipment Corporation) 设计 Alpha AXP 体系结构的时候，AXP 团队参与一个工程项目——在新的 Alpha AXP 计算机上运行现有的 VAX 和 MIPS 代码。他们选择了一个二进制翻译器，能把旧体系结构的指令序列转换成新体系结构的指令序列。此过程需要完全自动化，而且需要照顾到在执行期间创建或修改代码的需要。移值过程定义为两个部分：二进制翻译和运行时环境 [SCK+93]。

二进制翻译阶段读入二进制程序并且把它们翻译成 AXP 操作码。它使用反编译技术了解机器指令的潜在含义。进行条件码使用分析，因为这些条件在 Alpha 体系结构上不存在。并通过分析代码，确定函数返回值以及寻找 bug (例如，未初始化的变量)。MIPS 有标准的库例程——嵌入在二进制程序中。对于这种情况，一个模式匹配算法被用来检测例程是否库例程——这些例程不被分析而是用它们的名字代替。寻找成语并且用一个最理想的指令序列代替它。最后，代码以 AXP 操作码的形式生成。新的二进制文件包含新代码和旧代码二者。

运行时环境执行翻译的代码而且做为在新旧操作系统之间的一个桥梁 (例如，不同的调用标准、异常处理)。它有一个内建的旧代码解释程序，用来运行在翻译时没有发现或不存在的旧代码。这是可以的，因为旧代码也作为新的二进制文件的一部分被保存。

编写了两个二进制程序的翻译器：VEST 从 OpenVMS VAX 系统翻译到 OpenVMS AXP 系统，和 mx 将 ULTRIX MIPS 映像翻译成 DEC OSF/1 AXP 映像。这些翻译器的运行时环境分别是 TIE 和 mxr。

这个工程举例说明在一个现代翻译系统中反编译技术的使用。证明对于众多类别的二进制程序来说它是成功的。一些无法翻译的程序是在技术上不可翻译的程序，比如使用特权操作码的程序或者以超级用户特权运行的程序。

Source/PROM Comparator, 1993.

这是英国核电子股票上市公司开发的一个工具，论证源代码和 PROM 内容的等价，用于验证从 PL/M-86 程序到 PROM 程序的正确翻译，这些程序要在安全关键的计算机控制系统上运行 [PW93]。

可以被看成三阶段：从 PROM 文件再组织目标代码文件，借助从源代码建立的一个名字表把目标代码反汇编成一个类似汇编形式，以及汇编程序的反编译并且与最初源代码进行比较。注意，在反编译阶段必须清除中间跳转、寄存器和栈操作，识别子过程参数，解决结构、数组和指针的索引，而且将表达式转换成一个规格形式。为了比较最初的程序和反编译的程序，使用了一个中间语言。使用一个商业产品把源程序翻译成这个语言，而且反编译阶段的输出也是用相同的语言编写。该工程证明，对于被分析的这个特定的安全系统而言，它是验证翻译代码正确性以及论证那些用来创建程序的工具 (编译器、链接器、优化器) 行为可靠性的一个实际方法。

这个工程描述了反编译技术的一个应用，帮助论证在一个安全关键的系统中高级代码和低级代码的等效。借助从最初源程序构造的一个符号表，反编译阶段进行许多分析。通过对编译高级程序所使用的编译器的了解，任务得以简单化。

在去年内，商业的特定厂商反编译器已经被制造出来。这些反编译器针对数据库语言，生二进制文件的反编译，比如 Clipper和 FoxPro。它们的厂商没有提供用于反编译这些程序的技术信息。下面列表提到其中一些商业的反编译器：

Valkyrie, 1993.

用于 Clipper Summer '87 的可视化反编译器，CodeWorks 制造 [Val93]。

OutFox, 1993.

用于加密的 FoxBASE+程序的反编译器 [Out93]。

ReFox, 1993.

反编译加密的 FoxPro 文件，Xitech 公司制造 [HHB+93]。

DOC, 1993.

用于 AS/400 和 System/38 的 COBOL 反编译器。把目标文件程序转换成 COBOL 源程序，然后可以由程序员修改。Harman Resources 制造 [Cob93].

Uniclip, 1993.

用于 Clipper Summer '87 EXE 文件的反编译器，Stro Ware 制造 [Unc93]。

Clipback, 1993.

用于 Summer '87 可执行文件的反编译器，Intelligent Information Systems 制造 [Unc93]。

Brillig, 1993.

用于 Clipper 5.X .exe 文件和.obj 文件的反编译器，APTware 制造 [Bri93]。