摘 要： 在经典的K基数循环链表" title="链表">链表结构和PPCT结构水印编码" title="水印编码">水印编码方式的基础上，提出了一种新的动态数据结构" title="数据结构">数据结构软件水印" title="软件水印">软件水印编码方案。理论和实验证明,该方案中采用改进的PPCT水印编码结构在多种评价指标上都具有一定的优势，是一个优良的动态软件水印编码方案。
    关键词： 软件水印  水印编码  K基数循环链表  改进的PPCT  数据率

    软件水印(Software Watermarking)作为一项新兴的软件保护技术在版权保护及软件防破解方面具有独特的优势。Collberg和Thomborson提出了一种相对高级的动态数据结构软件水印(Dynamic Data Structure Software Watermarking)技术，这种动态水印在隐蔽性和鲁棒性方面较通常的静态软件水印有明显的提高。对于一个动态数据结构软件水印系统来说，水印结构的编码方式尤为重要。Collberg和Thomborson在参考文献[2]中介绍了两种水印编码方案，其中分别引入了两种水印拓扑结构：“K基数循环链表结构” 和“PPCT（Planted Plane Cubic Tree）结构”。这两种水印结构各有优缺点，前者易于实现并且充分利用了节点的每一个指针域，但水印信息的表示结构单一；后者对于同一个水印信息可以有多种表示结构，有利于生成水印库，但对于叶节点的右指针却没有充分利用。
    本文在结合了这两种水印结构各自的优点的同时，摒弃了它们结构上的不足，对PPCT水印编码方式进行了改进，引进了一种新的动态数据结构软件水印编码方式。理论和实践证明，改进后的编码方案相对于改进前具有较好的性质。
1 动态数据结构软件水印技术
1.1 理论基础
    动态数据结构水印技术是指在程序运行时动态地生成水印，并将水印信息转化成某种拓扑结构隐藏在软件代码中，由于这种特殊的数据结构包含许多指针并且是在运行时动态生成，而指针的具体值在每次运行时都是不同的，所以相对于通常的静态水印来说，给攻击者带来的攻击难度更大。
    根据数论中的大数分解难的问题，可选择一个代表版权信息的大自然数N作为水印数，并将此大数N转化成某种数据结构后嵌入到软件程序代码里，由于此大数能够分解为两个足够大素数P和Q的乘积，只有合法用户才能检测到N并将其分解为P和Q，从而可证明该用户的合法身份。动态数据结构水印的嵌入是指在运行时将一个代表版权信息的大数表示成图拓扑结构并嵌入到宿主程序中，其过程具体描述为：
    步骤1：选取一个合适的水印数N。
    步骤2：将N表示成某种图拓扑结构G。
    步骤3：在运行时创建生成图拓扑结构G的水印代码。
    步骤4：将此水印代码嵌入到宿主程序中。
    其中，步骤2和3称为水印编码过程，它在一个动态数据结构软件水印系统中通常起着举足轻重的作用。
1.2 水印编码
    Collberg和Thomborson在参考文献[3]中曾描述了两种动态数据结构软件水印方案，它们分别是基于K基数循环链表和PPCT的水印编码结构。
1.2.1 K基数循环链表水印编码结构
    这种水印结构是一个首尾相连的循环双指针链表，如图1所示。该链表中每个节点有两个指针，后一个指针指向下一个节点，另外一个指针用来编码水印信息，其取值为：从这个指针指向的节点返回原节点所需要经过的节点数。也就是说，空指针表示0，指向自身的指针表示1，指向下一个节点的指针表示2，以此类推。并且为了在提取时便于定位水印，特意在链表首节点前添加了一个称之为Head的头节点，它的右指针指向首节点，左指针为空。

    对于十进制的水印数N，可以将其K进制分解为：例如，水印数N=4 453，其质因子为R₁=61，R₂=73。可以将此十进制水印数分解为六进制数：N=4453₁₀=3×6⁴+2×6³+3×6²+4×6¹+1×6⁰=32 3416
