（计算机应用技术专业论文）面向java的代码混淆技术的研究.pdf

江苏大学硕士学位论文 摘要 近年来，j a v a 语言得到广泛的应用，由于j a v a 目标代码一字节码( b y t e c o d e ) 中包含了大部分的源码结构等信息，很容易被反编译成j a v a 源码，所以研究有 效的保护j a v a 字节码的方法成为当务之急。目前应用最广泛也是最有效的方法 就是软件混淆，对混淆技术的研究主要集中在控制混淆和数据混淆上，这两种 技术在一定程度上提高了程序的复杂度和抗反编译的能力。 进入2 1 世纪以来，对混淆技术的研究转移到了利用数学语言描述的理论领 域，利用密码学等数学理论研究代码混淆技术的成果不断涌现，但是这些方法 还不够成熟和完善。本文的针对此问题做了以下研究工作： 1 对d r a p e 等人提出的基于数据求精的抽象数据类型的混淆方法做了深 入研究，分析其存在的不足之处，提出了一种基于数据求精的图的混淆转换方 法。首先采用数据求精方法证明了混淆的正确性，然后形式化的描述了混淆前 后图的定义和相关操作，以及图的具体混淆过程，最后给出该方法的核心算法。 2 对w i l l i a m 等人提出的基于同态函数的混淆方法做了深入研究，给出一 种基于同念函数的方法的应用。首先描述了一维同态混淆和k 维同态混淆的相 关定义和表示方法，然后利用同态混淆变换给出了数组索引，平辗和折叠三种 变换的变换方法，以及相应的变换实例，最后给出来该方法的核心算法。 3 设计并实现了一个j a v a 字节码混淆工具( j a v ab y t e c o d eo b f u s c a t i o n t o o l ，j b o t ) ，对本文提出的两种算法进行测试分析。通过对几种典型算法混淆 变换结果的分析表明：该混淆工具可以保证程序的功能的不变性，是一种有效 的混淆转换工具；本文提出的两种混淆算法增加了程序的复杂度，可以达到软 件保护的目的。 关键词：代码混淆，数据求精，同态混淆，j b o t 江苏大学硕士学位论文 a bs t r a c t r e c e n t l y , j a v al a n g u a g ew a su s e dw i d e l y d u et o i t so b j e c tc o d e - - - b y t e c o d e c o n t a i n sm o s to ft h es o u r c es t r u c t u r ea n do t h e ri n f o r m a t i o n s ，i ti se a s yt ob e d e c o m p i l e dt oj a v as o u r c ec o d e ，s ol o o kf o ra ne f f e c t i v em e t h o dt op r o t e c tj a v a b y t e c o d ei su r g e n t c u r r e n t l yaw i d e l yu s e da n da n e f f e c t i v ew a yi ss o f t w a r e o b f u s c a t i o n ，t h i sm e t h o dm a i n l yc o n c e n t r a t e do nt h ec o n t r o lf l o wo b f u a c a t i o na n d d a t af l o wo b f u s c a t i o n ，t h e s et w ot e c h n i q u e sh a v er a i s e dt h ep r o g r a m sc o m p l e x i t y a n dt h ea b i l i t yo fa n t i c o m p i l e dt os o m ee x t e n t i n t ot h e2 1 s tc e n t u r y , t h er e s e a r c ho fo b f u s c a t i o ns h i f t e dt ot h et h e o r yo f m a t h e m a t i c a lf i e l d t h er e s e a r c h e so fc r y p t o g r a p h ya n dm a t h e m a t i c a la r ee m e r g i n g ， b u tt h e s em e t h o d sa r es t i l li m m a t u r ea n di m p e r f e c t ，s ot h i sp a p e rw i l ld ot h e f o l l o w i n gw o r k ： 1 o nt h eb a s eo ft h ed a t ar e f i n e m e n to b f u s c a t i o nw h i c hw a sp r o p o s e db yd r a p e ， t h i sp a p e rd oad e p t hs t u d i e sa n da n a l y z et h es h o r t c o m i n g so fi t ，p r o p o s e dam e t h o d o fo b f u s c a t i o nf o rg r a p h f i r s t ，u s i n gd a t ar e f i n e m e n tp r o v e dt h ec o r r e c t n e s so ft h e o b f u s c a t i o n , t h e ng i v e n t h ef o r m a l d e s c r i p t i o n t o t h ed e f i n i t i o na n dt h e c o r r e s p o n d i n go p e r a t i o n so fg r a p h ，a n dt h es p e c i f i cp r o c e s so fg r a p ho b f u s c a t i o n ， f i n a l l y , g i v e no u tt h ec o r ea l g o r i t h m 2 o nt h es t u d yo ft h eh o m o m o r p h i co b f u s c a t i o nw h i c hw a sp r o p o s e db yw i l l i a m ， t h i sp a p e rg i v e na na p p l i c a t i o nm e t h o do fo b f u s c a t i o nf o ra r r a y f i r s t ，d e s c r i b e dt h e d e f i n i t i o na n dr e p r e s e n t a t i o no fo n e - d i m e n s i o na n dk - - d i m e n s i o nh o m o m o r p h i c o b f u s c a t i o n ，t h e ng i v e nt h ea r r a yi n d e x ，f l a t t e n i n ga n df o l d i n gt r a n s f o r m a t i o no nt h e b a s eo fh o m o m o r p h i co b f u s c a t i o nt r a n s f o r m a t i o n ，a n dt h ec o r r e s p o n d i n gi n s t a n c eo f t h e m ，f i n a l l y , g i v e no u tt h ec o r ea l g o r i t h m 3 i no r d e rt o t e s ta n da n a l y s i st h ea l g o r i t h mp r o p o s e di nt h i sp a p e r , aj a v a b y t e c o d eo b f u s c a t i o nt o o l j b o tw a sd e s i g n e da n di m p l e m e n t e d t h r o u g ht h e r e s u l t so fs o m et y p i c a lp r o g r a ms h o wt h a tt h i st o o lc a ng u a r a n t e et h ei n v a r i a n c eo ft h e 一一 江苏大学硕士学位论文 p r o g r a m sf u n c t i o n ，i 毒a ne f f e c t i v eo b f u s c a t i o nt o o l ；t h et w oa l g o r i t h m sp r o p o s e di n t h i s p a p e ra d d e dt h ep r o g r a m sc o m p l e x i t y , c a l la c h i e v et h ep u r p o s eo fs o f t w a r e p r o t e c t i o n k e y w o r d s ：c o d eo b f u s c a t i o n ，d a t a r e f i n e m e n to b f u s c a t i o n ，h o m o m o r p h i c o b f u s c a t i o n ，j a v ab y t e c o d eo b f u s c a t i o nt o o l i 一 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定， 同意学校保留并向国家有关部门或机构送交论文的复印件和电子版， 允许论文被查阅和借阅。本人授权江苏大学可以将本学位论文的全部 内容或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存和汇编本学位论文。 本学位论文属于 保密口，在年解密后适用本授权书。 不保密 学位论文作者签名：亳p 玉套、 2 0 l o 年6 月1 日 指导教师签 纠口年易月7 独创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究工作所取得的成果。除文中已经注明引用的内容以外，本 论文不包含任何其他个人或集体已经发表或撰写过的作品成果。对本 文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。 本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：郭玉於、 日期：2 0 j o 年6 月c 7 日 江苏大学硕士学位论文 1 1 研究背景及意义 第一章引言 j a v a 是由s u n 公司开发的新一代编程语言，自1 9 9 5 年推出以来，j a v a 已经 逐步成为业界最流行的软件开发平台，被业界广泛接受，各大公司纷纷推出各 自支持j a v a 的产品。j a v a 语言从诞生之日起就以“一次编译，到处运行”的简 单性、跨平台性等赢得许多著名公司的青睐。大量的开发人员、成熟的开发模 式以及丰富的开发资源，已经使j a v a 成为企业级应用程序的主流开发工具。它 彻底改变了应用软件的开发模式，带来了软件开发的一次革命。目前，j a v a 软 件广泛的应用在各类企业应用、嵌入式应用和移动终端等领域，为高速发展的 信息技术带来了新的动力。 j a v a 程序的编译过程与c c + + 程序的编译过程截然不同。c c + + 程序经编 译后生成的是二进制的机器码，这种代码只有在特定平台上才能运行，通过查 找表编译器可以将所有变量和方法符号的引用转换成特定的内存偏移量【1 1 。而 j a v a 编译器却既不能把变量和方法等符号的引用转换为数值引用，也不能确定 程序执行过程中的内存布局，而是将这些符号的引用信息保留在c l a s s 文件中【2 1 ， 由解释器在运行过程中创建内存布局，然后再通过查找表来确定一个变量或方 法所在的地址【3 1 。因此j a v a 字节码文件中保留了所有方法和变量的信息符号， 而这些符号根据编码规则通常带有语义信息【4 】，这就为反编译j a v a 类文件提供 了可能。也正是由于j a v a 本身的这种特性，使得j a v a 类文件很容易被反编译成 与原文件非常相似的文件，这就严重威胁到开发者的权益和信息的安全性，所 以寻求一种有效的保护j a v a 软件的方法【5 。7 】成为当务之急。 为了保护j a v a 类文件程序，代码混淆技术应需而生。代码混淆技术是在不 改变程序功能的前提下，对代码进行混淆变换，使得混淆后的代码更难以被反 编译。j a v a 语言的迅速发展推动了对代码混淆技术的研究热潮，通过对j a v a 字 节码混淆变换，可以有效的保护j a v a 软件开发者的权益和信息的安全。同时这 个研究过程也可以推动计算机科学向前发展。 江苏大学硕士学位论文 1 2 国内外研究现状 代码混淆技术是2 0 世纪9 0 年代末兴起的一种软件安全保护技术。它的基 本思想就是利用代码混淆技术对软件的代码部分进行混淆变换，增加混淆后代 码的复杂度，从而增加了反编译的难度。国内外的学者对此方面做了大量的研 究，并且出现了很多相对成熟的混淆方法。 c o l l b e r g 等人【8 - l o 】最先对代码混淆技术进行了详细的介绍与分析，对主要的 混淆算法进行了总结和分类，还提出混淆算法的有效性和性能的评价标准等相 关概念。他将混淆变换分为四类：外形混淆、控制混淆、数据混淆以及预防性 混淆。外形混淆变换的目的是改变源程序的信息格式，主要包括混淆变量名、 去除注释以及改变程序的文本格式；控制混淆变换主要包括增加混淆控制分支 以及控制流重组等；数据混淆变换主要包括存储与编码变换、聚集变换( 将多个 变量或对象组织在一起1 、次序变换；预防性混淆变换是通过添加别名等方法抵 抗反编译工具的攻击。 k e l l y 等人【1 1 】构造了一种混淆执行机制，用来自动实现构造代码的混淆算 法。t y m a 等人【1 2 】根据j a v a 语言的特点，提出了一种新的外形混淆技术。文献 【1 2 】【1 3 】对j a v a 的外形混淆算法进行了更加系统的研究。w a n g 等人【1 4 】构造的代 码混淆算法实现了对源代码上的多种控制混淆变换和数据混淆变换，并且对静 态分析工具如何获取程序语义做了深入的研究，通过使用基于保护控制变量和 控制流压平技术降低了静态程序分析工具的分析精度。o g i s o 等人【1 5 】又进一步 对w a n g 等人提出的混淆算法进行了扩展，使得混淆算法应用于过程内的限制 得到了很好的解决，并提出了过程间混淆算法。他们把函数指针作为混淆对象 以增加静态程序分析工具对混淆后的程序分析的难度。m i k h a i l 等人【1 6 】对类设计 层次的混淆算法进行了研究，并提出了通过对类进行分裂，合并以及类型隐藏 等方法来增加类继承关系的复杂度，从而实现对类的混淆。h o u 等人【1 7 】实现了 烟雾和镜子变换、高级语言削弱变换以及改变控制流变换三种控制流混淆算法， 同时将它们应用于j a v a 软件中，并用多种反编译工具进行测试，结果验证了这 三种算法的混淆效果。s t a s h i 等人【1 8 】通过研究辅助输入虚拟黑盒零知识和零知 识的差距，对代码混淆进行了形式化定义。w m b l e w s 等人【1 9 1 对代码混淆技术做 了形式化描述。 江苏大学硕士学位论文 h o u l m l 提出了用带有时间限制的黑盒方法来保护移动代理，这里的黑盒就 是指混淆变换过的代理程序。对移动代理进行逆向工程，发现或修改软件中的 关键信息需要一定的时间，据此在派发移动代理之前，对其进行混淆变换能有 效限制移动代理在目的主机上运行的时间，增加逆向工程的代价，从而延长在 目的主机上的运行时间。针对移动代理在内的程序都可能受到黑盒测试攻击问 题，h o u l 2 1 】提出了一个用来检测移动代理的运行的协议。另外，还提出了针对 可执行代码和汇编指令的混淆技术。 进入2 1 世纪之后，代码混淆技术研究的重点集中在利用数学语言描述的理 论领域，利用密码学等数学理论研究代码混淆技术的成果不断涌现：a p p l e 等 人【2 2 】利用密码学理论提出了对混淆算法的攻击是n p 复杂度问题；b a r a k 等人【2 3 】 证明了某些类型的函数无法进行有效的混淆；l y n n 等人【纠提出了一种利用形式 化证明来研究混淆技术的数学方法。目i j i 数学与密码学是代码混淆技术的两个 最主要的研究手段。 目前国内关于代码混淆技术【挥3 0 】的研究基本上处于跟踪国外研究发展的阶 段，关于代码混淆技术方面的研究成果多集中于对控制流混淆和类结构混淆， 对较新的把数学和密码学应用于软件混淆的这种混淆方法涉及甚少，所以本文 将主要对这方面进行研究。 1 3 主要研究内容 本文的研究内容主要包括以下几个方面： 1 深入研究了基于数据求精的抽象数据类型的混淆转换方法，分析其存在 的不足之处，提出了一种基于数据求精的图的混淆转换方法。首先用数据求精 方法证明了混淆的正确性，然后形式化描述了混淆前后图的定义及相关操作， 给出了图的具体混淆过程，最后给出了此方法的核心算法。这种方法的提出不 仅增加了图的抗反编译和静态分析能力，而且也完善了利用数据求精方法混淆 抽象数据类型的应用。 2 深入研究了同余、同态、同构这一新的混淆变换研究方法，给出了一种 基于同态函数的数组的混淆变换方法。首先介绍了一维同念混淆和k 维同态混 淆的相关定义和表示方法，然后利用同态混淆变换给出了数组索引，平辗和折 江苏大学硕士学位论文 叠三种变换的变换方法，以及相应的变换实例，最后给出来该方法的核心算法。 3 设计并实现了一种j a v a 字节码混淆工具( j a v ab y t e c o d eo b f u s c a t et o o l ， j b o t ) ，给出系统设计思想、系统模型、工作流程和它的两个主要模块的详细 设计。并通过对测试结果进行分析，从混淆算法的正确性、时间过载、空间过 载和有效性等方面，验证了这两种混淆方法的有效性。 1 4 本文的内容安排 第一章为引言部分，介绍了代码混淆技术的研究背景和意义，代码混淆技 术的国内外研究现状，引出问题，提出本文的研究方向。 第二章对当前存在的几种混淆技术进行了研究，包括词法变换、控制混淆、 数据混淆和类结构混淆，为后文混淆方法作铺垫；接着介绍了代码混淆技术的 性能与度量方法，为评价本文的两种混淆算法提供了标准和依据。 第三章是本文重点章节之一，对利用数据求精方法混淆抽象数据类型的方 法做了深入研究，针对当前图应用的广泛性和重要性，提出了一种基于数据求 精的图的混淆转换方法。首先用数据求精方法证明了混淆的正确性，然后给出 了混淆前后图的定义及相关操作的形式化描述，最后给出了图的具体混淆过程。 第四章也是本文的重点章节之一，是针对第三章图的混淆过程中引入的用 来存储节点和相关参数的数组而展开的，通过混淆数组，来进一步增强图的混 淆程度。并且对基于同态函数的混淆方法做了深入的研究，给出了一种基于同 态函数的数组的混淆转换方法。 第五章是为验证第三章和第四章的混淆方法而设计的，详细介绍了系统的 设计模型和工作流程，最后给出了两种混淆方法的核心算法，这两种算法也是 该系统核心模块的主要算法。 第六章是对混淆工具j b o t 的功能测试和性能分析，包括正确性、时间过 载、空间过载和有效性，间接的证明了混淆方法的有效性。 第七章是全文的总结和展望，总结了全文的主要研究内容以及研究成果， 并对文章的不足之处以及如何进一步研究进行了规划和展望。 江苏大学硕士学位论文 第二章代码混淆技术 本章具体研究了现有的较为常用的几种代码混淆技术，首先给出代码混淆 的定义，然后介绍了词法变换混淆、数据混淆、控制混淆和类结构混淆，最后 给出了代码混淆的性能与度量的方法。 2 1 代码混淆的定义 代码混淆技术【3 1 。3 5 】是一种重要的软件保护方法，混淆的实质就是一种变换， 通过这种变换把原来的代码变成与其功能相同或相近的，但是更难被理解和反 编译的代码。由于混淆技术可以根据不同的目的，不同的混淆对象采用不同的 方法，这使得混淆方法非常多。 给定一个程序p 、混淆策略t ，经过混淆变换后得到程序p 。 混淆前 的程序p 相同输出 图2 1 混淆变换原理示意图 混淆后的 程序p ， 图2 1 变换过程称之为混淆变换，即对程序进行一种功能保持一致的变换， 变换后的程序p ，拥有和原程序p 相同的功能。更确切的说应该满足以下两个条 件： 如果p 出错终止或终止失败，p 不一定终止。 p 和p 在正常终止情况下，p 必须产生与p 相同的输出。 原程序和混淆程序所不同的是：经过混淆变换t 后的p 比p 更难被反编译， 生成的程序也难以被人理解或者相关工具解析。 江苏大学硕士学位论文 2 2 代码混淆的分类 根据混淆变换原理，本文将代码混淆技术分为词法变换、控制混淆、数据 混淆和类结构混淆，以下将分别对这四种混淆技术加以阐述。 2 2 1 词法变换 词法变换的原理是对函数和变量的名称进行变换，使其违背j a v a 命名规范 中见名知义的原则。其原理依照j a v a 虚拟机规范中有关类文件结构的规定，对 常量池中存储的类、字段、方法和变量等名称的“c o n s t a n tu t f 8i n f o 类 型的数据项加以混淆，在保持程序语义不变的前提下将名字更改为毫无意义、 无规律的字符串。这种方法具有单向性，并且没有引入额外的执行代价。目前 j a v a 字节码混淆器和混淆编译器大多支持这一功能，文献 3 6 1 q b 对这些j a v a 字 节码混淆器做了介绍。 为了提高混淆算法的隐蔽性，r o o 和o o r d l 3 7 1 提出了使用标识符交换来进行 词法变换，其思想是用标识符作交换而非更改成毫无意义的名字。标识符交换 包括交换变量名、函数名和类型三种。 使用标识符交换来进行词法变换在提高隐蔽性的同时，由于标识符的保留 也为反编译者提供了方便，不具有单向性。 2 2 2 控制混淆 控制混淆【8 】是一种被广泛使用的代码混淆技术，其基本原理是通过改变程 序的判断条件，或向程序中添加不透明谓词等方法来增加程序的复杂度，并且 可以通过对程序结构和执行路径的调整，来增加反编译工具反编译程序的难度。 目前较为流行的控制混淆变换主要有以下几种：分支插入变换、循环条件 插入变换、将可化简的控制流转换成不可化简的控制流、使用对象和别名的不 透明谓词和使用并行技术构建不透明谓词等【3 8 1 。这些变换中很多都涉及到不透 明谓词这一概念，所以首先对其进行介绍。 不透明谓词：一个谓词p 在p 点若其值在混淆时，混淆者可知而反编译者 很难获知，则称它为不透明谓词。符号p p f ( p p t ) ：表示当且仅当其值在点p 恒为 江苏大学硕士学位论文 f a l s e ( t r u e ) l 扣j ，若其值在p 点有时为真有时为假，则记为p p 2 。 程序中插入不透明谓词的方法，如图2 2 所示。 2 2 2 1 分支插入变换 ( a ) f ( b ) = f )f ( b ) l _ f ( b b i - g ) ( b )( c ) 图2 2 不透明谓词插入示意图 对一串语句s = s 1 s 。，利用不透明谓词可以构造出如图2 3 ( 0 、( b ) 、( c ) 所 示的三种变换【9 】。其中对任意语句s i 、s j ，若有f ( s i ) = f ( s i ) ，则表示它们的语义 相同。其中图2 3 m ) 所示的混淆变换对抵抗动态分析【9 】有较好的效果。 对于按次序执行的语句s = s 1 s 。，增加一个控制条件，来决定后面语句的 执行顺序。通过这种方式大大增加了反编译的难度。但是必须保证所有增加的 控制条件都不会影响后续语句的执行。如图2 3 中，实线表示程序可能执行的 路径，虚线表示程序永远不会执行的路径。 江苏大学硕士学位论文 s i s 2 s 3 s n 上 s 1 s j s 1 s j 大、广 l 1 s 1 s j 7 够“。上丫土t 人f 上 ls a j 小s a iis k s 6 。 i1 j l s j 小s 。 il l s a j + 1 s a ns b j + 1 。s 6 。 l 【1 f ( s i ) = f ( s 4 i ) = f ( s 6 i ) 【vi 2 2 2 2 循环条件插入变换 图2 3 分支插入变换 f ( s o = f ( s 8 i ) ；f ( s i ) f ( s 6 i ) ( c ) 通过不透明谓词使一个循环的终止条件更为复杂，可以对循环进行混淆。 图2 4 描述的是两种可能的变换原理图。 ( a ) 图2 4 循环条件插入变换原理图 2 2 2 3 将可规约的控制流图转换为不可规约的控制流图 秘 z f 墩1 ( 】 司 上 i s k ；f ( 均 l j = 甙l ( ，j ) i 通过将一个结构化的循环变换为有多个循环，可以将可规约的控制流图转 换成不可规约的控制流图，其原理图【9 】如图2 5 所示。由于j a v a 语言规范不支 持“g o t o ”语句，这两种混淆变换在j a v a 混淆器中的实现目前依赖于对编译后 生成的j a v ac l a s s 文件进行直接操作。 江苏大学硕士学位论文 ( a ) 图2 5 可规约的控制流图转换为不可规约变换原理图 2 2 2 4 使用对象和别名的不透明谓词 堆分析可以用来确定某个引用所指向的具体类型。但是目前存在的堆分析 算法都不精确。通过剖析现有算法的缺点，可以得到廉价的、具有较好弹性和 隐蔽性的混淆算法，具体步骤如下： 1 在程序中加入一些复杂的动态结构s 1s 2 ； 2 将一些引用p 1 ，p 2 ，指向这些结构； 3 新插入的代码更新这些结构，并保持一定的不变量； 4 将上述不变量用来生成所需的不透明谓词。 算法的实现可以采用有向图来描述程序设计语言的抽象数据结构( a b s t r a c t d a t at y p e ，a d z ) 。对a d t 图的常见操作主要有：插入节点、遍历、分裂、合并、 反转等，将这些操作与a d t 图相结合就可以用于不透明谓词的生成。 2 2 2 5 使用并行技术构建不透明谓词 并行程序与串行程序相比较，更难以被静态分析。n 个并行的语句可以有 n ! 种不同的执行顺序。使用并行技术可以构造极有弹性的不透明谓词。其基本 思想【9 】是创建一个全局数据结构q ，q 可以被一组并行的程序改变，但是保持 在一个可以用于不透明谓词的状态中。此方法可以和数据流变换方法结合产生 强度和弹性较好的混淆算法。 江苏大学硕士学位论文 2 2 3 数据混淆 数据混淆是对程序中的数据域进行混淆变换。对数据的混淆变换主要有： 数组重构变换、变量重组变换、将静态数据转换成与程序相关数据、数值变量 混合变换等。 2 2 3 1 数组重构变换 数组重构变换的基本形式【8 】有：数组分裂变换、数组合并变换、数组折叠 变换和数组平辗变换。数组分裂变换是指一个数组分成两个或多个相同维数的 数组；数组合并变换则相反，将两个或多个数组合并成一个；数组折叠变换是 增加数组的维数；数组平辗变换是减小数组的维数。将上述几种方法连合使用， 可以隐藏数组数据所代表的意义，获得更好的混淆效果。本文第4 章将采用一 种新的方法来实现数组折叠和数组平辗变换。 2 2 3 2 变量重组变换 变量重组技术用于把一些简单的数据结构或数据类型，例如i n t 、b o o l e a n 等分解成一些变量的组合，从而起到隐藏原始数据的效果。将类型t 的一个变 量v 分解成另外一种类型u 的两个变量p 和q ，并提供函数f q ，q ) 和g ( v ) ，使 得这两种类型的数据相互映射，原来对变量v 的操作转换成对p 和q 的操作。 例如布尔值分解变换【1 0 】把布尔值变量v 分解成为两个整型变量x 和y ，定 义函数： v = f ( x ，y ) = h ( x ) o h ( y ) h ( t ) = t r u e t = 1 ，h ( t ) = f a l s e 兮t = o 定义函数i = 甙 ) = 2 x + y ，可得出表2 1 所示的对应关系： 表2 1 布尔值变量分解函数 x yf ( x ，y )2 x + y 00 假 0 01 真 1 l0真2 11 假 3 通过定义表2 2 所示运算表，就可以把逻辑运算转换为自定义的对整型变 江苏大学硕士学位论文 量的运算。这种自定义的运算要求运算后输出的整型变量对应的逻辑变量的值 必须符合对应的逻辑运算规则。 表2 2 整犁变量自定义运算表 b a 或运算并运算 01230123 031233000 111123123 222 1 10213 3002000 o 3 2 2 3 3 将静态数据转换成与程序相关数据 以一个静态字符串为例，可以通过混淆变换将其转化为一个函数或者一段 子程序，从而在程序的执行过程中通过调用来生成相应的字符串。 这种变换的实现并不困难，但应用时需要考虑以下两种矛盾因素： 1 在常见的应用程序中都包含大量的静态数据，如果对所有的静态数据都 进行混淆，将导致代码的执行代价和传输代价显著增加。 2 如果仅对关键的静态数据进行混淆，则等同于为反编译者提供了关键数 据的提示。 所以如何把握以上两点，是实践中需要解决的问题。 2 2 3 4 数值变量混合变换 数值变量混合变换就是将一系列的数组变量v 1 ，v 2 ，v n 合并为一个变 量v m 。例如，两个3 2 位整数变量可被合并为一个6 4 位整数变量。为了增加混 淆变换的弹性，可以在程序中加入一些不影响任何原始变量值的位操作。 2 2 4 类结构混淆 对于j a v a 程序而言，高层的程序结构，如系统类图等，能够揭示系统的设 计，帮助对程序的理解，这对攻击者来说是非常有用的。本节所讨论的类的转 换，就是希望能够改变系统类图，隐藏系统的整体架构。类结构混淆方面主要 是以s o s o n k i n 等人【1 6 l 的研究为主。为了更好的了解这种混淆技术，首先介绍有 江苏大学硕士学位论文 关术语。 设p r 是一个j a v a 程序，令c l a s s e s ( p r ) 和i n t e r f a c e s ( p r ) 分别代表程序p r 中定 义的类和接口的集合。对任意的类或者接口c ，m e t h o d s ( c ) 表示c 中定义的方法 集合，f i e l d s ( c ) 表示c 中定义的字段集合，它们不包括c 继承而来的字段或方法， 而只包括c 中新定义或重载的字段或方法。相应的还可以定义实例方法集合 i n s t a n c e m e t h o d s ( p r ) 并 l 公有方法集合p u b l i c m e t h o d s ( p r ) ，它们分别表示程序p ，中 各个类定义的所有的实例方法和公有方法。 类结构混淆主要有：类合并、类分裂、类型隐藏等。 2 2 4 1 类合并 类的合并就是将程序中的两个或多个类合并成一个类，从而破坏系统类图， 达到隐藏系统设计的目的【1 6 1 。最极端的类合并就是将所有的类都合并成一个类。 假设有两个类名c ，和c 2 ，转换为目标类c t ，且都满足以下条件： 1 c 1 和c 2 都是j a v a 1 a n g o b j e c t 的直接子类； 2 c l 和c 2 中未覆盖任何父类的成员函数( 方法) ； 3 c 1 和c 2 都未继承任何接口。 首先合并两个类中的字段和方法放在c t 中，然后重命名重名的字段和方法， 最后，将所有用c 1 和c 2 声明的对象全都改为用c 。来声明，并将相应的方法调 用改为c t 中的方法调用。形式上，类的合并可以看作是创建两种映射：字段的 映射和方法的映射，即： i lf ：f i e l d s ( c 1 ) u f i e l d s ( 呦- f i e l d s ( c t ) um ：m e t h o d s ( c 1 ) um e t h o d s ( c 2 ) 一m e t h o d s ( q ) 对于两个类中同名的方法和字段可以采用重命名的方法来处理，但构造函 数除外：对两个参数表示完全相同的构造函数可以通过对其中一个参数表添加 一个伪参数的方法来解决。 2 2 4 2 类分裂 下： 给定一个原始类c ，将其分裂为两个新的目标类c t ，1 和c t 2 。定义分裂函数如 u 印l i t ：m e m b e r s ( c ) _ 2 c t ，1 ，c t , 2 】 江苏大学硕士学位论文 该函数可以将原始类中的某一成员放到某一或全部目标类之中。一个分裂 函数是合法( v a l i d ) 的，当且仅当程序在其作用下的执行结果仍然是正确的。这 里必须要考虑的问题是类成员间的依赖关系。为了使一个分裂函数是合法的， 可以采用继承的方法来解决这一问题，其形式化的描述如下： v m m e t h o d s ( c ) ：近c l 1 us p l “m ”t h e n ：vnem e t h o d s ( c ) ：d e p e n d s ( m , n ) 号c t ，1 u 印叔n ) a n dv f ef i e l d s ( c ) ：d e p e n d s ( m , 0 号c t 1 | l 印l h ( f ) 2 2 4 3 类型隐藏 在j a v a 中除了类，还有接口( i n t e r f a c e ) 。在接口中只有方法的声明，而没有 实现；接口也是一种类型，可以用来定义对象的引用；接口定义的对象引用也 可以进行类型映射操作。所有这些特性可以被用来实现类型隐藏。 通过对一个给定的类c ，定义n 个接口i 1 ，i 2 ，i n 来代替类c 进行类型 声明，可以实现类型的隐藏。 每一个新定义的接口都只随机的包含类c 中的一小部分公有方法。实际上 这种混淆变换需要定义一个映射： uh 砌i n g ：m e t h o d s ( c ) np u b l i c m e t h o d s ( p r ) oi n s t a n c e m e t h o d s ( p r ) - i l ，i 2 ，i n 在生成了接口i 1 ，i 2 ，i n 之后使用映射um d d i n g 来修改程序p r 中与类c 相关的语句。 如果引入的这些接口只为一个类服务，则很容易被一些优化工具( 如j a x l 3 9 】 等) 所识别并且去掉。为了避免这种情况，可以使引入的接口同时为若干个类服 务，这样就使自动分析变得更加困难。 需要注意的是，类型映射在j a v a 中代价很高。由于方法的声明在不同的接 口中，使得这种混淆变换需要进行大量的类型映射。如果对程序中所有的类都 进行类型隐藏，则会大大降低程序效率。为了避免这种情况的发生，需要用户 进行有选择的混淆变换换，一般只对关键的类进行混淆。 2 3 代码混淆的性能与度量 通常情况下，对混淆后的程序从以下四个方面进行度量：强度0 0 t e n c y ) 、 弹性( r e s i l i e n c e ) 、执行代价( c o s t ) 和隐蔽性( s t e a l t h ) 。 江苏大学硕士学位论文 2 3 1 强度及其度量 强度是指混淆变换后的程序相对于原程序对恶意用户理解程序造成的困难 程度和复杂度。其定义如下【8 】： 混淆策略t 是对程序p 到程序p 的一种混淆变换，设e ( p ) 是p 的复杂度， 则t 对程序p 的强度：t o o t ( p ) = e ( p 徊( p ) 一1 。 规定t 是对p 的一个有效的混淆变换，当且仅当t p o t ( p ) 0 。 2 3 2 弹性及其度量 与强度度量不同，弹性的度量用于表征一种变换能够在何种程度上抵抗反 编译的攻击。它包括以下两个方面：( 1 ) 反编译程序设计者编写程序所需要的代 价；( 2 ) 反编译程序运行所需要付出的时间和空间代价。其定义如下【8 】： 混淆策略t 是程序p 到程序p 的一种混淆变换，令t 对程序p 的弹性 锚( p ) = r e s i l i e n c e ( t d e ，t p 。) 。其中t d 。和t p e 分别为反编译和反编译混淆程序的 开发者所付出的代价。 2 3 3 执行代价及其度量 执行代价被用来度量由于混淆变换所引起的程序执行时的额外的时间和空 问代价，其定义如下【8 】： 混淆策略t 是对混淆前程序p 到程序p 的一种混淆变换，t 对程序p 的执 行代价t o 吲( p ) 的取值如表2 3 所示。 表2 3 执行代价度量表 执行代价额外消耗资源情况 非常高昂( d e a r ) 当且仅当p 的执行比p 的执行需要额外的开销为多指数级别。 昂贵( c o s t l y ) 当且仅当p 的执行比p 的执行需要额外的开销为一次以上的多项式 级别。 低廉( c h e a p ) 当且仅当p 的执行比p 的执行需要额外的开销为一次多项式级别。 无代价( f r e e ) 当且仅当p 的执行比p 的执行需要额外的开销为零次多项式级别。 相对于强度和弹性这两种度量方法，执行代价的度量比较容易取得并且作 江苏大学硕士学位论文 定性的分析。 2 3 4 隐蔽性及其度量 隐蔽性【8 1 是指混淆变换前后的程序的相似程度。由于隐蔽性与具体被混淆 的程序密切相关，所以难以得到通用的形式化的度量方法。 2 4 本章小结 代码混淆技术是保护j a v a 软件的一个重要的方法，为了更好的研究混淆技 术，本章首先给出了代码混淆的定义，然后分析了四种主要的代码混淆技术： 词法变换、数据混淆、控制混淆和类结构混淆。其中词法变换比较容易实现， 并且不会给混淆后的程序带来额外的执行开销，但是比较容易被反编译者识破。 数据混淆和控制混淆较难实现，同时也增加了混淆后程序的空间过载和时间过 载，有待于寻求一种方法可以把两者结合，产生更好的混淆效果。类结构混淆 改变了程序的类图，可以有效地保护软件，但是改变类名使得该类对于其它接 口变得不可用。本章最后对混淆的度量方法给出详细的介绍。 后续第三章将给出一种基于数据求精的图的控制混淆变换，第四章是针对 第三章混淆过程中产生的存储数据进行混淆，给出一种基于同态函数的数组的 数据混淆变换，两章将控制混淆与数据混淆相结合，增加了程序的复杂度。 江苏大学硕士学位论文 第三章基于数据求精的图的混淆变换 目前图是一种被广泛应用的数据结构，如求两点间的所有路径问题或者两 点间最短路径问题等等，与人们日常生活紧密相关。与此同时，保护图中的数 据结构和算法也成为当务之急。本文对d r a p e 等人【柏】提出的混淆变换方法和相 关知识进行了深入的研究，提出了一种基于数据求精的图的混淆变换方法。 3 1 数据求精混淆 假设存在一数据类型d ，经过混淆之后得到数据类型o ，混淆过程包括给 出混淆数据类型d 中每个操作的定义和验证混淆的正确性。为了提供一个混淆 数据类型的框架，并且确定混淆的正确性，本章把混淆过程看作是一个数据求 精过程。求精过程可以用一个抽象函数a ( a b s t r a c t ) 和一个具体函数c ( c o n c r e t e ) 之间的状态关系r 表示： r ：a + c 当且仅当存在一个变量d t i 和一个抽象函数a f 满足： a f ：c a 时，这种数据求精过程被称之为函数求精。则关系r 可以表示成如下形式： a r c 三a f ( c ) = a 八d t i ( c ) ( 3 1 ) 函数求精必须满足每一个具体状态的数据类型都与一个抽象状态数据类型 相关，并且具体状态比抽象状态包含更多的结构。通常情况下，混淆是靠增加 更多的结构来混淆数据类型的，所以混淆后的数据类型o 比混淆前的数据类型 d 更抽象。大多数的数据求精方法是函数求精，其中一种方法是先执行一个求 精过程，然后混淆这个求精过程，从而达到混淆数据类型的目的。数据求精已 经是一个比较成熟的技术，所以本文重点主要集中在求精混淆上。 由公式3 1 可知，数据求精混淆需要一个抽象函数a f 满足： a f ：o _ d 并且，存在一个数据类型变量d t i ，对于元素x ：d 和y ：o 有： x _ y 兮x = ( 咀y ) 八d t i ( y ) )( 3 2 ) 其中x _ y 表示x 经混淆后变成y ，其中“_ ”前后的数据类型是相关的。 在混淆过程中，抽象函数起到防止反编译的作用，为此必须保证此函数的 江苏大学硕士学位论文 隐蔽性以免被攻击者得到。并且函数a f 是一个双射函数，所以若找到一个混淆 函数o f ： o f ：d _ o 满足o f ( x ) = y 号x - y ，则： a f o f = i d ( 3 3 ) 函数o f 是函数a f 的一个逆函数，但是不一定要满足： o f a f = i d ( 3 4 ) 因为可以找到另一个混淆函数o f 满足o f ( x ) = y ，并且x _ y ，所以可以推 出： o f ( a f ( y ) ) = o f ( x ) = y 当抽象函数为一个单射