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

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

2、進(jìn)的PPCT水印構(gòu)造算法，通過(guò)Hash數(shù)學(xué)變換與驗(yàn)證，實(shí)現(xiàn)對(duì)水印的動(dòng)態(tài)嵌入和可靠提取。分析與實(shí)現(xiàn)表明，本方法具有較強(qiáng)的安全性和魯棒性，能夠較好地實(shí)現(xiàn)軟件的版權(quán)保護(hù)。關(guān)鍵詞：動(dòng)態(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動(dòng)態(tài)圖水印技術(shù)是近年來(lái)被廣泛研究與討論的一種軟件水印技術(shù)。Collberg和Thomborson首次提出并討論了動(dòng)態(tài)圖水印(Dynamic Graph Watermark，DGW)1，它是在軟件運(yùn)行時(shí)動(dòng)態(tài)地將水印信息轉(zhuǎn)化成某種圖結(jié)構(gòu)并隱藏在軟件代碼中，即把軟件水印隱藏在程序動(dòng)態(tài)建立的圖結(jié)構(gòu)拓?fù)渲?。由于這種圖結(jié)構(gòu)包含許多指針并且是在運(yùn)行時(shí)動(dòng)態(tài)生成，且指針的具體值在每次運(yùn)行時(shí)不同，因此動(dòng)態(tài)圖水印算法不容易受到代碼優(yōu)化和代碼迷亂等水印攻擊的

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

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

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

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

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

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

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

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

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

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

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

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

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