基于動態(tài)圖的軟件水印算法

雷 敏，楊 榆，胡若翔，譚逢亮

(1.北京郵電大學(xué)信息安全中心，北京100876;2.災(zāi)備技術(shù)國家工程實(shí)驗(yàn)室，北京100876)

0 引言

軟件水印主要用于保護(hù)軟件的版權(quán)，分為靜態(tài)水印和動態(tài)水印[1－6]，其中動態(tài)軟件水印保存在程序的執(zhí)行狀態(tài)中。在動態(tài)軟件水印算法中，最具代表性的是 CT[7，8]和 NT[9]算法。

研究基于已有的CT動態(tài)圖軟件水印算法，提出一種新的基于PPCT(Planted Plane Cubic Tree)、排序圖和中國剩余定理的水印算法DGSW算法。實(shí)驗(yàn)仿真表明，使用DGSW水印算法方案的CT軟件水印算法在抗攻擊能力方面有所提高，同時(shí)具有較好的數(shù)據(jù)嵌入率。

1 動態(tài)圖軟件水印技術(shù)

動態(tài)軟件水印系統(tǒng)評估性能的方式有別于靜態(tài)軟件水印系統(tǒng)。動態(tài)水印算法在嵌入水印時(shí)要考慮靜態(tài)數(shù)據(jù)嵌入率和動態(tài)數(shù)據(jù)嵌入率兩種嵌入率。靜態(tài)數(shù)據(jù)嵌入率是指在程序中嵌入多少生成水印的額外代碼，而動態(tài)數(shù)據(jù)嵌入率是指在程序運(yùn)行時(shí)生成多少額外的數(shù)據(jù)。此外，動態(tài)軟件水印算法的隱蔽性分為靜態(tài)隱蔽性和動態(tài)隱蔽性兩種。靜態(tài)隱蔽性是指生成水印的代碼的存在是否容易被感知或定位的能力，而如果程序運(yùn)行時(shí)生成的有關(guān)水印的數(shù)據(jù)結(jié)構(gòu)能夠與程序原本的數(shù)據(jù)結(jié)構(gòu)協(xié)調(diào)一致，那么就說算法是動態(tài)隱蔽的。

CT算法需要將水印數(shù)字轉(zhuǎn)換成對應(yīng)的生成圖結(jié)構(gòu)的代碼，圖的結(jié)構(gòu)對水印嵌入率和隱蔽性具有非常重要影響。不同的圖編碼方案如底數(shù)圖、排序圖等等，單位比特的水印對應(yīng)的圖的大小是不一樣的，因此影響了生成水印的代碼的體積。而數(shù)據(jù)嵌入率越低，圖對應(yīng)的水印代碼的量越大，水印隱蔽性就越差。所以，文中致力于研究改進(jìn)CT算法的圖編碼方案，從而提高算法的數(shù)據(jù)嵌入率和隱蔽性。

CT動態(tài)水印算法的抗干擾能力是一項(xiàng)重要指標(biāo)，主要取決于算法采用的圖編碼方式。例如，排序圖不能抵抗邊翻轉(zhuǎn)攻擊，如果攻擊者交換其中幾條邊的順序，那么圖的結(jié)構(gòu)就會完全發(fā)生改變，對應(yīng)的水印數(shù)字就不一樣了。提出一種新的編碼方案DGSW，其抗攻擊能力更強(qiáng)，即使圖的結(jié)構(gòu)由于攻擊被改變，仍然可以發(fā)現(xiàn)并糾正錯誤，從而還原出正確的水印，同時(shí)也能夠保持較高的數(shù)據(jù)嵌入率。

2 DGSW算法

2.1 嵌入過程

DGSW使用中國剩余定理，首先構(gòu)造一個(gè)同余方程組把一個(gè)水印W分解成一個(gè)余數(shù)的集合，這些余數(shù)代表W的各個(gè)片段，只要獲得足夠多的片段就能恢復(fù)出W。算法如下:

(1)選取r個(gè)兩兩互素的數(shù) p1，p2，…，pr，使 W＜∏rk=1pk。

(2)把W分解成r(r－1)/2個(gè)形如W'≡xkmodpikpjk(0≤xk＜pikpjk)的整數(shù)。

(3)利用中國剩余定理解出W。

這其中最關(guān)鍵的是，不需要將所有的同余方程都找齊才能夠得到最終的水印數(shù)字。只要把模數(shù)的因子p1、p2、…、pr找全，就能夠還原出正確的水印。換句話說，在運(yùn)氣最好的情況下，只需要找到[r/2]個(gè)水印片段就能夠正確恢復(fù)水印。所以在這個(gè)例子中，即使這3個(gè)片段丟失或者被篡改任意1個(gè)，依然有機(jī)會計(jì)算出正確的水印數(shù)字。

