基于程序向量樹(shù)的代碼克隆檢測(cè)

曾 杰，賁可榮，張 獻(xiàn)，李曉偉，周 全

1.海軍工程大學(xué)電子工程學(xué)院，武漢 430033

2.北京京航計(jì)算通訊研究所，北京 100074

3.武漢大學(xué)計(jì)算機(jī)學(xué)院，武漢 430072

1 引言

復(fù)制一段代碼，經(jīng)過(guò)修改或者不修改，使得兩個(gè)或多個(gè)代碼片段彼此相似，稱之為代碼克隆[1]。代碼克隆能夠加速軟件開(kāi)發(fā)，但也會(huì)導(dǎo)致缺陷重復(fù)（bug replication）現(xiàn)象廣泛存在[2]。當(dāng)原始代碼存在缺陷時(shí)，克隆的代碼通常也存在相同缺陷，會(huì)使得缺陷在軟件系統(tǒng)中散播開(kāi)來(lái)，但是缺陷修復(fù)過(guò)程往往難以覆蓋所有的克隆點(diǎn)。針對(duì)此類(lèi)問(wèn)題，基于代碼克隆檢測(cè)的復(fù)用缺陷檢測(cè)技術(shù)被廣泛研究[3-5]，取得了良好的應(yīng)用效果。因此，代碼克隆檢測(cè)作為一項(xiàng)基礎(chǔ)分析技術(shù)，對(duì)于維護(hù)軟件質(zhì)量具有重要意義。

Bellon等人[6]按相似程度由高到低將代碼克隆分為T(mén)ype-1到Type-4共計(jì)四種類(lèi)型。Svajlenko等人[7]進(jìn)一步將Type-3和Type-4兩種類(lèi)型克隆根據(jù)字面相似程度統(tǒng)一劃分為三種類(lèi)型：Strongly Type-3，相似度范圍為[0.7,1.0)；Moderately Type-3，相似度范圍為[0.5，0.7)；Weakly Type-3或Type-4，相似度范圍為[0，0.5)。四種類(lèi)型的代碼克隆在文獻(xiàn)[8]中被舉例列出。

傳統(tǒng)代碼克隆檢測(cè)方法利用不同層次的源代碼表征，主要分為基于文本、單詞、抽象語(yǔ)法樹(shù)、程序依賴圖、度量元和混合多種表示等六類(lèi)[1]，如NiCad[9]、CCFinder[10]、Deckard[11]和SourcererCC[12]等。這些方法針對(duì)字面相似度較高的克隆類(lèi)型進(jìn)行檢測(cè)時(shí)具有一定優(yōu)勢(shì)，但是針對(duì)字面相似度較低的克隆類(lèi)型，如Moderately Type-3和Type-4，則有效性不足。因此，針對(duì)復(fù)雜類(lèi)型克隆，究竟選取何種特征來(lái)分析代碼相似性和完成克隆檢測(cè)，仍是一個(gè)復(fù)雜的科學(xué)問(wèn)題。

為此，本文提出一種基于程序向量樹(shù)的代碼克隆檢測(cè)方法，通過(guò)在詞法和語(yǔ)法層面上分別融合單詞的語(yǔ)義信息和抽象語(yǔ)法樹(shù)的結(jié)構(gòu)信息，為檢測(cè)字面相似度低的復(fù)雜類(lèi)型克隆提供一種解決方案。本文的程序向量樹(shù)是抽象語(yǔ)法樹(shù)的一種變體，通過(guò)將抽象語(yǔ)法樹(shù)的所有樹(shù)節(jié)點(diǎn)賦值一個(gè)向量表示，即可得到?；诔绦蛳蛄繕?shù)表示方法進(jìn)行代碼相似性分析，旨在避免基于嚴(yán)格樹(shù)結(jié)構(gòu)匹配的相似性分析方法所面臨的“是即是，非即非”問(wèn)題，通過(guò)將代碼間的相似程度量化，以期更好地應(yīng)對(duì)代碼克隆后在字面上的復(fù)雜變化。

本文方法在真實(shí)代碼克隆的大規(guī)模標(biāo)準(zhǔn)數(shù)據(jù)集BigCloneBench[7]上進(jìn)行評(píng)測(cè)，并與相關(guān)方法進(jìn)行比較，證實(shí)了方法有效性。為保證實(shí)驗(yàn)可再現(xiàn)，相關(guān)代碼和數(shù)據(jù)已開(kāi)源（https://github.com/zyj183247166/ProgramVectorTree）。

2 相關(guān)工作

Whale[13]將克隆檢測(cè)過(guò)程分為兩個(gè)階段：代碼表示和相似性分析。代碼表示方法包括文本、單詞、抽象語(yǔ)法樹(shù)、程序依賴圖、度量元等[1]。Tufano等人[14]研究表明，不同的代碼表示方法在用于檢測(cè)代碼克隆時(shí)，具有互補(bǔ)性。

早期克隆檢測(cè)方法主要基于文本展開(kāi)工作，如Dup[15]和NiCad[9]。兩者均以行為單位，進(jìn)行代碼片段間的相互比較。后者相較于前者，能夠?qū)ψ兞棵M(jìn)行標(biāo)準(zhǔn)化處理，較小程度上能夠適應(yīng)代碼克隆后的變量名修改與變化。

CCFinder[10]基于程序單詞展開(kāi)工作，首先利用詞法分析將程序轉(zhuǎn)變?yōu)閱卧~的序列，然后利用后綴樹(shù)算法尋找兩個(gè)單詞序列的公共子序列，完成克隆檢測(cè)。與之類(lèi)似，CP-Miner[3]利用頻繁項(xiàng)挖掘方法來(lái)實(shí)現(xiàn)公共子序列，不同之處在于CCFinder針對(duì)變量名進(jìn)行一致性處理，因此對(duì)于Type-2類(lèi)型克隆[6]尤為有效。

無(wú)論是利用程序文本還是程序單詞，相關(guān)方法都局限于詞法層面。比較而言，基于抽象語(yǔ)法樹(shù)的方法能夠檢測(cè)更為復(fù)雜的克隆。Baxter等人[16]通過(guò)檢測(cè)不同抽象語(yǔ)法樹(shù)的最大子樹(shù)來(lái)識(shí)別代碼克隆。但是，共同子樹(shù)查詢計(jì)算復(fù)雜，耗時(shí)巨大。為此，一些方法首先將抽象語(yǔ)法樹(shù)編碼為向量，然后比較向量距離，完成代碼間的相似度測(cè)量。比如，Yamaguchi等人[17]通過(guò)識(shí)別特殊模式的節(jié)點(diǎn)和子樹(shù)的數(shù)目，將抽象語(yǔ)法樹(shù)表示為向量；Deckard[11]區(qū)分重要節(jié)點(diǎn)和不重要節(jié)點(diǎn)，將子樹(shù)表示為向量，再合并不同子樹(shù)將整棵樹(shù)表示為最終向量。為了減少向量比較開(kāi)銷(xiāo)，Deckard使用局部敏感哈希算法來(lái)完成向量聚類(lèi)，識(shí)別代碼克隆。

