張茂勝，孫小雁

(1.玉林師范學(xué)院數(shù)學(xué)與信息科學(xué)學(xué)院，廣西玉林537000;2.玉林師范學(xué)院計(jì)算機(jī)科學(xué)與工程學(xué)院，廣西玉林537000)

軟件水印是一種證明軟件版權(quán)歸屬的技術(shù)，可以對(duì)盜版軟件有破壞作用并且證明盜版行為，以維護(hù)版權(quán)所有者的權(quán)益［1－2］. COLLBERG 和THOMBORSON［3］提出了一種動(dòng)態(tài)圖的水印算法(CT 算法)，基本思想是在程序運(yùn)行過程中，由一個(gè)特殊的輸入序列激發(fā)程序執(zhí)行特定路徑下的水印代碼而生成水印圖.當(dāng)前，動(dòng)態(tài)圖的主要拓?fù)浣Y(jié)構(gòu)有3 種:排列圖、PPCT (Planted Plane Cubic Tree)和改進(jìn)的PPCT(IPPCT)［4］.文獻(xiàn)［5］－［7］提出軟件相似性分析技術(shù)，有效地促進(jìn)了軟件版權(quán)證明技術(shù)的發(fā)展.本文提出一種利用隨機(jī)數(shù)和哈希函數(shù)構(gòu)建PPCT 與排列圖混合結(jié)構(gòu)生成軟件水印. 將版權(quán)信息與隨機(jī)數(shù)相加，再計(jì)算兩者之和的哈希值，然后用PPCT 編碼，用PPCT 的葉節(jié)點(diǎn)以排列圖的方式編碼隨機(jī)數(shù)，最后生成拓?fù)鋱D嵌入軟件當(dāng)中.PPCT 與排列圖中任何一個(gè)正確提取即可證明版權(quán). 在水印受到攻擊的情況下，通過提取的水印拓?fù)鋱D，計(jì)算與版權(quán)所有者掌握的水印的相似度，為版權(quán)的歸屬提供證據(jù).

1 PPCT 與排列圖編碼

1.1 PPCT 編碼

PPCT 編碼的基本結(jié)構(gòu)是在二叉樹的基礎(chǔ)上加了一個(gè)右指針指向根節(jié)點(diǎn)的生成節(jié)點(diǎn)，二叉樹的所有葉節(jié)點(diǎn)和生成節(jié)點(diǎn)組成一個(gè)循環(huán)鏈表.根據(jù)Goulden 給出的定義，一個(gè)PPCT 有如下幾個(gè)特征［8］:

(1)有一個(gè)根結(jié)點(diǎn)，這個(gè)結(jié)點(diǎn)是不同于其他節(jié)點(diǎn)的單獨(dú)頂點(diǎn)，根的度為1;

(2)樹是平面的;

(3)每一個(gè)頂點(diǎn)的度為1 或者3.

生成結(jié)點(diǎn)的左指針指向最右葉結(jié)點(diǎn)，葉結(jié)點(diǎn)的左指針指向自己左邊最近的葉結(jié)點(diǎn)，右結(jié)點(diǎn)指向自己.最左邊葉結(jié)點(diǎn)的左指針指向生成節(jié)點(diǎn).所有結(jié)點(diǎn)通過指針鏈接在一起，構(gòu)成一個(gè)循環(huán)鏈表，這個(gè)特性使得PPCT 結(jié)構(gòu)容易定位，從任何一個(gè)結(jié)點(diǎn)出發(fā)，均可到達(dá)生成結(jié)點(diǎn). 一個(gè)具有3個(gè)葉結(jié)點(diǎn)的PPCT 如圖1 所示.

圖1 具有3個(gè)葉結(jié)點(diǎn)的PPCT 圖Figure 1 PPCT diagram with 3 leaf nodes

按照樹的大小比較結(jié)果對(duì)每種PPCT 編號(hào)，就可以將PPCT 與其可表示范圍內(nèi)的整數(shù)序列一一對(duì)應(yīng).根據(jù)Catalan 數(shù)列，具有n個(gè)葉子的不同的PPCT的數(shù)量為c(n)，計(jì)算公式如下:

由上式可知，PPCT 可以表示0 到c(n)－1 內(nèi)的任意整數(shù).

1.2 排列圖編碼

排列圖編碼的結(jié)構(gòu)是由一個(gè)指針和一個(gè)循環(huán)鏈表組成，左指針的編碼方式是由循環(huán)鏈表的節(jié)點(diǎn)序號(hào)所對(duì)應(yīng)的某個(gè)自然數(shù)序列的全排列決定的. 簡(jiǎn)單地說(shuō)，就是用數(shù)字0，1，2，…，n－1 的一個(gè)排列的序號(hào)來(lái)表示一個(gè)整數(shù)，然后用一個(gè)循環(huán)鏈表來(lái)編碼該整數(shù).如1，2，3，4，5 的排列＜1，2，3，4，5 ＞對(duì)應(yīng)整數(shù)0，＜1，2，3，5，4 ＞對(duì)應(yīng)整數(shù)1，＜5，4，3，2，1 ＞對(duì)應(yīng)整數(shù)119.在排列＜4，5，3，1，2 ＞的排列圖中，循環(huán)鏈表的1 號(hào)節(jié)點(diǎn)的左指針指向4 號(hào)節(jié)點(diǎn)，2 號(hào)節(jié)點(diǎn)左指針指向5 號(hào)節(jié)點(diǎn)，以此類推，可得排列圖(圖2).

圖2 整數(shù)29 的排列圖(節(jié)點(diǎn)數(shù)為5)Figure 2 Permutation diagram which represents 29 (the number of nodes is 5)

由排列圖編碼的原理可知，節(jié)點(diǎn)數(shù)為n 的排列圖編碼能表示的整數(shù)范圍為0～n!－1.

2 利用隨機(jī)數(shù)創(chuàng)建可重構(gòu)軟件水印

2.1 現(xiàn)有動(dòng)態(tài)圖水印算法的不足

PPCT 被認(rèn)為是魯棒性最強(qiáng)的算法，然而，為了安全性，算法中使用的大整數(shù)應(yīng)該在150 位以上，而表示150 位整數(shù)至少需要260個(gè)節(jié)點(diǎn)，可見為了增強(qiáng)安全性，需要大幅增加節(jié)點(diǎn)的數(shù)量，節(jié)點(diǎn)數(shù)量的增加導(dǎo)致指針數(shù)量大幅增加，即增加了內(nèi)存開銷，又降低了水印的隱蔽性［9－10］.排列圖編碼的表示范圍較大，但其抗攻擊能力較差. 為提高魯棒性，兼顧高效率，有些學(xué)者提出將PPCT 與排列圖相結(jié)合的方法.然而PPCT 與排列圖所表示的水印數(shù)字的數(shù)量級(jí)上差異很大，兩者運(yùn)算時(shí)，較小的數(shù)值有可能被當(dāng)作誤差而損失掉. 本文設(shè)計(jì)一種利用隨機(jī)數(shù)結(jié)合PPCT與排列圖的可重構(gòu)軟件水印算法，既能完美地解決兩者的運(yùn)算問題，又可顯著提高抗攻擊性能.

2.2 可重構(gòu)的排列圖與PPCT 混合編碼方案

水印使用的數(shù)據(jù)由兩部分組成:版權(quán)信息N1，與N1等長(zhǎng)的隨機(jī)數(shù)N2，假設(shè)N1是2個(gè)大素?cái)?shù)的乘積:

從安全性的角度，要求N1和N2盡可能地大，最好在1024 位以上.在獲得N1和N2后，作以下運(yùn)算:

在完成對(duì)N1和N2的處理后，將整數(shù)N0用PPCT 編碼，將葉節(jié)點(diǎn)的右指針指向右側(cè)下一個(gè)葉節(jié)點(diǎn)，左指針留空.按排列圖的方式利用PPCT 的葉結(jié)點(diǎn)的某一個(gè)排列表示隨機(jī)N2，將PPCT 的葉節(jié)點(diǎn)的左指針指向排列圖所對(duì)應(yīng)的下一個(gè)葉節(jié)點(diǎn).

