基于多特征的靜態軟件胎記提取算法

王曙燕，趙鵬飛，孫家澤

(西安郵電大學 計算機學院，西安 710121)

0 引言

隨著計算機技術及計算機網絡的迅猛發展，軟件已經成為日常生活中不可或缺的一部分，它不僅為生活帶來了極大的便利而且為社會帶來了數以億萬記的經濟效益。然而軟件作為一種數字產品在有著傳輸便利性的同時也為其版權保護帶來了相當的難度，許多別有用心的人可以輕易地在網絡上獲得目標軟件并且通過一些技術手段來將其破解并且以低廉的價格再發行出去，為軟件的開發者帶來重大損失。

程序胎記(BirthMark)這一概念較早是在由劍橋大學出版社出版的《程序識別》[1]一書中提到的。軟件胎記之所以被稱為“胎記”，是指在程序中一些“與生俱來”的東西，即使經過了軟件混淆或加密也會保持不變的東西。

而靜態軟件胎記提取技術與其他軟件抄襲檢測和軟件保護技術相比主要有以下兩點優勢：第一，其技術主要是對源碼或中間碼進行分析而無需額外插入任何代碼，減少人為插入代碼導致程序被惡意分析的可能性；第二，與動態提取軟件胎記技術相比，這種方法可以更全面地覆蓋軟件的執行路徑，而動態執行通常只能覆蓋軟件的一部分執行路徑，增強了胎記的可信度，并且若軟件需要頻繁交互，提取動態胎記所花費的時間與用戶體驗代價要比靜態胎記大得多。這兩方面的優勢使靜態軟件胎記技術在盜版檢測、代碼抄襲等方面更具有實用性。

通過程序胎記進行抄襲檢測主要可分為兩個步驟：第一步從程序中提取某些特征形成胎記；第二步通過比較兩個胎記來確定程序之間是否存在抄襲行為。文獻[2]提出了一種使用k-gram算法得到軟件胎記的算法，這種算法使用軟件的指令序列作為胎記提取的特征，首先提取Java程序中的字節碼指令序列，隨后使用k-gram算法對字節碼指令序列進行分割形成胎記，通過對這種胎記的對比來確定兩軟件之間是否存在抄襲行為;文獻[3]研究了利用程序的應用程序接口(Application Programming Interface, API)生成軟件胎記，通過提取不同層級包、類、方法的API調用形成API調用流圖和調用序列進而生成軟件胎記。

然而，以上方法存在以下兩個缺陷：1)使用k-gram算法產生的靜態軟件胎記的彈性較弱，因為該算法對軟件指令序列是機械切割分片的，所以由這種算法產生的胎記存在嚴重的語義丟失，導致其彈性弱。2)使用程序調用的API生成軟件胎記可信性較弱，由于這種胎記僅由程序的API特征生成，沒有考慮多特征，故而該胎記的可信性較弱，并且這種胎記也需要考慮源程序與待測程序之間是否是同一系統平臺編寫，故也存在一定的局限性。

文獻[4]研究了一種基于系統函數調用頻率與指令基本塊的軟件胎記的方法，并且驗證了其效果不弱于傳統的k-gram胎記，說明了使用多特征生成軟件胎記是可行的。

本文采用一種新的算法生成軟件胎記，可以克服原有程序胎記的缺點。在從程序中提取胎記時，綜合了API和指令序列兩方面特征，使提取到的胎記可信性比原有胎記更強，并且在提取軟件的指令序列特征使用了最長公共子串(Longest Common SubString, LCS)算法，使胎記的彈性比使用k-gram算法提取的胎記更強。

1 預備知識

一個完整的軟件對比程序主要使用以下兩個公式[5]：

(1)

其中：extracte是軟件胎記提取公式；BP表示程序P的胎記，由程序P通過特征提取函數所得到的。sim是兩軟件胎記的相似度計算公式[6]，程序P和程序Q之間的相似度則需要通過對比BP和BQ來得到。

1.1 軟件胎記的可信性和彈性

衡量一個軟件胎記的好壞有以下兩個標準。定義[2,7]如下：

