基于改進WL圖核的代碼克隆檢測方法*

班 必 奐，徐 云

(1.中國科學(xué)技術(shù)大學(xué) 大數(shù)據(jù)學(xué)院，安徽 合肥 230026；2.安徽省高性能計算重點實驗室，安徽 合肥 230026；3.中國科學(xué)技術(shù)大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，安徽 合肥 230026)

0 引言

在實際的軟件系統(tǒng)開發(fā)過程中，開發(fā)人員出于提高開發(fā)效率或者降低軟件錯誤風(fēng)險的原因，通常會將其他模塊中功能相同或者相近的代碼片段通過復(fù)制—修改(或不修改)—粘貼的模式引入到當(dāng)前正在開發(fā)的模塊中，這些粘貼而來的功能相同或相似的代碼片段在學(xué)術(shù)界通常被稱為克隆代碼[1]。大量的研究表明，過多的克隆代碼會給軟件系統(tǒng)帶來維護成本提高[2]和Bug蔓延[3]等問題。例如，假設(shè)某一段代碼中存在Bug并且這段代碼被復(fù)制粘貼在不同的位置，那么這個Bug將會隨著這些克隆代碼在整個軟件中傳播，進而增加了維護的難度。因此，檢測出軟件系統(tǒng)中的克隆代碼并對其進行統(tǒng)一管理是非常有必要的。

隨著代碼克隆檢測技術(shù)的不斷發(fā)展，高級別代碼克隆(即Type-3和Type-4克隆)的檢測成為當(dāng)前的研究熱點之一。由于高級別克隆代碼往往在復(fù)制粘貼之后還進行了一些修改，因此也更有可能存在Bug[4]。另外，修改所導(dǎo)致的差異性也使得這一類型的克隆更加難以被檢測。

得益于程序依賴圖(Program Dependency Graph，PDG)中所包含的大量語法結(jié)構(gòu)信息和語義信息，基于PDG的克隆檢測方法在檢測高級別克隆上更具優(yōu)勢，能夠檢測出更多的結(jié)構(gòu)相似但文本差異較大的高級別克隆代碼。但在已有的方法中，采用精確圖匹配算法的CCSharp[5]、GPLAG[6]等克隆檢測方法存在時間性能差和召回率低的缺點，而采用Weisfeiler-Lehman(WL)圖核進行近似圖匹配計算的CCGraph[7]，受限于節(jié)點初始標(biāo)簽的單一性和WL圖核迭代過程中對近似子結(jié)構(gòu)識別能力的缺失，召回率也相對較低。為此，本文針對WL圖核算法在PDG克隆檢測應(yīng)用中存在的缺陷，提出了一種改進思路：首先利用語法分析技術(shù)將PDG節(jié)點所包含的源代碼信息解析為特征向量的形式來作為該節(jié)點的初始標(biāo)簽，使其能夠保留更多的語義信息；然后通過引入局部敏感哈希技術(shù)提升PDG中近似子結(jié)構(gòu)的識別能力，進而提升高級別克隆的召回率。

1 相關(guān)研究

1.1 基于文本的方法

基于文本的代碼克隆檢測方法通常將代碼片段視為普通的字符序列，通過計算這些代碼字符序列的相似度來尋找克隆。例如在經(jīng)過一系列如刪除注釋、刪除多余空行和對代碼格式重新排布之后再使用字符串匹配算法來檢測克隆。典型的研究成果為Baker所提出的工具Dup[8]。此類方法優(yōu)點在于檢測的速度非?？欤荒軝z測出Type-1克隆以及部分Type-2克隆，更高級別的Type-3和Type-4克隆則幾乎無法檢測。

1.2 基于Token的方法

基于Token的代碼克隆檢測方法主要思路依然是采用字符串匹配相關(guān)的算法來檢測克隆，其與基于文本的方法最大的區(qū)別就是在進行比對之前增加了詞法分析過程，例如，將變量名統(tǒng)一解析為“id”。因此，這種方法能夠忽略變量重命名帶來的影響，除了能夠快速并且較為精確地識別出Type-1克隆以外，還能夠識別出Type-2克隆和少量的相似度較高的Type-3克隆，但對于文本相似度較低的Type-3克隆則幾乎無法檢測。其中，SourcererCC[9]和CCAligner[10]是這類方法中比較典型的工具。

1.3 基于抽象語法樹的方法

基于抽象語法樹(Abstract Syntax Tree，AST)的代碼克隆檢測方法主要考慮源代碼的語法規(guī)則，將源代碼轉(zhuǎn)換為其對應(yīng)的AST形式，然后通過尋找AST之間的相似性來尋找克隆。Deckard[11]是其中較為典型的工具，其主要思想是通過將AST轉(zhuǎn)換為特征向量的形式來快算尋找AST之間的相似性。但由于Type-3克隆的AST結(jié)構(gòu)之間往往差異較大，并且子樹的定位較為復(fù)雜，因此其召回率并不高。