假設(shè)葉結(jié)點(diǎn)個(gè)數(shù)為n，則n 需滿足的條件為:

根據(jù)Hash 函數(shù)的運(yùn)算結(jié)果，N0比N2小得多，因此很容易求出滿足上式的最小的n.

圖3 是運(yùn)行混合編碼的圖示，圖中PPCT 表示整數(shù)7，排列圖表示整數(shù)29.

圖3 混合編碼圖Figure 3 Hybrid coding diagram

編碼結(jié)束后，將N0與N2連加，作為軟件水印結(jié)果.定義連加運(yùn)算如定義1 所示.

定義1 設(shè)X1、X2分別為已知數(shù)值，定義X1與X2的連加運(yùn)算為:

其中DIG(X)表示十進(jìn)制整數(shù)X 的位數(shù).

圖3 所示的水印編碼圖的水印信息為729. 編碼圖中，除葉結(jié)點(diǎn)外，其余節(jié)點(diǎn)與PPCT 相同. 在葉結(jié)點(diǎn)中，增加左指針指向排列的下一個(gè)節(jié)點(diǎn)，最左側(cè)葉節(jié)點(diǎn)入度為2、出度為3，最右側(cè)葉節(jié)點(diǎn)入度為4、出度為1，其余葉節(jié)點(diǎn)入度為3、出度為2，即用于排列圖編碼的葉節(jié)點(diǎn)度為5，PPCT 的非葉節(jié)點(diǎn)的度為3，根據(jù)節(jié)點(diǎn)的度，在提取水印圖時(shí)很容易先提取排列圖，然后再提取PPCT.

3 性能分析與仿真實(shí)驗(yàn)

3.1 信息隱藏量

首先使用Hash 函數(shù)將版權(quán)信息進(jìn)行了處理，因此，無(wú)論版權(quán)信息的長(zhǎng)度是多少，通過Hash 函數(shù)運(yùn)算后將版權(quán)信息映射成哈希值，從而使真正嵌入到程序中的水印信息的數(shù)值并不會(huì)很大. 而且算法可以輕易地?cái)U(kuò)展成具有更大數(shù)值范圍的信息隱藏量，只需版權(quán)信息進(jìn)行分段計(jì)算Hash 函數(shù)，并將每段的結(jié)果作連加運(yùn)算即可，然后將連加的結(jié)果用PPCT 表示.總之，本算法對(duì)信息隱藏量的控制十分靈活，可以將任何長(zhǎng)度的版權(quán)信息轉(zhuǎn)變成任意長(zhǎng)度的水印信息.

3.2 魯棒性

將水印信息經(jīng)過與隨機(jī)數(shù)相加后再用Hash 函數(shù)進(jìn)行變換，將真實(shí)水印信息進(jìn)行隱藏，目的是減少水印圖與真實(shí)水印信息的相關(guān)性，確保任何未授權(quán)個(gè)體，即使在提取到水印圖的情況下，依然無(wú)法得到真實(shí)的水印信息，可起到防止他人假冒合法生產(chǎn)者偽造水印圖的作用.同時(shí)，為了保證水印所有者能順利提取，在不增加結(jié)點(diǎn)數(shù)量情況下將PPCT 與排列圖結(jié)合，利用PPCT 的葉結(jié)點(diǎn)構(gòu)造隨機(jī)數(shù)N2(N2也不含真實(shí)的水印信息)的排列圖，無(wú)論攻擊者提取到完整的水印圖，還是PPCT、排列圖兩者之一，對(duì)攻擊者而言都沒有任何作用.

