鄒 悅，吳 鳴，徐 云

(1.中國科學技術大學計算機學院，安徽 合肥 230027;2.安徽省高性能計算重點實驗室，安徽 合肥 230026)

1 引言

在實際軟件項目中，代碼克隆是指復制粘貼式的代碼復用或者模式化思維所造成的相同或相似代碼重復出現的現象[1]。

由于開發(fā)風格因人而異，對同一功能的不同實現方式導致文本差異較大的高級別克隆在軟件中廣泛存在(如表1所示)，不利于后續(xù)開發(fā)人員對代碼的解讀和維護，也增加了對軟件進行二次開發(fā)的難度。因此，高級別代碼克隆的檢測可以幫助程序開發(fā)人員定位這些克隆代碼，然后進行代碼重構和系統(tǒng)維護，在軟件開發(fā)過程中十分重要。

Table 1 Number of different typecode clones in BigCloneBench

目前在學術界，相關研究者按照源碼文本之間的相似程度將代碼克隆劃分為4個級別[2,3]：Type-1的代碼克隆是指除了空白、注釋和布局之外完全相同的代碼。Type-2的代碼克隆是指在Type-1的基礎上，除了標識名、變量名、變量類型和函數名以外完全相同的代碼。Type-3的代碼克隆是指在Type-2的基礎上存在著一定的插入、刪除和修改語句的相似的代碼。Type-4的代碼克隆是指功能相似但是通過不同的語法方式實現的代碼。對于Type-3和Type-4的高級別代碼克隆檢測，目前已經有一些國內外的學者進行了相關研究，其中基于程序依賴圖PDG(Program Dependency Graph)的方法是一類重要的檢測方法[4]。

然而，現有的基于PDG的代碼克隆檢測方法首先使用靜態(tài)分析工具來構建包含源碼語法結構及調用關系，數據流等的程序依賴圖，再采用子圖同構檢測等精確圖匹配算法找出2個相同或相似的PDG，以此發(fā)現克隆代碼。但是，子圖同構檢測算法是經典的NP難問題[5]，算法的高復雜度會導致時間消耗巨大，無法用于檢測大型的軟件系統(tǒng)，而且這種精確的圖匹配算法容錯率低，也會導致克隆代碼的檢出率低。

為此，本文提出了一種基于Weisfeiler-Lehman圖核算法的代碼克隆檢測方法。本方法首先對PDG的結構進行了簡化；然后使用特征向量相似度的計算進行候選代碼對的過濾；最后采用Weisfeiler-Lehman圖核這種非精確圖匹配的算法進行PDG的相似度計算，能夠更高效地檢測出更多的高級別克隆。

2 相關研究

本節(jié)主要介紹了一些學術界的代碼克隆相關的研究，例如不同類型的代碼克隆檢測方法，現有的圖匹配算法分類。

2.1 代碼克隆檢測方法

基于度量的代碼克隆檢測方法主要是收集代碼塊的若干度量值，如函數長度等，構成向量，通過比較向量的相似度來進行克隆的檢測。例如，Mayrand等[6]的方法就是收集函數單元的行數、函數調用的數目等進行相似度比較，這種方法雖然能夠更快速地進行代碼相似度比較，但是無法保留源代碼中的一些語法結構信息，會帶來假陽性過高的問題。

基于文本的克隆檢測方法將代碼行作為長字符串，使用字符串匹配算法來檢測克隆。例如，Baker[7]將每一行的代碼文本哈希后做行粒度的字符串匹配，這種方法比較適用于低級別的克隆檢測，對文本相似度高的克隆代碼，仍存在召回率低、檢測級別低等問題。

基于token的克隆檢測方法通過解析工具將源代碼程序解析成token序列后再進行比較。例如，CCAligner[8]、SourcererCC[9]和NICAD[10]等方法，對代碼的token序列進行相似子序列的查找，這種方法速度快、精度高，可以檢測出克隆代碼的格式變換以及重命名，但是不適用于語法結構相似的高級別克隆。

