摘  要  本文给出了一种改进的动态水印算法，该算法采用基于剩余定理的水印分割方法，并通过在程序中同时插入与分割的拓扑图相对应的校验比特串的方法提高其纠错能力和抗篡改能力。该算法具有编码纠错能力强、抗攻击能力好的特点，同时兼顾了基数－k编码方法编码率高、编码范围广的优点。     关键词  软件水印; 动态图; 路径; 防篡改 

1 引言

    软件水印技术是通过向程序中嵌入识别信息来抗击软件盗版，现今大多数已提出的软件水印算法都存在方方面面的缺点。根据水印被加载的时刻，软件水印分为静态水印和动态水印。静态水印存储在可执行的程序代码中，已知的静态水印都易于遭受简单的变形水印攻击，抗攻击能力差，任何代码优化技术都可以破坏水印。动态水印在程序运行时被构建，存储在程序的执行状态中。动态水印由于鲁棒性较强，现在受到了广泛的关注。    Collberg 和Thomborson^[1]提出了一种动态图水印技术，即把软件水印隐藏在程序动态建立的图结构拓扑中。由于指针结构的引入，使得控制动态图结构的那部分代码不易被分析，因而很难对图进行保持语义变换。这种技术的基本思想是用图的拓扑结构来代表一个数N，这个数是两个大素数的乘积，在进行水印检测时，先根据图的拓扑结构恢复出N，由于数论中的大数分解难问题，只有合法用户才能将检测到的N分解成大素数P和Q的乘积，从而证明其合法版权。与静态水印相比，动态图水印算法不容易受到代码最优化和代码迷乱等水印攻击的破坏，但是同样不能很好地抵抗篡改、裁减等恶意攻击。    软件水印的防篡改技术可以对软件及水印本身提供保护，当水印遭到破坏（水印代码被部分删除或优化等），程序能够立即感知并终止软件的运行。针对静态水印，Holmes（1994）提出了在水印中包含校验和的防篡改措施，但是如果攻击者掌握了校验和算法，就很容易修改校验和，防篡改能力十分有限。Moskowite和Cooperman^[5]（1998年）提出了另一种静态水印防篡改技术，即把水印代码嵌入到应用程序的特殊资源中，一旦该图像被篡改就立即终止程序的运行以此达到防篡改的目的。但是问题是这种凭空产生和执行的代码的不寻常性会使水印失去隐蔽性，引起攻击者的注意。至今为止，软件水印的防篡改技术仅仅处在一个摸索的阶段，所提出的各种理论和算法都存在一定的缺陷。    本文首先给出了一种基于中国剩余定理的动态图的构造算法和一种基于路径的防篡改的水印图的嵌入技术，在此基础上提出了一种改进的给予路径的动态防篡改水印算法。

2 动态图水印算法

动态图水印算法过程可以描述为下面几个步骤：    (1)将两个大质数的乘积作为水印数字w；    (2)将这个水印数字用一个特殊的拓扑图来表示；    (3)构造编码函数code() (构造编码函数的同时，应有相对应的解码函数decode())使该函数在运行时可以产生这个拓扑图；    (4)在原始程序中嵌入这段代码，使得添加水印后的程序只有在输入一个特定的序列时才构造出这个水印(我们称嵌入水印代码后的程序为载体程序)；    (5)当需要提取水印时，运行载体程序和水印检测例程，输入特定的序列，提取出拓扑图；    (6)调用解码函数decode()，将提取出的拓扑图还原为水印数字w。    假设p是未加入水印的原始程序，i是特定的输入序列，w是要嵌入的水印信息，g是可以唯一表示w的图，  为嵌入水印后的程序，e为水印嵌入函数，ex为水印提取函数。那么一个完整的动态图水印的过程就由下面四个函数组成：    水印数字映射为拓扑图: ;    拓扑图嵌入原始程序: ;    从载体程序中提取拓扑图: ;    图结构映射为水印数字: 。

3 基于路径的防篡改动态水印算法

    一个完整的软件水印算法应包含水印拓扑图构造、水印嵌入和水印提取三个部分。

