基于序列聚類的相似代碼檢測算法

于世英，袁雪梅，盧海濤，任家東，李碩

(1.燕山大學(xué) 信息科學(xué)與工程學(xué)院，河北秦皇島066004;2.河北省科技管理信息中心，河北 石家莊050021)

隨著計(jì)算機(jī)軟件的發(fā)展，程序代碼在日常生活中越來越常見，代碼能夠?qū)崿F(xiàn)各種各樣的計(jì)算、匹配和查詢.正是由于軟件行業(yè)的快速發(fā)展，以編程為職業(yè)的工作人員層出不窮，因而代碼的質(zhì)量也因人而異.相似代碼的檢測應(yīng)運(yùn)而生，能在許多應(yīng)用中發(fā)揮作用，比如可以通過檢測源程序中的相似代碼對源程序進(jìn)行簡化，也可以查找出多個(gè)程序之間的相似功能，還能用于抄襲檢測.

國內(nèi)外許多學(xué)者對檢測相似代碼進(jìn)行了大量研究，K.Kontongiannis等提出一種使用模式檢測代碼相似性的方法［1］，模式被指定為概念語言中的源程序或者摘要描述的序列.該方法采用一系列代碼對代碼和摘要描述對代碼的匹配技術(shù)，前者使用動態(tài)編程技術(shù)來局部化相似代碼片段，能處理大型軟件系統(tǒng).后者使用馬爾可夫模型，根據(jù)一個(gè)給定摘要描述生成一個(gè)給定代碼段的概率，來計(jì)算一個(gè)摘要描述與代碼段之間的不同距離.A.Ohno提出一種使用相關(guān)向量來度量源代碼相似性的算法［2］.該算法直接使用相關(guān)向量而不是使用源程序代碼，相關(guān)向量中的元素是從源代碼中產(chǎn)生的token-cooccurrence矩陣的結(jié)構(gòu)特征值，由于相似性僅僅定義為2個(gè)相關(guān)向量之間的距離，因此該方法節(jié)省了計(jì)算時(shí)間，同時(shí)也不用為存儲源程序開辟大的存儲空間.T.Yamamoto等提出一種基于源代碼通信的大型軟件系統(tǒng)相似性度量算法［3］，根據(jù)這個(gè)相似度量開發(fā)出了一個(gè)軟件相似性度量工具SMAT，并且應(yīng)用到了多個(gè)版本的操作系統(tǒng)中.J.H.Ji等提出一種自適應(yīng)的局部隊(duì)列，把關(guān)鍵字的頻率映射到相似度矩陣中，使用這個(gè)局部隊(duì)列來自動檢測程序中的相似代碼片段［4］.文獻(xiàn)［5］提出了一種基于編譯優(yōu)化和反匯編的程序相似性檢測方法.該方法采用編譯優(yōu)化和反匯編技術(shù)將源程序代碼轉(zhuǎn)化為匯編指令集合，再刪除和替換匯編指令中對程序本質(zhì)影響不大的易變因素，然后使用一個(gè)與指令序列無關(guān)的決策函數(shù)計(jì)算程序相似度，最后給出一個(gè)簡單有效的聚類算法，從程序集合中聚類出相似的程序子集.文獻(xiàn)［6］針對源程序代碼相似度的度量問題，提出一種基于屬性計(jì)數(shù)和結(jié)構(gòu)度量的方法.通過統(tǒng)計(jì)源程序代碼的操作符和操作數(shù)個(gè)數(shù)，得到Halstead長度、Halstead詞匯和Halstead容量這3個(gè)源程序的特征向量，使用向量夾角的余弦公式計(jì)算屬性相似度，利用最長公共子序列算法得到結(jié)構(gòu)相似度，從而權(quán)衡程序之間的相似程度.文獻(xiàn)［7-9］中也分別提出了不同的相似代碼檢測算法，它們基于不同的結(jié)構(gòu)，從不同的角度來對相似代碼進(jìn)行檢測.

