（计算机系统结构专业论文）反编译器自动评测与中间代码生成研究.pdf

摘要 摘要 反编泽是将较为低级的程序代码翻泽成与之等价的、更为高级和抽象的程序语言表示 的过程。作为软件逆向工程的霞要组成部分，反编译在软件移植、恶意代码柃测、程序凋 试以及软件维护与理解等方面起着十分重要的作用。虽然很早就开始了与反编译相关的研 究( 1 9 6 0 年) ，并且未曾中断，然而一直以来都还没有形成一套系统的理沦和方法，并且随 着程序设计语言理论和编洋器技术的发展，反编泽的研究内容和对象也在不断变化。 本文在已有的反编译研究的基础之上，针对现有的c 语言反编译器提出了一个基于抽 象语法树的反编译器自动评测方法，用于帮助改进现有反编译器的设计，并在c i l 系统的 基础上实现了一个比较系统s d d i f f ，通过对d c c ，d e c l e r b 0 0 m e r a n g 和h e x r a y s 这四种 c 语言反编译器的反编译效果的评测表明该方法能有效地对反编译器的反编译效果进行自 动评测，同时也揭示了反编泽技术随着时间的推移在不断进步和发展。 此外，本文还描述了一个基于栈空间分析的反编译中问代码牛成系统r e n e ，与传统基 于模式匹配的方法不同的是，r e n e 通过分析函数中各点的当前栈偏移来恢复局部变量和函 数参数，并以此处理函数调用语句。该方法克服了模式匹6 l 通用性差的缺点，并且能够减 少函数内无关的操作语句，从而能够牛成更为简洁的中问代码。 关键词：反编译抽象语法树自动评测中问代码牛成栈空问分析 a b s t r a c t a b s t r a c t d e c o m p i l a t i o ni sm er e v e r s ep r o c e s so fc o m p i l a t i o n na i m st oc o n v e r tl o w l e v e lc o d e si n t o t h ee q u i v “e ma i l dh i 曲1 e v e ll a i l g u a g ec o d e s a sa ni m p o r t a mp a no ft h es o r w a r er e v e r s e e n g i n e e r i n 岛d e c o m p i l a t i o np l a y sac r i t i c a lr 0 1 e i nm a n ya r e a s ，s u c ha sp r o g r 锄m i 昏a t i o n ， m a l i c i o u sc o d e sd e t e c t i o n ，p r o g r a md e b u g g i n g ，s o f h v a r em a i n t e n a n c ea 工l ds oo n a l t l l o u 曲t h e r e s e a r c ho fd e c o m p i l a t i o nc a nb et r a c e db a c kt o1 9 6 0 sa n dn e 、7 e rh a sb e e ni m e r r u p t e d ，a s y s t e m a t i ct h e o 巧h a sn e v e rb e e nb u i l t b e s i d e s ，t h eg o a l sa n dm e t h o d so fd e c o r n p i i a t i o na r e c h a n g i n ga 王l 出et i m ew i t | 1t h ed e v e l o p m e n to fp r o g r a i i l m i n gl a n g u a g et 1 1 e o r i e sa 1 1 dc o m p i l e r t e c m o l o g y b a s e do ne x i s t i n gr e s e a r c h e so fd e c o m p i l a t i o n ，t h i st b e s i sh a sp r e s e n t e da na p p r o a c hf o r q u i c k i ya 1 1 da u t o m a i i c a l l ye v a l u a t i n gt 1 1 eq u a l i t yo fd e c o m p i l a t i o no u t p u to facp r o g m m a n e x p e r h t l e n t a lt o o l ( s d d i 圩) h a sb e e ni m p l e m e n t e da n dm ep r e l i m i n a r yr e s u l t ss h o wt h a tt h e p r e s e n t e d 印p r o a c hc a ni d e n t i 母t h ed i f r e r e n c e si nb o ma c c u r a c ya n de m c i e n c y ，t h ep e r f o n n a n c e s o nd c c ，d e c l e r ，b o o m e r a i l ga i l dh e x r a y sa l s os h o wt h a td e c o 埘【p i l a t i o nt e c m i q u e sh a v eb e e n m a k i n gp r o g r e s s e sa l lt h et i m e b e s i d e s ，t h i sm e s j sh a sa l s od e s c r i b e da ni n t e 咖e d i a t ec o d eg e n e r a t i o ns y s t e m ( r e n e ) b a s e d o ns t a c ks p a c e 柚a l y s i s d i 雎r e n tf r o mt h et r a d i t i o n a lm e t h o do fp a t t e mm a t c h i n g ，r e n ea n a l y z e d m eo f r s e to fs t a c kp o i n t e ra te v e r yp o i n ti np r o 鲈a mw h i l er e c o v e r i n g1 0 c a lv a r i a b l e s ，p a r a m e t e r s a 1 1 dc a l l i n gs t a t e m e n t s 1 1 1 i sm e t h o di sm o r ea d a p t a b l e 出a i lp a t t e mm a t c h i n ga n dc a l lr e d u c e i r r e l e v a n to p e r a t i o ni no r d e rt om a k et h ei n t e r m e d i a t ec o d e sm o r ec o n c i s e k e yw o r d s ：d e c o m p i l a t i o n ，a b s 衄c ts y m a xt r e e ，a u t o m a t i ce v a l u a t i o n ， i n t e i t n e d i a t ec o d eg e n e r a t i o n ，s t a c ks p a c ea n a l y s i s 目录 图表索引 图1 1反编译器系统框架结构4 图2 1s d d 胛比较系统框架1 5 图2 2 源代码与对应反编译代码举例18 图z 3 源代码与反编译代码的e c i l 表示2 0 图2 4b e s tm a t c h i n g 算法2 2 图2 5 反编译代码和源代码的语法树2 3 罔2 6s d d i f f 输出结果示例2 4 图3 1p a l 过程调用模式描述2 8 图3 2中间代码生成系统r e n e 的框架结构3 0 图3 3 扎编代码解析中的主要数据结构3 1 图3 4x 8 6 指令格式描述31 图3 5 操作数解析举例3 2 图3 6 控制流图举例3 3 图3 7区间划分算法一3 4 幽3 8i a 体系结构中栈结构3 4 图3 9 基本块i 的e s p 入u ，卅u 和改变值3 5 图3 1 0 循环结构对入口和【出口值的影响3 6 罔3 1 1 基本块入口和出口e s p 值算法3 7 图3 1 2 坏节点引起的状态循环转换3 8 图3 1 3 函数调用过程示例4 1 图3 1 4 函数调用时的栈结构4 2 图3 15 中间代码生成示例4 6 表2 1条件表达式e 1 利e 2 的等价转换表2 0 表2 2图2 5 巾第二层节点问的相似度2 3 表2 3 语法差异统计2 5 表2 4 重命名分析统汁。2 5 表3 1x 8 6 中通用寄存器的编号4 0 v 中国科学技术大学学位论文原创性和授权使用声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究工作所取得的 成果。除己特别加以标注和致谢的地方外，论文中不包含任何他人已经发表或 撰写过的研究成果。与我一同工作的同志对本研究所做的贡献均已在论文中作 了明确的说明。 本人授权中国科学技术大学拥有学位论文的部分使用权，即：学校有权按 有关规定向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅 和借阅，可以将学位论文编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存、汇编学位论文。 保密的学位论文在解密后也遵守此规定。 作者签名：谗茁冬 年月 日 第1 章绪论 1 1 引言 1 1 。1 反编译简介 第1 章绪论 反编译( d e c o m p i l a t i d n ) 即编译的逆过程，是将较为低级的程序代码翻译成与之等价的， 更为高级和抽象的程序语言代码的过程 1 ，2 ，3 。这不仅包括一般意义上的将机器语言程序 转换到高级语言的反编译过程，而且包括将中f 白j 代码( j a v a 字节码等) 以及源代码转换到更 为高级的表示形式的过程 4 。 作为软件逆向工程重要的组成部分，反编译技术在许多方面都发挥着重要的作用： 软件移植。例如在二进制翻译中，直接的二进制代码之恻的转换非常困难，通过反 编译技术能够帮助实现从较高的抽象层次进行程序移植，从而降低了移植的难度和 移植后程序的执行效率 5 ，6 ，7 。 恶意代码检测。由于计算机和网络的普及和应用，二进制代码的安全性分析变得十 分重要，尤其是那些可能含有恶意的稃序代码，例如，病毒、木马、蠕虫、后门以 及其他的安全隐患等。相对于基奉的反汇编，反编译能够对这些二避制代码进行更 为深入分析 8 ，9 。 程序调试。现有的调试器通常将机器代码反汇编到汇编一级，以便获得较为结构化 的代码表示来帮助调试，然而一般来说，汇编级的程序代码非常艮，通常有一千行 以上。这样的代码调试起来非常的不方便，也不容易理解。反编译能够将汇编代码 转换至更高级的表示形式，从而极大地减少了被调试程序的长度，提 。j 了调试的效 率 8 ，1 0 。 软件维护与理解。软件维护作为软件生命周期的最后一个环节，在过去的三十年中 在软件开发中所占的开销持续上升，成为制约计算机技术应用和发展的一个重要因 素，在某些情况下，反编译投术能够帮助我们对软件进行维护。例如，很多优秀的 软件是用过时的编程语言实现的，如汇编语言，c o b o l 、b c p l 等，利用反编译 技术能够将这些稗序转换成软件维护者较为熟悉的高级语言代码，如c 、j a v a 等， 从而方便了软件的维护和理解 6 。 然而反编译并非像一些人想象的那样理想，例如存在一个反编译器能完全自动地对任 何机器代码进行反编译。实际上，这个问题理论上等价于停机问题( h a l t i n gp r o b i e m ) ，即这 个问题是不可判断的( u n d e c i d a b i e ) 1 1 。此外，即使存在这样的反编译器，也不可能得到与 第l 章绪论 源代码完全致的高级语言代码。既然如此，为何还要进行反编译的研究呢? 首先，并非 所有不可判定的问题都没有研究的价值，很多有用的算法问题都有类似的理论限制，例如， t s p 问题( t m v e l i n gs a l e s m a np r o b l e m ) 和h a m i l t o n 同路问题等；其次，我们所关心的并不是 能不能够反编译任意的机器代石弓程序，而是程序经过反编译能够帮助进行有用的分析；最 后，实践是最好的检验手段，现有众多的反编译器和反编译领域的研究成果在一定程度上 证明了反编译的必要性 2 ，1 2 1 3 1 4 。 1 1 2 反编译的历史和现状 反编译技术产生于上世纪六十年代，最初被用来帮助将一个体系结构下的程序移植到 另一个体系结构的机器上。1 9 6 0 年，美国海军电子实验室的j kd o n n e i l v 和h e n g l a n d e r 编写了历史上第一个反编泽器n e i i a c 1 5 ，它能够将u n i v a cm 一4 6 0 机器代码转换成n e l i a c 语言程序。早期反编译方面的研究主要足开发专用的反编译器作为软件移植的工具。例如， 1 9 6 6 年，s a s s a m a n 开发了一个将i b m 7 0 0 0 系列符号汇编程序翻译成f o r t r a n 语言程序的 反编译器 1 6 ；1 9 7 3 年，h o l i a n d e r 建立了一个将i b m 3 6 0 汇编子集翻译成类a l g o l 语言 的反编译器 1 7 ；h o u s e l 在1 9 7 3 年完成的博上论文中提出了一种新的清晰的反编译方法 1 ，他借用了编泽器构造过程中的流程图以及代码优化的理论，他将反编译分成i 个阶段， 首先反汇编程序，将指令与数据区分开来，并建立控制流图，以生成中间代码；其次，分 析循环结构和消除) c 余指令；最后，优化算术表达式，生成目标语言代码。b a r b e 1 8 开 发的p i l e r 系统采用了= i 地址码的中间语言表示，并尝试设训成为一个通用的反编泽器。 进入八十年代，随着逆向工程技术的发展，与其他逆向工程技术一样，反编译也曾受 到了足否合法的质疑。虽然反编译的目标并不足对某一编译器的破解，也不能够得到与源 代码一模一样的高级语言代码。然而，这种质疑曾一度阻碍了整个逆向工程领域的研究。 尽管如此，仍有一些反编泽的研究不容忽视，其中，k a t z 1 9 将反编泽技术运用于数据库 领域；f o n hd e c 口m i l e r 己成为f o r t h 工具箱的重要组成部分 2 0 j ；s t s 系统的核心就足 其反编译部分，它是一个目标代码层次上的软件自动移植系统，以汇编代码为输入，将其 转换成a s t ( 抽象语法树) ，再输入给反编泽程序从而生成高级语言程序，随后再将它翻译 成其他机器上的w ：编语言以完成程序移植 2 1 。后来的二进制翻译系统u 0 b t 7 所采用的 正是这种程序移植思想。 九十年代以来，各国纷纷开始对软件逆向工程进行立法以规范该领域的研究工作。根 据美国法律，对拥有版权的软件进行逆向工程操作，例如反，i 编，反编译，女果其目的不 是通过剖析原软件来研制新产品与之竞争，所进行的逆向操作是合法的 2 2 。同本也立法 规定软件工程是合法的，认为它有利于软件应用人员之间的互操作性。因此，反编译研究 又重新焕发了生机，并且研究的内容也不再局限于程序移植领域，而足呈现出多样化的趋 2 第1 章绪沦 势，例如，反编译技术作为逆向工具破用于检测软件中可能存在的恶意代码，验证编译器 产生的代鸦的正确性，帮助理解某个特定库甬数的具体实现细节等 2 3 。 a u s t i n 的一个研究小组于1 9 9 0 年发布了一款反编译器e x e 2 c 2 4 ，它针对d o s 操作系 统下的可执行文件，将它们转换成对应的c 语言代码。e x e 2 c 由二二个部分组成：e 2 a ，e 2 a p a r s e ， e 2 c 。e 2 a 实际上是一个反汇编器；e 2 a p a r s e 则负责处理从汇编到中f 刨表示的转换：最后由 e 2 c 将中间结果转换成c 语言代码。艮久以来e x e 2 c 是第一个尝试从可执行文件进行反编译 并完成到高级语言代码完整过程的反编译器，不过从其反编译的结果来看，e x e 2 c 并没有进 行数据流相关的分析，基本上每个汇编指令对应于一个或若干个c 语言语句，这使得得到 的结果非常不易阅读和理解。 1 9 9 5 年，澳大利亚昆士兰理工大学( q u e e n s l a n du n i v e r s i t yo ft e c h n o l o g y ) 与s u n 公司合作开发了c 语言反编译器d c c 2 ，d c c 针对i 3 8 6 体系结构下d o s 系统中的可执行 程序，将它们反编译成对应的c 语言程序。它采用了与编译器类似的处理过程，将反编译 分成前端，中间表示和后端二个部分，从而使中间表示独立于任何的体系结构。此外，它 还采用了函数签名( s i g n a t u r e ) 来进行库雨数识别，以便消除系统库甬数和s t a r t u p 代 码，增加了反编译结果的可靠性和可读性。d e c l e r 1 2 反编译器则利用符号执行的方法进 行中间代码生成，并取得了较好的反编译效果。 一直以来，反编译最难解决的问题就是数据类型的恢复，一般的反编译器最多只能恢 复出基本的数据类型，对于像数组，结构体等复杂数据类型的恢复都非常不理想。a l a n m y c r o f t 2 5 于1 9 9 9 年提出了一种新的解决方法，以便从汇编层( r t l ) 代码中恢复出复杂 的数据类型。该方法描述了一个类型推导系统，它借鉴于函数式编程语言中关于类型推导 的算法，该算法最初由m “n e r 在设计m l 程序设计语言时提出 2 6 。b 0 0 m e r a n g 1 3 是一个 开源的反编译器项目，最新的版本更新至2 0 0 6 年，b o o m e r a n g 采用了s s a 2 7 ，2 8 ( s t a t i c s i n 9 1 ea s s i g n m e n t ) 作为内部的中间表示，并采用基于数据流分析的类型恢复策略。它试 图将可执行程序反编译成高级语言代码，并使它可再编译，甚至可以作为源代码来进行维 护。然而，目前的b 0 0 m e r a n g 和其他反编译器一样，仅限于处理规模不太大的可执行程序。 1 1 t a kg u i l f a n o v ，i d ap r o 反汇编器的设计者，于2 0 0 7 年发布了一个基于i d ap r o 的商、l k 反编译器h e x r a y s 1 4 ，该反编译器实际上是i d a 的一个插件。与b o o m e r a n g 不【_ j 的是， 它并不努力使反编译结果达到可以重新编译，相反，它追求的是使反编译结果尽可能地被 用户阅读和理解。即便如此，由于它是最新开发的反编译器，凶此它的反编译效果是迄今 为止最令人满意的。 1 1 3 进行反编译的条件 反编译过程的难度要远远人于编译过程，因为编译后得到的机器代码已经将源程序中 3 笕1 章绪论 所有显式的高级语言特征信息都丢失了。针刘某种高级语言进行反编译，不但需要较深的 关于编译器和操作系统以及硬件等方面的理论知识的支持，还需要通过大量的实践和摸索 来获得机器代码与目标高级代码之间的某些对应的模式，并在此基础上进行研究和实践。 反编译的实践，要以如下的条件和背景知识作为基础： ( 1 ) 反编译所要达到的高级语言的语法描述，反编译过程是南它所翻译到的目标高 级语言的语法来指导的。 ( 2 ) 反编译源文件所包含的目标代码集，即编译所对应的机器指令集合，只有掌握 作为反编译器的输入的机器指令集的规格说明，才能有效地恢复低级代码程序 的控制流和数据流结构。 ( 3 ) 编译所得到的可执行代码的内存映象，从而可以有效地区分数据区和代码区， 减小反编译的工作量。 ( 4 ) 输入给反编译器的目标程序的相关信息，例如其相关的软硬件环境，所使用的 编译器，运行于何种操作系统之上等，从而使反编译能够有针对地进行。 1 1 4 反编译器的基本框架 b i n a r vc o d e 臣习川， 互 i 。墨竺赫 i n t e m e d i a 【ec o d e g e n e r a l o r i n t e r m ed ia l ec o d e s t c t ur i “g u p e a n a l y z e r h ；g h l “e lc o d eg e n e r a t o r p r e t t yp r i n e r h 1 9 h l e v e ic o d e 罔l _ l 反编译器系统框架结构 第1 章绪论 典型的反编译器的系统框架如图1 1 所示 中端( m 1 d d l ee n d ) 和后端( b a c ke n d ) 三个部分， 的是高级语言代码，与编译器的流程f 好相反。 和编译器一样可以分为前端( f r o n te n d ) ， 但是反编译器输入的是二进制代码，输出 前端通常是一个中间代码生成器，用于将进制代码转换成与具体机器无关的中间代 码。它一般分为三个步骤，首先加载器( l o a d e r ) 将以二进制形式存在的程序文件加载进内 存，分析所要加载的二进制代码文件的格式，比如w i n d n w s 下的p e 文件格式，c 0 m 文件格 式以及l i 叫x 下的e l f 文件格式等，并由此得到出文件的数据段和代码段等信息，然后对 该文件进行反汇编，将二进制代码转换成对应的汇编代码。解析器( p a r s e r ) 对以汇编代码 表示的程序进行分析，例如通过分析汇编代码的控制流来建立程序的控制流图( c o n t r o l f l o wg r a p h ) ，同时进行必要的数据流分析，最后将以文本表示的汇编代码转换成一个内部 表示形式，以方便生成中间代码。中间代码生成器( i n t e r m e d i a t ec o d eg e n e r a t o r ) 则从汇 编代码中初步恢复出局部变量，函数的形式参数以及函数调用语句等信息，从而将汇编代 码转换成较为高级的中间代码。 反编译器的中端和编译器的中端处理的对象都是中白j 语言代码，所不i j 的是在编译器 的中端能够掌握程序的所有高层抽象信息，而反编译中端基本上只能依靠以中间表示的代 码来进行分析。中间代码通常是与具体机器兀关的，从而方便了对其进行研究和分析的难 度，同时也吸引了更多的人从事中端的研究。然而反编译的中端的研究主要是前端产生的 控制流图进行结构化( s t r u c t u r i n g ) 和从中间代码中恢复出更为高级和复杂的数据类型 ( t y p e ) ，这部分是反编译中最为困难的工作。 反编译后端接受中端的分析结果，通常这种分析结果已经是高级语言形式了，只是以 中端的内部表示存在，例如抽象语法树等。后端主要负责将完成的分析结果进行输山，产 生可供用户阅读的目标高级代码( h i g h l e v e lc o d eg e n e r a t o r ) ，并针刘目标高级代码进行 排版优化( p r e t t yp r i n t e r ) 。 1 2 主要的研究方法和内容 反编译是编译的逆过程，在编浑过程中不可避免的会有大量的信息丢失，并且在理沦 上足不可判定的，因此实现一个完整的反编译过程是非常困难的。从简化问题的伯度以及 程序设计语言的发展趋势等方面考虑，现有的反编译研究都把反编泽过程分为库函数识别， 控制流分析和数据类型恢复这i 个主要的研究方面。 1 2 1 库函数识别 库函数和普通的用户函数并没有本质上的差别，早期的反编译研究集t i t 十程序移植领 5 奠1 章绪论 域，因此并没有刘库函数进行特殊处理的必要，然而随着反编译技术的发展，人们发现反 汇编山的雨数中，大部分函数其实是系统库函数或者用户库函数，真正属于用户函数的并 不多，这些库函数的功能其实早已知道，并无反编译的需要，凶此，将这些库函数先行识 别出来，一方而减少了反编译的工作量，另一方而也增加了反编译结果的可读性。近年来 的反编译系统都对库函数进行了识别处理 2 9 3 0 。 常见的识别方法是对每个库函数定义一个签名( s i g n a t u r e ) ，签名包括了一个函数的各 种特征，例如函数的总氏度，名称，操作码串，返回值类型，参数类型和个数等，识别时 对每个需要判别的函数提取其签名，再与标准的库函数签名进行比较，当相似度达到某个 阀值的时候便可以认为此函数是一个库函数。可以看出，这种方法需要事先对可能出现的 库函数建立签名库，每当要识别一个新的库函数便要把这个库函数的签名加入库中，因此， 现有的库雨数识别方法都针对的是系统厍两数，对于用户库函数的识别还没有比较有效的 方法。 1 2 2 控制流分析 反编译中的控制流分析分为控制流恢复和控制流结构化两个部分，控制流恢复足指从 汇编代码中恢复出程序的执行路径，也就是对每个跳转指令的跳转目标进行分析，确定具 体的跳转地址，从而使程序的执行路径清晰化：控制流结构化则指将以控制流图表示的程 序转换成用循环，分支等结构化语句组成的程序，例如在c 语言里用w h i l e ，d o w h i l e ， i f e l s e ，b r e a k ，c o n t i n u e 等结构化语句表示的程序，尽量消除非结构化的g o t o 语句。 控制流恢复的目标是要从汇编代码中建立程序的控制流图( c f g ) ，更进一步说便是确定 各种跳转指令的具体跳转地址。返一点看似简单，实际上却非常困难，因为对于一些间接 跳转的指令，无法确定其操作数的具体值，也就不能确定该指令的后继指令，进而不能建 立准确的控制流图。通常这类问题的解决办法是对汇编代码进行程序切片 3 1 ，3 2 ，并期梁 能由此确定跳转指令操作数的值，这足一个普遍适用的方法，很多反“：编器盎i d ap r o 等 都会作这样的分析，然而这种通用方法的缺点在于并未考虑程序的具体特征，囚此恢复的 效率不是很高。c i f u e n t e s 对涉及跳转表结构的控制流恢复作了进一步的优化，总结出跳 转表中的跳转指令的三种模式：a 。o ，h 。并且实验结柴表明通过匹配该模式能够有效地提 高程序控制流恢复的精度 3 3 。 控制流恢复的研究非常少见，一般仅限于逆向工程领域，但是控制流结构化的研究则 比较广泛和普遍，而且并未局限于逆向工程领域。早期的结构化算法土要用于对某牡编程 语言的程序进行结构化处理以帮助理解程序的流程，囚为这些程序设讣语言并不是结构化 的。例如，f o r t r a n 语言程序中通常缺少结构化的控制语句，这使得f o r t r a n 程序变得非常 难以理解，b a k e r 3 4 提出了一个方法，用于将f o r t r a n 语言程序转换成r a t f o r 语言程序， 6 第1 章绪沧 该方法使用了i f t h e n e l s e ，l o o p s ，c o n t i n u e 和多出口语句等，该方法使转换后程序的 可读性有了很大的提高。此外，在p a s c a l 语言中，g o t o 语句不仅用于过程内的跳转，还可 以在不同过程间跳转，为此提山了很多方法来消除这种过程问g o t o 语句，大多数采用引入 新的局部或全局变量的方法，或者采用多层出口语句 3 5 。 现有的结构化算法大多采用节点分裂，引入新的变量，选用一些不常用或者普通编程 语言中不存在的控制结构如多山口循环等 3 6 ，3 7 。这些方法的优点在于能将不可规约的程 序流图转换成可规约的程序流图，然而大多数结构化算法的最终目的是方便编译器的优化 操作，并不适于反编译中的控制流结构化分析。c i f u e n t e s 提山了一个针对反编译过程的控 制流结构化方法 3 8 ，3 9 ，该方法针对于可规约控制流图，并采用了区间( i n t e r v a l ) 划分 1 的方法来帮助实现结构化的循环结构，该方法已应用于d c c 反编译器中，取得了较好的结 构化效果。 1 2 3 数据类型恢复 数据类型恢复是反编译过程中最重要然而也是最难解决的问题，因为高级语言程序经 过编译连接以后，原来的类型信息都己不复存在。数据类型恢复的任务便足从可执行文件 中发掘出隐含的数据类型信息。数据类型的恢复通常采用数据流分析的手段，如分析定值一 引用链，引用一定值链，符号执行，程序切片等。 反编译的数据类型恢复一般分为两个阶段，第一个阶段是将二进制代码转换成与机器 无关的中间代码表示，中间代码的设计和选取既要符合目标高级语言的特征，同时也要易 于从二进制代码进行转换；第二个阶段便是将中间代码转换为目标高级语言代码，并尽刚 能地恢复出易于理解的函数和变量的类型信息。 c i f u e n t e s 提出了一个基于模式匹配的过程恢复方法 4 0 ，该方法在分析了p e n t i u m 和s p a r c 处理器体系结构下的a b i ( a p p l i c a t i o nb i n a r yi n t e r f a c e ) ，提取出典型的过程 轲：编语言模式，主要包括了序言( p r o l o g u e ) ，结语( e p i l o g u e ) ，函数参数和局部变量阻及 返回值。由于采用的是模式匹配的方法，该方法能快速有效地对汇编代码进行转换，但是 所匹配的模式必须事先设定，囚此对于不符合模式的过程，该方法将得不到正确的结果， 最重要的是该方法没有提及普通“编代码的转换，因为普通的“一编代码没有模式可以提取。 d e c l e r 反编译器除了采用了模式匹配的方法，对于普通汇编代码则使用了符号执行的方 法，但是符号执行却不能很好地处理循环过程! “。 数据类型恢复中一个重要的目标便是消除寄存器，h o u s e l 1 给出了一个文本压缩 ( t e x tc o m p r e s s i o n ) 的方法用来消除不必要的j j 口载( 1 0 a d ) 和访存( s t o r e ) 操作，该方 法对赋值指令进行向前和向后替换，能够减少4 0 由m i x a l 编译器编泽的指令代码。 h o d w o o d 4 2 则描述了一种称作表达式浓缩( e x p r e s s i o nc o n d e n s a t i o n ) 的方法，采用向 7 茆1 章绪沦 前替换的方法将两个或更多的指令转换成等价的表达式，该方法捕述了5 个可以进行向前 替换的必要条件和6 个充要条件，然而并未看到与该方法有关的实验结果。 m y c r o f t 2 5 提出了一个基于类型推导( t y p ei n f e r e n c e ) 技术的反编译方法，用于将 汇编代码转换成c 语言程序。该方法首先将汇编代码转换成s s a 的表示形式，然后根据每 条指令的具体语义得出相应操作数的类型，并生成相应的约束条件，例如对于指令m o vr 7 ， # 0 ( r 7 代表某个寄存器，# o 表示立即数0 ) ，则寄存器r 7 的类型为：t 7 = i n tvp t r ( a ) ， 其中a 为任意的未确定的类型；最后，利用类型推导计算出整个函数内各个变量的类型。 此外，对于推导过程中山现的类型冲突，该方法采用了最初南h e r h r a n d 4 3 提出的类型冲 突检测与恢复的方法，而不是简单地结束推导。 k a t s u m a t a 也提出了一个采用类型推导技术的方法，该方法基于其先前提出的 l a m ( l o g i ca b s t r a c tm a c h i n e ) 4 4 ，l a m 提供了一种从自然规约( 即类型化的 演算) 到连 续序列演算( s e q u e n t i a ls e q u e n tc a l c u l u s ，类似于机器代码) 之日j 的转换机制。凶此其反 编译过程即是该转换的逆过程。首先由一个规则系统捕述了一个可以被类型化的指令序列， 并计算出程序中任意一点的j v m 栈结构；然后每个基奉块被当作一个函数进行翻译，并按 照执行语义进行嵌套，所有的雨数都将是无副作用的( s i d e e f f e c t f r e e ) ，所有的副作 用将会通过对象而被模型化：最后由类型推导技术完成数据类型恢复。m y c r o f t 和 k a t s u m a t a 的方法都尝试用函数式程序语言中类型推导的技术作为数据类型恢复手段，只是 m y c r o f t 将汇编代码转换成c 语言程序，而k a t s u m a t a 则是从中日代码( 相对于汇编代码) ， 即j a v a 字节码到函数式语言代码l a m ，尽管如此，者在本质上其实是相同的 4 5 。 1 3 相关的研究领域 1 3 1 反汇编 反汇编即汇编的逆过程，能够将可执行程序转换成与之等价的汇编代码。反汇编是对 二进制程序进行反编译的第一个步骤，反汇编结果的好土1 、将赢接影响到反编译的结果，是 反编译过程。 ，重要的部分。反汇编最大的难题在于代码与数据的分离，即如何判断二进 制文件中某个字节是代码还是数据，例如指令序列中可能会出现跳转表，对齐字节等数据 信息，小幸的是这个问题也是小可判的。此外，在c i s c 体系结构下如i n t e lx 8 6 等，指令 的大小是可变的，从而增加了反汇编的难度。 现有的反编译方法主要有两种：线性清除( 1 i n e a rs w e e p ) 和递归遍历( r e c u r s i v e t r a v e r s a l ) 4 6 。线性清除的方法只对二进制文件中典犁的包括代码的节( s e c t i o n ) 进行 反汇编。这种方法的主要优点便是简单直观，然而其缺点在于它将指令序列小的数据字节 也当作指令代码，从而给出错误的反编译结果，只有存某些特殊情况下这种错误才会被发 8 第l 章绪论 现，如遇到错误的指令操作码等等。尽管如此，仍有很多反汇编器采用了此类方法，例如 g n u 工具o b j d u p 4 7 ，链按时优化器a l t o 4 8 ，o m 4 9 和s p i k e 5 0 等。 递归遍历的方法对反汇编过程中遇到的每个跳转指令的后继进行分析，凼为跳转的目 标地址处也一定是指令，于是可以从跳转的目标地址处重新反汇编，这样递归地进行下去， 直到不再涉及新的地址。相对于线性清除的方法这种方法能够得到更好的反汇编效果，很 多二进制翻译系统和优化系统如u 0 b t 采用的是这种方法 7 ，5 1 。s c h w a r z 4 6 综合运用了 线性清除和递归遍历两种方法，实验结果汪明这两种方法并不冲突，因此综合的方法会有 更好的反汇编效果。递归遍历方法的核心在于对已反汇编代码的控制流分析，这几乎等同 于反编译中控制流的恢复过程，不i 一的是反汇编中只要确认了目标地址的范围在己反汇编 的地址范围之内便可以了，而反编译则要求分析出所有具体的转移目标地址。 1 3 2 二进制翻译 二进制删泽( b i n a r yt r a n s l a t i o n ) 是一种直接翻译口j 执行二进制程序的技术，能够把 一种处理器上的二进制程序翻译到另一种处理器上执行 5 ，6 ，7 。它使得不同处理器之间的 二进制程序可以很容易地相互移植，扩人了硬件和软件的适用范围。基于软件的二进制翻 译方法可以分为三类：解释执行，静态翻泽和动态翻译。解释执行对源处理器代码中的每 条指令实时解释执行，系统不保存也不缓存解释过的指令，无需用户。】：涉和优化。解释器 相对容易开发，兼容性好，然而代码执行效率很低 5 2 。静态翻译足在原处理器代码执行 前对其进行自j ：晕，将源机器上的二进制文件翻译成目标机器上的二进制文件，然后在目标 机器上执行。因此一次的翻泽结果一，以多次使用，并且町以进行完整细致的优化，代码执 行效率高 7 。然而静态翻译可能无法完整地翻译一个程序，因而需要解释器的支持和用户 的参与。动态翻泽则在程序运行时对执行到的片段进行翻泽，町以利用执行时的动态信息 来发掘静态翻译所不能发现的优化机会，并且口j 以做到无需用广i ：预 5 3 ，5 4 。 h p 公司于1 9 8 7 年开发的b e r g h 系统是最早的商用二进制翻译系统，用于软件模拟利目 标代码翻译 5 5 ：d e c 的f x13 2 系统将运行在x 8 6 w i n n t 系统下的程序翻译到a l p h a w i n n t 环境下运行，它结合了静态翻译和动态翻泽，具有正确，高效和透明的特点 5 6 ； p 的a r i e s 是一个基于软件的i a 6 4 翻译器，它结合了快速翻译和动态翻译，可以仿真p a r i s c 伞部的 指令，无需用户二门耍 5 3 ；d i g i t a l b r i d g e 是中科院计算所开发的二进制到泽系统，它能 够将x 8 6 的应用程序翻译到m i p s 上执行，它尽町能地进行静态积泽，并由动态翻泽来弥补 静态的不足，从而最人限度地提高翻译后程序的性能 5 7 ；d a i s y 和b o a 足i b m 分别于1 9 9 6 年和1 9 9 9 年开发的二进制翻译系统，它们都动态解决了陪如精确中断，自修改代码和内存 一致性等二进制翻泽中通常会遇到的难题 5 4 ；t r a n s m e t a 公司2 0 0 0 年开发的代码变换 ( c o d em o r p h i n g ) 软件利用二进制翻译使其研发的芯片能够兼容x 8 6 的软件 5 8 。 9 前1 章绪沦 u q b t 则是一个可变源和目标的_ 进剖翻译系统，它使用了两种中间表示：机器相关的 r t l 和机器无关的h r t l 、通过将源程序转换成r t l 的形式，再语义抽象到h r t l ，并在此基础 上进行与机器无关的分析和转换，最后再甫h r t l 生成目标机器代码。u q b t 中的h r t l 可看 作是反编译中的中间代码形式，更进一步，若反编译的效果非常理想时，_ 进制翻译系统 可以将二进制代码先反编译成高级语言代码，然后在高级语言代码层进行不同体系结构下 的移植，将会大大减小翻译的难度。 1 3 3 软件逆向工程 软件逆向工程的范围非常广泛，不仅与反编译相关的研究都属于软件逆向工程的内容， 而且它还包括各种程序分析技术。例如，程序代码迷惑( c o d e0 b f u s c a t i o n ) 5 9 ，对文档 的重构( r e d o c u m e n t a t i o n ) 6 0 等。通过应用逆向工程能够提高软件重用性和改善程序设训 风格，有利于软件维护，提高软件的生产率和质量。 逆向工程最初被用于对硬件的分析 6 1 ，它的定义为：分析他人设计的硬件产品，生 成产品规格说明的活动，通常用于修正原产品中的缺陷或增强原产品的功能 6 2 。逆向工 程用于软件领域足指分析，理解软件系统并将其抽象成更高抽象级上的新形式，其根本目的 是帮助人们理解软件 6 3 。软件逆向工程是相对于正向软件工程而言的。正向工程是从高 级的规格说明发展到系统实现的过程。软件正向工程与传统的软件工程的定义是有区别的， 它在软件工程的结果之上进行二次开发。最常见的正向工程行为主要足从逆向工程获得的 设讣信息生成新的程序代码。 有些人认为，软件逆向工程是指从源代码重构设讣阶段的每一步，即只是从程序源代 码获得需求分析和规格说明等原始设计阶段文档。这种观点将反编译和反a 编等操作排除 在逆向工程之外，囚为它们是将低抽象级代码翻译成高抽象级代码的过程。这种看法是不 全面的，反汇编和反编译应该被看成是逆向工程的特使形式，因为二者都具有提高软件抽 象级，