基于程序依賴圖的方法則更多關(guān)注于程序語(yǔ)義信息，利用子圖同構(gòu)分析來(lái)檢測(cè)代碼克隆，如GPLAG[18]和CBCD[19]。相較于公共子樹(shù)查找，子圖同構(gòu)檢測(cè)開(kāi)銷(xiāo)更大。為此，Li等人[20]將程序依賴圖在保持主要信息的基礎(chǔ)上，轉(zhuǎn)化為樹(shù)結(jié)構(gòu)，然后基于公共子樹(shù)查找完成克隆檢測(cè)。

基于度量元的方法[21]將代碼片段表示為一系列度量元（如圈復(fù)雜度）的取值向量。但是這種方法過(guò)于抽象，導(dǎo)致誤報(bào)率很高，往往將完全不相關(guān)的兩段代碼報(bào)告為代碼克隆。因此，此類(lèi)方法存在較大弊端。

傳統(tǒng)方法大多基于上述五種表示或者混合幾種表示，再人工定義需要提取的程序特征，最后制定代碼克隆判定規(guī)則。不同于這些方法，基于深度學(xué)習(xí)的代碼克隆檢測(cè)方法能夠自動(dòng)學(xué)習(xí)或優(yōu)化程序特征。深度學(xué)習(xí)起初在自然語(yǔ)言和圖像處理等領(lǐng)域取得了成功，之后逐步被應(yīng)用到了程序分析領(lǐng)域。它的最大優(yōu)勢(shì)是擺脫“特征工程”難題，能夠自動(dòng)學(xué)習(xí)出數(shù)據(jù)特征。

2016年，White等人[22]用遞歸自編碼器模型（recursive autoencoders，RAE）[23]來(lái)自動(dòng)化學(xué)習(xí)出可用于完成代碼相似性分析的程序特征，檢測(cè)到了傳統(tǒng)方法如Deckard[11]等無(wú)法檢測(cè)到的代碼克隆。2018年，Oreo[8]則先基于選定的度量元提取程序特征，然后利用具有對(duì)稱結(jié)構(gòu)的深度神經(jīng)網(wǎng)絡(luò)來(lái)進(jìn)一步優(yōu)化程序特征，并用最后學(xué)習(xí)出的特征來(lái)完成代碼克隆的二分判定。

對(duì)于字面相似度較高的代碼克隆，上述相關(guān)方法檢測(cè)效果良好。但是，對(duì)于字面相似度較低的克隆類(lèi)型，則有效性仍然不足，而本文正是針對(duì)這一問(wèn)題進(jìn)行研究。

在評(píng)測(cè)用的標(biāo)準(zhǔn)數(shù)據(jù)集方面，早期的克隆方法缺少統(tǒng)一，使得不同的方法不能進(jìn)行合理比較。為此，Svajlenko等人[7,24]結(jié)合程序搜索和人工驗(yàn)證方法構(gòu)建了一個(gè)真實(shí)克隆的大規(guī)模標(biāo)準(zhǔn)數(shù)據(jù)集Big-CloneBench，并針對(duì)十余種克隆工具完成了評(píng)測(cè)，被廣泛使用。該數(shù)據(jù)集也作為評(píng)價(jià)本文方法和對(duì)比方法的基準(zhǔn)數(shù)據(jù)集。

代碼克隆檢測(cè)方法的可擴(kuò)展性[25]是指檢測(cè)方法應(yīng)用于較大規(guī)模系統(tǒng)時(shí)，時(shí)間和空間開(kāi)銷(xiāo)合理。在該方面，SourcererCC[12]和Oreo[8]均采取過(guò)濾機(jī)制縮小候選克隆的規(guī)模，再進(jìn)行進(jìn)一步判定。郭穎等人[26]借鑒網(wǎng)頁(yè)查重中的Simhash算法思想實(shí)現(xiàn)面向大規(guī)模軟件系統(tǒng)進(jìn)行克隆檢測(cè)。D-CCFinder[27]則在CCFinder的基礎(chǔ)上采取并行機(jī)制加速運(yùn)算過(guò)程。不同于它們，Deckard[11]利用向量聚類(lèi)完成克隆檢測(cè)，使用局部敏感哈希算法在高維向量集合中完成近似最近鄰搜索[28]來(lái)縮小候選克隆規(guī)模。與Deckard類(lèi)似，本文方法將代碼片段最終表示為數(shù)字向量，同樣需要完成近似最近鄰搜索。但是，Oreo[8]聲稱，Deckard的方法在BigCloneBench上評(píng)測(cè)時(shí)，由于中間數(shù)據(jù)龐大，導(dǎo)致評(píng)測(cè)失敗。因此，本文改用導(dǎo)航展開(kāi)圖（navigating spreading-out graph，NSG）[29]算法完成近似最近鄰搜索。

3 基于程序向量樹(shù)的代碼克隆檢測(cè)方法

代碼克隆操作的字面修改主要體現(xiàn)在兩方面：一是在詞法層面，程序單詞序列發(fā)生了變化，而程序單詞是程序的基本單元；二是在語(yǔ)法層面，程序的抽象語(yǔ)法樹(shù)結(jié)構(gòu)發(fā)生變化，而抽象語(yǔ)法樹(shù)則規(guī)定了程序執(zhí)行的具體語(yǔ)義操作如何進(jìn)行以及按照什么順序進(jìn)行。因此，為了充分應(yīng)對(duì)克隆操作進(jìn)行時(shí)在字面上的修改，本文方法結(jié)合詞法與語(yǔ)法層面這兩方面信息完成克隆檢測(cè)，整體框架如圖1所示。

檢測(cè)過(guò)程包括兩個(gè)階段：構(gòu)造程序向量樹(shù)；向量編碼與近鄰向量搜索。前一階段旨在融合程序單詞的分布式語(yǔ)義信息和抽象語(yǔ)法樹(shù)的結(jié)構(gòu)信息；后一階段的目標(biāo)是將每個(gè)代碼片段基于程序向量樹(shù)結(jié)構(gòu)編碼為定長(zhǎng)向量，再基于向量比較完成克隆檢測(cè)。

3.1 構(gòu)造程序向量樹(shù)

傳統(tǒng)基于文本和單詞的代碼克隆檢測(cè)方法關(guān)注于程序字面信息，在處理語(yǔ)義相似而字面不同的單詞時(shí)，無(wú)法建立不同單詞之間的相似關(guān)系，因此無(wú)法應(yīng)對(duì)存在復(fù)雜字面變化的代碼克隆。為此，本文借鑒DLC（deep learning code）[22]的思路，使用統(tǒng)計(jì)語(yǔ)言模型來(lái)分析不同字面單詞的語(yǔ)義相似性。比如，“for”和“while”這兩個(gè)程序關(guān)鍵字，在字面上完全不同，但是在向量空間中的分布式表示是相近的。