1.2.2 PPCT水印编码结构

    这种水印结构由PPCT树演化而来。PPCT树是一种具有良好性质的拓扑结构，从形式上看，它是一个特殊的二叉树，如图2(a)所示。对这种特殊的二叉树稍作改进就可生成一种能用以表示动态数据结构软件水印的PPCT水印编码结构，如图2(b)所示。

    PPCT水印编码结构具有以下一些特征，使之可以作为一个具有良好抗攻击性的软件水印载体，用以表示水印数。
    (1)有一个头节点，该节点的左指针指向这个树的右下节点，右指针指向树的根节点。
    (2)每个节点具有左、右两个指针，非叶节点的这两个指针分别指向自己的左、右子节点；叶节点的右指针指向自己，左指针的指向遵从下述规则：某非叶节点的右子树的左下节点的左指针指向其左子树的右下节点，整个树的左下节点的左指针指向Head节点。
    (3)PPCT结构是可以枚举的。因此，可以利用PPCT结构可枚举的特点，使水印数与某种PPCT结构在枚举中的索引号相对应，换句话说，给定了PPCT结构节点数目M和合法的水印数N，就会有一个惟一的PPCT结构来表示此水印信息。根据Catalan数理论^[4]，具有m个叶节点(总共2m个节点)的PPCT结构共有其中C(m)为Catalan数，即具有m个叶节点的PPCT 结构的数目。具有1～15个叶节点的PPCT结构所具有的种类数目分别为：1、1、2、5、14、42、132、429、1 430、4 862、16 796、58 786、208 012、742 900、2 674 440。
2 改进的PPCT结构水印编码方案
    图3(a)给出一种具有四个叶节点的PPCT水印编码结构。由图3(a)可以看出，所有叶子节点的右指针都指向自身，因此可以对叶子节点的右指针加以改进，使其包含一定的信息。

    类似于K基数循环链表结构，可以用这些叶节点的右指针来编码水印信息。在K基数循环链表结构中，水印数N可以用k-1个节点表示成以k为基数的表达式：其中，0≤e_i系数e_i的值可以用相应叶节点的右指针所包含的信息来表示，具体定义为：从相应叶节点右指针指向的叶节点返回到原叶节点所需要经过的叶节点的个数。换句话说，相应叶节点的右指针为空指针表示0，指向自身表示1，指向下一个叶节点则表示2，以此类推。图3(b)给出了改进后的PPCT结构，此结构表示水印数：

    由于这种改进的PPCT结构本身具有二叉树和链表的双重特点，在构造软件水印时，可以利用指针进行树的生成，根据现代操作系统中内存管理的特点，指针的具体值在每次运行时都是不同的，这就给攻击者带来极大的干扰。同时，对于具有m个叶节点的这种结构，只要找到其中的一个节点，按其左指针就可以在m-1步内找到Head节点，从而实现对整个图拓扑结构的遍历，这对于在内存堆栈中定位水印图拓扑结构很有帮助。同样，在这种结构中，某些节点的指针若被篡改，可以依据规则进行有效的恢复。
    对于一个动态数据结构软件水印系统而言，若采用改进的PPCT结构作为水印编码方案，表示一个512比特（约为10¹⁵⁵）的水印数，只需要81个叶节点，它相对于J.Palsberg方案^[5]中采用的PPCT结构表示法来说，降低了创建水印的空间复杂度以及水印的构造时间；并且，由于这种结构仍然保持了传统的PPCT结构的部分特征，对于m个叶节点，可以从个结构中任意选择一种作为水印的载体，这样就可以形成一个足够大的软件水印库，从而有利于抵抗针对水印的合谋攻击（Collusive Attacks）。
3 试验分析与比较
3.1 性能过载比较
    水印的嵌入改变了宿主程序的初始结构，势必会对程序的运行效率造成影响。因此有必要了解采用不同的水印编码方案会对程序造成怎样的影响。这里将从两方面衡量这种影响：不同结构水印的加载所带来的空间上的过载和时间上的过载。
    笔者选择了不同的测试用例进行性能测试，希望得到的一些结论，有助于辅助确定水印方案，寻求性能和安全的平衡点。
    测试环境：
        硬件：PC机，Pentium 4 CPU(3GHz)，512MB RAM
        软件：Microsoft Windows XP，j2sdk1.4.2_01
