一種基于圖的程序行為相似性比較方法

摘 要:針對目前的軟件盜版現象，在沒有軟件源代碼的情形下提出一種程序相似性的比較方法。該方法是運用程序系統調用之間的參數依賴關系組成依賴圖，對程序行為進行描述;在此基礎上定義了一種動態程序胎記，用它比較兩個功能類似的應用程序。最后的試驗數據表明，該方法能夠有效地檢測出相似程度不一的各組程序之間的相似度，具有一定的可信度和適用性。

關鍵詞:軟件剽竊; 圖; 系統調用; 動態軟件胎記; 相似性

中圖分類號:TP311.5

文獻標志碼:A

文章編號:1001-3695(2010)02-0532-05

doi:10.3969/j.issn.1001-3695.2010.02.036

Approach for measuring software similarity based on graphs

CHEN Hao， WANG Guang-nan， SUN Jian-hua

(Dept. of Computer Science Technology， Institute of Computer Communication， University of Hunan， Changsha 410082，China)

Abstract:View of software piracy， this paper proposed an approach for measuring software similarity without sourcecode. It created dependence graphs to specify relationships between system call arguments for describing program behavior， based on which defined an dynamic software birthmark. It could be used to measure the similarity of two same-purpose applications. Experimental results indicate that the approach is effective in detecting similarity between two programs in groups of varying degrees similar， which proves its certain degree of credibility and applicability.

Key words:software theft; graphs; system call; dynamic software birthmark; similarity

0 引言

對越來越多的被剽竊的軟件無源代碼發布，程序動態胎記技術近年來在各項剽竊軟件與源程序的相似性檢測技術中逐漸成為一個研究熱點。它主要是從表示程序運行時的動態行為的信息中提取程序特征，因此無需源代碼，并且面對程序模糊或反編譯等常見的剽竊痕跡隱藏技術能很好地保存原程序的特征信息[1]。在提取動態胎記的許多方法中，系統調用序列是經常被用到的一個[1~4]。因為其數目有限，且各操作系統的系統調用函數版本間變化非常小，對其進行分析，數量適中穩定;但是許多程序的系統調用序列由于其數量巨大，很多研究者并不考慮其參數而直接使用函數本身在程序運行時的執行次序或者出現的頻率作為程序行為特征[1，2，4]。由于其程序特征提取不明顯，只能適應于比較兩個相似程度很大的程序，并且容易受到程序每次運行時系統調用執行次序差異的影響以及添入其他系統調用等偽裝技術的攻擊，盡管后者所花費的代價將很大。

程序行為不僅體現在不同系統調用間的先后次序上，即使同一個系統調用由于其所帶參數的不同也會讓程序表現大不一樣，因此準確分析程序行為必須充分考慮系統調用參數。本文對于程序相似性研究的主要貢獻在于挖掘系統調用參數之間的依賴關系[5]，將這種關系用圖來表示，這樣能夠比較準確地描述程序的行為特征。本文的主要內容有以下幾點:

a)程序行為的圖形化描述以及基于行為子圖的程序特征胎記的提取。

b)程序相似性比較算法及兩個程序相似度的定義。

c)性能測評實驗對于本文所提出的方法可信度以及健壯性的證明。

1 關于程序胎記的一些概念

定義1 程序復制關系[1，2，6~8]。假設Prog是一組給定的程序集，令“≡cp”表示程序集Prog之間的相等關系，使得對于P，Q∈Prog，如果Q是P的一個副本，那么P≡cpQ。有關程序間幾種具體的復制關系的詳細描述見參考文獻[1，2，6，7]。對于程序復制關系有如下屬性:

性質1 對于程序P，Q∈Prog，有反身性P≡cpP，對稱性P≡cpQQ≡cpP，傳遞性P≡cpQ∧Q≡cpRP≡cpR。

上述屬性直接由程序復制關系而來，另外，如果Q是P的一個拷貝，那么Q的外部實現規范應該與P一樣。

