一种HASH变换验证的软件水印算法实现（（

1、一种HASH变换验证的软件水印算法实现基金项目：国家863基金资助项目（2007AA01Z438200）作者简介：刘亚琦（1966），甘肃天水人，副教授，硕士研究生，主要从事信息安全的研究。吴振强（1968）男，陕西柞水人，博士，副教授，硕士生导师，研究方向为匿名通信技术、可信计算、自适应安全。刘亚琦（甘肃工业职业技术学院点电信学院）1 吴振强2（1甘肃工业职业技术学院信息工程系 天水 741025；2陕西师范大学计算机科学学院，西安 710062）中图分类号：TP309 文献标识码：A摘要：动态数据结构水印就是将水印隐藏在程序动态建立的图结构拓扑中，水印提取时的完整性是其关键技术。本文基于改

2、进的PPCT水印构造算法，通过Hash数学变换与验证，实现对水印的动态嵌入和可靠提取。分析与实现表明，本方法具有较强的安全性和鲁棒性，能够较好地实现软件的版权保护。关键词：动态图水印；，PPCT树；，Hash变换；，水印攻击Transformation of a HASH verification software watermarking algorithmLiu Ya-qi1 Wu Zhen-qiang2 (1 Department of Information Engineer, Gansu Industry Polytechnic College, Tianshui 741025 2

3、College of Computer Science, Shanxi Normal University, Xian 710062, China)Abstract: Dynamic data structure is to hide the watermark in the program dynamically builting graph structure topology, how to determine the integrity when the extracted watermark. Based on an improved watermark PPCT construct

4、ion algorithm, through the Hash mathematical transformation and verification, to realize the dynamics of the watermark embedding and reliable extraction. Analysis and implementation show that this method has strong security and robustness, can be used better for software copyright protection.Key wor

5、ds: Dynamic map watermarking;, PPCT tree;, Hash transformation,; Watermark attack动态图水印技术是近年来被广泛研究与讨论的一种软件水印技术。Collberg和Thomborson首次提出并讨论了动态图水印(Dynamic Graph Watermark，DGW)1，它是在软件运行时动态地将水印信息转化成某种图结构并隐藏在软件代码中，即把软件水印隐藏在程序动态建立的图结构拓扑中。由于这种图结构包含许多指针并且是在运行时动态生成，且指针的具体值在每次运行时不同，因此动态图水印算法不容易受到代码优化和代码迷乱等水印攻击的

6、破坏。但是这种图结构在抵抗篡改、裁减等恶意攻击方面表现较差。为了提高动态图水印技术的抗攻击能力，文献2提出多常量编码伪水印来对动态图水印进行保护的方法。该算法通过创建多个对宿主程序功能性有依赖关系的改进型PPCT （Improved Planted Plane Cubic Tree，IPPCT）结构的伪水印，对真实水印起到了防篡改的作用，增加了攻击者的攻击难度。文献3提出了基于二次剩余理论和Rabin 密码体制的水印信息方法，该算法在多个水印与宿主程序之间建立功能性的依赖关系，对真实水印起到掩盖作用，增加了攻击难度。文献4提出基于门限方案的动态图水印算法AB 算法，把水印信息分为无关联 n份嵌

7、入，在还原原始水印信息时，提取其中 t(tn)份以上的份额就可以恢复原始水印，提高嵌入水印的程序经攻击后恢复水印的成功率。文献5提出一种动态自我验证的软件水印防篡改技术，利用线性哈希函数对水印结构进行分块计算, 采用常量迁移技术使完整性检查隐藏在程序本身正常的逻辑判断语句中，对其篡改会导致应用程序功能错误。但这些方法减少了程序可容纳的水印信息量，水印恢复时涉及复杂的逆运算，增加了计算量和计算时间。本文提出一种基于节点命令词的ASC的HASH变换验证软件水印算法，水印完整性信息保存在程序结构中，当水印遭到攻击以致被破坏时（水印代码被部分删除或优化等），程序能够立即感知并终止软件的运行，从而实现对

