Author: MalwareBenchmark

0x00 简介

《编译原理》课程在大学本科阶段就难道了很多计算机专业的同学。而反编译技术更需要从事者具有深厚的编译技术基础,因此一直是很多业内人士希望能够深入了解和掌握的一门技术。

从现在开始,我们讨论反向编译的一些内容。顾名思义,反编译可以认为是编译的逆过程,这一点从编译和反编译(Compile and De-compile,英文中也有用De-compilation来表示反编译的)的中英文描述都可看出。但这看似只有一字之差的名称,在实际应用中并不是简单的“逆流而上”。因为在多数时候“创造”远比“恢复”来得简单,就好像您不小心打碎了家里的花瓶,想要通过修复和粘接把碎片恢复成原样,几乎是不可能办到的。即便能够基本复原,但粘接的花瓶与它原来的样子也不会完全一样。与碎片到花瓶的变化类似,反编译过程远比编译过程复杂和繁琐,而且反编译的结果也远远不如您原来编写的代码那么“美妙”。但是反向编译却能在程序功能分析、恶意代码发现、二进制翻译等特殊工作中发挥重要作用,这也是笔者仍然致力于研究这一并不十分完善的技术的重要原因。

0x01 反编译的概念和基本过程


1.什么是反编译

在这一节里我们将对反编译做出一个基本的说明,给出反编译的概念,使读者们可以对反编译有一个初步的理解。我们给出的概念不是学术研究中严谨的定义,只是作者基于相关文献和多年来的研究心得所给出的一段说明。此外,我们还会揭示一个事实,尽管编译与反编译看起来是正反两项技术,但有趣的是:反编译器的编写方法却恰恰依赖于编译器的编写技术。

反编译概念

反编译技术是通过对低级语言代码(二进制代码或者汇编代码等)进行分析转化,得到等价的高级语言(不限制语言类型,本书的描述主要以C语言为例)代码的过程。它涉及指令系统,可执行文件格式,反汇编技术,数据类型分析技术,控制流分析技术和高级代码生成技术等。

编译与反编译

反编译的本质是编译的逆过程。从二十世纪五十年代第一个编译器出现开始,将机器码转换成为高级语言的期望就引发了人们广泛的兴趣。图1揭示了编译器同反编译器之间的关系。

可以看到编译器同反编译器都将程序从一种形式转换到另外一种形式,而且在转换的步骤中,都使用了类似的中间表示。差别只是在于编译器的总体方向是从源程序到机器码,而反编译器的总体方向则是从机器码到源程序。尽管在整体方向上两者是相反的,但编译器和反编译器往往在分析阶段使用类似的技术,例如数据流分析。

编译器通过对源代码进行解析得到中间表示(IR,intermediaterepresentation),反编译器通过对指令进行解码得到中间表示。类似的,编译器的低级代码生成同反编译器的高级代码生成恰好对应。

1-1

图1 编译器同反编译器在结构上的对应性

编译的过程为源程序打上了机器属性,比如CPU及寄存器的使用、机器指令的使用、以及内存地址的分配等;而反编译过程则需要剥离机器相关的细节,尽可能地区分指令和数据,通过逆向分析,重建高级数据结构和程序结构。

反编译器

反编译器是利用反编译技术实现的具体软件系统。它读入一个机器语言的程序(被编译器编译生成的二进制编码,即源语言),并把它翻译为一个等价的高级语言程序(即目标语言)。反编译器或反向编译器,尝试逆向一个编译器的过程,把一个二进制程序或可执行程序翻译成一个高级语言程序。它应用基本的反编译器技术,把多种多样的机器语言二进制程序反编译成某种高级语言。反编译器的结构是基于编译器的结构,而且应用类似的原理和技术进行程序分析。

2.反编译的基本过程

在这一小节,我们按照三种不同的分类,从多个角度阐述反编译的基本过程。

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

    1-2

    图2 按照反编译技术实施的顺序划分

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

    1-3

    图3 反编译操作

    以逆向分析为目的,反编译的各个阶段并不是一个严格的一遍顺序,而是存在着一些并行的模块,并且也需要通过循环执行分析过程来针对某些特殊问题(例如非N分支代码产生的间接跳转指令)进行分析和恢复。

  3. 反编译的处理过程,如果按功能区分,可以分为:前端、中端和后端三个部分。其实这种划分方式是将上述两种过程的阶段进行合并,也就是将几个反编译器阶段组合在一起。这样划分的好处是:通过设计不同的前端、中端和后端以实现针对多种源和目标的反编译器。