性質2 假設spec(p)為實現程序P所遵從的(外部的)規范，那么將有如下推導關系:P≡cpQspec(P)=spec(Q)。

需要注意的是性質2的逆命題并不一定成立，不同的程序實現可能會遵從相同的程序規范。接下來，給出程序動態胎記的定義:

定義2 動態胎記[1，2，8]。對給定的程序P、Q，輸入I以及復制關系“≡cp”，假設f(P，I)為用一種特定的方法從給定輸入I的程序P中提取出的一組特征集，那么f(P，I)可以稱為在滿足如下所有條件時，程序P在復制關系“≡cp”下的一種動態胎記。

條件1f(P，I)僅僅只從程序P本身在給定的輸入I下運行時得來。

條件2 P≡cpQf(P，I)= f(Q，I);同樣反過來不一定成立。

條件1意味著提取胎記并不需要其他信息(如用戶自己編寫代碼)來實現;條件2說明胎記f(P，I)只是程序相似關系的一種證明，而不是標記。但是如果f(P，I)≠ f(Q，I)，那么可以肯定P≠Q。這樣，能確定Q一定不是P的一個拷貝。

當定義了一個胎記時，理想情況下，希望它具有如下的性質:

性質3 保留性[1]。如果P′是從程序P經過任何一種程序變換得到的，那么f(P′，I)=f(P，I)。

性質4 區別性[1]。對于程序P和Q，以及spec(P)=spec(Q)，如果P和Q是獨立實現的，那么f(P，I)≠f(Q，I)。

從性質1和2可以看到，性質1確切說明胎記的保留屬性對于程序變換的抵抗性。可以假設這種程序變換是黑客們試圖通過對程序作保留語義的模糊變換而改變胎記以隱藏程序剽竊的痕跡，如程序模糊技術。性質2則是說明胎記的區別性，即使程序P和Q實現時所遵從的外部規范是一樣的，但如果它們是獨立實現的，則提取的胎記必然不同。一般而言，兩個獨立的程序細節幾乎從來不會完全一樣。然而大量的研究表明，不排除P、Q是只有幾十行的小程序，那么盡管P、Q是獨立實現的，但是提取的胎記特征有可能一致[7]。這表明:程序胎記有一定的適應范圍，并且從理想意義上，提取的胎記應該完全滿足上述的兩性質。然而由于程序的各種實現方法和變換，在現實中很難做到提取的胎記同時完美地符合上述兩種性質。本文工作是如何有效地提取程序胎記以盡可能地符合這兩種性質。

2 程序胎記的提取

2.1 圖的基本概念

圖是一種普遍且強大的數據結構，不論對圖形作何種轉換、旋轉，或把它轉變成它的鏡像圖像，圖的數學意義仍然不變。因此，本文提出用圖來表示系統調用及各參數間的依賴關系。先回顧一下需要用到幾個圖的基本概念。

定義3 圖[9]。本文用一個四元組來表示圖，用Lv和Le分別表示圖中節點與邊的屬性，即G=(V，E，U，W)。其中:

V為有限的節點集;

E≤V×V是邊集;

U: V→Lv是定義節點屬性的函數，

W: E→Le是定義邊屬性的函數。

定義4 子圖[9]。給定一個圖G=(V，E，u，v)，它的一個子圖可以這樣表示:S=(Vs，Es，Us，Ws)。其中:

VsV; Es=E∩(Vs×Vs);

Us和Ws則分別為定義節點屬性和邊屬性的函數，如下

Us(v) =U(v)

如果 v∈Vs，

undefined否則

Ws(e) =W(e)

如果 e∈Es

undefined否則

定義5 最大共同子圖[9]。給定圖G1、G2，如果G既使是G1的子圖也是G2的子圖，并且G1和G2中不存在其他子圖的節點數比G大，那么G是G1和G2的一個最大共同子圖，本文用mcs(G1，G2)表示。

