基于哈希不透明謂詞的JavaScript軟件水印算法

吳偉民 林水明 余國鵬 林志毅

基于哈希不透明謂詞的JavaScript軟件水印算法

吳偉民 林水明 余國鵬 林志毅

(廣東工業(yè)大學計算機學院 廣東 廣州 510006)

針對現(xiàn)有軟件水印算法存在性能開銷大或無法抵抗各類攻擊的缺點和鮮有在JavaScript源碼中實現(xiàn)的現(xiàn)狀，提出一種基于哈希不透明謂詞的JavaScript軟件水印算法。該算法構造一種新的基于除留余數(shù)法哈希映射不透明謂詞并將軟件水印信息嵌入不透明謂詞的表達式中，進而構造此不透明謂詞的永假基本塊嵌入程序中實現(xiàn)軟件水印。開發(fā)了一個基于此算法的JavaScript軟件水印系統(tǒng)。實驗證明，該算法能在增加較少的系統(tǒng)開銷的前提下有效抵抗各種常見的靜動態(tài)攻擊，同時還能提高水印的隱秘性和魯棒性。

不透明謂詞 除留余數(shù)法 軟件水印 JavaScript

0 引 言

軟件水印是軟件安全領域中的研究熱點。其原理是通過借助數(shù)字水印的相關思想，將水印嵌入到軟件中，以保護軟件的知識產(chǎn)權和取締各類非法盜版。目前研究的大部分軟件水印技術都是基于C/C++或Java等編譯型語言，對于諸如JavaScript(JS)等解釋型腳本語言的代碼安全技術研究相對較少，而JS軟件水印技術更加鮮見。隨著云計算技術的快速發(fā)展，以JS為代表的客戶端語言的使用更加廣泛，如何保護JS版權是一項具有現(xiàn)實意義和經(jīng)濟效益的研究課題。

目前保護JS源碼版權的主要研究有：Patrick等人使用基于堆圖的軟件胎記技術來保護JS代碼的安全性和版權[1]，并通過構建對比樹來提取軟件胎記，而缺點是構建對比樹的性能消耗很大，一般限制樹的深度小于3；Swati進行改進提出基于凝聚聚類和頻率子圖的動態(tài)JS軟件胎記技術[2]，然而動態(tài)軟件胎記存在只保護局部代碼和不適合交互性軟件的缺點。

在C/C++或Java軟件水印領域的研究主要包括：Myles和Gregory分別介紹了基于重新排列基本塊[3]和在軟件執(zhí)行時重新分配寄存器[4]的軟件水印算法，但此類算法的隱蔽性較差。為進一步提高水印的隱秘性，Nagra從程序并發(fā)入手，提出基于線程關系的軟件水印算法[5]，許金超等對其進行了改進[6]。然而，以上方法的抗干擾性較差。Collberg等人將擴頻技術應用于軟件水印中以提高抗干擾能力[7]，但此方法是個非盲水印算法，且它嵌入的水印比特率相當?shù)汀珣?zhàn)勇等對PPCT軟件水印編碼結構進行優(yōu)化并根據(jù)特定策略進行加密，實現(xiàn)提高軟件水印的隱秘性和防篡改[8]，但此方法通過加密等操作增加系統(tǒng)開銷，降低性能。同時，在軟件水印中引入不透明謂詞的研究有：Arboit使用不透明謂詞建立靜態(tài)軟件水印算法[9]，Myles對其進行動態(tài)擴展[10]，然而此算法通過模式匹配的方法提取水印，無法抵抗模式匹配攻擊；楊志剛將不透明謂詞用于防篡改軟件水印技術中能有效防止篡改[11]，但在水印嵌入位置問題上缺乏討論；高軍提出基于中國剩余定理和拉格朗日插值公式的不透明謂詞軟件水印[12]，但魯棒性和隱蔽性較差。

為了進一步提高水印性能、降低系統(tǒng)開銷和抵抗各類靜動態(tài)攻擊，本文提出一種基于哈希映射的改進構造不透明謂詞的方法，并將此方法應用于JS軟件水印中，提出一種基于不透明謂詞的軟件水印算法，同時對水印嵌入位置和水印內容進行討論，并結合JS的特性開發(fā)一個基于此算法的JS軟件水印系統(tǒng)。最后，將對算法性能、水印可靠性、隱秘性和抗干擾性等方面進行驗證與分析。

1 不透明謂詞的構造

不透明謂詞就是謂詞表達式在嵌入程序之前，其真值已經(jīng)確定(通常為布爾類型)，并廣泛應用于分支結構和循環(huán)結構的判斷條件中。目前構造不透明謂詞的方法主要有：利用同余方程[9]和基于改進混沌映射Logistic[13]的構造方法，而這些方法只能構造結果為布爾類型的不透明謂詞。據(jù)此，本文提出一種能構造具有多種結果狀態(tài)的不透明謂詞的方法，此方法是基于哈希映射機制將輸入從一數(shù)值空間映射成另一數(shù)值空間并輸出，具體的算法過程描述如下：