定義1 軟件胎記的彈性。令P′表示對P使用語義保留的混淆技術生成的派生程序，BP為P的胎記，BP′為P′的胎記，sim()表示胎記的相似性計算函數，如果sim(BP,BP′)≥1-θ，則表明該軟件胎記具有很好的彈性，其中θ表示相似性閾值。

定義2 軟件胎記的可信性。令P和Q表示兩個完全獨立的軟件，如果sim(BP,BQ)<θ，則表明稱該軟件胎記具有很好的可信性。

1.2 最長公共子串算法。

為了方便說明算法，以下使用字符串來舉例，假定有兩個字符串A和B：

可發現其中有3個相同的長度大于1的字串。

表1 串A與串B的所有公共子串Tab. 1 All common substrings of string A and B

根據文獻[8-9]提出的一種計算最長公共子串的算法，對算法步驟描述如下：

記字符串A的長度為l1，字符串B的長度為l2，構建一個規模為l1×l2的矩陣，矩陣的值按照以下兩條規則填寫：

規則1 若矩陣該元素對應位置上兩字符不相同，則置矩陣元素值為0。

規則2 若矩陣元素對應位置上兩字符相同，且不在第一行、列上，則矩陣該元素值為其左上角元素值加1；若在第一行、列上，則將該元素值置為1。

按照以上規則填充矩陣，得到記錄了串比較信息的矩陣(圖1)。

圖1 LCS算法動態規劃矩陣 Fig. 1 Dynamic planning matrix generated by LCS algorithm

其中2,4,4三個數字表明了公共子串的長度，而從這三個元素出發向其左上角一直追溯到元素值為1的元素的橫縱坐標表明了這個公共子串在串A和串B中的起始位置。

1.3 k-gram軟件胎記提取算法。

k-gram軟件胎記(StaticK-gram Birthmark, SKB)提取算法最早是受到自然語言處理中n-gram算法[10]的啟發而產生的算法，其定義[11]如下：

定義3k-gram碎片集。記A={a1,a2,…,an}是一個序列，(aj+1,aj+2,…,aj+k)是A中的一個k-gram碎片，則序列A的k-gram碎片集記為seg(A,k)={(aj+1,aj+2,…,aj+k)|0≤j≤n-k}，其中k為k-gram算法中滑動窗口的長度。

定義4 SKB。記p為一個程序，A(p)為p的操作碼序列，那么p的靜態k-gram胎記為SKB(p,k)=seg(A(p),k)。

提取一個k-gram胎記的步驟為：

步驟1 提取程序中的操作碼序列；

步驟2 對操作碼序列進行k-gram分割得到長度為k的操作碼子序列，稱為k-gram碎片；

步驟3 將程序中k-gram 碎片的集合作為軟件胎記。

例如，對于Java程序字節碼指令序列{aload_0,iload_1,invokevirtual,aload_0,invokevirtual,return}，其k-gram胎記中k取值為3時軟件胎記為：

{(aload_0,iload_1,invokevirtual),(iload_1,invokevirtual,aload_0),(invokevirtual,aload_0,invokevirtual),(aload_0,invokevirtual,return)}

當我們計算兩個k-gram胎記的相似度時，其公式如下：

2 基于多特征的靜態軟件胎記提取算法

一個程序P可以提取的特征包括：API調用集合、程序控制流結構、程序指令序列、程序調用棧依賴關系等，在使用extracte函數時可以選擇提取其中的某些特征，本文所用的程序胎記的特征包含程序指令序列和API調用集合。

程序實質上是對數據的處理和變換，而一個程序的語義就體現在對數據的處理過程中，通過分析程序的指令序列，就可以很好地把握程序的功能和語義。而在現代軟件開發中，幾乎所有的程序都需要調用底層或其他人開發的程序，通過分析程序的API調用，可以快速地模糊定性一個程序的功用，這一點在大型的開發軟件中體現得尤為明顯。而想要通過分析程序的控制流結構或棧依賴關系來確定兩個程序是否相似時，不可避免地要用到圖或樹的對比算法，而這一類算法的時間復雜度是指數級的。

