一種改進(jìn)的基于PPCT編碼軟件水印方案

程成+曾嶸

摘要：該文針對(duì)PPCT軟件水印編碼效率低等問題提出了一種改進(jìn)的基于PPCT編碼的軟件水印方案。該方案是結(jié)合了基數(shù)K編碼、排列圖編碼以及PPCT編碼的混合編碼方案，將基數(shù)K編碼的鏈表指針編碼系數(shù)及排列圖編碼中枚舉編碼方案運(yùn)用到PPCT編碼中。并在SandMark實(shí)驗(yàn)平臺(tái)上通過具體的實(shí)例證明在不影響PPCT數(shù)據(jù)結(jié)構(gòu)及其抗攻擊性的前提下增加了水印的數(shù)據(jù)率及魯棒性。

關(guān)鍵詞：PPCT編碼；基數(shù)K編碼；排列圖編碼；混合編碼

中圖分類號(hào)：TP18 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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

計(jì)算機(jī)及互聯(lián)網(wǎng)等相關(guān)技術(shù)的不斷發(fā)展給人類的生活帶來了極大的便利，同時(shí)也帶來了許多新的問題。數(shù)字信息技術(shù)的不斷進(jìn)步使得軟件的盜版及非法使用變得越來越容易，給社會(huì)造成了巨大的經(jīng)濟(jì)損失，而且仍在逐年增加。軟件版權(quán)的保護(hù)被越來越多的學(xué)者所關(guān)注。

軟件水印是將作者的個(gè)人及版權(quán)信息轉(zhuǎn)換成相應(yīng)的水印信息嵌入到程序中，當(dāng)軟件發(fā)生版權(quán)糾紛時(shí)可提取出已嵌入的水印信息作為有效的法律依據(jù)證明作者的版權(quán)。軟件水印按照嵌入時(shí)刻不同分為靜態(tài)水印和動(dòng)態(tài)水印[1]，靜態(tài)水印由于其本身抗攻擊性較低的缺點(diǎn)，許多學(xué)者轉(zhuǎn)而研究動(dòng)態(tài)水印，動(dòng)態(tài)水印嵌入的不是水印信息本身而是代表水印的動(dòng)態(tài)信息，保存在程序的執(zhí)行狀態(tài)中，如動(dòng)態(tài)的數(shù)據(jù)結(jié)構(gòu)中。

1996年，Davison和Myhrvold發(fā)表了基本模塊調(diào)整算法[2]，該算法的基本思想類似于文本水印算法，把源程序中的每個(gè)基本模塊進(jìn)行重新排列，并將水印信息嵌入到程序中，這種算法比較容易在面向?qū)ο蟮某绦蛑袑?shí)現(xiàn)，只需將各個(gè)函數(shù)的排列順序進(jìn)行重新排列即可達(dá)到目的，但由于其實(shí)現(xiàn)方法較簡(jiǎn)單，導(dǎo)致其抗攻擊性偏低。

2010年王慧嬌等人提出一種基于PPCT和基數(shù)K的動(dòng)態(tài)圖混合編碼方案[3]，主要是針對(duì)PPCT動(dòng)態(tài)圖編碼效率低的問題，在保證其抗攻擊性的前提下，將基數(shù)K枚舉編碼的循環(huán)鏈表指針編碼系數(shù)的方法運(yùn)用到PPCT枚舉編碼中，該方案同時(shí)具有了PPCT枚舉編碼的抗攻擊能力和基數(shù)K枚舉編碼的編碼效率。但由于兩種方法中都含有大量的指針，導(dǎo)致這種混合編碼方案的水印嵌入程序中后會(huì)對(duì)程序的運(yùn)行速度有一定的影響。

在以上研究的基礎(chǔ)上，提出了一種改進(jìn)的基于PPCT編碼的軟件水印方案。該方案結(jié)合了PPCT編碼、基數(shù)K編碼以及排列圖編碼，使得PPCT樹中葉節(jié)點(diǎn)指針能夠指向樹中所有的節(jié)點(diǎn)，在保證其抗攻擊性的前提下提高了數(shù)據(jù)率及魯棒性。

1基于PPCT的編碼方案

1.1典型的PPCT編碼方案