Step1 確定映射機制集F={F1,F2,…,FN}，其中Fi(i=1,2,…,N)必須滿足以下條件：

i) Fi(X)→Y。其中X∈{X1,X2,…,Xm}，Xj=(x1,x2,…,xt)是輸入向量，當t=1時，F(xiàn)i是一元映射機制，Y∈{y1,y2,…,yn}是輸出結果，也就是不透明謂詞的狀態(tài)集合。

ii) 將結果存放回Xin，重新選擇yi，重復i)的操作直至產(chǎn)生達到上限數(shù)量的結果為止。

本文以哈希函數(shù)構造方法除留余數(shù)法作為映射機制，實現(xiàn)構造具有n種狀態(tài)的不透明謂詞，具體的偽代碼如圖1所示。

圖1 基于除留余數(shù)法哈希函數(shù)的不透明謂詞構造算法

為了提高不透明謂詞抵抗逆向分析的能力，在具體實現(xiàn)中進行如下的優(yōu)化：將輸入序列存放在全局數(shù)組中，并通過引用的方式訪問其中的元素[14]；理論上可以使用所有滿足條件的映射機制相結合，提高不透明謂詞的復雜性；構造新型混合輸入序列，由兩個或兩個以上的數(shù)組元素進行代數(shù)運算操作形成新的輸入序列。

2 軟件水印算法

2.1 基于JS的軟件水印

軟件水印技術已廣泛應用于C、C++、Java等流行語言編寫的程序軟件當中，然而對客戶端語言諸如JavaScript(JS)腳本程序的水印技術研究卻很鮮見。JS作為熱門的腳本語言，廣泛應用于各類Web應用開發(fā)當中，再者JS腳本嵌入在網(wǎng)頁文件中，一般用戶都可以使用瀏覽器獲得源碼，這對網(wǎng)站信息的安全性、源代碼的保密性等都帶來更大的挑戰(zhàn)。因此，通過在JS代碼中嵌入水印來保證軟件著作權和防止盜版是一項具有現(xiàn)實意義和經(jīng)濟效益的研究課題。

2.2 不透明謂詞軟件水印算法

本文需要借助Antlr對JS程序源碼進行語法分析并收集源碼信息，包括源碼的三類基本塊：循環(huán)基本塊(包括while、for和do…while)、分支基本塊(包括if…else和switch…case)以及順序基本塊三類，基本塊在運行中都是順序執(zhí)行的。據(jù)此，將上文構造的不透明謂詞應用于JS軟件水印當中，基于不透明謂詞的JS軟件水印算法包括水印的嵌入和水印的提取兩個過程。

2.2.1 水印的嵌入算法

水印嵌入算法的過程描述如下：

Step1 初始化水印序列M和程序基本塊數(shù)N，其中M=m1,m2,…,mt是長度為t的數(shù)字水印，并且mi∈N+,0≤mi≤9。

Step2 選擇M中的一個位數(shù)mi，構造不透明謂詞P(mi)，使得P(mi)=mi。

Step3 構造永假基本塊FalseBlock，并且有：

其中if結構可以替換成while、do…while或for結構，IDi用于指示mi在M中的位置，code部分是永不執(zhí)行的代碼，其選擇方法主要有：

? 自定義生成：系統(tǒng)自動生成符合語法要求的垃圾代碼。

? 源程序的任意函數(shù)：在程序代碼中確定某一函數(shù)作為FalseBlock的代碼部分。

? 隨機選擇源程序的函數(shù)：每次構造FalseBlock的同時隨機確定某一函數(shù)做為代碼部分。此方法的優(yōu)點是：若代碼中多次出現(xiàn)同一代碼段容易引起攻擊者的注意，并且即使某一水印片段的函數(shù)被破解，不會影響其他水印片段。

Step4 確定水印片段mi嵌入的位置pi并將FalseBlock嵌入在基本塊pi之后，并將pi和唯一標識符IDi保存到秘鑰副本key(p)當中用于水印提取。其嵌入的策略主要有：

? 簡單策略。直接令pi=Ni/t，這是一種基于平均分配的思路，將水印片段均勻地分布在程序源碼當中。

? 隨機策略。包括可重復隨機策略和不可重復隨機策略：

a) 可重復隨機策略，pi=random(1～N)。

b) 不可重復隨機策略，pi=random(1～N),pi≠pj(j=1,2,…,i-1)。

Step5 不斷重復Step2-Step4直至所有水印片段嵌入完成。

其原理如圖2所示。

