??? 摘?要： 在經(jīng)典的K基數(shù)循環(huán)鏈表" title="鏈表">鏈表結(jié)構(gòu)和PPCT結(jié)構(gòu)水印編碼" title="水印編碼">水印編碼方式的基礎(chǔ)上，提出了一種新的動態(tài)數(shù)據(jù)結(jié)構(gòu)" title="數(shù)據(jù)結(jié)構(gòu)">數(shù)據(jù)結(jié)構(gòu)軟件水印" title="軟件水印">軟件水印編碼方案。理論和實驗證明,該方案中采用改進的PPCT水印編碼結(jié)構(gòu)在多種評價指標上都具有一定的優(yōu)勢，是一個優(yōu)良的動態(tài)軟件水印編碼方案。
??? 關(guān)鍵詞： 軟件水印? 水印編碼? K基數(shù)循環(huán)鏈表? 改進的PPCT? 數(shù)據(jù)率

?

??? 軟件水印(Software Watermarking)作為一項新興的軟件保護技術(shù)在版權(quán)保護及軟件防破解方面具有獨特的優(yōu)勢。Collberg和Thomborson提出了一種相對高級的動態(tài)數(shù)據(jù)結(jié)構(gòu)軟件水印(Dynamic Data Structure Software Watermarking)技術(shù)，這種動態(tài)水印在隱蔽性和魯棒性方面較通常的靜態(tài)軟件水印有明顯的提高。對于一個動態(tài)數(shù)據(jù)結(jié)構(gòu)軟件水印系統(tǒng)來說，水印結(jié)構(gòu)的編碼方式尤為重要。Collberg和Thomborson在參考文獻[2]中介紹了兩種水印編碼方案，其中分別引入了兩種水印拓撲結(jié)構(gòu)：“K基數(shù)循環(huán)鏈表結(jié)構(gòu)” 和“PPCT（Planted Plane Cubic Tree）結(jié)構(gòu)”。這兩種水印結(jié)構(gòu)各有優(yōu)缺點，前者易于實現(xiàn)并且充分利用了節(jié)點的每一個指針域，但水印信息的表示結(jié)構(gòu)單一；后者對于同一個水印信息可以有多種表示結(jié)構(gòu)，有利于生成水印庫，但對于葉節(jié)點的右指針卻沒有充分利用。
??? 本文在結(jié)合了這兩種水印結(jié)構(gòu)各自的優(yōu)點的同時，摒棄了它們結(jié)構(gòu)上的不足，對PPCT水印編碼方式進行了改進，引進了一種新的動態(tài)數(shù)據(jù)結(jié)構(gòu)軟件水印編碼方式。理論和實踐證明，改進后的編碼方案相對于改進前具有較好的性質(zhì)。
1 動態(tài)數(shù)據(jù)結(jié)構(gòu)軟件水印技術(shù)
1.1 理論基礎(chǔ)
??? 動態(tài)數(shù)據(jù)結(jié)構(gòu)水印技術(shù)是指在程序運行時動態(tài)地生成水印，并將水印信息轉(zhuǎn)化成某種拓撲結(jié)構(gòu)隱藏在軟件代碼中，由于這種特殊的數(shù)據(jù)結(jié)構(gòu)包含許多指針并且是在運行時動態(tài)生成，而指針的具體值在每次運行時都是不同的，所以相對于通常的靜態(tài)水印來說，給攻擊者帶來的攻擊難度更大。
??? 根據(jù)數(shù)論中的大數(shù)分解難的問題，可選擇一個代表版權(quán)信息的大自然數(shù)N作為水印數(shù)，并將此大數(shù)N轉(zhuǎn)化成某種數(shù)據(jù)結(jié)構(gòu)后嵌入到軟件程序代碼里，由于此大數(shù)能夠分解為兩個足夠大素數(shù)P和Q的乘積，只有合法用戶才能檢測到N并將其分解為P和Q，從而可證明該用戶的合法身份。動態(tài)數(shù)據(jù)結(jié)構(gòu)水印的嵌入是指在運行時將一個代表版權(quán)信息的大數(shù)表示成圖拓撲結(jié)構(gòu)并嵌入到宿主程序中，其過程具體描述為：
??? 步驟1：選取一個合適的水印數(shù)N。
??? 步驟2：將N表示成某種圖拓撲結(jié)構(gòu)G。
??? 步驟3：在運行時創(chuàng)建生成圖拓撲結(jié)構(gòu)G的水印代碼。
??? 步驟4：將此水印代碼嵌入到宿主程序中。
??? 其中，步驟2和3稱為水印編碼過程，它在一個動態(tài)數(shù)據(jù)結(jié)構(gòu)軟件水印系統(tǒng)中通常起著舉足輕重的作用。
1.2 水印編碼
??? Collberg和Thomborson在參考文獻[3]中曾描述了兩種動態(tài)數(shù)據(jù)結(jié)構(gòu)軟件水印方案，它們分別是基于K基數(shù)循環(huán)鏈表和PPCT的水印編碼結(jié)構(gòu)。
1.2.1 K基數(shù)循環(huán)鏈表水印編碼結(jié)構(gòu)
??? 這種水印結(jié)構(gòu)是一個首尾相連的循環(huán)雙指針鏈表，如圖1所示。該鏈表中每個節(jié)點有兩個指針，后一個指針指向下一個節(jié)點，另外一個指針用來編碼水印信息，其取值為：從這個指針指向的節(jié)點返回原節(jié)點所需要經(jīng)過的節(jié)點數(shù)。也就是說，空指針表示0，指向自身的指針表示1，指向下一個節(jié)點的指針表示2，以此類推。并且為了在提取時便于定位水印，特意在鏈表首節(jié)點前添加了一個稱之為Head的頭節(jié)點，它的右指針指向首節(jié)點，左指針為空。