Fig.1 Overall framework of code clone detection based on program vector tree圖1 基于程序向量樹(shù)的代碼克隆檢測(cè)整體框架

本文的統(tǒng)計(jì)語(yǔ)言模型使用Mikolov等人提出的word2vec[32]，該模型對(duì)于分析單詞之間的語(yǔ)義相似性尤其有效，具體包括兩種訓(xùn)練模型：CBOW模型和Skip-gram模型。兩種模型結(jié)構(gòu)見(jiàn)文獻(xiàn)[32]的圖1。本文具體使用Skip-gram模型，計(jì)算公式如下：

p(Wi|Wt),t-k≤i≤t+k（1）即對(duì)于訓(xùn)練語(yǔ)料庫(kù)中的所有單詞，利用初始化參數(shù)的投射模型預(yù)測(cè)其上下文單詞的概率，并與真實(shí)出現(xiàn)的單詞進(jìn)行比較，計(jì)算損失值。降低損失值作為參數(shù)優(yōu)化的目標(biāo)。因此，最終學(xué)習(xí)出的每個(gè)單詞的嵌入表示能夠反映出訓(xùn)練語(yǔ)料庫(kù)中單詞出現(xiàn)的統(tǒng)計(jì)規(guī)律，而不同單詞相互之間的相似關(guān)系便可以用嵌入表示之間的距離進(jìn)行表示。

本文選取BigCloneBench中的所有Java程序構(gòu)建程序庫(kù)。為了獲取word2vec模型的訓(xùn)練語(yǔ)料庫(kù)，本文利用Eclipse平臺(tái)的JDT（Java development tool）工具套件自動(dòng)化抽取程序庫(kù)中所有Java程序的抽象語(yǔ)法樹(shù)，并針對(duì)每一棵語(yǔ)法樹(shù)按后序遍歷方式將所有葉子節(jié)點(diǎn)對(duì)應(yīng)的單詞排成序列，形成一個(gè)文本。在抽取過(guò)程中，字符串、字符常量、整數(shù)以及浮點(diǎn)數(shù)被分別標(biāo)準(zhǔn)化為＜string＞、＜char＞、＜int＞和＜float＞。

利用word2vec模型獲取每個(gè)單詞的詞向量表示以后，將抽象語(yǔ)法樹(shù)的每一個(gè)葉子節(jié)點(diǎn)賦予對(duì)應(yīng)字面單詞的詞向量，形成一棵程序向量樹(shù)。圖2給出了一個(gè)由Java語(yǔ)言編寫(xiě)的示例函數(shù)的代碼，以及其對(duì)應(yīng)的抽象語(yǔ)法樹(shù)和程序向量樹(shù)。其中，Type表示樹(shù)節(jié)點(diǎn)的類(lèi)型，Word表示樹(shù)節(jié)點(diǎn)對(duì)應(yīng)的程序單詞。所有的非葉子節(jié)點(diǎn)均無(wú)具體程序單詞與之對(duì)應(yīng)。

Fig.2 Code,AST and program vector tree of example function print圖2 示例函數(shù)print的代碼、抽象語(yǔ)法樹(shù)和程序向量樹(shù)

3.2 向量編碼與近鄰向量搜索

傳統(tǒng)基于抽象語(yǔ)法樹(shù)的代碼克隆檢測(cè)方法主要是尋找兩個(gè)程序抽象語(yǔ)法樹(shù)的相同子樹(shù)。由于是嚴(yán)格匹配，使得代碼克隆后存在復(fù)雜修改與變化時(shí)，檢測(cè)方法失效。本文在得到程序向量樹(shù)以后，基于樹(shù)結(jié)構(gòu)和葉子節(jié)點(diǎn)對(duì)應(yīng)的詞向量將整棵樹(shù)編碼為定長(zhǎng)向量，通過(guò)距離度量完成代碼相似性分析，距離小于指定閾值時(shí)判為代碼克隆。

3.2.1 將抽象語(yǔ)法樹(shù)轉(zhuǎn)化為完滿二叉樹(shù)

抽象語(yǔ)法樹(shù)中的一些節(jié)點(diǎn)，對(duì)于度量代碼相似性并無(wú)太大作用，比如Java語(yǔ)言中程序關(guān)鍵字extends對(duì)應(yīng)的樹(shù)節(jié)點(diǎn)。本文借鑒DLC[22]中提出的二叉樹(shù)生成規(guī)則，從抽象語(yǔ)法樹(shù)中去除無(wú)效節(jié)點(diǎn)，縮減樹(shù)的規(guī)模，并將抽象語(yǔ)法樹(shù)由多叉樹(shù)結(jié)構(gòu)轉(zhuǎn)變?yōu)橥隄M二叉樹(shù)，便于后續(xù)計(jì)算。轉(zhuǎn)換過(guò)程結(jié)束后，對(duì)應(yīng)的程序向量樹(shù)也會(huì)變?yōu)橥隄M二叉樹(shù)。完滿二叉樹(shù)的所有非葉子節(jié)點(diǎn)的度數(shù)均為2。

DLC中共提出25種二叉樹(shù)生成規(guī)則（https://sites.google.com/site/deeplearningclone/binary-grammar.pdf?attredirects=0）用于處理抽象語(yǔ)法樹(shù)中子節(jié)點(diǎn)數(shù)目超過(guò)2的非葉子節(jié)點(diǎn)，稱之為Case II類(lèi)型轉(zhuǎn)換。當(dāng)這些非葉子節(jié)點(diǎn)處理完畢后，繼續(xù)處理子節(jié)點(diǎn)數(shù)目為1的非葉子節(jié)點(diǎn)，并根據(jù)父子節(jié)點(diǎn)類(lèi)型的重要程度合并父節(jié)點(diǎn)和它僅有的子節(jié)點(diǎn)，保留更重要節(jié)點(diǎn)，稱之為Case I類(lèi)型轉(zhuǎn)換。

本文在25種二叉樹(shù)生成規(guī)則之外，另外補(bǔ)充了7種生成規(guī)則（https://github.com/zyj183247166/Recursive_autoencoder_xiaojie/blob/master/added_binary_grammar.pdf），用于處理DLC目前不能處理的7種節(jié)點(diǎn)類(lèi)型。否則，無(wú)法將包含這7種類(lèi)型節(jié)點(diǎn)的抽象語(yǔ)法樹(shù)成功轉(zhuǎn)換為完滿二叉樹(shù)。這里以Java程序的AST節(jié)點(diǎn)類(lèi)型ArrayType為例，其Java語(yǔ)法規(guī)則和本文制定的二叉語(yǔ)法規(guī)則見(jiàn)表1。

