（计算机软件与理论专业论文）基于代码加密的防篡改软件水印技术的研究与实现.pdf

摘要 软件水印是一种解决软件版权保护的技术。传统的软件水印技术面临防篡改能力有 限，水印嵌入的数据率、鲁棒性较低等问题。本文围绕软件水印在版权保护中所关注的 上述问题，从软件盗版、软件篡改和逆向工程等攻击出发，结合静态分析、软件水印和 代码加密技术，来提高软件水印的数据率、鲁棒性和防篡改能力，增强软件水印的版权 证明能力。 论文通过比较静态水印与动态水印，深入研究了水印数据的分割算法、动态图软件 水印的水印拓扑图结构、水印的嵌入与提取过程等。在此基础上，给出了改进的水印拓 扑图结构，同时提出了“软件水印+ 代码加密 的软件保护方案，通过原型系统及实验 数据验证了该方案的可行性和有效性。具体研究工作主要包括： ( 1 ) 围绕动态图水印中的水印拓扑图结构进行研究。针对抗攻击性最好，但是数 据率较低的p p c t 结构，提出一种改进的m p p c t 结构，并将其与p p c t 结构进行比较 分析，结果表明m p p c t 结构在数据率方面具有明显优势，且能有效抵抗共谋攻击，是 一种良好的水印拓扑图结构。 ( 2 ) 为了增强软件水印的鲁棒性及防篡改能力，提出一种基于代码加密的防篡改 软件水印方案。水印嵌入过程中，使用基于广义中国剩余定理的数据分割法，对代表版 权信息的大数进行分割，以提高水印信息的隐蔽性。通过修改软件的源代码和目标代码 实现水印的嵌入过程，根据特定的策略对部分目标代码进行加密，并提高加解密密钥与 程序自身的关联聚合度，从而增强软件水印的鲁棒性以及防篡改能力。 ( 3 ) 设计并开发了原型系统m p p c t m a r k 。结合水印生命周期，使用一个具体 应用实例来阐述系统的整体工作流程。针对软件水印的数据率、隐蔽性、鲁棒性、安全 性以及给程序带来的性能过载等评价指标，对m p p c t m a r k 进行大量实验，实验数据和 结果充分表明了本文中水印方案的有效性、健壮性和可行性。 关键词：软件水印，动态图水印，广义中国剩余定理，代码加密，防篡改 a b s t r a c t s o f t w a r ew a t e r m a r k i n gi st h ek i n do ft e c h n i q u et op r o t e c tt h ec o p 河曲to fs o f t w a r e t r a d i t i o n a ls o f t w a r ew a t e r m a r k i n gh a ss o m el i m i t a t i o n so nt a m p e r p r o o f i n g , t h ed a t ar a t e ， i i o b u s t n e s sa n ds t e a l t h t h i st h e s i sf o c u s e so nt h ea b o v ei s s u e so fa p p l y i n gw a t e r m a r k i n gt o s o f t w a r ep r o t e c t i o n i no r d e rt oe n h a n c et h ea b i l i t yo fc o p y r i g h tp r o t e c t i o n ，t a m p e r p r o o f i n g s o f t w a r ew a t e r m a r k i n gs c h e m ew h i c hi sb a s e do nc o d ee n c r y p t i o nh a sb e e np r o p o s e d t h i st h e s i sc o m p a r e sd y n a m i cs o f h v a r ew a t e r m a r k i n gw i t hs t a t i cs o f t w a r ew a t e r m a r k i n g ， a n ds t u d i e so fw a t e r m a r kd a t as p l i ta l g o r i t h m ，t h et o p o l o g ys t r u c t u r eo fd y n a m i cg r a p h w a t e r m a r k i n g ，a sw e l la st h ep r o c e s so fe m b e d d i n ga n de x t r a c t i n gw a t e r m a r k an e w m e t h o d o fi m p r o v i n gt h ed a t ar a t eo fp p c ts t r u c t u r eh a sb e e np r o p o s e d f o re n h a n c i n gt h e t a m p r o o f i n ga b i l i t y , s o f t w a r ew a t e r m a r k i n ga n dc o d ee n e r y p t i o na r ec o m b i n e dt o g e t h e r t h e a c c o m p l i s h e dr e s e a r c h e sa r ea sf o l l o w s ： f i r s to fa l l ，s t u d yo ft h eg r a p ht o p o l o g ys t r u c t u r eo fd y n a m i cg r a p hw a t e r m a r k i n g ，a n d p r o p o s ea ni m p r o v e dt o p o l o g ys t r u c t u r e ，n a m e dm p p c t c o m p a r e d t ot h ep p c t , m p p c t s h o w st h ea d v a n t a g eo fd a t ar a t ea n dr e s i s t a n c et oc o l l u s i v ea t t a c k s e c o n d l y , i no r d e rt oi m p r o v et h et a m p e r p r o o f i n ga n de n h a n c et h ed i f f i c u l t yo f r g v e t s e e n g i n e e r i n ga n a l y s i s ，an o v e la p p r o a c ho ft a m p e r - r e s i s t a n ts o f c w a r ew a t e r m a r k i n gi sp r o p o s e d ， w h i c hi sb a s e do nt h ec o d ee n c r y p t i o nt e c h n i q u e t h ew a t e r m a r k i n gi se m b e d d e di n t oa p r o g r a mb ym o d i f y i n gi t ss o u r c ec o d ea n db i n a r yc o d e a c c o r d i n g t oo u rs t r a t e g y , p a r to ft h e c o d ei sc h o s e nt oe n c r y p t ，a n dt h ee n c r y p t i o nk e yi st i g h t l yr e l a t e dt ot h ep r o g r a m i na d d i t i o n ，w ed e s i g na n di m p l e m e n tap r o t o t y p es y s t e mw h i c hi sc a l l e dm p p c t m a r k ， a n dt h e nw ec o n d u c tal o to ft e s tc a s e s a c c o r d i n gt ot h ee x p e r i m e n tr e s u l t s ，w ea n a l y s et h e v a l i d i t y , r o b u s t n e s s ，d a t ar a t ea n dp e r f o r m a n c eo v e r l o a dw h i c hc a u s e db yt h ee m b e d d e d w a t e r m a r k ，t h er e s u l tv e r i f i e st h ef e a s i b i l i t ya n dv a l i d i t yo f t h es c h e m et h a tp r o p o s e d 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 cg r a p hw a t e r m a r k i n g ，g e n e r a lc h i n e s e r e m a i n d e rt h e o r e m ，c o d ee n c r y p t i o n ，t a m p e r p r o o f i n g 西北大学学位论文知识产权声明书 本人完全了解西北大学关于收集、保存、使用学位论文的规定。学校 有权保留并向国家有关部门或机构送交论文的复印件和电子版。本人允许 论文被查阅和借阅。本人授权西北大学可以将本学位论文的全部或部分内 容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存 和汇编本学位论文。同时授权中国科学技术信息研究所等机构将本学位论 文收录到中国学位论文全文数据库或其它相关数据库。 保密论文待解密后适用本声明。 学位论文作者签名：盏盈芷指导教师签名： 20 10 年6 月c 7 日2 0 10 年6 月7 日 西北大学学位论文独创性声明 本人声明：所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。 据我所知，除了文中特别加以标注和致谢的地方外，本论文不包含其他人已经发表或撰写过的 研究成果，也不包含为获得西北大学或其它教育机构的学位或证书而使用过的材料。与我一同 工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名：苗崭牝 2 0 l o 年6 月7 日 西北大学硕士学位论文 第一章绪论 本章首先介绍本课题的研究背景与意义；然后分析软件水印的研究现状；随后阐明 论文研究的主要内容；最后给出论文的结构以及章节安排。 1 1 研究背景与意义 随着计算机和互联网技术的快速发展，以及网络下载软件带来的便利性，使得人们 在没有被授权的情况下使用软件成为可能。从软件销售商到多媒体( 电影、音乐) 提供 商，他们都不希望自己的知识产权被侵犯，因此掀起了软件保护技术的研究热潮。软件 保护主要面临以下两种威胁【l j ： 一方面，软件盗版问题。软件盗版是指非法发布、复制、使用以及销售软件产品。 软件作为一种数字产品，开发成本很高，但是复制成本极低，复制过程几乎不会降低软 件质量，所以软件保护首要面对的是版权保护，预防软件盗版行为。随着互联网的普及， 高速大范围的盗版传播代替了以往小范围的复制，盗版软件可在极短的时间内传递到世 界各地。软件盗版给软件所有者带来巨大的经济损失：2 0 0 0 年，软件盗版率为3 7 ， 带来的经济损失约为11 7 5 亿美元，2 0 0 8 年，软件盗版率上升至4 1 ，带来的经济损失 约为5 3 0 亿美元【2 】，因此如何保护软件所有者的合法权益问题需要亟待解决。 另一方面，软件篡改以及逆向工程威胁。篡改技术最开始用于非法修改软件的 l i c e n s e 验证模块，以实现对软件或者多媒体文件的非法使用。逆向工程技术【3 】是指在 未经版权所有者同意的情况下，通过逆向工程工具分析出软件的架构，模块之间的调用 关系，从而窃取软件的关键算法，篡改用户数据。由于软件代码中包含着大量具有商业 价值的算法，一旦被窃取或篡改，造成的损失将会非常严重。 在软件自身安全问题越来越突出、盗版越来越猖獗的情况下，如何对软件进行有效 保护，是学术界与软件产业界更为关心的。许多国际大型软件公司和学术研究机构已经 深刻认识到软件保护的重要性，并已采取一定的措施，研究软件保护的相关技术。在国 际上，商业软件联盟b s a 每年发布的年度分析报告中都会给予软件保护高度的关注； 微软、i b m 等国际软件产业巨头投入大量的人力物力，对软件保护的关键技术进行研 究；加拿大、法国等国家也纷纷开展该领域的研究工作。在国内，西北大学、南京大学、 北京邮电大学、浙江大学、中国科技大学等学术机构也参与到软件保护方面的研究。由 于我国在软件保护方面的研究起步较晚，与当今发达国家相比仍有很大的差距。 第一章绪论 针对软件保护中面临的威胁，常用的保护手段有代码混淆、软件防篡改技术以及软 件水印技术等。代码混淆技术将代码进行混淆转换，将其变为难以理解的形式，从而增 加逆向工程的难度；软件防篡改技术是防止软件被非法篡改而提出的一种保护技术，当 检测到软件被篡改时，它会采取一定的响应机制来抵抗这种篡改行为；软件水印技术主 要用于证明软件的版权归属，所有者通过在软件里秘密嵌入一个代表版权的信息，嵌入 的信息可以用来标识作者、发行者、所有者等，它采取的是被动防御方式，将水印作为 盗版行为发生后的一种证据，当发生版权纠纷时，所有者从嵌入水印信息的软件中提取 出水印，来保护自己的版权。随着人们对版权问题的不断重视，软件水印技术受到越来 越多的关注，对软件水印技术的研究拥有广阔的应用前景。本文则以计算机面临的两类 威胁为主要出发点，将软件防篡改技术与软件水印技术相结合，对软件版权保护技术进 行新的探索。 1 2 软件水印的研究现状 随着软件水印技术不断被关注与重视，越来越多的学者开始研究软件水印技术，总 结如下： d a v i d s o n 和m y h r v o l d 提出了基本块重排算法【4 】。他们先把程序代码划分成基本块， 通过改变程序中的控制流图，对基本块进行重排编码的方式嵌入水印信息。提取水印信 息时，将嵌入水印前后程序中的基本块之间的顺序进行比较，得出水印信息。攻击者可 以使用代码混淆技术来重排基本块【5 1 ，或者在程序的控制流图中添加一个始终为t r u e 的不透明谓词分支来修改程序的控制流图【6 】，从而修改水印信息。 m o s k o w i t z 和c o o p e r m a n 提出了将代码以及水印嵌入到应用程序的特殊资源中【7 】 ( 例如图片声音等) 。程序在运行过程中，从资源里提取代码并执行，一旦隐藏水印信 息和代码的资源被篡改，程序就会终止运行，以此达到防篡改的目的。问题是这种凭空 产生和执行的代码的不寻常性会使水印失去隐蔽性，引起攻击者的注意。 s t e r n 等人提出ts h k q 算法【8 】，将扩频通信原理应用于软件水印中。在s h k q 算法 中，代码不仅作为顺序指令集，还作为统计对象。嵌入水印信息时使用了扩频技术，通 过修改代码里的某些连续指令集的频率来嵌入水印信息，通过比较软件在嵌入水印前后 的频率差额来提取信息。2 0 0 4 年，s a l l 0 0 与c o l l b e 唱对s h k q 算法进行了改进【9 】，引入了 一个代码簿( c o d eb o o k ) ，将同义的指令集存入代码簿中。根据水印信息，以及代码 簿中的同义指令，来修改指令频率。提取水印信息时，通过比较嵌入水印前后的两份程 2 西北大学硕士学位论文 序中的指令频率来获取水印信息。国内浙江大学的吴建军等人在2 0 0 5 年也提出了这种思 想【l o 】。由于攻击者可以通过保留语义攻击来修改程序中的同义指令，因此s h k q 算法难 以抵抗保留语义攻击，所以无法被广泛地应用。 m o n d e n 提出了基于不透明谓词的软件水印算法【1 1 1 ，通过在程序里构造虚假分支来嵌 入水印，a r b o i t 和f u k u s h i m a 分别对该算法进行了改进 1 2 , 1 3 。基于不透明谓词的水印算法 的主要思想是将水印嵌入到虚构方法或者不透明谓词分支中。不透明谓词是指谓词的结 果很难通过静态分析来预知，但是程序的设计者能够知道谓词的计算结果。由于每次执 行程序时，不透明谓词的值都是固定的，所以可以通过动态分析获取它的值。另外，如 果攻击者尝试在程序里构造自己的不透明谓词分支，则他就可能修改水印信息。 基于图理论的水印技术是软件水印的一个重要研究方向，目前国外已发表多篇关于 该课题研究的文献，主要有c t 算法和g t w 算法。第一个动态图水印技术是由c o l l b e r g 与t h o m b o r s o n 提出的，称为c t 算法【1 4 】。这种水印技术的基本思想是将水印图分解为 若干水印子图，并将它们分散地插入到程序中，在特定的输入下执行程序时，程序会在 堆中动态生成隐藏水印信息的拓扑图结构。它是最好的软件水印算法之一，由于水印结 构是在程序执行过程中动态生成的，因此隐蔽性较高。w s 提出了第一个g t w 水印算 法【1 5 1 ，将水印图分解为若干水印子图，通过在源程序的控制流图中插入不透明谓词分支， 将生成水印的基本块插入程序的控制流图中。为了能够方便地提取水印信息，生成水印 信息的基本块被标识，c o l l b e r g 等人实现了这种技术【1 6 ，1 7 1 。 c o l l b e r g 提出了基于软件分支的水印算法【1 8 】，基本思想是通过修改程序中的无条件 转移指令，将其跳转至一个新的分支函数，修改该分支函数的返回地址，使其返回至无 条件转移指令原始的目标地址，将水印信息隐藏在无条件转移指令序列的地址比较中。 规定对于无条件跳转指令序列l h e g i n a l a 2 _ _ l e n d ，如果a d d r e s s ( a i ) a d d r e s s ( a j ) ， 则隐藏的水印信息为0 ，反之为1 。基于软件分支的思想最初来源于代码混淆技术，优点 是能够隐藏程序真正的控制流。该方法容易遭受添加攻击，如果攻击者在l 蛐_ a l _ a 2 _ 一l e n d 里插入一条没有操作的无条件跳转指令，则会修改原有的水印信息，因此该 水印算法的鲁棒性较差。另一种具有代表性的分支水印算法是由g i n g e rm y l e s 等人提出 的【1 9 1 ，基本思想和c o l l b e r g 相似，将水印信息隐藏在程序的执行分支中，不同的是水印 的嵌入过程以及目标地址的计算方式不一样，它将水印信息作为常量，直接隐藏在分支 函数中，该算法鲁棒性也不好。由于插入的分支函数与程序的关联度不是很高，如果攻 击者通过监视执行无条件跳转指令时，寄存器中栈指针的值，那么就可以找到分支函数， 3 第一章绪论 当所有被替代函数以及分支函数都被找出后，恢复被修改的无条件跳转指令，就可以删 除分支函数，从而删除水印信息。g a u r a vg u p t a 已提出对这种算法的攻击方式【2 0 】。 n a g e a 和t h o m b o r s o n 提出了基于线程的软件水印算法1 2 1 1 ，并在j a v a 环境中进行实 现。该算法充分利用了多线程程序中的线程随机执行的优点，将水印嵌入在多线程并发 执行的轨迹中，具有较好的隐蔽性，但缺点是只能嵌入少量的水印信息。 至今为止，软件水印技术仅仅处于摸索阶段，还没有在商业领域中得到广泛应用。 1 3 研究的主要内容 本文将对软件水印及其防篡改技术进行全面分析和研究，并实现具有防篡改功能的 软件水印原型系统。本文主要研究内容包括以下四个方面： 1 分析软件水印技术的研究现状，阐述软件水印的分类、遭受的攻击以及常用的保护 方式。系统地分析并比较了静态水印技术与动态水印技术，由于静态水印鲁棒性不 如动态水印，因此本文重点研究动态软件水印技术。 2 研究现有动态图水印中隐藏水印信息的拓扑图结构。针对抗攻击性最好，但是数据 率较低的p p c t 结构，提出一种改进的m p p c t 结构，并将这种结构与其它拓扑图 结构进行比较，结果表明这种结构在数据率和鲁棒性方面具有明显优势，是一种良 好的水印拓扑图结构。 3 研究软件水印及其防篡改技术。为了提高软件水印的鲁棒性以及防篡改性能，提出 使用交错和互相保护机制，采用基于广义中国剩余定理的数据分割法，对代表版权 信息的水印大数进行分割，结合基于完整性的代码加密防篡改技术，以增强软件水 印的版权证明能力。 4 设计并开发了原型系统m p p c t m a r k ，并详细介绍实现过程，结合一个应用实 例来阐述m p p c t m a d k 的整体工作流程。根据对m p p c t m a r k 所做的大量测试以及 性能分析，验证了本文所提的水印算法具有较高的数据率、鲁棒性以及安全性。 1 4 论文结构以及章节安排 本文主要研究的是当前的软件水印及其防篡改技术，在对现有技术进行深入分析的 基础上，提出了一种基于代码加密的防篡改软件水印方案，同时对隐藏水印信息的p p c t 结构进行改进，使其具有更高的数据率。本文共分为六章，组织结构如下： 4 西北大学硕士学位论文 第一章：介绍本文的研究背景与研究意义，分析软件水印的研究现状，阐明本文的 研究内容以及论文的章节安排。 第二章：首先分析了软件水印的基本框架、评价指标、遭受的攻击以及常用的保护 方式，接着概要介绍了软件水印的分类，然后详细介绍了应用广泛的动态图软件水印技 术，最后重点介绍了基于广义中国剩余定理的水印数据分割法，为第三章的研究做理论 铺垫。 第三章：在对现有软件水印算法研究基础上，提出基于代码加密的防篡改软件水印 方案。首先介绍了相关支撑技术，随后针对p p c t 结构，提出了一种改进方式，以提高 它的数据率；然后阐明本方案的总体框架；最后详细讨论水印的嵌入以及提取过程，并 对所提方案进行防篡改性能分析。 第四章：设计并实现原型系统，详细阐述了关键算法的实现过程，最后结合一个应 用实例，来具体阐述原型系统的工作流程。 第五章：对原型系统进行测试，根据测试结果，从软件水印的评价指标出发，对原 型系统进行性能分析，分析结果证明了该方案的可行性、健壮性和有效性。 最后，对本文工作进行总结，并对后续工作进行展望。 5 第二章软件水印技术概述 第二章软件水印技术概述 软件水印技术是新兴的软件保护技术之一，解决的是软件版权保护问题。通过将水 印信息嵌入在宿主程序里，当发生版权纠纷时提取水印信息，用以证明软件的版权归属。 嵌入水印信息时，可以将水印嵌入在源代码中，也可以嵌入在二进制目标代码中。本章 介绍软件水印的相关技术，为第三章的研究做理论铺垫。 2 1 软件水印的模型 软件水印属于数字水印的一种，通过一定的嵌入算法，将软件的版权、发行者等信 息隐藏在程序中，当发生版权纠纷时，从软件中提取水印信息。下面给出软件水印的一 些理论模型，包括软件水印的基本框架、软件水印的评价、软件水印遭受的攻击以及常 用的保护方式。 2 1 1 软件水印的基本框架 图2 - 1 软件水印的基本框架 软件水印的基本框架是由用户密钥、原始程序、水印信息、水印的嵌入算法以及提 取算法组成( 如图2 1 ) ，具体包括水印的嵌入过程以及提取过程。 1 嵌入过程 根据用户密钥即程序的特定输入序列，以及嵌入算法，将水印信息编码后插入到原 始程序中，形成一个包含水印信息的新程序，表示为：e m b e d ( p ，w ，k e y ) p w 。 2 提取过程 根据用户密钥即程序的特定输入序列，以及提取算法，选择是否使用原始程序，从 包含水印的程序中提取水印信息，表示为：r e e o g n i z e ( p w ，k e y ) jw ，或者 r e e o g n i z e ( p w ，k e y ，p ) j w 。 6 西北大学硕士学位论文 2 1 2 软件水印的评价 度量软件水印算法好坏的指标主要包括2 2 2 3 】：嵌入水印后程序的正确性、软件水印 的数据率、鲁棒性、隐蔽性以及给程序带来的性能过载。 1 正确性：这是软件水印最基本要求。正确性是指嵌入水印前后的程序在行为上必须 保持一致。换句话说，就是要求相同的输入产生相同的输出。 2 数据率：表示嵌入在程序中的水印代码隐藏的信息量，要求软件水印应该包括足够 多的信息量。 3 鲁棒性：表示嵌入水印后的程序，能够抵抗攻击的能力，一般要求软件水印具有较 高的鲁棒性。 4 隐蔽性：表示攻击者得到一份程序后，通过各种方法仍不能确定该程序是否嵌入水 印，或者无法定位水印嵌入位置的能力。 5 性能过载：嵌入水印后的程序与嵌入水印前的程序相比，不能明显地影响程序的性 能，包括对占用空间以及执行时间的影响。一般要求软件水印具有较低的性能过载。 一个好的软件水印算法要求嵌入水印后的程序具有较高的数据率、较强的鲁棒性、 较高的隐蔽性和较低的性能过载。但高的数据率往往意味着低的鲁棒性以及差的隐蔽 性。因此设计一个水印算法时，往往需要对数据率、鲁棒性、隐蔽性以及性能过载进行 折衷考虑。除此以外，还要考虑下述2 个问题： 1 宿主程序的形式：嵌入水印前需要清楚的是宿主程序是二进制目标代码还是源代 码。 2 预期的攻击模型：由于没有一种水印技术能够抵抗所有的攻击，因此设计软件水印 算法时应该考虑期望系统能够抵抗何种类型的攻击。 2 1 3 针对软件水印的攻击 要评估软件水印算法的好坏，必须了解软件水印可能遭受的攻击。为了更好地阐述 针对软件水印的攻击模型，我们进行如下假设：a l i c e 在她的产品p 中嵌入自己的水印 信息w ，然后将包含水印信息的产品p 卖给b o b 。当b o b 将这个产品转售给j a c k 之前， 他必须使用一些攻击手段来破坏水印信息，从而避免引起版权纠纷。b o b 可以使用如下 的攻击方式【2 4 2 5 】： 1 减少攻击( s u b t r a c t i v ea t t a c k ) b o b 使用反编译、反汇编等技术，定位到软件水印的位置后，删除部分或者全部水 7 第二章软件水印技术概述 印信息，但是程序的功能保持不变，称为减少攻击。 2 添加攻击( a d d i t i v ea t t a c k ) b o b 在p 里添加自己的水印信息，如果b o b 的水印信息能够完全覆盖a l i c e 的水印 信息，或者不能证明a l i c e 的水印信息嵌入时间比自己早，称这种攻击为一个有效的添 加攻击。 3 扭曲攻击( d i s t o r t i v ea t t a c k ) 当b o b 不能够定位到水印位置时，他会通过保留语义转换程序，使得程序能够正常 运行，但a l i c e 无法提取水印的攻击手段，称为扭曲攻击。当攻击者无法定位软件水印 位置时，他常常使用保留语义转换的方法来破坏水印信息。保留语义转换是指在不改变 原程序语义的情况下，改变程序的控制流以及数据流，但转换后的程序功能和转换前是 相同的。常用的保留语义转换的手段有：反编译重编译、代码优化、代码混淆等。 4 共谋攻击( c o l l u s i v ea t t a c k ) 共谋攻击主要是针对软件指纹的。攻击者b o b 得到a l i c e 包含指纹的多个程序，通 过比较程序得出软件指纹的嵌入位置，继而破坏指纹的过程称为共谋攻击。 口 吟日( 2 ) a d d i t i v e l i ： w w w 2i 筇 图2 - 2 软件水印的攻击模型 2 1 4 软件水印的保护 软件水印的保护技术主要有代码混淆以及防篡改技术2 6 1 。代码混淆技术能够增加攻 击者分析源代码难度，防篡改技术能够在不影响程序功能的前提下，检测软件程序是否 被篡改，当检测到篡改行为发生时，会采取一定的响应机制，来抵抗篡改行为。下面概 要介绍这两种技术。 1 代码混淆技术 前面我们曾提到代码混淆技术对软件水印的攻击，在这里我们可以利用混淆技术的 另一面，来保护软件水印。代码混淆2 7 弓1 1 通过某种算法转换程序，转换后的程序保持原 r 西北大学硕士学位论文 有的功能，但代码变得难以阅读与理解。常用的混淆技术包括换名混淆、数据结构混淆、 数据流混淆与控制流混淆。混淆过程是不可逆的，在混淆过程中，一些不影响正常运行 的信息被永久删除或修改，例如死代码、程序注释以及调试信息等。将代码混淆技术应 用于软件水印中，增加攻击者分析代码难度，提高水印代码的隐蔽性，阻止攻击者找出 水印。 2 防篡改技术 防篡改技术使用篡改检测机制，控制软件在恶意主机上的运行方式。当篡改检测机 制检测出篡改行为时，它能够采取一系列的响应机制，来改变程序的正常执行逻辑【3 2 捌。 防篡改技术分为基于硬件的防篡改技术和基于软件的防篡改技术。基于硬件的防篡改技 术是将软件与硬件设备配套使用，通过安全的硬件设备来预防软件被篡改，而基于软件 的防篡改技术仅仅依靠软件自身机制来预防篡改行为。在软件水印中加入防篡改思想， 当攻击者找出水印位置并对其进行修改时，篡改检测机制能够检测篡改行为，并能够采 取相应的措施来阻止其修改水印信息。 没有一种水印技术方案能够抵抗所有的攻击，因此需要将多种技术结合起来，用以 提高软件水印的健壮性，增强水印的版权证明能力。 2 2 软件水印的分类 下面给出几种常见的软件水印分类方法【3 4 3 5 】： 按照水印的可见性分为可见水印和不可见水印。可见水印能通过人眼检测，当程序 在特定的输入下执行时，会显示图片或者l o g o 等；不可见水印是指产生的水印信息不 能够为人眼所感知，需要使用提取算法来证明版权。 按照水印的抗攻击能力可分为鲁棒水印和脆弱水印。鲁棒水印可以抵抗一定程度的 攻击，主要用于防止非法使用软件，保护软件的版权问题；对于脆弱水印，任何修改都 会破坏水印信息，使水印无法被检测，它一般用于确认软件的完整性；还有一种水印介 于二者之间，称为半脆弱水印，它对些操作是鲁棒的，但对重要数据特征的修改则是 脆弱的。 按照提取时是否需要未嵌入水印的原始程序，分为盲水印与非盲水印。盲水印在提 取水印信息时不需要原始程序，只需要用户密钥以及嵌入水印后的程序；而非盲水印提 取水印信息时需要原始程序，有时还需要添加至程序中的水印信息。 按照水印被加载的时刻，水印又可分为静态水印与动态水印，这是常用的分类方法， 9 第二章软件水印技术概述 下面主要按这种分类标准来讨论软件水印的分类。 2 2 1 静态软件水印 静态软件水印的存在不依赖于程序的运行状态，水印嵌入时不需要运行程序1 2 4 ，并 且在程序的执行过程中保持不变，可以在软件的分发与运行过程中被提取验证。根据水 印嵌入位置的不同可分为静态数据水印与静态代码水印【3 6 1 。 1 静态数据水印 静态数据水印将水印信息嵌入在程序的数据区域，比如注释、头文件、资源文件、 字符串或者调试信息中。由于它嵌入的位置比较有限，因此隐蔽性较差，容易被攻击者 定位，也难以抵抗代码混淆工具等保留语义转换攻击。例如，将水印信息隐藏在字符串 中，攻击者可以使用代码混淆工具，将字符串分割为多个字符子串，并把它们散布在程 序中，从而水印信息被分解，导致水印不能被正常提取；或者将水印信息隐藏在图片资 源里，如果使用图片修改工具对图片进行编辑，也会破坏水印信息。 2 静态代码水印 多媒体水印技术利用人眼对多媒体的部分修改不可感知性，将水印隐藏在多媒体的 冗余信息中，静态代码水印技术也借鉴了这种思想。代码水印技术利用代码冗余信息， 将水印嵌入到这些冗余信息中。例如在一些顺序无关的指令中，通过修改这些指令顺序 实现嵌入水印的目的。d a v i d s o n 提出的算法就是通过调整基本块序列来嵌入水印信息 【4 】，攻击者可以通过增加基本块来修改原始水印。m o s k o w i t z 提出将水印与代码一起嵌 入在程序的特殊资源里【7 1 ( 例如图片和音乐) ，程序执行时从资源里提取代码并执行， 这种算法的隐蔽性很低，凭空产生的代码很容易引起攻击者的怀疑，因此实用性较差。 静态软件水印的嵌入和提取过程都很简单，但是它难以抵挡扭曲攻击，一般的代码 混淆与代码优化工具都可以破坏水印信息。总之，尽管静态软件水印实现过程比较简单， 但是由于它本质的缺陷导致它的发展前景远不如动态软件水印。 2 2 2 动态软件水印 动态软件水印技术2 5 1 将水印信息隐藏在程序的执行状态中，而不是隐藏在程序的代 码或者数据中。动态软件水印根据特定的输入序列i = 1 0 i k 来嵌入水印信息，当执行 完i k 时，水印图在内存中生成，由于水印图是动态生成的，因此称这种水印技术为动态 软件水印技术。常用的动态水印技术有以下几种： 1 e a s t e r e g g 水印。 1 0 西北大学硕士学位论文 根据特定的输入序列嵌入水印信息，提取水印时，当执行完这些特定的输入时，会 显示出嵌入的水印。嵌入的水印信息可以是图片，或者版权者的姓名，公司的u r l 等。 由于提取水印信息时，e a s t e re g g 水印暴露了所嵌水印的位置，只要发现了正确的输入 序列，使用标准的调试工具可以去除水印信息。 2 动态数据结构水印 将水印信息隐藏在程序的数据结构中，例如树、链表、图等。当执行特定的输入序 列时，隐藏水印信息的数据结构在堆中生成。提取水印时也需要在特定的输入下执行程 序，当输入完毕后，通过检测隐藏水印信息的数据结构变量当前值来进行水印提取，提 取时可以使用一个水印提取进程，或者使用调试工具调试程序时查看变量的值。动态数 据结构水印与e a s t e re g g 相比有一个显著的优点：当输入特定的序列时，程序不会产生 一个明显的输出，因此不容易找出水印嵌入的位置，从而避免引起攻击者的注意。 3 执行踪迹水印 通过在特定的输入下执行程序，对程序中指令的执行顺序或内存地址走向进行编码 生成水印。检测水印时，通过检测地址流和操作码顺序的统计特性来完成。混淆转换以 及代码优化等工具会削弱指令的执行轨迹。 综合以上介绍，由于动态水印技术的鲁棒性高于静态水印，而动态水印技术中的动 态图水印技术的抗攻击性和隐蔽性又较好，因此我们选择动态图水印技术作为我们的研 究点，下面详细介绍动态图水印技术。 2 3 动态图( d g w ) 软件水印 c h r i s t i a nc o u b e r g 和c l a r kt h o m b o r s 提出一种新的软件水印技术，即动态图软件水 印( d y n a m i cc s r a p hw a t e r m a r k i n g ，简称d g w ) 【1 4 2 5 1 ，它将水印信息编码为某种拓扑图 结构，并把生成该图结构的代码嵌入到程序中，在程序运行时动态生成水印拓扑图。这 种水印技术充分利用操作系统的虚拟内存管理方式，使用指针来创建水印拓扑图结构。 由于指针技术的广泛应用、指针链接的相互影响，以及程序每次运行时，程序的逻辑内 存地址都会映射到不同的物理内存中，因此使用指针技术，将水印信息隐藏在一个不断 变化的拓扑图结构中，能够增加攻击者分析拓扑图结构的难度，从而大大地增加了软件 水印的鲁棒性与隐蔽性。 d g w 的水印信息选取方式与以往的水印技术不同。以往的水印技术通常将公司的 名称、地址、l o g o 等作为水印信息，而动态图水印技术将两个大质数p 、q 的乘积w 第二章软件水印技术概述 ( w = p xq ) 作为水印信息，然后将w 编码为某种拓扑图结构并将其嵌入程序中。根 据大数难分解理论，即使攻击者得到w ，他也很难得出代表版权信息的两个大质数p 与q 。 2 3 1d g w 的水印拓扑图结构 动态图软件水印( d g w ) 技术将水印编码在程序运行时动态建立的拓扑图结构中， 对隐藏水印信息的载体，即拓扑图结构的选取异常关键，好的拓扑图结构不但能有效阻 碍攻击者的分析，还能够降低程序的性能过载。表示水印信息的拓扑图结构有多种，例 如k 基数循环链表结构、排列图结构，以及p p c t 结构等1 2 5 1 ，下面详细介绍这些常用 的水印拓扑图结构。 1 k 基数循环链表结构 某一个整数可由n = a ox ? - 2 + a 1x k k - 3 + + 胪表示，因此就产生使用k 基数循环链表结构来表示水印信息的思想。如图2 3 ，这种水印结构是一个首尾相连的 循环链表，具有k 个节点，除了头节点外，其它的节点都有两个指针，右指针指向下 一个节点，左指针用来表示乘积因子a i 。a i 的取值遵循下述原则： a ) 如果左指针指向n u l l ，则a i = o ； b ) 如果左指针指向自身，则a i = l ； c ) 如果左指针指向下一个节点，则a i = 2 ； d ) 以此类推，如果左指针指向它前一节点，则锄= k 1 。 i 左指针l j - 卜右指针 图2 - 36 l 7 3 = 3 x 6 4 + 2 x 6 3 + 3 x 6 2 + 4 6 1 + l 6 0 由于n = 翰k 七一一2 ( k 为基数，且o a f 后) ，因此具有m 个节点的k 基数 循环链表能够表示水印数据的范围为0 到- 1 1 即能表示的数据数目为一1 。 2 排列图结构 自然数 19 - * 9 n 】的全排列的索引号与某个整数相对应，可以将这个整数作为水印信 息。表示自然数 1 ， 1 1 的某个全排列的图结构，称作排列图结构。排列图结构与k 基 1 2 西北大学硕士学位论文 数循环链表结构相似，都为具有双向指针的循环链表，唯一不同的是左指针的指向方式。 在排列图结构中，左指针指向该节点的节点序号在自然数某个全排列中所对应位置的节 点。例如，下图2 4 除了头节点外有5 个节点，1 号节点的左指针指向4 号节点，2 号 节点的左指针指向5 号节点，3 号节点的左指针指向自身，4 号节点的左指针指向1 号 节点，5 号节点的左指针指向2 号节点，因此图中表示的是【1 ，2 ，3 ，4 ，5 】的第2 9 个全排列 4 ，5 ，3 ，l ，2 】，它代表整数2 9 ，即水印信息为2 9 。由于自然数 1 ，n 】的全排列个数为n ! ， 所以具有m 个节点的排列图结构所能表示的数据数目为( m 1 ) l 。 ；一左指针i l ：! 右指针l 图2 _ 4 使用排列图结构表示数字2 9 3 p p c t 结构 在文献【2 5 】中，c o l l b e r g 和t h o m b o r s o n 描述了一种基于p p c t 结构的水印方案， p p c t 结构是由p p c t 树改进而来的。根据g o u l d e n 对p p c t 树的定义【3 7 1 ，如图2 - 5 ( a ) ， p p c t 树的特征可以描述如下： a ) 具有一个根节点，该根节点只有一个孩子节点。 b ) 树是平面的，具有n 个叶节点的p p c t 树，具有2 n 个节点。 c ) 所有节点的度为一或三。 p p c t 结构是对p p c t 树的改进，如图2 5 ( b ) ，它具有以下一些特征，使之可以成为 一种具有良好鲁棒性的水印载体。其特征描述如下： a ) 有一个根节点( o r i g i n 节点) ，该节点有两个指针，左指针指向这棵树的最右 下叶节点，右指针指向二叉树的根节点。 b ) 每个节点都拥有左右两个指针，非叶节点的左右指针指向自己的左右孩子，叶 节点的右指针指向自身，其左指针满足如下规则：非叶节点的右子树的左下节 点指向其左子树的右下节点，整棵树的最左叶节点指向o r i g i n 节点。 c ) p p c t 结构是可以枚举的结构。枚举规则为：比较2 棵树的左子树，深度大的 p p c t 结构序号大，如果深度相同，则递归比较左子树的左子树，深度大的序 号大，如果整棵树的左子树相同，则开始比较右子树的左子树。根据c a t a l a n 1 3 第二章软件水印技术概述 数理论【3 7 1 ，具有n 个叶节点的p p c t 结构共有c 伽) = 三c 2 ：种。 甩 根据特征( b ) ，具有n 个叶节点的p p c t 结构，只要找出p p c t 结构的任一节点，就 可以沿其左指针在n 1 步内找到o r i g i n 节点，从而实现对p p c t 结构的遍历。根据特征 ( c ) 中的枚举规则，p p c t 结构在p p c t 结构库中的索引号是唯一的，因此可以将水印数 与p p c t 结构的索引号相对应。换句话说，给定了合法的水印数据以及p p c t 结构的叶 节点数目，将会产生唯一的p p c t 结构。根据c a t a l a n 数理论【3 7 1 ，具有m 个节点的p p c t 结构可以表示的最大数为舌( i ，即能表示的数据数目为舌巧乏。 ( - p i i - w w( b ) p p c i | 尊柯 图2 - 5p p c t 树与p p c t 结构 2 3 2d g w 水印的嵌入 根据文献 2 5 】，如图2 - 6 ，d g w 水印的嵌入过程可以分为以下几个步骤： 1 标记：在程序里插入标记，这个标记是没有任何操作的m a r k 函数。避免将m a r k 函 数插入到循环语句或者频繁执行的位置。 2 追踪：根据特定的输入序列执行程序，找出能够执行到的标记，这些标记所在的位 置用来嵌入水印信息，没有执行到的标记被删除。当程序在给定的输入序列下执行 时，确保已保留的m a r k 标记肯定会被执行，这保