定義6 基于最大共同子圖的圖的相似度。給定兩個非空圖G1和G2，以及它們的最大共同子圖mcs(G1，G2)，那么它們之間的距離[9，10]可以計算如下:

D(G1，G2)=1- |mcs(G1，G2)|/max(|G1|，|G2|)

其中:|G1|和|G2|分別表示G1，G2的節點數，|mcs(G1，G2)|表示最大共同子圖的節點數。那么圖G1與G2的相似度可以定義為

S(G1，G2)=1-D(G1，G2)=|mcs(G1，G2)|/max (|G1|，|G2|)

假如G1的節點數為5，G2的節點數為4，最大共同子圖節點數為3，則D(G1，G2)=0.4，G1與G2的相似度S(G1，G2)=0.6。

2.2 程序行為的語義描述與圖形化建模

不論程序的源代碼或編譯后的指令有什么樣的改變，也不論編譯器的版本或者編譯的方式是否不同，在CPU中運行的代碼總是無法改變的。程序在運行時，任何一個涉及到與進程環境交互的行為都需要進程調用相應的系統服務函數[5]。除了前面提到的各種優點，對于筆者的研究工作來說，截取程序系統調用序列的工具或方法很多而且容易實現[1，2，5，11]。從系統調用之間的參數流向關系上可以看到程序的各種動態行為。基于圖語義表達上的優越性，本文對這些行為作圖形化建模，所得到的每個局部子圖體現的是程序的每個局部行為語義。對搜集到的系統調用序列進行分析發現，其在每個程序運行時出現的次序有一定規律，如頻繁的文件操作。Linux下vsftpd-2.0.6運行時所截取到的部分系統調用序列代碼如下:

open(\"/etc/ld.so.cache\"，O_RDONLY)=3

fstat64(3，{st_mode=S_IFREG|0644，st_size=98823，…})=0

old_mmap(NULL，98823，PROT_READ，MAP_PRIVATE，3，0)=0xb7ef0000

colse(3)=0

munnap(0xb7eff0000，98823)=0

open(\"/usr/lib/libgssapi_krb5.so.2\"，O_RDONL Y_=3

read(3，\"\\177ELF\\1\\1\\1\\0\\0\\0\\0\\0\\0\\0\\0\\0\\3\\0\\3\\0\\1\\0\\0\\0\\362\\217\"，…，512)=512

fstat64(3，{st_mode=S_IFREG|0755，st_size=96108，…})=0

old_mmap(NULL，93132，PROT_READ|PROT_EXEC，MAP_PRIVATE|MAP_DENYWRITE，3，0)=0x8d1000

old_mmap(0x8e7000，4096，PROT_READ|PROT_WRITE，MAP_PRIVATE|MAP_FIXED|MAP_DENYWRITE，3，0x16000)=0x8e7000

close(3)=0

這樣，可以對上述系統調用序列進行劃分，系統調用1~5可以劃分為一個序列子集，表示程序的一個行為，即打開一個文件，取文件狀態，對其內容進行內存映射等操作，然后關閉文件，并釋放該文件所占用的資源;系統調用5~10則為程序對另一個文件的一系列操作行為。由此，可將系統調用序列按照程序的局部行為劃分為一個個長短不一的序列片段，稱之為序列子集。每一個序列子集代表程序的一個行為，然后對每個序列子集進行組圖。具體過程如下:

將圖的節點表示為每一個系統調用函數，節點屬性用操作系統給系統調用分配的序列號(詳見文獻[12])表示，系統調用參數之間的依賴關系定義為節點之間的邊。對邊的定義是這樣:由于參數的類型各異，通常將這些不同類型的參數間的約束關系按值與參數類型進行劃分，定義為邊的一種屬性。Linux的參數類型一共有70種(詳見文獻[12])，那么這種邊屬性一共有70種。另外，由于實驗平臺Linux操作系統的特殊性，很多文件操作系統調用的返回值會經常參與到與其他系統調用的依賴關系中，如圖1(b)中Fx=T0)，于是系統調用的返回值也當成一種特殊的參數值進行處理。用0表示系統調用的返回值與系統調用的參數值相等，1表示系統調用的參數值與其他系統調用的參數值相等。對于第二種情況，假定系統調用的參數最多有六個[11]，那么考慮到系統調用執行的先后順序，對于兩個系統調用的相等參數對，一共有36種可能的組合，而對于第一種情況，則有六種可能的組合。本文用一個三元組{X，Y，Z}來表示邊的屬性，X表示是否返回值與參數值的相等，取值為0和1，Y表示參數值類型，取值為0~69;Z表示匹配的參數對序數;Z的取值依賴于X(如果X=0，取值為0~5;X=1，取值為0~35)。圖1表示了圖形化建模的過程。

在圖1(d)的程序行為子圖中沒有標出依賴關系S1=W1，這是因為在系統調用參數依賴關系的分析中，有一部分參數遠不如其他的參數重要，這些參數與其他參數之間的依賴關系并不是關心的描述程序行為的最主要的依賴關系。因此針對具體的系統調用對其參數依據重要程度進行適當的刪減。另外，為了提取所需要的程序特征胎記，還對截獲的系統調用序列進行了其他的處理。所有的操作具體如下:

a)參數刪減。例如獲取文件狀態的系統調用函數fstat64[13]，參數“3”表示其操作文件的描述符，是最重要的參數;“st_mode=S_IFREG” 等參數表示所獲取的文件狀態，通常在程序行為中不會當成重要參數傳遞，除非有專門針對文件狀態進行處理的系統調用函數。所以在組圖的時侯，這部分的參數可以舍棄掉。這樣做還可以避免假邊依賴[5] ，即有許多無關的系統調用的整型參數與所關心的依賴關系中的系統調用參數值相等。組圖時的數據處理開銷也節省許多。對圖1(a)中的序列進行參數刪減后的序列如下:

open(\"/etc/ld.so.cache\")=3

fstat64(3)=0

old_mmap(3)=0xb7ef0000

close(3)=0

mumap(0xb7ef0000)=0

從以上序列可以很清楚地看到各系統調用參數之間的主要流向關系，能更加明確地表達出程序的行為。

b)系統調用序列聚類。在組建系統依賴圖時，有很多系統調用是對于同一個資源連續的相似操作，如1 000次向一個文件中連續地讀入1 Byte，相當于一次往這個文件中讀入1 000 Byte。系統調用中諸如此類的操作都可以聚集為一個節點。對系統調用的聚類操作不僅使得依賴圖中的節點數目大幅度減少，降低進行圖匹配計算時的內存開銷，而且可以得到系統調用序列的一些簡單的等價形式，便于在組圖時對程序行為進行描述。

c)序列子集的截取與統計。依據前面的分析，將截取到的系統調用序列按照程序的行為動作劃分為一個個序列片段，每一個序列片段代表程序的一個局部行為。Linux系統平臺是以文件的形式管理所有資源，即使是硬件設備。所以在一個程序中，大部分的系統調用都是對文件的操作，并且有一定的次序約束。比如在文件操作中，對于同一個文件描述符，close函數必須在open函數之后，網絡操作中receive函數必須在send函數之后等，可以將系統調用序列按一定的程序行為規律進行劃分，如圖1(a)所示。然后統計相同的子序列出現次數，組成子序列集，本文中用DL表示，DL={(L1，F1)，(L2，F2)，…，(Ln，Fn)}。其中Li和Fi(1≤i≤n)分別表示每一個子序列和其出現的次數。

3 胎記的定義

