一種增強型動態(tài)圖的軟件水印算法

王 巍, 何 穎, 譚永坤, 劉衍珩,3

(1. 長春財經(jīng)學(xué)院 信息工程學(xué)院, 長春 130122；2. 中國電子科技集團公司第五十四研究所, 石家莊 050081；3. 吉林大學(xué) 計算機科學(xué)與技術(shù)學(xué)院, 長春 130012)

軟件水印是一種軟件版權(quán)保護技術(shù), 其將承載版權(quán)保護信息和身份認(rèn)證信息的數(shù)據(jù)直接或間接嵌入數(shù)字載體. 目前實現(xiàn)方式主要有靜態(tài)軟件水印和動態(tài)軟件水印兩大類. 由于動態(tài)軟件水印技術(shù)在隱蔽性、 抗攻擊、 防篡改等方面明顯優(yōu)于靜態(tài)軟件水印, 因此已逐漸成為軟件水印技術(shù)的主要實現(xiàn)方法, 其典型代表是基于動態(tài)圖的軟件水印.

基于動態(tài)圖的軟件水印[1]是指將水印信息編碼到某種圖結(jié)構(gòu)中, 然后在程序運行過程中動態(tài)構(gòu)建圖結(jié)構(gòu)并生成水印信息. Collberg等[2]首次提出了動態(tài)圖水印CT(Collberg-Thomborson)算法, 在程序運行時動態(tài)生成的數(shù)據(jù)結(jié)構(gòu)圖拓?fù)渲星度胨⌒畔? 探討了PPCT(planted plane cubic tree)編碼、 基數(shù)k鏈表水印數(shù)的可行性； Palsberg等[3]采用PPCT編碼結(jié)構(gòu)實現(xiàn)了CT算法, 進一步證明了基于動態(tài)圖的軟件水印算法具有較強抗攻擊性、 防篡改和魯棒性; 劉嘉怡等[4]提出了一種基于PPCT和排序圖的混合編碼方法, 增強了水印的隱蔽性, 但在兩種編碼方案所需葉節(jié)點不同時, 會導(dǎo)致葉節(jié)點的冗余； 蘇慶等[5]將水印信息編碼至Petri網(wǎng)運行時狀態(tài)序列中, 該方案具有較高的水印數(shù)據(jù)率和一定的檢錯恢復(fù)能力, 但攻擊者易發(fā)現(xiàn)程序中的水印片段, 防篡改相對減弱； 鄭秋梅等[6]利用顏色直方圖差值法從視頻序列中提取關(guān)鍵幀, 對關(guān)鍵幀和水印圖像分別進行非下采樣Contourlet變換、 離散余弦變換以及離散平穩(wěn)小波變換, 提高了水印的嵌入容量, 對抵抗常見時、 空域攻擊具有較好的魯棒性.

目前, 對動態(tài)圖軟件水印技術(shù)的研究已有許多成果[7-8]. 但研究將水印信息保存在數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)域中的相關(guān)報道較少. 基于此, 本文提出一種基于動態(tài)圖的軟件水印算法----增強型動態(tài)圖水印(enhanced dynamic graph watermarking, EDGW)算法, 并對數(shù)據(jù)嵌入率、 隱蔽性及抗攻擊性3個參數(shù)的性能進行取舍, 設(shè)計適應(yīng)實際應(yīng)用場景的軟件水印算法, 研究其可行性與性能的優(yōu)劣.

1 算法核心思想

本文提出一種新的動態(tài)圖水印算法, 水印數(shù)不再由圖結(jié)構(gòu)的拓?fù)浔旧砭幋a, 而是向水印圖結(jié)構(gòu)的每個節(jié)點中增加一個數(shù)據(jù)域用以存儲水印信息, 使水印保護不受水印圖結(jié)構(gòu)編碼的影響.

增強型動態(tài)圖水印算法是對動態(tài)圖軟件水印算法的一種改進算法, 其采用增強型動態(tài)圖數(shù)據(jù)結(jié)構(gòu), 通過將水印信息存儲在動態(tài)生成數(shù)據(jù)結(jié)構(gòu)的數(shù)據(jù)域中的方式向程序中嵌入水印信息, 其水印嵌入和提取過程如下：