0x02 反编译的前世今生


1.建立——20世纪60年代

随着第一台计算机的诞生,硬件与软件就成了构成计算机系统的两个重要组成部分,它们相伴而生、相互促进,它们分工迥异、各司其职。为了使用和驱动不断演化的硬件系统,通过计算机语言来编写系统和应用程序的方式逐渐确立了主流的地位。伴随着高级编程语言的出现,第一代编译器也在20世纪50年代产生了,它实现了高级语言到机器代码的等价转换,完成了人类认知到机器“认知”的转换。而几乎与此同时,将机器码还原成为高级语言的逆向思考也引发了研究人员的求知欲望。

在第一代编译器出现十年之后的20世纪60年代,以小规模集成电路为特征的第三代计算机开始出现。由于其与第二代晶体管计算机的差异较大,使得运行在第二代计算机上的软件几乎面临着即将被全部淘汰的危险。然而基于当时的软件开发技术和开发成本,淘汰软件意味着巨大的损失。为了挽救这些价值不菲的软件,同时也为了加速开发第三代机器的软件,与软件移植技术相关的研究逐渐兴起,例如:程序转换器、交叉汇编器、翻译器、反编译器等。其中反编译器成了最初的研究热点。

1) D-Neliac——反编译器的开山祖师

一些美国公司和研究机构开始着手进行软件移植工具的研究,并且由美国海军电子实验室的J.K.Donally和H.Englander在1960年实现了第一代反编译器D-Neliacdecompiler。由此我们的反编译器鼻祖正式“粉墨登场”了,比它的兄弟“编译器”整整小了10岁。Donnelly-Neliac(D-Neliac)可以将机器代码反编译成Neliac(类似于Algol的一种编程语言,是NEL在1955年开发的一个Algol-Algorithmiclanguage类型语言)程序代码。

2) Sassaman的Fortran反编译器——不是一个人的江湖

无独有偶,1966年Sassaman在TRW公司开发了一个反编译器,该反编译器以IBM 7000序列的符号化汇编程序做为输入并产生Fortran程序,是第一个使用汇编程序而非纯二进制代码作为输入的反编译器。它是有据可查的第二个正式的反编译器,但是由于它以包含大量有用信息的符号化汇编程序作为输入,而省却了反汇编的过程,也因此降低了反编译的难度。这是第一个使用汇编程序而非纯二进制代码作为输入的反编译器。汇编程序包含名字、宏、数据和指令形式的有用信息,在二进制程序或者可运行程序中是没有这些信息的,因此避免了在反编译器的语法分析阶段区分数据和指令的问题。

又因为该反编译器的输出是1960年代的标准编程语言Fortran程序(第二代、第三代计算机上都在使用Fortran),所以使得它看起来更具有实用意义。该反编译器面向的是涉及代数运算的工程应用程序,使用者需要掌握一定的相关知识,并能够为子程序的识别自定义规则。在熟练的程序员干预下,该反编译器的正确率可以达到90%,因此它是属于少数人的“阳春白雪”。

3)Lockheed Neliac——开山祖师的传人

1967年,洛克希德导弹与空间公司在海军电子实验室开发的Neliac编译器上做了一些增强,我们称它为Lockheed Neliac。

反编译器LockheedNeliac与D-Neliac类似,它们都可将机器代码程序转换成Neliac程序代码,特别是它们可以将非Neliac语言生成的机器代码转换为Neliac程序代码。这一时期的反编译器采用模式匹配的方法进行反编译,把许多复杂的问题留给程序员手工解决。

4)小结——De-compiler的拓荒者们

整个60年代,反编译方面的研究主要集中在研制专门用途的反编译器上,并希望其可以作为软件移植的工具来使用。但是受限于当时计算机发展水平,以及体系结构的影响,这一时期的反编译器主要采用模式匹配的方法进行反编译,需要较多的人工干预;并且反编译的结果通常不经过优化处理,所以输出的结果代码效率较低、可读性较差。

