一種HASH變換驗證的軟件水印算法實現(xiàn)（（

1、一種HASH變換驗證的軟件水印算法實現(xiàn)基金項目：國家863基金資助項目（2007AA01Z438200）作者簡介：劉亞琦（1966），甘肅天水人，副教授，碩士研究生，主要從事信息安全的研究。吳振強（1968）男，陜西柞水人，博士，副教授，碩士生導(dǎo)師，研究方向為匿名通信技術(shù)、可信計算、自適應(yīng)安全。劉亞琦（甘肅工業(yè)職業(yè)技術(shù)學(xué)院點電信學(xué)院）1 吳振強2（1甘肅工業(yè)職業(yè)技術(shù)學(xué)院信息工程系 天水 741025；2陜西師范大學(xué)計算機科學(xué)學(xué)院，西安 710062）中圖分類號：TP309 文獻(xiàn)標(biāo)識碼：A摘要：動態(tài)數(shù)據(jù)結(jié)構(gòu)水印就是將水印隱藏在程序動態(tài)建立的圖結(jié)構(gòu)拓?fù)渲?，水印提取時的完整性是其關(guān)鍵技術(shù)。本文基于改

2、進(jìn)的PPCT水印構(gòu)造算法，通過Hash數(shù)學(xué)變換與驗證，實現(xiàn)對水印的動態(tài)嵌入和可靠提取。分析與實現(xiàn)表明，本方法具有較強的安全性和魯棒性，能夠較好地實現(xiàn)軟件的版權(quán)保護(hù)。關(guān)鍵詞：動態(tài)圖水??；，PPCT樹；，Hash變換；，水印攻擊Transformation of a HASH verification software watermarking algorithmLiu Ya-qi1 Wu Zhen-qiang2 (1 Department of Information Engineer, Gansu Industry Polytechnic College, Tianshui 741025 2

3、College of Computer Science, Shanxi Normal University, Xian 710062, China)Abstract: Dynamic data structure is to hide the watermark in the program dynamically builting graph structure topology, how to determine the integrity when the extracted watermark. Based on an improved watermark PPCT construct

4、ion algorithm, through the Hash mathematical transformation and verification, to realize the dynamics of the watermark embedding and reliable extraction. Analysis and implementation show that this method has strong security and robustness, can be used better for software copyright protection.Key wor

5、ds: Dynamic map watermarking;, PPCT tree;, Hash transformation,; Watermark attack動態(tài)圖水印技術(shù)是近年來被廣泛研究與討論的一種軟件水印技術(shù)。Collberg和Thomborson首次提出并討論了動態(tài)圖水印(Dynamic Graph Watermark，DGW)1，它是在軟件運行時動態(tài)地將水印信息轉(zhuǎn)化成某種圖結(jié)構(gòu)并隱藏在軟件代碼中，即把軟件水印隱藏在程序動態(tài)建立的圖結(jié)構(gòu)拓?fù)渲小Ｓ捎谶@種圖結(jié)構(gòu)包含許多指針并且是在運行時動態(tài)生成，且指針的具體值在每次運行時不同，因此動態(tài)圖水印算法不容易受到代碼優(yōu)化和代碼迷亂等水印攻擊的

6、破壞。但是這種圖結(jié)構(gòu)在抵抗篡改、裁減等惡意攻擊方面表現(xiàn)較差。為了提高動態(tài)圖水印技術(shù)的抗攻擊能力，文獻(xiàn)2提出多常量編碼偽水印來對動態(tài)圖水印進(jìn)行保護(hù)的方法。該算法通過創(chuàng)建多個對宿主程序功能性有依賴關(guān)系的改進(jìn)型PPCT （Improved Planted Plane Cubic Tree，IPPCT）結(jié)構(gòu)的偽水印，對真實水印起到了防篡改的作用，增加了攻擊者的攻擊難度。文獻(xiàn)3提出了基于二次剩余理論和Rabin 密碼體制的水印信息方法，該算法在多個水印與宿主程序之間建立功能性的依賴關(guān)系，對真實水印起到掩蓋作用，增加了攻擊難度。文獻(xiàn)4提出基于門限方案的動態(tài)圖水印算法AB 算法，把水印信息分為無關(guān)聯(lián) n份嵌

