基于方程式逆序數的軟件水印算法

摘 要:針對方程式重排序等算法存在的程序運行速度、信息隱藏量等問題，提出基于方程式操作數系數排列逆序數的軟件水印算法。重新排列那些可以相互交換的操作數，使各操作數的系數按照一定次序排列。通過排列的逆序數和二進制數的一一對應關系來隱藏水印。這一方法無須向程序中添加任何代碼，并且能有效提高隱藏數據的效率，程序的規模和速度并不受影響。

關鍵詞:軟件水印; 映射字典; 排列; 逆序數

中圖分類號:TP309

文獻標志碼:A

文章編號:1001-3695(2010)02-0748-03

doi:10.3969/j.issn.1001-3695.2010.02.096

Software watermarking algorithm by inverse number of equation

JIANG Hua， SHA Zong-lu， XUAN Ai-cheng

(School of Computer Control， Guilin University of Electronic Technology， Guilin Guangxi 541004， China)

Abstract: Aiming at speed of the program and capacity of hidden information in traditional algorithms as equation reordering，this paper proposed a new algorithm based on inverse number of equation’s operand coefficient.Reordered the operands that could be swapped， so that arranged the coefficients of the operands with a certain order.Embedded the watermark in one-to-one relationship between the inverse number and the binary number. This method is that no code added to the program， and can effectively improve the efficiency of hidden data. The size and speed of the program is not changed.

Key words:software watermarking; mapping dictionary; permutation; inverse number

0 引言

源代碼是軟件公司的一項重要資產。保護其源代碼并同時證明公司對源代碼的所有權，對于軟件公司來說很重要。其中一個方法就是使用軟件水印。軟件水印是一種添加到源代碼中的特殊水印。軟件水印還有其他用途，如探測源代碼的變化、鑒定、完整性驗證[1]等。

文獻[2]提出把一些啞函數(dummy blocks)添加到源代碼中。這些啞函數被放到if-then-else等語句中，if的條件總是為假。啞函數永遠不會運行，但是啞函數的代碼塊可以用來隱藏水印。

文獻[3]提出在程序中添加一些啞指令(dummy instructions)，在映射字典中指令與二進制數一一對應，以此來隱藏水印，而這些指令不會影響程序的執行。以上兩種算法向程序中添加代碼很簡單，并且不會影響程序的結果，但是增加了程序運行負擔。

文獻[4]提出通過方程式操作數的重排序，結合二叉樹左右子樹的區別來隱藏水印信息。該算法無須額外添加代碼，但隱藏的信息量小。

針對以上算法的缺陷，本文提出了一種新的軟件水印算法，通過方程式操作數系數排列的逆序數來隱藏水印數據。其中，方程式操作數系數排列的逆序數與要隱藏的水印數據之間是一一對應的。該算法是靜態水印中的盲水印，水印可以從源代碼中直接提取而無須參照原始代碼[4，5]。

1 算法

1.1 算法思想

本文算法的主要思想是重新排列可以相互交換的操作數，使各操作數的系數按照一定次序排列，同時保留程序的原始功能。該算法選擇了一個特殊的指令，即數學方程式。

算法抽象圖如圖1所示。

算法可以分成四個主要步驟:a)水印編碼;b)映射字典;c)水印嵌入;d)水印提取。

1.2 水印編碼

在程序中，數學方程式非常普遍，每個程序中都有很多這種數學方程式。其中一些算術運算的操作數是可以交換的，本文把加法和乘法叫做可安全交換操作?？砂踩粨Q操作的操作數順序可以改變，同時方程式的結果不會改變。基于這一概念，一個數學方程式可以寫成不同的形式，卻具有相同的功能。在不改變方程結果的情況下，重新排列數學方程式的操作數，并把水印信息隱藏在操作數系數的排列順序中。

定義1 把方程式各操作數的系數看成不同的元素，若共有α1，α2，α3，…，αn這n個系數，把這n個不同的元素按照一定的次序排成一列(α1，α2，α3，…，αn)，即這n個元素的排列，并事先定義一個標準次序(這里規定由小到大為標準次序即α1<α2<α3<…<αn)，那么每一個方程式操作數系數的排列都有一個逆序數，即要隱藏的數據。