从前边的叙述中可以看出,尽管从编译器被发明以来,人们就对编译的逆过程倍感兴趣,但真正迈出这关键的一步却是由于进行“软件移植”的诉求。那个年代的计算机程序停留在大型商业公司和高等院校的实验室里,只有很少的人能接触和掌握高级语言的编程,程序的复杂程度也较为有限,也没有大量出现病毒,因此利用反编译进行程序分析并没有那么重要。

2.发展——20世纪70年代

反编译技术建立初期,并没有很快成为通用的商业软件流行起来。大学校园的理论研究,成为推动这项技术发展的主要动力。下面我们按照时间的脉络,走进历史进程中的“象牙塔”,回顾一下反编译技术的发展过程。反编译理论方面的研究成为这个时期的热门,随着美国多位博士以反编译作为博士研究课题,一些对逆向编译和程序移植有一定影响的理论和技术被相继提出。在这个研究领域,豁然呈现出百花齐放的景象。

1)花开一朵——博士们的研究

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

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

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

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

2)花开二朵——反编译技术在工程上的应用

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

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

3)花开三朵——反编译技术在军事上的应用

反编译技术同样被军方慧眼识珠,在上世纪70年代多项军事应用中可以看到它的身影。

1974年,Ultrasystems公司的一个反编译工程中也用到了反编译器。这个反编译器作为三叉戟 (Trident)潜艇射击控制软件系统的一个文档编写工具。它以Trident汇编程序作为输入,产生这个公司开发的Trident高级语言程序。该编译器分成四个主要阶段:规格化、分析、表达式凝聚和代码生成。该系统的输入为经过“规格化预处理”的汇编程序,其目的是为了解决部分指令和数据的区分问题;与此同时,预处理过程还会生成一种中间表示,并对数据进行分析;然后,在表达式凝聚的过程期间,算术表达式和逻辑表达式将被还原并建立;最后,再通过和THLL(Ultra systems公司的名为Trident的高级语言)匹配控制结构,而生成输出的高级语言程序。

1978年,D.A.Workman主导了一项有军方背景的反编译应用研究,目的是为美国军方实时训练装置系统设计适用的高级语言。该应用在F4型教练机的相关设计中发挥了作用。F4教练机的操作系统是用汇编语言编写的,因此这个反编译器的输入语言是汇编语言。由于这项应用的目标是用于设计,因此没有确定输出语言,没有实现代码生成,仅仅实现了反编译器的两个阶段:阶段一,把汇编程序映射为一个中间语言并收集关于源程序的统计信息;阶段二,产生基本块的控制流向图,依据它们的可能类型来划分指令,并且分析控制流以确定高级控制结构。这项成果的贡献在于,提出了一种在当时看起来十分独特的反编译技术应用。即这个反编译器,并未以输出高级语言代码为最终目的,而是通过把指令分类来进行数据分析。从这一案例,可以看出反编译技术的先进性在当时得到了美国军方的认可,并且在实际应用中催生出了代码分析的功能,值得后续研究的借鉴。

4)小结

有了1960年代的技术积累,反编译技术在高等院校得到了理论和实践的双重推进。在理论研究的支撑下,越来越多的实用系统中都使用了反编译技术。以至于被大家公认的高科技技术集散地的美国军方,也将反编译技术投入到军事训练和实战中。因此,在1970年代反编译技术拥有自己完美的发展期,并获得了长足的进步。

3.瓶颈期——20世纪80年代

之所以将1980年代称为反编译发展的瓶颈期,主要是这项技术所能实现的功能的合法性问题。毕竟随着计算机的普及和发展,软件知识产权逐步被人们所重视。反编译技术可以逆向获得程序源代码的特性,与软件知识产权的保护存在着一定的矛盾。如何界定科学研究和非法获利,一时没有定论,但是这个十年中,相关研究也没有完全停滞,仍然有一些具有代表性的工作。

1) Zebra

1981年,美国军方的另一个反编译实例:美国海军水下系统中心开发的Zebra样机试图实现汇编程序的可移植性。Zebra的主要功能是把ULTRA/32汇编语言的一个名叫AN/UYK-7的子集作为输入语言,进而产生PDP-11/70的汇编程序输出。尽管Zebra并不是传统意义的反编译器,更像是单纯的程序移植和变换,但是该系统的实现方式与反编译并没有什么不同,即Zebra的实现主要由三大步骤构成。第一阶段,词汇和流分析:对原程序进行解析,并在基本块内做控制流分析;第二阶段,程序被翻译为中间形式;第三阶段,做中间表示的化简。

