基于動態(tài)圖和線程關(guān)系的混合軟件水印算法

史寶會，徐振華，武 宏

（1.北京信息職業(yè)技術(shù)學(xué)院 計算機工程系，北京 100018；2.北京市經(jīng)濟管理學(xué)校 信息技術(shù)系，北京 100042）

基于動態(tài)圖和線程關(guān)系的混合軟件水印算法

史寶會1，徐振華1，武 宏2

（1.北京信息職業(yè)技術(shù)學(xué)院 計算機工程系，北京 100018；2.北京市經(jīng)濟管理學(xué)校 信息技術(shù)系，北京 100042）

針對單一動態(tài)圖水印算法以及線程水印存在的不足，為了提高軟件水印的安全性，提出一種基于動態(tài)圖和線程關(guān)系的混合軟件水印算法。首先采用動態(tài)圖水印算法將子圖生成代碼嵌入到程序中，然后充分利用線程隱蔽性恢復(fù)嵌入到線程關(guān)系矩陣的水印信息，最后對算法性能進行仿真測試。結(jié)果表明，本文算法充分利用了動態(tài)圖水印和線程關(guān)系的優(yōu)點，實現(xiàn)了優(yōu)勢互補，不僅提高了水印的數(shù)據(jù)率，而且增強了水印的抗攻擊性。

軟件水??；動態(tài)圖水??；線程水??；抗攻擊性

隨著計算機應(yīng)用的日益深入，軟件已經(jīng)滲透到多個領(lǐng)域，軟件產(chǎn)品的需要量急劇增加，但由于軟件具有成本高、研發(fā)周期長、易復(fù)制等特點，軟件版權(quán)問題也越來越嚴重[1]。尤其隨著計算機網(wǎng)絡(luò)技術(shù)的發(fā)展，信息傳播更加方便，軟件盜版日益猖獗，給企業(yè)和個人均帶來了經(jīng)濟損失，如何對軟件版權(quán)進行保護引起了人們的廣泛關(guān)注[2]。

針對軟件版權(quán)保護問題，大量學(xué)者投入了精力、物力和財力進行相關(guān)的研究，學(xué)術(shù)界和一些大型企業(yè)紛紛提出各種軟件版權(quán)保護技術(shù)。傳統(tǒng)軟件保護方法主要有軟件狗、加密、序列號等，這些方法比較簡單，但是不能進行盜版跟蹤，易被破解，無法對軟件版權(quán)進行保護，應(yīng)用范圍比較窄[3-4]。為了更好的對軟件版權(quán)進行保護，軟件水印技術(shù)應(yīng)運而生，其將用戶身份信息、版權(quán)信息等以水印形式預(yù)先嵌入到軟件中，而且嵌入的信息難以去除，如果發(fā)生版權(quán)糾紛時，版權(quán)所有者可以通過提取軟件中的水印以檢測非法復(fù)制以及盜版，來證明版權(quán)或追查盜版源[5-6]。軟件水印根據(jù)水印嵌入和提取方式的不同，可以分為靜態(tài)水印和動態(tài)水印兩種[7]。靜態(tài)軟件水印算法是將水印信息隱藏于軟件的靜態(tài)文本中，具有嵌入和提取速度快、簡單，但該水印易被混淆變換所破壞而失去作用，抗攻擊性很差，實用價值低[8]。相對靜態(tài)軟件水印，動態(tài)軟件水印算法將水印嵌入到軟件的動態(tài)執(zhí)行環(huán)境中，具有很高的隱蔽性，成為當(dāng)前主要的軟件版權(quán)保護技術(shù)。1999年，Collbergt等提出了一種動態(tài)圖水?。╠ynamic graph watermarking，DGW）算法，又稱CT算法[9]。CT算法的核心思想是：用一種圖的拓撲結(jié)構(gòu)來編碼水印數(shù)字，由于數(shù)據(jù)結(jié)構(gòu)中引入了對指針的操作，增加了混淆作用，可以有效抵抗各種攻擊，具有較強的魯棒性[10-12]，但是面對復(fù)雜多變的軟件攻擊，單一動態(tài)圖水印技術(shù)遠遠不夠；Nagra等給出了線程軟件水?。╰hread-based watermarking，TBW）算法，可以夠抵抗許多語義保持變換攻擊，同時對程序大小和運行時間的影響保持在一個可以容忍的范圍內(nèi)，但存在效率低下的缺陷[13]。