Table 1 Java grammar and binary grammar of ArrayType表1 ArrayType類(lèi)型的Java語(yǔ)法規(guī)則和二叉樹(shù)生成規(guī)則

轉(zhuǎn)換過(guò)程中，可以從ArrayType類(lèi)型節(jié)點(diǎn)的子節(jié)點(diǎn)中依據(jù)二叉樹(shù)生成規(guī)則抽取出相關(guān)節(jié)點(diǎn)，構(gòu)建二叉樹(shù)。DimensionList是人工制定的非葉子節(jié)點(diǎn)類(lèi)型，主要是為了維持二叉樹(shù)的結(jié)構(gòu)。二叉轉(zhuǎn)換過(guò)程中會(huì)產(chǎn)生只有一個(gè)兒子的父親節(jié)點(diǎn)，如表1中的DimensionList類(lèi)型節(jié)點(diǎn)和Dimension類(lèi)型的子節(jié)點(diǎn)（執(zhí)行語(yǔ)法規(guī)則＜DimensionList＞::=＜Dimension＞產(chǎn)生），則再進(jìn)行一次Case I類(lèi)型轉(zhuǎn)換[22]。對(duì)樹(shù)中所有節(jié)點(diǎn)完成Case I和II類(lèi)型轉(zhuǎn)換以后，就可以將抽象語(yǔ)法樹(shù)轉(zhuǎn)化為完滿二叉樹(shù)。

3.2.2 基于程序向量樹(shù)將程序編碼為定長(zhǎng)向量

前述過(guò)程已經(jīng)將抽象語(yǔ)法樹(shù)和程序向量樹(shù)轉(zhuǎn)換為完滿二叉樹(shù)，所有的葉子節(jié)點(diǎn)均對(duì)應(yīng)一個(gè)具體程序單詞的詞向量。程序向量樹(shù)融合了詞法信息與語(yǔ)法信息，但無(wú)法直接比較。因此，本文提出一種加權(quán)編碼規(guī)則，基于葉子節(jié)點(diǎn)的詞向量表示，編碼出所有非葉子節(jié)點(diǎn)的向量表示，最后將根節(jié)點(diǎn)的向量表示作為整棵樹(shù)的表示。這樣操作以后，不同規(guī)模的程序向量樹(shù)變?yōu)橄嗤L(zhǎng)度的數(shù)字向量，被統(tǒng)一到同一個(gè)比較體系內(nèi)。

Fig.3 Encode program into fixed-sized vector based on its program vector tree圖3 基于程序向量樹(shù)將程序編碼為定長(zhǎng)向量

如圖3所示，每個(gè)葉子節(jié)點(diǎn)對(duì)應(yīng)程序具體單詞的詞向量。接著，對(duì)每一個(gè)非葉子節(jié)點(diǎn)，根據(jù)其子節(jié)點(diǎn)的向量表示進(jìn)行編碼，自下而上直到編碼出根節(jié)點(diǎn)的向量表示，并作為程序的最終表示。自下而上依據(jù)樹(shù)結(jié)構(gòu)對(duì)非葉子節(jié)點(diǎn)進(jìn)行編碼，能夠融合樹(shù)結(jié)構(gòu)信息與葉子節(jié)點(diǎn)對(duì)應(yīng)的單詞的語(yǔ)義信息，使得程序的最終表示能夠很好地表示程序本身。這種自下而上的遞歸編碼過(guò)程與遞歸自編碼器模型[23]類(lèi)似，但又與之有很大不同。遞歸自編碼器模型對(duì)于任意非葉子節(jié)點(diǎn)的兩個(gè)子節(jié)點(diǎn)，采取先壓縮編碼之后再展開(kāi)重建的方式計(jì)算重構(gòu)損失，并在訓(xùn)練樣本上優(yōu)化重構(gòu)損失至局部最優(yōu)，而后再用編碼層去編碼出非葉子節(jié)點(diǎn)的向量表示。本文則省去了深度網(wǎng)絡(luò)訓(xùn)練和優(yōu)化重構(gòu)損失的過(guò)程，直接提出一種加權(quán)編碼規(guī)則對(duì)非葉子節(jié)點(diǎn)進(jìn)行編碼。下文的實(shí)驗(yàn)部分，將對(duì)本文方法與應(yīng)用了遞歸自編碼器模型的DLC[22]進(jìn)行對(duì)比，分析兩者應(yīng)用于代碼克隆檢測(cè)的實(shí)際效果。面向程序向量樹(shù)表示，本文提出的加權(quán)編碼規(guī)則如下：

給定父親節(jié)點(diǎn)p，假設(shè)其兩個(gè)子節(jié)點(diǎn)的向量表示分別為vector1和vector2，兩個(gè)子節(jié)點(diǎn)對(duì)應(yīng)的子樹(shù)的葉子節(jié)點(diǎn)數(shù)目分別為n1和n2（當(dāng)子樹(shù)只有一個(gè)節(jié)點(diǎn)時(shí)，計(jì)數(shù)為1），則p的向量表示是：

這樣做的主要原因是，抽象語(yǔ)法樹(shù)中的任何一個(gè)節(jié)點(diǎn)，其涵蓋的信息應(yīng)當(dāng)包括該節(jié)點(diǎn)對(duì)應(yīng)子樹(shù)所包含的所有葉子節(jié)點(diǎn)（程序單詞）的信息。因此，如果子節(jié)點(diǎn)對(duì)應(yīng)子樹(shù)包含的程序單詞越多，那么在對(duì)其父親節(jié)點(diǎn)進(jìn)行編碼時(shí)，該子節(jié)點(diǎn)貢獻(xiàn)的信息量就應(yīng)當(dāng)更大。通過(guò)添加兩個(gè)和為1的權(quán)重系數(shù)，能夠很好地體現(xiàn)這一特性。

本文對(duì)所有節(jié)點(diǎn)的向量表示進(jìn)行標(biāo)準(zhǔn)化，使向量的模長(zhǎng)為1。這樣就使得任何兩個(gè)不同向量的距離都不會(huì)超過(guò)2，從而劃定了距離范圍，方便了距離閾值的選取。當(dāng)所有程序被編碼為定長(zhǎng)向量后，歐式距離小于設(shè)定距離閾值的向量對(duì)，它們所對(duì)應(yīng)的程序?qū)⒈慌卸榇a克隆。

3.2.3 近鄰向量搜索

目標(biāo)軟件系統(tǒng)的所有程序按一定粒度（如函數(shù)粒度或者文件粒度）抽取出代碼片段后，每個(gè)代碼片段用上述方法可以編碼為數(shù)字向量，形成一個(gè)向量集合。通過(guò)搜索近鄰向量，即可識(shí)別代碼克隆。

