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

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

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

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

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

1 引言

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

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

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

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

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

2 相關工作

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.1 構造程序向量樹

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

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

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

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

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

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

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

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

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

3.2.1 將抽象語法樹轉化為完滿二叉樹

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

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

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

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

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

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

前述過程已經將抽象語法樹和程序向量樹轉換為完滿二叉樹，所有的葉子節點均對應一個具體程序單詞的詞向量。程序向量樹融合了詞法信息與語法信息，但無法直接比較。因此，本文提出一種加權編碼規則，基于葉子節點的詞向量表示，編碼出所有非葉子節點的向量表示，最后將根節點的向量表示作為整棵樹的表示。這樣操作以后，不同規模的程序向量樹變為相同長度的數字向量，被統一到同一個比較體系內。

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

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

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

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

本文對所有節點的向量表示進行標準化，使向量的模長為1。這樣就使得任何兩個不同向量的距離都不會超過2，從而劃定了距離范圍，方便了距離閾值的選取。當所有程序被編碼為定長向量后，歐式距離小于設定距離閾值的向量對，它們所對應的程序對將被判定為代碼克隆。

3.2.3 近鄰向量搜索

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

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

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

4 實驗與結果分析

4.1 實驗數據集與評測指標

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

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

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

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

4.2 實驗步驟

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

（1）實驗數據集預處理

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

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

（2）訓練詞向量

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

（3）生成程序向量樹

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

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

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

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

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

4.3 實驗結果

為了分析距離閾值的選取對分類器性能的影響以及選取合適的距離閾值，本文方法先直接應用于BigCloneBench上標記過的正負克隆對，繪制評測后的ROC曲線（包括TPR和FPR），如圖4所示。TPR面向不同類型克隆分別計算。由于數據集中負標簽克隆對沒有克隆類型劃分，因此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在逐漸增加，意味著能夠檢測更多克隆。但是，FPR也在逐漸增加，意味著誤報逐漸增多，而在克隆檢測工具的實際應用過程中太多誤報是不可接受的。因此，必須在兩者之間做出權衡，對于距離閾值進行合理選擇。

后續實驗選取距離值0.7作為閾值，因為這個閾值下的FPR很低，只有0.04。也就是對于100個真實情況為負標簽的克隆對，本文方法只會將其中大約4個錯誤報告為克隆，是可以接受的。接著，在此距離閾值下，應用本文方法面向bcb_reduced源碼庫進行克隆檢測，按照4.2節中的實驗步驟進行。如果直接在785 438個元素的向量集合中兩兩比較，并用numpy.linalg.norm計算兩個高維向量（設為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上進行評測，本文復現了其方法。由于標簽數據集過于龐大，對所有距離閾值進行遍歷選取是不現實的。因此，不太容易找到本文方法的一個閾值和DLC方法的另一個閾值去保證這一點，即這兩個閾值使得兩種方法在標簽數據集上的誤報率相同。參照DLC距離閾值的選取規則，本文設置其距離閾值為0.25。該閾值下，DLC的誤報率為0.08，高于本文方法的0.04。在此基礎上，進一步比較兩種方法。由于DLC本身沒考慮到擴展性問題，本文在復現過程中同樣應用了導航展開圖算法。其余克隆檢測工具的指標均來源于Oreo的論文[8]。需要說明的是，它們的查準率用隨機抽樣的方式進行評估。與之不同，本文方法的查準率利用BigClone-Bench提供的公式去估計[7]。兩種方式在4.1節已經闡述。此外，本文在實驗過程中，從BigCloneBench去除了一定的噪聲，詳見4.2節的實驗數據集預處理步驟。

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

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

查全率和查準率等性能對比結果在表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%。主要原因是，存在一個克隆對，一個函數的編號是22648747，另一個函數的編號是3516892，被BigCloneBench標記為Type-1類型克隆，而真實情況經過人工驗證并不是，是又一個數據噪聲。所有方法中，Deckard面向T1、T2和VST3類型克隆的檢測性能最差。

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

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

4.4 討論

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

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

比如，“cfg”“Configuration”和“config”等均與配置功能有關；“s”“c”和“u”等均是字母，可能是變量名的縮寫；“ZipOutputStream”“zip”和“ZipEntry”等與壓縮功能有關。利用統計語言模型學習出不同字面單詞之間的關聯，可以更好地適應克隆后的復雜修改與變化，而這些是嚴格匹配方法如NiCad和SourcererCC等無法做到的。

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

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

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

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 總結與展望

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

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