大部分判斷代碼相似的文獻(xiàn)是通過不同的相似度度量來判斷2個(gè)或多個(gè)源代碼整體是否相似，這樣增加了一些不必要的計(jì)算.這是因?yàn)楹瘮?shù)功能段在程序代碼中占有主體地位，如果2個(gè)源程序中的功能段相似，那么就能確定這2個(gè)源程序基本相似.因此，本文首先提取出源代碼中的功能段，再以帶權(quán)重的編輯距離為相似度量標(biāo)準(zhǔn)，通過聚類源程序代碼序列的方法，查找出源程序中相似的代碼功能段，以達(dá)到檢測相似功能程序的目的.

1 問題定義

假設(shè) CS={a1，a2，…}作為字符集，大小為N=|CS|.S∈CS*表示一個(gè)字符序列，S由CS中的字符組成，其中的字符數(shù)為|S|.2條序列S1和S2之間的編輯距離DE(S1，S2)是將S1經(jīng)過插入、刪除、替代等操作變換成S2所需要的最少操作次數(shù).

如果有序列S=s1s2… sn，ni是字母表中字母ai在序列S中出現(xiàn)的次數(shù)，則向量SN(S)=(n1，n2，…，nN)為序列S的簽名.若序列S和S'的簽名分別為 SN(S)=(n1，n2，…，nN)和 SN(S')=(n'1，n'2，…，n'N)，那么 DS(S，S')(n－ n')，ii為序列 S 和 S'之間的簽名距離，當(dāng)，否則=0;當(dāng) n'j＞ nj時(shí)=1，否則=0.

1.1 帶權(quán)重的編輯距離

本文對序列中各種不同類型的字符賦予不同的權(quán)重，根據(jù)字符的可替代性大小規(guī)定各個(gè)字符的權(quán)重.如果是代表關(guān)鍵字的字符，所得到的權(quán)重就大一些，代表變量的字符得到的權(quán)重就比較小，因?yàn)橄啾戎拢兞康目商娲砸汝P(guān)鍵字的可替代性大.本文中，把代表關(guān)鍵字的字符權(quán)重設(shè)為2，代表函數(shù)或者變量的符號權(quán)重設(shè)為1，代表操作符的符號權(quán)重設(shè)為1，如表1所示.

表1 不同符號的權(quán)重Table 1 The weight of different symbol

要對程序代碼段進(jìn)行聚類分析，首先要解決的問題就是怎樣定義程序代碼段之間的距離度量，以及怎樣確定這2段代碼是相似的.本文定義一種帶權(quán)重的編輯距離(weight edit distance，WED)來衡量2個(gè)序列之間的距離，度量它們的相似性.

定義1 帶權(quán)重的編輯距離(WED) 編輯距離是指將一個(gè)符號序列經(jīng)插入、刪除、替換等編輯操作變?yōu)榱硪粋€(gè)序列所需的操作次數(shù)，根據(jù)序列中各種不同類型的符號的不同權(quán)重，把進(jìn)行編輯操作乘以相應(yīng)符號操作的權(quán)重，就得到一個(gè)符號序列到另外一個(gè)符號序列的帶權(quán)重的編輯距離.

1)插入、刪除操作.對于插入或刪除操作，由于只涉及一個(gè)符號，所以其權(quán)重編輯距離設(shè)置為該符號規(guī)定的權(quán)重，如表2.

表2 符號插入、刪除的權(quán)重編輯距離Table 2 Weight edit distance of insert and delete symbol

2)轉(zhuǎn)換操作.同一類型符號內(nèi)部轉(zhuǎn)換的權(quán)重在表3中給出了，不同類型符號之間的轉(zhuǎn)換權(quán)重編輯距離則規(guī)定為這2種符號類型的權(quán)重之和.表3列舉出了本文使用到的符號轉(zhuǎn)換時(shí)的不同權(quán)重編輯距離.

表3 符號轉(zhuǎn)換的權(quán)重編輯距離Table 3 The weight edit distance of transform symbol

