??? 摘?要： 在經典的K基數循環鏈表" title="鏈表">鏈表結構和PPCT結構水印編碼" title="水印編碼">水印編碼方式的基礎上，提出了一種新的動態數據結構" title="數據結構">數據結構軟件水印" title="軟件水印">軟件水印編碼方案。理論和實驗證明,該方案中采用改進的PPCT水印編碼結構在多種評價指標上都具有一定的優勢，是一個優良的動態軟件水印編碼方案。
??? 關鍵詞： 軟件水印? 水印編碼? K基數循環鏈表? 改進的PPCT? 數據率

?

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

?

?

??? 對于十進制的水印數N，可以將其K進制分解為：例如，水印數N=4 453，其質因子為R₁=61，R₂=73。可以將此十進制水印數分解為六進制數：N=4453₁₀=3×6⁴+2×6³+3×6²+4×6¹+1×6⁰=32 3416
1.2.2 PPCT水印編碼結構

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

?

?

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

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

???

?

?

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

?

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

???

??? 式中，N為水印圖結構中節點個數。
??? 從圖4中三種水印結構的數據率曲線走勢可以看出，K基數循環鏈表水印編碼結構具有最高的數據率，改進后的結構次之，PPCT結構的數據率最低。

?

??? 對于一個動態數據結構軟件水印系統而言，一個優良的水印編碼結構應該滿足：
??? (1)具有較高的數據率。
??? (2)結構難于破解,易于實現，抗攻擊性強。
??? (3)對于同一個水印,最好有多種表示方法。
??? (4)水印的加載應該盡可能少地帶來程序空間和時間上的過載。
??? 綜合上述分析可得出，所改進的水印編碼結構雖然數據率略低于K基數循環鏈表結構，但由于自身結構上的特點，其抗攻擊性要強于K基數循環鏈表結構，所帶來的性能過載又比K基數鏈表結構低，再加上它的數據率又比PPCT結構要高，并且這種結構可以生成一個有利于抵抗合謀攻擊的水印庫。因此，對于一個動態數據結構水印系統而言，采用所改進的PPCT水印編碼結構不失為一個良好的水印方案。
參考文獻
[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.