一种改进的基于PPCT编码软件水印方案
程成+曾嵘
摘要：该文针对PPCT软件水印编码效率低等问题提出了一种改进的基于PPCT编码的软件水印方案。该方案是结合了基数K编码、排列图编码以及PPCT编码的混合编码方案，将基数K编码的链表指针编码系数及排列图编码中枚举编码方案运用到PPCT编码中。并在SandMark实验平台上通过具体的实例证明在不影响PPCT数据结构及其抗攻击性的前提下增加了水印的数据率及鲁棒性。
关键词：PPCT编码；基数K编码；排列图编码；混合编码
中图分类号：TP18 文献标识码：A 文章编号：1009-3044（2016）12-0055-03
Abstract： In this paper a new dynamic graph encoding scheme based on hybrid encoding between radix-k encoding enumeration， permutation graph coding and PPCT encoding enumeration is proposed for improving the low efficiency of PPCT dynamic graph encoding. In order to improve the efficiency of PPCT， the method that the pointer of circular linked list is used to encode the coefficients in radix-k encoding enumeration to PPCT encoding enumeration is applied. On the SandMark experimental platform， the data rate and robustness of the watermark are increased without affecting the PPCT data structure and its anti attack.
Key words： PPCT coding； radix-k coding； permutation graph coding； hybrid coding
计算机及互联网等相关技术的不断发展给人类的生活带来了极大的便利，同时也带来了许多新的问题。数字信息技术的不断进步使得软件的盗版及非法使用变得越来越容易，给社会造成了巨大的经济损失，而且仍在逐年增加。软件版权的保护被越来越多的学者所关注。
软件水印是将作者的个人及版权信息转换成相应的水印信息嵌入到程序中，当软件发生版权纠纷时可提取出已嵌入的水印信息作为有效的法律依据证明作者的版权。软件水印按照嵌入时刻不同分为静态水印和动态水印[1]，静态水印由于其本身抗攻击性较低的缺点，许多学者转而研究动态水印，动态水印嵌入的不是水印信息本身而是代表水印的动态信息，保存在程序的执行状态中，如动态的数据结构中。
1996年，Davison和Myhrvold发表了基本模块调整算法[2]，该算法的基本思想类似于文本水印算法，把源程序中的每个基本模块进行重新排列，并将水印信息嵌入到程序中，这种算法比较容易在面向对象的程序中实现，只需将各个函数的排列顺序进行重新排列即可达到目的，但由于其实现方法较简单，导致其抗攻击性偏低。
2010年王慧娇等人提出一种基于PPCT和基数K的动态图混合编码方案[3]，主要是针对PPCT动态图编码效率低的问题，在保证其抗攻击性的前提下，将基数K枚举编码的循环链表指针编码系数的方法运用到PPCT枚举编码中，该方案同时具有了PPCT枚举编码的抗攻击能力和基数K枚举编码的编码效率。但由于两种方法中都含有大量的指针，导致这种混合编码方案的水印嵌入程序中后会对程序的运行速度有一定的影响。
在以上研究的基础上，提出了一种改进的基于PPCT编码的软件水印方案。该方案结合了PPCT编码、基数K编码以及排列图编码，使得PPCT树中叶节点指针能够指向树中所有的节点，在保证其抗攻击性的前提下提高了数据率及鲁棒性。
1基于PPCT的编码方案
1.1典型的PPCT编码方案
PPCT编码也是从二叉树转化而来的，它增加了一个生成节点Origin，这个节点的右指针指向第一个根节点，左指针指向最右边的叶节点，所有的叶节点的左指针从右向左依次链接，最左边的叶节点的左指针指向生成节点，所有的叶节点的右指针指向自己，如图1所示：
n个节点的PPCT编码表示的最大水印值为[Cn-12n-2n]，所以水印编码值的范围为0～[Cn-12n-2n]。PPCT编码的编码效率较低，但其容错与检错性较强。
1.2 PPCT与基数K混合编码
PPCT与基数K混合编码是将基数K链表水印编码中的叶节点系数编码方案运用到PPCT中[4]。对PPCT树中叶节点进行编号，并改变每个叶节点右指针指向，使其指向其他叶节点，这样即可得到一组对应的数字编码，通过计算可得到嵌入的水印数字。可大大增加嵌入水印的数据率。
1.3 PPCT与排列图混合编码
PPCT与排列图混合编码是在PPCT与基数K编码的基础上改进而来，对图中的叶节点进行编号，PPCT树中叶节点的每一个状态对应着一组数字，并对图中叶节点的编号进行全排列，每一组排列对应着一个数字，这样n个叶节点的PPCT图结构所能够表示的最大水印值为n！-1.此种编码结构的性能过载度与纠错能力要高于K基数编码，有较高的数据率，但其抗攻击能力较差，鲁棒性与PPCT编码相比要低一些，在实际使用中用的不多。
2.改进的PPCT水印方案
2.1 基本思想
本文提出的基于PPCT混合编码方案是将PPCT、K基数链表及排列图三种编码方案融合在一起，在不影响PPCT编码自身抗攻击性及程序运行速度的前提下提高水印的数据率，在水印中加入防篡改技术以提高水印的抗攻击性，利用水印的冗余嵌入实现水印的容错提取。其基本思想如下：
1） 首先需要对PPCT树进行改造。给树中的每个叶节点增加一个next指针，每个叶子节点的next指针只能指向除生成节点及叶子节点外的其他节点。下面对PPCT树中除生成节点外的其他节点编号，叶节点的编号规则：从PPCT树中的最左叶节点开始按照从左至右深度遍历的方式依次从0编号，假设PPCT树中的叶节点数为m，某个叶节点的编号为j，当某一节点指针指向此节点时，其代表的值为[mj]；除叶节点及生成节点外的其它节点编码规则：从生成节点的右指针所指向的节点开始按照深度遍历的方式从0逐个节点编号。同上，假设PPCT树中的此类节点数为n，某个节点的编号为k，当某一节点的指针指向此节点时其代表的值为[nk]。（如图2所示）
3） 基数编码值K既是重要的水印数据，又作为防篡改信息用于判定水印是否遭到攻击。为了进一步加强对K值的保护，采用AES模块对PPCT树及K值进行加密处理并将密钥妥善保管，使用AES模块加密处理是为了使其具有防篡改的功能。
2.2 水印的嵌入
水印的嵌入：1）首先确定需要嵌入的水印数据值并构造相应的PPCT树；2）在程序中嵌入创建PPCT水印的代码，同时为了提高水印的隐蔽性，可将水印进行分解，将不同的分支分别嵌入在程序中的不同位置；3）对嵌入水印后的代码及基数编码值K使用AES加密模块进行加密处理。
2.3 水印的提取
提取水印：1）计算实际的基数编码值[K']；2）通过密钥解密得到基数编码值K，并将[K']与K的值进行比较，若相等则说明版权得到验证；若不相等则说明水印遭到攻击破坏，程序会立刻终止运行；3）在提取水印的同时，随机执行验证代码检查程序是否发生可识别的攻击并恢复PPCT树结构.在水印中加入防篡改代码后，当嵌入水印后的程序遭到可识别的攻击后，程序不会立即终止，而是转而执行隐藏其中的冗余代码创建与原图相同的水印图，继续提取水印以验证程序的版权。
3 水印的性能分析
3.1 数据率
数据率是指一个程序中可嵌入的最大水印信息量，是软件水印系统的重要指标。一个好的水印方案必须满足在较少的节点中嵌入较多的水印数据，同时还要保证嵌入水印的隐蔽性与安全性，根据计算得到K基数编码、排列图编码、PPCT编码、PPCT混合编码及改进后的PPCT混合编码方案的数据率如下表所示：
从表1中可见，PPCT的数据率偏低，K基数编码的数据率强于其他水印方案，PPCT混合编码方案相对于PPCT编码数据率有较大提升，改进后的PPCT混合编码方案相比于原混合方案在数据率上略有提升，但仍低于K基数编码方案。四种水印方案的数据率对比图如图3所示：
3.2 隐蔽性
隐蔽性是用来衡量嵌入到程序中的水印信息被攻击者发现和和定位的难易程度。基于此，文献[5]提出了一个用水印信息与其周围代码及未嵌入水印的程序的特征值来表示水印的隐蔽性，特征值计算公式为：[d=i=0k（ni-mi）2]，其中{[ni]}为嵌入水印后的程序各个字节码指令所占的百分比，{[mi]}为一般程序各种字节码指令所占的百分比，特征值越小表示水印的隐蔽性越强。通过计算得到的4种算法的特征值如表2所示：
PPCT树的结构类似于线索二叉树，虽采用混合编码的方式提高了水印的数据率，但并未改变或破坏PPCT树的结构，因此PPCT本身仍然具有较高的隐蔽性，从表中的数据也可知，PPCT的隐蔽性要略好与其他方案。
3.3 抗攻击性
抗攻击性是水印性能指标中的重要一项，它是指水印抵抗攻击能力，在不计代价的条件下，理论上任何一种水印方案都是可以被破解的，对一种水印方案而言，只需其破解所需付出的代价要大于其破解所获得的利益，那么便可说这种水印方案的抗攻击性达到了要求[6]。下面从四个方面来介绍本水印方案的抗攻击性：
1） 添加或删除攻击。它是指攻击者对程序中的语句进行简单的添加或删除，由于在本水印方案中加入了防篡改方法，当攻击者对代码进行添加或删除后，程序运行时防篡改代码会进行检测，当发现代码被篡改后，会生成一个新的与原来相同的PPCT树结构来继续完成水印的提取。若不能够生成新的PPCT树结构，程序会立即停止运行。
2） 扭曲攻击。它是指在攻击者在找到水印嵌入的位置后，对嵌入水印的代码进行变换，如更改语序、改变表达式顺序以及更改条件规则等方法，以达到破坏水印提取的目的。这时防篡改代码同样会进行修复，因此该方法对水印的破坏力有限。
3） 代码优化攻击。该方案是攻击者同样在找到了水印的嵌入位置后，采用代码优化的方法将嵌入水印的冗余代码删除掉，达到破坏水印的目的。此种方法可能会删掉防篡改代码，使得水印无法修复。但在该水印方案中水印代码被拆分并嵌入到程序的不同区域，防篡改代码被删除的几率很低。
4） 语义保持攻击。它是指采用代码迷乱技术对程序进行攻击，在不改变程序的功能和特性的前提下打乱原程序的结构。对于本水印方案而言，打乱程序结构不会对水印造成影响，因为水印是经过拆分后嵌入到水印的不同区域中，单纯的打乱结构对水印功能不会有影响。
4 结束语
水印的各种性能指标之间是相互约束的，通常是一项指标的增强往往意味着另外其他性能指标的降低。软件水印方案的构造需要在其中寻找一个平衡点，使得各种性能指标都能够处于一个较高的水平。同时软件水印的发展仍处于起步阶段，其理论体系尚需不断完善。本文对基于PPCT编码的混合水印方案进行了改进，通过实验证明，在不影响PPCT编码原有的较好抗攻击性的前提下提高了水印的数据率，但仍低于K基数编码，而且由于水印中指针的大量增加，必定会对程序的运行造成一定的影响，因此该水印方案仍有进一步改进的空间，这也是下一步工作的方向。
参考文献：
[1] 张立和，杨义先，钮心忻，等.软件水印综述[J].软件学报，2003，14（2）：268-277.
[2] AKITO M， HAJIMUI， KEN-ICHI M，et al.Apractical method for watermarking Java programs[C]. Proceedings of the24th Computer Software and Applications Conference ，2000.
[3] 王慧娇.基于PPCT和基数K的动态图混合编码方案[J].计算机工程与应用.2010，46（25）：109-111.
[4] 周亮.软件水印算法评估研究[D].长春：吉林大学，2010.
[5] 蒋华，沙宗鲁，轩爱成.基于表达式逆序数的软件水印算法[J]. 计算机应用，2009，9（6）：3189-3190.
[6] 汤战勇，房鼎益，苏琳.一种基于代码加密的防篡改软件水印方案[J].中国科学技术大学学报，2011，41（7）：599-606.
[7]Christian S C， Ginger M， Andrew H Sandmark-A Tool for software Protection Research
[J] .IEEE Security & Privacy.2003，1（4）：40-49.
[8]虞泳.基于公钥加密算法和PPCT动态图编码的软件指纹方案[J].电脑与信息技术，2006，14（2）：38-40.