1.4 基于程序依賴圖的方法

基于PDG的代碼克隆檢測方法首先利用分析工具來生成源代碼的程序依賴圖，再利用圖匹配算法來尋找相似的圖結(jié)構(gòu)，相似或者同構(gòu)的PDG對將被視為克隆。比較典型的方法有CCSharp和CCGraph，其中CCSharp采用了精確子圖同構(gòu)判定算法VF2[12]；而CCGraph則采用了基于WL圖核的近似圖匹配算法。然而這兩種方法都沒有考慮到高級別克隆對PDG之間的特點，因此召回率偏低。

2 方法設(shè)計與實現(xiàn)

本文所提出的檢測方法主要由兩個部分組成，即預(yù)處理階段和克隆檢測階段。如圖1所示，預(yù)處理階段首先生成了與源代碼相關(guān)的函數(shù)級別的PDG，然后利用解析工具將每個頂點所代表的語義解析為特征向量的形式，最后利用滑動窗口算法對所有的PDG建立一個索引表，具有相同Key值的PDG將被視為潛在的克隆對進入到下一個階段。在克隆檢測階段主要應(yīng)用改進的WL圖核算法進行圖相似性的比較，判定其是否為克隆對。

圖1 本文代碼克隆檢測方法流程圖

2.1 節(jié)點特征向量提取

由于解析工具生成的原始PDG中，圖節(jié)點的標(biāo)簽被定義為與之相對應(yīng)的源代碼，不利于直接進行圖核計算，而如果只將其簡單地按照語句類型(如賦值語句、條件判斷語句等)進行處理則會損失掉大量有用信息，因此需要對其進行解析，如提取出不同變量個數(shù)、賦值運算符個數(shù)、加減乘除運算符個數(shù)、比較運算符個數(shù)、數(shù)組訪問運算符個數(shù)和不同函數(shù)調(diào)用個數(shù)等語義信息(如表1所示)，最終以特征向量的形式作為該節(jié)點的初始標(biāo)簽。

表1 語義信息類型

例如，假設(shè)某個PDG節(jié)點所包含源碼信息為“OutputStream zOut=new OutputStream(out)”，則該節(jié)點的初始標(biāo)簽為[2，1，0，0，0，0，0，0，0，1]，表示在該節(jié)點中共有2個變量(分別為“zOut”和“out”)且該節(jié)點是一個賦值節(jié)點，同時還進行了一次函數(shù)調(diào)用。

2.2 滑動窗口過濾

如算法1所示，在獲得所有節(jié)點的特征向量之后，將這些特征向量按照其對應(yīng)頂點在程序流程中出現(xiàn)的先后順序排序，再利用窗口大小為w，步長為1的滑動窗口在這些排好序的節(jié)點上滑動。假設(shè)節(jié)點的個數(shù)為N，則將獲得N-w+1個標(biāo)簽(向量)序列。然后，對這N-w+1個序列做哈希，將哈希值作為索引，對應(yīng)的PDG序號和相關(guān)信息作為值插入到索引表中。例如，假設(shè)PDG的序號為P1，相應(yīng)的排好序的標(biāo)簽為{a，b，c，d}，窗口大小為3，則索引表的內(nèi)容為{hash(a，b，c)：[P1]，hash(b，c，d)：[P1]}。最后通過遍歷索引表來獲取所有的候選克隆對。

算法1：滑動窗口過濾算法

輸入：所有的待檢測PDG集合G，窗口大小w；

輸出：候選克隆對C。

2.3 基于改進WL圖核的克隆檢測

原始的WL圖核迭代過程主要分為3步：

(1)對于每個節(jié)點，獲取其所有的直接鄰居節(jié)點的標(biāo)簽從而得到一個多重標(biāo)簽；

(2)對每一個多重標(biāo)簽集合進行排序，再利用哈希算法對排序后的多重標(biāo)簽集合進行哈希；

(3)將得到的哈希值作為該節(jié)點的新標(biāo)簽進行下一次迭代。

從WL圖核的迭代過程中不難看出，兩個標(biāo)簽集合即使只相差一個元素，在迭代步驟(2)進行哈希后得到的標(biāo)簽也會完全不同，而隨著迭代次數(shù)的增加，這些差異將會隨著迭代影響到越來越多的節(jié)點，最終導(dǎo)致原本相似的兩個PDG被判定為不相似。

針對該問題，本文提出改進的WL圖核，利用局部敏感哈希的特點，使得迭代過程中差異較小的子結(jié)構(gòu)能夠被識別出來。同時，為了降低精度的損失，本文還在子結(jié)構(gòu)匹配過程中引入了向量相似度量方法。

