基于动态图和线程关系的混合软件水印算法

史宝会，徐振华，武 宏

（1.北京信息职业技术学院 计算机工程系，北京 100018；2.北京市经济管理学校 信息技术系，北京 100042）

基于动态图和线程关系的混合软件水印算法

史宝会1，徐振华1，武 宏2

（1.北京信息职业技术学院 计算机工程系，北京 100018；2.北京市经济管理学校 信息技术系，北京 100042）

针对单一动态图水印算法以及线程水印存在的不足，为了提高软件水印的安全性，提出一种基于动态图和线程关系的混合软件水印算法。首先采用动态图水印算法将子图生成代码嵌入到程序中，然后充分利用线程隐蔽性恢复嵌入到线程关系矩阵的水印信息，最后对算法性能进行仿真测试。结果表明，本文算法充分利用了动态图水印和线程关系的优点，实现了优势互补，不仅提高了水印的数据率，而且增强了水印的抗攻击性。

软件水印；动态图水印；线程水印；抗攻击性

随着计算机应用的日益深入，软件已经渗透到多个领域，软件产品的需要量急剧增加，但由于软件具有成本高、研发周期长、易复制等特点，软件版权问题也越来越严重[1]。尤其随着计算机网络技术的发展，信息传播更加方便，软件盗版日益猖獗，给企业和个人均带来了经济损失，如何对软件版权进行保护引起了人们的广泛关注[2]。

针对软件版权保护问题，大量学者投入了精力、物力和财力进行相关的研究，学术界和一些大型企业纷纷提出各种软件版权保护技术。传统软件保护方法主要有软件狗、加密、序列号等，这些方法比较简单，但是不能进行盗版跟踪，易被破解，无法对软件版权进行保护，应用范围比较窄[3-4]。为了更好的对软件版权进行保护，软件水印技术应运而生，其将用户身份信息、版权信息等以水印形式预先嵌入到软件中，而且嵌入的信息难以去除，如果发生版权纠纷时，版权所有者可以通过提取软件中的水印以检测非法复制以及盗版，来证明版权或追查盗版源[5-6]。软件水印根据水印嵌入和提取方式的不同，可以分为静态水印和动态水印两种[7]。静态软件水印算法是将水印信息隐藏于软件的静态文本中，具有嵌入和提取速度快、简单，但该水印易被混淆变换所破坏而失去作用，抗攻击性很差，实用价值低[8]。相对静态软件水印，动态软件水印算法将水印嵌入到软件的动态执行环境中，具有很高的隐蔽性，成为当前主要的软件版权保护技术。1999年，Collbergt等提出了一种动态图水印（dynamic graph watermarking，DGW）算法，又称CT算法[9]。CT算法的核心思想是：用一种图的拓扑结构来编码水印数字，由于数据结构中引入了对指针的操作，增加了混淆作用，可以有效抵抗各种攻击，具有较强的鲁棒性[10-12]，但是面对复杂多变的软件攻击，单一动态图水印技术远远不够；Nagra等给出了线程软件水印（thread-based watermarking，TBW）算法，可以够抵抗许多语义保持变换攻击，同时对程序大小和运行时间的影响保持在一个可以容忍的范围内，但存在效率低下的缺陷[13]。

为了更好的保护软件版权，提高软件水印的安全性，综合动态图和线程关系的优点，提出一种基于动态图和线程关系的混合软件水印算法，并采用仿真实验对算法性能进行分析和测试。

1 软件水印的工作原理

软件水印算法工作过程包括两个阶段：水印嵌入和提取，软件水印嵌入指采用一定的技术将版权信息嵌入到软件中，产生包含水印信息的软件；软件水印提取是水印嵌入的逆过程，当发生盗版问题时，通过一定的水印检测技术提取原先嵌入的水印，以鉴别软件版权，但为了更好的保护软件版权，在水印嵌入之前，通常采用一定的加密技术对水印进行加密，即密钥，综合上述可知软件水印的工作原理如图1所示。

图1 软件水印算法的原理

2 动态图水印和线程水印算法

2.1 动态图水印算法

2.1.1 水印信息的编码方式

在动态图水印算法中，首先将水印信息编码为图结构，然后将其存储于软件动态执行过程中，当前水印信息编码方式主要有：基数K链表、排列图、PPCT（planted plane cubic tree）等，每一种编码方式均具有各自的优点，相对于其他编码方式，PPCT编码的时间和空间复杂相对较低，数据嵌入率高，因此本文采用PPCT编码方式[14-15]。

