[發(fā)明專利]一種在計算機(jī)程序中嵌入和提取水印的方法

有效

• 申請?zhí)枺?/td>: 200810119358.0
• 申請日: 2008-09-05
• 公開（公告）號: CN101350055A
• 公開（公告）日: 2009-01-21
• 發(fā)明（設(shè)計）人: 王建民;張長江;王朝坤;李德毅
• 申請（專利權(quán)）人: 清華大學(xué)
• 主分類號: G06F21/22
• 分類號: G06F21/22
• 代理公司: 北京清亦華知識產(chǎn)權(quán)代理事務(wù)所
• 代理人: 羅文群

1、一種在計算機(jī)程序中嵌入和提取水印的方法，其特征在于該方法包括以下步驟：

嵌入水印的過程為：

(1)將計算機(jī)程序版權(quán)人的版權(quán)信息和密鑰信息分別轉(zhuǎn)化為一個整型數(shù)字字符串，分別記為w和k，w和k是大整數(shù)；

(2)將上述w和k分別轉(zhuǎn)換成具有n個元素的單調(diào)非遞減的整數(shù)數(shù)組W[]和K[]，n是水印嵌入者設(shè)定的整數(shù)，1≤i≤n-1，具體的轉(zhuǎn)換過程為：

(2-1)任意設(shè)定一個大于1的整數(shù)q，求出滿足不等式w≤(ql-1)Σj=0n-2qjl]]>的整數(shù)l，以及滿足不等式k≤(qp-1)Σj=0n-2qjp]]>的整數(shù)p；

(2-2)根據(jù)等式w=Σj=0n-2vjqjl,]]>k=Σj=0n-1ujqjp]]>分別求出系數(shù)v₀，v₁，...，v_n-2和u₀，u₁，...，u_n-2，其中，對于0≤j≤n-2，系數(shù)v_j為整數(shù)且滿足：0≤v_j＜q^l，系數(shù)u_j為整數(shù)且滿足：0≤u_j＜q^p；

(2-3)令W[0]＝l-1，K[0]＝p-1，對1≤i≤n-1，得到W[i]＝W[i-1]+v_i-1，K[i]＝K[i-1]+u_i-1；

(3)在上述轉(zhuǎn)換得到的版權(quán)信息整數(shù)數(shù)組W[]與密鑰信息整數(shù)數(shù)組K[]的每一對相對應(yīng)的元素之間建立m個映射關(guān)系，m是水印嵌入者設(shè)定的另一整數(shù)，得到一個具有m×n個映射關(guān)系的集合；

(4)從計算機(jī)程序中選擇待嵌入水印的方法，其過程為：

(4-1)建立一個待嵌入水印的方法集合，從計算機(jī)程序中讀入一個方法；

(4-1-1)根據(jù)讀入的方法的控制流構(gòu)建該讀入的方法的控制流圖，并得到控制流圖的基本圖，求出該基本圖中所有割點的集合；

(4-1-2)對割點集合進(jìn)行判斷，若為空集，則轉(zhuǎn)入步驟(4-1-5)，若不為空集，則讀取上述割點集合中的一個割點；

(4-1-3)對讀取的割點進(jìn)行判斷，若符合：與該讀取的割點對應(yīng)的控制流圖中的基本塊能被拆分成兩個基本塊，且在兩個基本塊之間插入一個新的基本塊之后，兩個基本塊在新的控制流圖中成為相鄰割點，則該讀取的割點為可嵌入水印的割點，記錄與該可嵌入水印的割點相對應(yīng)的基本塊的入口位置，并將上述讀入的方法加入到待嵌入水印的方法集合中，轉(zhuǎn)入步驟(4-1-5)，若不符合，轉(zhuǎn)入步驟(4-1-4)；

(4-1-4)對上述割點集合進(jìn)行判斷，若該割點集合的所有割點遍歷結(jié)束，則轉(zhuǎn)入步驟(4-1-5)，否則，讀取該割點集合中的下一個割點，轉(zhuǎn)入步驟(4-1-3)；

(4-1-5)若計算機(jī)程序中的所有方法遍歷結(jié)束，則轉(zhuǎn)入步驟(4-2)，否則，讀入計算機(jī)程序中的下一方法，重復(fù)步驟(4-1-1)至步驟(4-1-4)，直至遍歷計算機(jī)程序中的所有方法；

(4-2)判斷可嵌入水印的割點個數(shù)，若少于m×n，則從計算機(jī)程序中任意選擇一個不在待嵌入水印的方法集合中的方法，在與所選擇的方法相對應(yīng)的控制流圖中添加新的分支，使得添加了新的分支的控制流圖含有可嵌入水印的割點，記錄與由于添加了新的分支而含有的可嵌入水印的割點相對應(yīng)的基本塊的入口位置，并將修改后的該所選擇的方法加入到上述待嵌入水印的方法集合中，重復(fù)本步驟中以上部分直至遍歷計算機(jī)程序中所有不在待嵌入水印的方法集合中的方法；