針對現有軟件胎記可信性弱、彈性弱的特點，本文提出一種新的軟件胎記提取算法。該算法首先將程序進行分析得到程序元信息，通過元信息提取程序的API調用集合和指令序列，再將API調用集合和指令序列作為輸出生成程序的程序胎記。通過構建比較模型，將源程序與可疑程序的程序胎記進行對比得到兩程序胎記之間的相似度，根據相似度判斷源程序與可疑程序之間是否存在抄襲行為。由以上算法提取的胎記記為多特征胎記(Multiple Feature Birthmark, MFB)。

圖2 融合雙特征的軟件胎記生成與比較模型 Fig. 2 Dual-feature-birthmark generation and comparison model

使用軟件胎記進行程序抄襲檢測可分為兩大步驟[12]。第一步是軟件胎記的生成，而一個軟件胎記的質量主要決定于如何對特征進行處理，針對不同的特征我們采用的特征提取算法是不同的，而對同一特征我們使用不同的提取算法提取出的胎記也是不同的。本文提出的多特征軟件胎記提取算法主要對以前的胎記有以下兩點改進；

一是本文在提取API和指令序列特征時都進行了解引用處理：對于API特征，若類A引用了類B，而類B引用了類C和D，那么類A的API特征不僅包含B，也會包含C和D。而對于指令序列特征；若一個方法MA的指令序列為a、b、c、d而b指令引用了方法MB，MB的指令序列為e、f、g，則最終MA的指令序列特征會被記錄為a、b、e、f、g、c、d。

二是本文在構建軟件胎記比較模型時沒有使用k-gram算法而使用了LCS算法。使用k-gram算法比較兩個指令序列時，是將兩個指令序列進行機械固定粒度切割然后比較相同碎片在總碎片中的占比；而LCS算法因為是比較指令序列，存在語義關系，兩個相同的片段保留了一定的語義信息。

2.1 Java程序的API特征提取

本文提出一種Java程序的API特征提取算法，描述如下：

步驟1 由用戶在工程P中選定待提取特征的類C，設定迭代深度為d，建立集合SetAPI用于存儲類C的引用類。

步驟2 找到類C除了本類和父類以外的所有引用類，將其添加至SetAPI中。

步驟3 遍歷SetAPI中所有的項，記遍歷過程中正在遍歷的類為Ctemp，若Ctemp是一個在工程P中存在的類，則將Ctemp除了本類和父類以外的所有引用類添加至SetAPI中，并將其標記為已添加。遍歷結束時d=d-1。

步驟4 重復步驟3，直到SetAPI中不存在未標記為已添加的類或d=0時，將SetAPI輸出。

例如，在迭代深度為3時，對以下Java程序進行API特征提取。

class A {

public void function(int index) {

new B().function(index);

}

}

class B {

public double function(int index) {

return 1+

new C().function(index)/new D().function(index);

}

}

class C {

public long function(int index) {

return 2*index;

}

}

class D {

public long function(int index) {

return 3-index;

}

}

2.2 Java程序的指令序列特征提取

步驟3 重復步驟2，直到d=0或Arrayinstruction中任意一項的指令序列中都不包含指向工程P中存在的方法的指令時，將Arrayinstruction輸出。

例如，圖2中的類A,B,C,D中的function方法操作序列碼分別為：

A.function(){new,dup,invokespecial,iload_1,invokevirtual,pop2,return}

B.function(){lconst_1,new,dup,invokespecial,iload_1,invokevirtual,new,dup,invokespecial,iload_1,invokevirtual,ldiv,ladd,l2d,dreturn}

C.function() {iconst_2,iload_1,imul,i2l,lreturn}

D.function() {iconst_3,iload_1,isub,i2l,lreturn}

在迭代深度為3時，最終得到類A中function方法的指令序列特征為：