3.1.1 空间过载分析
    对于不同的水印结构，即使嵌入的水印节点数量相同，但由于它们结构上的不同，所带来的空间过载也并不相同。根据表1中的空间过载量可以看出，在嵌入水印节点数相同的情况下，采用PPCT和改进的PPCT结构所带来的空间过载量相当。

    无论采用何种编码结构的水印，它们所带来的空间过载量都相对比较稳定，并不随宿主程序的变换而发生变化。也就是说，在嵌入的水印信息量相同的情况下，宿主程序越大，水印系统所带来的空间过载越不明显。
3.1.2 时间过载分析
    表1中数据显示，对于动态数据结构水印系统而言，嵌入节点数均为6的K基数循环链表结构水印、PPCT结构水印和改进的PPCT结构水印后，程序执行时间分别比嵌入前平均上升了413.5%、123.6%和227.5%。
    由以上数据可以看出，对于动态数据结构水印系统，嵌入不同编码结构的水印所带来的时间过载并不相同，其中采用K基数链表结构时间过载最大，采用PPCT结构时间过载最小，而采用改进的结构水印所带来的时间过载介于二者之间。
3.2 数据率" title="数据率">数据率比较
    水印编码结构的选取对于动态数据结构软件水印系统来说至关重要，所选取的水印结构不仅要求易于实现、在性能上带来的过载小，而且最好具有较高的数据率，即能利用尽可能少的节点表示尽可能大的水印数。对K基数循环链表结构、PPCT结构以及改进的PPCT结构分别进行了实现。根据软件水印数据率的定义，可得这三种水印结构的数据率分别为：

    式中，N为水印图结构中节点个数。
    从图4中三种水印结构的数据率曲线走势可以看出，K基数循环链表水印编码结构具有最高的数据率，改进后的结构次之，PPCT结构的数据率最低。

    对于一个动态数据结构软件水印系统而言，一个优良的水印编码结构应该满足：
    (1)具有较高的数据率。
    (2)结构难于破解,易于实现，抗攻击性强。
    (3)对于同一个水印,最好有多种表示方法。
    (4)水印的加载应该尽可能少地带来程序空间和时间上的过载。
    综合上述分析可得出，所改进的水印编码结构虽然数据率略低于K基数循环链表结构，但由于自身结构上的特点，其抗攻击性要强于K基数循环链表结构，所带来的性能过载又比K基数链表结构低，再加上它的数据率又比PPCT结构要高，并且这种结构可以生成一个有利于抵抗合谋攻击的水印库。因此，对于一个动态数据结构水印系统而言，采用所改进的PPCT水印编码结构不失为一个良好的水印方案。
参考文献
[1] COLLBERG C， THOMBORSON J. Software watermarking: models and dynamic embeddings[C]. In: Aiken A, et al., eds. Proceedings of the 26th Annual SIGPLAN-AIGACT Symposium on Principles of Programming Languages (POPL’99), Association for Computing Machinery Press, 1999：311-324 .
[2] COLLBERG C， THOMBORSON J. Watermarking, tamperproofing, and obfuscation-tools for software protection[R].University of Arizona Technical Report 2000-0, Feb 2000.
[3] COLLBERG C,THOMBORSON J，TOWNSEND M. Dynamic graph-based software watermarking[R]. University of Arizona Technical Report，TR04-08,April 28, 2004.
[4] GOULDEN I P,JACKSON D M. Combinatorial enumeration[R]. NewYork: Wiliy,1983.
[5] PALSBERG J, KRISHNASWAMY S, KWON M, et al.Experience with software watermarking[C]. In Proceedings of ACSAC’00, 16th Annual Computer Security Applications Conference, 2000:308-316.