步驟1) 根據(jù)水印分解算法將水印數(shù)W拆分為包含k個水印分存值的集合Wi(0≤i

步驟2) 根據(jù)k的大小從候選數(shù)據(jù)結(jié)構(gòu)中選擇一個包含k個節(jié)點的水印圖G, 用其節(jié)點的數(shù)據(jù)域嵌入水印分存值Wi；

步驟3) 分裂水印圖G, 得到子水印圖集合Gi(0≤i

步驟4) 將子水印圖Gi轉(zhuǎn)換為中間代碼段Mi(0≤i

步驟5) 將中間代碼段Mi轉(zhuǎn)換為創(chuàng)建水印子圖的目標(biāo)代碼段Ci；

步驟6) 將目標(biāo)代碼段Ci嵌入到一個特定輸入序列l(wèi)i(0≤i

步驟7) 在嵌入水印程序中輸入步驟6)中選取的輸入序列l(wèi)i(0≤i

步驟8) 選取特定的遍歷算法遍歷水印圖G, 從G中提取Wi；

步驟9) 選取特定的合并算法將水印分存值集合Wi還原為水印數(shù)W.

與通常的動態(tài)圖水印算法相比, 增強型動態(tài)圖水印算法提高了動態(tài)圖水印的性能.首先, 動態(tài)圖數(shù)據(jù)結(jié)構(gòu)以通過增加數(shù)據(jù)域保存水印信息的方式明顯提高了數(shù)據(jù)嵌入率； 其次, 動態(tài)圖的數(shù)據(jù)結(jié)構(gòu)仍在程序運行過程中動態(tài)構(gòu)建生成, 動態(tài)特性仍保持不變, 仍保留其隱蔽性、 抗攻擊性和防篡改等動態(tài)圖結(jié)構(gòu)的優(yōu)點.

2 增強型動態(tài)圖數(shù)據(jù)結(jié)構(gòu)

本文提出的增強型動態(tài)圖數(shù)據(jù)結(jié)構(gòu)針對鏈表結(jié)構(gòu)和二叉樹結(jié)構(gòu)的水印圖結(jié)構(gòu)進行改進.

定義1動態(tài)圖數(shù)據(jù)結(jié)構(gòu)以通過增加數(shù)據(jù)域保存水印信息得到的數(shù)據(jù)結(jié)構(gòu)稱為增強型動態(tài)圖數(shù)據(jù)結(jié)構(gòu)； 由基數(shù)k鏈表改進后的數(shù)據(jù)結(jié)構(gòu)稱為增強型基數(shù)k鏈表結(jié)構(gòu), 由PPCT結(jié)構(gòu)改進的數(shù)據(jù)結(jié)構(gòu)稱為增強型PPCT結(jié)構(gòu).

2.1 增強型基數(shù)k鏈表結(jié)構(gòu)

鏈表結(jié)構(gòu)包含n個節(jié)點, 每個節(jié)點由左指針域、 右指針域和數(shù)據(jù)域構(gòu)成. 其中： 右指針實現(xiàn)節(jié)點鏈接; 左指針用于防篡改, 可被設(shè)計成置換鏈表形式或基數(shù)k鏈表編碼形式； 數(shù)據(jù)域用于存儲采用大數(shù)分解算法得到的水印分存值. 圖1為增強型鏈表結(jié)構(gòu)示意圖.

圖1 增強型鏈表結(jié)構(gòu)示意圖Fig.1 Schematic diagram of enhanced linked list structure

圖2 增強型PPCT結(jié)構(gòu)示意圖Fig.2 Schematic diagram of enhanced PPCT structure

2.2 增強型PPCT結(jié)構(gòu)

增強型PPCT結(jié)構(gòu)中, 每個節(jié)點增加一個數(shù)據(jù)域, 用于存儲水印數(shù). 由于水印分存值個數(shù)即PPCT的葉節(jié)點數(shù)確定, 因此可從構(gòu)建的水印庫中隨機選擇具有相同葉節(jié)點數(shù)的增強型PPCT的任意一種拓?fù)浣Y(jié)構(gòu)表示同一水印數(shù), 以降低模式匹配攻擊的威脅. 圖2為增強型PPCT結(jié)構(gòu)示意圖.

3 實現(xiàn)過程

本文借助已有的實驗平臺Sandmark[9]實現(xiàn)包含嵌入水印和提取水印兩個過程.

3.1 嵌入水印

嵌入水印的流程主要有以下步驟：