本文對于胎記定義是這樣的:對于前面DL中的每一個子序列分別進行組圖，得到Dg={(G1，F1)， (G2，F2)， …，(Gn，Fn)}，Gi和Fi分別表示每個行為子圖以及其數目。對Dg中的行為子圖兩兩之間進行圖同構的匹配[14]，將同構的子圖合并為一個，其次數值為兩者之和，得到新的集合，用Dg′={(G1′，F1′)，(G2′，F2′)， …，(Gm′，Fm′)}表示，則Gi′表示程序P中的每一種行為子圖，Fi′表示其出現次數(Fi′=F′(Gi′))，然后依次將Fi′(1≤i≤n)除以總圖數∑mi=1Fi′得到比值fi。為了區別，本文用B(p)={(g1，f1)，(g2，f2)，…，(gm，fm)}表示，并將此定義為程序P的一個動態胎記。

4 程序相似性計算

為了對給定程序P、Q之間進行相似性比較，進行了如下工作:給定程序P、Q及其提取的程序胎記B(P)和B(Q)，令B(P)={(p1，Pf1)，(p2，Pf2)，(p3，Pf3)，…，(pn，Pfn)}，B(Q)={(q1，Qf1)，(q2，Qf2)，(q3，Qf3)，…，(qm，Qfm)}。基本算法如下:

a)首先找出程序P的每一個行為子圖pi(如圖1(d))與程序Q的所有行為子圖qj之間的最大共同子圖，再在pi的所有最大共同子圖中選取節點數目最大的作為pi與對應的qj之間的最大共同子圖，記為(pi，qj，mcs(pi， qj))(1≤i，j≤n)。若pi與qj有多個最大共同子圖，任選其中的一個作為代表，使得qj在{(pi，qj，mcs(pi，qj))}中不重復出現。

b)在{(pi，qj，mcs(pi，qj))}集中，若存在|mcs(pi，qj)|=|mcs(pi，qk)|，1≤k， j≤m且k≠j，則從{(pi，qj，mcs(pi，qj))}集中刪去mcs(pi，qj)/|qj|與|mcs(pi，qk)|/|qk|的值較小的，|qj|，|qk|分別表示子圖qj與qk中節點個數，得到pi的最大共同子圖集Spi={(pi′，qj′，mcs(pi′，qj′))}。

c)對于程序Q，重復a)~b)同樣的操作，得到qj的最大共同子圖集Sqj。

d)將{Spi}與{Sqj}求交集(視(pi，qj，mcs(pi，qj))與(qj，pi，mcs(qj，pi))為同一項)得到結果集{(pk，qk，mcs(pk，qk))}，用Wp，q表示。

e)計算Wp，q中，依據定義6，每兩圖之間的相似度，S(pk， qk)=|mcs(pk，qk)|/max(|pk|，|qk|)。假設Wp，q中的元素個數為t，則程序P與Q的相似度可以定義為

Sp，q=(∑tk=1min(Pfk/Qfk，Qfk/Pfk)×S(pk，qk)/n)×

min(∑tk=1F(pk)/∑ni=1F(pi)∑tk=1F(qk)/∑mj=1F(qj))

其中:Pfk和Qfk為Wp，q中pk與qk在各自程序中出現的幾率。

5 實驗與測評

5.1 實驗

本文比較了六組功能相似程度不同的程序相似度，采用虛擬機搭建的Linux操作系統FC4作為實驗平臺，運用strace-o命令對六組運行中的程序進行了跟蹤和系統調用搜集，兩個程序的行為子圖的最大共同子圖的計算采用文獻[15]中的最大共同子圖算法，實驗結果如表1所示。

表1 實驗結果數據

程序名稱參與比較子圖數(∑F(pj′))

行為子圖數總系統調用總數相似度

KuickShow/Kview278/371298/38910631/156310.597

vsftpd(2.1.0/2.0.3)26/3026/30361/3740.852

bzip2/gzip1269/12691274/127416264/162641

jar/tar5/419/25223/1710.106

