（计算机应用技术专业论文）基于swf中as的反编译的研究.pdf

中文摘要 计算机科学与技术发展到今日，出现了很多的优秀软件，在这些软件产品 中积累着开发者的很多好的设计思想和经验，要了解和学习一个软件所包含的 思想和原则，必须对软件的源程序进行分析；要获得该软件的各种参数，开发 能与该软件兼容的软件也必需获得软件的源程序。然而，为了在市场竞争中取 得优势，软件的开发者一般不会将源程序公开。因此，对软件进行反编译就成 了软件开发技术人员经常采用的方法。随着计算机软件的广泛应用，反编译已 成为软件逆向工程的重要研究领域，在程序的移植、商业软件的安全性分析、 软件的加解密分析、软件的复用等方面充分显示其应用价值。 反编译，是将以机器代码级语言书写的源程序翻译成与其等价的编译器级 语言书写的高级语言程序的过程。反编译器作为一种软件工具，其实现的功能 相当于编译器的逆过程。它是软件逆向工程中的一个重要组成部分。s w f 是 m a c r o m e d i a 公司的动画设计软件f l a s h 的专用格式，是一种支持矢量和点阵图形 的动画文件格式，具有缩放不失真、文件体积小等特点，它采用了流媒体技术， 可以一边下载一边播放，目前被广泛应用于网页设计，动画制作等领域，由h e a d e r 和b o d y 两部分组成。为了能更好的实现用户与界面的交互，向f l a s h 中加入了 动作脚本语句a c t i o n s c r i p t ( 简称a s ) 。a c t i o n s c r i p t 是f l a s h 的脚本语言，与 j a v a s c r i p t 相似，是一种面向对象编程语言。而本文就是基于对此的反编译。 本论文的主要工作内容包括：( 1 ) 介绍了反编译的关键技术，包括数据流 分析、控制流分析、库函数识别等内容；( 2 ) 介绍了反编译的几种主要模式， 选择了一种适合于我们反编译的基予模式识别的反编译模式，句法分析，语义 分析，中间代码的生成，控制流图的生成。( 3 ) 介绍了反编译系统d e c o m p i l e r 的运行环境，将文本文件转化成二进制文件，以及运用模式匹配的思想，成功 实现从二进制文件到源文件转化的反编译过程。 论文的主要贡献在于设计并实施了基于s w f 文件中a s 脚本的反编译系统。 该系统能够满足客户需求，完成s w f 存储中a s 文件的还原，为以后反编译更 好的发展提供了基础研究。 关键字：反编译，s w f ，a s ，模式匹配 a b s t r a c t 、t o d a yt h e r ea r em a n ye x c e l l e n ts o f t w a r ew i t ht h ed e v e l o p m e n to fc o m p u t e r s c i e n c ea n dt e c h n o l o g y t h e s es o f t w a r ep r o d u c t sh a v ea c c u m u l a t e dal o to fg o o d d e v e l o p e r s d e s i g ni d e a sa n de x p e r i e n c e w em u s ta n a l y s et h es o f t w a r es o u r c e p r o g r a mi no r d e r t ou n d e r s t a n da n dl e a r n i d e a sa n d p r i n c i p l e sw i t h i ns o f t w a r e ；a n dw e s h o u l do b t a i nv a r i o u sp a r a m e t e r so ft h es o f t w a r e i fw ew a n tt o d e v e l o ps o f t w a r e c o m p a t i b l ew i t ht h es o f t w a r e ，w es h o u l dg e tt h es o f t w a r es o u r c ec o d e s h o w e v e r , i n o r d e rt og a i na d v a n t a g ei nt h em a r k e tc o m p e t i t i o n ，s o f t w a r ed e v e l o p e r sg e n e r a l l yw i l l n o tb eo p e ns o u r c ec o d e s t h e r e f o r e ，d e c o m p i l i n go ns o f t w a r eh a sb e c o m ea f r e q u e n t l yu s e dm e t h o dt od e v e l o p m e n ta n dt e c h n i c a lp e r s o n n e l w i t hg e n e r a l a p p l i c a t i o no fc o m p u t e rs o f t w a r e ，d e c o m p i l a t i o nb e c o m e si m p o r t a n tr e s e a r c hf i e l di n s o f t w a r er e v e r s ee n g i n e e r i n g m a n yp r a c t i c a ls i t e ss h o wi t ss i g n i f i c a n c e , s u c ha s m i g r a t i o no fs o f t w a r ep r o g r a m s ，s e c u r i t ya n a l y s i so fb u s i n e s ss o f t w a r e ，c r y p t a n a l y s i s ， a n dr e u s eo fs o f t w a r e d e c o m p i l a t i o ni st h ep r o c e s sw h i c ht r a n s l a t e s s o u r c ep r o g r a m sw r i t t e db y m a c h i n e c o d el e v e ll a n g u a g ei n t oc o r r e s p o n d i n ga d v a n c e dl a n g u a g ep r o g r a mw r i t t e d b yc o m p i l e rl e v e ll a n g u a g e d e c o m p i l e ri sl o o k e da sas o f t w a r et o o l ，w h o s ef u n c t i o n i se q u i v a l e n tt ot h er e v e r s ep r o c e s so fc o m p i l e r i ti sa ni m p o r t a n tc o m p o n e n to ft h e s o f t w a r er e v e r s ee n g i n e e r i n g s w fi sas p e c i a lf o r m a to fm a c r o m e d i a sa n i m a t i o n d e s i g ns o f t w a r e - - h a s h i ti saa n i m a t i o nf i l ef o r m a tw h i c hs u p p o r tv e c t o ra n db i t m a p g r a p h i c s ，w h i c hh a st h ec h a r a c t e r i s t i c ss u c ha sn o th a v i n gt h es c a l i n gd i s t o r t i o n ，n o s m a l ls i z ed o c u m e n ta n ds oo n i tu s e ss t r e a m i n gm e d i at e c h n o l o g y y o uc a np l a yi t w h i l ed o w n l o a d i n g n o w a d a y si th a sb e e nw i d e l yu s e di nw e bd e s i g n ，a n i m a t i o n p r o d u c t i o na n do t h e rf i e l d s i ti sc o m p o s e db yt h eh e a d e ra n dt h eb o d y i no r d e rt o i n t e r a c t i v eb e t t e ru s e rw i t hi n t e r f a c e ，w ei n t r o d u c e da c t i o n s c r i p tl a n g u a g e a c t i o n s c r i p t ( s h o r tf o ra s ) t oh a s h a c t i o n s c r i p ti st h eh a s hs c r i p t i n gl a n g u a g e i ti s s i m i l a rt oj a v a s c r i p tw h i c hi sa no b j e c t - o r i e n t e dp r o g r a m m i n gl a n g u a g e t h i sa r t i c l e d e s c r i b et h ec o m p i l a t i o nb a s e do na s 。 t h em a i nc o n t e n t so ft h et h e s i sa r ef o l l o w i n g ：( 1 ) d i s c u s s e dt h em a i n t e c h n o l o g yo nc o m p i l a t i o n ，i n c l u d i n ga n a l y s i so fd a t af l o w , a n a l y s i so fc o n t r o lf l o w , i d e n t i f i c a t i o no fl i b r a r yf u n c t i o n s ，a n ds oo n ；( 2 ) d e s c r i b e ds o m em a i np a t t e r n so f d e c o m p i l a t i o n w es e l e c t e dad e c o m p i l a t i o np a t t e r nb a s e do np a t t e r nr e c o g n i t i o n w h i c hi ss u i t a b l ef o ro u rs y s t e m s y n t a xa n a l y i s ，g r a m m a ra n a l y i s ，s y n t a c t i ca n a l y s i s ， s e m a n t i ca n a l y s i s ，g e n e r a t i o no fi n t e r m e d i a t ec o d e ，g e n e r a t i o no fc o n t r o lf l o wg r a p h o ) i n t r o d u c et h er u n n i n ge n v i r o n m e n to fd e c o m p i l i n gs y s t e m - - d e c o m p i l e r t r a n s l a t e t e x tf i l ei n t ob i n a r yf i l e ，a n dc o m p l ys u c c e s s f u l l yc o m p i l a t i o nf r o mb i n a r yf i l et o s o u r o gf i l eb yu s i n gt h ei d e ao fp a t t e r nm a t c h i n g t h em a i nc o n t r i b u t i o no ft h et h e s i si st h ef o l l o w i n g ，d e s i g n e da n df i n i s h e dt h e d e c o m p i l a t i o ns y s t e mo na c t i o n s c r i p tb a s e do ns w f , w h i c hc a nm e e tt h en e e do f c u s t o m e r s ，a n df u l f i l lt h er e c o v e r yo fa ss t o r e di ns w f , a n ds u p p l yb a s i cr e s e a r c ht o t h eb u t t e rd e v e l o p m e n to ff u t u r ed e c o m p l i a t i o n k e yw o r d s ：d e c o m p i l a t i o n ，s w f ，a s ，p a t t e r nm a t c h i n g i l l 独创性声明 本人声明，所呈交的论文是本人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得武汉理工大学或其它教育 机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何 贡献均已在论文中作了明确的说明并表示了谢意。 签名：鲴亟菌e t 期：通：墨罗 学位论文使用授权书 本人完全了解武汉理工大学有关保留、使用学位论文的规定，即：学校有 权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅 和借阅。本人授权武汉理工大学可以将本学位论文的全部内容编入有关数据库 进行检索，可以采用影印、缩印或其他复制手段保存或汇编本学位论文。同时 授权经武汉理工大学认可的国家有关机构或论文数据库使用或收录本学位论 文，并向社会公众提供信息服务。 ( 保密的论文在解密后应遵守此规定) 武汉理工大学硕士学位论文 1 1 课题的研究背景 第1 章绪论 在计算机技术迅速发展的今天，出现了越来越多的优秀软件，在这些软件产 品中积累着开发者的很多好的设计思想和经验，要了解和学习一个软件所包含的 思想和原则，必须对软件的源程序进行分析；要获得该软件的各种参数，开发能 与该软件兼容的软件也必需获得软件的源程序。然而，为了在市场竞争中取得优 势，软件的开发者一般不会将源程序公开。因此，对软件进行反编译就成了软件 开发技术人员经常采用的方法。 反编译在软件教学、科研、开发等场合都是一种非常重要的手段。在教学和 科研中，为了学习国外先进的软件设计理念，我们经常需要把国外一些机构和个 人开发程序反编译来进行分析和借鉴；早期的汉化爱好者把外文版的软件进行反 编译，找到目标菜单的源代码，然后把汉语写进去替换相应的外文，汉化人填入 汉语的长度不得超过原文的长度，不足的可用空格补齐，然后再进行编译，最终 完成外文软件的汉化；而在与病毒的斗争中，虽然每个研究人员的工作方式不同， 但他们使用的技术是类似的。例如在编译环境下执行病毒程序，观察病毒的行为 方式，使用反编译工具分析代码结构【。 网络游戏作为当前学术和商业界最流行的一个方向，当前和未来几年都将是 一个热点。与网络游戏相辅相成的就是外挂，由于网络游戏的服务器源代码的保 密性和外挂存在的特殊性，外挂就只能从网络游戏客户端的通讯协议进行分析。 同样，反编译是这个协议分析的非常有力的一个工具。 与上述情况类似，有了s w f 文件的反编译工具，我们就可以更加方便的学 习经典f l a s h 的制作方法，从技术和设计思想上提高整体的f l a s h 设计水平。 反编译的用途非常广泛，对于软件的理解、维护、移植以及开发新软件起着 重要作用。总的来说，反编译有两大应用领域： ( 1 ) 软件维护 在软件维护方面，反编译被用来恢复丢失的或者无法获取的源程序代码，将 一个使用过时语言编写的代码翻译成更新的语言，将一个以非结构化方式编写的 旧程序变成一个结构化程序，将应用程序移植到一个新的硬件平台，以及调试已 知有缺陷但是源代码不可得的二进制程序。 ( 2 ) 软件安全性 武汉理工大学硕士学位论文 在软件安全性方面，反编译在软件关键的系统中被用来验证一个编译器产生 的目标代码，因为在这些系统中我们不能绝对信赖编译器，另外，反编译也被用 来检查是否存在恶意代码比如病毒【2 1 。 本课题正是在这样的需求背景下提出的。 1 2 研究内容 本文主要运用基于文法和模式匹配的方法对反编译技术进行了研究，并以反 编译a c t i o n s c r i p t 2 0 的二进制代码为基础的适用于其他语言的反编译系统。具体 包括控制流的恢复、数据流的恢复、库函数的识别三个部分。要研究高级语言程 序中的各种控制流、数据流和库函数是如何在目标代码中存储，并反过来根据这 些如何实现的有关信息进行相关数据的恢复，就要选定一种高级语言和相应的编 译器进行实验：编写大量程序，这些程序涵盖了各种数据类型的变量，还有对这 些变量的各种各样的操作，然后将这些程序编译到目标代码，接着对这些目标代 码进行分析，看看对这些变量的操作在目标代码中是如何实现的，并从中总结出 控制流，数据流，库函数恢复的规律。 我们实验选择的高级语言是a s 2 0 语言，因为该语言程序与c 语言程序很相 似，而c 语言被程序开发人员广泛使用，且包含的数据类型和操作也很丰富。 编译器我们选择了v i s u a ls t u d i 0 2 0 0 3 ，它是一个具有代表性的编译器，它很简单 但功能很全，允许的数据类型和操作也很丰富，所以它是我们理想的实验目标。 我们的实验是在i n t e l8 0 x 8 6 体系结构的机器上进行的，因为这种机器最普遍。 我们先根据m a c r o m e d i af l a s h 8 帮助里的a c t i o n s c r i p t 2 0 语言参考里的 a c t i o n s c r i p t 语言元素里面的例子，里面包含了各种数据类型的变量，还有对这 些变量的各种操作。然后将它们编译成机器代码程序( 保存在* s w f 文件中) ，接 着将这些机器代码程序反汇编成对应的汇编程序，因为这些汇编程序和源程序编 译得到的机器代码是一一对应的，所以可以把这些汇编程序作为我们分析的目标 代码，最后对这些目标代码进行仔细分析，研究源程序中的各种变量在目标代码 中的实现，并进而得出有关结论。 1 3 论文结构 本文的组织结构安排如下： 第1 章说明了反编译的研究背景及其用途，以及内容和结构安排。 第2 章介绍了反编译的关键技术。三个最重要也最难的模块：数据流分析、 控制流分析、库函数识别。 2 武汉理工大学硕士学位论文 第3 章介绍反编译系统d e c o m p i l e r 的技术分析，包括反编译的模式，以及 我们选择的基于模式识别的反编译模式，句法分析，语义分析，中间代码生成， 控制流图生成。 第4 章介绍了反编译系统d e c o m p i l e r 的运行环境和具体实现过程。 第5 章总结与展望。对本文研究内容做了总结，并指出了反编译的下一步 研究工作。 3 武汉理工大学硕士学位论文 第2 章反编译的关键技术 反编译，是将以机器代码级语言书写的源程序翻译成与其等价的编译器级语 言书写的程序的过程【3 1 。反编译器作为一种软件工具，其实现的功能相当于编译 器的逆过程【4 】。它是软件逆向工程中的一个重要组成部分。反编译的主要过程包 括数据流分析，控制流分析，库函数识别这三大主要模块。下面介绍这些知识。 2 1 数据流分析 数据流分析，即从低级中间代码到高级中间代码的转换。转换前后代码必须 保证功能上等价1 5 1 。低级中间代码是一个汇编类型的表示法，它使用寄存器和条 件码。数据流分析的过程即求解方程式的过程【6 】。具体阶段包括：无用指令的清 除、条件码的清除、寄存器参数和函数返回寄存器( 组) 的确定、通过再生表达 式来清除寄存器和中间指令、实际参数的确定、以及在跨函数调用之间传播数据 类型。 2 1 1 数据流分析的阶段 1 死寄存器清除 如果一个寄存器用一条指令定义了、而且在它被后来的指令重新定义之前没 有被使用，那么这个寄存器是死的1 刀。如果定义死寄存器的那条指令只定义了这 一个寄存器，我们认为该指令是无用的，因而把它清除掉。另一方面，如果该指 令还定义了其它寄存器( 组) ，那么该指令仍然是有用的，但是不应该再让它定 义死寄存器了。在这种情况下，我们把该指令修改成反映该事实的。死寄存器分 析是利用有关寄存器的定义一使用链1 9 l 来求解，因为定义一使用链【9 】说明了哪些指 令使用了该定义的寄存器；如果没有指令使用这个寄存器，那么该寄存器是死的。 2 死条件码清除 如果一个条件码( 或标志) 用一条指令定义了而且在重新定义之前没有被使 用，那么它是死的【引。因为一个条件码的定义是某一条指令的边缘效应( 副作用， 即该指令还有其它功能) ，所以清除死标志不造成某一条指令多余，因此指令不 因为死标志而被清除。在这个分析中，一旦确定某一个条件码是死的，就不再需 要让那一条指令来定义它了，因此，把这个信息从那条指令中去掉。关于条件码 的信息以集合的形式保持在一条指令中：一个被定义的条件的集合和一个被使用 4 武汉理工大学硕士学位论文 的条件的集合( 置位) 。用来寻找死条件码的分析类似于死寄存器分析使用 定义一使用链。但是这次不需要使用一定义链，因为没有指令被清除。 3 条件码传播 死条件码清除去掉了所有在程序中没有被使用的条件码的定义。剩下的所有 条件码定义在其定义后面的指令中有一个使用，而且将在弄懂这些条件的本质以 后把它们清除。该问题能够用条件码的定义一使用链或使用一定义链解决，不论用 此二者中哪一个办法都得到相等的解。 4 寄存器参数转化 寄存器调用约定是编译器用来加速函数调用。在大多数现代编译器中这是一 个可用的选项，而且也在编译器运行时支持例程所使用。给定一个函数，寄存器 参数转化成在函数中要使用的寄存器在该函数定义这些寄存器之前；也就是 说，在整个函数中向后影响寄存器的使用。 5 函数返回寄存器( 组) 函数在寄存器返回结果，而没有机器指令表明哪些寄存器被函数返回。在函 数返回之后，调用者在重新定义它们之前使用函数返回的寄存器( 即，这些寄存 器在函数调用后跟着的基本块入口上是活的) 。我们跨函数边界传播这个寄存器 信息，并且用一个延伸的活的寄存器分析求解。 6 寄存器拷贝传播 寄存器拷贝传播方法就是，对于一个在一条赋值指令中被定义的寄存器( 以 a x = c x 为例) ，在引用或使用它的后继指令( 组) 中，如果在这条赋值指令之 后两个寄存器都没有被修改( 即，重新定义) ，那么就把a x 代换【l o 】。就这个例 子来讲，对寄存器a x 的引用被替换成对寄存器c x 的引用，而且，如果a x 的所 有使用被c x 代替，那么a x 变成死的并且赋值指令被清除。如果a x = c x 是延伸到 那个a x 使用的唯一的a x 定义、而且在指令a x = c x 之后没有给c x 赋值的话，那 么一个a x 使用可以用一个c x 使用代入。前一条件是用寄存器的使用一定义链来 检查。后一条件是用一个r c l e a r 条件来检查。 7 实际参数转化 传给一个函数的实际参数通常是在对函数调用之前入栈。因为大多数语言允 许嵌套的函数调用，被推入栈中的参数可以是多个函数的参数，因此，有必要确 定哪些参数属于哪一个函数。我们用一个表达式栈来储存与p u s h 指令关联的表 达式。每当遇到一个c a l l 指令，所需要的参数个数从栈中被弹出1 1 1 1 。 8 跨函数调用的数据类型传播 在用实际参数实例化形式参数的期问，这些参数的数据类型需要被验证，因 为如果两个数据类型是不同的，那么其中一个需要被修改【l 引。 5 武汉理工大学硕士学位论文 9 寄存器变量清除 寄存器变量转化成一个高级语言程序中的局部变量。这些寄存器用新的局部 变量名字代替。这个名字替换在数据流分析期间进行【1 3 j 。 2 1 2 数据流分析的过程 为了在中间代码上进行改善代码的转换，反编译器需要在整个程序中收集关 于寄存器和条件码的信息，并且跨不同的基本块传播该信息。该信息的收集是通 过一个数据流分析过程，即求解方程式1 1 4 l 。 从基本块中以集合的形式( 例如，g e n ( ) 和k i l l ( ) ) 收集关于被定义的或被 终止的寄存器信息，然后在基本块入口和出口以集合的形式( 例如，i n ( ) 和o u t ( ) 集合) 做统计。对于基本块b l ，一个典型的数据流方程式有以下形式【1 5 j ： o u t ( b 1 ) = g e n ( b 1 ) u ( i n ( b 1 ) 一k i l l ( b 1 ) ) 它表示“在基本块b ；出口的信息或者是在b 。上生成的信息、或者是进入该 基本块而且没有在该基本块内被终止的信息 。统计信息i n ( ) 是从该图的前导 结点收集，其方程式形式如下【1 6 】： i n ( b 1 ) = u p e p r e d ( b 1 ) o u t ( p ) 它收集在任何前导结点的出口可用的信息。因为从前导结点收集的信息是来 自任何一个路径( 即，并非所有的路径需要有相同的信息) ，所以这个数据流问 题被归类为一个任何路径( a n y - p a t h ) 问题。任何路径问题是前导结点与后续结 点联合表现的方程式，具体取决于问题本身。 类似地，所有路径( a l l p a t h s ) 问题是用一个方程式给予说明的数据流问 题，这个方程式在所有的路径中( 从当前基本块到后继结点或前导结点) 收集可 用的信息，具体取决于问题的类型。 下面介绍向前流和向后流的定义： ( 1 ) 向前流：o u t 0 集合是根据在相同基本块里的i n ( ) 集合计算的，且i n ( ) 集合是从前导基本块的o u t0 集合计算的【l 刀。 ( 2 ) 向后流i n ( ) 集合根据在相同基本块里的o u t0 集合计算的，且o u t0 集合是从前导基本块的i n ( ) 集合计算的【1 8 】。 表2 1 是它们对应的数据流分析方程式： 6 武汉理工大学硕士学位论文 表2 1 数据流分析方程式 向前流向后流 任何o u t ( b ) = g e n ( b ) u ( i n ( b ) 一i n ( b ) = g e n ( b ) u ( o u t ( b ) 一 路径k i l l ( b ) ) k i l l ( b ) ) i n ( b ) = u p e p r e d ( b ) o u t ( p )o u t ( b ) = us s u c c ( b ) i n ( s ) 所有o u t ( b ) = g e n ( b ) u ( i n ( b ) 一i n ( b ) = g e n ( b ) u ( o u t ( b ) 一 路径k i l l ( b ) )k i l l ( b ) ) i n ( b ) = npep r e d ( b ) o u t ( p )o u t ( b ) = ns s u c c ( b ) i n ( s ) 一般来说，数据流方程式没有唯一解；但是在数据流问题中，我们关心的解 是满足方程式的最小或最大的固定点解【l 训。对于向前流问题，找到这个解是通 过把头基本块的i n ( b ) 集合的初始值设定为一个边界条件，而对于向后流问题， 找到这个解是通过把出口基本块的o u t ( b ) 集合的值设定为一个边界条件。根据 该问题的说明，这些边界条件集合被初始化为空集或全集( 即，所有可能的值) 。 函数内的数据流问题只求解与一个函数有关的方程式，而不考虑被其它函数 使用或定义的值。由于这些问题是流向不敏感的，因此为所有最初结点( 对于向 前流问题) 或所有出口结点( 对于向后流问题) 设定边界条件。函数间的数据流 问题则求解与一个程序的函数有关的方程式，它考虑到由被调用函数使用或定义 的值。信息在调用图的函数之间流动。这些流向敏感的问题只为程序调用图的 m a i n 函数设定边界条件，而所有其它函数都是从调用图中所有的前导结点( 对 于向前流问题) 或所有的后继结点( 对于向后流问题) 统计信息。 在调用图中每个调用结点有两个结点：( 1 ) c a l l 结点：有一个去往被调用 者函数头结点的出边；( 2 ) r e t c a l l 结点：有一个来自被调用者函数返回结点 的入边。 使用以下两个步骤来去掉在无关函数上的信息传播。( 1 ) 信息流动只经过 普通结点和调用边；从调用图中把返回边去掉了。( 2 ) 信息流动只经过普通结 点和返回边；从调用图中把调用边去掉了。步骤( 2 ) 使用在步骤( 1 ) 中计算的 统计信息i 硎。 给定一个函数的控制流向图，数据流方程式可以用两个方法求解：迭代方法， 用一个解反复计算直至遇到一个固定点；区间方法，为某一个区间建立一个解， 然后向那个区间里的所有结点传播这个解。这些方程式没有唯一解，但是我们把 最小的解作为答梨2 1 1 。 7 武汉理工大学硕士学位论文 2 2 控制流分析 控制流分析主要是利用控制流图( c o n t r o lf l o wg r a p h ) 将非结构化的中间 语言转化成结构化的高级语言的过程【捌。下面详细介绍其转化过程。 2 2 1 高级语言控制结构 高级语言的控制结构总的可分为三大类：顺序结构、循环结构、条件判断结 构，为了使反编译系统具有更好的通用性，选择的高级控制结构应该足够通用， 现细分高级语言的控制结构如图2 1 所示： 1 基本结构单元：单一的基本块结点是一个动作。 2 顺序结构：由两个结构组成的序列是一个顺序结构。 3 条件结构：含有i f e l s e 形式的结构。 4 先测试循环：含有w h i l e ( p ) d os 形式的循环，其中p 是一个断言，而 8 武汉理工大学硕士学位论文 s 是一个结构，这是一个先测试循环结构。 5 单一分支条件结构：只含有i f 而没有e l s e 形式的条件结构，是一个单 一分支条件结构。 6 1 1 路条件结构：s w i t c h c a s e 结构，这是一个1 3 路条件结构。 7 后测试循环：含有d o w h i l e 形式的循环，是一个后测试循环结构。 8 多出口循环：当w h i l e 循环里含有多个e x i t 出口的结构，如下： w h i l e ( p 1 ) s l ； i f ( p 2 ) e x i t ； s 2 ： i f ( p 3 ) e x i t ： s 3 ； ) 其中s 1 ，s 2 是语句( 结构) 、而p 1 ，p 2 是条件，这是一个多出口循环 结构。每个e x i t 语句从循环分支转移到该循环之后的第一个语句基本块。 9 无穷循环：f o r ( ；) ，w h i l e ( 1 ) 等的结构。 1 0 多级出口：一个e x i t ( i ) 语句导致封闭无穷循环i 的终止。 1 1 多级循环：嵌套的f o r 或w h i l e 循环结构。 1 2 g o t o 语句：它用来转移控制给任何其它基本块，不管唯一入口条件。 通过对常用的高级语言的分析，上图中前8 种高级控制结构最为常用，其它 几种高级控制结构并不常用，而且可以用g o t o 语句和前8 种控制结构的适当组 合替代，所以反编译系统中选择前8 种再加上g o t o 语句作为对控制流图结构化 后能得到的高级控制结构。 控制流图的结构化算法主要包括两部分：循环结构的结构化；条件语句结构 的结构化。 2 2 2 控制流分析的基本原理 控制流分析是整个反编译的主要工作。由于机器语言程序是非结构化的，它 不存在与高级语言程序中相同的结构，只有简单的跳转语句是控制语句，要把机 器语言程序转化成结构化的高级语言程序，就必须对控制流进行分析，从中归约 出高级语言程序的结构，且保证在功能上的等价。 步骤如下： ( 1 ) 将中间语言的控制流图( c f g ) 画出； ( 2 ) 对控制流图进行结构化，以转化成功能和语义上均等价的，由一组高 9 武汉理工大学硕士学位论文 级控制结构( 如循环、条件等) 组成的结构化的控制流图。 ( 3 ) 当这组高级控制结构无法对给定的控制流图结构化时，还需要用到g o t o 跳转语句。 ( 4 ) 这个含有高级控制结构的控制流图对应了控制流分析后的高级语言程 序。 通过以上步骤画出控制流图后，就可对其进行结构化，即控制流分析i 矧。 下面介绍控制流分析里涉及到的几个基本概念： 基本块( b a s i cb l o c k ) ：程序中的一个连续的语句序列，控制流从它的开始 进入，并从它的末尾离开，不可能有中断或分支( 末尾除外) 2 4 1 。 对一个只有简单跳转语句的指令序列，划分基本块的算法如下： 1 首先确定入口语句( 即基本块的第一个语句) 的集合。所用规则如下： ( 1 ) 第一个语句是入口语句。 ( 2 ) 任何能由条件转移语句或无条件转移语句转移到的语句都是入口语句。 ( 3 ) 紧跟在转移语句或条件转移语句后面的语句是入口语句。 2 对于每个入口语句，其基本块是由它和直到下一个入口语句( 但不包含 该入口语句) 或程序结束的所有语句组成。 控制流图( c o n t r o lf l o wg r a p h ) ：程序的一种图形表示，该图以基本块为节 点，用以表示计算，包含程序入口语句的基本块是唯一的首节点；有向边表示控 制涮2 5 1 。当满足以下条件之一时，从基本块b l 有一条指向b 2 的有向边： ( 1 ) 从b l 的最后一条语句有条件或无条件转移到b 2 的第一条语句； ( 2 ) 按程序的次序，b 2 紧跟在b l 之后，并且b l 不是结束于无条件转移。 控制流图的结构化算法主要包括两部分：循环结构的结构化；条件语句结构 的结构化。其中利用到了编译器理论中的处理控制流图的区间理论( i n t e r v a l t h e o r y ) 2 6 l 。 2 2 3 区间理论 给定一个结点h ，区间i ( h ) 是单一入口的极大子图，在其中h 是唯一的入口 结点，而且所有闭合的路径包含h 。这个唯一的区间结点h 叫做区间头结点，或 简称头结点。通过选择正确的头结点集合，图g 能够被划分成一个唯一的不相交 区间集合i = i ( h 。) ，i ( h ：) ，i ( h 。) ) ，这里n 1 。 1 0 武汉理t 大学硕士学位论文 砖h t ， f 。觑a 5 卿 图2 2 图的区间 在图2 2 e p 的例子表示一个图g ，用点框表示它的区间。这个图有两个区间， i ( 1 ) 和i ( 2 ) 。区间i ( 2 ) 包含一个循环，这个循环的范围由回边( 4 ，2 ) 决定。 一个区间是控制流图中的一个最大单入口子图，且要满足区间中每个封闭的 路都要经过这个入口点。一般称该入口点h 为区间头节点。根据区间理论，一个 控制流图g 总能划分成若干个不相交的区间的并。即g = i ( h 1 ) ui ( h 1 ) u u ( h n ) ，n 是某个常整数。有相应的算法可以实现区间的划分。在对控制流图g 作 了区间划分以后，如果对每个区间均用一个节点代替，对得到的新的图再划分区 间，再将区间用节点代替，区间之间的边不变，如此反复变换，可产生一个图的 序列，称为图的导出序列。最后得到的图称为g 的限制流图，若限制流图是个平 凡的图( 即只有一个节点) ，就称g 是可归约的。否则，限制流图必含有如下结构 的不可归约子刚z 7 j ： 图2 3 不可规约子图 此时，称g 是不可归约的。反编译中出现的绝大多数控制流图都是可归约 武汉理工大学硕十学位论文 的，这类图较好处理。但也会有不可归约的图的情况，这时就要用到g o t o 语句 了。 2 2 4 可规约控制流图的结构化算法 1 循环结构的结构化算法： 划分区间_ 在区间中寻找回边一确定循环叶确定循环中的所有点_ 确定循 环类型一确定循环的跟随节点一根据导出序列的信息确定循环的嵌套层次【冽【2 9 】 ( 内部循环先被分析出来) 。 这里，回边指的是从控制流图中下层节点回到上层节点的边，回边是确定循 环的关键依据。循环结构又可分为三类：前部测试循环结构( w h i l e 循环) ；后部 测试循环结构( d ow h i l e 循环) ；无限循环结构。可以根据循环的头节点或尾节点 包含的信息判断出究竟是哪种循环结构。循环的跟随节点就是循环一结束马上进 入的那个节点，一般一个循环对应一个跟随节点，也有例外，如多出口循环就对 应多个跟随节点。循环的嵌套层次是个很重要的信息，在结构化算法的最后要充 分利用区间理论的导出序列的有关信息来从内到外地确定其嵌套层次。 2 条件语句结构的结构化算法： 分几种情况来分别处理：2 分支条件语句结构；复合条件语句结构( 短路求 值) ；多分支条件语句结构。 a ) 2 分支条件语句结构：先确定条件语句的头节点和跟随节点，然后根据 是否某一分支直接到跟随节点来判断是单一分支条件语句结构( i f ) 还是2 - 分支 条件语句结构( i f e l s e ) 。 m 复合条件语句结构：所有复合条件语句产生的控制流子图是非结构化的， 如下图是四种复合条件语句对应的短路子图： 图2 4 四种短路子图 这些子流图具有共同的特征： 1 2 武汉理工大学硕士学位论文 ( 1 ) 节点x 和y 都是2 分支的。 ( 2 ) 节点y 只有一条入边。 ( 3 ) 节点y 只有唯一一条指令，即条件跳转指令( j c o n d ) 。 ( 4 ) 节点x 和y 必须到达共同的t 或e 节点。 根据这些共同的特征，再加上子图的具体形状，完全可以准确地结构化复合 条件语句结构。 曲多分支条件语句结构：结构化算法与2 分支条件语句类似。在确定了头 节点和跟随节点之后，根据跟随节点有几条入边即可判断分支数目。 3 各个结构化算法的应用顺序： 应用顺序如下：多分支条件语句结构的结构化_ 循环结构的结构化_ 2 分 支条件语句结构的结构化。复合条件语句结构的结构化在任何时候进行都可以。 2 2 5 不可规约控制流图的结构化算法 如果一个图包含一个有标准不可归约流图形状的子图，如图2 3 ，那么它是 不可归约的。基本上，如果一个图有两个或多个入口，至少两个入口由相同的共 同结点支配，而且这个共同结点支配该循环的入口结点，那么一个图是不可归约 为的。 对于这样的子图，因为一个反编译器结构化算法的目标是不修改控制流向图 的语义和功能，结点分割法没有用来结构化不可归约图，因为新结点的加入会修 改程序的语义。因此期望不使用结点复制而把该图结构化，即保持该图为一个有 g o t o 跳转的不可归约图，再将其结构化为2 分支条件语句，把3 节点作为这个 条件语句的跟随节点，2 节点和3 节点间的循环用g o t o 语句来代替表示闭j 。 2 3 库函数识别 库函数的识别主要是利用签名生成器，它用来识, n - - 进制代码中的病毒、编 译器和库函数。 2 3 1 签名生成器 签名生成器是一个为输入文件自动生成签名的程序。确定哪些函数是库函数 哪些是编译器启动代码，对于库函数用它们的名字代替它们，对于编译器启动代 码从目标输出代码中去掉它们。这用于某些不共享库而是将库函数的目标代码绑 入程序二进制映像的操作系统。在二进制程序中没有储存函数的名字或参数，因 此，没有办法区别它们和用户编写的函数，不可能从其它函数区分出它们。而对 武汉理工大学硕士学位论文 于共享库函数的操作系统，这些函数并不成为二进制程序的组成部分，而是在程 序中有对它们的引用，因此，函数的名字被储存在二迸制文件中( 最有可能在头 部节中) 1 3 1 】。 为一组库函数产生一个签名文件以后，调用一个接口过程根据库签名检查一 个特定的函数是否匹配库签名，以便决定要不要由反编译器反汇编器对它进行 语法分析1 3 2 1 。如果一个函数匹配其中一个签名，那么函数用它的名字( 即函数 在库中的名字，比如p r i n t f ) 代替并且做上记号，以便不再需要对它做任何分析。 这样，需要被分析的函数数目减少了，更大的意义在于，由于那些函数调用使用 真正的库函数名而非无意义的任意名字，使得目标高级程序的可读性得到相当大 的改善。而且，由于对性能或者低级机器访问的要求，某些库函数是用汇编语言 编写的，这些程序大都没有相应的高级表示法，因此无法反编译而只能被反汇编； 库签名识别方法的应用使我们可以不必分析这一类函数，从而产生更好的目标代 码。 一个标准库文件是一个可重定位的目标文件，实现一个特定语言编译器为 用户提供的不同函数。一个库函数签名是一个二进制代码段，唯一地标识该库中 的一个函数，区别于在相同库中的其它任何函数。因为所有函数执行不同的功能， 一个包含有函数完整二进制映像的签名能够从其它任何函数唯一地标识该函数。 这个方法的主要问题在于签名的尺寸及创建它造成的