7、入，在還原原始水印信息時，提取其中 t(tn)份以上的份額就可以恢復(fù)原始水印，提高嵌入水印的程序經(jīng)攻擊后恢復(fù)水印的成功率。文獻(xiàn)5提出一種動態(tài)自我驗證的軟件水印防篡改技術(shù)，利用線性哈希函數(shù)對水印結(jié)構(gòu)進(jìn)行分塊計算, 采用常量遷移技術(shù)使完整性檢查隱藏在程序本身正常的邏輯判斷語句中，對其篡改會導(dǎo)致應(yīng)用程序功能錯誤。但這些方法減少了程序可容納的水印信息量，水印恢復(fù)時涉及復(fù)雜的逆運算，增加了計算量和計算時間。本文提出一種基于節(jié)點命令詞的ASC的HASH變換驗證軟件水印算法，水印完整性信息保存在程序結(jié)構(gòu)中，當(dāng)水印遭到攻擊以致被破壞時（水印代碼被部分刪除或優(yōu)化等），程序能夠立即感知并終止軟件的運行，從而實現(xiàn)對

8、軟件及水印本身提供保護(hù)。1 動態(tài)圖水印信息的形成根據(jù)數(shù)論中的大數(shù)分解難的問題，可選擇一個代表版權(quán)信息的大自然數(shù)N 作為水印數(shù)，并將此大數(shù)N 轉(zhuǎn)化成某種圖拓?fù)浣Y(jié)構(gòu)后嵌入到軟件程序代碼里。只有合法用戶才能將檢測到N 分解成大素數(shù)P 和Q 的乘積，從而證明其合法版權(quán)通過拓?fù)漕愋偷膭討B(tài)圖數(shù)據(jù)結(jié)構(gòu)水印隱藏此大數(shù)，如果能從軟件中有效提取出此大數(shù)，且此過程能夠在有限時間內(nèi)完成，則證明對包含水印的待驗證軟件具有知識產(chǎn)權(quán)。其中，圖的拓?fù)浣Y(jié)構(gòu)可以由面向?qū)ο蟪绦蛟O(shè)計中的對象作為節(jié)點構(gòu)成，即圖的編碼采用改進(jìn)的PPCT樹。如圖1表示：圖1 用戶水印信息轉(zhuǎn)換成改進(jìn)的PPCT樹其具體過程為：(1)選擇一個水印數(shù)字。(2)將

9、這個水印數(shù)字用一個水印圖來表示。(3)構(gòu)造一段水印代碼，用來在運行時產(chǎn)生上述圖結(jié)構(gòu)。(4)在軟件程序中嵌入這段代碼，使得添加水印后的程序只有在接受一個特殊的輸入序列時才構(gòu)造這個水印。大數(shù)N根據(jù)公式 這個表達(dá)式的m 則是由這個樹的葉子節(jié)點個數(shù)，系數(shù)ei取決PPCT樹的葉子節(jié)點右指針指向的葉子節(jié)點返回到原葉節(jié)點所需要經(jīng)過的葉節(jié)點的個數(shù)，這里規(guī)定葉節(jié)點的右指針為空表示0，指向自身表示1，指向下一個葉節(jié)點為2，依此類推。本文規(guī)定m的值為6，即葉子節(jié)點的個數(shù)為6個，則改進(jìn)的PPCT結(jié)構(gòu)表示成（m+1）=7為基數(shù)的表達(dá)式。任何葉子節(jié)點的右指針?biāo)赶虻慕Y(jié)點返回它本身所需經(jīng)過的結(jié)點個數(shù)最多為6個，即任何一個系

10、數(shù)ei的值不超過6。所以N數(shù)的取值范圍為0-117648之間。由Catalan理論，具有n個葉子結(jié)點的樹共有：種，則對于6個葉子節(jié)點的樹一共有42棵，所以我們所構(gòu)造的指紋庫中的序列也是這42棵樹所對應(yīng)的序列。22 水印信息嵌入過程2.1構(gòu)造PPCT樹隨機構(gòu)造總圖，如圖2。由構(gòu)造的PPCT樹計算其先序遍歷順序為：zabdhoooeoocfiooj oogkooloo，為了使構(gòu)造的樹唯一，要輸入每個葉子結(jié)點的空值。圖2 隨機構(gòu)造總圖2.2 子圖分解將圖2的PPCT樹分成幾個子圖，其中C節(jié)點為兩個圖的相交節(jié)點。分解成的兩個子圖如圖3、圖4所示。圖3的先序遍歷順序為zabdhoooeoocoo，圖4的