PPCT編碼也是從二叉樹轉(zhuǎn)化而來的，它增加了一個(gè)生成節(jié)點(diǎn)Origin，這個(gè)節(jié)點(diǎn)的右指針指向第一個(gè)根節(jié)點(diǎn)，左指針指向最右邊的葉節(jié)點(diǎn)，所有的葉節(jié)點(diǎn)的左指針從右向左依次鏈接，最左邊的葉節(jié)點(diǎn)的左指針指向生成節(jié)點(diǎn)，所有的葉節(jié)點(diǎn)的右指針指向自己，如圖1所示：

n個(gè)節(jié)點(diǎn)的PPCT編碼表示的最大水印值為[Cn-12n-2n]，所以水印編碼值的范圍為0～[Cn-12n-2n]。PPCT編碼的編碼效率較低，但其容錯(cuò)與檢錯(cuò)性較強(qiáng)。

1.2 PPCT與基數(shù)K混合編碼

PPCT與基數(shù)K混合編碼是將基數(shù)K鏈表水印編碼中的葉節(jié)點(diǎn)系數(shù)編碼方案運(yùn)用到PPCT中[4]。對(duì)PPCT樹中葉節(jié)點(diǎn)進(jìn)行編號(hào)，并改變每個(gè)葉節(jié)點(diǎn)右指針指向，使其指向其他葉節(jié)點(diǎn)，這樣即可得到一組對(duì)應(yīng)的數(shù)字編碼，通過計(jì)算可得到嵌入的水印數(shù)字。可大大增加嵌入水印的數(shù)據(jù)率。

1.3 PPCT與排列圖混合編碼

PPCT與排列圖混合編碼是在PPCT與基數(shù)K編碼的基礎(chǔ)上改進(jìn)而來，對(duì)圖中的葉節(jié)點(diǎn)進(jìn)行編號(hào)，PPCT樹中葉節(jié)點(diǎn)的每一個(gè)狀態(tài)對(duì)應(yīng)著一組數(shù)字，并對(duì)圖中葉節(jié)點(diǎn)的編號(hào)進(jìn)行全排列，每一組排列對(duì)應(yīng)著一個(gè)數(shù)字，這樣n個(gè)葉節(jié)點(diǎn)的PPCT圖結(jié)構(gòu)所能夠表示的最大水印值為n！-1.此種編碼結(jié)構(gòu)的性能過載度與糾錯(cuò)能力要高于K基數(shù)編碼，有較高的數(shù)據(jù)率，但其抗攻擊能力較差，魯棒性與PPCT編碼相比要低一些，在實(shí)際使用中用的不多。

2.改進(jìn)的PPCT水印方案

2.1 基本思想

本文提出的基于PPCT混合編碼方案是將PPCT、K基數(shù)鏈表及排列圖三種編碼方案融合在一起，在不影響PPCT編碼自身抗攻擊性及程序運(yùn)行速度的前提下提高水印的數(shù)據(jù)率，在水印中加入防篡改技術(shù)以提高水印的抗攻擊性，利用水印的冗余嵌入實(shí)現(xiàn)水印的容錯(cuò)提取。其基本思想如下：

1） 首先需要對(duì)PPCT樹進(jìn)行改造。給樹中的每個(gè)葉節(jié)點(diǎn)增加一個(gè)next指針，每個(gè)葉子節(jié)點(diǎn)的next指針只能指向除生成節(jié)點(diǎn)及葉子節(jié)點(diǎn)外的其他節(jié)點(diǎn)。下面對(duì)PPCT樹中除生成節(jié)點(diǎn)外的其他節(jié)點(diǎn)編號(hào)，葉節(jié)點(diǎn)的編號(hào)規(guī)則：從PPCT樹中的最左葉節(jié)點(diǎn)開始按照從左至右深度遍歷的方式依次從0編號(hào)，假設(shè)PPCT樹中的葉節(jié)點(diǎn)數(shù)為m，某個(gè)葉節(jié)點(diǎn)的編號(hào)為j，當(dāng)某一節(jié)點(diǎn)指針指向此節(jié)點(diǎn)時(shí)，其代表的值為[mj]；除葉節(jié)點(diǎn)及生成節(jié)點(diǎn)外的其它節(jié)點(diǎn)編碼規(guī)則：從生成節(jié)點(diǎn)的右指針?biāo)赶虻墓?jié)點(diǎn)開始按照深度遍歷的方式從0逐個(gè)節(jié)點(diǎn)編號(hào)。同上，假設(shè)PPCT樹中的此類節(jié)點(diǎn)數(shù)為n，某個(gè)節(jié)點(diǎn)的編號(hào)為k，當(dāng)某一節(jié)點(diǎn)的指針指向此節(jié)點(diǎn)時(shí)其代表的值為[nk]。（如圖2所示）