public void A.function(int index) {

new,dup,invokespecial

void () {

//B的構造函數

aload_0,invokespecial,return

}

iload_1,invokevirtual

public double B.function(int index) {

lconst_1,new,dup,invokespecial

void () {

//C的構造函數

aload_0,invokespecial,return

}

iload_1,invokevirtual

public long C.function(int index) {

iconst_2,iload_1,imul,i2l,lreturn

}

new,dup,invokespecial

void () {

//D的構造函數

aload_0,invokespecial,return

}

iload_1,invokevirtual

public long D.function(int para1) {

iconst_3,iload_1,isub,i2l,lreturn

}

ldiv,ladd,l2d,dreturn

}

pop2,return

}

2.3 多特征胎記相似度計算方法

根據文獻[13]提出的一種BP(Back Propagation)神經元輸出模型，提出當待比較程序P和Q提取了n方面特征時，其相似度計算公式：

(2)

(3)

其中，API相似度的計算公式[14]為：

(4)

在比較兩個程序胎記的指令序列特征時：

本文提出一種計算指令序列相似度的方法：

步驟1 用戶輸入本次處理的閾值為threshold，對源程序和可疑程序的指令序列，使用LCS算法尋找源程序和可疑程序的公共子串，將所有長度大于閾值的公共子串記錄到集合Set中，其中Seti記錄了一個子串的長度lengthi，其規模為n。

(5)

綜上，最終得到比較兩個提取了API和指令序列特征的軟件胎記的比較公式：

(6)

其中：w1,w2分別為相似度在API特征和在指令序列特征方面的權重。

2.4 根據軟件胎記的相似度判定是否抄襲

檢測程序P和程序Q是否存在盜版現象[15]步驟如下：

步驟3 設置檢測閾值γ1、γ2，其中γ1>γ2。若simP,Q≥γ1，認為兩程序之間是拷貝關系；若simP,Q≤γ2，認為兩程序之間是獨立開發；否則將認定為無法判定。最后輸出兩程序盜版檢測結果。

對于盜版程序Q：

class FakeA {

public void f(int i) {new FakeB().f(i);}

}

class FakeB {

public double f(int i) {

return 1+

new C().function(i)/new D().function(i);

}

}

class C {

public long function(int i) {return 2*i;}

}

class D {

public long function(int i) {return 3-i;}

}

3 實驗驗證

3.1 實驗對象及環境

實驗將驗證多特征胎記的可信性和彈性，并與SKB進行對比。實驗在Windows 7系統下完成，迭代深度d=3，API和指令序列的特征權重分別為w1=0.3,w2=0.7，修正參數α=8，使用多特征胎記時LCS算法閾值為threshold=5，使用SKB將k-gram算法粒度為gram=5。設置檢測閾值γ1為0.8，γ2為0.5。

本文實驗使用Junit4.0-4.5，checkstyle4.2-5.2，findbugs4.2-4.7，soot-2.5.0共計19個jar包，6 720個類用于驗證比較，其中Junit、checkstyle、findbugs均為代碼測試工具，soot為代碼分析工具。

3.2 多特征胎記的可信性驗證

本文選擇驗證Junit、checkstyle、findbugs不同大小版本之間的同一類的相似度和Junit、checkstyle、findbugs與Soot之間隨機抽取的類之間的相似度。同一程序的不同版本，對比版本1和版本2之間的軟件胎記，應該得到較高的相似度；而由兩支團隊分別獨立開發的程序，對比其軟件胎記應得到較低的相似度。

以下用首字母代稱驗證程序。根據可信性定義，當兩程序是獨立開發的程序時，其胎記應不同，得到的相似度應低于檢測閾值的下界。由實驗數據可知，多特征胎記在判定兩個獨立開發的程序時，得到的相似度均低于0.5，即判定為獨立開發；而對于同一程序的不同版本之間對比得到的相似度均高于0.8，即判定為抄襲程序。這說明由本文提出的軟件胎記具有可信性。

表2 使用多特征胎記得到的相似度Tab. 2 Similarity obtained by using multiple feature birthmark

3.3 在可信性上與SKB的對比

本次實驗驗證多特征胎記和SKB對相似程序和獨立開發程序的識別效果。