但是，對(duì)于大規(guī)模軟件系統(tǒng)，得到的向量集合元素較多，向量間兩兩比較耗時(shí)較大。為了增強(qiáng)本文方法的可擴(kuò)展性，即應(yīng)用于大規(guī)模軟件系統(tǒng)時(shí)的時(shí)間和空間開(kāi)銷(xiāo)合理，本文基于導(dǎo)航展開(kāi)圖算法[29]完成近似最近鄰搜索[28]。近似最近鄰搜索無(wú)需在向量集合內(nèi)部完成嚴(yán)格的兩兩比較，可以快速地從向量集合中搜索出目標(biāo)查詢向量的近似最近鄰向量。當(dāng)搜索出近似最近鄰向量以后，再進(jìn)一步用距離閾值進(jìn)行篩選，就能夠縮小候選克隆對(duì)規(guī)模，減少計(jì)算開(kāi)銷(xiāo)。

導(dǎo)航展開(kāi)圖算法基于K近鄰圖算法[30]演變而來(lái)。K近鄰圖算法首先將向量集合中的每個(gè)向量看作空間中的一個(gè)點(diǎn)，然后構(gòu)建K近鄰圖，并在圖中搜索查詢向量的近鄰向量。給定一個(gè)查詢向量，在圖中隨機(jī)選取一個(gè)起點(diǎn)，然后檢查該起點(diǎn)的相鄰點(diǎn)與查詢向量的距離是否更近。如果更近，則該相鄰點(diǎn)作為新的搜索起點(diǎn)，直到無(wú)更近點(diǎn)為止。導(dǎo)航展開(kāi)圖算法對(duì)K近鄰圖進(jìn)行了優(yōu)化，主要是去除圖的冗余邊，從而減少搜索時(shí)間。

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

4.1 實(shí)驗(yàn)數(shù)據(jù)集與評(píng)測(cè)指標(biāo)

本文方法在真實(shí)代碼克隆的大規(guī)模標(biāo)準(zhǔn)數(shù)據(jù)集BigCloneBench[7,31]上進(jìn)行評(píng)測(cè)。該數(shù)據(jù)集分為標(biāo)簽數(shù)據(jù)庫(kù)和bcb_reduced源碼庫(kù)兩部分。bcb_reduced源碼庫(kù)中有43個(gè)子文件夾，共存儲(chǔ)了55 499個(gè)Java文件。標(biāo)簽數(shù)據(jù)庫(kù)標(biāo)記了8 584 153個(gè)正克隆對(duì)和279 032個(gè)負(fù)克隆對(duì)，每個(gè)克隆對(duì)反映了兩個(gè)函數(shù)之間的克隆關(guān)系。正克隆對(duì)表示兩個(gè)函數(shù)真實(shí)情況是克隆關(guān)系，負(fù)克隆對(duì)則表示兩個(gè)函數(shù)真實(shí)情況不是克隆關(guān)系。

BigCloneBench的標(biāo)簽數(shù)據(jù)庫(kù)全部來(lái)源于人工驗(yàn)證和標(biāo)記，耗時(shí)巨大，而bcb_reduced源碼庫(kù)中仍有大量函數(shù)之間的克隆關(guān)系尚未被標(biāo)記。因此，當(dāng)克隆檢測(cè)工具面向源碼庫(kù)進(jìn)行評(píng)測(cè)時(shí)，如果其報(bào)告出的克隆對(duì)沒(méi)有被BigCloneBench標(biāo)記，該克隆對(duì)真實(shí)情況是否是克隆關(guān)系仍然有待驗(yàn)證。因此，BigCloneBench主要衡量查全率（Recall）指標(biāo)，而查準(zhǔn)率（Precision）指標(biāo)只能通過(guò)估計(jì)的方式[7]或者隨機(jī)抽樣[8]來(lái)確定。配套有BigCloneEval[31]工具計(jì)算查全率。查全率是指：被評(píng)測(cè)的克隆檢測(cè)工具面向被BigCloneBench標(biāo)記的正克隆對(duì)集合，能夠檢測(cè)出的克隆對(duì)比例。查準(zhǔn)率是指：被評(píng)測(cè)的克隆工具面向bcb_reduced源碼庫(kù)檢測(cè)出的克隆對(duì)，其真實(shí)情況為正克隆對(duì)的比例。

本文進(jìn)一步繪制受試者工作特征（receiver operator characteristic，ROC）曲線，更充分地衡量分類(lèi)器的分類(lèi)性能。ROC曲線包括兩部分：正報(bào)率（true positive rate，TPR）和誤報(bào)率（false positive rate，F(xiàn)PR）。前者等同于查全率，后者反映了分類(lèi)器將負(fù)克隆對(duì)錯(cuò)誤報(bào)告為正克隆對(duì)的比例。所有指標(biāo)的計(jì)算方式見(jiàn)式（3）。

其中，TP表示正克隆對(duì)被檢測(cè)為克隆的個(gè)數(shù)；FP表示負(fù)克隆對(duì)被檢測(cè)為克隆的個(gè)數(shù)；TN表示負(fù)克隆對(duì)被檢測(cè)為非克隆的個(gè)數(shù)；FN表示正克隆對(duì)被檢測(cè)為非克隆的個(gè)數(shù)。

4.2 實(shí)驗(yàn)步驟

本文方法的實(shí)驗(yàn)步驟如下：

（1）實(shí)驗(yàn)數(shù)據(jù)集預(yù)處理

BigCloneBench中仍然存在一定的數(shù)據(jù)噪聲。本文在實(shí)驗(yàn)過(guò)程中移除了BigCloneBench重復(fù)標(biāo)記的克隆對(duì)，并在網(wǎng)址https://github.com/zyj183247166/Recursive_autoencoder_xiaojie/blob/master/duplicate_true_pair_record.txt中解釋。同時(shí)，實(shí)驗(yàn)使用Eclipse平臺(tái)的JDT開(kāi)發(fā)套件從bcb_reduced源碼庫(kù)抽取出所有函數(shù)，并記錄其所在的文件路徑和源碼位置。通過(guò)與BigCloneBench標(biāo)記的函數(shù)位置比較，本文發(fā)現(xiàn)了25個(gè)被錯(cuò)誤標(biāo)記位置的函數(shù)，經(jīng)人工驗(yàn)證后在網(wǎng)址https://github.com/zyj183247166/Recursive_autoencoder_xiaojie/blob/master/wrongLocationMarkedByBigClone-Bench.txt中解釋。為了避免被錯(cuò)誤標(biāo)記的函數(shù)所干擾，實(shí)驗(yàn)從標(biāo)簽數(shù)據(jù)庫(kù)中移除了包含這些函數(shù)的正負(fù)克隆對(duì)。

標(biāo)簽數(shù)據(jù)庫(kù)中的正克隆對(duì)數(shù)目從8 584 153減少到了8 575 774，有3 740個(gè)包含錯(cuò)誤標(biāo)記函數(shù)的克隆對(duì)和4 639個(gè)重復(fù)標(biāo)記的克隆對(duì)被去除。負(fù)克隆對(duì)數(shù)目從279 032減少到278 961個(gè)，有71個(gè)包含錯(cuò)誤標(biāo)記函數(shù)的克隆對(duì)被去除。