Ksnapshot/scrot165/48270/5114844/5740.259

java_make/c_make12/477/45635/9980.041

a)KuickShow和KView是FC4桌面上的兩個看圖軟件，分別用其打開桌面的一張圖文件，并跟蹤搜集其系統調用。

b)Vsftpd 2.1.0和vsftpd 2.0.3是兩個不同版本的FTP軟件，分別以匿名身份登錄到本地主機，查看主機中的文件。

c)Bzip2和gzip雖是Linux下的兩個壓縮軟件，但是不能單獨使用，而是通過tar -xjf和tar -xzf命令分別對glib-2.19.0.tar.bz2和glib-2.19.0.tar.gz兩個壓縮文件進行解壓，搜集解壓過程中的系統調用集。

d)Jar和tar是兩個打包軟件，但不同的是，jar是Java類文件的一種壓縮工具，生成的jar文件直接被Java運行;而tar則是一種文件打包工具，程序實現不同。本文分別用jar和tar對/application/alcatraz-0.64/GUI目錄下.class文件和/application/etrace-0.8.2/libetrace/目錄下的.h文件打包。

e)KSnapshot和scrot是截圖軟件，但不同的是KSnapshot是基于KDE桌面環境的一個截圖軟件，而scrot是個基于終端使用的截圖小軟件。雖然精簡小巧，但是兩者的功能大同小異，scrot幾乎能完成KSnapshot所有的基本功能，分別應用其對桌面、窗口和鼠標截取的區域進行截圖操作。

f)Java_make和C++_make分別表示Java編譯器和C++編譯器，實現完全不同。本文應用javac和make命令對/application/alcatraz-0.64/GUI目錄下的.java文件和/application/etrace-0.8.2/下的所有C++源代碼進行了編譯。

5.2 分析與總結

1)對于程序相似性的檢測

從實驗數據可以看到，對于功能一致、實現相同的程序，如Vsftpd-2.1.0和Vsftpd-2.0.3、bzip2和gzip，在相同的輸入下程序的相似程度比較高。對于實現不同，功能也有很大出入的程序在不同的輸入下用本文提出的方法比較則顯示出很低的相似度，如jar和tar、java_make和C_make，而介于中間的程序，如Kuickshow和KView、KSnapshot和Scrot，前者在實現上比較接近，但功能上有部分差異，后者在功能上接近但是具體實現不同，因此前者的相似度要大些。由此可以看到，本文的檢測方法對相似程度各異、規模大小不一以及功能繁簡程度不一的程序相似程度有較好的體現和證明。這主要是由于本文提取的胎記特征中，行為子圖以及其在程序中的出現幾率較好地表征了程序局部行為及其在整體程序中的分布，對程序行為特征有較好的保留性，同時也具有良好的區別性。

2)方法的健壯性

由于采用程序局部行為圖形建模的方式，提取動態胎記能不受每次程序運行時因進程調度差異或CPU并行處理所造成的系統調用序列調用次序差異的影響，并且能夠能夠抵抗一部分API混淆技術[2~4]，如添入一部分無關的系統調用或將無約束關系的系統調用次序打亂以隱藏其剽竊的痕跡。

3)未來的研究工作

a)關于相似性閾值的設定。文獻[4]中依據文中程序胎記的定義，將檢測的經驗閾值界定為0.2，它是依據多次實驗數據結果值而設定的。相似度小于閾值0.2的兩個程序可以視為相互獨立的兩個程序，相似度大于0.8的兩個程序可以視為相似的兩個程序，屬于中間值的不作分類。對于本文提出的方法中相似性界定閾值的設定工作還在研究中，需要更多的實驗予以證明。