基于抽象語法樹AST(Abstract Syntax Tree)的克隆檢測方法是將代碼轉化為抽象語法樹(AST),然后通過樹的匹配算法來檢測相似的子樹。DECKARD[11]就是通過AST的相似子樹的匹配來檢測克隆的，但是這種方法仍然丟失了一部分代碼語法信息，并且子樹的定位和匹配復雜度過高，存在檢測不全的問題。

基于PDG的克隆檢測方法通過比較源代碼的PDG之間的圖相似性來檢測代碼克隆。例如，CCSharp[12]使用VF2子圖同構檢測算法[13]來發(fā)現代碼克隆，但是這種精確圖匹配的算法存在時間復雜度高、召回率低等問題。

此外，近年來隨著深度學習的發(fā)展，也有一些方法通過使用深度學習模型在一些大型的代碼集上進行訓練然后檢測克隆代碼，例如，Oreo[14]方法在單一的數據集上精確率和召回率表現都較好，但是存在過擬合和可解釋性差等問題。

2.2 圖匹配算法

圖匹配算法可分為精確匹配和非精確匹配算法。精確圖匹配算法主要是通過子圖同構匹配來判斷圖相似度，例如Ullmann[15]提出的同構檢測算法、VF2同構檢測算法[13]等。但是，精確圖匹配大都是NP難問題，檢測算法時間消耗過大，且還會降低對圖結構誤差的容忍性。

非精確圖匹配算法主要是通過將圖結構識別轉為統(tǒng)計識別問題，找到精確圖匹配最好的近似解[16]，主要包括圖嵌入和圖核2種算法。圖嵌入是指提取圖的一些特征值進行相似度比較。這種降維處理損失了圖中包含的大量結構信息，會降低圖匹配精度，可以用于過濾操作。圖核算法[17]，是把圖映射到向量特征空間，使得2個圖的相似性等于它們在向量特征空間中的內積。圖核算法具體的流程如下所示：

(1) 給定2個圖G1(V1,E1)、G2(V2,E2),以及一種圖分解方式F，分解后的子結構為：

F(G1)={S1,1,S1,2,…,S1,N1}

F(G2)={S2,1,S2,2,…,S2,N2}

(2) 基于上述子結構，G1和G2的圖核值可以表示為:

其中,σ(S1,n1,S2,n2)在S1,n1和S2,n2同構時為1，不同構時為0。因此,任何一種圖分解方式和子結構同構判斷方式的組合都可以定義出一個新的圖核。這種算法既保留了核函數計算效率高的優(yōu)點，也包含了圖數據的結構化信息。

Figure 2 Example of PDG of codes圖2 代碼程序依賴圖示例

3 方法設計

本文首先生成了源代碼中函數級別的程序依賴圖，并對生成的圖結構設計了約簡的策略，隨后對候選的代碼對集合進行特征向量的提取和過濾，最后應用Weisfeiler-Lehman圖核算法[17]進行圖相似性的比較，找出代碼克隆，其總體流程圖如圖1所示。

Figure 1 Flow chart of the proposed code clone detection method圖1 本文代碼克隆檢測方法流程圖

3.1 PDG的生成和簡化

為了進行程序依賴圖相似度的計算，本文需要選取一個合適的程序依賴圖生成工具，目前開源的工具有Frama-C[18]和TinyPDG[19]。Frama-C工具只針對C語言程序，TinyPDG是針對Java語言程序的PDG生成工具。由于代碼克隆檢測方法的評估框架BigCloneBench是基于Java語言的，本文選取TinyPDG工具進行改進，用于PDG的生成。

TinyPDG將源代碼程序生成對應的PDG后通過dot文件類型存儲，通過節(jié)點編號、形狀等屬性來表示語句的不同類型，例如聲明語句、控制語句和賦值語句，通過邊的形狀來表示語句間的控制依賴、數據依賴以及地址依賴關系。本文首先對PDG按照函數級別進行了切分，剔除了工具自動生成的與語法無關的節(jié)點，例如函數進入和退出節(jié)點，最后對函數中一些冗余子圖，例如第三方函數調用子圖進行了合并，這樣可以縮小PDG的規(guī)模，從而減少后續(xù)圖匹配算法的時間消耗，示例如圖2所示。

3.2 PDG集合的過濾