對(duì)版權(quán)所有者而言，當(dāng)出現(xiàn)版權(quán)糾紛的時(shí)候，若水印未被破壞，則可證明版權(quán). 若水印被部分破壞，則通過提取排列圖還原出隨機(jī)數(shù)，或出具自己保存的隨機(jī)數(shù)還原出排列圖，起到證明版權(quán)的作用. 同時(shí)，由隨機(jī)數(shù)N2與版權(quán)信息N1作相加再求Hash 函數(shù)值，可重構(gòu)PPCT，根據(jù)重構(gòu)的PPCT 與軟件中提取的PPCT 進(jìn)行對(duì)比，若相同則可證明版權(quán). 即使PPCT 受到攻擊，在PPCT 沒有被完全破壞的情況下，根據(jù)重構(gòu)的水印拓?fù)鋱D與提取的拓?fù)鋱D相似度，也可起到證明版權(quán)的作用.

下面給出水印相似度定義.

將水印信息w 嵌入宿主程序p 后，可能會(huì)因某些原因?qū)е滤⊥負(fù)鋱D發(fā)生改變，導(dǎo)致提取的水印信息與嵌入的水印信息不相等. 記符號(hào)Pw_Points為水印程序中的指針數(shù)量，P_Points 為宿主程序中的指針數(shù)量，Con_Points 為水印程序和宿主程序共有的指針數(shù)量.分別定義水印相似度PwSim 和宿主指針相似度PSim:

根據(jù)哈希函數(shù)的特點(diǎn)，輸入值的改變會(huì)導(dǎo)致哈希值發(fā)生巨大變化，從而其PPCT 拓?fù)鋱D也會(huì)發(fā)生很大的變化.隨機(jī)數(shù)具有很強(qiáng)的安全性，任何人不可能同時(shí)產(chǎn)生出相同的隨機(jī)數(shù)，這一特性會(huì)反應(yīng)到拓?fù)鋱D上，即任何人不可能有意識(shí)地再次產(chǎn)生同樣的拓?fù)鋱D.對(duì)于葉節(jié)點(diǎn)的不同排列也會(huì)導(dǎo)致指針信息的巨大差異，基于這些性質(zhì)，可以得出一個(gè)結(jié)論:如果版權(quán)所有者重構(gòu)的拓?fù)鋱D與軟件中提取的拓?fù)鋱D在結(jié)構(gòu)上“十分”相似，即水印相似度很高，也可以證明版權(quán).

為了對(duì)混合水印編碼方案的魯棒性有更客觀的評(píng)價(jià)，在window 環(huán)境下(windosXPSP2，CPU1.86G，內(nèi)存1G)，利用Visual C++6.0 實(shí)現(xiàn)了仿真實(shí)驗(yàn)，對(duì)水印嵌入和提取前后、水印攻擊前后的運(yùn)行情況作進(jìn)一步的試驗(yàn)分析.源程序是一個(gè)小型計(jì)算器程序，對(duì)水印信息和隨機(jī)數(shù)以及哈希函數(shù)均作了簡(jiǎn)化運(yùn)算.

在仿真程序中，插入源程序的水印是233252，其中PPCT 表示233，排列圖表示隨機(jī)數(shù)252. 對(duì)水印拓?fù)鋱D同時(shí)進(jìn)行刪除一個(gè)指針、附加一個(gè)指針、修改一個(gè)指針等攻擊后提取的水印數(shù)字為286261，提取的結(jié)果與正確水印信息有很大的差別. 但是版權(quán)所有者依據(jù)所掌握的隨機(jī)數(shù)，重構(gòu)出排列圖和PPCT，然后與提取的拓?fù)鋱D進(jìn)行比較，分別計(jì)算水印指針相似度PwSim 和宿主指針相似度PSim:

雖然水印信息發(fā)生巨大改變，但水印拓?fù)鋱D相似度分別高達(dá)85.71%和92.31%，根據(jù)隨機(jī)數(shù)和哈希函數(shù)的特性，完全可以證明版權(quán)的歸屬.甚至還可以進(jìn)一步分別計(jì)算PPCT 指針相似度和排列圖指針相似度，提高版權(quán)證明的說(shuō)服力.

3.3 水印的執(zhí)行效率與隱蔽性