圖2 水印嵌入原理

2.2.2 水印的提取算法

水印提取算法的過程描述如下：

Step1 初始化已添加水印程序代碼S(M)，并對其進行源碼分析，提取出順序執(zhí)行基本語句塊Block1,…,Blockn。

Step2 根據(jù)嵌入算法保存的水印秘鑰副本獲嵌入位置pi。

Step3 提取基本塊Blockpi的首行if條件表達式并計算真值mi，并根據(jù)表達式中的IDi將其保存在M中的相應位置。

Step4 不斷重復Step2-Step3直至所有嵌入位置完成計算。

水印的提取過程比較簡單，關鍵是秘鑰副本必須安全保存。提取過程原理如圖3所示。

圖3 水印提取原理

3 實驗結果及其分析

3.1 實驗結果

借組VS2010 C#語言集成開發(fā)環(huán)境，本文實現(xiàn)了一個基于不透明謂詞的JavaScript腳本語言軟件水印系統(tǒng)。系統(tǒng)包括隨機生成水印序列、構造不透明謂詞、不透明謂詞水印的嵌入和提取等功能。使用Google公司開發(fā)的基準測試套件V8 Benchmark Suit version7作為測試用例，本系統(tǒng)成功實現(xiàn)對所有測試用例進行水印嵌入和提取，結果如圖4-圖6所示。

圖4 不透明謂詞生成結果

圖5 軟件水印嵌入結果

圖6 軟件水印提取結果

3.2 性能分析

負載性能 在程序中嵌入水印必定會增加系統(tǒng)的性能開銷，主要包括程序變大和運行時間延遲。本文提出的基于不透明謂詞軟件水印算法通過添加永不運行的垃圾代碼確保運行時間片變化不大，同時由于水印大小固定，因此本算法適合軟件規(guī)模較大的情況。五個基準測試嵌入水印前后的容量、運行時間結果如表1所示。結果顯示，水印嵌入前后測試用例在容量和運行時間的增長率僅為：4.92%、8.70%。

表1 嵌入水印前后程序容量和運行時間對比

隱蔽性 分支語句是JS程序經(jīng)常使用到的結構，通過將水印片段隱藏在帶不透明謂詞的分支結構中不容易引起攻擊者的注意，同時，構造分支語句的永假基本塊都是原程序的部分函數(shù)代碼，使得水印代碼在編碼風格、思維方式等方面都與程序的其他部分很相似。這樣能在一定程度上提高水印的隱秘性。

魯棒性 暴力破壞是相對于破解的另一種攻擊行為，在保留軟件功能的前提下修改程序代碼、結構等操作獲得相關權限，此時軟件水印也有可能受到干擾。不透明謂詞軟件水印算法將水印分割成相互獨立的片段并賦予唯一標識符，即使部分片段受到干擾，大部分信息仍能保留下來。并且水印提取算法是通過秘鑰文件中的位置表進行水印檢索和提取，能夠有效抵制模式匹配攻擊。如果通過非法修改順序基本塊的位置來破壞水印，程序將無法正確運行。通過對程序執(zhí)行標識符模式匹配修改和打亂程序基本塊攻擊操作，程序執(zhí)行結果和水印提取結果如表2所示。

表2 模式匹配攻擊和程序基本塊攻擊結果

3.3 安全性分析

3.3.1 靜態(tài)攻擊

靜態(tài)分析技術主要有識別循環(huán)、別名分析、控制流分析、切片技術等。由于不透明謂詞軟件水印算法是通過將水印保存在分支表達式中，因此對程序循環(huán)進行識別不會影響水印的安全性；該算法將源數(shù)據(jù)保存在全局數(shù)組并通過引用訪問數(shù)據(jù)，這樣能有效抵抗別名分析[14]；控制流分析和切片技術主要通過改變程序流程結構或者代碼執(zhí)行順序來破壞水印完整性，而本文提出的水印算法是將水印信息隱藏在不透明謂詞表達式中，水印信息并不依賴程序流程和執(zhí)行順序，也就是說表達式不被修改的前提下都能通過唯一標識符提取水印。通過對嵌入水印后程序進行控制流變形(如圖7所示)再次進行水印提取，所有測試結果都能成功提取正確水印。

圖7 控制流壓扁前后代碼變形情況

3.3.2 動態(tài)攻擊

攻擊者還能通過設置斷點進行調試、剖分和跟蹤，進而分析程序執(zhí)行路徑和流程結構等信息，對于分支結構條件表達式，攻擊者往往只注重條件的真假，忽視其中隱藏的信息，基于不透明謂詞的軟件水印算法能夠逃避這類攻擊。然而，反匯編工具能夠優(yōu)化刪除程序不被執(zhí)行的垃圾代碼。據(jù)此，本文通過全局數(shù)組存放數(shù)據(jù)，并對數(shù)據(jù)進行運算以增強不透明謂詞的隱蔽性，使得跟蹤變得更加困難。同時，還可以將永假基本塊改裝成不影響程序結果但又被調用執(zhí)行的代碼，這樣即使動態(tài)攻擊也無法實現(xiàn)對軟件水印的破壞。