3） 基數(shù)編碼值K既是重要的水印數(shù)據(jù)，又作為防篡改信息用于判定水印是否遭到攻擊。為了進(jìn)一步加強(qiáng)對(duì)K值的保護(hù)，采用AES模塊對(duì)PPCT樹及K值進(jìn)行加密處理并將密鑰妥善保管，使用AES模塊加密處理是為了使其具有防篡改的功能。

2.2 水印的嵌入

水印的嵌入：1）首先確定需要嵌入的水印數(shù)據(jù)值并構(gòu)造相應(yīng)的PPCT樹；2）在程序中嵌入創(chuàng)建PPCT水印的代碼，同時(shí)為了提高水印的隱蔽性，可將水印進(jìn)行分解，將不同的分支分別嵌入在程序中的不同位置；3）對(duì)嵌入水印后的代碼及基數(shù)編碼值K使用AES加密模塊進(jìn)行加密處理。

2.3 水印的提取

提取水印：1）計(jì)算實(shí)際的基數(shù)編碼值[K']；2）通過密鑰解密得到基數(shù)編碼值K，并將[K']與K的值進(jìn)行比較，若相等則說明版權(quán)得到驗(yàn)證；若不相等則說明水印遭到攻擊破壞，程序會(huì)立刻終止運(yùn)行；3）在提取水印的同時(shí)，隨機(jī)執(zhí)行驗(yàn)證代碼檢查程序是否發(fā)生可識(shí)別的攻擊并恢復(fù)PPCT樹結(jié)構(gòu).在水印中加入防篡改代碼后，當(dāng)嵌入水印后的程序遭到可識(shí)別的攻擊后，程序不會(huì)立即終止，而是轉(zhuǎn)而執(zhí)行隱藏其中的冗余代碼創(chuàng)建與原圖相同的水印圖，繼續(xù)提取水印以驗(yàn)證程序的版權(quán)。

3 水印的性能分析

3.1 數(shù)據(jù)率

數(shù)據(jù)率是指一個(gè)程序中可嵌入的最大水印信息量，是軟件水印系統(tǒng)的重要指標(biāo)。一個(gè)好的水印方案必須滿足在較少的節(jié)點(diǎn)中嵌入較多的水印數(shù)據(jù)，同時(shí)還要保證嵌入水印的隱蔽性與安全性，根據(jù)計(jì)算得到K基數(shù)編碼、排列圖編碼、PPCT編碼、PPCT混合編碼及改進(jìn)后的PPCT混合編碼方案的數(shù)據(jù)率如下表所示：

從表1中可見，PPCT的數(shù)據(jù)率偏低，K基數(shù)編碼的數(shù)據(jù)率強(qiáng)于其他水印方案，PPCT混合編碼方案相對(duì)于PPCT編碼數(shù)據(jù)率有較大提升，改進(jìn)后的PPCT混合編碼方案相比于原混合方案在數(shù)據(jù)率上略有提升，但仍低于K基數(shù)編碼方案。四種水印方案的數(shù)據(jù)率對(duì)比圖如圖3所示：

3.2 隱蔽性

隱蔽性是用來衡量嵌入到程序中的水印信息被攻擊者發(fā)現(xiàn)和和定位的難易程度?；诖耍墨I(xiàn)[5]提出了一個(gè)用水印信息與其周圍代碼及未嵌入水印的程序的特征值來表示水印的隱蔽性，特征值計(jì)算公式為：[d=i=0k（ni-mi）2]，其中{[ni]}為嵌入水印后的程序各個(gè)字節(jié)碼指令所占的百分比，{[mi]}為一般程序各種字節(jié)碼指令所占的百分比，特征值越小表示水印的隱蔽性越強(qiáng)。通過計(jì)算得到的4種算法的特征值如表2所示：

PPCT樹的結(jié)構(gòu)類似于線索二叉樹，雖采用混合編碼的方式提高了水印的數(shù)據(jù)率，但并未改變或破壞PPCT樹的結(jié)構(gòu)，因此PPCT本身仍然具有較高的隱蔽性，從表中的數(shù)據(jù)也可知，PPCT的隱蔽性要略好與其他方案。

3.3 抗攻擊性