Junit4.0到Junit4.5版本之間BaseTestRnuuer.class是一個幾乎沒有改動的類(以下簡稱BTR類)，將Junit4.0版本的BTR類作為源程序，分別與Junit4.0到4.5版本的BTR類進行比對，首先使用多特征胎記進行比對，再使用SKB進行比對，由兩種胎記對同一對類同程序的檢測結果均為判定抄襲，說明多特征胎記在檢測類同程序上的效果是不弱于SKB的。由兩種胎記得到的相似度對比如圖3所示。

Junit和Soot是兩個完全獨立開發的程序，將Soot-2.5.0-ByteType.class作為源類，分別與Junit4.0到4.5版本的Version.class類進行比對，首先使用多特征胎記進行比對，再使用SKB進行比對，由兩種胎記得到的相似度對比如圖4。

圖3 兩種胎記在檢測類同程序上的表現 Fig. 3 Performance of two kinds of birthmarks in detecting similar programs

圖4 兩種胎記在檢測獨立開發程序上的表現 Fig. 4 Performance of two kinds of birthmarks in detecting independent development programs

3.4 軟件胎記的彈性驗證

使用代碼混淆工具proGuard對程序進行加密混淆，記源程序中的類C經過proGuard混淆過的類為C′，對比由C和C′產生的胎記，應得到較高的相似度。本次實驗選取Junit中6個類與其對應混淆類分別使用多特征胎記和SKB進行對比，相似度對比如表3。

SKB在對比C和C′時相似度平均值為0.52，多特征胎記對比C和C′時相似度平均值為0.84，可以看出多特征胎記在彈性上優于傳統的SKB。

表3 兩種胎記的彈性對比Tab. 3 Resilience comparison of two kinds of birthmarks

圖5 兩種胎記的彈性對比測試 Fig. 5 Resilience of two kinds of birthmarks

4 實驗結果分析

實驗首先驗證了多特征胎記的可信性，驗證類同程序得到較高的相似度，驗證獨立開發程序得到較低的相似度，以上兩點說明使用多特征胎記進行抄襲檢測，其結果是可靠的。

隨后對比了多特征胎記與SKB在抄襲檢測上的表現，在對比抄襲程序和獨立開發程序時，兩種胎記得到的結論是一致的。這說明多特征胎記在抄襲檢測方面的可信性不弱于SKB。

最后驗證了多特征胎記的彈性，由多特征胎記得到源程序C與其迷惑程序C′的相似度均值為0.84，而由SKB得到C與C′之間相似度均值只有0.52。由這兩種胎記得到的檢測結果完全不同，由SKB得到的相似度我們只能得出兩程序的關系是無法判定的，而由多特征胎記得到的相似度可以得出兩程序之間存在抄襲關系。這說明多特征胎記在檢測經過迷惑的抄襲程序上表現要優于傳統的SKB，即多特征胎記的彈性比SKB要強。

5 結語

本文提出了使用兩個特征生成的多特征軟件胎記MFB，MFB能夠直接分析Java的字節碼而無需使用源代碼。通過提取程序中的API調用信息和指令序列信息來生成軟件胎記，驗證了多特征融合生成軟件胎記這一模型的有效性。本文提出的算法主要側重于克服SKB彈性弱的缺點，通過更換指令序列特征提取算法來克服由k-gram算法所帶來的語義丟失問題，使得胎記的彈性增強，并且加入其他特征保證胎記的可信性，因此MFB對于語義保留的代碼混淆和抄襲有很好的檢測能力。下一步可以嘗試融合其他方面特征來生成可信性與彈性更優的多特征胎記。

參考文獻(References)

[1] GROVER D. Program Identification [M]. London：Cambridge University Press,1989: 119-150.

[2] MYLES G, COLLBERG C.K-gram based software birthmarks [C]// Proceedings of the 2005 ACM Symposium on Applied Computing. New York: ACM, 2005: 314-318.

[3] PARK H, CHOI S, LIM H, et al. Detecting Java theft based on static API trace birthmark [C]// Proceedings of the 3rd International Workshop on Security: Advances in Information and Computer Security. Berlin: Springer, 2008: 121-135.