3.1 水印的拓扑图映射

    将水印数字编码为拓扑图已经提出了多种编码方案^[1]，例如PPCT编码、基数-k编码、父指针树编码和排列编码。几种编码方式各有优缺点，实际应用时应根据软件水印系统的需求决定。比如，PPCT树的比特率比较低但纠错能力较强，而基数编码具有较高的比特率但纠错能力太差。    由于要嵌入的水印数字会是一个相当大的值，无论运用上述任何一种编码方式，它对应的拓扑图g的规模都会很大，如果将一个完整的g的构建代码全部嵌入程序中的某个位置，会使水印的隐秘性减弱而容易引起攻击者的注意，从而遭到破坏。随后Collberg 和Thomborson提出将拓扑图g分解为多个水印子图 ，并分别嵌入程序的不同执行路径中。该方法必须考虑水印图应如何分解才能保证在水印提取时添加最少的边连通所有的子图，而且对拓扑图进行分割，存在算法复杂度高、均匀分割困难以及分割后连通子图更困难的问题。    针对动态图分割存在的问题，本文给出了一种基于中国剩余定理的分割方法。3.1.1中国剩余定理    设Z_N 表示集合{0,1,…,N-1}, [M]_N表示M除以N的余数。    定理1 令 是两两互素的整数，且 ，则存在唯一的整数 ，且M的编码 是一个k元组< >。    定理2 如果 是两两互素的整数，且 ， 为整数序列且 ，若存在唯一的整数 ，使得 ，则有

其中， ， 。    借助于中国剩余定理可以把一个水印数据w分解为若干个子水印数据，之后可以通过这些子水印恢复水印数据w。3.1.2 算法描述    将素数序列 看作水印嵌入和提取的密钥， 水印数据 。把水印数据w转换为被嵌入水印中的拓扑图集合包含图1所示的几个步骤：    （1） 首先使 成对地关联在一起，共有 对，则w即被分成 块，每一块记为， （ ， ）。如果把每一个P_i 看作一个结点， 作为 P_i 和 P_j之间的一条边，那么当水印被攻击时，结点因被破坏而不能认知的几率减少一半。依据3.1.1中的定理2，如果要成功构建w，需要知道w对每一个P_i  取模的值。因为 是成对关联的，由 可以推导出所需要的值，从而从这个整数序列中能够重新构建w。这是图1中的第①步。    （2） 所有的 都可以通过一个枚举表被依次转化为一个单独的整数，枚举表中表达如下， ， 这是第②步。    （3） 在第③步中，每一个 都被编码为对应的拓扑图（3.2.2中给出了一个使用基数-k编码将水印数字转化为一个循环链表即拓扑图的例子）。    （4） 在第④步中，尽量选择在相对的执行频率比较低的代码中调用嵌入程序，加入水印代码。

图1 水印数字w=17,     这种把水印数字分解为数字序列再编码为相应的拓扑序列的方法就可以有效地解决拓扑图分割和组合困难的问题。