2) 生成圖結(jié)構(gòu).從候選數(shù)據(jù)結(jié)構(gòu)中隨機選擇一個節(jié)點與水印分存值個數(shù)相等的圖結(jié)構(gòu), 即包含k個節(jié)點的水印圖G； 然后按照一定的算法將水印分存值Wi依次存入水印圖G的數(shù)據(jù)域內(nèi).

3) 分裂圖結(jié)構(gòu).將水印圖G分裂為若干水印子圖Gi(0≤i

4) 生成中間代碼.圖3為某子水印圖及其中間代碼.由圖3可見, 從水印圖的根節(jié)點進行深度優(yōu)先遍歷搜索, 生成過程如下： 以一個相反的拓?fù)漤樞蛟诿總€節(jié)點處都生成CreateNode( )指令； 生成m=CreateNode( )和n=CreateNode( )兩個節(jié)點后, AddEdge(n,m)添加鏈接指針連接節(jié)點m和n； 用SaveNode指令將子圖的根節(jié)點保存在一個全局的數(shù)據(jù)結(jié)構(gòu)中, 以保證子圖的所有節(jié)點在任何時刻均可全局訪問.

5) 生成目標(biāo)代碼并插入. 根據(jù)中間代碼生成目標(biāo)代碼, 圖4為某水印圖對應(yīng)的目標(biāo)代碼(以Java語言為例). 生成目標(biāo)代碼后, 先將被選中的可用標(biāo)記點替換成Watermark.create( ), 然后用一個覆蓋整個程序的混淆算法對該成員函數(shù)進行內(nèi)嵌化或者重命名該類名字等操作. 混淆和優(yōu)化防止攻擊者對水印代碼進行模式匹配攻擊.

圖3 某子水印圖(A)及其中間代碼(B)Fig.3 Sub watermark image (A)and its intermediate code (B)

圖4 水印圖對應(yīng)的目標(biāo)代碼Fig.4 Object code corresponding to watermark image

3.2 提取水印

首先輸入跟蹤過程中輸入過的密鑰序列, 水印圖G會在內(nèi)存的堆中構(gòu)建； 其次選取特定的遍歷算法從G中提取Wi； 最后通過特定的合并算法將水印分存值集合Wi合并得到原始水印數(shù)W.

4 結(jié)果分析

4.1 實驗環(huán)境

本文借助實驗平臺Sandmark進行實驗, 實驗硬件及軟件配置要求如下： 內(nèi)存為1 GB以上, 剩余磁盤空間為2 GB以上, 操作系統(tǒng)為Windows7 64 bit或Windows10 64 bit, 軟件為JDK,Eclipse,Sandmark.

4.2 實驗樣本

實驗選擇兩個軟件作為實驗的樣本程序： 計算器(Calculator)和tic-tac-toe(TTT). 樣本程序的特征參數(shù)列于表1.

表1 樣本程序的特征參數(shù)

圖5 不同數(shù)據(jù)結(jié)構(gòu)動態(tài)嵌入率對比結(jié)果Fig.5 Comparison results of dynamic embedding rate of different data structures

兩個樣本程序的大小成倍遞增, 計算器的規(guī)模較小, 而TTT則具有適中的規(guī)模. 因此, 該樣本程序具有代表性.

4.3 實驗結(jié)果分析

下面從數(shù)據(jù)嵌入率、 隱蔽性和抗攻擊性三方面分析增強型動態(tài)圖水印算法的性能.

4.3.1 數(shù)據(jù)嵌入率分析

不同數(shù)據(jù)結(jié)構(gòu)動態(tài)嵌入率對比結(jié)果如圖5所示. 由圖5可見： PPCT嵌入率最低, 極限小于0.5； IPPCT(intensify planted plane cubic tree)嵌入率約為基數(shù)k鏈表的1/2； 置換鏈表與基數(shù)k鏈表動態(tài)嵌入率的漸近趨勢一致, 在給定的根節(jié)點上置換鏈表的嵌入率小于基數(shù)k鏈表的嵌入率； 而EDGW結(jié)構(gòu)的嵌入率在任何節(jié)點情況下均約為10.6. 因為每個節(jié)點增加了一個數(shù)據(jù)域, 在通常的32位處理機中, 一個整型變量所占的空間是一個雙字, 其數(shù)據(jù)嵌入率約為10.6位/雙字, 與基數(shù)k鏈表編碼當(dāng)n=255時嵌入率約為1 bit/節(jié)點相比約為其30倍.基數(shù)k鏈表數(shù)據(jù)嵌入率隨節(jié)點數(shù)的增加呈對數(shù)形式增長, 而EDGW數(shù)據(jù)嵌入率則不再增長. 因此, 增強型水印算法的動態(tài)嵌入率有極大提升.

