（信号与信息处理专业论文）基于排列图和ppct混合编码的软件水印技术的研究与实现.pdf

武汉理工大学硕士学位论文 摘要 由于数字产品的复制和传播变得越来越经济和方便，软件安全和盗版的问 题也日益变得突出。据统计，到2 0 0 1 年软件盗版业已经有大约1 6 亿美元的产 值，而且正在快速增长。现在，软件产品已经渗透到工农业生产、商业活动和 日常生活的各个方面。所以各种软件版权保护技术成为了研究热点。目前的软 件版权保护技术主要有基于加密方法和信息隐藏技术两种。在信息隐藏领域， 主要有三种软件版权保护技术，分别是代码迷乱、软件水印和篡改验证技术， 本文主要关注软件水印技术。 软件水印从嵌入和提取方式分为静态软件水印和动态软件水印。静态软件 水印具有嵌入提取方便的优点，但是抗攻击性能较差，无法应用于对水印强度 要求高的场合。相反，动态软件水印技术具有抗攻击性能强的特点，因此具有 广阔的应用前景，也成为这一领域的研究重点。动态图软件水印技术是目前最 好的动态软件水印技术之一，核心思想是将水印信息编码成拓扑图结构，从而 使对拓扑图进行变换的保持语义攻击难以实现。提取过程是在用户输入提取密 钥后在内存中建立拓扑图，然后用解码算法将图结构恢复成水印信息，其鲁棒 性更高，隐蔽性更强。 动态图软件水印技术的核心部分就是图的编解码问题。在目前基本的编码 方式中，p p c t 枚举编码由于其结构上的优势，鲁棒性是最好的，但是缺点是编 码效率较低。为了克服这缺点，本文提出一种结合排列图和p p c t 的混合编码 方案，该方案充分利用了p p c t 在结构上的优势，又结合了排列闰编码效率高的 特点。 针对这种混合编码方案，本文在j a v a 语言中用两种方法做了实现，一种是 交换叶节点混合枚举编码，另一种是增加指针混合枚举编码。前者是通过将 p p c t 的叶节点交换位置的方式来完成排列图编码，其结构完全与p p c t 相同， 具有很好的鲁棒性。后者是用p p c t 的叶节点之间增加指针的方式来完成排列图 编码，编码过程简单，时间开销较少。 关键字：软件水印，动态图，排列图枚举编码，p p c t 枚举编码，混合编码 塞堡型兰查堂堡主堂些丝塞 a b s t r a c t s i n c ed i g i t a lp r o d u c t sc a l lb ed u p l i c a t e da n dd i s t r i b u t e de a s i l ya n de c o n o m i c a l l y ， s o f t w a r es e c u r i t ya n dp i r a c yb e c o m e sam o r ea n dm o r ei m p o r t a n ti s s u e a c c o r d i n gt o t h es t a t i s t i c si n2 0 0 1 ，s o f t w a r ea n dt e c h n o l o g yp i r a c yi ss u s p e c t e dt oc a u s e a p p r o x i m a t e l y $ 1 6b i l l i o nb u s i n e s sa n di n c r e a s er a p i d l y s o f t w a r eh a sp e n e t r a t e d a l m o s ta l lo ft h ea s p e c t so fi n d u s t r y ，a g r i c u l t u r e ，c o m m e r c ea n dd a i l yl i f en o w a d a y s ， s ov a r i o u st e c h n o l o g i e sf o rs o f t w a r ec o p y r i g h tp r o t e c t i o nh a v eb e e ns t u d i e d s of a r ， t h e s et e c h n o l o g i e sa r eb a s e do nc r y p t o g r a p h yo rs t e g a n o g r a p h y t h e r ea r et h r e ek i n d s o ft e c h n o l o g i e sa b o u tt h i si s s u ei ns t e g a n o g r a p h y ，c o d eo b f u s c a t i o n ，s o f t w a r e w a t e r m a r k i n ga n dt a m p e r - p r o o f i n g t h i s t h e s i si sc o n c e r n e da b o u ts o f t w a r e w a t e r m a r k i n g s o f t w a r ew a t e r m a r k sc a r lb ec l a s s i f i e db yt h ew a yo fe m b e d d i n ga n de x t r a c t i n g t e c h n i q u e sa ss t a t i co rd y n m - n i c a l t h o u g hi tc a nb ee m b e d d e da n de x t r a c t e de a s i l y ， s t a t i cs o f t w a r ew a t e r m a r kc a n tb ea p p l i e dt ot h es i t u a t i o nw h i c hn e e d sr o b u s t w a t e r m a r k sb e c a u s eo f v u l n e r a b i l i t y o nt h ec o n t r a r y ，d y n a m i cs o f t w a r ew a t e r m a r ki s r o b u s t n e s s ，s oi tb e c o m e sah o t s p o ti nt h i sf i e l d d y n a m i cg r a p hw a t e r m a r k ( d o w ) i so n eo ft h eb e s td y n a m i cs o f t w a r ew a t e r m a r k s t h ei d e ao fd g wi se n c o d i n gt h e w a t e r m a r ki n t ot o p o l o g yg r a p hi no r d e rt ob ei m m u n et os e m a n t i c sp r e s e r v i n ga t t a c k a f t e ru s e ri n p u tt h ee x t r a c t i o nk e y ，t h et o p o l o g yg r a p hi sr e c o n s t r u c t e do nt h eh e a p ， a n dt h e nt h ed e c o d i n ga l g o r i t h mr e t r i e v e st h ew a t e r m a r k s od g wi sm o r er o b u s ta n d s t e a l t h i e rt h a no t h e rs o f t w a r ew a t e r m a r k s t h ec o r ei s s u eo fd g w i se n c o d i n ga n dd e c o d i n g 谢t l lt o p o l o g yg r a p h s c u r r e n t l y t h er o b u s t n e s so fp l a n t e dp l a n ec u b i ct r e e ( p p c t ) i ss t r o n g e s ta m o n gt h ef o u rb a s i c g r a p h sf o rd g w ，b u ti t sd a t ar a t ei sl o w e s t f o ri m p r o v i n gd a t ar a t eo fp p c t ，an o v e l s c h e m ew h i c hc o m b i n e sp e r m u t a t i o ne n c o d i n ge n u m e r a t i o na n dp p c te n c o d i n g e n u m e r a t i o ni sp r o p o s e di nt h i st h e s i s t h en e ws c h e m em a k e su s eo ft h es t r u c t u r e a d v a n t a g e o f p p c t a n d t h e h i 曲d a t ar a t e o f p e r m u t a t i o ns u f f i c i e n t l y t h e r ea r et w om e t h o d sf o ri m p l e m e n t i n gt h en e ws c h e m ei nj a v a ，e x c h a n g i n gl e a f i i 武汉理工大学硕士学位论文 n o d e sm i x e de n c o d i n ge n u m e r a t i o na n da d d i n g p o i n t e r sm i x e d e n c o d i n g e n u m e r a t i o n t h ef o r m e re x c h a n g e st h ep o s i t i o n so fl e a fn o d e so fp p c tf o r p e r m u t a t i 0 1 3 e n c o d i n ge n u m e r a t i o n ，s o i t ss t r u c t u r ei ss i m i l a rt op p c ta n d r o b u s t n e s si ss t r o n g n l el a t t e ra d d sp o i n t e r sa m o n gt h el e a fn o d e so fp p c tt o a c h i e v et h ep u r p o s e ，a n dt h ep r o c e s so fe n c o d i n gi sf a c i l e ，m o r e o v e r ，t h ee n c o d i n g t i m ei ss h o r t k e yw o r d s ：s o f t w a r ew a t e r m a r k i n g ，d y n a m i co r a p h ，p e r m u t a t i o ne n c o d i n g e n u m e r a t i o n ，p p c te n c o d i n ge n u m e r a t i o n ，m i x e de n c o d i n g i i i 武汉理工大学硕士学位论文 第1 章引言 11 课题背景和研究的意义 计算机网络技术的飞速发展，为数字信息传播提供了极大的便利，越来越 多的知识产品以电子版的方式在网上传播。数字信号处理和网络传输技术可以 对数字媒体的原版进行无限制的任意编辑、修改、拷贝和散布，造成数字产品 的知识产权保护和信息安全的问题日益突出，并已成为数字世界的一个非常重 要和紧追的议题。因此，如何防止知识产品被非法复制及传播，是急需解决的 问题。随着计算机软件被应用到工农业生产和人们日常生活的各个领域，随之 而来的软件盗版则是日益猖獗”2 】。为了保护软件产品的知识产权，许多软件版 权保护技术被陆续开发出来，其中代码迷a l ( c o d eo b f u s c a t i o n ) 、软件水印 ( s o , w a r ew a t e r m a r k i n g ) 和篡改验证( t 细p * p r o o f i n g ) 是近几年涌现出的保护软 件版权的热点技术p j 。 以前，针对软件版权的保护主要是通过加密的方式进行。比如常见的软件 狗技术就使用在计算机并口或u s b 口上的硬件产品来对软件进行保护的。其工 作原理是程序通过调用软件狗开发套件提供的接口模块对软件狗操作，软件狗 响应该操作并通过接口模块将相应数据返回给程序，程序可以对返回值进行判 定并采取相应的动作。如果返回无效的响应，表明没有正确的软件狗，应用程 序可以自动终止运行。但是，就如同在多媒体技术领域一样，加密技术并不是 保护软件产品版权的万能钥匙，一旦加密机制被破解，则软件产品的版权保护 也就无从谈起了。 为了能够开发出和加密机制互补的软件产品保护技术，国际上开始提出并 尝试一种新的关于信息安全的概念，开发设计不同于密码学的技术，即将机密 资料信息秘密的隐藏于一般的文件中，然后再通过网络传递。由于这些机密资 料并不像加密过的文件一样是一堆乱码，而是看起来和其他非机密性的般资 料无异，因而不易被盗版者察觉，也就不会被盗版者破解。而这种特点是密码 技术所欠缺的，电是信息隐藏技术的基本思想。数字化的信息隐藏技术是一种 全新的技术，最开始的时候主要应用于数字图像、音频和视频等多媒体信息的 武汉理工大学硕士学位论文 版权保护研究，随着这种技术的不断发展，逐渐发展出了在可执行文件中隐藏 信息的技术，即针对软件产品的信息隐藏技术。可执行文件可以通过许多方式 包含许多冗余信息，如可以安排独立的一串指令，或者选择一个指令子集解决 特定的问题【1 埘。 1 2 软件保护技术的研究现状 目前，针对软件版权的攻击方法主要有三种，最普遍的攻击形式是软件盗 版，第二种形式是逆向工程( r e v e r s ee n g i n e e r i n g ) ，第三种形式是代码篡改。一 般来说，如果软件能被专利、版权、契约、贸易安全法等合法形式保护，那么 对软件的攻击可以被阻止。遗憾的是，发现破坏软件版权的行为通常很困难， 即使发现了违法行为，通过法律手段获得补偿也是非常昂贵的，甚至是不可能 的。正因为如此，用技术方法来保护软件开发商的知识产权是非常重要的。针 对上述三种攻击形式，三种相应的保护软件知识产权的技术应用而生，用代码 迷乱技术阻止逆向工稔，用软件水印技术对抗软件盗版，用篡改验证技术防范 代码篡改1 4 。j 。 1 2 1 代码迷乱技术 攻击软件知识版权的方法之一是软件逆向工程方法。软件逆向工程，就是 通过分析软件目标系统，认定系统的构件及其相互关系，并经过高层抽象或其 它形式来展现软件目标系统的过程。逆向工程师通过反汇编器或反编译器可以 反编译应用程序，然后去分析它的数据结构和控制流图。这既可以用手工完成， 也可以借助一些自动化工具。只要应用程序被反编译过来，程序就会一览无遗， 有被黑客发现安全漏洞的可能。为减小逆向工程的威胁，最有效的办法是代码 迷乱。另外两种方法是反编译和反汇编。 代码迷乱技术最初主要是用来保护软件产品的不正当再处理，它能被用来 在可执行文件中存储额外的信息。这种技术试图把一个程序p 变换成一个功能 等价的程序一，而相对p 更难以阅读和理解，对其进行逆向工程也就更困难。 在技术的角度上说，代码迷乱技术和代码优化技术( c o d eo p t i m i z a t i o n ) 的基本原 理相似。只是二者的应用方向相反，代码优化是使程序的结构更加合理，执行 效率和阅读性更高。 2 武汉理工大学硕士学位论文 代码迷乱的目的有两个：一是使程序被自动反编译变的更困难；二是即使 程序被成功反编译，也更难被阅读和理解。被代码迷乱技术处理过的程序代码， 依然遵照原来的档案格式和指令集，执行结果也与被处理前一样。只是被处理 后的程序代码变得无规则，难以成功地被反编译。同时，代码迷乱是不可逆的， 在处理的过程中一些不影响正常运行的信息将永久丢失，这些信息的丢失使程 序变得更加难以阅读和理解。但是，代码迷乱技术的特点也使其成为攻击软件 水印技术的有效手段，特别是针对静态软件水印的攻击效果十分显著。有关内 容在本文2 4 节有更详细的阐述。 另外，代码迷乱技术还可以结合动态软件水印技术抵御针对软件指纹技术 的合谋攻击。由于类似c t 算法等动态图软件水印技术能够有效的防止代码迷乱 技术对水印信息的破坏，所以可以综合利用这两种技术。在不同的产品拷贝中 嵌入不同的指纹信息，然后对每份拷贝进行全面的代码迷乱( 不能仅仅对嵌入 指纹信息的部分进行处理) ，这使通过合谋比较各拷贝中的不同之处来发现水印 和指纹信息变的毫无意义。 代码迷乱技术可以通过多种手段达到其目标，主要的途径有让标识符名字 不再具有指示其作用的能力、加密字符串和文字、插入各种欺骗指令使反编译 得到的代码不可再编译等。 代码迷乱技术的一种常见形式是以任意的名称重新命名代码中的所有标识 符。但是，这种处理不太有效，因为攻击者能从代码的上下文推断程序标识符 的意义，只是要花费更多的时间和精力。为了解决字符串明文带来的安全问题， 大多数代码迷乱技术运用了加密字符串的技术。但是由于解密操作需要一定的 代价，所以运行时访问字符串的性能肯定会有所降低。 控制流程迷乱是一种用来误导反编译器的技术，它在原始的代码中插入许 多g o t o 指令，虽然程序最终执行的指令序列仍跟原来的一样，但太多的“迂回 动作”使得分析程序实际的逻辑流程变得非常困难。表1 1 列举了代码迷乱技术 的基本方法。 1 2 2 软件水印技术 软件水印是近年来出现的一种针对软件盗版的新的保护软件版权的技术， 也是本论文研究的重点内容，有关软件水印技术的详细内容将在后续章节中详 细介绍。 武汉理工火学硕士学位论文 表1 1 代码迷乱技术的基本方法 常用的迷乱方法 反编译的代码破坏代码的难度 函数重命名 参数重命名标识符反编译的 符号迷乱 本地变量重命名 变的没有意义代码很难理解 全局变量重命名 简单的“包装”容易 不可再现的 得到无用代码较难 控制流迷乱 重构控制流图 控制流被 隐藏了实际 展开重整 的代码逻辑 较难 程序使用的数据 数据迷乱中等 存储方式被打乱 一些比较敏感 字符串加密 中等 的文本被加密 1 2 3 篡改验证技术 在很多情况下，只要程序被修改过，就需要阻止该程序的运行。例如，在 下列情况下，程序p 就不能允许运行：( 1 ) p 已被嵌入水印，构造标记的代码已 被改动；( 2 ) p 被感染了病毒；( 3 ) p 是种电子商务应用程序，其代码中安全性 比较敏感的部分被修改过。 上述的几种修改，我们称之为篡改攻击( t a m p e r i n ga r r a c k s ) 。篡改验证技术 就是用来防护对软件的篡改，保护可信任的软件能在恶意的主机上有效运行。 篡改验证技术有基于软件的和基于硬件的两种。 1 2 3 1 基于软件的篡改验证技术 基于软件的篡改验证技术仅仅依靠软件机制来防范篡改。主要的技术有： 代码迷乱、代码加密技术等。代码迷乱技术在1 2 1 节中已经阐述。 代码加密技术就是利用密码技术，防止来自恶意攻击者的窥探和访问。普 遍采用的方法是利用公钥算法实现的数字签名来防止应用软件被攻击，实现方 法如下。 4 武汉理工大学硕士学位论文 应用程序的源代码在连接编译器时，利用程序发布方的私钥对其进行加密， 即对程序进行签名。签名与程序绑定在一起，就有了对该程序是否被篡改进行 检验的依据。签名一旦成功，就具有确定性，无法伪造，也不可否认。当然， 程序发布方的公钥应该公开，以此作为程序使用者验证签名来自正确发布方的 依据。实现方案主要有两种： 方案一：在操作系统中设置验证服务程序，当应用程序装入内存运行时， 先进行签名验证，如果没有篡改，则可继续运行；否则，给出提示信息，退出 运行。这种方案只是给出警告信息不会对操作系统带来不良影响，但要改变 操作的功能，只有操作系统的设计者才可完成，使用者是无法实现的。 方案二：在程序的开始代码中加入校验代码，当应用程序装入内存执行时， 先进行签名验证，如果没有篡改，则可继续进行；否则，给出提示信息，退出 运行。这种方案，程序只有在运行校验代码后才能发觉被篡改，如果病毒先于 校验代码运行，则只能事后给出被篡改的信息。 1 2 3 2 基于硬件的篡改验证技术 基于硬件的篡改验证技术是指将软件和硬件配套使用，通过安全的硬件设 备来防范篡改。基于硬件的数字版权管理( d r m ) 方法，就是提供一个可信任的硬 件空间，存放被保护的数字内容，执行得到许可的应用，防止外部软件的攻击。 如内容加密、认证、权限实现等d r m 服务就是在这种可信任的空间中完成。 例如，现在微软( m i c r o s o i t ) 为实现可信任的计算，正在发展一种称为 “p a l l a d i u m ”的体系结构。“p a l l a d i u m ”体系结构能为d r a m 系统的实现提供一个可 信任的环境。“p a l l a d i u m ”将提供一种保护d r m 应用不被其它软件窥探和修改的 机制，从而保证只有被用户信任并被授予访问权的软件才能访问指定的数字内 容。当然，这种技术能否成功，还取决于许多其他因素。 1 2 3 3 发现篡改的三种主要方式 ( 1 ) 检查可执行程序本身，看它是否与原始的相同。为了加速测试，可采用 像m d 5 这样的信息摘要算法。 ( 2 ) 检查程序运行的最终结果的有效性。这种方法也称为程序检验或结果检 验。 ( 3 ) 加密可执行程序，由此可阻止任何人修改它，除非他能解密它。 5 武汉理工大学硕士学位论文 要注意的是，篡改有时与其它攻击方式一起发生，也可单独发生。当篡改 与其它攻击方式一起发生时，就需要采取多种保护措施了。 实际上，不同的软件保护方式所起的作用是可以相互补充的，所以，以上 所列举的保护方式可以单独使用，也可以同时使用。 1 3 本课题的主要研究内容 本课题主要探讨有关软件水印技术的相关内容，全面介绍了目前的软件版 权保护技术。重点解释了软件水印技术的基本概念、研究现状及相关算法。在 充分研究软件水印相关技术的基础上，本文针对目前软件水印的热点技术 动态图软件水印进行了详细的研究，并在现有编码方式的基础上提出了一种改 进的水印编码方法，即结合排列图枚举编码和p p c t 枚举编码的混合编码方式， 并采用两种方法对其进行了实现，同时对编码效果进行了定性分析。全文安排 如下： 第1 章，结合国内外研究的现状和发展趋势，全面介绍了本课题的研究背 景和意义，目前软件产品数字版权保护技术的发展状况和相关技术。 第2 章，全面而详细的阐释了软件水印技术的概念、分类、研究现状、针 对软件水印的攻击技术以及j a v a 程序所面临的威胁。 第3 章。对动态图软件水印算法进行了说明，详细解释了本文所应用到的 c t 算法： 第4 章，在归纳总结现有动态图软件水印算法编码方式的基础上，提出了 结合排列图枚举编码和p p c t 枚举编码的混合编码方案，给出了该编码方案的两 种实现方式及其性能分析。 第5 章，最后，对本论文所做的工作进行了总结和展望。 6 武汉理工大学硕士学位论文 第2 章软件水印技术 2 1 软件水印技术的定义 数字水印就是被永久镶嵌在其他数据( 宿主数据) 中具有可鉴别性的数字信 号或模式，而且不影响宿主数据的可用性。数字水印是信息隐藏技术的最重要 的一个分支，也是目前国际学术界研究的一个前沿热门方向。它可为计算机网 络上的多媒体数据( 产品) 的版权保护等问题提供一个潜在的有效的解决方法。 如果没有稳健性的要求，数字水印与信息隐藏从本质上来说是完全一致的。在 绝大多数情况下，希望添加的水印信息是不可察觉的或不可见的，但在某些使 用可见数字水印的特定场合，版权保护标志不要求被隐去，并且希望攻击者在 不破坏数据本身质量的情况下无法将水印去掉。发展数字水印技术的原动力是 为了提供多媒体数据的版权保护，但人们发现数字水印还具有一些其他的重要 应用，如数字文件真伪鉴别、网络的秘密通信和隐含标注等，在软件产品中通 过数字水印保护版权的技术也成为人们关注的内犁”。 软件水印技术的概念与多媒体数字水印技术相似，就是在软件产品中嵌入 作者、发行者、所有者的版权信息，也可以标识软件使用者的身份信息( 软件 指纹) ，其目的是证明版权所有者的合法身份或者确认参与盗版的用户，给利用 法律手段追究盗版者的侵权行为提供技术支持【3 1 。软件水印技术就是在程序p 中 嵌入水印结构生成目标程序p ，其中矿应该具有以下特点5 l ： ( 1 ) 在p 遭受各种代码转换攻击( 如代码优化、代码迷乱等) 之后，仍能将 矿可靠的查找和识别，即形在p 遭受攻击后是可恢复的： ( 2 ) p 和p 的静态特性无差异，即具有隐秘性； ( 3 ) 矽具有较高的数据率； ( 4 ) p 和p 在功能上应无明显差异，即矿具有便易性； ( 5 ) 具有某种数学特性可以用来证明其在p ，中的存在是人为的结果。 对于软件水印来说，水印能修改应用程序但不能修改用户可观测到的行为， 它可以修改应用程序的大小、需要的内存以及执行速度。软件水印也可以作自 检。 7 武汉理工大学硕士学位论文 2 2 软件水印技术的分类 目前的软件水印技术按照不同的分类方法，可以分为以下几种：按照功能 分类可分为防止非授权使用水印( p r e v e n t i o nw a t e r m a r k ) ，版权证明水印( a s s e r t i o n w a t e r m a r k ) ，有限许可水g p ( p e r m i s s i o nw a t e r m a r k ) 和可靠性证明水印( a f f i r m a t i o n w a t e r m a r k ) ；按照嵌入和提取方法可分为静态水印( s t a t i cw a t e r m a r k ) 和动态水印 ( d y n a m i cw a t e r m a r k ) ；按照水印加入的位置可分为代码水印( c o d ew a t e r m a r k ) 和 数据水印( d a t aw a t e r m a r k ) ：按照抗攻击强度可分为健壮水印( r o b u s tw a t e r m a r k ) 和脆弱性水e p ( f r a g i l ew a t e r m a r k ) ；按表现方式可分为可见水e p ( v i s i b l ew a t e r m a r k ) 和不可见水印( i n v i s i b l ew a t e r m a r k ) ；还可以按照提取过程中是否需要原始程序分 为盲水印( b l i n dw a t e r m a r k ) 和非盲水印( i n f o r m e dw a t e r m a r k ) 。其中大部分的分类 方式都和多媒体数字水印类似，从嵌入和提取方式上分为两种：静态水e p ( s t a t i c w a t e r m a r k ) 和动态水印( d y n a m i c w a t e r m a r k ) 6 - 7 1 2 2 1 静态软件水印 静态软件水印一般将水印信息存储在可执行程序代码中。比如在u n i x 环境 下，比较典型的是把水印信息放在安装模块部分，或者是指令代码中，或者是 调试信息的符号部分。对于j a v a 程序，水印信息也可以隐藏在类文件( 包括常 量池表、方法表、行号表) 的任何部分中【3 】f 8 】。静态水印又可以分为静态代码水 印和静态数据水印。图2 1 为静态软件水印示例图。 p c h a r v ： s w i t c hc f c a s c1 ：v ；c - 芷、1 一。 c a s e2 v = o 1 岙i pk k c a s e3 ：v ；p c a s e4 ：v = y c 踮e5 v = r ： 图2 - 1 静态软件水印( 静态数据水印静态代码水印) 8 武汉理工大学硕士学位论文 2 2 11 静态代码水印 静态代码水印的嵌入原理和多媒体数字水印的嵌入原理相似，一般是加载 在目标代码的冗余信息当中，比如调燕两条无关联关系语句的顺序可以嵌入l b i t 的信息。类似的有很多方法可以在目标代码的冗余信息中嵌入一定的水印信息。 例如，通过对含有m 个分支的选择语句进行重排列，就可以将 l o g ：( m ! ) “l o g ：( 2 4 2 4 2 4 2 4 2 4 2 4 2 4 2 4 2 4 丽( m e ) ”= o ( m l o gm ) 比特位的水印信息嵌入到目标代码 中。d a v i d s o n 描述了一种类似的代码水印，它在程序的控制流图的一个基本模 块中对软件的序列号进行编码【9 j 。 许多代码水印都经不起一些简单的攻击( 比如调整指令的顺序) 。既然交换 指令的顺序不影响原程序，那么就可以把源代码中所有满足这个条件的指令都 交换位置，这样就无法检测到先前加入的水印了。 很多代码迷乱技术能够破坏代码水印。对于d a v i d s o n 的方法，只要能够准 确地找到控制流图的基本模块。就很容易通过插入一个布尔值始终为t r u e 的 条件分支破坏这个基本模块，使水印无法检测。通过迷乱变换，所有静态结构 水印都会被破坏。另外，内嵌、循环变换代码等常见的优化技术也很容易破坏 静态代码水印。m o s l k o w i t z 1 0 提出了一种具有防篡改功能的水印算法，其基本思 想是把关键代码的一部分隐藏在软件的其他资源( 如图标、声音) 中，并且程 序会不时地从资源中提取出这段代码执行，如果资源被破坏，那么程序就会出 错。 静态代码水印更难抵抗语义保持变换攻击。出于安全考虑，j a v a 程序不能 检测自己的代码，比如语句i f ( i n s t r u c t i o n 撑1 0 0 ! 掣a d d ”) e x i t ( ) 在j a v a 语法中是不 允许的，虽然在其他语言如c 中是可以的。但是由于这种语句的特殊性，它要 检查指令，而不是可执行程序数据段中的数据，所以很容易找到这种语句在程 序中的位置。 22 1 2 静态数据水印 数据水印很容易产生和识别，是一种常见的水印。这种水印可以在程序中 的一些数据中体现出来，因而很容易被迷乱攻击破坏。比如把所有的数据分解 成一系列数据，然后散布到整个程序中，这样代表水印信息的数据也被分解， 增加了水印检测的难度；或者用一个产生这些数据的子程序来代替这些数据， 这样在程序中就找不到该数据的原型，也就无法检测水印。 9 武汉理工大学硕士学位论文 静态水印具有创建和识别都很简单的优点，但是抗语义保持攻击性能却很 差，一般的代码优化或者代码混淆工具都可以使静态水印遭受很大的破坏从而 难以识别。总之，尽管静态水印比较简单，但是由于它容易遭到破坏、鲁棒性 不好，且依赖于物理文件格式和具体的程序文件，因此很难设计出通用性好、 逻辑层次高的水印方案，因而不能得到广泛应用。 2 2 2 动态软件水印 为了提高水印的抗攻击性能，动态软件水印y n 锄i cs o f t w a r ew a t e r m a r k i n g ) 的概念被提了出来。区别于静态水印，动态水印的创建是在程序的执行过程中 进行的。动态水印技术通常被分为三类司：e a s t e re g g 水印，执行踪迹水印和数 据结构水印。其中，每种情况都需要有预先输入，然后根据输入，程序会运行 到某种状态，这些状态就代表水印。图2 2 为动态软件水印示例图。 户 s i r i n gv i f i n p u t = = i f v 【i 】t l c + ；v 2 1 = 。o + ， v 3 】d p ：v 4 】d y ； v t s l 。r ，v 【6 j = 1 ； i 涟河黟誊墓譬警 图2 - 2 动态软件水印 ( o e a s t e re g g 水印数据结构水印执行踪迹水印) 2 2 2 1e a s t e r e g g 水印 e a s t e re g g 水印无须检测，它通过一个输入产生一个输出。比如输入一个非 常规的字符串，然后屏幕上就显示出版权信息或一幅图像。比较典型的例子是 在n e t s c a p e 4 0 以上版本的浏览器地址栏中输入 a b o u t ：m o z i l l a ，将会出现一个喷 火的怪兽。另外一个类似的例子是在w i n d o w s 2 0 0 0 及以上的操作系统中，在空 1 0 答咚 武汉理工大学硕士学位论文 当接龙游戏中按下c t r l + s h i f l + f 1 0 ，点击a b o r t 键，然后双击任何一张牌，就能 赢得游戏! 但是，如果点击了r e t r y 键再双击任何一张牌，就只能认输了! e a s t e r e g g 水印的主要问题是水印在程序中的位置容易找到。一旦输a j e 确 信息，用s o f f i c e 这样的标准调试软件就可以跟踪程序执行情况，进而找到水印 的位置，进而被完全删除或更改，所以这种水印不是很安全，抗攻击性能较差。 2 2 2 2 执行踪迹水印 执行踪迹水印也需要一个提取密钥，但并不会输出水印信息，而是运行程 序时通过监视指令或地址执行踪迹的统计信息来提取水印。 2 2 2 3 数据结构水印 数据结构水印的机制是当对程序输入特定的提取密钥的时候，水印信息会 被隐藏在堆、栈或者全局变量域等程序状态中，或者构造特殊的数据结构，比 如图、树或链表，用数据结构的拓扑属性表示特殊的水印信息，然后通过检测 程序变量的当前值来进行水印提取。通常情况下，这种数据结构水印信息的提 取都要通过与目标程序相关联的特定的水印提取程序的运行来完成。或者将目 标程序在调试器中运行。 数据结构水印具有以下一些良好的特性： ( 1 ) 与e a s t e re g g 水印相比，由于在输入提取密钥时，数据结构水印并不 会有特别的输出结果，所以不会让攻击者很轻易的就发现水印信息； ( 2 ) 水印提取程序并不需要跟应用程序捆绑在一起( 只有版权所有者提取 水印的时候才需要) ，所以在目标程序中只有水印位置很少的信息； ( 3 ) 相比较于e a s t e re g g 水印和执行踪迹水印，数据结构水印抵抗代码迷 乱技术攻击的能力相对更强。 但是，数据结构水印在抵抗代码迷乱攻击时也不完全令人满意。有几种迷 乱变换能够有效的改变程序的数据结构从而使得水印的识别无从谈起。 2 3 软件水印技术的研究现状 软件水印是密码学、软件工程、算法设计、图论、程序设计等学科的交叉 研究领域。目前国外主要是美国的a r i z o n a 大学、w i s c o n s i n - m a d i s o n 大学和 武汉理工大学硕士学位论文 p u r d u e 大学、新西兰的a u c k l a n d 大学、日本o s a k a 大学在做这方面的研究工 作，并取得了一定的成果，美国在软件水印方面就已经申请了至少4 项专利f 9 。 在国内，相关的研究工作刚刚起步，还处在探索阶段，北京邮电大学信息安全 中心、浙江大学等院校的研究人员开展了相关的工作。 1 9 9 6 年，d a v i d s o n 和m y h r v o l d 发表了基本模块调整算法1 9 ，该算法的基本 思想类似于文本水印算法，即将原始程序中的各基本模块进行重新排列，嵌入 水印信息，例如在面向过程的程序设计中调整各函数的排列顺序即可达到此目 的，但是显然该算法的鲁棒性比较差。 s t e m 等人提出了基于扩频思想的软件水印方梨1 3 】。其基本思想来源于将水 印信息嵌入视频或音频频域因子的多媒体数字水印方案，利用指令序列出现频 率的向量提取范式，将扩频思想应用于软件水印领域，构成一种私有软件水印。 该方案在理论上具有很强的健壮性，但实现起来很困难，因为软件代码所能经 受的操作比视频和音频信号要有限的多。gh a e h e z 后来指出【l4 1 ，他们在以j a v a 字节码为目标实现该方案时，遇到了无法克服的困难，最终在原先方案的基础 上作了后退。他们所做的最主要的修改是：不再随机产生水印然后修改代码进 行嵌入，而是先对代码做随机修改，然后把所产生的修改当成水印。这样的修 改显然损害了原先方案的强度。此外，作为私有软件水印方案，在检测水印时 除了要有含水印的水印程序之外，还必须提供不含水印的原始程序作比较。而 且该方案也不能抵御解释攻击。吴建军和高济在此基础上提出了基于指令统计 分布的软件方案【1 孓1 6 1 。该方案是一种盲提取软件水印方案，水印信号分散在整 个代码的指令统计分布上。在程序的指令集中随机抽取两个不相交的基数相等 的子集。对特定子集的选取就是要嵌入的水印。改变程序使对应于某个子集的 所有指令的出现次数都增加一个常数。检测时，分别计算相应两个子集指令出 现次数的平均值，如果两个均值之差大于阙值，则认为包含水印。s h k q 算法【 】 也是基于频域的软件水印算法之一。 m o n d e n 【1 8 1 和a r b o i t t l 9 1 等人提出了一种针对j a v a 程序的软件水印方案，即通 过在j a v a 程序中加入从不执行的d u m m y 类方法来编辑版权拥有者的身份信息， 并通过所谓的“o p a q u e 谓词”( 让攻击者很难判断真假的复杂表达式) 用来保护 那些从不执行的对d m m n y 方法调用的代码以免很轻易的被识别出是无用代码 而被清除。n a g r a 和1 1 1 0 m b o r s o n 口0 】提出了在多线程程序中基于线程固有的随机 特性的软件水印算法。 1 2 武汉理工大学硕士学位论文 e c o u s o t 和r c o u s o t 提出了抽象解释算法【2 i j ，该算法将水印信息嵌入到指 定的局部整型变量的分配值当中，这些值可以通过特定的抽象解释框架来分析 获得，只要目标程序的部分代码存在，水印信息就能够被检测出来。 c o l l b e r g 等人提出了将水印信息嵌入执行期的分支结构中的动态路径算法 f 2 2 1 。该算法主要是基于分支结构在程序中的大量重用性而导致其很难被全部分 析的特性。 y e n k a t e s a n ，v a z i r a n i 和s i n h a 提出了首个基于图论的软件水印算法【2 ，叫 做w s 算法，该算法是一个静态软件水印算法。c o l l b e r g 和t h o m b o r s o n 提出了 第一个动态图软件水印算法c t 算、法【引，该算法的核心思想是将水印信息嵌入到 动态的拓扑图结构中，由于指针结构的关联性导致通过自动软件分析代码变得 很困难，从而使保持语义攻击( 对拓扑图进行变换) 难以实现。t h o m b o r s o n 等 人发展了一种c t 算法的变种常量编码算法【2 4 1 。该算法将一些程序中的数字 型或非数字型的常量转换成拓扑图结构，嵌入到程序中。 2 4 针对现有软件水印技术的攻击方法 任何信息隐藏系统的安全强度都与隐藏信息量、隐蔽性和可靠性密切相关， 而且要在这三个参量之间进行折衷 3 1 。比如，被隐藏信息量大必然导致隐蔽性和 可靠性的降低。为了评价水印算法的好坏，我们必须清楚水印可能遇到哪些攻 击。一般来说，没有一种信息隐藏系统可以抵抗所有类型的攻击。目前的所有 多媒体水印技术都存在着缺陷，要达到保护大量隐藏信息抵抗所有试图去掉这 些信息的目的是不可能的【2 5 1 。同样的问题也困扰着软件水印技术，只要有足够 的时间，个熟练的软件工程师总能够对任何应用软件进行逆向工程。逆向工 程师通过反汇编器或反编译器可以反编译应用程序，然后可以分析它的数据结 构和控制流图。这可以手工来做，也可以借助一些逆向工具。这个问题其实很 早就出现了，只是一直没有得到软件开发商的重视，因为多数程序都非常大， 而且被统一封装起来，要想对它进行逆向工程非常困难，几乎是不可能的。但 是现在软件正在以一种越来越容易被反编译和逆向工程的方式发行。比如现在 的j a v a 字节码和中性分布格式体系。 1 3 武汉理工夫学硕士学位论文 2 4 1 攻击方法的种类 目前，针对软件水印技术的攻击主要有两种类型，一种是恶意客户端攻击， 另一种是恶意主机攻击【4 】o 如果是客户端机对安全主机的攻击，主机环境可以通 过限制客户端的访问权限来控制其对软件的攻击，所以这种攻击的威胁相对较 小。但是由于恶意主机可以拥有检查和修改程序代码的全部权限，所以来自恶 意主机攻击的威胁性远大于来自恶意客户端的攻击。因此在讨论有关针对软件 水印的攻击技术时主要考虑的就是来自恶意主机的攻击。 对于我们感兴趣的作者身份水印和指纹水印来说，必须满足健壮性的要求。 不管是正常的处理或者是攻击，都不能影响到水印的检测。一般情况下只考虑 这样的攻击：能够影响水印的检测的同时不使软件质量下降过多。否则尽管水 印被消除了，但软件也不再能使用。通常关于健壮性并没有一个清楚的定义， 因此也无法证明水印的健壮性。到目前为止，健壮性仅仅定义为对系列对己 知攻击的抵抗力。 目前针对软件水印的恶意主机攻击主要有剪裁攻击( s u b t r a c t i v ea t t a c k ) 、变 形攻击( d i s t o r t i v ea t t a c k ) 和附加攻击( a d d i t i v ea t t a c k ) 。另外，针对标识软件使 用者的