一種改進的基于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 水印的提取

提取水?。?）計算實際的基數編碼值[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.