由于動(dòng)態(tài)水印圖中既有PPCT 編碼，又有排列圖編碼，所以指針數(shù)量比單純使用PPCT 或排列圖要多，對(duì)水印的隱蔽性和編碼效率會(huì)有影響. 為了體現(xiàn)出在水印嵌入前后運(yùn)行時(shí)間上的差異，將源程序和嵌入水印后的程序各運(yùn)算10 000 次，并且每個(gè)程序運(yùn)行5 次，記錄其運(yùn)行時(shí)間，如表1 所示.從總體上看，嵌入水印后，程序的執(zhí)行效率略微有所降低.

表1 程序運(yùn)行時(shí)間對(duì)比Table 1 Comparison of running time ms

以上結(jié)果表明，采用該算法嵌入混合水印后對(duì)源程序的可用性沒有影響，而且該算法對(duì)常見的攻擊有較強(qiáng)的魯棒性. 在同時(shí)受到刪除、修改、增加的攻擊的情況下，仍然能有力地證明版權(quán).

4 結(jié)束語(yǔ)

利用隨機(jī)數(shù)創(chuàng)建可重構(gòu)的混合軟件水印方案充分利用了PPCT 的抗攻擊性能和排列圖的編碼效率的優(yōu)勢(shì)，預(yù)處理后隱藏真實(shí)的版權(quán)信息，既可以防止第三方偽造版權(quán)所有者的產(chǎn)品，又可以防止排列圖數(shù)值超出PPCT 葉結(jié)點(diǎn)的表示范圍. 連加運(yùn)算的設(shè)計(jì)有效克服了2個(gè)不在同一數(shù)量級(jí)上的數(shù)值相加致使較小值因精度原因丟失的現(xiàn)象. 兩者任意提取一個(gè)即可證明版權(quán)，即使PPCT 和排列圖均遭到破壞，根據(jù)指針信息的相似度，仍可以為版權(quán)所有者提供證據(jù)并在一定程度上證明版權(quán)的歸屬. 通過仿真實(shí)驗(yàn)?zāi)M水印被攻擊后再實(shí)施提取，計(jì)算水印相似度證明版權(quán)明顯增強(qiáng)水印的魯棒性.

［1］ZHU W. Informed recognition in software watermarking［M］. New York:Intelligence and Security Informatics，2007:257－261.

［2］FALCARIN P，COLLBERG C，ATALLAH M，et al.Guest editors'introduction:Software protection［J］. Software，IEEE，2011，28(2):24－27.

［3］COLLBERG C S，THOMBORSON C D. Software watermarking:Models and dynamic embeddings［C］∥Proceedings of the ACM SIGPLAN－SIGACT Symposium on Principles of Programming Languages－POPL.New York，NY，USA，1999:311－324.

［4］ZHU J Q，LIU Y H，YIN K X. A novel dynamic graph software watermark scheme［C］∥Proceedings of the 2009 First International Workshop on Education Technology and Computer Science. Washington，DC，USA，2009:775－780.

［5］金惠生，黃荔，王桂海. 軟件相似性分析方法的運(yùn)用［J］.華南師范大學(xué)學(xué)報(bào):自然科學(xué)版，1995(4):7－11.

［6］王桂海. 多層次的軟件相似性分析［J］. 華南師范大學(xué)學(xué)報(bào):自然科學(xué)版，1996(1):99－103.

［7］王桂海，羅蘇平. 軟件著作權(quán)的驗(yàn)證及軟件相似性判別案例［J］. 華南師范大學(xué)學(xué)報(bào):自然科學(xué)版，1995(4):1－6.

［8］PALSBERG J，KRISHNASWAMY S，KWON M，et al. Experience with software watermarking［C］∥Proceedings of the Computer Security Applications，2000 ACSAC'00 16th Annual Conference. New Orleans，LA，2000:308－316.

［9］ZHU J Q，WANG A M，LIU Y H. Tamper－proofing software watermarking scheme based on constant encoding［C］∥Proceedings of the Education Technology and Computer Science (ETCS). Dunedin，New Zealand，2010:129－132.

［10］AGUZZI M，ALBANESI M，F(xiàn)ERRETTI M. A novel watermarking algorithm for image authentication:Robustness against common attacks and JPEG2000 compression［J］.Image Analysis and Processing－ ICIAP，2005，3617:559－567.