（2）訓(xùn)練詞向量

本文使用word2vec[32]來(lái)訓(xùn)練詞向量。源碼庫(kù)中共有31 937 932個(gè)單詞，其中987 474個(gè)獨(dú)特單詞。訓(xùn)練過(guò)程中存在10個(gè)單詞的長(zhǎng)度過(guò)長(zhǎng)，超出了word2vec的限制，如102108.java文件第56行以“_005”開(kāi)頭的單詞，多達(dá)142個(gè)英文字符。針對(duì)這10個(gè)單詞，本文人工標(biāo)定其詞向量為零向量。這樣做，一方面是忽略其對(duì)所在程序最終向量表示的信息貢獻(xiàn)量，另一方面則是維持樹(shù)結(jié)構(gòu)的完整性。如果直接去除這些單詞，會(huì)導(dǎo)致基于程序向量樹(shù)的編碼過(guò)程無(wú)法正常進(jìn)行。詞向量的維數(shù)一般越高表示越精準(zhǔn)，依據(jù)經(jīng)驗(yàn)并綜合考慮計(jì)算開(kāi)銷(xiāo)與表示精確度兩方面因素，詞向量選取長(zhǎng)度為300維左右。由于后續(xù)實(shí)驗(yàn)使用導(dǎo)航展開(kāi)圖算法的開(kāi)源工具包NSG（https://github.com/ZJULearning/nsg），該工具包基于AVX指令進(jìn)行浮點(diǎn)數(shù)處理的加速，要求向量為8的倍數(shù)。因此，最終詞向量的長(zhǎng)度確定為296維。

（3）生成程序向量樹(shù)

從bcd_reduced源碼庫(kù)中共抽取出785 438個(gè)函數(shù)。對(duì)ast2bin（https://github.com/micheletufano/ast2bin）程序作了一定修改，添加了額外7種二叉樹(shù)生成規(guī)則，然后將所有函數(shù)的抽象語(yǔ)法樹(shù)轉(zhuǎn)化為完滿二叉樹(shù)，并將每個(gè)葉子節(jié)點(diǎn)賦值對(duì)應(yīng)單詞的詞向量，得到對(duì)應(yīng)的程序向量樹(shù)。二叉樹(shù)的結(jié)構(gòu)采取列表的方式記錄，列表的每一元素記錄了兩個(gè)子節(jié)點(diǎn)編號(hào)和其父親節(jié)點(diǎn)編號(hào)。

（4）向量編碼與近鄰向量搜索

面向所有的程序向量樹(shù)，使用提出的加權(quán)編碼規(guī)則計(jì)算出程序的最終表示，形成一個(gè)向量集合，共包含了785 438個(gè)向量。

完全進(jìn)行兩兩比較耗時(shí)巨大，本文使用導(dǎo)航展開(kāi)圖算法完成近似最近鄰搜索。首先，使用Efanna（https://github.com/ZJULearning/efanna_graph）工具基于向量集合構(gòu)建K近鄰圖（K值設(shè)定為200）；然后，使用NSG工具包將K近鄰圖轉(zhuǎn)化為導(dǎo)航展開(kāi)圖；接著，對(duì)于向量集合中的每個(gè)向量，以其為查詢向量，在導(dǎo)航展開(kāi)圖中搜索出K個(gè)近似最近鄰向量，作為候選克隆對(duì)返回；最后，用設(shè)定的距離閾值，基于歐式距離從候選克隆對(duì)中篩選出要報(bào)告的克隆對(duì)，并在BigCloneBench上計(jì)算相關(guān)指標(biāo)。

K值的設(shè)定依據(jù)目標(biāo)向量集合的規(guī)模，參照論文提出者的做法依據(jù)經(jīng)驗(yàn)設(shè)定[29]，本文實(shí)驗(yàn)中設(shè)定K為200，如果設(shè)定的K值超過(guò)200，則近鄰搜索需要返回更多的候選克隆對(duì)。以K值設(shè)定200為例，在785 438個(gè)向量的集合中完成近似最近鄰搜索以后，會(huì)返回157 087 600個(gè)候選克隆對(duì)，進(jìn)一步需要計(jì)算候選克隆對(duì)中兩個(gè)向量之間的歐式距離與設(shè)定閾值之間的大小關(guān)系。因此，K值每增大1，候選克隆對(duì)數(shù)目便增多785 438個(gè)，導(dǎo)致時(shí)間開(kāi)銷(xiāo)增大。

4.3 實(shí)驗(yàn)結(jié)果

為了分析距離閾值的選取對(duì)分類(lèi)器性能的影響以及選取合適的距離閾值，本文方法先直接應(yīng)用于BigCloneBench上標(biāo)記過(guò)的正負(fù)克隆對(duì)，繪制評(píng)測(cè)后的ROC曲線（包括TPR和FPR），如圖4所示。TPR面向不同類(lèi)型克隆分別計(jì)算。由于數(shù)據(jù)集中負(fù)標(biāo)簽克隆對(duì)沒(méi)有克隆類(lèi)型劃分，因此FPR面向所有標(biāo)記為負(fù)的克隆對(duì)進(jìn)行計(jì)算。ROC曲線下的面積反映了被評(píng)測(cè)分類(lèi)器的綜合性能。

Fig.4 ROC curves for detecting clones of different types in BigCloneBench圖4 面向BigCloneBench中不同類(lèi)型克隆進(jìn)行檢測(cè)的ROC曲線

可以看出，從Type-1到Type-4類(lèi)型，由于代碼克隆的字面相似度逐漸降低，本文方法的綜合檢測(cè)性能也在逐漸下降。對(duì)于字面完全相同或者改動(dòng)很少的Type-1、Type-2以及Very Strongly Type-3三種類(lèi)型克隆，本文方法能夠達(dá)到很高的TPR，同時(shí)FPR很低。隨著距離閾值的增加，針對(duì)其余幾種克隆類(lèi)型的TPR在逐漸增加，意味著能夠檢測(cè)更多克隆。但是，F(xiàn)PR也在逐漸增加，意味著誤報(bào)逐漸增多，而在克隆檢測(cè)工具的實(shí)際應(yīng)用過(guò)程中太多誤報(bào)是不可接受的。因此，必須在兩者之間做出權(quán)衡，對(duì)于距離閾值進(jìn)行合理選擇。