通過上述算法獲得水印W的各個(gè)片段后，需要構(gòu)造每個(gè)水印片段對應(yīng)的子圖并將它們連接。設(shè)子圖中葉子結(jié)點(diǎn)的個(gè)數(shù)為n，要選取足夠大的n使n個(gè)結(jié)點(diǎn)形成的排序圖所表示的數(shù)的范圍大于子圖對應(yīng)的同余方程的模數(shù)，并且葉子結(jié)點(diǎn)數(shù)為n的PPCT結(jié)構(gòu)所表示的整數(shù)范圍同樣足夠大能表示余數(shù)。這里采用的選取方法是，根據(jù)PPCT結(jié)構(gòu)的特點(diǎn)，計(jì)算出最小n，使Calalan(n)＞=余數(shù)，再計(jì)算出最小的n'，使n'!＞=橫數(shù)。最后選出max(n'，n)，作為最終的子圖的葉子結(jié)點(diǎn)個(gè)數(shù)，從而構(gòu)造出對應(yīng)的圖結(jié)構(gòu)。首先構(gòu)造以下同余方程:

其中0＜k≤r(r－1)/2。

利用如下算法可以構(gòu)造出完整的圖結(jié)構(gòu):

for(each subgraph k)

calculate n1Catalan(n1)≥Wkand n1is minimum

calculate n2PermutaitonGraphLength(n1)≥pikpjkand n2is minimum

n=max(n1，n2)

build PPCT structure according to n and Wk

build Permutaiton Graph

connect each subgraph

下面用一個(gè)示例來具體說明嵌入過程。假設(shè)要將水印W=25分解成3部分。

(1)首先選取3個(gè)兩兩互質(zhì)的數(shù)，這里選取p1=2、p2=3、p3=5 這3 個(gè)數(shù)。

(2)接下來把25分解成一個(gè)含有3個(gè)方程的同余方程組:

由此計(jì)算出1和5、10是水印數(shù)字25的3個(gè)分解片段。然后根據(jù)這3個(gè)片段及其對應(yīng)的模數(shù)構(gòu)造相應(yīng)的子圖，最后連接這3個(gè)子圖就完成了水印的嵌入過程。同理，在提取水印時(shí)，根據(jù)圖的結(jié)構(gòu)還原同余方程組，再根據(jù)中國剩余定理計(jì)算出水印。

該同余方程組對應(yīng)的圖結(jié)構(gòu)如下圖1所示。

圖1 同余方程組結(jié)構(gòu)

余數(shù)1對應(yīng)的PPCT圖的葉子結(jié)點(diǎn)個(gè)數(shù)為1，而模數(shù)6對應(yīng)的排序圖的結(jié)點(diǎn)個(gè)數(shù)為3，所以選取3作為葉子結(jié)點(diǎn)個(gè)數(shù)構(gòu)造對應(yīng)的PPCT結(jié)構(gòu)，再根據(jù)排序圖編碼方案改變?nèi)~子結(jié)點(diǎn)右指針方向使其表示模數(shù)6.依此類推，構(gòu)造出其他的2個(gè)子圖。最后把這些子圖通過他們的生成結(jié)點(diǎn)相連形成一個(gè)完整的圖結(jié)構(gòu)。

圖中箭頭都表示圖的邊，但是作用不同。箭頭3用于分割子圖，箭頭1用于連接子圖內(nèi)PPCT結(jié)構(gòu)的結(jié)點(diǎn)。箭頭2表示模數(shù)。在每個(gè)子圖內(nèi)部，各個(gè)葉子結(jié)點(diǎn)的右指針(箭頭2)以排序圖的方式編碼，用于表示該子圖對應(yīng)的同余方程的模數(shù)，而子圖的PPCT結(jié)構(gòu)對應(yīng)這個(gè)同余方程的余數(shù)。如最左邊的子圖對應(yīng)的PPCT結(jié)構(gòu)表示1，而葉子結(jié)點(diǎn)形成的排序圖表示6。

2.2 提取過程

