一種改進(jìn)的動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)軟件水印編碼方案

1、一種改進(jìn)的動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)軟件水印編碼方案李 婧 時(shí)間:2008年07月08日 字 體: 大 中 小關(guān)鍵詞:? 摘?要：關(guān)鍵詞： 軟件水印? 水印編碼? K基數(shù)循環(huán)鏈表? 改進(jìn)的PPCT? 數(shù)據(jù)率? 軟件水印(Software Watermarking)作為一項(xiàng)新興的軟件保護(hù)技術(shù)在版權(quán)保護(hù)及軟件防破解方面具有獨(dú)特的優(yōu)勢。Collberg和Thomborson提出了一種相對(duì)高級(jí)的動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)軟件水印(Dynamic Data Structure Software Watermarking)技術(shù)，這種動(dòng)態(tài)水印在隱蔽性和魯棒性方面較通常的靜態(tài)軟件水印有明顯的提高。對(duì)于一個(gè)動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)軟件水印系統(tǒng)來說，水

2、印結(jié)構(gòu)的編碼方式尤為重要。Collberg和Thomborson在參考文獻(xiàn)2中介紹了兩種水印編碼方案，其中分別引入了兩種水印拓?fù)浣Y(jié)構(gòu)：“K基數(shù)循環(huán)鏈表結(jié)構(gòu)” 和“PPCT（Planted Plane Cubic Tree）結(jié)構(gòu)”。這兩種水印結(jié)構(gòu)各有優(yōu)缺點(diǎn)，前者易于實(shí)現(xiàn)并且充分利用了節(jié)點(diǎn)的每一個(gè)指針域，但水印信息的表示結(jié)構(gòu)單一；后者對(duì)于同一個(gè)水印信息可以有多種表示結(jié)構(gòu)，有利于生成水印庫，但對(duì)于葉節(jié)點(diǎn)的右指針卻沒有充分利用。? 本文在結(jié)合了這兩種水印結(jié)構(gòu)各自的優(yōu)點(diǎn)的同時(shí)，摒棄了它們結(jié)構(gòu)上的不足，對(duì)PPCT水印編碼方式進(jìn)行了改進(jìn)，引進(jìn)了一種新的動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)軟件水印編碼方式。理論和實(shí)踐證明，改進(jìn)后的編

3、碼方案相對(duì)于改進(jìn)前具有較好的性質(zhì)。1 動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)軟件水印技術(shù)1.1 理論基礎(chǔ)? 動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)水印技術(shù)是指在程序運(yùn)行時(shí)動(dòng)態(tài)地生成水印，并將水印信息轉(zhuǎn)化成某種拓?fù)浣Y(jié)構(gòu)隱藏在軟件代碼中，由于這種特殊的數(shù)據(jù)結(jié)構(gòu)包含許多指針并且是在運(yùn)行時(shí)動(dòng)態(tài)生成，而指針的具體值在每次運(yùn)行時(shí)都是不同的，所以相對(duì)于通常的靜態(tài)水印來說，給攻擊者帶來的攻擊難度更大。? 根據(jù)數(shù)論中的大數(shù)分解難的問題，可選擇一個(gè)代表版權(quán)信息的大自然數(shù)N作為水印數(shù)，并將此大數(shù)N轉(zhuǎn)化成某種數(shù)據(jù)結(jié)構(gòu)后嵌入到軟件程序代碼里，由于此大數(shù)能夠分解為兩個(gè)足夠大素?cái)?shù)P和Q的乘積，只有合法用戶才能檢測到N并將其分解為P和Q，從而可證明該用戶的合法身份。動(dòng)態(tài)數(shù)據(jù)結(jié)

4、構(gòu)水印的嵌入是指在運(yùn)行時(shí)將一個(gè)代表版權(quán)信息的大數(shù)表示成圖拓?fù)浣Y(jié)構(gòu)并嵌入到宿主程序中，其過程具體描述為：? 步驟1：選取一個(gè)合適的水印數(shù)N。? 步驟2：將N表示成某種圖拓?fù)浣Y(jié)構(gòu)G。? 步驟3：在運(yùn)行時(shí)創(chuàng)建生成圖拓?fù)浣Y(jié)構(gòu)G的水印代碼。? 步驟4：將此水印代碼嵌入到宿主程序中。? 其中，步驟2和3稱為水印編碼過程，它在一個(gè)動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)軟件水印系統(tǒng)中通常起著舉足輕重的作用。1.2 水印編碼? Collberg和Thomborson在參考文獻(xiàn)3中曾描述了兩種動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)軟件水印方案，它們分別是基于K基數(shù)循環(huán)鏈表和PPCT的水印編碼結(jié)構(gòu)。? 這種水印結(jié)構(gòu)是一個(gè)首尾相連的循環(huán)雙指針鏈表，如圖1所示。該鏈表中

