（计算机软件与理论专业论文）软件水印及其防篡改技术研究与实践.pdf

摘要 传统的软件保护大多依赖于加密技术，软件水印是一种新型的软件保护方式。 该技术在软件程序中嵌入某些特定的秘密信息，在必要的时候，这些秘密信息可 以被提取出来证明软件所有者的版权。 根据水印被加载的时刻，可以将软件水印分为静态水印和动态水印。静态水 印存储在可执行程序代码中，动态水印则保存在程序的执行状态中。静态水印的 生成和检测比较简单，但是对于水印攻击的抵抗性能较差，一般仅用于研究。动 态水印更有可能用于实际应用。 动态阻水印( d g w ) 是一种较新的动态软件水印技术，这种技术在程序运行时 动态生成一个图结构，用这个图的拓扑来表示一个水印数字。因为分析动态数据 的困难性，这种动态水印对水印攻击的抵抗能力较强。 本文的主要工作是在研究现有软件水印理论的基础上，提出一种新的防篡改 的动态图水印方案，并实现一个原型系统d - j s m 。该方案可以分为水印嵌入和水印 提取两大阶段。水印的嵌入首先将两个大素数的乘积编码进一个平面环路树p p c t 的数据结构中，将该结构作为水印嵌入软件程序。然后提取候选程序中的关键常 量，将其转换为一组小整数，并在水印树结构中寻找这些常量整数对应的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 o f t w a r ew a t e r m a r ke m b e d ss o m es p e c i a ls e c r e tm e s s a g e si ns o f t w a r ep r o g r a m ， a n dt h e s em e s s a g e sa r ee x t r a c t i v ew h e ni ti sn e c e s s a r yt oi m p r o v ea u t h o r i t yo w n e r s h i p s o f t w a r ew a t e r m a r kc a nb ed i v i d e di n t os m i l es o f t w a r ew a t e r m a r ka n dd y n a m i c s o f t w a r ew a t e r m a r k d y n a m i cg r a p h i cw a t e r m a r ki sar e l a t i v e l yn e w d y n a m i cs o f t w a r e w a t e r m a r kt e c h n i q u e 。i tu s e sag r a p h i ct o p o l o g yp r o d u c e di ne x e c u t i v et i m ea st h e w a t e r m a r kn u m b e r d y n a m i cd a t aa n a l y s e sa r ed i f f i c u l t ，s ot h i sk i n do fw a t e r m a r ki s m o r er o b u s tt ow a t e r m a r ka r t a c k s t h i sp a p e r # y e san e wt a m p e r - p r o o f i n gd y n a m i c g r a p h i cw a t e r m a r ks c h e m eb a s e o n e x i s t i n gs o f t w a r ew a t e r m a r kt h e o r i e s ，a n d r e a l i z e sa p r o t o t y p es y s t e mn a m e d d j s m d j s mu s e st h er e s u l to ft w o b i gp r i m e s a sw a t e r m a r k i te n c o d e st h er e s u l ti na p l a n t e d p l a n e c u b i ct r e es t r u c t u r e t h e ni tt r a n s f o r m st h ec o n s t a n ti nt h ec a n d i d a t e p r o g r a mi n t o s m a l li n t e g e r s ，w h o s ep i c ts u b s t r u c t u r e sc a nb ef o u n di nt h ew a t e r m a r kt r e e ，a n dg i v e s t h er e f e r e n c ei n f o r m a t i o no ft h e s es u b s t r u c t u r e si no r d e rt ol o c a t et h e m t h e nw e m o d i f y t h ec a n d i d a t e p r o g r a m s o n l e c o d e ，r e p l a c i n g t h ec o n s t a n t si nc a n d i d a t e p r o g r a m w i t l lc o n s t a n t d e c o d i n gf u n c t i o n s w h i c ha r eb a s eo nt h er e f e r e n c ei n f o r m a t i o n t h er e c o g n i z i n gp h a s eo ft h i ss c h e m ec a nu s ed e b u g g i n gs o f t w a r e i tc a nw a t c ht h e e x e c u t i o ns t a t e m e n to fs o f t w a r ep r o g r a ma n dd e t e c tt h ea p p e a r a n c eo fp l a n t e dp l a n e c u b i ct r e e s t r u c t u r e s ，s ot h eo w n e ro fs o f t w a r ec a nr e t r i e v et h es o f t w a r ew a t e r m a r k n u m b e r t h ei n n o v a t i o no ft h i ss c h e m ei st h a ti tc a nt a m p e r - p r o o fs o f t w a r ew a t e r m a r k o n c ea na t t a c k e rm o d i f i e st h ew a t e r m a r k t r e e ，t h er e f e r e n c ei n f o r m a t i o nt or e t r i e v ek e y c o n s t a n t sw i l lb e c o m ei n v a l i d ，a n dt h ep r o g r a mw i l lf a l lt or u n a c c o r d i n gt oe x p e r i e n c er e s u l t ，t h i ss c h e m ei sf e a s i b l e ，b u ti ts t i l ln e e d sl o t so f i m p r o v e m e n t b e f o r ei tc a nb eu s e df o rp r a c t i c e k e y w o r d s ：s o f t w a r ew a t e r m a r k ，d g w , p p c t , c o n s t a n te n c o d i n g ，t a m p e r - p r o o f 第一章绪论 1 1 本课题的研究目的及意义 随着计算机网络技术的迅速发展，信息交换与传递变得越来越快捷，但同时 也给软件保护问题带来了巨大的隐患。从网络下载软件是如此简单，以至看起来 是在鼓励人们不经认证使用软件。c u r t i s 将软件盗版定义为非法地传播、复制、 使用和出售软件产品，而这些产品是被版权法保护或者是拥有使用许可的“1 。根据 商务软件联盟( b s a ) 在2 0 0 4 年7 月给出的调查结果表明“。，2 0 0 3 年软件盗版造成的 损失在全球范围内已经达到2 9 0 亿美元。软件产业继续受到挑战，应该如何保护软 件产品和世界范围内的经济呢? 软件保护技术是国际普遍关心的研究课题，具有商业利益驱动，得到了工业 界的大力支持，但是到目前为止仍无突破性进展。这是因为软件保护问题缺乏统 一性，基于现有的软件实现机制，完全意义上的软件保护目标几乎是不可能达到 的。但是，随着软件复杂程度的增加和知识产权法规的健全，保护软件的分发和 运行安全是可以达到的。 软件水印就是在这种情况下产生的。目前在软件版权保护方面，人们主要通 过加密的方式进行，比如软件狗，v b o x ，s o f t s e n t r y ，s e c u r o m f 阳s a f e d i s c 等”。近 几年出现的软件水印则是一种全新的软件保护措施，可以用来标识作者、发行者、 所有者、使用者等，并携带有版权保护信息和身份认证信息，可以鉴别出非法复 制和盗用的软件产品。传统的加密技术一旦被攻破，软件产品的所有信息就完全 暴露在敌手面前；而软件水印通过在软件中隐秘地加入秘密信息，在必要的时候 提取出来以证明版权。软件水印本身并不能防止盗版，但可以在必要时候提供控 诉的证据。 美国在软件水印研究方面的成果最为显著，已经具备多项专利“。7 ，其次主要 是新西兰的a u c k l a n d 大学和日本的o s a k a 大学在做这方面的研究。国内关于该技术 广东工业大学工学硕士学位论文 的研究仍不多见8 m 3 ，这与多媒体水印研究的热潮形成鲜明的对比。 1 2j a v a 软件保护的威胁 本文将主要讨论对使用j a v a 语言开发的软件程序的保护。这是由于j a v a 语 言现今的地位和它的一些特性决定的。j a v a 程序运行时，它的源代码首先被编译 成为字节码的格式，然后储存在一个类( c l a s s ) 文件中。这个类文件并不包括在 某一特定的平台或者硬件上进行操作的信息。相应的，每个平台都有一个对应的 与j a v a 开发包无关的j a v a 虚拟机j w ，来识别这些字节码格式，然后将这些指令 翻译为平台相关的代码。因此，j a v a 语言具备一次编译，多处运行的能力，这使 其成为服务提供商和系统集成商用以支持多种操作系统和硬件平台的首选解决方 案。但这同时也带来了安全隐患。为了允许平台无关和保证平台的安全，源代码 中的许多信息都必须被保存到字节码格式中，例如用于对象链接的类型信息。这 种类文件的格式使得对j a v a 程序的逆向工程和静态分析比对其它的许多可执行格 式的文件进行操作要容易的多。反编译字节码很容易，并且有很多工具软件可以 完成这一功能，如d jj a v ad e c o m p i l e t 等，从而，攻击者可以从类文件反编译得 到源代码。如果他们理解了每一部分的工作流和功能，就可以插入或者移除一些 重要的信息，比如序列号有效性检查等。他们甚至有可能识别出那些用来给程序 加水印的代码。如果他们9 够可靠地识别出这些代码，攻击者通常会使这些代码 失效而不影响源程序的正确性。 因此，j a f a 语言的安全问题正受到越来越多的关注。这也是本文选择j a v a 语 言作为保护的目标语言的原因。 1 3 本文的目的及相关工作 本文的目的在于研究和分析现有的软件水印理论，在已有的理论基础上提出 一个改进的动态图水印方案并实现一个原型系统。该方案中使用防篡改技术对水 印结构进行保护。给软件加水印包括水印嵌入和水印识别两大阶段，本文的侧重 点在于水印嵌入阶段以及水印结构的防篡改。 2 第一章绪论 1 4 本文的组织 本文共分为四章。第一章对论文的相关背景做了简要介绍，第二章详细介绍 软件水印技术。第三章分析一个软件水印系统所应该包括的功能，并对本文提出 的防篡改的动态图水印方案进行了大致描述。第四章介绍基于该方案的原型系统 的具体实现过程并给出部分实验结果。最后给出结论。 3 广东工业大学工学硕士学位论文 第二章软件水印技术概述 加水印可以定义为在明文中嵌入秘密信息的操作行为“。在本文中，只对明文 信息是软件程序的形式进行讨论。本章将对软件水印技术做一些概要介绍，包括 软件水印的攻击和防护的背景知识。本章将重点讨论动态图水印以及p p c t 结构。 动态图水印是一种较新的软件水印技术，在参考文献 11 - 1 4 中讨论了一些动态图 水印的方案。本文将在后面2 2 节中做具体介绍。 2 1 软件水印的定义及其分类 软件水印有多种分类标准“。可以按照功能来分类，也可以按照水印加载的 时刻来分类。按照软件水印的功能可以将其分为下面几种： 所有者水印：这种水印用来标识作者的身份。标识单一作者身份的水印，称 为单拥有者水印，这种水印需要在一定范围内唯一；标识多个拥有者的水印称为 复拥有水印。 指纹水印：这种水印必须包含一个在一定范围内独一无二的身份信息，用来 标识购买者( 或称用户) 的身份。 验证水印：用来验证软件的所有信息，包括源代码、程序可执行文件、程序 安装文件和程序资源文件( 图标、图像或其它多媒体信息) 仍然与软件生成时的 信息一样，没有经过篡改。 许可证水印：许可证水印的作用主要用于表明软件规定的使用方式，以配合 验证软件是否被盗用或误用。 针对各种不同的应用，上述各种水印在鲁棒性和可见性方面也有不同的要求。 拥有者水印应该是具有较强鲁棒性的不可见水印；指纹水印应是具有较强鲁棒性 的不可见水印；验证水印应该是脆弱的可见水印；许可证水印应该是脆弱的不可 见水印。 按照水印被加载的时刻分类，可以将软件水印分为静态水印和动态水印“”。下 面主要按照这个分类标准来讨论。 4 第二章软件水印技术概述 2 1 1 静态软件水印 个静态软件水印以某种特定格式储存在程序代码中，并且在程序执行的过 程中不发生改变。根据水印信息的表示，有两种类型的静态水印：静态数据水印 和静态代码水印。一个静态数据水印以程序数据的方式储存水印信息，可以储存 在程序的任何地方，比如注释或者变量中。 一个静态代码水印可以通过选择一个特定的指令序列来表示，以防止有不止 一个指令序列有相同的效果。例如，在一个j a v a 程序中，s w i t c h 转换语句中c a s e 语句的一个特定序列可以被用来表示一个水印数字。i b m 也曾宣称他们的寄存器出 栈和入栈的顺序表示了某些特定的信息。g i n g e rm y l e s 和c h r i s t i a nc o ll b e r g 在 1 6 中对使用寄存器分配构造的软件水印的实现、分析和攻击做了论述。一个静 态的代码水印还可以被储存在“死代码”( 永远不会被执行到的代码) 中；在个死 代码区域内的任何指令序列都可能有相同的效果。 关于静态软件水印问题的更多的讨论可以在 1 7 和 1 8 中找到。 2 1 2 动态软件水印 一个动态软件水印在程序执行时被构造，有可能是被某个特定的输入序列激 发。水印可以通过分析水印程序运行时构造的数据结构来提取，也可以执行追踪 程序来提取。 有三种类型的动态软件水印：e a s t e re g g 水印、执行跟踪水印和动态数据结 构水印“。 e a s t e re g g 水印：在输入一个特殊的输入序列后，这些动态水印将在用户界 面上显示出来。水印有可能是版权信息或者料想不到的文本或图像。在网络上可 以找到很多有关e a s t e re g g 水印的资源和例子。最常用的一个例子就是在n e t s c a p e 4 o 中输入下面的u r l ：“a b o u t ：m o z i l l a ”，将会出现一个喷火的怪物。e a s t e re g g 水印的主要问题在于它们容易定位。因此，除非e a s t e re g g 水印真的是设计精妙 的( 在这种情况下攻击者将很难判定它们是构造了一个水印，而不是b u g 的结果或 者随机的程序选择) ，否则水印经常一被发现就被清除了。一旦正确的输入序列被 发现，标准的调试技术将允许我们跟踪可执行代码中的水印的位置，从而可以将 广东工业大学工学硕士学位论文 其移去或者使其失效。 执行跟踪水印：当这种类型的水印程序运行时，水印信息将在指令中表示出来， 或者通过程序执行序列中与数据相关的痕迹来表示。有可能需要一个特殊的输入 序列。这种水印可以通过分析地址或者程序的操作序列来提取。 8 中将其称为执 行过程水印。 数据结构水印：当这种类型的水印程序在一个特殊的输入序列下运行时，水印 信息将保留在程序的堆或栈中。这些水印可以通过分析程序运行时的内存状态来 提取。下面一节将要介绍的动态图水印( d g w ) 就属于这种类型。 2 2 动态图水印 c 0 1 b e r g 和t h o m b o r s o n 在他们的论文 1 9 中系统地讨论了水印技术及其保 护。他们指出当前的水印技术有可能被典型的迷乱转换成功地攻击。由这个观点 出发，他们给出了一种新的水印技术，称为动态图水印d g w 。d g w 用一个图的拓扑 结构来表示水印，这个拓扑结构只在程序运行时创建，由一个特殊的输入序列触 发。与静态水印相比，他们的d g 臌术更不容易受代码最优化和代码迷乱等水印攻 击的影响。 2 2 1 添加动态图水印的过程 在下面关予水印技术的讨论中。本文用“候选程序”指需要添加水印的软件程 序。“水印程序”指添加了水印后的候选程序。“嵌入”是指在候选程序中嵌入 一个水印或水印图结构的过程；“解码”指将一个图结构转化为一个整数的过程。 “编码”指将整数转化为图结构的过程。添加动态图水印的过程可以描述为下面 几个步骤： ( 1 ) 选择一个水印数字。 ( 2 ) 将这个水印数字用一个图结构来表示。 ( 3 ) 构造一段水印代码，来在运行时产生这个图结构。 ( 4 ) 在软件程序中嵌入这段代码，使得添加水印后的程序只有在接受一个特殊的输 入序列时才构造这个水印。 第二章软件水印技术概述 上面( 2 ) 到( 4 ) 的步骤在图2 1 中被举例说明。 在图2 1 ( a ) 中的水印过程表明个水印数字可以通过某些特定的枚举方法转 化为一个图结构g ( 上面列举的步骤( 2 ) ) 。 图2 - 1 ( b ) 构造了一个产生水印结构g 的源代码( 上面列举的步骤( 3 ) ) 。当这段 源代码被执行时，将产生水印图g 。 图2 - 1 ( c ) 将源代码插入到候选程序中，图2 - 1 ( d ) 确认只有在一个特殊输入序 列被输入时，水印才会被构造( 上面列举的步骤( 4 ) ) 。为了提取水印，需要输入这 个特殊的输入序列来运行水印程序，然后检查堆寄存器中的对象。 图2 1 ( a ) 将水印数字1 1 转化为水印图g f i g u r e2 - 1 ( a ) t r a n s f o r man u m b e r t oa g r a p h 因 图2 - 1 ( b ) 构造图g 的代码 f i g u r e2 - l ( b ) c o d e t oc o n s t r u c tg r a p hg 图2 - 1 ( c ) 将代码插入到候选程序中 f i g u r e2 - 1 ( c ) i n s e r tt h ec o d e t oc a n d i d a t e p r o g r a m 7 广东工业大学工学硕士学位论文 图2 - 1 ( d ) 一个特殊序列激发水印的构造 f i g u r e2 - 1 ( d ) w a ：l e r m a z ki sb u i l to n l yw i t has p e c i a li n p u t 图2 1 动态水印嵌入过程 f i g u r e2 - 1d y n a m i c w a t e r m a r k e m b e d d i n g c o l l b e r g 和t h o m b o r s o n 在这篇文章中也提到在基本的d g w 方法上的两个改进。 一个是将i ) g w 结构分解成为许多单独构造的片。在一个特定的输入序列全部被输入 后，所有这些分解的1 ) g w 结构片已经全部被建造，然后合并在一起。另一个改进是 在d g w 的方案中结合防篡改技术。为了简单起见，图2 1 中没有体现这种想法。水 印保护技术的细节将在第2 4 节中讨论。 与静态水印相比。动态图水印的最大优点就是一个动态的水印图结构中包含 很多指针，而在运行肘分析指针是很困难的。同时，因为一个d c w z f ( 印是动态构造 的，要分析这个水印结构必须将运行时的信息收集起来。与分析简单的语言代码 相比，攻击者需要花费更多的代价来分析栈和堆寄存器。所有上面的这些特性使 得i ) g w 水印只是通过它构造的方法，就能获得一定程度的保护。 2 2 2d 黼嵌入的枚举方法 在上一节中指出，水印嵌入过程的第( 2 ) 步要找出与一个需要嵌入的水印数字 相对应的图。这一类型的问题已经在组合数学中被广泛地研究过。通常的解决方 法是首先对一个图结构的集合按照某个特定的枚举方法进行索引，然后用这个索 引数字来表示水印。因此，我们假设水印使用一个整数来表示。通常，这个索引 数字与图之间的转换是由编码解码器来实现的。一个编码解码器应该包含编码函 数e 和解码函数d 。e 函数将一个数字映射为某种结构的图，更确切地说，是映射 8 第二章软件水印技术概述 为这种图的数据结构的表示。d 的作用相反，将这种结构的图映射为一个数字。 显然，有很多种枚举方法和很多种图结构可以用于水印的嵌入。在 1 9 中，讨 论了四种图的枚举编码方法。它们是：( 1 ) p p c t ( p l a n t e dp l a n ec u b i ct r e e ) 编码， ( 2 ) 基数一k 编码，( 3 ) 父指针树编码，和( 4 ) 排列编码。下面将简要叙述这些枚举方法 是如何工作的。本文将强调p p c t 结构的编码，因为在本文提出的水印方案中使用 这种编码方式。 ( 1 ) p p c t 编码 首先，需要定义一个p p c t 的类。根据g o u l d e n 给出的定义，一个p p c t 有下面的 这些特征“： ( a ) 有一个根节点，这个节点是不同于其它节点的单独顶点。 ( b ) 根的度为1 。 ( c ) 树是平面的。 ( d ) 每一个顶点的度为1 或者3 。 图2 2 一个p p c t 的例子 f i g u r e2 - 2ap p c te x a m p e 图2 2 中显示的图具有所有的这些特征。它的根节点被画成黑色的。树的所 有内在的节点是三价的，并且没有相交的边。p p c t 结构是用于动态水印嵌入的。 被c o l l b e r g 和t h o m b o r s o n 选中来表示水印图的p p c t ，对上面的特性进行了扩展。 树中的每个节点都有左右两个指针。上面提到的单独的根被称为生成节点 ( o r i g i n ) ，生成节点的右指针指向的节点被称为根节点( r o o t ) 。叶节点的右 指针指向自己，左指针指向它左边的下一个叶节点。最左叶节点的左指针指向生 成节点。生成节点的左指针指向最右叶节点，右指针指向根节点。图2 - 3 中给出 了一个扩展p p c t 的例子。 广东工业大学工学硕士学位论文 图2 - 3 一个扩展的p p c t f i g u r e 2 - 3a n e x p a n d e d p p c t 扩展的p p c t 有一些有用的特征。例如，一个扩展的p p c t 是一个二叉树，并且 树结构中的所有指针都不为空；生成节点指向二叉树结构的根节点；所有的叶节 点通过左指针被连接到一起，并且最左节点的左指针指向生成节点，生成节点的 左指针指向最右叶节点。这些特征使得p p c t 结构容易定位。例如，从该结构中任 意一个节点可以找出生成节点。根据c a t a l a n 数论，一个具有n 个叶节点( 2 n 个节点) 的p p c t ，可以表示下面集合中的任意整数： 0 ，1 2 i c ；2 ：一1 1 。 l n j 图2 4 给出了具有4 个时节点的所有p p c t 的枚举。 久冬厶度公 h 如x = o i n d e x = 1 1 a d e = 2h 如z = 3k d c x = 4 图2 4 具有4 个叶节点的p p c t f i g u r e2 - 4a l lp p c t sw i t h4l e a v e s ( 2 ) 基数k 编码 基数k 编码基于一个具有k 一1 个节点的循环链表，这个循环链表有一个唯一的 首节点。索引数字通过下面的函数来决定： i n d e x = a i 七o + a 2 x k l + + 口j x k - 1 + + a t _ 1 七一2( 公式2 1 ) 】0 第二章软件水印技术概述 循环链表中的每个节点包含两个指针，左指针和右指针。a 。的值是通过节点 的左指针来决定的，根据下面的规则： n = 0 ，如果左指针为空； a ；= 1 ，如果左指针指向自己； a = 2 ，如果左指针指向下个节点； - - ： a ；= k 一1 ，如果左指针指向循环链表中的前一个节点。 一个长度为的链表可以编码从0 到+ 1 ) ”一l 范围内的任何整数。 例如，下面图2 - 5 表示了一个基数k 编码的例子，这里k = 6 。实际的k 可以根 据需要选择。 6 1 x7 3 = 3 6 + 2 6 + 3 6 2 + 4 6 + 1 6 。 图2 - 5r a d i x - 6 编码 f i g u r e2 - 5r a d i x 一6e n c o d i n g ( 3 ) 父指针树编码： 另外一个通过索引图表示水印的方法是使用父指针树。在一棵父指针树中， 每一个节点都有一个指向它的父节点的指针。可以指定某种规则来比较树的大小。 比如指定“最大子树优先”的比较规则，则在具有1 1 个节点的图中，长度为旷1 的 路径对应最小索引。图2 6 给出了具有4 个节点的所有的父指针树。 l o 卜 n d e x = or n d e x = lh d e x = 2i n d e x = 3 图2 6 具有4 个节点的父指针树列举 f i g u r e2 - 6p a r e n t - p o i n t e rt r e ee n u m e r a t i o nw i t h4n o d e s ( 4 ) 排列编码：排列编码用一个数字( o ，1 ，一1 ) 的排列来表示一个水印。 例如，水印数字2 9 可以用数字( 1 ，2 ，3 ，4 ，5 ) 的排列( 4 ，5 ，3 ，l ，2 ) 来表示。一个循环链表可 。十o千66 广东工业大学工学硕士学位论文 以被用做嵌入的数据结构。图2 7 用一个循环链表表示数字2 9 ，将排列中的第一个 数字4 通过从链表的第一个节点到第4 个节点的指针来表示，第二个数字5 通过从第 二个节点到第五个节点的指针来表示。依次类推。 图2 7 使用一个循环链表来排列编码数字2 9 f i g u r e2 - 7a c i r c u l a rl i n k e dl i s tf o r p e r m u t a t i o ne n c o d i n gn u m b e r2 9 2 3 软件水印的攻击类型 对软件程序的攻击可以分为两类：恶意的客户程序攻击和恶意的宿主攻击”。 在恶意的客户程序攻击一个良性的软件宿主时，客户程序的权限可以被软件宿主 限制。因此，一个恶意的客户程序攻击不如一个恶意的软件宿主攻击时的威胁大。 在后者情形中，软件宿主有全部的权限来检查和修改客户代码。因为水印程序被 嵌入在客户程序中，软件水印的攻击属于恶意软件宿主攻击的类别。 2 3 1 对软件水印的攻击概述 由于软件宿主的权限高，许多技术可以被恶意的软件宿主用来进行水印攻击。 可以使用的方法包括逆向工程，源代码字节码分析，程序输出分析，执行跟踪分 析，堆栈分析等等。静态数据水印和代码水印对于使用迷乱技术的攻击是高度敏 感的。2 3 1 。这是因为迷乱技术将会改变程序中静态数据的表示。在那些指令的顺序 不关键的地方，它还可能改变一些指令的顺序。迷乱技术还可能用等价的指令序 列来替代原来的指令序列。例如，迷乱有可能将字符串转换为子串，或者改变 s w i t c h 语句中c a s e 语句的顺序。如果水印信息依赖于这些字符串或者c a s e 语句的 釜三塞鳖丝查! ! 茎查竺鎏 顺序，经过这种变换后，水印将不再能够被识别。 关于迷乱( 有文献也称为混乱) ，可以定义如下“： 已知一系列的迷乱转换丁= 亿，l ，l 和一个程序p ，p 由源代码对象( 类、 r，、1 方法、声明等) 墨。，s ：，足 组成；要找到一个新的程序p = 0 量= 王8 j l 一0 ，使 得： ( 1 ) p 与p 有相同的可观察到的行为，也即转换需要保持语义； ( 2 ) p 的隐秘性达到最大，也就是说，要理解和逆向工程p 将比对p 进行同样的工 作花费远远多的时间。 ( 3 ) 每个转换正( s ，) 的可靠性最大，也即要构造一个自动的工具来逆向转换的过程 或者执行这样的一个工具将花费大量的时间。 ( 4 ) 每个转换互( s ，) 的隐秘性达到最大，也即s ，。的统计学特性要与s ，类似。 ( 5 ) p 的代价( 转换时的执行时间空间消耗) 最小。 一些动态水印也可能被迷乱技术攻击。执行跟踪水印对于迷乱技术是相当敏 感的。e a s t e re g g 水印则是不受迷乱攻击影响的。动态数据结构水印对于某些高 级的数据迷乱攻击是敏感的。比如，当那些表示一个d g w 的节点被“分裂”或者“合 并”时。更多的关于迷乱攻击的分析可参见 2 2 。 除了迷乱之外，还有很多其它的攻击水印的方法。根据c o l l b e r g 和t h o m b o r s o n 在 1 7 中的论述，攻击可以分为三类，如在图2 - 9 中所示，下面做简要描述。 ( 1 ) 添加攻击：攻击者插入他自己的水印。这种尝试的结果是覆盖了原来的 水印，或者至少使得很难判断原来的水印是否是在攻击者的水印之前加入的。 ( 2 ) 裁减攻击：攻击者试图定位和除去一个水印。而不影响软件程序的可用性。 ( 3 ) 扭曲攻击：攻击者试图修改水印而不破坏软件程序的可用性。这种攻击的 结果是水印不再能够识别，但是软件对于攻击者仍然是有价值的。 许多工具对于攻击者都是可得的。j o b e 。“可以改变程序的标识符。 k l a s s m a s t e r 。”不但能转换名字和字符串，而且还能提供流程来改变大多数的选择 语句( 例如，i f e l s e ) 和循环语句( 例如w h i l e 和f o r ) 。j a d ”能够反编译j a v a 的 c l a s s 文件为源代码。使用这些工具都能使得攻击者的攻击更有效率和成效。 广东工业大学工学硕士学位论文 2 。3 2 对d g w 水印的攻击 下面将分析这些攻击会对动态图水印产生如何的影响。大多数攻击其它类型 的水印的技术，比如语义保持变换和代码迷乱对于动态图水印没有影响。但是， 一些水印攻击技术能够有效地使d g w 水印的提取过程失败。根据 2 0 ，对d g w 水印 的攻击有可能是添加攻击，裁减攻击或者扭曲攻击。 ( 1 ) 添加攻击： 如前面讨论的，添加个新的水印。这种攻击对动态图水印与对其它类型的 水印一样有效。 ( 2 ) 裁减攻击： 完全地除去水印。这样软件的所有者就不能提取水印。因为别名分析的困难 性，动态图水印很难被移去。但是，一旦攻击者发现y d g w 结构的任何部分，他们 就能在程序中除去所有该类型的节点( 或者字段) ，然后删除所有对这些节点( 或 字段) 的引用，除非有防篡改技术来保护水印。防篡改技术能够检测出程序是否 被非法篡改，当有篡改时，该技术将使程序运行失败。 请看图2 8 。图2 8 中的方法使用了不透明谓词进行防篡改，创建了两个指向 水印结构w m 的指针。攻击者必须成功地进行别名分析才能将谓词( 啊f _ n ，) 用恰当 的常量值( t r u e ) 来代替。关于不透明谓词的介绍，可参见参考文献 2 7 【2 8 。 第二种防篡改技术也在图2 - 8 中进行了说明。水印结构和程序中的有用结构是 使用同一种d 6 w 的数据类型表示的。这种防篡改利用了两种结构的相似性。如果攻 击者从程序中移去所有的d g w 类型的节点，那么他们也将移去这种类型的有用结 构。区分w m 和那些有用的结构需要精确的别名分析。第一种方法在 1 9 中有简要 介绍。在 2 9 中对两种方法进行了扩展。 1 4 第二章软件水印技术概述 p u b l i ，fn 2i sa i l o t h e r n o d ei nw m 一1 # 出e r en l ! = n 2 ； i ( n 11 = n 2 ) ( p e r f o r m t a s l ) ： ) 图2 8 对一个d g w 进行防篡改 f i g u r e2 - 8t a m p e r - p r o o f i n gad g w ( 3 ) 扭曲攻击： 下面定义五种类型的扭曲攻击，并将依次讨论。见图2 9 。 ( a ) 在图节点中添加额外的指针。一个攻击者可能修改水印图结构的节点 类，使得水印的提取过程更加困难。例如，通过给节点类增加一些附加的字 段，原来的水印结构图g ( 如图2 9 ( i ) 所示) 变成图2 - 9 ( i i ) 。 ( b ) 删除结构的一部分。一个攻击者有可能删除水印结构的一部分，使得 提取过程失败。例如，图2 9 ( i i i ) 中的结构g 2 展示了g 中的节点d 和e 被移去之 后的样子。 ( c ) 分裂节点。水印结构的节点类被分裂为两个( 图2 9 ( i v ) ) 。这一行为 给g 中的每个节点添加了额外的引用，原来节点之间的链接状态被改变了，并 且水印树的数据结构有可能也被改变了。 ( d ) 给图结构增加额外的节点。在图2 9 ( v ) 中，三个额外的节点( f ，g ，h ) 添 加到g 上。这将使得水印提取过程困难，因为图结构改变了。 ( e ) 重命名或者重排序节点中的字段。如图2 1 1 ( v i ) 所示，图g 中的左右 指针的名字被交换了。结果就使得左予树从一个三个节点的子树变成了单节 点，而右子树从单节点的子树，变成了有三个节点的子树。这个改变有可能 影响到水印提取的结果。 1 5 广东工业大学工学硕士学位论文 2 4 水印的保护 g 蛾。a 圈阁。 图2 - 9 对d g w 水印的攻击 f i g u r e2 - 9 a t t a c k so i ld g ww a t e r m a r k 软件水印保护技术的目标是使得攻击者很难分析水印程序，从而防止水印被 发现，或者防止水印代码被修改或者被移去。然而，软件水印保护近年来并没有受 到很多关注。不同类型的水印可能需要不同的保护技术，对于新发展的水印技术 ( 如d g w ) 的保护，也没有受到重视。在本节中将讨论仅有的几种已经公开发表的 软件水印的保护技术。本文首先对这些保护技术进行概述，然后将重点介绍当前 可得的保护d g w 的方法。 2 4 1 软件水印保护技术概述 迷乱技术能够使攻击者分析源代码变得困难。防篡改技术能够使得攻击者很 难修改软件程序而不影响程序的可用性。关于迷乱和防篡改的概念。我们已经在 2 3 节中有介绍。图2 1 0 演示了如何使用这些技术来保护软件免于攻击。 第二章软件水印技术概述 在图2 1 0 ( a ) 中，a l i c e 使用密钥k 来对她的程序加水印，c h a l e s 使用同一个 密钥来提取水印。 在图2 - 1 0 ( b ) 中，a 1 i c e 通过增加防篡改代码丁来保护她的秘密信息s ，如果s 被篡改了，丁将使得程序运行失败。防篡改通常创建一个从水印程序到嵌入的水印 结构的依赖关系。如果水印结构被修改或者被除去，水印程序的功能有可能会出 错。图2 1 0 ( e ) 展示了迷乱技术。a 1 i c e 对她的程序进行一系列迷乱转换正疋e ，来 阻止b o b 对程序进行逆向工程。 c h 盯1 图2 - 1 0 ( a ) 给程序加水印 f i g u r e2 - l o ( a ) w a t e r m a r k a p r o g r a m 恸 团昂圜邑咯稚 好 图2 1 0 ( b ) 防篡改程序中的秘密信息 f i g u r e2 - 1 0 ( b ) t a m p e r p r o o f i n gap r o g r a m w i t hs e c l - e im e s s a g e ，雩查口奄， 吩l j1 图2 1 0 ( c ) 对程序进行迷乱转换 f i g u r e2 - l o ( c ) o b f u s c a t i o n t op r o g r a m 图2 1 0 水印保护方法：防篡改和迷乱 f i g u r e 2 1 0w a t e r m a r k p r o t e c t i o n ：t a m p e r - p r o o f i n ga n do b f u s c a t i o n 然而，上述的保护方法不可能适用于所有类型的水印。举例来说，一个静态 水印更有可能被迷乱转换破坏掉，而不是被保护。因此，构造水印的方式在它的 保护中起着重要的作用。 1 7 口 叠卷贫蕊贫 广东工业大学工学硕士学位论文 2 4 2 对d s w 水印的保护 如果一个攻击者不知道水印是怎样添加的，他们将必须使用通常的方法，这 些方法对于攻击大多数的普通水印是有效的。幸运地是，d g w 水印有一些虑在的特 性能够保护它免受攻击，正如在 1 9 中讨论的。因此，一般的水印攻击对于个d g w 水印可能并不是那么危险。举例来说，任何进行语义转换的迷乱攻击将不会影响 d g w 水印。然而，如果攻击者持有一些关于水印的信息，例如说知道它是一个d g w ， 或者明确地知道是一个p p c t 类型的d g w ，甚至更明确地知道p p c t 的根节点，他们的 攻击将会是更严重的，甚至是致命的。 一个攻击通常以下面两种方式发生：当一个攻击者不知道水印的位置时，他试 图通过迷乱来破坏或者扭曲水印：或者攻击者分析水印程序，试图发现水印的位 置然后瞄准水印进行攻击。因此，可以从三个方面改进水印保护方式。首先，可以 使d g w 变得更加鲁棒，这样d g w 水印就不会受那些更高级的迷乱转换( 比如数据结构 转换) 的影响。其次，可以阻止攻击者发现水印结构。最后，需要保护水印，避 免它被除去，甚至在攻击者发现了水印的位置之后。当然，一个保护方法可能有 上述的三个方面中的一个或者更多的功能。 在 1 9 中，c o l l b e r g 和t h o m b o r s o n 讨论了一个对d g w 水印的改进，来防止节点 分裂攻击。前面提到过，如果d g w 永印中的节点被分裂成多个部分或者如果一个额 外层次上的引用被添加到一个节点类上，如图2 9 ( i v ) 所示，那么d g w 水印结构将 不能够再被识别。 c o l l b e r g 和t h o m b o r s o n 建议将每个d g w 水印结构中的节点替换为一个节点的 循环，如图2 一l l 所示。在这种情况下，即使一个攻击者试图将一个节点分裂为两 个来破坏水印结构( 图2 1 1 ( c ) ) ，我们仍然能够把每个节点环合并成一个单独的节 点，这样原来的形状就可以获得。任何进一步的节点分裂只是使得这个节点环变 得更大，但是并不影响水印的提取。当然，这种方法需要额外的空间来储存许多 额外的节点，这看起来是不经济的。 c o l l b e r g 和t h o m b o r s o n 还提出了通过使用映射( r e f l e c t i o n ) 来迸行保护的 方法。j a v a 语言的映射可以被用来获得关于程序的信息，比如方法，字段和构造 函数等。这些信息可以被用来验证一个水印结构中的节点类没有被改变。因此， 第二章软件水印技术概述 j a v a 的映射可以被用来抵抗许多类型的攻击，如节点的重排序和重命名等。但是 正如他们指出的，在程序中使用映射是不隐秘的。 图2 - 1 1 ( a ) 原结构图2 1 1 ( b ) 用循环链表代替节点图2 1 1 ( c ) 攻击者分裂节点 f i g u r e