首先把表示同余方程組的完整圖結(jié)構(gòu)分割成若干子圖，分析每個(gè)子圖的PPCT是否完整，然后對每個(gè)子圖進(jìn)行解碼得到對應(yīng)的同余方程，進(jìn)而還原出同余方程組。由于水印可能受到攻擊，所以接下來要過濾掉錯誤的水印片段從而得到正確的同余方程組。辦法是首先建立兩個(gè)圖G、H，每一個(gè)方程在G、H中都有對應(yīng)的頂點(diǎn)，并計(jì)算出各個(gè)子圖對應(yīng)的同余方程，如果兩個(gè)同余方程不相容(不相容有2種情況，第一種情況指2個(gè)方程模數(shù)相同但是余數(shù)不同，另一種情況是指2個(gè)方程的模數(shù)中有一個(gè)因數(shù)相同，但是方程的余數(shù)模這個(gè)因數(shù)得到的余數(shù)不同)，就在G的對應(yīng)結(jié)點(diǎn)之間建立一條邊，如果兩個(gè)方程相容，就在圖H的對應(yīng)結(jié)點(diǎn)之間建立一條邊。從圖H中找出最大的頂點(diǎn)，因?yàn)楹瓦@個(gè)方程相容的其他同余方程最多，所以這個(gè)方程是正確的。接下來將這個(gè)頂點(diǎn)對應(yīng)的方程放到同余方程組U中，并將這個(gè)頂點(diǎn)和與它不相容的頂點(diǎn)從H、G中刪除，不斷重復(fù)這個(gè)過程直到圖G變成一個(gè)空圖為止。最后應(yīng)用中國剩余定理就能夠計(jì)算出同余方程組U表示的水印了。

下面用一個(gè)示例具體說明過濾錯誤片段的過程。已知從各個(gè)子圖提取出以下同余方程組:

其中 p1=2、p2=3、p3=5。

前3個(gè)方程是原來正確的方程，而第4個(gè)方程是與原水印不相干的方程。

在圖G、H中各構(gòu)造這4個(gè)方程對應(yīng)的頂點(diǎn)。由于第1個(gè)方程與第3個(gè)方程不相容，圖G中這2組頂點(diǎn)間就有了一條邊。只要不斷在G中去掉頂點(diǎn)和對應(yīng)的邊，最后就能夠去掉第4個(gè)方程得到如下同余方程組:

然后拆解同余方程組得到以下方程:

最后利用中國剩余定理解出這個(gè)同余方程的解W。

由該方程組可知其中存在很多冗余方程，因此只要把模數(shù)的因子p1、p2、…、pr找全，就能夠得到還原出正確的水印。在運(yùn)氣最好的情況下，只需要找到[r/2]個(gè)水印片段就能夠正確恢復(fù)水印。所以在這個(gè)例子中，即使這3個(gè)片段丟失或者被篡改任意一個(gè)，依然有能計(jì)算出正確的水印數(shù)字。

3 仿真測試

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

圖2 3種編碼方案的水印嵌入率

計(jì)算DGSW理論上的數(shù)據(jù)嵌入率不僅比較困難，而且計(jì)算結(jié)果與實(shí)際不太一致，因?yàn)镃T軟件水印算法真正需要的是產(chǎn)生水印圖所需代碼盡可能地少，而水印圖所表示的數(shù)盡可能大的一種圖，所以通過實(shí)驗(yàn)測量單位比特水印對應(yīng)的圖的代碼體積是最佳選擇。圖2顯示3種編碼方案的水印嵌入率，由圖2可知，提出的新編碼方案數(shù)據(jù)嵌入率優(yōu)于PPCT編碼，與排序圖相差無幾。

3.2 抗干擾能力

3.2.1 抵抗邊翻轉(zhuǎn)攻擊

該水印算法采用了PPCT結(jié)構(gòu)，因此具有很好抵抗邊翻轉(zhuǎn)攻擊能力。雖然在新編碼方案中葉子結(jié)點(diǎn)構(gòu)成的排序圖無法抵御邊翻轉(zhuǎn)攻擊，排序圖所表示的模數(shù)會因此改變。根據(jù)中國剩余定理，提取水印時(shí)只要能夠找齊各個(gè)模數(shù)的因子，就能夠正確提取水印，改變少數(shù)幾個(gè)模數(shù)的大小并不會影響正確的提取因子。再加上可以在同余方程組中添加冗余方程增強(qiáng)糾錯能力，因此，新的編碼方案相較于已有的PPCT和排序圖的抵抗邊翻轉(zhuǎn)攻擊的能力都要強(qiáng)。

3.2.2 抵抗結(jié)點(diǎn)分裂攻擊