3.2 水印的嵌入

    在把水印数字w分解为序列串并转换为拓扑图序列后，如果对每一个拓扑图只是按照动态图水印的嵌入方法分散地嵌入整个原始程序中，则载体程序仍然不能抵抗高级迷乱攻击（比如当那些表示拓扑图的节点被成功“分裂”或“合并”），裁减攻击，扭曲攻击等。针对这些问题，本文给出了一种基于路径的防篡改动态嵌入方法。3.2.1 基于路径的动态嵌入方法    由于这种方法是根据条件语句（即程序的执行路径）的执行结果来表示比特串的，故称之为“基于路径”^[2]。下面对这种基于路径的比特位串的嵌入方法进行说明。这种方法包含的循环代码中必须有一个条件分支体，假设给定一个比特串0101，则下面的代码可以用来将0101嵌入。    因为0xa最小的有效位是0，循环内部的测试失效，那么指定这种测试失败产生一个0，测试成功产生一个1，0xa的剩余位从最小有效位到最大有效位排列是0，1，0，1，也就是内部虚幻测试先失败，然后成功，然后再失败，最后成功。测试结果产生需要的0101比特位。    理想情况下，我们应该把这些循环代码插入看起来不显眼的地方以使它们较少地成为攻击者显而易见的目标。为了达到这些目的，可以把条件谓词基于已经存在的程序变量，并可以在追踪中保存变量的值。通过检测程序中的变量值，当输入秘密的序列时，在程序中特定的点生成真假谓词的值。另外，在程序中一个特定的点把某些谓词的组合确定为真，把它们逻辑“与”产生也为真的复合条件，那么使用已经存在的程序变量构造任意的集合条件语句，就能使攻击者很难确定在保持程序正确性前提下这些语句是否可以安全除去。3.2.2 防篡改的动态水印嵌入    简单地说，每次在嵌入拓扑图的同时，使用基于路径的嵌入方法加入一段比特串用来和拓扑图相关联，通过对比特串和拓扑图的比较来检测水印是否遭到破坏。下面我们以基数-k编码^[4]为例来详细说明如何嵌入 。    基数-k编码是利用链接指针构成长度为n的循环链表并以n为基数进行编码；数据指针（虚线表示）表示各项系数：为空表示0，指向自身表示1，指向下一个节点表示2，依次类推；各项指数是当前节点到最后一个节点的节点数（如图2）。

图2 基数-k编码    该编码中指针的任何改变都会影响链表的循环结构以及编码属性，纠错能力较差。    为此本文设计了一个与拓扑图相关联的校验比特串依次表示出链表长度n，每一个数据指针的指向和所指向的节点数之和（称为校验位），图3给出了一个与图2中的拓扑图相关联的例子。
图3 校验比特串    下面的程序在嵌入拓扑图的同时嵌入上述比特串：

    当在进行水印检测时，检测程序记下嵌入水印前所嵌入的比特串，然后与提取出的水印拓扑图相比较，如果相符，则说明水印完好；如果不相符，则证明水印被改动过，这时再将拓扑图和比特串中表示数据指针指向的部分分别与比特串中的校验位相比较，取其中与校验位相符的取值重新构建水印。如果两者都不与校验位相符，还可以根据对w分解的过程对某个无法恢复的水印图做随机的假设。    通过增加校验比特串增加了软件所有者发现攻击者的任何对水印的细微改动的可能性，并且极大地增强了载体程序的纠错能力，即使水印被破坏也可以较完整地恢复。

3.3 水印的提取

水印的提取分为三步：    ● 在特定序列i下运行载体程序和检测例程，创建存在于堆中的拓扑图序列 。    ● 调用图的解码函数将拓扑图序列转化为水印数字序列 。    ● 将水印数字序列 根据剩余定理重新组合为水印数字w。     成功地恢复出水印数字w后，由于只有版权所有者才能分解w为两个大质数的乘积，版权归属问题即可得到证实。

4 结论

    本文在现有动态图软件水印系统的基础上，给出了基于中国剩余定理的水印分割方法，以及基于动态路径插入与分割后的拓扑图相对应的校验比特串的方法，有效地简化了动态水印的分割方法，极大地提高了其纠错能力和防篡改能力。

[1] Collberg, C., Thomborson, C., Townsend, G. Dynamic graph-based software watermarking. Technical report, Dept. of Computer Science, Univ. of Arizona (2004)[2] C. Collberg, E. Carter, S. Debray, A. Huntwork, C. Linn, and M. Stepp. Dynamic path-based software watermarking. In Proceedings of the Conference on Programming Language Design and Implementation,pages 107–118, 2004[3] C. Collberg and C. Thomborson. Software watermarking: Models and dynamic embeddings. In Proceedings of the 26th Conference on Principles of Programming Languages, pages 311–324, 1999.[4] Collberg C S, Thomborson C D. Watermarking, tamper-proofing, and obfuscation-tools for software protection[J]. IEEE Transactions on software Engineering, 2002, 28(8). Pages 735-746[5] 白雪梅,凌捷.基于动态图的防篡改软件水印实现方案[J].安全技术与应用,2005.07[6] 张立和,杨义先,钮心忻,牛少彰. 软件水印综述. 软件学报. 2003.02