?

?

??? 對于十進制的水印數(shù)N，可以將其K進制分解為：例如，水印數(shù)N=4 453，其質(zhì)因子為R₁=61，R₂=73?？梢詫⒋耸M制水印數(shù)分解為六進制數(shù)：N=4453₁₀=3×6⁴+2×6³+3×6²+4×6¹+1×6⁰=32 3416
1.2.2 PPCT水印編碼結(jié)構(gòu)

??? 這種水印結(jié)構(gòu)由PPCT樹演化而來。PPCT樹是一種具有良好性質(zhì)的拓撲結(jié)構(gòu)，從形式上看，它是一個特殊的二叉樹，如圖2(a)所示。對這種特殊的二叉樹稍作改進就可生成一種能用以表示動態(tài)數(shù)據(jù)結(jié)構(gòu)軟件水印的PPCT水印編碼結(jié)構(gòu)，如圖2(b)所示。

?

?

??? PPCT水印編碼結(jié)構(gòu)具有以下一些特征，使之可以作為一個具有良好抗攻擊性的軟件水印載體，用以表示水印數(shù)。
??? (1)有一個頭節(jié)點，該節(jié)點的左指針指向這個樹的右下節(jié)點，右指針指向樹的根節(jié)點。
??? (2)每個節(jié)點具有左、右兩個指針，非葉節(jié)點的這兩個指針分別指向自己的左、右子節(jié)點；葉節(jié)點的右指針指向自己，左指針的指向遵從下述規(guī)則：某非葉節(jié)點的右子樹的左下節(jié)點的左指針指向其左子樹的右下節(jié)點，整個樹的左下節(jié)點的左指針指向Head節(jié)點。
??? (3)PPCT結(jié)構(gòu)是可以枚舉的。因此，可以利用PPCT結(jié)構(gòu)可枚舉的特點，使水印數(shù)與某種PPCT結(jié)構(gòu)在枚舉中的索引號相對應(yīng)，換句話說，給定了PPCT結(jié)構(gòu)節(jié)點數(shù)目M和合法的水印數(shù)N，就會有一個惟一的PPCT結(jié)構(gòu)來表示此水印信息。根據(jù)Catalan數(shù)理論^[4]，具有m個葉節(jié)點(總共2m個節(jié)點)的PPCT結(jié)構(gòu)共有其中C(m)為Catalan數(shù)，即具有m個葉節(jié)點的PPCT 結(jié)構(gòu)的數(shù)目。具有1～15個葉節(jié)點的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。
2 改進的PPCT結(jié)構(gòu)水印編碼方案
??? 圖3(a)給出一種具有四個葉節(jié)點的PPCT水印編碼結(jié)構(gòu)。由圖3(a)可以看出，所有葉子節(jié)點的右指針都指向自身，因此可以對葉子節(jié)點的右指針加以改進，使其包含一定的信息。

