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

关键词 软件水印; 动态图; 路径; 防篡改

软件水印技术是通过向程序中嵌入识别信息来抗击软件盗版，现今大多数已提出的软件水印算法都存在方方面面的缺点。根据水印被加载的时刻，软件水印分为静态水印和动态水印。静态水印存储在可执行的程序代码中，已知的静态水印都易于遭受简单的变形水印攻击，抗攻击能力差，任何代码优化技术都可以破坏水印。动态水印在程序运行时被构建，存储在程序的执行状态中。动态水印由于鲁棒性较强，现在受到了广泛的关注。

Collberg 和Thomborson[1]提出了一种动态图水印技术，即把软件水印隐藏在程序动态建立的图结构拓扑中。由于指针结构的引入，使得控制动态图结构的那部分代码不易被分析，因而很难对图进行保持语义变换。这种技术的基本思想是用图的拓扑结构来代表一个数N，这个数是两个大素数的乘积，在进行水印检测时，先根据图的拓扑结构恢复出N，由于数论中的大数分解难问题，只有合法用户才能将检测到的N分解成大素数P和Q的乘积，从而证明其合法版权。与静态水印相比，动态图水印算法不容易受到代码最优化和代码迷乱等水印攻击的破坏，但是同样不能很好地抵抗篡改、裁减等恶意攻击。

软件水印的防篡改技术可以对软件及水印本身提供保护，当水印遭到破坏（水印代码被部分删除或优化等），程序能够立即感知并终止软件的运行。针对静态水印，Holmes（1994）提出了在水印中包含校验和的防篡改措施，但是如果攻击者掌握了校验和算法，就很容易修改校验和，防篡改能力十分有限。Moskowite和Cooperman（1998年）提出了另一种静态水印防篡改技术，即把水印代码嵌入到应用程序的特殊资源中，一旦该图像被篡改就立即终止程序的运行以此达到防篡改的目的。但是问题是这种凭空产生和执行的代码的不寻常性会使水印失去隐蔽性，引起攻击者的注意。至今为止，软件水印的防篡改技术仅仅处在一个摸索的阶段，所提出的各种理论和算法都存在一定的缺陷。

本文首先给出了一种基于中国剩余定理的动态图的构造算法和一种基于路径的防篡改的水印图的嵌入技术，在此基础上提出了一种改进的给予路径的动态防篡改水印算法。

动态图水印算法过程可以描述为下面几个步骤：

(1)将两个大质数的乘积作为水印数字w；

(2)将这个水印数字用一个特殊的拓扑图来表示；

(3)构造编码函数code() (构造编码函数的同时，应有相对应的解码函数decode())使该函数在运行时可以产生这个拓扑图；

(4)在原始程序中嵌入这段代码，使得添加水印后的程序只有在输入一个特定的序列时才构造出这个水印(我们称嵌入水印代码后的程序为载体程序)；

(5)当需要提取水印时，运行载体程序和水印检测例程，输入特定的序列，提取出拓扑图；

(6)调用解码函数decode()，将提取出的拓扑图还原为水印数字w。

假设p是未加入水印的原始程序，i是特定的输入序列，w是要嵌入的水印信息，g是可以唯一表示w的图，为嵌入水印后的程序，e为水印嵌入函数，ex为水印提取函数。

那么一个完整的动态图水印的过程就由下面四个函数组成：

水印数字映射为拓扑图: ;

拓扑图嵌入原始程序: ;

从载体程序中提取拓扑图: ;

图结构映射为水印数字: 。

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

将水印数字编码为拓扑图已经提出了多种编码方案[1]，例如PPCT编码、基数-k编码、父指针树编码和排列编码。几种编码方式各有优缺点，实际应用时应根据软件水印系统的需求决定。比如，PPCT树的比特率比较低但能力较强，而基数编码具有较高的比特率但能力太差。

由于要嵌入的水印数字会是一个相当大的值，无论运用上述任何一种编码方式，它对应的拓扑图g的规模都会很大，如果将一个完整的g的构建代码全部嵌入程序中的某个位置，会使水印的隐秘性减弱而容易引起攻击者的注意，从而遭到破坏。随后Collberg 和Thomborson提出将拓扑图g分解为多个水印子图 ，并分别嵌入程序的不同执行路径中。该方法必须考虑水印图应如何分解才能保证在水印提取时添加最少的边连通所有的子图，而且对拓扑图进行分割，存在算法复杂度高、均匀分割困难以及分割后连通子图更困难的问题。

针对动态图分割存在的问题，本文给出了一种基于中国剩余定理的分割方法。

3.1.1中国剩余定理

设ZN 表示集合{0,1,…,N-1}, [M]N表示M除以N的余数。

定理1 令 是两两互素的整数，且 ，则存在唯一的整数 ，且M的编码 是一个k元组 。

定理2 如果 是两两互素的整数，且 ， 为整数序列且 ，若存在唯一的整数 ，使得 ，则有

其中， ， 。

借助于中国剩余定理可以把一个水印数据w分解为若干个子水印数据，之后可以通过这些子水印恢复水印数据w。

3.1.2 算法描述

将素数序列 看作水印嵌入和提取的密钥， 水印数据 。把水印数据w转换为被嵌入水印中的拓扑图集合包含图1所示的几个步骤：

（1） 首先使 成对地关联在一起，共有 对，则w即被分成 块，每一块记为， （ ， ）。如果把每一个Pi 看作一个结点， 作为 Pi 和 Pj之间的一条边，那么当水印被攻击时，结点因被破坏而不能认知的几率减少一半。依据3.1.1中的定理2，如果要成功构建w，需要知道w对每一个Pi 取模的值。因为 是成对关联的，由 可以推导出所需要的值，从而从这个整数序列中能够重新构建w。这是图1中的第①步。

（2） 所有的 都可以通过一个枚举表被依次转化为一个单独的整数，枚举表中表达如下， ， 这是第②步。

（3） 在第③步中，每一个 都被编码为对应的拓扑图（3.2.2中给出了一个使用基数-k编码将水印数字转化为一个循环链表即拓扑图的例子）。

（4） 在第④步中，尽量选择在相对的执行频率比较低的代码中调用嵌入程序，加入水印代码。

图1 水印数字w=17,