史寶會(huì)，徐振華，武 宏

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

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

史寶會(huì)1，徐振華1，武 宏2

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

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

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

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

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

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

1 軟件水印的工作原理

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

圖1 軟件水印算法的原理

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

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

2.1.1 水印信息的編碼方式

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

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

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

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

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

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

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

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

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

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

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

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

2.2 線程軟件水印算法

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

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

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

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

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

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

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

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

4 仿真實(shí)驗(yàn)

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

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

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

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

4.2 空間過載量對(duì)比

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

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

4.3 時(shí)間過載量對(duì)比

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

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

4.4 抗攻擊性能對(duì)比

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

表3 各算法的抗攻擊性能對(duì)比

5 結(jié)束語(yǔ)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[15]王億首，徐江峰.改進(jìn)的PPCT混合編碼方案[J].計(jì)算機(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稿件編號(hào)：201606188

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