后續(xù)實(shí)驗(yàn)選取距離值0.7作為閾值，因?yàn)檫@個(gè)閾值下的FPR很低，只有0.04。也就是對(duì)于100個(gè)真實(shí)情況為負(fù)標(biāo)簽的克隆對(duì)，本文方法只會(huì)將其中大約4個(gè)錯(cuò)誤報(bào)告為克隆，是可以接受的。接著，在此距離閾值下，應(yīng)用本文方法面向bcb_reduced源碼庫(kù)進(jìn)行克隆檢測(cè)，按照4.2節(jié)中的實(shí)驗(yàn)步驟進(jìn)行。如果直接在785 438個(gè)元素的向量集合中兩兩比較，并用numpy.linalg.norm計(jì)算兩個(gè)高維向量（設(shè)為296維）的歐式距離，在實(shí)驗(yàn)機(jī)器上運(yùn)行Python程序，預(yù)估需要14天才能完成全部運(yùn)算，平均10 000次比較需要大約40 ms。應(yīng)用導(dǎo)航展開(kāi)圖算法后，全部時(shí)間開(kāi)銷(xiāo)在30 min左右。這對(duì)于具有大約1 300萬(wàn)行代碼的bcb_reduced源碼庫(kù)來(lái)說(shuō)，克隆檢測(cè)的時(shí)間開(kāi)銷(xiāo)是可以接受的。

在BigCloneBench上評(píng)測(cè)，將本文方法與主流克隆檢測(cè)工具進(jìn)行對(duì)比，包括NiCad[9]、Deckard[11]、SourcererCC[12]、CloneWorks[33]、Oreo[8]和DLC[22]。后兩種工具均應(yīng)用深度學(xué)習(xí)方法完成克隆檢測(cè)。DLC尚未在BigCloneBench上進(jìn)行評(píng)測(cè)，本文復(fù)現(xiàn)了其方法。由于標(biāo)簽數(shù)據(jù)集過(guò)于龐大，對(duì)所有距離閾值進(jìn)行遍歷選取是不現(xiàn)實(shí)的。因此，不太容易找到本文方法的一個(gè)閾值和DLC方法的另一個(gè)閾值去保證這一點(diǎn)，即這兩個(gè)閾值使得兩種方法在標(biāo)簽數(shù)據(jù)集上的誤報(bào)率相同。參照DLC距離閾值的選取規(guī)則，本文設(shè)置其距離閾值為0.25。該閾值下，DLC的誤報(bào)率為0.08，高于本文方法的0.04。在此基礎(chǔ)上，進(jìn)一步比較兩種方法。由于DLC本身沒(méi)考慮到擴(kuò)展性問(wèn)題，本文在復(fù)現(xiàn)過(guò)程中同樣應(yīng)用了導(dǎo)航展開(kāi)圖算法。其余克隆檢測(cè)工具的指標(biāo)均來(lái)源于Oreo的論文[8]。需要說(shuō)明的是，它們的查準(zhǔn)率用隨機(jī)抽樣的方式進(jìn)行評(píng)估。與之不同，本文方法的查準(zhǔn)率利用BigClone-Bench提供的公式去估計(jì)[7]。兩種方式在4.1節(jié)已經(jīng)闡述。此外，本文在實(shí)驗(yàn)過(guò)程中，從BigCloneBench去除了一定的噪聲，詳見(jiàn)4.2節(jié)的實(shí)驗(yàn)數(shù)據(jù)集預(yù)處理步驟。

在時(shí)間開(kāi)銷(xiāo)上，依據(jù)Oreo的論文[8]，Oreo耗費(fèi)1 600 min，CloneWorks耗費(fèi)約110 min，SourcererCC耗費(fèi)約280 min。本文方法耗費(fèi)約99 min，其中word2vec模型訓(xùn)練耗費(fèi)約38 min，處理和生成程序向量樹(shù)耗費(fèi)約20 min，基于程序向量樹(shù)和加權(quán)編碼規(guī)則完成所有程序的向量編碼耗費(fèi)約8 min，近似最近鄰搜索和克隆對(duì)判定耗費(fèi)約33 min。

Table 2 Performance measurements on BigCloneBench of proposed method and compared methods表2 本文方法與對(duì)比方法在BigCloneBench上的性能指標(biāo)

查全率和查準(zhǔn)率等性能對(duì)比結(jié)果在表2中列出，本文使用T1、T2、VST3、ST3、MT3和T4分別作為T(mén)ype-1、Type-2、Very Strongly Type-3、Strongly Type-3、Moderately Type-3和Type-4（Weakly Type-3）幾種克隆類(lèi)型的縮寫(xiě)。對(duì)于T1類(lèi)型克隆，本文方法的查全率是99.99%，而不是100%。主要原因是，存在一個(gè)克隆對(duì)，一個(gè)函數(shù)的編號(hào)是22648747，另一個(gè)函數(shù)的編號(hào)是3516892，被BigCloneBench標(biāo)記為T(mén)ype-1類(lèi)型克隆，而真實(shí)情況經(jīng)過(guò)人工驗(yàn)證并不是，是又一個(gè)數(shù)據(jù)噪聲。所有方法中，Deckard面向T1、T2和VST3類(lèi)型克隆的檢測(cè)性能最差。

除了T1克隆類(lèi)型以外，本文方法在面向字面相似度較低的MT3和T4類(lèi)型克隆進(jìn)行檢測(cè)時(shí)，查全率均優(yōu)于其余方法；在面向T2和VST3類(lèi)型克隆檢測(cè)時(shí)，和表中最優(yōu)方法Oreo十分接近；在面向ST3類(lèi)型克隆檢測(cè)時(shí)，查全率略低。綜合來(lái)看，與主流方法相比，本文方法面向字面相似度較低的代碼克隆進(jìn)行檢測(cè)具有一定的優(yōu)勢(shì)，具備較好的檢測(cè)性能。

事實(shí)上，使用導(dǎo)航展開(kāi)圖算法在大規(guī)模程序向量集合中完成近似最近鄰搜索，搜索過(guò)程返回的近鄰結(jié)果數(shù)目限制了本文方法的性能。如果將查詢向量的近鄰搜索數(shù)目從200進(jìn)一步向上提升，即候選克隆對(duì)的規(guī)模增長(zhǎng)，可以使得查全率進(jìn)一步提升。但是，這樣做也會(huì)使得近似近鄰搜索的時(shí)間開(kāi)銷(xiāo)大量增長(zhǎng)。因此，近鄰搜索的數(shù)目與距離閾值一樣，其選取必須平衡考慮多方面因素。

4.4 討論

本文方法利用統(tǒng)計(jì)語(yǔ)言模型學(xué)習(xí)和分析不同字面單詞的語(yǔ)義相似性，這一點(diǎn)對(duì)于檢測(cè)字面相似度較低的復(fù)雜代碼克隆尤為重要，而嚴(yán)格的匹配方法則無(wú)法應(yīng)對(duì)。圖5給出了BigCloneBench中部分程序單詞和對(duì)應(yīng)的詞向量表示在二維空間中的分布情況。其中，利用t-SNE降維算法[34]對(duì)高維向量進(jìn)行降維，將向量對(duì)應(yīng)的點(diǎn)繪制在二維空間?？梢钥吹?，具有相似語(yǔ)義信息或與同一功能相關(guān)的程序單詞對(duì)應(yīng)的詞向量在空間中距離更近，形成許多簇。