例1 假如一個(gè)符號序列S1=asdfght，另一個(gè)符號序列S2=abcfght.可以看出這2個(gè)序列中只有2個(gè)符號不同，設(shè)定其中的b、c、d都為關(guān)鍵字類型的符號，而s為操作符類型的權(quán)重，根據(jù)上面定義的轉(zhuǎn)換權(quán)重編輯距離可知，序列S1和S2之間的權(quán)重編輯距離是3+2=5.

1.2 序列間的相似度

定義2 序列間的相似度 2個(gè)序列S1和S2間的權(quán)重編輯距離為 DW(S1，S2)，則序列S1和S2之間的相似度Sm(S1，S2)表示為

若有2個(gè)序列S1和S2，它們之間的相似度為Sm(S1，S2)，如果 Sm(S1，S2)≥Smin成立，就說這 2 個(gè)序列S1和S2相似，說明在聚類時(shí)這2個(gè)序列可以被歸為同一個(gè)簇，Smin被稱為序列間的最小相似度閾值.

為了方便計(jì)算，在進(jìn)行聚類時(shí)，可以直接以權(quán)重編輯距離為衡量相似度的標(biāo)準(zhǔn).根據(jù)相似度的定義式(1)，可以得到滿足Sm(S1，S2)≥Smin的最大權(quán)重編輯距離邊界值Dmax(S1，S2)為

即如果滿足 DW(S1，S2)≤Dmax(S1，S2)時(shí)，則這 2 個(gè)序列相似.

性質(zhì)1 若有2個(gè)序列S1和S2，其簽名距離為DS(S1，S2)，如果滿足 DS(S1，S2)≥Dmax(S1，S2)時(shí)，那么這2個(gè)序列不相似.

證明 序列S1和S2之間的簽名距離DS(S1，S2)反映了序列字母組成上的差異，而權(quán)重編輯距離DW(S1，S2)反應(yīng)了S1和S2之間插入、刪除、替換操作不同權(quán)重的差異，由于給序列中不同類型符號的插入、刪除、替換操作賦予了不同的權(quán)重(表1～3)，那么 DW(S1，S2)≥DE(S1，S2)成立，而簽名距離是編輯距離的下界［10］，即 DE(S1，S2)≥DS(S1，S2)，因此可得到 DW(S1，S2)≥DS(S1，S2)成立.因 此，Sm(S1，S2)≤1－，如果 D(S，S)≥D(S，S)，那么根S12max12據(jù)式(2)，可以得到 Sm(S1，S2)≥Smin，說明這2個(gè)序列不相似.

由于計(jì)算簽名距離的時(shí)間復(fù)雜度O(m+n)遠(yuǎn)小于計(jì)算權(quán)重編輯距離的時(shí)間復(fù)雜度O(mn).因此，根據(jù)性質(zhì)1，在判斷序列是否相似時(shí)，可以首先通過計(jì)算序列間的簽名距離來進(jìn)行初始過濾，再通過計(jì)算權(quán)重編輯距離來進(jìn)行最后的判斷.

2 基于帶權(quán)重編輯距離的相似序列聚類算法

本節(jié)將詳細(xì)介紹提出的基于權(quán)重編輯距離的相似序列聚類算法SSCW(similar sequence clustering based on weight edit distance).

2.1 源程序代碼的分段提取

檢測源程序的相似代碼，首先需要對源程序代碼進(jìn)行分段，提取出函數(shù)功能段.在對源程序代碼進(jìn)行分段時(shí)，采用一種多級分段方法，把源代碼分為不同標(biāo)準(zhǔn)下的多種分段，分段的標(biāo)準(zhǔn)有類、函數(shù)、語句，然后再對同一個(gè)級別下的各個(gè)分段代碼進(jìn)行處理.在查找相似代碼時(shí)，由于函數(shù)功能段是整個(gè)源程序代碼的主體，因此只需要使用第二級函數(shù)分段即可，對函數(shù)、語句和類的處理意義不大.

2.2 程序代碼的部分轉(zhuǎn)換