8、软件及水印本身提供保护。1 动态图水印信息的形成根据数论中的大数分解难的问题，可选择一个代表版权信息的大自然数N 作为水印数，并将此大数N 转化成某种图拓扑结构后嵌入到软件程序代码里。只有合法用户才能将检测到N 分解成大素数P 和Q 的乘积，从而证明其合法版权通过拓扑类型的动态图数据结构水印隐藏此大数，如果能从软件中有效提取出此大数，且此过程能够在有限时间内完成，则证明对包含水印的待验证软件具有知识产权。其中，图的拓扑结构可以由面向对象程序设计中的对象作为节点构成，即图的编码采用改进的PPCT树。如图1表示：图1 用户水印信息转换成改进的PPCT树其具体过程为：(1)选择一个水印数字。(2)将

9、这个水印数字用一个水印图来表示。(3)构造一段水印代码，用来在运行时产生上述图结构。(4)在软件程序中嵌入这段代码，使得添加水印后的程序只有在接受一个特殊的输入序列时才构造这个水印。大数N根据公式 这个表达式的m 则是由这个树的叶子节点个数，系数ei取决PPCT树的叶子节点右指针指向的叶子节点返回到原叶节点所需要经过的叶节点的个数，这里规定叶节点的右指针为空表示0，指向自身表示1，指向下一个叶节点为2，依此类推。本文规定m的值为6，即叶子节点的个数为6个，则改进的PPCT结构表示成（m+1）=7为基数的表达式。任何叶子节点的右指针所指向的结点返回它本身所需经过的结点个数最多为6个，即任何一个系

10、数ei的值不超过6。所以N数的取值范围为0-117648之间。由Catalan理论，具有n个叶子结点的树共有：种，则对于6个叶子节点的树一共有42棵，所以我们所构造的指纹库中的序列也是这42棵树所对应的序列。22 水印信息嵌入过程2.1构造PPCT树随机构造总图，如图2。由构造的PPCT树计算其先序遍历顺序为：zabdhoooeoocfiooj oogkooloo，为了使构造的树唯一，要输入每个叶子结点的空值。图2 随机构造总图2.2 子图分解将图2的PPCT树分成几个子图，其中C节点为两个图的相交节点。分解成的两个子图如图3、图4所示。图3的先序遍历顺序为zabdhoooeoocoo，图4的

11、先序遍历顺序为cfioojoogkooloo。 图3 子图1 图4 子图22.3 Hash变换先序遍历所有的节点，令每个节点的ID域乘以它的序号作为di，计算子图的Hash值：Hash(0)=0Hash(i)=c*(di+Hash(i-1)其中0=i=n; c为非零常数，Hash(n)为该子图最后节点的hash值。 -695.1428图5 Hash变换以图5为例，将相应的节点值由字符转化为对应的ASCII值，进行Hash变换（表1），为了使子图的Hash值为0，将最后节点的值更改为 -695.1428。表1 Hash变换表节点ID值diHash值新的ID值1122122*112229797*2

12、31639898*36104100100*41010.13111111*13973214111111*1411286-695.14282.4嵌入水印流程图 嵌入水印的流程如下：（1）将版权信息映射为一个大数，从指纹库里面选取树，绑定水印信息；（2）分解树，构造两个子图G1，G2；（3）修改各个子图的最后一个结点，使得hash值和程序里面的一个常数对应。（4）用hash（Gi）替换程序中的常数，完成嵌入，如图6。部分关键代码如下：float ha(int n,float Gi) /计算节点的Hash值float re;if(n=0) re=0;else re=cc*(n*Gin+ha(n-1),

13、Gi);return(re);检测子图节点：void Checkall(int checkc,char cAry,float Gi,float Checki,int CG) /存储的检测信息的数组Checki,逆序计算出的用于计算大数的数组CG float checkchgvalue; checkchgvalue=(checkc/cc-Checki4)/Checki1;if(checkchgvalue=Checki5) /判断计算出的最后一个节点的数值是否等于数组Checki中存储的值 reha(int)Checki1,Gi,Checki,CG); /相等的话，则取出数组Checki中更改前的