在二叉树的基础上，PPCT增加了一个指向最右叶结点的左指针，同时右指针指向根节点，这样所有节点形成一个循环链表，PPCT结构具体如图2所示。

图2 PPCT的结构

PPCT结构的枚举规则：首先比较2个树的左子树，若它们深度相同，那么比较左子树的左子树，深度大的则序号大；若全部左子树均相同，那么比较右子树的左子树，这样就可以得到PPCT结构的全部种类数目。对于N个节点数的PPCT结构，就可以产生一个PPCT结构来描述水印信息，这样产生的编码具有防篡改性、隐蔽性。

2.1.2 动态图水印嵌入和提取步骤

Step1：输入要嵌入的水印信息；

Step2：将水印信息表示成一个水印数，并转化为PPCT结构；

Step3：将图 G 分割成几个子图 C0，C1，…，Cm；

Step4：编码每个子图G，并转换成相应的程序代码；

Step5：根据预定的输入序列 i0，i1，…，im，在程序标记位置嵌入C0，C1，…，Cm完成水印的嵌入；

Step6：提取水印时，执行含有水印的程序，在输入正确的预定序列后，程序会调用相应的水印构造代码 C0，C1，…，Cm，并在堆内存中动态生成图 Gi，当生成最后一个图Gm时，根据水印分割算法，还原整个拓扑图G，再将其转化为对应的原始水印信息。

动态图水印嵌入和提取过程具体如图3所示。

2.2 线程软件水印算法

线程是一段完成某个特定功能的代码，是软件中单个顺序的控制流。线程软件算法的主要思想为：在软件运行时的线程作为载体，将水印拓扑图的纠错码信息嵌入到软件中。在本文中将信息隐藏到线程关系矩阵中，线程关系矩阵是线程关系的矩阵表示形式，矩阵元素的值描述线程之间是否有关系。线程软件水印算法工作流程如图4所示。

图3 动态图水印算法的工作流程

图4 线程水印算法的工作流程

3 动态图和线程相融合的软件水印算法

由于软件盗版技术和攻击技术日益猖獗，单一的动态图水印算法和线程水印算法均存在各自的不足，难以实现软件版权保护，为此，基于组合优化理论，结合动态图水印算法和线程软件水印算法的优点，提出一种混合软件水印算法，其工作步骤如下：

1）先将需要嵌入的水印信息转换成一个大素数W，其中大素数W为两个较大素数的乘积，接着将水印数W用PPCT表示，然后用动态图的CT算法将水印图的子图生成代码嵌入到程序中。

2）将生成的PPCT水印图用邻接矩阵表示，对生成的邻接矩阵先进行置乱处理，得到纠错码矩阵，最后将纠错码矩阵编码到程序的线程关系矩阵中。

3）在水印图的提取过程中，检验提取的水印是否满足哈希映射，若不满足则根据提取的纠错码矩阵恢复水印信息。

4 仿真实验

为了测试本文混合软件水印算法（DGW-TBW）的性能，在Pentium Dual-Core 2.80GHz CPU，4 GB RAM，Unix操作系统，采用VC++6.0编程实现仿真实验。在相同条件下，采用动态图水印算法（DGW）、线程水印算法（TBW）进行对比实验，最终结果取10次实验结果的平均值。

4.1 数据率对比

数据率代表了一个软件水印算法的空间效率，是嵌入单位水印对目标程序内容大小增加的数量，TBW、DGW以及DGW-TBW算法的数据率对比结果如图5所示。从图5可知，随着节点的增加，所有算法的数据率都增加，但是在相同条件下，本文算法的数据率是最高的，空间利用效率最高，对比结果表明，DGW-TBW算法能够容纳更多的信息量，是一种性能良好的软件水印算法。

图5 数据率比较

4.2 空间过载量对比

TBW、DGW以及DGW-TBW算法的空间过载量如表1所示。从表1可知，相对于TBW、DGW算法，DGW-TBW算法的空间过载量相对较小，而空间过载量十分稳定，结果表明，DGW-TBW算法不仅可以很好隐藏嵌入的信息，同时出现空间过载量的概率相当小。

表1 不同算法的空间过载量（kB）比较

4.3 时间过载量对比

TBW、DGW以及DGW-TBW算法的时间过载量如表2所示。从表2可以明显看出，DGW时间过载量比较大，时间复杂比较大，TBW次之，DGWTBW算法的时间过载量最小，减轻了软件的负载，工作效率最高，可以较好的满足软件水印算法的在线检测要求。