??? 類似于K基數(shù)循環(huán)鏈表結(jié)構(gòu)，可以用這些葉節(jié)點的右指針來編碼水印信息。在K基數(shù)循環(huán)鏈表結(jié)構(gòu)中，水印數(shù)N可以用k-1個節(jié)點表示成以k為基數(shù)的表達式：其中，0≤e_i系數(shù)e_i的值可以用相應(yīng)葉節(jié)點的右指針所包含的信息來表示，具體定義為：從相應(yīng)葉節(jié)點右指針指向的葉節(jié)點返回到原葉節(jié)點所需要經(jīng)過的葉節(jié)點的個數(shù)。換句話說，相應(yīng)葉節(jié)點的右指針為空指針表示0，指向自身表示1，指向下一個葉節(jié)點則表示2，以此類推。圖3(b)給出了改進后的PPCT結(jié)構(gòu)，此結(jié)構(gòu)表示水印數(shù)：

???

?

?

??? 由于這種改進的PPCT結(jié)構(gòu)本身具有二叉樹和鏈表的雙重特點，在構(gòu)造軟件水印時，可以利用指針進行樹的生成，根據(jù)現(xiàn)代操作系統(tǒng)中內(nèi)存管理的特點，指針的具體值在每次運行時都是不同的，這就給攻擊者帶來極大的干擾。同時，對于具有m個葉節(jié)點的這種結(jié)構(gòu)，只要找到其中的一個節(jié)點，按其左指針就可以在m-1步內(nèi)找到Head節(jié)點，從而實現(xiàn)對整個圖拓撲結(jié)構(gòu)的遍歷，這對于在內(nèi)存堆棧中定位水印圖拓撲結(jié)構(gòu)很有幫助。同樣，在這種結(jié)構(gòu)中，某些節(jié)點的指針若被篡改，可以依據(jù)規(guī)則進行有效的恢復(fù)。
??? 對于一個動態(tài)數(shù)據(jù)結(jié)構(gòu)軟件水印系統(tǒng)而言，若采用改進的PPCT結(jié)構(gòu)作為水印編碼方案，表示一個512比特（約為10¹⁵⁵）的水印數(shù)，只需要81個葉節(jié)點，它相對于J.Palsberg方案^[5]中采用的PPCT結(jié)構(gòu)表示法來說，降低了創(chuàng)建水印的空間復(fù)雜度以及水印的構(gòu)造時間；并且，由于這種結(jié)構(gòu)仍然保持了傳統(tǒng)的PPCT結(jié)構(gòu)的部分特征，對于m個葉節(jié)點，可以從個結(jié)構(gòu)中任意選擇一種作為水印的載體，這樣就可以形成一個足夠大的軟件水印庫，從而有利于抵抗針對水印的合謀攻擊（Collusive Attacks）。
3 試驗分析與比較
3.1 性能過載比較
??? 水印的嵌入改變了宿主程序的初始結(jié)構(gòu)，勢必會對程序的運行效率造成影響。因此有必要了解采用不同的水印編碼方案會對程序造成怎樣的影響。這里將從兩方面衡量這種影響：不同結(jié)構(gòu)水印的加載所帶來的空間上的過載和時間上的過載。
??? 筆者選擇了不同的測試用例進行性能測試，希望得到的一些結(jié)論，有助于輔助確定水印方案，尋求性能和安全的平衡點。
??? 測試環(huán)境：
??? ??? 硬件：PC機，Pentium 4 CPU(3GHz)，512MB RAM
??????? 軟件：Microsoft Windows XP，j2sdk1.4.2_01
3.1.1 空間過載分析
??? 對于不同的水印結(jié)構(gòu)，即使嵌入的水印節(jié)點數(shù)量相同，但由于它們結(jié)構(gòu)上的不同，所帶來的空間過載也并不相同。根據(jù)表1中的空間過載量可以看出，在嵌入水印節(jié)點數(shù)相同的情況下，采用PPCT和改進的PPCT結(jié)構(gòu)所帶來的空間過載量相當。

?