5、每個(gè)節(jié)點(diǎn)有兩個(gè)指針，后一個(gè)指針指向下一個(gè)節(jié)點(diǎn)，另外一個(gè)指針用來編碼水印信息，其取值為：從這個(gè)指針指向的節(jié)點(diǎn)返回原節(jié)點(diǎn)所需要經(jīng)過的節(jié)點(diǎn)數(shù)。也就是說，空指針表示0，指向自身的指針表示1，指向下一個(gè)節(jié)點(diǎn)的指針表示2，以此類推。并且為了在提取時(shí)便于定位水印，特意在鏈表首節(jié)點(diǎn)前添加了一個(gè)稱之為Head的頭節(jié)點(diǎn)，它的右指針指向首節(jié)點(diǎn)，左指針為空。? 對(duì)于十進(jìn)制的水印數(shù)N，可以將其K進(jìn)制分解為：例如，水印數(shù)N=4 453，其質(zhì)因子為R1=61，R2=73?？梢詫⒋耸M(jìn)制水印數(shù)分解為六進(jìn)制數(shù)：N=445310=364+263+362+461+160=32 3416? 這種水印結(jié)構(gòu)由PPCT樹演化而來。PPCT

6、樹是一種具有良好性質(zhì)的拓?fù)浣Y(jié)構(gòu)，從形式上看，它是一個(gè)特殊的二叉樹，如圖2(a)所示。對(duì)這種特殊的二叉樹稍作改進(jìn)就可生成一種能用以表示動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)軟件水印的PPCT水印編碼結(jié)構(gòu)，如圖2(b)所示。? PPCT水印編碼結(jié)構(gòu)具有以下一些特征，使之可以作為一個(gè)具有良好抗攻擊性的軟件水印載體，用以表示水印數(shù)。? (1)有一個(gè)頭節(jié)點(diǎn)，該節(jié)點(diǎn)的左指針指向這個(gè)樹的右下節(jié)點(diǎn)，右指針指向樹的根節(jié)點(diǎn)。? (2)每個(gè)節(jié)點(diǎn)具有左、右兩個(gè)指針，非葉節(jié)點(diǎn)的這兩個(gè)指針分別指向自己的左、右子節(jié)點(diǎn)；葉節(jié)點(diǎn)的右指針指向自己，左指針的指向遵從下述規(guī)則：某非葉節(jié)點(diǎn)的右子樹的左下節(jié)點(diǎn)的左指針指向其左子樹的右下節(jié)點(diǎn)，整個(gè)樹的左下節(jié)點(diǎn)的左指

7、針指向Head節(jié)點(diǎn)。? (3)PPCT結(jié)構(gòu)是可以枚舉的。因此，可以利用PPCT結(jié)構(gòu)可枚舉的特點(diǎn)，使水印數(shù)與某種PPCT結(jié)構(gòu)在枚舉中的索引號(hào)相對(duì)應(yīng)，換句話說，給定了PPCT結(jié)構(gòu)節(jié)點(diǎn)數(shù)目M和合法的水印數(shù)N，就會(huì)有一個(gè)惟一的PPCT結(jié)構(gòu)來表示此水印信息。根據(jù)Catalan數(shù)理論4，具有m個(gè)葉節(jié)點(diǎn)(總共2m個(gè)節(jié)點(diǎn))的PPCT結(jié)構(gòu)共有其中C(m)為Catalan數(shù)，即具有m個(gè)葉節(jié)點(diǎn)的PPCT 結(jié)構(gòu)的數(shù)目。具有115個(gè)葉節(jié)點(diǎn)的PPCT結(jié)構(gòu)所具有的種類數(shù)目分別為：1、1、2、5、14、42、132、429、1 430、4 862、16 796、58 786、208 012、742 900、2 674 440