Zebra利用已知的技术来开发一个汇编程序的反编译器,整个研发过程并没有引入新的概念。但是Zebra提出一个观点值得我们回味,也就是说:从Zebra的研发过程中看出,反编译应该作为一个工具帮助解决某个问题,而不是完全解决该问题的工具。这个结论,源于科研人员对反编译的了解而提出的假设,即假如反编译器不可能达到100%正确。虽然这是一个上世纪80年代初就提出的论断,但我们仍然可以从中一窥反编译发展至今的主要作用——程序分析(相关的讨论,我们放到相应的章节来具体讨论)。

2)Forth Decompiler

1982到1984年,Forth Decompiler系统具有一定的代表性。它是一种可以通过递归扫描Forth语言编译字典条目,而把单词反编译成原语和地址的一个工具。但是Forth Decompiler并不是一个纯正的反编译器,它更像是一个逆语法分析工具,该工具递归地扫描一个字典表并且返回与给定单词有关的原语或地址。

3)STS(SoftwareTransport System)

1985年,C.W. Yoo介绍了软件传输系统STS (SoftwareTransport System),实现汇编代码从一机器到另一机器的自动转换。STS的转换思路是:将机器m1的汇编代码反编译成高级语言程序,然后将获得的程序在机器m2上编译成新的汇编代码。一个实验型的STS系统是针对Z-80处理器而研发的C语言交叉编译器,但是由于STS系统缺少数据类型信息导致此项目搁浅。

4)Decomp

1988年,Reuter编写了一套反编译器,并命名为Decomp,它是一种专用于Vax BSD 4.2机器的反编译器。Decomp需要带有符号信息的目标文件作为反编译的输入,而通过反编译生成类C源码程序,部分输出的C源码经过手工编辑后可以被再次编译。Decomp做了一件今天看起来十分有趣的事情,也就是它为了一款游戏而生,它在没有可用源代码的情况下把帝国游戏(Empire)移植到VMS环境。这件事情与笔者目前从事的二进制翻译相关研究非常类似,即实现了应用程序级别的移植,并以游戏这种生动的形式加以展示。

Decomp反编译器在当时的条件下,花费了大概5人月的工作量,并且可以从因特网上免费获取它。昆士兰大学的Cristina Cifuentes在她的博士论文中,成功地重现了Decomp的反编译过程。从实验中可以看出,Decomp反编译生成的程序有正确的控制结构、正确的变量数据类型、库例程和子过程的名字,甚至用户程序入口点也得到了还原。当然上述功能的取得,都需要满足一定的先决条件,但仅从功能上来看,Decomp是一个又实用价值的反编译器。

5)小结

经过20年的技术积累,1980年代本来应该成为反编译技术的爆发期,但是由于它天生的逆向属性,导致其与软件知识产权的保护产生了矛盾。在法律监管的空白时间里,并没有产生一些让我们记忆犹新的优秀系统和应用。整个1980年代的研究延续了不温不火的态势,但是对反编译完备性的讨论和实用化的驱使,仍然使得这个方向的研究延续下来。这个10年的研究比1970年代更注重实用性,并从专用这个角度加以体现。

4.反编译的春天——20世纪90年代

1990年代,反编译技术作为一个主体终于有了可以依据的法律——许多国家针对软件逆向工程进行立法,以规范该领域的研究工作。从一篇美国研究者Pamela Samuelson的文章“Reverse-engineering SomeoneElse’s Software: Is It Legal?”中,可以重现当时美国对“反编译”这一类技术的法律定义:根据美国联邦法律,对拥有版权的软件进行逆向工程操作,例如反汇编、反编译,若其目的不是通过剖析原软件,来研制新产品与之竟争,所进行的逆向操作是合法的。仔细品味这句话可知,只要是非盈利性的软件分析和源代码获取是被允许的。在上述背景下,反编译技术迎来了发展的春天,一批国家层面的综合性研究项目代表了反编译在当时的地位,比如:由11个欧洲工业和学术组织合作研究的REDO计划,主要是以调查研究软件的维护、有效性和软件系统文档化为目标。他们在软件逆向工程研究主题下对反编译进行了大量研究,从逻辑语义上给出反编译的一些实现方法和本质描述,并将其结果应用于英国核工业部。既然春天来了,除了上述枝叶返青的参天大树,哪能没有百花齐放呢?我们再把1990年代的反编译发展脉络梳理一下。