Fig.5 Visualization results of program word embeddings using t-SNE dimension-reduction algorithm圖5 t-SNE算法降維后的程序詞向量的可視化結(jié)果

比如，“cfg”“Configuration”和“config”等均與配置功能有關(guān)；“s”“c”和“u”等均是字母，可能是變量名的縮寫(xiě)；“ZipOutputStream”“zip”和“ZipEntry”等與壓縮功能有關(guān)。利用統(tǒng)計(jì)語(yǔ)言模型學(xué)習(xí)出不同字面單詞之間的關(guān)聯(lián)，可以更好地適應(yīng)克隆后的復(fù)雜修改與變化，而這些是嚴(yán)格匹配方法如NiCad和SourcererCC等無(wú)法做到的。

為了進(jìn)一步闡述本文方法的優(yōu)勢(shì)和不足，本節(jié)列出數(shù)據(jù)集BigCloneBench中三個(gè)字面相似度較低的克隆對(duì)代碼示例，包括本文方法檢測(cè)出的兩個(gè)正報(bào)和一個(gè)誤報(bào)。圖6是本文方法檢測(cè)的一個(gè)正報(bào)克隆對(duì)示例，屬于Strongly Type-3類(lèi)型。從圖6中可以看出，兩個(gè)函數(shù)實(shí)現(xiàn)的功能是對(duì)一個(gè)二維矩陣進(jìn)行轉(zhuǎn)置。這個(gè)克隆對(duì)也能被NiCad[9]檢測(cè)到（設(shè)置閾值為0.3），并且必須是blind renaming模式，即將所有的變量標(biāo)識(shí)符全部標(biāo)準(zhǔn)化為字符“X”。NiCad以行為粒度，基于文本進(jìn)行匹配。如果兩個(gè)代碼片段相同行的比例小于設(shè)定閾值，就會(huì)被判定為代碼克隆。而本文方法則將兩個(gè)代碼片段映射為向量之后，判定向量間的歐式距離是否小于設(shè)定的距離閾值。本文方法和NiCad都能利用語(yǔ)法解析程序來(lái)排除注釋行對(duì)克隆檢測(cè)造成的影響。但是不同的是，本文方法不需要將所有變量名標(biāo)準(zhǔn)化為“X”，就能檢測(cè)到該克隆。這也說(shuō)明，本文方法能夠?qū)W習(xí)出不同字面單詞之間的關(guān)聯(lián)，更能適應(yīng)代碼克隆后的字面修改與變化。而NiCad則是嚴(yán)格匹配方式，無(wú)法做到這一點(diǎn)。

圖7是本文方法檢測(cè)到的另一個(gè)正報(bào)克隆對(duì)的示例，屬于Moderately Type-3類(lèi)型。如圖7所示，兩個(gè)函數(shù)實(shí)現(xiàn)的功能均是將一個(gè)文件添加到zip格式的壓縮包中。圖7中亂碼是BigCloneBench中函數(shù)代碼本身自帶的，但是這些亂碼對(duì)克隆檢測(cè)不會(huì)造成影響，因?yàn)楸疚姆椒ㄒ呀?jīng)將所有程序的字符串常量標(biāo)準(zhǔn)化為＜String＞。雖然兩個(gè)函數(shù)實(shí)現(xiàn)的功能相同，但是它們使用不同的Java程序包來(lái)實(shí)現(xiàn)，在字面上相似度很低。因此，這個(gè)克隆對(duì)不能被NiCad檢測(cè)到。即使NiCad使用了blind renaming策略，兩個(gè)函數(shù)在行粒度上有許多行之間無(wú)法嚴(yán)格匹配上。上述兩個(gè)例子都說(shuō)明了本文方法相對(duì)于嚴(yán)格匹配方法，面向字面相似度較低的克隆進(jìn)行檢測(cè)時(shí)存在的優(yōu)勢(shì)。

但是，本文方法也存在一些誤報(bào)。圖8是一個(gè)誤報(bào)克隆對(duì)示例，兩個(gè)函數(shù)實(shí)現(xiàn)的是完全不同的功能。一個(gè)函數(shù)是將輸入流寫(xiě)入輸出流，操作對(duì)象是steam流。而另一個(gè)函數(shù)則是復(fù)制文件到一個(gè)新文件，并且在實(shí)際實(shí)現(xiàn)時(shí)用到了steam流去讀和寫(xiě)文件。本文方法分析出兩者不同字面單詞之間的相似性，如“safeClose”與“close”；也分析出兩者在語(yǔ)法樹(shù)結(jié)構(gòu)上的相似性，如均使用了while循環(huán)。但是，這兩個(gè)函數(shù)按克隆的定義[6]，確實(shí)不屬于克隆關(guān)系。對(duì)于這種誤報(bào)，目前只能使用人工驗(yàn)證的方式去解決。

Fig.6 Example 1 of true positive clone圖6 正報(bào)克隆對(duì)示例1

Fig.7 Example 2 of true positive clone圖7 正報(bào)克隆對(duì)示例2

Fig.8 False positive clone example圖8 誤報(bào)克隆對(duì)示例

5 總結(jié)與展望

本文主要針對(duì)字面相似度低的代碼克隆存在的檢測(cè)困難問(wèn)題，提出一種基于程序向量樹(shù)的檢測(cè)方法。通過(guò)程序向量樹(shù)表示去融合程序單詞的詞法信息和語(yǔ)法結(jié)構(gòu)信息，并利用統(tǒng)計(jì)語(yǔ)言模型建模不同字面單詞之間的相似性，從而提升克隆檢測(cè)方法對(duì)克隆后字面修改與變化的適應(yīng)性，相較于基于單詞、文本以及樹(shù)等代碼表示進(jìn)行嚴(yán)格匹配的方法有很大改進(jìn)。本文方法在真實(shí)代碼克隆的大規(guī)模標(biāo)準(zhǔn)數(shù)據(jù)集BigCloneBench上進(jìn)行了評(píng)測(cè)，并與主流克隆檢測(cè)方法進(jìn)行了比較，證實(shí)了有效性。

本文方法的局限在于，目前只針對(duì)Java程序，以及評(píng)測(cè)數(shù)據(jù)集BigCloneBench只包含Java程序，因此遷移到其他程序語(yǔ)言需要進(jìn)一步提出針對(duì)性的二叉樹(shù)生成規(guī)則。此外，方法工作于函數(shù)粒度，對(duì)于不能完整解析出抽象語(yǔ)法樹(shù)的程序片段則無(wú)法應(yīng)用。下一步，會(huì)將代碼克隆檢測(cè)模型融入到實(shí)際的復(fù)用缺陷檢測(cè)工具中，去尋找目標(biāo)軟件中從已知缺陷代碼復(fù)用而來(lái)的潛在缺陷。