8、。2 改進(jìn)的PPCT結(jié)構(gòu)水印編碼方案? 圖3(a)給出一種具有四個(gè)葉節(jié)點(diǎn)的PPCT水印編碼結(jié)構(gòu)。由圖3(a)可以看出，所有葉子節(jié)點(diǎn)的右指針都指向自身，因此可以對(duì)葉子節(jié)點(diǎn)的右指針加以改進(jìn)，使其包含一定的信息。? 類似于K基數(shù)循環(huán)鏈表結(jié)構(gòu)，可以用這些葉節(jié)點(diǎn)的右指針來編碼水印信息。在K基數(shù)循環(huán)鏈表結(jié)構(gòu)中，水印數(shù)N可以用k-1個(gè)節(jié)點(diǎn)表示成以k為基數(shù)的表達(dá)式：其中，0eik。類似地，水印數(shù)N也可以用具有m個(gè)葉節(jié)點(diǎn)的改進(jìn)的結(jié)構(gòu)表示成以m+1為基數(shù)的表達(dá)式：系數(shù)ei的值可以用相應(yīng)葉節(jié)點(diǎn)的右指針?biāo)男畔肀硎荆唧w定義為：從相應(yīng)葉節(jié)點(diǎn)右指針指向的葉節(jié)點(diǎn)返回到原葉節(jié)點(diǎn)所需要經(jīng)過的葉節(jié)點(diǎn)的個(gè)數(shù)。換句話說，相應(yīng)

9、葉節(jié)點(diǎn)的右指針為空指針表示0，指向自身表示1，指向下一個(gè)葉節(jié)點(diǎn)則表示2，以此類推。圖3(b)給出了改進(jìn)后的PPCT結(jié)構(gòu)，此結(jié)構(gòu)表示水印數(shù)：? ? 由于這種改進(jìn)的PPCT結(jié)構(gòu)本身具有二叉樹和鏈表的雙重特點(diǎn)，在構(gòu)造軟件水印時(shí)，可以利用指針進(jìn)行樹的生成，根據(jù)現(xiàn)代操作系統(tǒng)中內(nèi)存管理的特點(diǎn)，指針的具體值在每次運(yùn)行時(shí)都是不同的，這就給攻擊者帶來極大的干擾。同時(shí)，對(duì)于具有m個(gè)葉節(jié)點(diǎn)的這種結(jié)構(gòu)，只要找到其中的一個(gè)節(jié)點(diǎn)，按其左指針就可以在m-1步內(nèi)找到Head節(jié)點(diǎn)，從而實(shí)現(xiàn)對(duì)整個(gè)圖拓?fù)浣Y(jié)構(gòu)的遍歷，這對(duì)于在內(nèi)存堆棧中定位水印圖拓?fù)浣Y(jié)構(gòu)很有幫助。同樣，在這種結(jié)構(gòu)中，某些節(jié)點(diǎn)的指針若被篡改，可以依據(jù)規(guī)則進(jìn)行有效的恢復(fù)

10、。? 對(duì)于一個(gè)動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)軟件水印系統(tǒng)而言，若采用改進(jìn)的PPCT結(jié)構(gòu)作為水印編碼方案，表示一個(gè)512比特（約為10155）的水印數(shù)，只需要81個(gè)葉節(jié)點(diǎn)，它相對(duì)于J.Palsberg方案5中采用的PPCT結(jié)構(gòu)表示法來說，降低了創(chuàng)建水印的空間復(fù)雜度以及水印的構(gòu)造時(shí)間；并且，由于這種結(jié)構(gòu)仍然保持了傳統(tǒng)的PPCT結(jié)構(gòu)的部分特征，對(duì)于m個(gè)葉節(jié)點(diǎn)，可以從個(gè)結(jié)構(gòu)中任意選擇一種作為水印的載體，這樣就可以形成一個(gè)足夠大的軟件水印庫，從而有利于抵抗針對(duì)水印的合謀攻擊（Collusive Attacks）。3 試驗(yàn)分析與比較3.1 性能過載比較? 對(duì)于不同的水印結(jié)構(gòu)，即使嵌入的水印節(jié)點(diǎn)數(shù)量相同，但由于它們結(jié)構(gòu)上的不

11、同，所帶來的空間過載也并不相同。根據(jù)表1中的空間過載量可以看出，在嵌入水印節(jié)點(diǎn)數(shù)相同的情況下，采用PPCT和改進(jìn)的PPCT結(jié)構(gòu)所帶來的空間過載量相當(dāng)。? 無論采用何種編碼結(jié)構(gòu)的水印，它們所帶來的空間過載量都相對(duì)比較穩(wěn)定，并不隨宿主程序的變換而發(fā)生變化。也就是說，在嵌入的水印信息量相同的情況下，宿主程序越大，水印系統(tǒng)所帶來的空間過載越不明顯。? 表1中數(shù)據(jù)顯示，對(duì)于動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)水印系統(tǒng)而言，嵌入節(jié)點(diǎn)數(shù)均為6的K基數(shù)循環(huán)鏈表結(jié)構(gòu)水印、PPCT結(jié)構(gòu)水印和改進(jìn)的PPCT結(jié)構(gòu)水印后，程序執(zhí)行時(shí)間分別比嵌入前平均上升了413.5%、123.6%和227.5%。? 由以上數(shù)據(jù)可以看出，對(duì)于動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)水印系

