基于路徑的防篡改動(dòng)態(tài)軟件水印算法

1、基于路徑的防篡改動(dòng)態(tài)軟件水印算法     摘  要  本文給出了一種改進(jìn)的動(dòng)態(tài)水印算法，該算法采用基于中國(guó)剩余定理的水印分割方法，并通過(guò)在程序中同時(shí)插入與分割的拓?fù)鋱D相對(duì)應(yīng)的校驗(yàn)比特串的方法提高其糾錯(cuò)能力和抗篡改能力。該算法具有編碼糾錯(cuò)能力強(qiáng)、抗攻擊能力好的特點(diǎn)，同時(shí)兼顧了基數(shù)k編碼方法編碼率高、編碼范圍廣的優(yōu)點(diǎn)。     關(guān)鍵詞  軟件水印; 動(dòng)態(tài)圖; 路徑; 防篡改  1 引言    軟件水印技術(shù)是通過(guò)向程序中嵌入識(shí)別信息來(lái)抗擊軟件盜版，現(xiàn)今大多數(shù)已提

2、出的軟件水印算法都存在方方面面的缺點(diǎn)。根據(jù)水印被加載的時(shí)刻，軟件水印分為靜態(tài)水印和動(dòng)態(tài)水印。靜態(tài)水印存儲(chǔ)在可執(zhí)行的程序代碼中，已知的靜態(tài)水印都易于遭受簡(jiǎn)單的變形水印攻擊，抗攻擊能力差，任何代碼優(yōu)化技術(shù)都可以破壞水印。動(dòng)態(tài)水印在程序運(yùn)行時(shí)被構(gòu)建，存儲(chǔ)在程序的執(zhí)行狀態(tài)中。動(dòng)態(tài)水印由于魯棒性較強(qiáng)，現(xiàn)在受到了廣泛的關(guān)注。     Collberg 和Thomborson1提出了一種動(dòng)態(tài)圖水印技術(shù)，即把軟件水印隱藏在程序動(dòng)態(tài)建立的圖結(jié)構(gòu)拓?fù)渲小Ｓ捎谥羔樈Y(jié)構(gòu)的引入，使得控制動(dòng)態(tài)圖結(jié)構(gòu)的那部分代碼不易被分析，因而很難對(duì)圖進(jìn)行保持語(yǔ)義變換。這種技術(shù)的基本思想是用圖的拓?fù)浣Y(jié)構(gòu)來(lái)代表

3、一個(gè)數(shù)N，這個(gè)數(shù)是兩個(gè)大素?cái)?shù)的乘積，在進(jìn)行水印檢測(cè)時(shí)，先根據(jù)圖的拓?fù)浣Y(jié)構(gòu)恢復(fù)出N，由于數(shù)論中的大數(shù)分解難問(wèn)題，只有合法用戶才能將檢測(cè)到的N分解成大素?cái)?shù)P和Q的乘積，從而證明其合法版權(quán)。與靜態(tài)水印相比，動(dòng)態(tài)圖水印算法不容易受到代碼最優(yōu)化和代碼迷亂等水印攻擊的破壞，但是同樣不能很好地抵抗篡改、裁減等惡意攻擊。     軟件水印的防篡改技術(shù)可以對(duì)軟件及水印本身提供保護(hù)，當(dāng)水印遭到破壞（水印代碼被部分刪除或優(yōu)化等），程序能夠立即感知并終止軟件的運(yùn)行。針對(duì)靜態(tài)水印，Holmes（1994）提出了在水印中包含校驗(yàn)和的防篡改措施，但是如果攻擊者掌握了校驗(yàn)和算法，就很容易修改校驗(yàn)

4、和，防篡改能力十分有限。Moskowite和Cooperman5（1998年）提出了另一種靜態(tài)水印防篡改技術(shù)，即把水印代碼嵌入到應(yīng)用程序的特殊資源中，一旦該圖像被篡改就立即終止程序的運(yùn)行以此達(dá)到防篡改的目的。但是問(wèn)題是這種憑空產(chǎn)生和執(zhí)行的代碼的不尋常性會(huì)使水印失去隱蔽性，引起攻擊者的注意。至今為止，軟件水印的防篡改技術(shù)僅僅處在一個(gè)摸索的階段，所提出的各種理論和算法都存在一定的缺陷。     本文首先給出了一種基于中國(guó)剩余定理的動(dòng)態(tài)圖的構(gòu)造算法和一種基于路徑的防篡改的水印圖的嵌入技術(shù)，在此基礎(chǔ)上提出了一種改進(jìn)的給予路徑的動(dòng)態(tài)防篡改水印算法。 2 動(dòng)態(tài)圖水印算法動(dòng)態(tài)圖