14、最后一个节点的数值 for(int i=1;i=(int)Checki1;i+) cAryi-1=(char)CGi; /将数值数组转化为字符数组存储到字符数组中 elseprintf(常数或数组与嵌入不一致!n);3 水印信息的提取由于有Hash(i-1)=Hash(i)/c-di，对于给定的Hash(i)和i，可以逆序计算出所有节点的Hash值，因此可以计算出每个节点的ID值。然后将这些节点的值逆序转化为字符串，构造子图，然后进行子图的合并，构造树，然后根据树的指针的跳数来重新计算大数。如果大数与数据库中的大数匹配，则从数据库中读出水印信息，如果不匹配，则跳出或是执行相应的操作，如图7。图

15、6 水印嵌入 图7 水印提取4 模拟攻击分析4.1模拟攻击之一：去除攻击去除攻击是将水印信息w从软件Pw中去除。假设可以进行去除攻击的话，那么攻击者所要做的工作就是：将嵌入时用hash（Gi）替换的常数，还原成正常的常数，否则则攻击失败。基于分解子图G1，G2，将G1、G2嵌入源程序中，如：G1:ab*cd*e*,G2: ef*.假设，G1、G2中的一个被删除，那么我们借助于另外一个将其恢复，最极端的情况就是将G1、G2都替换，但是实现的难度比较大。4.2模拟攻击之二添加攻击即使攻击者给Pw再一次的嵌入新的水印，那么攻击者必须同时具备嵌入和检测的技术，以便来标识新的水印信息并保证软件的正常运行

16、。但添加攻击，并不影响对原水印信息的提取。为此，添加攻击的威胁性较小。4.3模拟攻击之三变形攻击由于变形攻击是基于对水印程序进行模糊变换，在不影响程序正常运行的基础上，攻击者有可能采取代码迷乱的技术进行模糊变换，但是，由于我们水印信息的嵌入和提取，与代码的执行流程等不相关，只是替换了程序中的常量，为此，变形攻击并不影响水印的正常不提取，变形攻击也变不构成威胁性。4.4模拟攻击之四共谋攻击 由于共谋攻击是通过对若干个已经嵌入过水印的软件进行比较，推测出水印的嵌入机制，显然，通过共谋攻击，最多的可以发现嵌入时，是用hash（Gi）来替换程序中的常量，但对于hash（Gi）所代表的子图长度，以及子图

17、的最后一个结点的数值无法获得，并且PPCT结构具有二又树和链表的双重特点，在构造软件水印时，可以利用指针来进行树的生成，根据现代操作系统中内存管理的特点，指针的具体值在每次运行时都是不同的，这给水印的隐藏提供了极好的条件。为此，共谋攻击最多也只是将hash（Gi）还原成原来正确的常量，这样以来就转化成了去除攻击。同时由于对于不同的软件嵌入水印的时候，都是随机的从指纹库里面读取树结构，随机产生一个大数与其对应，然后根据这个大数，添加指针的跳数，为此这么些随机性也就可以有效的防止共模攻击。5 性能测试及结论 在C+语言环境下，对C或C+语言编制的程序进行了测试，使用同方计算机（CPU 3.06GH

18、Z、512MB内存、100GB硬盘），其中一部分嵌入水印前后的各项参数比较如下：5.1文件大小比较文件的比较可以用表2所示。表2 软件水印嵌入前后程序大小比较嵌入前嵌入后大小7.16 MB （7,518,174字节）7.50MB (7,867,238字节)占用空间7.25 MB （7,602,176字节）7.79MB （8,171,520字节）包含39个文件，2个文件夹97个文件，2个文件夹5.2内存使用对比图8是内存的变化情况对比图。图8 内存使用情况对照从图中可以看出，添加水印前后的程序占用内存情况差距不大，相差大概100KB左右，改变率为1.07%。因此在运行方面不会对宿主程序产生太大的负载。虚拟内存使用图9是虚拟内存的使用情况对比图。图9 虚拟内存使用情况对照从图上分析，添加水印之前的虚拟内存使用情况大致为9100K左右，添加水印之后使得虚拟内存的使用情况上升至9400K左右，因此增加了300K的虚拟内存资源。这其中的大部分为二叉链表，二叉树，堆栈，队列等这些数据结构所开销，还有部分可能为系统的调用这些函数所要求的必要开支。对于一个比较小的函数来说，300K的内存资源增长略大，应该相应的控制以及精简，使得对宿主程序的影响更加小。本文实现了一种动态自