基于程序向量樹的代碼克隆檢測

曾 杰，賁可榮，張 獻，李曉偉，周 全

1.海軍工程大學電子工程學院，武漢 430033

2.北京京航計算通訊研究所，北京 100074

3.武漢大學計算機學院，武漢 430072

1 引言

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

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

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

為此，本文提出一種基于程序向量樹的代碼克隆檢測方法，通過在詞法和語法層面上分別融合單詞的語義信息和抽象語法樹的結(jié)構(gòu)信息，為檢測字面相似度低的復雜類型克隆提供一種解決方案。本文的程序向量樹是抽象語法樹的一種變體，通過將抽象語法樹的所有樹節(jié)點賦值一個向量表示，即可得到。基于程序向量樹表示方法進行代碼相似性分析，旨在避免基于嚴格樹結(jié)構(gòu)匹配的相似性分析方法所面臨的“是即是，非即非”問題，通過將代碼間的相似程度量化，以期更好地應對代碼克隆后在字面上的復雜變化。

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

2 相關(guān)工作

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

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

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

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

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

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

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

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

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

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

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

3 基于程序向量樹的代碼克隆檢測方法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Table 1 Java grammar and binary grammar of ArrayType表1 ArrayType類型的Java語法規(guī)則和二叉樹生成規(guī)則

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

3.2.2 基于程序向量樹將程序編碼為定長向量

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

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

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

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

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

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

3.2.3 近鄰向量搜索

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

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

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

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

4.1 實驗數(shù)據(jù)集與評測指標

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

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

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

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

4.2 實驗步驟

本文方法的實驗步驟如下：

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

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

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

（2）訓練詞向量

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

（3）生成程序向量樹

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

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

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

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

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

4.3 實驗結(jié)果

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

Fig.4 ROC curves for detecting clones of different types in BigCloneBench圖4 面向BigCloneBench中不同類型克隆進行檢測的ROC曲線

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

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

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

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

Table 2 Performance measurements on BigCloneBench of proposed method and compared methods表2 本文方法與對比方法在BigCloneBench上的性能指標

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

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

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

4.4 討論

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

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”等均是字母，可能是變量名的縮寫；“ZipOutputStream”“zip”和“ZipEntry”等與壓縮功能有關(guān)。利用統(tǒng)計語言模型學習出不同字面單詞之間的關(guān)聯(lián)，可以更好地適應克隆后的復雜修改與變化，而這些是嚴格匹配方法如NiCad和SourcererCC等無法做到的。

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

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

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

Fig.6 Example 1 of true positive clone圖6 正報克隆對示例1

Fig.7 Example 2 of true positive clone圖7 正報克隆對示例2

Fig.8 False positive clone example圖8 誤報克隆對示例

5 總結(jié)與展望

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

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