此外,在这个十年中,反编译这项技术与另外一项称作“二进制翻译”的技术结合的越来越紧密。反编译技术作为二进制翻译的一种重要实现方式,我们将在后文详细介绍二者的联系和区别,同时也会花一定篇幅,着重揭开一下能够体现反编译技术实用性的“二进制翻译”的神秘面纱。

1) Exe2c

1990年,由AustinCode Works公司推出的实验项目Exe2c可以将Intel80286/DOS可执行程序反汇编,并转换为内部格式代码,最终转换成C程序。从Exe2c的输出代码看出,它并没有实现数据流分析,而仅仅实现了部分控制流分析。C语言使用的一些控制结构被恢复,如:if-then和循环。它生成的C语言程序的大小是汇编程序的3倍。这个反编译器的积极意义在于,它是在过去的若干年中第一个尝试反编译可运行文件的反编译器。其成果表明,为了产生更好的C代码需要引入一个较为完善的数据流分析和启发式功能。而且,建立一个忽略所有由编译器引进的外来代码和发现库子程序的机制会很有帮助。这一点可以大大降低反编译的工作量,同时提升反编译输出的可用性。

2) PLM-80 Decompiler

1991年研发的PLM-80Decompiler反编译器也是一款具有国家支持和军事应用背景的软件,它是澳大利亚国防部的信息技术司研究的一个反编译的国防应用,也是在“反编译的春天”里值得一提的一项研究。PLM-80Decompiler研发的主要目的是针对废弃代码的维护、具有科技情报产品的分析、以及针对信息系统的安全和保密风险的评估,其中除了第一点以外,其它的目的都与反编译在当今时代的需求所契合,可见该项目在当时是具有前瞻意义的一项研究。

虽然研发目标具有重要意义,但最终由于技术实现的难度,PLM-80Decompiler只实现了一个样机。该样机是用Prolog语言编写的,针对特定机器PLM-80编译器编译的Intel 8085汇编程序,可以产生一种称作“Small-C语言”的目标程序(Small-C代表所生成的代码是标准C语言的子集)。从公开可以查阅的文献中,可以了解到PLM-80Decompiler可以从输入的汇编程序中识别出部分if..then和while()等简单结构,可以还原一些int和char等简单的数据类型,以及一些全局和局部变量。除此之外,PLM-80Decompiler还设计了一个图形化用户界面用于显示汇编程序和伪C程序,并且用户还可以通过图形界面编辑变量的名字、增加注解,以及支持手工确定主程序的入口点等功能。

总的来说,PLM-80Decompiler所做的分析局限于控制结构和简单数据类型的识别,并没有引入针对寄存器使用的分析。同时,该反编译器也不支持分析编译器生成的优化代码。但值得称道的是,PLM-80Decompiler对图形界面的引入,是对用户体验的一次提升,也是对反编译这种需要人工反馈参与工作的一种新的支持手段。

3) 8086 C Decompiling System

1991年推出的8086C Decompiling System是一个将Intel 8086/DOS可执行程序翻译成C程序的反编译器。它实现了库函数的识别以减少生成代码的量,同时它基于规则识别出了数组和结构体的指针等数据类型。不出意外的是,这个反编译器同样对输入文件有特殊的要求——输入文件必须是由Microsoft C V5.0版本小存储器模型编译所生成的。这一点再一次印证了:一个反编译器的可用性受限于它对源编译器的依赖。多数反编译器只能针对特定的编译器类型(或者编译器版本)完成正确的反编译动作。

8086 C Decompiling System描述了五个阶段:库函数的识别、符号执行、数据类型识别、程序转换和C语言代码生成。

该系统在库函数识别阶段所做的工作具有一定代表性,很多反编译器和后来的二进制翻译器都采用类似的方法。有必要单独说明一下:8086 C DecompilingSystem主要实现了对Microsoft C库函数的识别,用来区分哪些是系统调用的库函数,哪些是用户自己编写的函数。这么做的目的是为了在反编译时只处理用户函数,生成相应的C代码,而所有库函数则不必被反编译。识别库函数是通过模板匹配的形式完成,即预先构造一个所有C语言的库函数表,包含一些特殊信息,这部分工作是反编译器作者手工实施的。