針對候選的代碼對集合，本文首先進行規(guī)模比過濾，如果2個圖的節(jié)點數相差過大，則過濾掉該候選對。然后，本文統(tǒng)計了PDG中不同依賴關系的邊的條數和不同類型的節(jié)點數目組成特征向量，進行余弦相似度的計算，小于給定閾值的候選對會被直接過濾掉。這樣可以大大縮小后續(xù)需要進行圖匹配的PDG對規(guī)模，提升速度。

3.3 基于Weisfeiler-Lehman圖核的克隆檢測

3.3.1 克隆檢測方法流程

針對程序依賴圖的結構特征，本文使用并改進了Weisfeiler-Lehman圖核算法來進行有向有標簽圖的相似度匹配。Weisfeiler-Lehman圖核算法的基本思想是，對每個節(jié)點的所有鄰接節(jié)點的集合的標簽進行排序，然后把這些標簽根據某一映射壓縮成新的更短的標簽值，如圖3所示。

Figure 3 Computation of the Weisfeiler-Lehman graph kernel for one iteration圖3 Weisfeiler-Lehman圖核一次迭代過程

因此,基于Weisfeiler-Lehman圖核的圖匹配算法及改進步驟如下所示：

(1) 對PDG圖中每個節(jié)點的標簽按照語法類別進行Hash處理,將其結果作為圖的初始標記。

(2) 在設定的h次迭代過程中，每次迭代都將當前節(jié)點的鄰居節(jié)點的標簽匯集在當前節(jié)點中，再對該標簽序列使用局部敏感哈希算法進行壓縮更新，得到新的節(jié)點標簽。

(3) 迭代過程完成后，若更新后2個節(jié)點的標簽相同，則認為以這2個節(jié)點為根節(jié)點，高度為h的子樹存在同構。

(4) 計算出2個圖結構間節(jié)點標簽集合中相同的節(jié)點標簽對數，即為圖核的值，若2個圖的圖核值滿足設定的閾值范圍，則認為2段代碼為克隆代碼。

(5) 動態(tài)設定迭代次數(較小圖直徑/2),每次迭代完成后統(tǒng)計圖中相同標簽的節(jié)點數目。

(6) 在第n(n≤h)次迭代過程加入權重因子(h-n+1)/h，對低次的迭代賦予更高的權重。

在基于Weisfeiler-Lehman圖核算法的圖匹配之后，即可計算代碼對的圖核值，代表著2個圖中相似點的總數量。本文使用圖核值與較小的程序依賴圖的比例作為2個圖的相似度，如果相似度大于設定的閾值，則認為該代碼對為代碼克隆。

3.3.2 基于Weisfeiler-Lehman圖核檢測算法的優(yōu)劣勢分析

使用基于Weisfeiler-Lehman圖核算法的非精確圖匹配方法可以有效地將每個節(jié)點的鄰居節(jié)點信息進行歸總，2個節(jié)點的標簽序列Hash值的比較，對應的就是以這2個節(jié)點為根的一個子樹結構的相似度比較。這樣可以有效地避免子圖同構這種精確圖匹配算法中每個節(jié)點比較的復雜性，更加快速地計算出2個圖的相似度，同時也考慮到了2個圖中只存在部分相似性的情況，提升克隆代碼的檢出率。但是,Weisfeiler-Lehman圖核算法對PDG的規(guī)范要求較高，所以需要提前對PDG做好預處理工作。同時，雖然本文方法已經大大縮短了圖匹配時間，但是與token方法相比，仍然存在很大差距，因此仍然需要設計好的過濾算法加以輔助。

4 實驗結果與分析

4.1 數據集介紹與實驗配置

在評估方法的有效性時，本文選擇了學術界代碼克隆檢測方法的統(tǒng)一評估框架BigCloneEval[20]。框架中使用的BigCloneBench數據集是由加拿大的Jeffery和Roy團隊建立的人造Java數據集，從25 000個軟件中提取了包含了43種功能共約59萬個Java文件，總代碼行數約350×106行，包含了800多萬對的真實克隆對。所有的實驗都在單機Ubuntu14.04LTS四核8 GB內存的操作系統(tǒng)下進行。