由于使用帶權(quán)重編輯距離作為相似性度量的標(biāo)準(zhǔn)，并且關(guān)鍵字類型、變量類型與操作符類型的權(quán)重各不相同，因此需要對它們進(jìn)行區(qū)分.一般來說，操作符類型的代碼能很好地與其他代碼區(qū)分，但是關(guān)鍵字類型和變量類型的代碼在讀取和計(jì)算距離的時(shí)候很難區(qū)分.本文首先把關(guān)鍵字類型的代碼轉(zhuǎn)換成一個(gè)個(gè)數(shù)字，再計(jì)算權(quán)重編輯距離，雖然變量代碼里面也不可避免地會出現(xiàn)數(shù)字代碼，但是這樣的源代碼很少，與關(guān)鍵字混淆的概率也不大.這樣處理既能與變量代碼進(jìn)行區(qū)分，保證可以得到帶權(quán)重的編輯距離，又能減少計(jì)算距離時(shí)的操作次數(shù).

2.3 符號序列的聚類

對同一個(gè)分段級別內(nèi)的序列，根據(jù)定義1中的權(quán)重編輯距離作為相似性度量進(jìn)行聚類，得到相似的代碼段.下面具體說明聚類過程中用到的幾個(gè)主要算法.

2.3.1 判斷序列與序列是否相似

首先根據(jù)式(2)計(jì)算出2個(gè)序列相似的最大距離閾值Dmax(S1，S2)(SandSMaxDis);然后根據(jù)性質(zhì)1，先計(jì)算2個(gè)序列的簽名距離DS(S1，S2)(signDisS-toS)來進(jìn)行初始過濾，如果它們的簽名距離大于最大距離閾值，就直接判定這2個(gè)序列不相似;如果簽名距離小于最大距離閾值，再計(jì)算其權(quán)重編輯距離DE(S1，S2)(wEditDisStoS)進(jìn)行進(jìn)一步判斷.如算法1所述.

算法1 判斷序列與序列是否相似算法(is-SandSSimilar).

輸入:要判斷相似性的2個(gè)序列S1和S2.

輸出:布爾值(isSimilar).

Begin

1)boolean isSimilar;

2)int SandSMaxDis=getMaxDistance(S1，S2);

3)int signDisStoS=calSignDisStoS(S1，S2);

4)If signDisStoS＜=SandSMaxDis

5) int wEditDisStoS=calWEditDisStoS(S1，S2);

6) If wEditDisStoS＜=SandSMaxDis

7) isSimilar=true;

8) Else

9) isSimilar=false;

10) End if

11)End if

End

2.3.2 判斷序列與簇是否相似

有了判斷序列與序列是否相似的算法作為支撐，判斷序列與簇是否相似就很容易了.只需要把簇中的所有序列依次與該序列進(jìn)行相似性判斷，如果簇中有任意一個(gè)序列與該序列相似，就判定為該序列與該簇相似.如算法2所述.

算法2 判斷序列與序列是否相似算法(is-SandCSimilar).

輸入:要判斷相似性的序列ser和簇cluster.

輸出:布爾值(isSimilar).

Begin

1)boolean isSimilar;

2)For each series s in cluster

3) isSimilar=isSandCSimilar(ser，s);

4) If isSimilar

5) break;

6) End if

7)End for

End

2.3.3 符號序列的聚類

本文采用改進(jìn)的基于密度的聚類算法對序列聚類，首先創(chuàng)建一個(gè)簇列表來存放聚類結(jié)果簇，對于存放在map中任意一個(gè)序列Si，判斷序列Si與簇列表中的簇的相似關(guān)系，直到所有的序列Si都被處理.此時(shí)的相似關(guān)系可能為3種情況:1)如果簇列表中沒有簇與序列Si相似，那么就新建一個(gè)簇存放該序列，并且把新創(chuàng)建的簇添加到簇列表中;2)如果簇列表中有一個(gè)簇與該序列相似，就把它加入到這個(gè)簇中，更新簇的特征值;3)如果簇列表中有多個(gè)簇與該序列相似，就把這幾個(gè)簇合成一個(gè)新簇，再把序列Si加入到新簇中，并且在簇列表中移除合并了的那幾個(gè)簇，添加新創(chuàng)建的簇.聚類過程如算法3所述.