4.3.2 隱蔽性分析

定義2(水印算法隱蔽性)[10]假設(shè)Java程序中所有類型的字節(jié)碼指令集合S1={I0,I1,…,Im}, 嵌入水印后樣本程序為Pw,Pw中各種字節(jié)碼指令相對S1占比為R1={x0,x1,…,xm}, 一般Java程序中各種字節(jié)碼指令占比為R2={y0,y1,…,ym}.則Pw和程序之間的特征距離值定義為

(1)

其中x0,x1,…,xm分別為字節(jié)碼I0,I1,…,Im在嵌入水印后樣本程序Pw相對S1占比,y0,y1,…,ym分別為字節(jié)碼I0,I1,…,Im在未嵌入水印程序中占比.

本文使用Sandmark平臺上的字節(jié)碼查看工具, 根據(jù)Collberg等[11]統(tǒng)計的1 000多個Java程序中各種類型字節(jié)碼占比頻率, 得到嵌入水印后的水印程序Pw的字節(jié)碼指令的分布情況. 不同動態(tài)圖水印的隱蔽性數(shù)據(jù)列于表2.

表2 不同動態(tài)圖水印的隱蔽性

由表2可見, 增強型動態(tài)圖水印的隱蔽性與一般動態(tài)圖水印的隱蔽性類似. 在一般程序中生成一種數(shù)據(jù)結(jié)構(gòu)時都含有數(shù)據(jù)域, 而一般動態(tài)圖水印節(jié)點中只有指針, 易引起攻擊者的興趣. 增強型動態(tài)圖水印在保持動態(tài)圖水印原有優(yōu)點的前提下避免了該缺欠, 在增強型算法中生成的數(shù)據(jù)結(jié)構(gòu)不僅具有指針域而且還有數(shù)據(jù)域, 使生成這種結(jié)構(gòu)的代碼更像一段“正常”的程序.

4.3.3 抗攻擊性分析

軟件水印攻擊方法主要有加法攻擊(additive attack)、 減法攻擊(subtractive attack)及扭曲攻擊(distortive attack)[12]. 加法攻擊和減法攻擊較難實施, 前者可通過在嵌入水印時添加時間戳避免, 后者進行攻擊需要大量的靜態(tài)程序代碼分析； 扭曲攻擊中的保持語意變換攻擊是目前最常用、 最有效的攻擊方法. 因此, 為驗證變換后能否正確提取出水印數(shù), 實驗中對樣本程序進行混淆變換攻擊. 實驗數(shù)據(jù)列于表3, 其中“+”表示抗攻擊性良好, “-”表示識別過程失效. 由表3可見, 在多種混淆攻擊下, 除Split Classes識別過程失效, 其他動態(tài)圖水印抗攻擊型都表現(xiàn)良好. 增強型軟件水印結(jié)構(gòu)有助于建立一個更大的水印庫, 增加攻擊者獲得嵌入軟件中的軟件水印具體結(jié)構(gòu)的難度, 使攻擊者破解水印的代價變高. 在總體上, 增強型動態(tài)圖水印算法保持著較高的抗攻擊性.

表3 不同動態(tài)圖的抗攻擊性結(jié)果

續(xù)表3

綜上所述, 本文提出的增強型動態(tài)圖水印算法較通常的動態(tài)圖水印算法具有優(yōu)勢. 首先, 算法改進了動態(tài)圖數(shù)據(jù)結(jié)構(gòu), 增加數(shù)據(jù)域保存水印信息, 明顯提高了動態(tài)軟件水印的數(shù)據(jù)嵌入率； 其次, 增強型動態(tài)圖的數(shù)據(jù)結(jié)構(gòu)仍在程序運行過程中動態(tài)構(gòu)建生成, 動態(tài)特性仍保持不變， 仍保留了動態(tài)圖結(jié)構(gòu)的隱蔽性、 抗攻擊性和防篡改等優(yōu)點； 最后, 引入中間代碼生成技術(shù)增加了程序的可重定位性及復(fù)用性. 因此, 本文算法提高了動態(tài)圖水印的性能且復(fù)用性較好.