12、統(tǒng)，嵌入不同編碼結(jié)構(gòu)的水印所帶來的時(shí)間過載并不相同，其中采用K基數(shù)鏈表結(jié)構(gòu)時(shí)間過載最大，采用PPCT結(jié)構(gòu)時(shí)間過載最小，而采用改進(jìn)的結(jié)構(gòu)水印所帶來的時(shí)間過載介于二者之間。? 水印編碼結(jié)構(gòu)的選取對(duì)于動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)軟件水印系統(tǒng)來說至關(guān)重要，所選取的水印結(jié)構(gòu)不僅要求易于實(shí)現(xiàn)、在性能上帶來的過載小，而且最好具有較高的數(shù)據(jù)率，即能利用盡可能少的節(jié)點(diǎn)表示盡可能大的水印數(shù)。對(duì)K基數(shù)循環(huán)鏈表結(jié)構(gòu)、PPCT結(jié)構(gòu)以及改進(jìn)的PPCT結(jié)構(gòu)分別進(jìn)行了實(shí)現(xiàn)。根據(jù)軟件水印數(shù)據(jù)率的定義，可得這三種水印結(jié)構(gòu)的數(shù)據(jù)率分別為：? ? 式中，N為水印圖結(jié)構(gòu)中節(jié)點(diǎn)個(gè)數(shù)。? 從圖4中三種水印結(jié)構(gòu)的數(shù)據(jù)率曲線走勢可以看出，K基數(shù)循環(huán)鏈表水印編

13、碼結(jié)構(gòu)具有最高的數(shù)據(jù)率，改進(jìn)后的結(jié)構(gòu)次之，PPCT結(jié)構(gòu)的數(shù)據(jù)率最低。? 對(duì)于一個(gè)動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)軟件水印系統(tǒng)而言，一個(gè)優(yōu)良的水印編碼結(jié)構(gòu)應(yīng)該滿足：? (1)具有較高的數(shù)據(jù)率。? (2)結(jié)構(gòu)難于破解,易于實(shí)現(xiàn)，抗攻擊性強(qiáng)。? (3)對(duì)于同一個(gè)水印,最好有多種表示方法。? (4)水印的加載應(yīng)該盡可能少地帶來程序空間和時(shí)間上的過載。? 綜合上述分析可得出，所改進(jìn)的水印編碼結(jié)構(gòu)雖然數(shù)據(jù)率略低于K基數(shù)循環(huán)鏈表結(jié)構(gòu)，但由于自身結(jié)構(gòu)上的特點(diǎn)，其抗攻擊性要強(qiáng)于K基數(shù)循環(huán)鏈表結(jié)構(gòu)，所帶來的性能過載又比K基數(shù)鏈表結(jié)構(gòu)低，再加上它的數(shù)據(jù)率又比PPCT結(jié)構(gòu)要高，并且這種結(jié)構(gòu)可以生成一個(gè)有利于抵抗合謀攻擊的水印庫。因此，對(duì)

14、于一個(gè)動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)水印系統(tǒng)而言，采用所改進(jìn)的PPCT水印編碼結(jié)構(gòu)不失為一個(gè)良好的水印方案。參考文獻(xiàn)1 COLLBERG C， THOMBORSON J. Software watermarking: models and dynamic embeddingsC. In: Aiken A, et al., eds. Proceedings of the 26th Annual SIGPLAN-AIGACT Symposium on Principles of Programming Languages (POPL99), Association for Computing Machinery P

15、ress, 1999：311-324 .2 COLLBERG C， THOMBORSON J. Watermarking, tamperproofing, and obfuscation-tools for software protectionR.University of Arizona Technical Report 2000-0, Feb 2000.3 COLLBERG C,THOMBORSON J，TOWNSEND M. Dynamic graph-based software watermarkingR. University of Arizona Technical Report，TR04-08,April 28, 2004.4 GOULDEN I P,JA