[4] 張杏,徐江峰,李曉陽. 基于系統函數調用頻率與指令基本塊的軟件胎記[J].計算機工程,2016,42(10):86-90.(ZHANG X, XU J F, LI X Y. Software birthmark based on system function call frequency and instruction basic block [J]. Computer Engineering, 2016,42(10): 86-90.).

[5] 王勇.基于Java平臺的靜態軟件胎記技術研究[D].鄭州：信息工程大學,2013: 4-6.(WANG Y. Study on static software birthmarking based on Java platform [D]. Zhengzhou: Information Engineering University, 2013: 4-6.)

[6] 黃壽孟,高華玲,潘玉霞. 軟件相似性分析算法的研究綜述[J]. 計算機科學,2016,43(S1):467-470.(HUANG S M, GAO H L, PAN Y X. Summary of research on similarity analysis of software [J]. Computer Science, 2016,43(S1): 467-470.)

[7] 范銘,劉均,鄭慶華,等. 基于棧行為動態胎記的軟件抄襲檢測方法[J]. 山東大學學報(理學版),2014,49(9):9-16.(FAN M, LIU J, ZHENG Q H, et al. SODB: a novel method for software plagiarism detection based on stack operation dynamic birthmark [J]. Journal of Shandong University (Natural Science), 2014, 49(9): 9-16.)

[8] 王開云,孔思淇,付云生,等.兩種基于雙向比較的最長公共子串算法[J].計算機研究與發展,2013,50(11):2444-2454.(WANG K Y, KONG S Q, FU Y S, et al. Two longest common substring algorithms based on bi-directional comparison [J]. Journal of Computer Research and Development, 2013, 50(11): 2444-2454.)

[9] 張毅超,車玫,馬駿. 求最長公共子串問題的算法分析[J]. 計算機仿真,2007,24(12):97-100.( ZHANG Y C, CHE M, MA J. Analysis of the longest common substring algorithm [J]. Computer Simulation, 2007, 24(12): 97-100.)

[10] 馬志強,張澤廣,閆瑞,等.基于N-Gram模型的蒙古語文本語種識別算法的研究[J].中文信息學報,2016,30(1):133-139.(MA Z Q, ZHANG Z G, YAN R, et al. N-Gram based language identification for Mongolian text [J]. Journal of Chinese Information Processing, 2016, 30(1): 133-139.)

[11] 陳林,劉粉林,蘆斌,等.基于k-gram頻數的靜態軟件胎記[J].計算機工程,2011,37(4):46-48.(CHEN L, LIU F L, LU B, et al. Static software birthmark based onk-gram frequency [J]. Computer Engineering, 2011, 37(4): 46-48.)

[12] 田振洲,劉烴,鄭慶華,等.軟件抄襲檢測研究綜述[J].信息安全學報,2016,1(3):52-76.(TIAN Z Z, LIU T, ZHENG Q H, et al. Software plagiarism detection: a survey [J]. Journal of Cyber Security, 2016, 1(3): 52-76.)

[13] 喻寶祿,段迅,吳云. BP神經網絡數據預測模型的建立及應用[J].計算機與數字程,2016,44(3):482-486.(YU B L, DUAN X, WU Y. Establishment and application of data prediction model based on BP neural network [J] . Computer and Digital Engineering, 2016, 44(3): 482-486.)

[14] 王廣南.基于系統調用依賴圖的程序相似性研究[D].長沙:湖南大學,2009:27-29.(WANG G N. Similarity of programs based on system call dependency graphs [D]. Changsha:Hunan University, 2009: 27-29.)

[15] SCHULER D, DALLMEIER V, LINDIG C. A dynamic birthmark for Java [EB/OL]. [2017- 03- 02]. https://www.st.cs.uni-saarland.de/birthmarking/schuler-ase-2007.pdf.

This work is partially supported by Science and Technology Department of Shaanxi Province (2017GY-092).

WANGShuyan, born in 1964, Ph. D., professor. Her research intererts include software testing, data mining.

ZHAOPengfei, born in 1993, M. S. candidate. His research intererts include computer software and theory.

SUNJiaze, born in 1980, Ph. D. candidate, associate professor. His research intererts include intelligent optimization algorithm.