(4-3)判斷可嵌入水印的割點個數(shù)，若仍然少于m×n，則從上述待嵌入水印的方法集合中隨機(jī)選擇一個方法，按照上述步驟(4-1)中的過程讀入另一割點，找到一個可嵌入水印的割點，并記錄與找到的可嵌入水印的割點相對應(yīng)的基本塊的入口位置，若沒有找到可嵌入水印的割點，則在隨機(jī)選擇的方法體中添加改變該隨機(jī)選擇的方法的控制流的輔助代碼，使得該隨機(jī)選擇的方法的控制流圖中含有新的可嵌入水印的割點，并記錄與該新的可嵌入水印的割點相對應(yīng)的基本塊的入口位置，重復(fù)本步驟中以上部分，直至可嵌入水印的割點個數(shù)達(dá)到m×n；

(5)將映射關(guān)系嵌入到選定的待嵌入水印的方法中，其過程為：

(5-1)從映射關(guān)系集合中選擇一個映射關(guān)系，從上述待嵌入水印的方法集合中選擇一個待嵌入水印的方法，并讀取待嵌入水印的方法中的一個可嵌入水印的割點；

(5-2)為待嵌入水印的方法增加多個整型局部變量，使新增加的局部變量中編號最小的局部變量對應(yīng)于映射關(guān)系中的自變量，編號最大的局部變量對應(yīng)于映射關(guān)系中的因變量，創(chuàng)建局部變量初始化指令以及與映射關(guān)系相關(guān)的操作指令，并將操作指令與局部變量相關(guān)聯(lián)，得到映射關(guān)系代碼；

(5-3)將與從待嵌入水印的方法中讀取的割點相對應(yīng)的基本塊拆分成兩個基本塊b₁、b₂，并將構(gòu)建的映射關(guān)系代碼以一個基本塊b₃插入到b₁和b₂之間，使得基本塊b₁、b₂、b₃滿足：基本塊b₁跳向基本塊b₂和b₃，基本塊b₃跳向基本塊b₂；

(5-4)讀取下一個映射關(guān)系，判斷待嵌入水印的方法中是否有新的可嵌入水印的割點，若有，則讀取待嵌入水印的方法中下一個可嵌入水印的割點，并重復(fù)步驟(5-2)和步驟(5-3)，完成映射關(guān)系代碼的嵌入；若沒有，則讀取下一個待嵌入水印的方法，讀取該下一個待嵌入水印的方法中一個可嵌入水印的割點，并重復(fù)以上步驟(5-2)和(5-3)，完成映射關(guān)系代碼的嵌入；

(5-5)重復(fù)步驟(5-4)，直至所有映射關(guān)系代碼嵌入到計算機(jī)程序中；

提取水印的過程為：

(6)建立一個待提取水印的方法集合；

(7)讀取計算機(jī)程序中的一個方法，根據(jù)讀取的方法的控制流構(gòu)建與該讀取的方法相對應(yīng)的控制流圖，得到相應(yīng)的基本圖，求出基本圖的所有割點，得到一個割點集合，依次讀取割點集合中的割點并進(jìn)行判斷，若與讀取割點相對應(yīng)的控制流圖中的基本塊b₄滿足：b₄的跳轉(zhuǎn)目標(biāo)為兩個基本塊b₅和b₆，且基本塊b₅也為割點而b₆不為割點，同時基本塊b₅為基本塊b₆的跳轉(zhuǎn)目標(biāo)，或基本塊b₆也為割點而b₅不為割點，同時基本塊b₆為基本塊b₅的跳轉(zhuǎn)目標(biāo)，則對不為割點基本塊作進(jìn)一步判斷，若滿足：該不為割點基本塊中含有的局部變量個數(shù)和類型與構(gòu)建的映射關(guān)系代碼中局部變量個數(shù)和類型相一致，則從計算機(jī)程序中提取該不為割點基本塊中包含的操作指令以及所有局部變量的初始值，并根據(jù)操作指令和局部變量的初始值構(gòu)建一個新的方法，具體構(gòu)建過程如下：對按大小次序編號的上述不為割點基本塊中的局部變量重新從0開始編號，使編號最小的局部變量為新方法的輸入?yún)?shù)，編號最大的局部變量的值為新方法的返回值，使提取的操作指令作為新方法的操作指令；

(8)將上述新方法加入到上述待提取水印的方法集合中；

(9)重復(fù)上述步驟(7)和(8)，直至計算機(jī)程序中的所有方法遍歷結(jié)束；

(10)根據(jù)上述待提取水印的方法集合，創(chuàng)建提取輔助類，提取密鑰，并解析出版權(quán)信息；

(11)使用與上述步驟(1)和(2)相同的方法，將用戶的密鑰信息轉(zhuǎn)換成具有n個元素的單調(diào)非遞減的整數(shù)數(shù)組g[]；

(12)依次讀取上述整數(shù)數(shù)組g[]中的每個整數(shù)，并分別將讀取的整數(shù)作為上述提取輔助類中每個方法的輸入，獲得提取輔助類中每一個方法運(yùn)行的返回值，若相同返回值的個數(shù)小于m，則提取密鑰有誤，提取失敗，若相同返回值的個數(shù)大于或等于m，則將該相同返回值加入到整數(shù)數(shù)組h[]中；

(13)判斷整數(shù)數(shù)組h[]是否為單調(diào)非遞減，若不是，則顯示提取失敗，若是，則令上述l＝h[0]+1，對0≤j≤n-2，令v_j＝h[j+1]-h[j]，根據(jù)公式w=Σj=0n-2vjqj1]]>得到一個大整數(shù)w，將大整數(shù)w作為一個整型數(shù)字字符串，還原成原始的字符串，顯示版權(quán)信息并提示提取成功。