b)提高方法的健壯性。 本文的方法雖然能抵抗一部分API混淆技術，但是如果在不破環程序原有功能的基礎上在程序中添加一部分自己定義的代碼，如添加一些其他功能，使得觸發一部分系統調用序列是行為依賴的子序列，那么將破壞程序中原有行為子圖的分布幾率，從而對程序胎記造成一定程度的破壞，影響程序相似性的測量準確度。但是這種方法需要比較專業的知識和技能，人力物力的花費將相應增加，那么這種類型的API攻擊也將大大減少，但不能排除這種情況的可能。為了提高程序胎記的健壯性，在未來的研究中將致力于其他程序胎記特征的挖掘，在對更多的程序進行檢測的過程中，將參考進程中資源的訪問，對系統調用的參數間關系作更多的挖掘，如程序局部行為之間的聯系、系統調用從屬功能函數之間的結構關系、兩個進程之間的通信等，這對程序整體行為的描述將更為精確。另外，除了上述的API混淆技術，每個程序在啟動時的普遍加載動作也會對程序的相似度計算帶來一定誤差，對于這些問題的研究一并留給將來的研究工作。

6 相關工作

關于程序相似性的研究，前人的工作主要集中在程序代碼的相似度檢測，常見的方法為屬性計數法和結構度量法[16~19]。前者只對代碼的各種統計屬性進行處理，后者則對程序的內部結構進行分析，大多數的程序相似性檢測系統將兩種方法結合在一起應用，如斯坦福大學的Moss系統[20]、德國卡爾斯魯厄大學的JPlag[21]、威奇塔州立大學的Sim[22]、悉尼大學的YAP3[23]等。其他的源代碼檢測方法還有代碼克隆[24]，程序水印、指紋[24]，基于編譯優化和反匯編的程序相似性檢測[25]等。程序胎記技術源于對程序自身各種特征的提取和定義，在程序源代碼基礎上提取的程序胎記特征主要有初始化類的常量值、方法調用序列、繼承結構和程序的類文件等[6，7]。隨著軟件無源代碼的發布，程序相似性研究逐漸趨向于從程序運行時的行為特征中提取證明信息[1~4，8，26~28]。對基于系統調用的程序行為的研究，多用于計算機安全領域的入侵檢測方面[11，29]，主要是利用系統調用序列不同方面的特性進行建模與分析，判別程序是否正常。其中文獻[5]中的內容與本文的研究相似，它是通過比較惡意程序與一組良性程序的依賴圖之間的最小相對子圖[15]，檢測出惡意程序異于良性程序的惡意行為。本文基于程序相似性的研究，側重的是兩個程序行為的相似之處，因此比較的是兩個行為圖之間的最大共同子圖。其他將系統調用應用于程序相似性的研究還有日本奈良先端科學技術大學Tamada等人[1，2]利用系統調用序列之間的先后次序及其出現的頻率作為程序的動態胎記，提出并應用于程序剽竊的檢測中。德國薩爾不呂肯大學的Schuler等人[4]將系統調用序列用定長的滑動窗口依次截取后的短序列片段定義為程序的動態胎記，這樣可以減少巨大的系統調用序列數量。

7 結束語

本文首先介紹了程序動態胎記技術的抽象定義及相關屬性，結合圖形在數據結構上的語義表達優勢，將系統調用序列以及其間的參數關系用圖形來建模，在此基礎上定義了一種基于程序行為子圖及其分布的程序動態胎記，并在此基礎上提出了一種程序相似性的比較方法。對此方法的實驗檢測表明，該方法能較好地體現相似程度各異、大小及功能繁簡程度不一的程序相似度，具有一定的可信度和適用性。未來的研究工作在組圖建模上將考慮更多程序局部之間的行為，這對程序整體行為的描述將更為精確。

參考文獻:

[1]OKAMOTO K， TAMADA H， NAKAMURA M，et al. Dynamic software birthmarks based on API calls[J]. IEICE Trans on Information and Systems， 2006， 89(8):1751-1763.

[2]TAMADA H， OKAMOTO K， NAKAMURA M， et al. Dynamic software birthmarks to detect the theft of windows applications[C]//Proc of International Symposium on Future Software Technology. 2004.