算法3 聚類算法(clustering).

輸入:存放序列的哈希表seriesMap.

輸出:簇列表clusters.

Begin

1)List clusters;

2)For each series s in seriesMap

3) List simCluNotoSList;//clusters in List clusters which are similar to series s

4) List removeCluList;

5) For each cluster c in clusters

6) If isSandCSimilar(s，c)

7) simCluNotoSList.add(c);

8) End if

9) End for

10) If simCluNotoSList.size()==0

11) Create a new cluster c'to put series s and put c'into clusters;

12) Else if simCluNotoSList.size()==1

13) Put s in cluster c and update the feature of c;

14) Else

15) Merging clusters in simCluNotoSList into a new cluster c'and put c'into clusters;

16) Remove clusters in simCluNotoSList from clusters;

17) End if

18)End for

End

算法3給出了改進(jìn)的基于密度的序列聚類過程.其中，步驟5)～9)是判斷簇列表中有幾個(gè)簇與序列是相似的，可能出現(xiàn)上面給出的3種情況.步驟10)～11)對應(yīng)情況1)，即簇列表中沒有簇與序列相似;步驟12)～13)對應(yīng)情況2)，簇列表中有一個(gè)簇與該序列相似;步驟14)～16)對應(yīng)情況3)，簇列表中有多個(gè)簇與該序列相似.

3 實(shí)驗(yàn)與分析

通過對4個(gè)文件對的相似性檢測，來分析SSCW算法結(jié)果的正確性以及運(yùn)行時(shí)間.測試中使用的代碼采用人工合成的代碼序列和從網(wǎng)上下載的真實(shí)代碼.實(shí)驗(yàn)中文件對1(int00和int05)和文件對3(cross-ref00和 cross-ref02)是從網(wǎng)站 http://www.sei.buaa.edu.cn/buaasim下載的，實(shí)現(xiàn)統(tǒng)計(jì)整數(shù)和交叉引用生成器功能的相似代碼.文件int05是在文件int00的基礎(chǔ)上改變了函數(shù)順序和修改了部分變量名得到的;文件crossref02是在文件cross-ref00的基礎(chǔ)上改變了函數(shù)內(nèi)部部分代碼順序，并在定義時(shí)添加了無用參數(shù)構(gòu)成.文件對2(cluster00和cluster01)和文件對4(adjustCluster00和adjustCluster01)是把筆者編寫的源程序中一些代碼段稍作修改得到，文件對2中文件cluster01是在文件cluster00的基礎(chǔ)上添加了一個(gè)功能函數(shù)段構(gòu)成;文件對4中文件adjustCluster01是在文件adjustCluster00的基礎(chǔ)上修改了函數(shù)內(nèi)部部分代碼得到的.

根據(jù)源文件中功能函數(shù)的個(gè)數(shù)以及聚類結(jié)果來評判它們是否相似.最終2個(gè)源文件的相似度由參數(shù)Rs來決定，其計(jì)算方法為

式中:Ns為聚類結(jié)果中包含了來自2個(gè)源文件的函數(shù)的簇個(gè)數(shù)，N為這2個(gè)源程序中總的功能函數(shù)個(gè)數(shù).

實(shí)驗(yàn)所用的計(jì)算機(jī)配置如下:CPU為Pentium(R)Dual-Core 2.93GHz，內(nèi)存為 2GB，操作系統(tǒng)為Microssoft Windows XP Professional Edition 2002 Service Pack 3.所有算法用JAVA語言編寫實(shí)現(xiàn).

3.1 SSCW算法聚類結(jié)果

表4給出了使用提出的SSCW算法對相似代碼序列的聚類結(jié)果，Rs，min為序列間的最小相似度閾值，Rs為2個(gè)源程序文件根據(jù)相似函數(shù)得到的相似度.