除了库函数识别阶段以外,该反编译器其余阶段的实施中规中矩。它的符号执行是将机器指令完全用特有符号来表示,形成一套中间指令;而对数据类型的识别则是通过两套规则配合来实现的,即首先通过一组规则对于不同数据类型进行信息收集,然后再根据所收集的信息和另外一组分析规则共同确定数据类型;程序转换则把存储计算转变成各种地址表达式,例如数组寻址;最后,C语言代码生成器通过识别控制结构,继而转换成相应的程序结构,并且生成C语言代码。

8086 C Decompiling System是由我国合肥工业微机所科研人员开发的一套较早的反编译系统,代表了当时我国的反编译研究的方向和水平。

4) Alpha AXP Migration Tools

数字装备公司(Digital Equipment Corporation)在设计Alpha AXP体系结构的时候,需要能够在“新”的Alpha AXP计算机上运行“现有”的VAX和MIPS代码。正是由于这个动议,使得Alpha AXP MigrationTools作为一套可以完成上述功能的二进制翻译工具被开发出来。Alpha AXPMigration Tools可以实现旧体系结构的指令序列转换成新体系结构的指令序列,即实现不同体系结构间二进制级代码的无缝移植。这个移植过程中被开发者定义成两个部分,分别是:二进制翻译过程和运行时环境。为了保证二进制翻译过程的全自动执行,同时能够实现执行期间创建或修改代码的功能,该移植工具在二进制翻译部分使用了反编译技术。

Alpha AXP Migration Tools中反编译技术的应用,主要体现在机器指令的潜在含义理解和分析上。例如:原体系结构上的条件码分析,以便后续翻译过程中可以转化为Alpha体系结构上的相应操作;通过代码分析,确定函数的返回值或者发现代码中的错误;MIPS中标准库例程的发现和定位,以减少代码翻译的工作量,因为库例程绝大多数情况下是可以在新体系架构中找到类似库函数实现其功能的;发现代码中的“成语”(可以理解为在特定体系结构上,完成特定功能的一组指令序列),并使用目标体系结构中功能等价的指令组合来实现该“成语”的功能。通过上述一系列的分析工作,以及其他翻译工作,最终以AXP操作码的形式组成翻译后的二进制编码,并由运行时环境执行翻译的代码。

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

5) 其它反编译器产品和研究

在这一阶段还有众多公司纷纷推出自己的反编译器产品,具体情况如表所示。

表1 20世纪90年代部分反编译器产品

产品名称 年份 用途 厂商
Valkyrie 1993 用于 Clipper Summer ’87 的可视化反编译器 CodeWorks
OutFox 1993 用于加密的FoxBASE+程序的反编译器 不详
ReFox 1993 用于反编译加密的FoxPro文件 Xitech
DOC 1993 用于 AS/400 和 System/38 的COBOL反编译器 Harman Resources
Uniclip 1993 用于 Clipper Summer ’87 EXE 文件的反编译器 Stro Ware
Clipback 1993 用于Summer ’87 可执行文件的反编译器 Intelligent Information Systems
Brillig 1993 用于 Clipper 5.X .exe文件和.obj文件的反编译器 APTware

同时也有一批大学的实验室,发表自己的试验系统,其中在这一领域Cifuentes博士的研究成果,成为以后反编译研究的主要参考方向。Cifuentes在自己的博士论文中指出,可以通过数据流分析识别参数和返回值,通过控制流分析将代码恢复成具有结构的C程序。研究型反编译器dcc展现了她的工作,但它只能处理很小的Intel 80286/DOS可执行程序。

在dcc的基础上,反编译器REC(Reverse Engineering Compiler)基于Cifuentes的工作在几个方面进行了扩展,但是它生成的类C程序比较难读,因为包含了寄存器符号。它可以处理多个处理器(如:Intel 386、Motorola 68K)上运行的多种格式的可执行文件(如:ELF和Windows PE等)。像数组等复杂的数据类型保留为访问内存的表达式。

5.持续的研究——进入21世纪

时间荏苒,当历史的脚步进入新世纪,反编译的相关研究也随之更进一步,本节我们将用简单的笔触介绍2000年后的相关研究和商用产品。