11、先序遍歷順序為cfioojoogkooloo。 圖3 子圖1 圖4 子圖22.3 Hash變換先序遍歷所有的節(jié)點，令每個節(jié)點的ID域乘以它的序號作為di，計算子圖的Hash值：Hash(0)=0Hash(i)=c*(di+Hash(i-1)其中0=i=n; c為非零常數(shù)，Hash(n)為該子圖最后節(jié)點的hash值。 -695.1428圖5 Hash變換以圖5為例，將相應(yīng)的節(jié)點值由字符轉(zhuǎn)化為對應(yīng)的ASCII值，進(jìn)行Hash變換（表1），為了使子圖的Hash值為0，將最后節(jié)點的值更改為 -695.1428。表1 Hash變換表節(jié)點ID值diHash值新的ID值1122122*112229797*2

12、31639898*36104100100*41010.13111111*13973214111111*1411286-695.14282.4嵌入水印流程圖 嵌入水印的流程如下：（1）將版權(quán)信息映射為一個大數(shù)，從指紋庫里面選取樹，綁定水印信息；（2）分解樹，構(gòu)造兩個子圖G1，G2；（3）修改各個子圖的最后一個結(jié)點，使得hash值和程序里面的一個常數(shù)對應(yīng)。（4）用hash（Gi）替換程序中的常數(shù)，完成嵌入，如圖6。部分關(guān)鍵代碼如下：float ha(int n,float Gi) /計算節(jié)點的Hash值float re;if(n=0) re=0;else re=cc*(n*Gin+ha(n-1),

13、Gi);return(re);檢測子圖節(jié)點：void Checkall(int checkc,char cAry,float Gi,float Checki,int CG) /存儲的檢測信息的數(shù)組Checki,逆序計算出的用于計算大數(shù)的數(shù)組CG float checkchgvalue; checkchgvalue=(checkc/cc-Checki4)/Checki1;if(checkchgvalue=Checki5) /判斷計算出的最后一個節(jié)點的數(shù)值是否等于數(shù)組Checki中存儲的值 reha(int)Checki1,Gi,Checki,CG); /相等的話，則取出數(shù)組Checki中更改前的

14、最后一個節(jié)點的數(shù)值 for(int i=1;i=(int)Checki1;i+) cAryi-1=(char)CGi; /將數(shù)值數(shù)組轉(zhuǎn)化為字符數(shù)組存儲到字符數(shù)組中 elseprintf(常數(shù)或數(shù)組與嵌入不一致!n);3 水印信息的提取由于有Hash(i-1)=Hash(i)/c-di，對于給定的Hash(i)和i，可以逆序計算出所有節(jié)點的Hash值，因此可以計算出每個節(jié)點的ID值。然后將這些節(jié)點的值逆序轉(zhuǎn)化為字符串，構(gòu)造子圖，然后進(jìn)行子圖的合并，構(gòu)造樹，然后根據(jù)樹的指針的跳數(shù)來重新計算大數(shù)。如果大數(shù)與數(shù)據(jù)庫中的大數(shù)匹配，則從數(shù)據(jù)庫中讀出水印信息，如果不匹配，則跳出或是執(zhí)行相應(yīng)的操作，如圖7。圖

15、6 水印嵌入 圖7 水印提取4 模擬攻擊分析4.1模擬攻擊之一：去除攻擊去除攻擊是將水印信息w從軟件Pw中去除。假設(shè)可以進(jìn)行去除攻擊的話，那么攻擊者所要做的工作就是：將嵌入時用hash（Gi）替換的常數(shù)，還原成正常的常數(shù)，否則則攻擊失敗?；诜纸庾訄DG1，G2，將G1、G2嵌入源程序中，如：G1:ab*cd*e*,G2: ef*.假設(shè)，G1、G2中的一個被刪除，那么我們借助于另外一個將其恢復(fù)，最極端的情況就是將G1、G2都替換，但是實現(xiàn)的難度比較大。4.2模擬攻擊之二添加攻擊即使攻擊者給Pw再一次的嵌入新的水印，那么攻擊者必須同時具備嵌入和檢測的技術(shù)，以便來標(biāo)識新的水印信息并保證軟件的正常運行