為了更好的保護軟件版權(quán)，提高軟件水印的安全性，綜合動態(tài)圖和線程關(guān)系的優(yōu)點，提出一種基于動態(tài)圖和線程關(guān)系的混合軟件水印算法，并采用仿真實驗對算法性能進行分析和測試。

1 軟件水印的工作原理

軟件水印算法工作過程包括兩個階段：水印嵌入和提取，軟件水印嵌入指采用一定的技術(shù)將版權(quán)信息嵌入到軟件中，產(chǎn)生包含水印信息的軟件；軟件水印提取是水印嵌入的逆過程，當(dāng)發(fā)生盜版問題時，通過一定的水印檢測技術(shù)提取原先嵌入的水印，以鑒別軟件版權(quán)，但為了更好的保護軟件版權(quán)，在水印嵌入之前，通常采用一定的加密技術(shù)對水印進行加密，即密鑰，綜合上述可知軟件水印的工作原理如圖1所示。

圖1 軟件水印算法的原理

2 動態(tài)圖水印和線程水印算法

2.1 動態(tài)圖水印算法

2.1.1 水印信息的編碼方式

在動態(tài)圖水印算法中，首先將水印信息編碼為圖結(jié)構(gòu)，然后將其存儲于軟件動態(tài)執(zhí)行過程中，當(dāng)前水印信息編碼方式主要有：基數(shù)K鏈表、排列圖、PPCT（planted plane cubic tree）等，每一種編碼方式均具有各自的優(yōu)點，相對于其他編碼方式，PPCT編碼的時間和空間復(fù)雜相對較低，數(shù)據(jù)嵌入率高，因此本文采用PPCT編碼方式[14-15]。

在二叉樹的基礎(chǔ)上，PPCT增加了一個指向最右葉結(jié)點的左指針，同時右指針指向根節(jié)點，這樣所有節(jié)點形成一個循環(huán)鏈表，PPCT結(jié)構(gòu)具體如圖2所示。

圖2 PPCT的結(jié)構(gòu)

PPCT結(jié)構(gòu)的枚舉規(guī)則：首先比較2個樹的左子樹，若它們深度相同，那么比較左子樹的左子樹，深度大的則序號大；若全部左子樹均相同，那么比較右子樹的左子樹，這樣就可以得到PPCT結(jié)構(gòu)的全部種類數(shù)目。對于N個節(jié)點數(shù)的PPCT結(jié)構(gòu)，就可以產(chǎn)生一個PPCT結(jié)構(gòu)來描述水印信息，這樣產(chǎn)生的編碼具有防篡改性、隱蔽性。

2.1.2 動態(tài)圖水印嵌入和提取步驟

Step1：輸入要嵌入的水印信息；

Step2：將水印信息表示成一個水印數(shù)，并轉(zhuǎn)化為PPCT結(jié)構(gòu)；

Step3：將圖 G 分割成幾個子圖 C0，C1，…，Cm；

Step4：編碼每個子圖G，并轉(zhuǎn)換成相應(yīng)的程序代碼；

Step5：根據(jù)預(yù)定的輸入序列 i0，i1，…，im，在程序標記位置嵌入C0，C1，…，Cm完成水印的嵌入；

Step6：提取水印時，執(zhí)行含有水印的程序，在輸入正確的預(yù)定序列后，程序會調(diào)用相應(yīng)的水印構(gòu)造代碼 C0，C1，…，Cm，并在堆內(nèi)存中動態(tài)生成圖 Gi，當(dāng)生成最后一個圖Gm時，根據(jù)水印分割算法，還原整個拓撲圖G，再將其轉(zhuǎn)化為對應(yīng)的原始水印信息。

動態(tài)圖水印嵌入和提取過程具體如圖3所示。

2.2 線程軟件水印算法

線程是一段完成某個特定功能的代碼，是軟件中單個順序的控制流。線程軟件算法的主要思想為：在軟件運行時的線程作為載體，將水印拓撲圖的糾錯碼信息嵌入到軟件中。在本文中將信息隱藏到線程關(guān)系矩陣中，線程關(guān)系矩陣是線程關(guān)系的矩陣表示形式，矩陣元素的值描述線程之間是否有關(guān)系。線程軟件水印算法工作流程如圖4所示。