由于在源程序中功能函數(shù)所占的比例很大，而且對于程序的功能取決定性作用，因此如果功能函數(shù)相似，那么基本上可以確定其所在的源程序也是相似的.從表4中可以看出，算法能夠正確判斷代碼的相似性.另外，還可以看出序列之間的最小相似度閾值Rs，min和結(jié)果文件相似度Rs的關(guān)系.由于判斷序列相似是判斷文件相似的基礎(chǔ)工作，而在判斷序列是否相似時(shí)，Rs，min是一個(gè)決定性參數(shù)，序列之間的最小相似度閾值Rs，min的確定會影響到結(jié)果文件相似度Rs.由表4中可以看出，Rs，min的增加會導(dǎo)致Rs不變或者減小，這是因?yàn)樾蛄凶钚∠嗨贫乳撝档脑黾樱瑫沟脻M足相似條件的序列減少，從而使得最終代碼相似性的減小，如表4中文件對1和文件對4中Rs，min設(shè)為0.9時(shí)的情況;如果函數(shù)代碼序列本身的相似度高于設(shè)定的最小序列相似度，那么Rs，min的設(shè)定就不會影響到最終結(jié)果.

表4 SSCW聚類結(jié)果Table 4 The clustering results of SSCW

3.2 SSCW算法運(yùn)行時(shí)間分析

表5中給出了SSCW算法的運(yùn)行時(shí)間隨著文件大小、函數(shù)個(gè)數(shù)以及最小序列相似度閾值Rs，min不同的變化情況，可以看出SSCW算法的運(yùn)行時(shí)間受這3個(gè)因素的共同影響.在SSCW算法中，運(yùn)行時(shí)間主要由計(jì)算權(quán)重編輯距離和聚類這2個(gè)過程的時(shí)間消耗組成，權(quán)重編輯距離的計(jì)算時(shí)間與序列的長度有關(guān)，因此當(dāng)一個(gè)功能函數(shù)序列的長度增大時(shí)，算法的運(yùn)行時(shí)間會大幅度增加;而聚類的運(yùn)行時(shí)間與功能函數(shù)序列的個(gè)數(shù)以及其相似性有關(guān)，如果函數(shù)序列的個(gè)數(shù)增多，聚類所花費(fèi)的時(shí)間也隨著增加.由于在計(jì)算權(quán)重編輯距離時(shí)，通過先計(jì)算序列的簽名距離來進(jìn)行初始過濾，因此當(dāng)最小序列相似度閾值Rs，min確定的序列距離小于序列之間的簽名距離時(shí)，就不需要計(jì)算序列的權(quán)重編輯距離，此時(shí)需要的時(shí)間消耗較少，如表5中文件對2中Rs，min被設(shè)定為0.9的情況.

表5中的3個(gè)因素中，文件大小和函數(shù)個(gè)數(shù)決定了函數(shù)序列的長度，它們與最小相似度閾值一起決定了權(quán)重編輯距離的運(yùn)行時(shí)間.而函數(shù)個(gè)數(shù)及其相似性決定了聚類過程的運(yùn)行時(shí)間，因此聚類過程的時(shí)間消耗就與文件個(gè)數(shù)和最小相似度閾值有關(guān).在文件大小一定的情況下，功能函數(shù)的個(gè)數(shù)越少，說明函數(shù)序列的長度越大，此時(shí)序列間權(quán)重編輯距離的計(jì)算時(shí)間消耗就越大;但是，功能函數(shù)的個(gè)數(shù)越少，聚類過程所需要的時(shí)間消耗就越小，因此，功能函數(shù)的個(gè)數(shù)對運(yùn)行時(shí)間的影響不是很明確.一般來說，當(dāng)功能函數(shù)個(gè)數(shù)一定時(shí)，文件的規(guī)模越大、最小相似性閾值越小，運(yùn)行時(shí)間也越多.