定義2 如果排列中元素個數為n，則算法取n-1位二進制塊編碼。

定義3 如果排列的元素個數為n，則這個排列所能表示的最大逆序數(即完全逆序時)為n(n-1)/2。

一個含有n個元素的排列，水印編碼是排列的逆序數所對應的n-1位二進制數，不夠n-1位時，在前面補零，直到補夠n-1位。

對于如下排列，其中α1<α2<α3<…<αn，逆序數為0

α1 α2 α3 …αn-1 αn(i)

利用冒泡排序的思想，先把最大的數αn與前面的αn-1交換位置，得到排列(ⅱ) 

a1a2…an an-1(ii)

排列 (ⅱ)的逆序數為1，再把αn與前面的αn-2交換位置，得到排列(iii)

α1 α2…αn αn-2 αn-1(iii)

排列 (ⅲ)的逆序數為2，按照這種方法操作，當最大數αn位于排列的最前端，不再移動αn，即得到排列(ⅳ)

αn α1…αn-3 αn-2 αn-1(iv)

排列 (ⅳ)的逆序數為n-1，按照同樣的算法思想操作，直到排列變成各元素從大到小的次序排列的完全逆序，此時的排列為(v)

αn αn-1…α3 α2α1(v)

排列 (v)的逆序數為n(n-1)/2，于是結束交換。

1.3 映射字典

映射字典通過程序中方程式的操作數系數的排列編碼水印。表1是系數個數為3時的映射字典，表2是系數個數為4時的映射字典。

算法根據排列中元素的個數取密鑰中的二進制塊進行編碼。每個方程式操作數系數構成排列的逆序數均與一個二進制數一一對應，即要隱藏的水印數據。圖2是密鑰中的二進制數和系數排列的映射關系。

1.4 水印嵌入

本文為了實現該算法，編寫了一個類似于編譯器的程序。程序讀入源代碼，并查找到方程式的位置。對于沒有方程式的程序代碼部分，該程序把從輸入文件中讀到的代碼寫入到輸出文件中。對于方程式，程序把信息隱藏到方程式中，并把已嵌入水印信息的方程式寫入到輸出文件中。

類似于其他編譯器，該程序分為三部分，即掃描器、分析器和輸出產生器。掃描器和分析器的用法與編譯器一樣;輸出產生器類似于編譯器中的代碼產生器，產生前面提到的輸出文件。

定義4 操作數系數按照標準次序排列的方程式為

T=(α1X1+α2X2+…+αmXm)+(β1Y1β2Y2…βnYn)+…其中:α1…αm和β1…βn是操作數的系數，且α1<α2<…<αm、β1<β2<…<βn，X1…Xm和Y1…Yn是操作數的變量部分。

要在下面的方程式(1)中隱藏水印:

(α1X1)×(α3X3)×(α2X2)+(β1Y1+β3Y3+β4Y4+β2Y2)(1)

其步驟如下:

a)在方程式(1)中有兩個可安全交換的操作:(α1X1)×(α3X3)×(α2X2)和(β1Y1+β3Y3+β4Y4+β2Y2)。如果把這兩個可安全交換操作的操作數系數按照標準次序排列，并用完全加括號的形式書寫這個方程式，則得到方程式(2)

(((α1X1)×(α2X2)×(α3X3))+((β1Y1)+(β2Y2)+(β3Y3)+(β4Y4)))(2)

b)在對方程式排序之后，把水印信息隱藏到方程式中。為了隱藏水印數據，把可安全交換操作的各操作數的系數分別組成排列，方程式(2)中的兩個可安全交換操作可以組成以下兩個排列:

α1 α2 α3 (vi)

β1 β2 β3 β4(vii)

每個排列可以隱藏的二進制位數等于排列中元素的總個數減去1。排列(ⅵ) 可以隱藏二位二進制數，排列(ⅶ)可以隱藏三位二進制數。方程式(2)總共可以隱藏五位二進制數。