圖3 動態(tài)圖水印算法的工作流程

圖4 線程水印算法的工作流程

3 動態(tài)圖和線程相融合的軟件水印算法

由于軟件盜版技術(shù)和攻擊技術(shù)日益猖獗，單一的動態(tài)圖水印算法和線程水印算法均存在各自的不足，難以實現(xiàn)軟件版權(quán)保護，為此，基于組合優(yōu)化理論，結(jié)合動態(tài)圖水印算法和線程軟件水印算法的優(yōu)點，提出一種混合軟件水印算法，其工作步驟如下：

1）先將需要嵌入的水印信息轉(zhuǎn)換成一個大素數(shù)W，其中大素數(shù)W為兩個較大素數(shù)的乘積，接著將水印數(shù)W用PPCT表示，然后用動態(tài)圖的CT算法將水印圖的子圖生成代碼嵌入到程序中。

2）將生成的PPCT水印圖用鄰接矩陣表示，對生成的鄰接矩陣先進行置亂處理，得到糾錯碼矩陣，最后將糾錯碼矩陣編碼到程序的線程關(guān)系矩陣中。

3）在水印圖的提取過程中，檢驗提取的水印是否滿足哈希映射，若不滿足則根據(jù)提取的糾錯碼矩陣恢復(fù)水印信息。

4 仿真實驗

為了測試本文混合軟件水印算法（DGW-TBW）的性能，在Pentium Dual-Core 2.80GHz CPU，4 GB RAM，Unix操作系統(tǒng)，采用VC++6.0編程實現(xiàn)仿真實驗。在相同條件下，采用動態(tài)圖水印算法（DGW）、線程水印算法（TBW）進行對比實驗，最終結(jié)果取10次實驗結(jié)果的平均值。

4.1 數(shù)據(jù)率對比

數(shù)據(jù)率代表了一個軟件水印算法的空間效率，是嵌入單位水印對目標程序內(nèi)容大小增加的數(shù)量，TBW、DGW以及DGW-TBW算法的數(shù)據(jù)率對比結(jié)果如圖5所示。從圖5可知，隨著節(jié)點的增加，所有算法的數(shù)據(jù)率都增加，但是在相同條件下，本文算法的數(shù)據(jù)率是最高的，空間利用效率最高，對比結(jié)果表明，DGW-TBW算法能夠容納更多的信息量，是一種性能良好的軟件水印算法。

圖5 數(shù)據(jù)率比較

4.2 空間過載量對比

TBW、DGW以及DGW-TBW算法的空間過載量如表1所示。從表1可知，相對于TBW、DGW算法，DGW-TBW算法的空間過載量相對較小，而空間過載量十分穩(wěn)定，結(jié)果表明，DGW-TBW算法不僅可以很好隱藏嵌入的信息，同時出現(xiàn)空間過載量的概率相當(dāng)小。

表1 不同算法的空間過載量（kB）比較

4.3 時間過載量對比

TBW、DGW以及DGW-TBW算法的時間過載量如表2所示。從表2可以明顯看出，DGW時間過載量比較大，時間復(fù)雜比較大，TBW次之，DGWTBW算法的時間過載量最小，減輕了軟件的負載，工作效率最高，可以較好的滿足軟件水印算法的在線檢測要求。

表2 不同算法的時間過載量（μs）比較

4.4 抗攻擊性能對比

TBW、DGW以及DGW-TBW算法的攻擊性能實驗結(jié)果如表3所示，其中“+”表示水印提取成功，“--”表示水印識別失敗。從表3可知，DGW-TBW算法不僅繼承了DGW算法各種抗攻擊特性，同時具有TBW算法的防篡改及水印自恢復(fù)能力，可以正確地識別出各種水印，具有更優(yōu)的魯棒性，應(yīng)用范圍更加廣泛。

表3 各算法的抗攻擊性能對比

5 結(jié)束語

在分析動態(tài)圖水印算法和線程水印算法不足的基礎(chǔ)上，為了提高軟件的安全性、以更好的保護軟件，提出了一種基于動態(tài)圖和線程關(guān)系的混合軟件水印算法，其綜合運用了動態(tài)圖水印和線程水印技術(shù)的優(yōu)勢，以克服單一水印算法存在的缺陷，并通過仿真實驗測度算法的性能。仿真結(jié)果表明，相對于動態(tài)圖水印算法和線程水印算法，本文算法不僅降低水印嵌入和提取的時間復(fù)雜度，而且增強了水印的魯棒性，具有更大的實際應(yīng)用價值。