4 結 語

本文提出一種基于不透明謂詞的軟件水印算法并開發(fā)一個基于此算法的JS腳本水印系統(tǒng)，通過實驗證實了該算法能在增加較少的系統(tǒng)開銷的前提下有效抵抗各種常見的靜動態(tài)攻擊，同時還能提高水印的隱秘性和魯棒性。下一步的工作是優(yōu)化和完善該算法，包括提高不透明謂詞的隱秘性和擴展水印的內容。

[1] Chan P P F,Hui L C K,Yiu S M.Heap graph based software theft detection[J].Information Forensics and Security,IEEE Transactions on,2013,8(1):101-110.

[2] Patel,Swati J,Tareek M Pattewar.Software birthmark based theft detection of JavaScript programs using agglomerative clustering and Frequent Subgraph Mining[C]//Embedded Systems (ICES),2014 International Conference on.IEEE,2014.

[3] Ginger Myles,Christian Collberg,Zachary Heidepriem,et al.The evaluation of two software watermarking algorithms[J].Software:Practice and Experience,2005,35(10):923-938.

[4] Wolfe G,Wong J L,Potkonjak M.Watermarking graph partitioning solutions[J].Computer-Aided Design of Integrated Circuits and Systems,IEEE Transactions on,2002,21(10):1196-1204.

[5] Nagra,Jasvir,Clark Thomborson.Threading software watermarks[C]//Berlin:Springer Heidelberg,2005.

[6] 許金超,曾國蓀.一種基于線程關系的軟件水印算法[J].電子學報,2012,40(5):891-896.

[7] Christian Collberg,Tapas Ranjan Sahoo.Software watermarking in the frequency domain: implementation,analysis,and attacks[J].Comput.Secur,2005,13(5):721-755.

[8] 湯戰(zhàn)勇,房鼎益,蘇琳,等.一種基于代碼加密的防篡改軟件水印方案[J].中國科學技術大學學報,2011,41(7):599-606.

[9] Arboit,Genevieve.A method for watermarking java programs via opaque predicates[C]//The Fifth International Conference on Electronic Commerce Research (ICECR-5).2002.

[10] Myles G,Collberg C.Software watermarking via opaque predicates:Implementation,analysis,and attacks[J].Electronic Commerce Research,2006,6(2):155-171.

[11] 楊志剛.基于常量編碼的防篡改軟件水印技術[D].吉林:吉林大學,2009.

[12] 高軍.軟件水印算法研究[D].四川:電子科技大學,2011.

[13] 蘇慶,吳偉民,李忠良,等.混沌不透明謂詞在代碼混淆中的研究與應用[J].計算機科學,2013,40(6):155-160.

[14] Udupa Sharath K,Saumya K Debray,Matias Madou.Deobfuscation:Reverse engineering obfuscated code[C]//Reverse Engineering,12th Working Conference on IEEE,2005.

A HASH OPAQUE PREDICATES-BASED SOFTWARE WATERMARKING ALGORITHM IN JAVASCRIPT

Wu Weimin Lin Shuiming Yu Guopeng Lin Zhiyi

(FacultyofComputer,GuangdongUniversityofTechnology,Guangzhou510006,Guangdong,China)

Because of the weakness of current software watermarking algorithms in high performance overhead or suffering from various attacks, and of being scarcely implemented in JavaScript source code, we proposed a new hash opaque predicate-based JavaScript software watermarking algorithm. By constructing a new kind of hash-mapping opaque predicate, which is based on the method of remainder of division operation, and embedding the watermark information of software into opaque predicate expression, the algorithm constructs the everlasting basic block of this opaque predicate and embedding it into program to implement software watermarking. We also developed a JavaScript software watermarking system which is based on this algorithm. Experiments proved that the algorithm can effectively resist various common static and dynamic attacks on the premise of less system overhead increase, as well as improve the invisibility and robustness of the watermark.

Opaque predicate Method of remainder of division operation Software watermark JavaScript

2014-12-09。廣州市科技計劃項目(2012Y2-00046，2013Y2-00043)；廣東高校優(yōu)秀青年創(chuàng)新人才培養(yǎng)計劃項目(2012LYM_0054)。吳偉民，教授，主研領域：可視計算，系統(tǒng)工具與平臺，代碼安全。林水明，碩士生。余國鵬，本科生。林志毅，講師。

TP309.7

A

10.3969/j.issn.1000-386x.2016.04.071