以圖2中的兩個源代碼片段為例，其生成的PDG如圖3所示。其中，虛線表示控制流，實線表示數(shù)據(jù)流。在預(yù)處理階段，已經(jīng)將節(jié)點對應(yīng)的源碼解析為特征向量的形式，如圖4(a)和圖4(b)所示。改進WL圖核算法每次迭代的過程同樣也分為3個步驟：

圖2 示例代碼片段

圖3 示例代碼片段的程序依賴圖

(1)將當(dāng)前節(jié)點的鄰居節(jié)點特征向量信息聚集到當(dāng)前節(jié)點中作為新的特征向量；

(2)根據(jù)局部敏感哈希函數(shù)以及該節(jié)點的類型和上一次迭代的分類情況，對得到的新特征向量進行進一步劃分，即：具有相同或相近哈希值并且上一次迭代中被劃分為同一類的節(jié)點將被視為潛在的相似節(jié)點；

(3)計算兩張圖中相似節(jié)點對（即具有相同哈希值并且特征向量的余弦相似度超過指定閾值的節(jié)點對）的個數(shù)作為本次迭代的圖核值。

仍然以圖4為例，假設(shè)只進行一次迭代。迭代之前，假設(shè)節(jié)點“＜3＞”“＜12＞”和“＜13＞”被歸為同 一 類，節(jié)點“＜4＞”和“＜7＞”為一類，節(jié)點“＜6＞”和“＜15＞”為一類。經(jīng)過迭代步驟(2)后，由于節(jié)點“＜13＞”與節(jié)點“＜3＞”和“＜12＞”的特征向量相差較大，因此有很大的概率被判定為不相似。而其余節(jié)點對之間因為特征向量依舊非常接近，因此將有非常大的可能性仍然被判定為相似(即“＜3＞”和“＜12＞”相 似，“＜4＞”和“＜7＞”相 似，“＜6＞”和“＜15＞”相似)，此時本次迭代的圖核值為k=2。而如果采用原始的WL圖核，迭代后圖中的所有節(jié)點將會擁有不同的標(biāo)簽，即本次迭代的圖核值為0。

圖4 改進WL圖核的一次迭代過程示例

最終，總的改進WL圖核值定義如下：

其中k(i)表示第i次迭代的圖核值，h表示迭代的總次數(shù)，αi為第i次迭代的權(quán)重因子。

在實際應(yīng)用過程中，由于改進WL圖核每次迭代都可以看做是將不同距離的節(jié)點標(biāo)簽信息匯聚到當(dāng)前節(jié)點中，例如第i次迭代獲取了與當(dāng)前節(jié)點的最短路徑距離為i的節(jié)點的標(biāo)簽信息，因此對所有的PDG設(shè)置一個太大的迭代次數(shù)反而會影響到時間性能，除此之外，相距越遠的節(jié)點對當(dāng)前節(jié)點的影響也應(yīng)該越小，為此，本文在計算兩個PDG之間的圖核值時動態(tài)地設(shè)置迭代次數(shù)為(|V1|+|V2|)/2(其中|V|表示PDG中節(jié)點的總數(shù))，并在每次迭代中加入權(quán)重因子αi=(h-i+1)/h來給予距離較近的鄰居節(jié)點信息更高的權(quán)重。

最后，考慮到差異較大的Type-3克隆的PDG中通常只存在一定的局部相似性，因此本文采用了非對稱相似性系數(shù)來衡量兩個PDG之間的相似程度，其計算方式如下：

其中G1，G2表示PDG；k(h)(G1，G2)表示這兩個PDG的改 進WL圖核值；|V1|，|V2|表 示PDG的頂點個數(shù)。最終，相似度超過閾值的PDG對將被視為克隆。

3 實驗結(jié)果與分析

3.1 數(shù)據(jù)集與實驗配置

在驗證工具的有效性方面，本文選用了公開的克隆檢測數(shù)據(jù)集BigCloneBench[13]進行實驗。該數(shù)據(jù)集由加拿大的Svajlenko團隊構(gòu)造，從IJaDataset-2.0中選取了總共55 499個Java文件，并標(biāo)記出其中的8 584 153個真實克隆對和279 032個假克隆對，是學(xué)術(shù)界用于評估檢測工具的常用數(shù)據(jù)集之一。

為了評估工具的可擴展性，在從IJaDataset-2.0數(shù)據(jù)集中隨機選取出來的1k、10k、1M和10M LoC(Lines of Code)的規(guī)模數(shù)據(jù)集分別進行了實驗。

實驗環(huán)境為Ubuntu 18.04系統(tǒng)，Intel?Xeon?Gold 5120 2.20 GHz CPU，503 GB內(nèi)存空間。