抗攻擊性是水印性能指標(biāo)中的重要一項(xiàng)，它是指水印抵抗攻擊能力，在不計(jì)代價(jià)的條件下，理論上任何一種水印方案都是可以被破解的，對(duì)一種水印方案而言，只需其破解所需付出的代價(jià)要大于其破解所獲得的利益，那么便可說這種水印方案的抗攻擊性達(dá)到了要求[6]。下面從四個(gè)方面來介紹本水印方案的抗攻擊性：

1） 添加或刪除攻擊。它是指攻擊者對(duì)程序中的語句進(jìn)行簡(jiǎn)單的添加或刪除，由于在本水印方案中加入了防篡改方法，當(dāng)攻擊者對(duì)代碼進(jìn)行添加或刪除后，程序運(yùn)行時(shí)防篡改代碼會(huì)進(jìn)行檢測(cè)，當(dāng)發(fā)現(xiàn)代碼被篡改后，會(huì)生成一個(gè)新的與原來相同的PPCT樹結(jié)構(gòu)來繼續(xù)完成水印的提取。若不能夠生成新的PPCT樹結(jié)構(gòu)，程序會(huì)立即停止運(yùn)行。

2） 扭曲攻擊。它是指在攻擊者在找到水印嵌入的位置后，對(duì)嵌入水印的代碼進(jìn)行變換，如更改語序、改變表達(dá)式順序以及更改條件規(guī)則等方法，以達(dá)到破壞水印提取的目的。這時(shí)防篡改代碼同樣會(huì)進(jìn)行修復(fù)，因此該方法對(duì)水印的破壞力有限。

3） 代碼優(yōu)化攻擊。該方案是攻擊者同樣在找到了水印的嵌入位置后，采用代碼優(yōu)化的方法將嵌入水印的冗余代碼刪除掉，達(dá)到破壞水印的目的。此種方法可能會(huì)刪掉防篡改代碼，使得水印無法修復(fù)。但在該水印方案中水印代碼被拆分并嵌入到程序的不同區(qū)域，防篡改代碼被刪除的幾率很低。

4） 語義保持攻擊。它是指采用代碼迷亂技術(shù)對(duì)程序進(jìn)行攻擊，在不改變程序的功能和特性的前提下打亂原程序的結(jié)構(gòu)。對(duì)于本水印方案而言，打亂程序結(jié)構(gòu)不會(huì)對(duì)水印造成影響，因?yàn)樗∈墙?jīng)過拆分后嵌入到水印的不同區(qū)域中，單純的打亂結(jié)構(gòu)對(duì)水印功能不會(huì)有影響。

4 結(jié)束語

水印的各種性能指標(biāo)之間是相互約束的，通常是一項(xiàng)指標(biāo)的增強(qiáng)往往意味著另外其他性能指標(biāo)的降低。軟件水印方案的構(gòu)造需要在其中尋找一個(gè)平衡點(diǎn)，使得各種性能指標(biāo)都能夠處于一個(gè)較高的水平。同時(shí)軟件水印的發(fā)展仍處于起步階段，其理論體系尚需不斷完善。本文對(duì)基于PPCT編碼的混合水印方案進(jìn)行了改進(jìn)，通過實(shí)驗(yàn)證明，在不影響PPCT編碼原有的較好抗攻擊性的前提下提高了水印的數(shù)據(jù)率，但仍低于K基數(shù)編碼，而且由于水印中指針的大量增加，必定會(huì)對(duì)程序的運(yùn)行造成一定的影響，因此該水印方案仍有進(jìn)一步改進(jìn)的空間，這也是下一步工作的方向。

參考文獻(xiàn)：

[1] 張立和，楊義先，鈕心忻，等.軟件水印綜述[J].軟件學(xué)報(bào)，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和基數(shù)K的動(dòng)態(tài)圖混合編碼方案[J].計(jì)算機(jī)工程與應(yīng)用.2010，46（25）：109-111.

[4] 周亮.軟件水印算法評(píng)估研究[D].長(zhǎng)春：吉林大學(xué)，2010.

[5] 蔣華，沙宗魯，軒愛成.基于表達(dá)式逆序數(shù)的軟件水印算法[J]. 計(jì)算機(jī)應(yīng)用，2009，9（6）：3189-3190.

[6] 湯戰(zhàn)勇，房鼎益，蘇琳.一種基于代碼加密的防篡改軟件水印方案[J].中國(guó)科學(xué)技術(shù)大學(xué)學(xué)報(bào)，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動(dòng)態(tài)圖編碼的軟件指紋方案[J].電腦與信息技術(shù)，2006，14（2）：38-40.