??? 無論采用何種編碼結(jié)構(gòu)的水印，它們所帶來的空間過載量都相對比較穩(wěn)定，并不隨宿主程序的變換而發(fā)生變化。也就是說，在嵌入的水印信息量相同的情況下，宿主程序越大，水印系統(tǒng)所帶來的空間過載越不明顯。
3.1.2 時間過載分析
??? 表1中數(shù)據(jù)顯示，對于動態(tài)數(shù)據(jù)結(jié)構(gòu)水印系統(tǒng)而言，嵌入節(jié)點數(shù)均為6的K基數(shù)循環(huán)鏈表結(jié)構(gòu)水印、PPCT結(jié)構(gòu)水印和改進的PPCT結(jié)構(gòu)水印后，程序執(zhí)行時間分別比嵌入前平均上升了413.5%、123.6%和227.5%。
??? 由以上數(shù)據(jù)可以看出，對于動態(tài)數(shù)據(jù)結(jié)構(gòu)水印系統(tǒng)，嵌入不同編碼結(jié)構(gòu)的水印所帶來的時間過載并不相同，其中采用K基數(shù)鏈表結(jié)構(gòu)時間過載最大，采用PPCT結(jié)構(gòu)時間過載最小，而采用改進的結(jié)構(gòu)水印所帶來的時間過載介于二者之間。
3.2 數(shù)據(jù)率" title="數(shù)據(jù)率">數(shù)據(jù)率比較
??? 水印編碼結(jié)構(gòu)的選取對于動態(tài)數(shù)據(jù)結(jié)構(gòu)軟件水印系統(tǒng)來說至關(guān)重要，所選取的水印結(jié)構(gòu)不僅要求易于實現(xiàn)、在性能上帶來的過載小，而且最好具有較高的數(shù)據(jù)率，即能利用盡可能少的節(jié)點表示盡可能大的水印數(shù)。對K基數(shù)循環(huán)鏈表結(jié)構(gòu)、PPCT結(jié)構(gòu)以及改進的PPCT結(jié)構(gòu)分別進行了實現(xiàn)。根據(jù)軟件水印數(shù)據(jù)率的定義，可得這三種水印結(jié)構(gòu)的數(shù)據(jù)率分別為：

???

??? 式中，N為水印圖結(jié)構(gòu)中節(jié)點個數(shù)。
??? 從圖4中三種水印結(jié)構(gòu)的數(shù)據(jù)率曲線走勢可以看出，K基數(shù)循環(huán)鏈表水印編碼結(jié)構(gòu)具有最高的數(shù)據(jù)率，改進后的結(jié)構(gòu)次之，PPCT結(jié)構(gòu)的數(shù)據(jù)率最低。

?

??? 對于一個動態(tài)數(shù)據(jù)結(jié)構(gòu)軟件水印系統(tǒng)而言，一個優(yōu)良的水印編碼結(jié)構(gòu)應(yīng)該滿足：
??? (1)具有較高的數(shù)據(jù)率。
??? (2)結(jié)構(gòu)難于破解,易于實現(xiàn)，抗攻擊性強。
??? (3)對于同一個水印,最好有多種表示方法。
??? (4)水印的加載應(yīng)該盡可能少地帶來程序空間和時間上的過載。
??? 綜合上述分析可得出，所改進的水印編碼結(jié)構(gòu)雖然數(shù)據(jù)率略低于K基數(shù)循環(huán)鏈表結(jié)構(gòu)，但由于自身結(jié)構(gòu)上的特點，其抗攻擊性要強于K基數(shù)循環(huán)鏈表結(jié)構(gòu)，所帶來的性能過載又比K基數(shù)鏈表結(jié)構(gòu)低，再加上它的數(shù)據(jù)率又比PPCT結(jié)構(gòu)要高，并且這種結(jié)構(gòu)可以生成一個有利于抵抗合謀攻擊的水印庫。因此，對于一個動態(tài)數(shù)據(jù)結(jié)構(gòu)水印系統(tǒng)而言，采用所改進的PPCT水印編碼結(jié)構(gòu)不失為一個良好的水印方案。
參考文獻
[1] COLLBERG C， THOMBORSON J. Software watermarking: models and dynamic embeddings[C]. In: Aiken A, et al., eds. Proceedings of the 26th Annual SIGPLAN-AIGACT Symposium on Principles of Programming Languages (POPL’99), Association for Computing Machinery Press, 1999：311-324 .
[2] COLLBERG C， THOMBORSON J. Watermarking, tamperproofing, and obfuscation-tools for software protection[R].University of Arizona Technical Report 2000-0, Feb 2000.
[3] COLLBERG C,THOMBORSON J，TOWNSEND M. Dynamic graph-based software watermarking[R]. University of Arizona Technical Report，TR04-08,April 28, 2004.
[4] GOULDEN I P,JACKSON D M. Combinatorial enumeration[R]. NewYork: Wiliy,1983.
[5] PALSBERG J, KRISHNASWAMY S, KWON M, et al.Experience with software watermarking[C]. In Proceedings of ACSAC’00, 16th Annual Computer Security Applications Conference, 2000:308-316.