c)把二進制塊I1I2I3I4I5(In為一位二進制數)隱藏到方程式(2)中。排列(ⅵ) 可以隱藏二位二進制數，排列(ⅶ)可以隱藏三位二進制數。首先確定把I1I2隱藏到排列(ⅵ)中，把I3I4I5隱藏到排列(ⅶ)中。I1I2對應的十進制數為d1，即對應的排列(ⅵ)的逆序數為d1。同理，與I3I4I5對應的排列(ⅶ)的逆序數為d2。

逆序數為d1時，可以由映射字典得到第一個可安全交換操作所對應的排列;同理，逆序數為d2時，第二個可安全交換操作對應另外一個排列。按照這兩個排列的次序得到嵌入水印后的方程式。

d)把嵌入水印數據后的方程式寫入到輸出文件。

文獻[4]提出的算法所能隱藏的水印數據的二進制位數等于方程式中可安全交換操作的個數。而本文的算法隱藏的二進制位數等于可安全交換操作中的操作數的個數，后者一定大于等于前者，因此，本文算法的信息隱藏量大。

1.5 水印提取

依次檢測方程式，如果一個方程式的可安全交換操作的操作數系數組成的排列不是標準次序，則從該方程式開始提取水印。

要從一個含有R個可安全交換操作的方程式中提取水印。首先把這R個操作的操作數系數按照其在方程式中的相對位置分別組成R個排列P1，P2，…，PR。這R個排列的逆序數分別為D1，D2，…，DR。根據定義2可知，若一個排列的元素個數為n，則該排列對應的二進制數是n-1位，即I1，I2，…，In-1。

根據排列的個數和各系數之間的相對位置到映射字典中查找與該排列相對應的二進制數，然后把這R個排列隱藏的二進制塊依次組合在一起，便得到隱藏的水印數據。

2 抗攻擊性

在提取水印時，方程式的系數為α1，α2，α3，…，αn(α1<α2<α3<…<αn)，當α1和αn之外的任何一個系數排在第一位則證明該方程式已遭到竄改等攻擊。根據算法思想，在最大數αn與α1交換之前的排列都是以α1開頭，兩者交換之后，直到排列完全逆序，排列都是以αn開頭。這種方法可以有效地檢測攻擊。

如果攻擊者能夠估計出水印的可能位置，則可以實施裁剪攻擊。例如剔除可能包含水印的部分代碼，或裁剪出不包含水印的部分代碼等。方程式是程序的重要組成部分，當按本文方法嵌入的水印遭到裁剪攻擊時，攻擊者裁剪掉包含水印的方程式部分，一個缺少方程式的程序很難完成它原有的功能，對攻擊者來說已沒有價值。

映射字典對攻擊者是保密的，即使攻擊者發現水印信息隱藏在方程式的系數排列中，也很難得到水印信息。

3 結束語

本文介紹了一種在源代碼中隱藏信息的新方法。重新排列那些可以相互交換的操作數，使各操作數的系數按照一定次序排列，同時保留程序的原始功能。系數排列的逆序數和要隱藏的二進制數構成一一對應的映射字典。這一方法無須向程序中添加任何代碼，并且能隱藏大量的水印數據;此方法還可以推廣到其他一些可以并行運行的程序指令中。

參考文獻:

[1]ZHU W， THOMBORSON C， WANG Fei-yue. A survey of software watermarking[C]//Proc of IEEE International Conference on Intelligence and Security Informatics. Germany: Springer-Verag，2005: 454-458.

[2]MONDEN A， IIDA H， MATSUMOTO K，et al. Practical method for watermarking Java programs[C]//Proc of the 24th IEEEAnnual International Computer Software and Applications Conference. Los Alamitos: IEEE Press， 2000: 191-197.

[3]ZEESHAN P， NOOR-UL-QAYYUM， YASIR M， et al. Semblance based disseminated software watermarking algorithm[C]//Proc of the 23rd International Symposium on Computer and Information Sciences.Piscataway: Inst of Elec and Elec Eng，2008.

[4]MOHAMMAD S S ，SAJAD S S. Software watermarking by equation reordering[C]//Proc of the 3rd International Conference on Information and Communication Technologies: From Theory to Applications. Piscataway: Inst of Elec and Elec Eng，2008:7-11.

[5]張立和，楊義先，鈕心忻，等. 軟件水印綜述[J].軟件學報，2003，14(2):268-277.