鄒 悅，吳 鳴，徐 云

(1.中國科學(xué)技術(shù)大學(xué)計(jì)算機(jī)學(xué)院，安徽 合肥 230027;2.安徽省高性能計(jì)算重點(diǎn)實(shí)驗(yàn)室，安徽 合肥 230026)

1 引言

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

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

Table 1 Number of different typecode clones in BigCloneBench

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

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

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

2 相關(guān)研究

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

2.1 代碼克隆檢測(cè)方法

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

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

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

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

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

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

2.2 圖匹配算法

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

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

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

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

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

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

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

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

3 方法設(shè)計(jì)

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

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

3.1 PDG的生成和簡化

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

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

3.2 PDG集合的過濾

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

3.3 基于Weisfeiler-Lehman圖核的克隆檢測(cè)

3.3.1 克隆檢測(cè)方法流程

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

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

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

(1) 對(duì)PDG圖中每個(gè)節(jié)點(diǎn)的標(biāo)簽按照語法類別進(jìn)行Hash處理,將其結(jié)果作為圖的初始標(biāo)記。

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

(3) 迭代過程完成后，若更新后2個(gè)節(jié)點(diǎn)的標(biāo)簽相同，則認(rèn)為以這2個(gè)節(jié)點(diǎn)為根節(jié)點(diǎn)，高度為h的子樹存在同構(gòu)。

(4) 計(jì)算出2個(gè)圖結(jié)構(gòu)間節(jié)點(diǎn)標(biāo)簽集合中相同的節(jié)點(diǎn)標(biāo)簽對(duì)數(shù)，即為圖核的值，若2個(gè)圖的圖核值滿足設(shè)定的閾值范圍，則認(rèn)為2段代碼為克隆代碼。

(5) 動(dòng)態(tài)設(shè)定迭代次數(shù)(較小圖直徑/2),每次迭代完成后統(tǒng)計(jì)圖中相同標(biāo)簽的節(jié)點(diǎn)數(shù)目。

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

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

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

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

4 實(shí)驗(yàn)結(jié)果與分析

4.1 數(shù)據(jù)集介紹與實(shí)驗(yàn)配置

在評(píng)估方法的有效性時(shí)，本文選擇了學(xué)術(shù)界代碼克隆檢測(cè)方法的統(tǒng)一評(píng)估框架BigCloneEval[20]?？蚣苤惺褂玫腂igCloneBench數(shù)據(jù)集是由加拿大的Jeffery和Roy團(tuán)隊(duì)建立的人造Java數(shù)據(jù)集，從25 000個(gè)軟件中提取了包含了43種功能共約59萬個(gè)Java文件，總代碼行數(shù)約350×106行，包含了800多萬對(duì)的真實(shí)克隆對(duì)。所有的實(shí)驗(yàn)都在單機(jī)Ubuntu14.04LTS四核8 GB內(nèi)存的操作系統(tǒng)下進(jìn)行。

4.2 評(píng)估標(biāo)準(zhǔn)與結(jié)果分析

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

4.2.1 召回率

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

4.2.2 精確率

由于BigCloneBench只報(bào)告方法的召回率，而檢測(cè)結(jié)果規(guī)模又較大，因此本文按照學(xué)術(shù)界通用的方法對(duì)克隆結(jié)果進(jìn)行了抽樣檢測(cè)，隨機(jī)選取了400對(duì)克隆代碼進(jìn)行人工確認(rèn)，結(jié)果如表2所示(其他工具的精度結(jié)果取自之前的工作[8])。實(shí)驗(yàn)結(jié)果表明，本文方法的精確率略低于Oreo及CCAligner這些基于token的檢測(cè)工具，但是仍然比NICAD提升了近25%，比DECKARD提升了近50%。因?yàn)橐恍┳兞棵蛘叽a語句的插入或刪除會(huì)導(dǎo)致PDG圖結(jié)構(gòu)的變化，以及預(yù)處理過程中對(duì)PDG進(jìn)行了簡化和節(jié)點(diǎn)標(biāo)簽化的處理，這些都會(huì)導(dǎo)致檢測(cè)結(jié)果中假陽性的存在，降低檢測(cè)結(jié)果的精確率，但是可以根據(jù)用戶需求通過調(diào)整相似度閾值來平衡召回率和精確率。

Table 2 Clone detection results comparison of different methods on BigCloneBench

4.2.3 時(shí)間性能

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

Table 3 Time cost comparison of different methodson different scale codesets

5 結(jié)束語

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

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