16、。但添加攻擊，并不影響對原水印信息的提取。為此，添加攻擊的威脅性較小。4.3模擬攻擊之三變形攻擊由于變形攻擊是基于對水印程序進(jìn)行模糊變換，在不影響程序正常運行的基礎(chǔ)上，攻擊者有可能采取代碼迷亂的技術(shù)進(jìn)行模糊變換，但是，由于我們水印信息的嵌入和提取，與代碼的執(zhí)行流程等不相關(guān)，只是替換了程序中的常量，為此，變形攻擊并不影響水印的正常不提取，變形攻擊也變不構(gòu)成威脅性。4.4模擬攻擊之四共謀攻擊 由于共謀攻擊是通過對若干個已經(jīng)嵌入過水印的軟件進(jìn)行比較，推測出水印的嵌入機制，顯然，通過共謀攻擊，最多的可以發(fā)現(xiàn)嵌入時，是用hash（Gi）來替換程序中的常量，但對于hash（Gi）所代表的子圖長度，以及子圖

17、的最后一個結(jié)點的數(shù)值無法獲得，并且PPCT結(jié)構(gòu)具有二又樹和鏈表的雙重特點，在構(gòu)造軟件水印時，可以利用指針來進(jìn)行樹的生成，根據(jù)現(xiàn)代操作系統(tǒng)中內(nèi)存管理的特點，指針的具體值在每次運行時都是不同的，這給水印的隱藏提供了極好的條件。為此，共謀攻擊最多也只是將hash（Gi）還原成原來正確的常量，這樣以來就轉(zhuǎn)化成了去除攻擊。同時由于對于不同的軟件嵌入水印的時候，都是隨機的從指紋庫里面讀取樹結(jié)構(gòu)，隨機產(chǎn)生一個大數(shù)與其對應(yīng)，然后根據(jù)這個大數(shù)，添加指針的跳數(shù)，為此這么些隨機性也就可以有效的防止共模攻擊。5 性能測試及結(jié)論 在C+語言環(huán)境下，對C或C+語言編制的程序進(jìn)行了測試，使用同方計算機（CPU 3.06GH

18、Z、512MB內(nèi)存、100GB硬盤），其中一部分嵌入水印前后的各項參數(shù)比較如下：5.1文件大小比較文件的比較可以用表2所示。表2 軟件水印嵌入前后程序大小比較嵌入前嵌入后大小7.16 MB （7,518,174字節(jié)）7.50MB (7,867,238字節(jié))占用空間7.25 MB （7,602,176字節(jié)）7.79MB （8,171,520字節(jié)）包含39個文件，2個文件夾97個文件，2個文件夾5.2內(nèi)存使用對比圖8是內(nèi)存的變化情況對比圖。圖8 內(nèi)存使用情況對照從圖中可以看出，添加水印前后的程序占用內(nèi)存情況差距不大，相差大概100KB左右，改變率為1.07%。因此在運行方面不會對宿主程序產(chǎn)生太大的負(fù)載。虛擬內(nèi)存使用圖9是虛擬內(nèi)存的使用情況對比圖。圖9 虛擬內(nèi)存使用情況對照從圖上分析，添加水印之前的虛擬內(nèi)存使用情況大致為9100K左右，添加水印之后使得虛擬內(nèi)存的使用情況上升至9400K左右，因此增加了300K的虛擬內(nèi)存資源。這其中的大部分為二叉鏈表，二叉樹，堆棧，隊列等這些數(shù)據(jù)結(jié)構(gòu)所開銷，還有部分可能為系統(tǒng)的調(diào)用這些函數(shù)所要求的必要開支。對于一個比較小的函數(shù)來說，300K的內(nèi)存資源增長略大，應(yīng)該相應(yīng)的控制以及精簡，使得對宿主程序的影響更加小。本文實現(xiàn)了一種動態(tài)自