表2 不同算法的时间过载量（μs）比较

4.4 抗攻击性能对比

TBW、DGW以及DGW-TBW算法的攻击性能实验结果如表3所示，其中“+”表示水印提取成功，“--”表示水印识别失败。从表3可知，DGW-TBW算法不仅继承了DGW算法各种抗攻击特性，同时具有TBW算法的防篡改及水印自恢复能力，可以正确地识别出各种水印，具有更优的鲁棒性，应用范围更加广泛。

表3 各算法的抗攻击性能对比

5 结束语

在分析动态图水印算法和线程水印算法不足的基础上，为了提高软件的安全性、以更好的保护软件，提出了一种基于动态图和线程关系的混合软件水印算法，其综合运用了动态图水印和线程水印技术的优势，以克服单一水印算法存在的缺陷，并通过仿真实验测度算法的性能。仿真结果表明，相对于动态图水印算法和线程水印算法，本文算法不仅降低水印嵌入和提取的时间复杂度，而且增强了水印的鲁棒性，具有更大的实际应用价值。

[1]陈帆，和红杰，王宏霞.用于图像认证的变容量恢复水印算法[J].计算机学报，2012，1（35）:9-12.

[2]王俊祥，倪江群，潘金伟.一种基于直方图平移的高性能可逆水印算法[J].自动化学报，2012，1（1）:88-96.

[3]赵春晖，刘巍.基于压缩感知的交互支持双水印算法[J].电子学报，2012，4（4）:681-687.

[4]霍耀冉，和红杰，陈帆.基于邻域比较的JPEG脆弱水印算法及性能分析[J].软件学报，2012，9（23）:2510-2521.

[5]张秋余，孙媛，晏燕.基于分块自适应压缩感知的可逆水印算法[J].电子与信息学报，2013，4（35）:797-804.

[6]王奇胜，朱长青，符浩军.利用数据点定位的矢量地理数据数字水印算法[J].测绘学报，2013，4（42）:310-316.

[7]刘真，白韬韬，卢鹏.一种解密图像无背景噪声的加密全息数字水印技术[J].光学学报，2015，2（2）:88-95.

[8]刘竹松，陈平华，刘怡俊.混沌数字水印技术研究进展[J].计算机应用研究，2011，1（28）:1-5.

[9]赵彦锋.基于 Asmuth-Bloom体系的动态图水印实现方案[J].现代电子技术，2011，34（5）:125-128.

[10]蒋刚毅，李文锋，郁梅，等.H.264/AVC压缩域鲁棒视频水印[J].光学精密工程，2015（1）：260-270.

[11]刘建蓉，秦拯，彭程.改进的动态图水印技术编码方案[J].计算机应用研究，2011，28（2）:720-724.

[12]李淑芝，王显珉.基于循环冗余校验的动态图软件水印方案[J].计算机应用研究，2012，29（3）:968-970.

[13]许金超，曾国荪.一种基于线程关系的软件水印算法[J].电子学报，2012，40（5）:891-896.

[14]王慧娇，沙宗鲁，轩爱成.基于PPCT和基数k的动态图混合编码方案[J].计算机工程与应用，2010，46（25）:109-111.

[15]王亿首，徐江峰.改进的PPCT混合编码方案[J].计算机工程与应用，2012，48（34）:107-111.

Hybrid software watermarking algorithm based on dynamic graph and thread relation

SHI Bao-hui1，XU Zhen-hua1，WU Hong2
（1.Department of Computer，Beijing Information Technology College，Beijing 100018，China；2.Department of Information，Beijing Economic Management School，Beijing 100042，China）

In order to improve the security of watermark，this paper proposes a hybrid software watermarking algorithm to solve the shortage of dynamic graph watermarking algorithm and thread-based watermarking，Firstly，the dynamic graph watermarking algorithm is used to improves the software watermarking dynamic bit rate，and then thread-based watermarking is used to recover of embedded watermark information from the thread connection matrix，finally the simulation experiments is used to test the performance of the algorithm.The results show that the proposed algorithm has the advantages of dynamic graph watermarking algorithm and thread-based watermarking to realize the complementary advantages,not only improves the watermark data rate,but also enhance the robustness of watermark.

software watermarking； dynamic graph watermarking；thread-based watermarking； resistance

TN702

A

1674－6236（2017）16-0175-04

2016-06-24稿件编号：201606188

史宝会（1964—），女，山东栖霞人，硕士，副教授。研究方向：网络与信息安全管理测评，云计算与虚拟化技术应用及云数据中心架构等。