2001年,Guilfanov介绍了IDA Pro反汇编器使用的类型传播系统,并着重讲解了库函数的识别工作。IDA Pro利用库函数的签名信息来恢复库函数调用语句使用的参数的数据类型,然后使用类型传播技术处理赋值语句来进行数据类型恢复。上述事实说明,没有一种数据类型恢复不是根据库函数类型信息进行的。

2002年,Morisada发布了处理32位Windows可执行程序的反编译器Anatomizer。对某些Windows可执行程序它表现的很出色,可以恢复参数和返回值,条件语句和switch语句也得到了很好的处理。当使用Anatomizer处理Cygwin程序时,库函数printf无法被恢复。另外,Anatomizer无法处理浮点指令和间接调用,数组仍然被保留为访问内存的表达式。当寄存器在某些过程体中未被定值而先使用时,它无法将其识别成参数。反编译器Anatomizer经常会异常终止。

2002年,Tröger和Cifuentes给出一个分析间接调用指令的方法。如果由虚函数产生的间接调用被成功识别,那么关于此间接调用的诸多信息都会获得。然而,此方法受限于一个基本块的范围,导致无法处理所有的情况。

2004年,RaimarFalke基于Mycroft的理论并进行扩展开发了反编译器Yadec,用于恢复数组数据类型。但需要一个相当于用户抉择的文件来处理冲突。

2004年,由AndreyShulga编写的反编译器Andromeda一直没有公开发行,但从网站可以获得一个GUI程序对应反编译生成程序。生成程序给人的印象非常深刻,但不能仅凭一个反编译生成程序来断定反编译器的优劣,可能它恢复出的数据类型是经过手工编辑的。

2007年,IlfakGuilfanov发布一个集成反汇编器IDA Pro的反编译器Hex-Rays,用来处理32位Windows可执行程序。反编译器Hex-Rays可以在窗口中展示反编译生成的类C代码,通过点击函数名跳到函数体视窗。所有函数的参数和返回值都得到了恢复,但作者声明反编译生成的程序仅用于阅读,不能对其进行编译。

遗憾的是,2008年后国外与反编译紧密的相关的重要研究很难再被检索到。笔者分析,其主要原因是反编译本身的复杂性,不完备性,以及在逆向分析实践中不如反汇编实用的现实所造成的。此外,虚拟化技术的日渐成熟,也分化了相当一部分使用反编译形式进行二进制翻译的研究资源。

6.身边的反编译——我国对反编译的研究

国内从事反编译方面研究的团队较少,能够在公开报道中查证的有:从1984年开始,合肥工业大学微机所开展了一系列与反编译相关的研究工作:在国家自然科学基金的资助下,以Dual-68000为硬件平台,研制T 68000 C反编译系统;用手工的方法反编译了UNIX操作系统部分组件;七•五期间,他们还进行了8086 C语言反编译系统的研究;随后,他们还发布了商业化的反编译系统DECLER V1.0和V1.1。1991年发表的文献中提及,武汉大学从1986年起就开始研制VAX机上的C语言反编译系统。同年发表的另外一篇文献中提及,北京控制工程研究所在PC机上开发TC语言反编译系统。1992年,上海交通大学的科研人员也发表了关于VAX机器上C语言反编译系统研究与实现的论文。1994年哈尔滨工业大学的研发团队开发了一款基于Turbo C的小模式反编译系统。2001年,解放军信息大学开始研发ITA二进制翻译系统(历时五年),该系统可以实现将IA64/Lunix架构下由C语言编制的可执行程序反编译到SW/Lunix下执行。2006年,北京大学计算机科学研究所研发了汇编级别的分析工具BESTAR。该工具实现了Linux平台上的轻量级汇编代码结构化表示功能,它能够实现利用控制流和数据流分析技术识别通用控制结构。该工具还可以分析程序执行流,重构表达式和函数,发现数据依赖关系,将汇编代码转换成一个结构化、易理解的中间语言程序。

当然前文还提到了8086 CDecompiling System也是国内非常重要的研究和工作,尤其8086 C Decompiling System还在Cifuentes的论文中被提及。

最后 ,致谢 小楠楠,借鉴了他大段文字。经过博士论文撰写,发现你文笔水平大增啊!