結(jié)點(diǎn)分裂攻擊指把動態(tài)分配的內(nèi)存對象一分為二，變成2個(gè)不同的對象，并且讓第一個(gè)對象指向第二個(gè)對象。為了抵抗這種攻擊，該編碼方案可以轉(zhuǎn)換成一個(gè)m次的循環(huán)結(jié)構(gòu)，并將所有的邊都換成一個(gè)m次的鏈接結(jié)構(gòu)。任何的結(jié)點(diǎn)分裂都會融入循環(huán)結(jié)構(gòu)或者鏈接結(jié)構(gòu)當(dāng)中，提取水印時(shí)需要規(guī)約這些循環(huán)和鏈接結(jié)構(gòu)，還原出原來的水印圖，因此能夠自然消除結(jié)點(diǎn)分裂帶來的影響，如圖3所示。

圖3 DGSW水印方案抵抗節(jié)點(diǎn)分裂攻擊

最上面的是一個(gè)表示整數(shù)3的底數(shù)圖，在經(jīng)過循環(huán)處理后變成了下面所示的結(jié)構(gòu)。結(jié)點(diǎn)1、2、3都變成了3個(gè)結(jié)點(diǎn)的鏈接結(jié)構(gòu)，A、B、C 3條邊也是如此。即使這樣的結(jié)構(gòu)遭受結(jié)點(diǎn)分裂攻擊，在最后還原水印圖時(shí)攻擊產(chǎn)生的影響都能夠被消除。

3.3 隱蔽性

由于對具有海量且復(fù)雜鏈接的數(shù)據(jù)結(jié)構(gòu)的程序進(jìn)行別名分析是非常困難的，所以CT算法具有很好的動態(tài)隱蔽性。然而CT算法本身并不能保證水印的靜態(tài)隱蔽性，所以必須使用代碼混淆等保護(hù)技術(shù)使得程序源代碼可分析性降低。因此需要通過實(shí)驗(yàn)判斷現(xiàn)有的代碼混淆技術(shù)是否會對CT算法的水印的提取產(chǎn)生影響。

以下測試的是本編碼方案抵抗代碼混淆處理的能力。其中“+”表示能夠抵御混淆處理，水印能夠正常提取，”－“表示不能抵御混淆處理。修改比例指程序中混淆的方法數(shù)占總方法數(shù)的比例。

表1 代碼混淆技術(shù)對水印提取的影響

由表1可知，除了Split Classes這個(gè)混淆算法之外，其余的混淆算法對水印的提取沒有任何影響。

4 結(jié)束語

在CT算法的現(xiàn)有編碼方案基礎(chǔ)上，綜合中國剩余定理和現(xiàn)有編碼方案的一些優(yōu)點(diǎn)提出DGSW編碼方案。實(shí)驗(yàn)結(jié)果表明這套編碼方案具備抗攻擊能力強(qiáng)，糾錯能力好，數(shù)據(jù)嵌入率較高的優(yōu)勢。

[1] Davidson R I，Myhrvold N.Method and system for generating and auditing a signature for a computer program:US，US5559884 A[P].1994.

[2] Hattanda K.The evaluation of Davidson＇s digital signature scheme[J].Ieice Transactions on Fundamentals of Electronics Communications＆Computer，2004，87(87-A):224－225.

[3] Myles G，Collberg C，Heidepriem Z，et al.The evaluation of two software watermarking algorithms.[J].Software Practice ＆ Experience，2005，35(10):923－938.

[4] Myles G，Collberg C，Heidepriem Z，et al.The evaluation of two software watermarking algorithms[J].Software Practice ＆ Experience，2005，35(10):923－938.

[5] Moskowitz，Scott A，Cooperman Marc.Method for stega-cipher protection of computer code[M].U-nited States Patent 5745569，1996.

[6] Collberg C，Thomborson C.Software watermarking:Models and dynamic embeddings[C].In:Principles of Programming Languages 1999，POPL 1999.

[7] Collberg C S，Thomborson C，Townsend G M.Dynamic graph-based software fingerprinting[J].Acm Transactions on Programming Languages＆Systems，2007，29(6):695－706.

[8] Palsberg J，Krishnaswamy S，Kwon M，et al.Experience with software watermarking[C].Proceedings of Acsac Annual Computer Security Applications Conference，IEEE Computer Society，2000:308.

[9] Nagra J，Thomborson C.Threading Software Watermarks[J].Lecture Notes in Computer Science，2004:208－233.

[10] Collberg C S，Thomborson C.Watermarking，Tamper-Proofing，and Obfuscation-Tools for Software Protection[J].Software Engineering IEEE Transactions on，2002，28(8):735－746.

[11] Christian Collberg，Jasvir Nagra.軟件加密與解密[M].北京:人民郵電出版社，2012:432－443.