[1]陳帆，和紅杰，王宏霞.用于圖像認證的變?nèi)萘炕謴?fù)水印算法[J].計算機學(xué)報，2012，1（35）:9-12.

[2]王俊祥，倪江群，潘金偉.一種基于直方圖平移的高性能可逆水印算法[J].自動化學(xué)報，2012，1（1）:88-96.

[3]趙春暉，劉巍.基于壓縮感知的交互支持雙水印算法[J].電子學(xué)報，2012，4（4）:681-687.

[4]霍耀冉，和紅杰，陳帆.基于鄰域比較的JPEG脆弱水印算法及性能分析[J].軟件學(xué)報，2012，9（23）:2510-2521.

[5]張秋余，孫媛，晏燕.基于分塊自適應(yīng)壓縮感知的可逆水印算法[J].電子與信息學(xué)報，2013，4（35）:797-804.

[6]王奇勝，朱長青，符浩軍.利用數(shù)據(jù)點定位的矢量地理數(shù)據(jù)數(shù)字水印算法[J].測繪學(xué)報，2013，4（42）:310-316.

[7]劉真，白韜韜，盧鵬.一種解密圖像無背景噪聲的加密全息數(shù)字水印技術(shù)[J].光學(xué)學(xué)報，2015，2（2）:88-95.

[8]劉竹松，陳平華，劉怡俊.混沌數(shù)字水印技術(shù)研究進展[J].計算機應(yīng)用研究，2011，1（28）:1-5.

[9]趙彥鋒.基于 Asmuth-Bloom體系的動態(tài)圖水印實現(xiàn)方案[J].現(xiàn)代電子技術(shù)，2011，34（5）:125-128.

[10]蔣剛毅，李文鋒，郁梅，等.H.264/AVC壓縮域魯棒視頻水印[J].光學(xué)精密工程，2015（1）：260-270.

[11]劉建蓉，秦拯，彭程.改進的動態(tài)圖水印技術(shù)編碼方案[J].計算機應(yīng)用研究，2011，28（2）:720-724.

[12]李淑芝，王顯珉.基于循環(huán)冗余校驗的動態(tài)圖軟件水印方案[J].計算機應(yīng)用研究，2012，29（3）:968-970.

[13]許金超，曾國蓀.一種基于線程關(guān)系的軟件水印算法[J].電子學(xué)報，2012，40（5）:891-896.

[14]王慧嬌，沙宗魯，軒愛成.基于PPCT和基數(shù)k的動態(tài)圖混合編碼方案[J].計算機工程與應(yīng)用，2010，46（25）:109-111.

[15]王億首，徐江峰.改進的PPCT混合編碼方案[J].計算機工程與應(yīng)用，2012，48（34）:107-111.

Hybrid software watermarking algorithm based on dynamic graph and thread relation

SHI Bao-hui1，XU Zhen-hua1，WU Hong2
（1.Department of Computer，Beijing Information Technology College，Beijing 100018，China；2.Department of Information，Beijing Economic Management School，Beijing 100042，China）

In order to improve the security of watermark，this paper proposes a hybrid software watermarking algorithm to solve the shortage of dynamic graph watermarking algorithm and thread-based watermarking，F(xiàn)irstly，the dynamic graph watermarking algorithm is used to improves the software watermarking dynamic bit rate，and then thread-based watermarking is used to recover of embedded watermark information from the thread connection matrix，finally the simulation experiments is used to test the performance of the algorithm.The results show that the proposed algorithm has the advantages of dynamic graph watermarking algorithm and thread-based watermarking to realize the complementary advantages,not only improves the watermark data rate,but also enhance the robustness of watermark.

software watermarking； dynamic graph watermarking；thread-based watermarking； resistance

TN702

A

1674－6236（2017）16-0175-04

2016-06-24稿件編號：201606188

史寶會（1964—），女，山東棲霞人，碩士，副教授。研究方向：網(wǎng)絡(luò)與信息安全管理測評，云計算與虛擬化技術(shù)應(yīng)用及云數(shù)據(jù)中心架構(gòu)等。