4.2 評估標準與結果分析

由于本文提出的基于Weisfeiler-Lehman圖核的方法基于非精確圖匹配算法，能夠更加快速、全面地檢測出高級別克隆。因此，在實驗評估標準的選擇上，本文選擇了代碼集合中檢測出克隆代碼對的精確率、召回率和時間性能3個評估標準。同時，在對比方法的選取上，本文選擇了代表性較強的克隆檢測方法，包括基于token的檢測方法CCAligner、SourcererCC、NICAD,基于AST的方法DECKARD，由于基于PDG的克隆檢測方法CCSharp只針對C語言程序，本文選取了包含PDG信息的Oreo工具進行對比實驗。

4.2.1 召回率

BigCloneBench評估框架會自動評估代碼克隆檢測方法每個級別的克隆檢測召回率。如表2所示的實驗結果表明，在文本相似度比較大的低級別克隆檢測上，由于在過濾階段過濾掉了一些較短的函數，本文方法的召回率都略低于其他克隆檢測方法的。但是，在Moderately Type-3、Weakly Type-3和Type-4的高級別克隆檢測的召回率上，本文方法明顯好于Oreo、CCAligner等其他克隆檢測方法。對克隆對詳細分析后發(fā)現，本文方法能夠檢測出更多的小結構克隆，即2個圖之間存在局部相似性，但是不存在子圖同構的情況，因為檢測方法對每個節(jié)點的子結構都進行了比較，能夠發(fā)現這種局部相似性。

4.2.2 精確率

由于BigCloneBench只報告方法的召回率，而檢測結果規(guī)模又較大，因此本文按照學術界通用的方法對克隆結果進行了抽樣檢測，隨機選取了400對克隆代碼進行人工確認，結果如表2所示(其他工具的精度結果取自之前的工作[8])。實驗結果表明，本文方法的精確率略低于Oreo及CCAligner這些基于token的檢測工具，但是仍然比NICAD提升了近25%，比DECKARD提升了近50%。因為一些變量名或者代碼語句的插入或刪除會導致PDG圖結構的變化，以及預處理過程中對PDG進行了簡化和節(jié)點標簽化的處理，這些都會導致檢測結果中假陽性的存在，降低檢測結果的精確率，但是可以根據用戶需求通過調整相似度閾值來平衡召回率和精確率。

Table 2 Clone detection results comparison of different methods on BigCloneBench

4.2.3 時間性能

在時間性能的對比實驗中，本文在不同規(guī)模的代碼數據集合上對不同的代碼克隆檢測方法進行了實驗。由于基于PDG的克隆檢測方法CCSharp只針對于C語言程序，因此本文加入了將Weisfeiler-Lehman圖核算法換成CCSharp采用的精確圖匹配算法(VF2子圖同構算法)的時間對比實驗。如表3所示的實驗結果表明，由于圖的生成和預處理過程的時間消耗較大，非精確圖匹配算法雖然快于精確圖匹配算法，但是仍然比不上token方法，本文方法的時間略慢于基于token的CCAligner和SourcererCC，但是相比NICAD和DECKARD算法以及CCSharp采用的VF2算法的速度有了很大的提升，能夠運行在更大規(guī)模的代碼集合上。

Table 3 Time cost comparison of different methodson different scale codesets

5 結束語

本文針對文本差異較大的高級別克隆檢測問題,提出了一種基于PDG的非精確圖匹配方法。

該方法首先對根據代碼文本生成的程序依賴圖進行了簡化處理，再通過特征提取和特征向量的相似度計算對候選的代碼對集合進行了過濾，減小了后續(xù)圖匹配的集合規(guī)模，最后使用基于Weisfeiler-Lehman圖核的非精確圖匹配算法進行了PDG的相似度計算，并輸出了檢測的克隆結果。實驗表明，在高級別克隆檢測的召回率上，本文方法相對于已有的克隆檢測方法有了很大的提高，并且運行速度也比已有的PDG檢測方法更快。下一步工作的重點是提高低級別克隆檢測的召回率，解決小圖克隆檢測不全的問題，并加快方法運行速度，提高方法的可擴展性。