3.2 評估標(biāo)準(zhǔn)與結(jié)果分析

本文主要用精確率、召回率和時間性能三個指標(biāo)來作為評估標(biāo)準(zhǔn)。在評估召回率方面主要采用了BigCloneEval[14]評估框架。BigCloneEval是基于Big-CloneBench數(shù)據(jù)集的自動化評估工具，能夠根據(jù)檢測工具所報告的克隆對自動計算出相應(yīng)的召回率。同時，BigCloneEval還將Type-3克隆按照源代碼的相似程度分為了Very Strongly Type-3(即源代碼相似度在90%～100%之間)、Strongly Type-3(即源代碼相似度在70%～90%之間)、Moderately Type-3(即源代碼相似度在50%～70%之間)和Weakly Type-3/Type-4(即源代碼相似度在0%～50%之間)。

在對比工具方面，分別選擇了各種類型的代碼克隆檢測工具中比較具有代表性的方法，包括基于Token的檢測方法CCAligner、SourcererCC，基于AST的檢測方法Deckard，基于深度學(xué)習(xí)的方法Oreo[15]以及基于PDG的方法CCGraph。由于CCSharp不支持Java語言的檢測，因此未進行對比。最終的實驗結(jié)果如表2所示。

表2 不同工具在BigCloneBench上的檢測結(jié)果

在召回率方面，本文方法在除了ST3(Strongly Type-3)克隆以外的所有克隆類型上的召回率明顯優(yōu)于采用原始WL圖核的CCGraph。在源代碼相似程度最低的MT3(Moderately Type-3)上召回率取得了最好的結(jié)果，并且在T1(Type-1)、T2(Type-2)和VST3(Very Strongly Type-3)克隆的召回率與基于Token方法的CCAligner和SourcererCC非常接近，均達到了接近100%的召回率。Type-1和Type-2克隆召回率未達到100%的主要原因是由于PDG生成工具自身存在的問題，致使某些程序未能正確生成相應(yīng)的PDG。

在精確率方面，由于BigCloneEval評估工具只報告方法的召回率，而檢測得到的克隆對數(shù)又較大，因此本文從檢測結(jié)果中隨機選取了400對克隆進行人工確認，結(jié)果如表2中所示。從表2的結(jié)果可以看到，精度最高的工具為SourcererCC，但其MT3克隆的召回率只有5%，而MT3克隆往往是假陽性克隆對的主要來源之一。本文方法略高于CCGraph，這是因為預(yù)處理階段將PDG節(jié)點中所包含的源代碼信息解析為特征向量的形式保留了更多的語義信息。

在對結(jié)果的進一步分析中發(fā)現(xiàn)，由于局部敏感哈希函數(shù)依然存在一個較小的可能性將特征向量相差較大的節(jié)點歸為同一類，從而導(dǎo)致了假陽性的產(chǎn)生。實際應(yīng)用中可以根據(jù)用戶需求通過調(diào)整相似度閾值以及多次哈希取并集的方式來平衡召回率和精確率。

在評估時間性能方面，本文主要對比了同樣基于PDG的克隆檢測工具。由于CCSharp不支持Java數(shù)據(jù)集的檢測，因此為了體現(xiàn)采用圖核方法與采用精確子圖同構(gòu)檢測方法的性能差距，本文加入了將WL圖核換成CCShrap中所采用的VF2算法進行比對。通過表3的實驗結(jié)果可以看出，與采用精確子圖同構(gòu)檢測的VF2算法相比，采用近似圖匹配的本文方法和CCGraph在時間性能方面得到了巨大的提升。但由于本文方法在預(yù)處理階段增加了節(jié)點特征向量提取的步驟，因此時間性能上比CCGraph略差，但依然在可接受范圍內(nèi)。

表3 算法運行時間比較

4 結(jié)論

本文針對WL圖核在PDG近似匹配過程中存在的問題，提出了一種改進思路：在迭代過程中將普通哈希算法替換為局部敏感哈希算法，同時參考上一次迭代的結(jié)果來計算圖核值。此外，本文還根據(jù)改進后的WL圖核方法設(shè)計并實現(xiàn)了相應(yīng)的克隆檢測工具：首先利用靜態(tài)解析工具將源代碼解析為特征向量的形式；然后根據(jù)程序流程的先后順序?qū)@些特征向量排序，利用滑動窗口算法建立索引表并過濾掉那些不可能為克隆的PDG對；最后利用改進的WL圖核方法對候選PDG對進行圖相似性檢測并輸出最后的結(jié)果。實驗結(jié)果表明，本文方法在Type-3克隆上的召回率得到了較大提升，同時在檢測精度和時間性能上得到了良好的保持。