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

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

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

隨著計算機軟件的發展，程序代碼在日常生活中越來越常見，代碼能夠實現各種各樣的計算、匹配和查詢.正是由于軟件行業的快速發展，以編程為職業的工作人員層出不窮，因而代碼的質量也因人而異.相似代碼的檢測應運而生，能在許多應用中發揮作用，比如可以通過檢測源程序中的相似代碼對源程序進行簡化，也可以查找出多個程序之間的相似功能，還能用于抄襲檢測.

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

大部分判斷代碼相似的文獻是通過不同的相似度度量來判斷2個或多個源代碼整體是否相似，這樣增加了一些不必要的計算.這是因為函數功能段在程序代碼中占有主體地位，如果2個源程序中的功能段相似，那么就能確定這2個源程序基本相似.因此，本文首先提取出源代碼中的功能段，再以帶權重的編輯距離為相似度量標準，通過聚類源程序代碼序列的方法，查找出源程序中相似的代碼功能段，以達到檢測相似功能程序的目的.

1 問題定義

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

如果有序列S=s1s2… sn，ni是字母表中字母ai在序列S中出現的次數，則向量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'之間的簽名距離，當，否則=0;當 n'j＞ nj時=1，否則=0.

1.1 帶權重的編輯距離

本文對序列中各種不同類型的字符賦予不同的權重，根據字符的可替代性大小規定各個字符的權重.如果是代表關鍵字的字符，所得到的權重就大一些，代表變量的字符得到的權重就比較小，因為相比之下，變量的可替代性要比關鍵字的可替代性大.本文中，把代表關鍵字的字符權重設為2，代表函數或者變量的符號權重設為1，代表操作符的符號權重設為1，如表1所示.

表1 不同符號的權重Table 1 The weight of different symbol

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

定義1 帶權重的編輯距離(WED) 編輯距離是指將一個符號序列經插入、刪除、替換等編輯操作變為另一個序列所需的操作次數，根據序列中各種不同類型的符號的不同權重，把進行編輯操作乘以相應符號操作的權重，就得到一個符號序列到另外一個符號序列的帶權重的編輯距離.

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

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

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

表3 符號轉換的權重編輯距離Table 3 The weight edit distance of transform symbol

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

1.2 序列間的相似度

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

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

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

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

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

證明 序列S1和S2之間的簽名距離DS(S1，S2)反映了序列字母組成上的差異，而權重編輯距離DW(S1，S2)反應了S1和S2之間插入、刪除、替換操作不同權重的差異，由于給序列中不同類型符號的插入、刪除、替換操作賦予了不同的權重(表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據式(2)，可以得到 Sm(S1，S2)≥Smin，說明這2個序列不相似.

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

2 基于帶權重編輯距離的相似序列聚類算法

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

2.1 源程序代碼的分段提取

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

2.2 程序代碼的部分轉換

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

2.3 符號序列的聚類

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

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

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

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

輸入:要判斷相似性的2個序列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 判斷序列與簇是否相似

有了判斷序列與序列是否相似的算法作為支撐，判斷序列與簇是否相似就很容易了.只需要把簇中的所有序列依次與該序列進行相似性判斷，如果簇中有任意一個序列與該序列相似，就判定為該序列與該簇相似.如算法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 符號序列的聚類

本文采用改進的基于密度的聚類算法對序列聚類，首先創建一個簇列表來存放聚類結果簇，對于存放在map中任意一個序列Si，判斷序列Si與簇列表中的簇的相似關系，直到所有的序列Si都被處理.此時的相似關系可能為3種情況:1)如果簇列表中沒有簇與序列Si相似，那么就新建一個簇存放該序列，并且把新創建的簇添加到簇列表中;2)如果簇列表中有一個簇與該序列相似，就把它加入到這個簇中，更新簇的特征值;3)如果簇列表中有多個簇與該序列相似，就把這幾個簇合成一個新簇，再把序列Si加入到新簇中，并且在簇列表中移除合并了的那幾個簇，添加新創建的簇.聚類過程如算法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給出了改進的基于密度的序列聚類過程.其中，步驟5)～9)是判斷簇列表中有幾個簇與序列是相似的，可能出現上面給出的3種情況.步驟10)～11)對應情況1)，即簇列表中沒有簇與序列相似;步驟12)～13)對應情況2)，簇列表中有一個簇與該序列相似;步驟14)～16)對應情況3)，簇列表中有多個簇與該序列相似.

3 實驗與分析

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

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

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

實驗所用的計算機配置如下:CPU為Pentium(R)Dual-Core 2.93GHz，內存為 2GB，操作系統為Microssoft Windows XP Professional Edition 2002 Service Pack 3.所有算法用JAVA語言編寫實現.

3.1 SSCW算法聚類結果

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

由于在源程序中功能函數所占的比例很大，而且對于程序的功能取決定性作用，因此如果功能函數相似，那么基本上可以確定其所在的源程序也是相似的.從表4中可以看出，算法能夠正確判斷代碼的相似性.另外，還可以看出序列之間的最小相似度閾值Rs，min和結果文件相似度Rs的關系.由于判斷序列相似是判斷文件相似的基礎工作，而在判斷序列是否相似時，Rs，min是一個決定性參數，序列之間的最小相似度閾值Rs，min的確定會影響到結果文件相似度Rs.由表4中可以看出，Rs，min的增加會導致Rs不變或者減小，這是因為序列最小相似度閾值的增加，會使得滿足相似條件的序列減少，從而使得最終代碼相似性的減小，如表4中文件對1和文件對4中Rs，min設為0.9時的情況;如果函數代碼序列本身的相似度高于設定的最小序列相似度，那么Rs，min的設定就不會影響到最終結果.

表4 SSCW聚類結果Table 4 The clustering results of SSCW

3.2 SSCW算法運行時間分析

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

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

表5 運行時間隨著不同因素改變的變化Table 5 Running time changes with different factors

4 結束語

本文提出一種基于序列聚類的相似代碼檢測算法SSCW，以得到相似功能的代碼段.該方法采用一種多級分段方法，把源代碼分為不同標準下的多種分段，分段的標準有類、函數、語句.將需要檢測的代碼段提取出來后，把不好區分權重的關鍵字代碼轉換為數字序列，以提出的權重編輯距離為距離度量標準，對同一個等級內的符號序列進行聚類分析，得到相似的代碼段.在實驗時，使用了多個數據集對提出的算法進行了驗證，實驗結果證明了該算法的有效性.

［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］趙長海，晏海華，金茂忠.基于編譯優化和反匯編的程序相似性檢測方法［J］.北京航空航天大學學報，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］于海英.程序代碼相似度度量的研究與實現［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］.計算機應用研究，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］.計算機工程與應用，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］.軟件學報，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.