5、水印算法過(guò)程可以描述為下面幾個(gè)步驟：     (1)將兩個(gè)大質(zhì)數(shù)的乘積作為水印數(shù)字w；     (2)將這個(gè)水印數(shù)字用一個(gè)特殊的拓?fù)鋱D來(lái)表示；     (3)構(gòu)造編碼函數(shù)code() (構(gòu)造編碼函數(shù)的同時(shí)，應(yīng)有相對(duì)應(yīng)的解碼函數(shù)decode()使該函數(shù)在運(yùn)行時(shí)可以產(chǎn)生這個(gè)拓?fù)鋱D；     (4)在原始程序中嵌入這段代碼，使得添加水印后的程序只有在輸入一個(gè)特定的序列時(shí)才構(gòu)造出這個(gè)水印(我們稱嵌入水印代碼后的程序?yàn)檩d體程序)；     (5)當(dāng)需要提取

6、水印時(shí)，運(yùn)行載體程序和水印檢測(cè)例程，輸入特定的序列，提取出拓?fù)鋱D；     (6)調(diào)用解碼函數(shù)decode()，將提取出的拓?fù)鋱D還原為水印數(shù)字w。     假設(shè)p是未加入水印的原始程序，i是特定的輸入序列，w是要嵌入的水印信息，g是可以唯一表示w的圖， 為嵌入水印后的程序，e為水印嵌入函數(shù)，ex為水印提取函數(shù)。 那么一個(gè)完整的動(dòng)態(tài)圖水印的過(guò)程就由下面四個(gè)函數(shù)組成：     水印數(shù)字映射為拓?fù)鋱D: ;     拓?fù)鋱D嵌入原始程序: ;   

7、0; 從載體程序中提取拓?fù)鋱D: ;     圖結(jié)構(gòu)映射為水印數(shù)字: 。 3 基于路徑的防篡改動(dòng)態(tài)水印算法    一個(gè)完整的軟件水印算法應(yīng)包含水印拓?fù)鋱D構(gòu)造、水印嵌入和水印提取三個(gè)部分。 3.1 水印的拓?fù)鋱D映射    將水印數(shù)字編碼為拓?fù)鋱D已經(jīng)提出了多種編碼方案1，例如PPCT編碼、基數(shù)-k編碼、父指針樹編碼和排列編碼。幾種編碼方式各有優(yōu)缺點(diǎn)，實(shí)際應(yīng)用時(shí)應(yīng)根據(jù)軟件水印系統(tǒng)的需求決定。比如，PPCT樹的比特率比較低但糾錯(cuò)能力較強(qiáng)，而基數(shù)編碼具有較高的比特率但糾錯(cuò)能力太差。    

8、; 由于要嵌入的水印數(shù)字會(huì)是一個(gè)相當(dāng)大的值，無(wú)論運(yùn)用上述任何一種編碼方式，它對(duì)應(yīng)的拓?fù)鋱Dg的規(guī)模都會(huì)很大，如果將一個(gè)完整的g的構(gòu)建代碼全部嵌入程序中的某個(gè)位置，會(huì)使水印的隱秘性減弱而容易引起攻擊者的注意，從而遭到破壞。隨后Collberg 和Thomborson提出將拓?fù)鋱Dg分解為多個(gè)水印子圖 ，并分別嵌入程序的不同執(zhí)行路徑中。該方法必須考慮水印圖應(yīng)如何分解才能保證在水印提取時(shí)添加最少的邊連通所有的子圖，而且對(duì)拓?fù)鋱D進(jìn)行分割，存在算法復(fù)雜度高、均勻分割困難以及分割后連通子圖更困難的問(wèn)題。     針對(duì)動(dòng)態(tài)圖分割存在的問(wèn)題，本文給出了一種基于中國(guó)剩余定理的分割方法。

9、     設(shè)ZN 表示集合0,1,N-1, MN表示M除以N的余數(shù)。     定理1 令 是兩兩互素的整數(shù)，且 ，則存在唯一的整數(shù) ，且M的編碼 是一個(gè)k元組< >。     定理2 如果 是兩兩互素的整數(shù)，且 ， 為整數(shù)序列且 ，若存在唯一的整數(shù) ，使得 ，則有     其中， ， 。     借助于中國(guó)剩余定理可以把一個(gè)水印數(shù)據(jù)w分解為若干個(gè)子水印數(shù)據(jù)，之后可以通過(guò)這些子水印恢復(fù)水印數(shù)據(jù)w。     將素?cái)?shù)序列 看作水印嵌入和提取的密鑰， 水印數(shù)據(jù) 。把水印數(shù)據(jù)w轉(zhuǎn)換為被嵌入水印中的拓?fù)鋱D集合包含圖1所示的幾個(gè)步驟：     （1） 首先使 成對(duì)地關(guān)聯(lián)在一起，共有 對(duì)，則w即被分成 塊，每一塊記為， （ ， ）。如果把每一個(gè)Pi 看作一個(gè)結(jié)點(diǎn)， 作為 Pi 和 Pjw，需要知道w對(duì)每一個(gè)Pi  取模的值。因?yàn)?是成對(duì)關(guān)聯(lián)的，由 可以推導(dǎo)出所需要的值，從而從這個(gè)整數(shù)序列中能夠重新構(gòu)建w。這是圖1中的第步。     （2） 所有的 都可以通過(guò)一個(gè)枚舉表被依次轉(zhuǎn)化為一個(gè)單獨(dú)的整數(shù)，枚舉表中表達(dá)如下， ，