[3]SCHULER D， DALLMEIER V. Detecting software theft with API call sequencesets[C]//Proc of Workshop on Software Reengineering. 2006.

[4]SCHULER D， DALLMEIER V， LINDIG C， et al. A dynamic birthmark for Java[C]//Proc of the 22nd IEEE/ACM International Conference on Automated Software Engineering. New York:ACM Press， 2007:274-283.

[5]CHRISTODORESCU M，JHA S，KRUEGEL C. Mining specifications of malicious behavior[C]//Proc of the 6th Joint Meeting European Software Engineering Conference and the ACM SIGSOFT International Symposium on Found Ations of Software Engineering. 2007:3-7.

[6]TAMADA H， NAKAMURA M， MONDEN A， et al. Detecting the theft of programs using birthmarks， NAIST-IS-TR-2003014[R]. Nara:Nara Institute of Science Technology， 2003.

[7]TAMADA H， NAKAMURA M， MONDEN A， et al. Design and eva-luation of birthmarks for detecting theft of Java programs[C]//Proc of the IASTED International Conference on Software Engineering. 2004:569-575.

[8]MYLES G， COLLBERG C. Detecting software theft via whole program path birthmarks[C]//Proc of the 7th International Conference on Information Security. Berlin:Springer-Verlag， 2004:404-415.

[9]BUNKE H， SHEARER K. A graph distance metric based on the maximal common subgraph[J]. Pattern Recognition Letters，1998，19(3-4):255-259.

[10]BUNKE H. Graph matching:theoretical foundations，algorithms， and applications[C]//Proc of Vision Interface Montreal. 2000:82-88.

[11]朱國強，劉真，李宗伯.對計算機系統中程序行為的分析和研究[J]. 計算機應用，2005，25(12):2739-2741.

[12]ZHEN Kai-liang. Etrace[CP/OL].[2008-05-30]. http://www.seclab.cs.sunysb.edu/etrace/.

[13]Linux C function()[EB/OL].(2003-06-06) [2009-01-30].http://man.chinaun-ix.net/develop/cc++/linux_c/default.htm.

[14]VENYO M. The Vflib graph matching library[CP/OL].(2003-05) [2008-08-30]. http://amalfi.dis.unina.it/graph/.

[15]TING R M H，BAILEY J. Mining minimal contrast subgraph patterns[C]//Proc of the 6thSIAM International Conference on Data Min-ing. 2006:638-642.

[16]周高嵚，彭四偉. 源代碼在線測評系統中剽竊檢測技術的研究與實現[J].計算機與信息技術，2005(12):85-87.

[17]陳金宏，劉東升. 程序代碼相似度自動度量技術研究綜述[J].內蒙古師范大學學報，2006，35(4):457-461.

[18]鄧愛萍，徐國梁，肖奔. 基于串匹配方法的源代碼復制檢測技術研究[J]. 科學技術工程，2007，7(10):63-66.

[19]鄧愛萍，徐國梁，肖奔. 程序源代碼剽竊檢測串匹配算法的研究[J]. 計算機工程與科學，2008，30(3):62-64.

[20]AIKEN A. Moss: a dystem for detecting software plagiarism[CP/OL]. [2009-04-23]. http://www.cs.berkeley.edu/～aiken/ moss.html.

[21]PRECHEL L，MALPOHL G，PHIPPSEN M. Finding plagiarisms among a set of programs with JPlag[J]. Journal of Universal Computer Science， 2002， 8(11):1016-1038.

[22]GITCHELL D，TRAN N. Sim: a utility for detecting similarity in computer programs[C]//Proc of the 30th SIGCSE Technical Symposium on Computer Science Education. 1999.

[23]WISE M. YAP3: improved detection of similarities in computer program and other texts[C]//Proc of the 27th SIGCSE Technical Symposium on Computer Science Education. 1996:130-134.