表5 運(yùn)行時(shí)間隨著不同因素改變的變化Table 5 Running time changes with different factors

4 結(jié)束語

本文提出一種基于序列聚類的相似代碼檢測算法SSCW，以得到相似功能的代碼段.該方法采用一種多級分段方法，把源代碼分為不同標(biāo)準(zhǔn)下的多種分段，分段的標(biāo)準(zhǔn)有類、函數(shù)、語句.將需要檢測的代碼段提取出來后，把不好區(qū)分權(quán)重的關(guān)鍵字代碼轉(zhuǎn)換為數(shù)字序列，以提出的權(quán)重編輯距離為距離度量標(biāo)準(zhǔn)，對同一個(gè)等級內(nèi)的符號序列進(jìn)行聚類分析，得到相似的代碼段.在實(shí)驗(yàn)時(shí)，使用了多個(gè)數(shù)據(jù)集對提出的算法進(jìn)行了驗(yàn)證，實(shí)驗(yàn)結(jié)果證明了該算法的有效性.

［1］KONTOGIANNIS K，GALLER M，DEMORI R.Detecting code similarity using patterns［C］//Working Notes of Third Workshop on AI and Software Engineering:Breaking the Toy Mold(AISE).［S.l.］，1995:68-73.

［2］OHNO A.Measure source code similarity using reference vectors［C］//Proceedings of the First International Conference on Innovative Computing，Information and Control.Washington，DC，USA:IEEE Computer Society，2006，2:92-95.

［3］YAMAMOTO T，MATSUSHITA M，KAMIYA T，et al.Measuring similarity of large software systems based on source code correspondence［C］//Proceedings of the 6th International Conference on ProductFocused Software Process Improvement.Berlin/Heidelberg:Springer-Verlag，2005:530-544.

［4］JI J H，PARK S H，WOO G，et al.Source code similarity detection using adaptive local alignment of keywords［C］//Proceedings of the Eighth International Conference on Parallel and Distributed Computing，Applications and Technologies.Washington，DC，USA:IEEE Computer Society，2007:179-180.

［5］趙長海，晏海華，金茂忠.基于編譯優(yōu)化和反匯編的程序相似性檢測方法［J］.北京航空航天大學(xué)學(xué)報(bào)，2008，34(6):711-715.ZHAO Changhai，YAN Haihua，JIN Maozhong.Approach based on compiling optimization and disassembling to detect program similarity［J］.Journal of Beijing University of Aeronautics and Astronautics，2008，34(6):711-715.

［6］于海英.程序代碼相似度度量的研究與實(shí)現(xiàn)［J］.計(jì)算機(jī)工程，2010，36(4):45-49.YU Haiying.Research and implementation of program code similarity measurement［J］.Computer Engineering，2010，36(4):45-49.

［7］JIANG Linxiao.Scalable detection of similar code:techniques and applications［D］.Davis，CA，USA:University of California Davis，2009:12-45.

［8］張麗萍，劉東升，李彥臣，等.一種基于AST的代碼抄襲檢測方法［J］.計(jì)算機(jī)應(yīng)用研究，2011，28(12):4616-4620.ZHANG Liping，LIU Dongsheng，LI Yanchen，et al.AST-based code plagiarism detection method［J］.Application Research of Computers，2011，28(12):4616-4620.

［9］鐘美，張麗萍，劉東升.基于XML的C代碼抄襲檢測算法［J］.計(jì)算機(jī)工程與應(yīng)用，2011，47(8):215-218.ZHONG Mei，ZHANG Liping，LIU Dongsheng.Plagiarism detection algorithm based on XML for C code［J］.Computer Engineering and Applications，2011，47(8):215-218.

［10］戴東波，湯春蕾，熊赟.基于整體和局部相似性的序列聚類算法［J］.軟件學(xué)報(bào)，2010，21(4):702-717.DAI Dongbo，TANG Chunlei，XIONG Yun.Sequence clustering algorithms based on global and local similarity［J］.Journal of Software，2010，21(4):702-717.