基于分層特征的代碼克隆檢測方法

張冬梅，陳永樂，楊玉麗

（太原理工大學 信息與計算機學院，山西 晉中 030600）

0 概述

代碼克隆是指存在于代碼庫中兩個及以上相同或者相似的源代碼片段［1］，當開發人員通過復制、粘貼、修改等方式重用現有代碼片段時會產生代碼克隆［2］。現有研究表明一個軟件系統的全部代碼庫中平均有7%～23%是克隆代碼［3-4］，例如，Linux 中存在22.3%［5］的代碼克隆，JDK 中存在29%［6］的代碼克隆。代碼克隆在一定程度上可提高開發效率，降低函數調用的時間成本，但也增加了軟件維護的成本，例如：克隆一段含有未知bug 的代碼，會導致bug 傳播［7］，維護者需要檢查所有克隆代碼中是否存在該bug［8］；修改一段代碼需要對該段代碼中的所有克隆進行一致性修改，若修改不一致則會引入新的bug，降低軟件整體質量。目前，研究人員提出4 種代碼克隆類型［9］。類型1 表示除了空格和注釋之外，兩個代碼片段完全相同的代碼對。類型2 表示除了變量名、類型名和函數名之外都相同的代碼對。類型3表示有若干語句的增刪，或使用不同的標識符、文字、類型、空格、布局和注釋，但是依然相似的代碼對。類型4 表示相同功能的異構代碼，在文本或者語法上不相似，但在語義上具有相似性。

為維護軟件質量、檢測和防止新的bug 及降低開發風險和成本，研究人員提出多種代碼克隆檢測技術和工具［10］，然而現有檢測方法除了token 轉換以外，其他方法都需要將源代碼轉換為抽象語法樹或者程序依賴圖等，中間過程復雜且成本高，難以擴展應用范圍［11］。雖然現有token 方法因檢測成本低、過程簡單，成為有效的克隆檢測方法，但目前基于token 的克隆檢測研究中通常使用字符串匹配方法或各token 類在代碼中出現頻次的相似性度量方法，并沒有挖掘代碼內的語義信息。

為解決復雜語義形式的代碼克隆檢測問題，本文將代碼表征為統一標記，利用基于注意力機制的雙層（Bi-directional Long Short-Term Memory，Bi-LSTM）網絡直接從標記描述的代碼中提取出深層語義特征，將基于注意力機制的Bi-LSTM網絡嵌入Siamese 結構［12-13］中，使代碼克隆檢測問題轉化為二分類問題，即檢測代碼對為克隆對或非克隆對，并在已知克隆對和非克隆對的數據集上訓練檢測模型。

1 相關工作

1.1 代碼克隆檢測技術

目前，代碼克隆檢測主要包括基于文本、標記、樹、圖、度量這5 種方法［2］：

1）基于文本的代碼克隆檢測方法使用基于行的字符串匹配算法［14-15］。該方法簡單快速，主要針對類型1 的克隆，但不能檢測復雜類型。

2）基于標記的代碼克隆檢測方法移除了源碼中的空格和注釋，將代碼轉換為統一的標記，利用后綴樹比配算法［3］、最長公共子序列匹配算法［6］或比對各標記類型出現次數的相似性［16-17］進行克隆檢測。該方法對格式化和重命名更改具有較強的魯棒性，可以處理類型1、類型2、類型3 甚至是類型4 的克隆，但由于標記的不同排列產生的代碼功能也不盡相同，因此在基于標記的克隆檢測方法中應考慮語義信息。

3）基于樹的代碼克隆檢測方法對目標代碼生成一個抽象語法樹，利用樹匹配算法或將樹嵌入空間檢測相似的子樹［18-19］。基于樹的代碼克隆檢測方法考慮了代碼的語法結構，可容忍語句數量的變化，并檢測類型1和類型4 的代碼克隆。但由于該方法需要大量的時間開銷和內存占用，因此無法擴展到大型代碼庫［20］。

4）基于圖的代碼克隆檢測方法為代碼生成控制流 圖（Control Flow Graph，CFG）或程序依賴圖（Procedure Dependence Graph，PDG），使用圖匹配或圖嵌入算法查找相似的代碼［11，21］。但該方法成本較高，不同編程語言使用的轉換工具存在較大差異，且擴展性差。

5）基于度量的代碼克隆檢測方法收集代碼中不同類型的度量值［3，22］。但由于該方法度量值的不同排列產生的代碼語義也不同，因此缺失了大量的代碼語法或語義信息。

1.2 Bi-LSTM 模型

循環神經網絡（Recurrent Neural Network，RNN）用于處理時間序列問題，特點是帶有循環的網絡，能夠有效利用之前的信息。但RNN 的記憶和存儲能力有限，隨著序列間隔的增大，RNN 很難學習到久遠的信息，存在梯度消失和梯度爆炸問題。MNIH［23］等提出并實現了長短時記憶（Long Short-Term Memory，LSTM）網絡，LSTM 中每個模塊有3 個門和1 個記憶單元，解決了長期依賴問題，但LSTM 無法利用序列的下文信息。為解決該問題，研究人員提出Bi-LSTM。Bi-LSTM 由時序相反的2 個LSTM 構成，且連接同一個輸出層，前向LSTM負責記憶上文信息，后向LSTM 負責記憶下文信息，為處理時間序列問題起到了促進作用。

1.3 注意力機制

注意力機制是一種模擬人腦注意力機制的模型，通過計算注意力概率分布對輸入的關鍵部分分配較多的注意力，對其他部分分配較少的注意力，且已在圖像處理［24］、自然語言處理［25］、情感分類［26］等領域中得到廣泛應用。由于基于標記的代碼克隆檢測方法可以較好地描述代碼實現，運行成本低、擴展性好，因此本文選擇基于標記的代碼克隆檢測方法來檢測代碼克隆，并引入基于注意力機制的雙層Bi-LSTM 網絡來挖掘代碼中更多的上下文語義特征。

2 檢測框架

基于分層特征的代碼克隆檢測框架如圖1 所示。代碼克隆檢測過程分為代碼表征、代碼語義提取、檢測分類3 個階段。挖掘代碼對中的代碼語義信息是構建代碼克隆檢測模型的關鍵。為規避不同變量名、函數名的影響，代碼表征階段將代碼中的常量、變量、保留字、運算符等代碼術語統一轉換為標記，建立標記向量化模型，將標記轉換為模型可接受的輸入形式。語義提取階段采取Siamese 結構，建立基于注意力機制的雙層Bi-LSTM 模型提取行級特征和全局代碼特征。代碼克隆對的檢測分類階段將代碼對的語義特征進行拼接作為一個樣本的有效特征，并使用softmax 分類器判斷代碼對的所屬類別，其中，0 表示非克隆對，1 表示克隆對。

圖1 基于分層特征的代碼克隆檢測框架Fig.1 Code clone detection framework based on hierarchical features

3 基于分層特征的代碼克隆檢測

3.1 代碼表征

代碼克隆檢測過程中的代碼表征步驟具體如下：

1）轉換規則。本文采用如下轉換規則將代碼術語統一轉換為標記：（1）數字常量用NUM 替代；（2）字符串用string 替代；（3）保留運算符；（4）保留字；（5）標點符號用PUN 代替。代碼轉換實例如圖2 所示。

圖2 代碼轉換實例Fig.2 Code conversion example

2）標記向量化。本文采用word2vec［27］中實現的skip-gram 模型來創建標記向量化模型。圖3 給出了向量化模型的訓練過程。

圖3 向量化模型的訓練過程Fig.3 Training process of vectorized model

3.2 語義提取

目標代碼由多行語義不同的代碼組成，標記和代碼行的不同排列產生的代碼語義不盡相同。不同于文獻［3］將不同標記類型的出現次數作為克隆檢測的屬性，本文使用雙層Bi-LSTM 直接從標記后的代碼表示中提取能夠體現前后標記關系、上下行關系的深層語義信息。不同詞性的單詞對文本分類有不同的作用［28］，不同標記和不同行對代碼克隆檢測也有不同的作用，因此本文引進注意力機制對重要的標記、行賦予更大的注意力權重，提升代碼克隆檢測效果。圖4 給出了基于分層特征的代碼克隆檢測模型。

圖4 基于分層特征的代碼克隆檢測模型Fig.4 Code clone detection model based hierarchical features

由于不同標記對代碼的語義表示有不同的作用，因此引入注意力機制，提升特定標記對于行代碼的重要程度。通過softmax 激活函數得到歸一化的注意力權重，將注意力權重與隱藏層表示加權求和得到局部行代碼的向量表示，如式（2）～式（4）所示：

其中：wt和bt分別為行級注意力層對應神經元的權值和偏置值；為的隱藏單元；ut為行級上下文向量，用來衡量標記的重要程度，隨機初始化并在訓練過程中與其他參數共同訓練。

2）全局代碼層次。將行級代碼層次中輸出的行向量V(Lim)組成的代碼流作為Bi-LSTM 網絡的輸入得到(V(Li1)，V(Li2)，…，V(Lin))，n表示代碼最大行數。經過Bi-LSTM 網絡輸出行代碼的隱藏狀態him，如式（5）所示：

其中：i=1，m?[1，M]；i=2，m?[1，N]。

在全局代碼層次引入注意力機制來標記對代碼克隆檢測更重要的代碼行。通過softmax 激活函數得到歸一化的注意力權重αim，并與隱藏層輸出him加權求和得到全局代碼的向量表示，如式（6）～式（8）所示：

其中：ws和bs分別為全局注意力層對應神經元的權值和偏置值；uim為him的隱藏單元；us為全局上下文向量，用來衡量行的重要程度，隨機初始化并在訓練過程中與其他參數共同訓練。

3.3 克隆檢測分類

通過代碼對(code1，code2)的向量表示(V( code1)，V( code2))，將兩個向量表示連接作為一個樣本的有效特征，即V(codepair)。例如，V(code1)=(1.230 0，-3.335 0，…，0 .388 7)，V( code2)=( 1.01，0.47，…，2.55)，則V(codepair)=(1.230 0，-3.335 0，…，0.388 7，1.010 0，0.470 0，…，2.550 0)，其中每個分量是構建分類模型需要的特征屬性。最終使用softmax 分類器，得到代碼對的分類結果，如式（9）所示：

其中：w和b分別表示softmax 分類器的權重和偏置。

3.4 模型訓練

訓練采用交叉熵作為優化的損失函數。若y為克隆檢測對應的真實分類結果，為模型分類結果，則損失函數如式（10）所示：

4 實驗與結果分析

爬取GitHub上的Python開源項目，得到7 000 多個Python 源文件的100 多萬行代碼，通過提取注釋和分詞并根據標記轉換規則對源代碼進行處理構建語料庫，利用word2vec 工具訓練語料庫。標記嵌入向量維度為100，行級代碼層次的注意力機制的權重與每行包含的標記數相同，全局代碼層次的注意力機制的權重與目標代碼包含的行數相同。本文采用Bi-LSTM 生成標記表示，輸出表示為100 維，利用tensorflow 框架來訓練基于注意力機制的雙層Bi-LSTM 模型，設置Bi-LSTM 的隱藏層神經元數目為300，batch size 為64，學習率為0.001。本文代碼克隆檢測問題為二分類問題，即代碼對為克隆對或非克隆對，因此采用召回率（Recall）、精確度（Precision）、F1 分數3 個度量指標來評價實驗結果。

4.1 數據集

為訓練和測試基于分層特征的代碼克隆檢測方法，本文采用CCIS［28］中構建的數據集，該數據集包含6 款開源項目中的215 個源碼片段、通過變異生成的275 個克隆片段以及72個噪聲片段，數據集信息如表1所示。數據集包括類型1、類型2、類型3 的代碼克隆對以及非克隆對，通過遍歷統計出各類型數量如表2 所示。

表1 數據集信息Table 1 Dataset information

表2 數據集類型設置Table 2 Type setting in the dataset

4.2 結果分析

4.2.1 注意力機制的有效性分析

本文在Bi-LSTM 中引入注意力機制來賦予標記、行不同的注意力權重，幫助模型更好地進行代碼克隆檢測。以單行代碼為例，“for string in string pun”，其中，“for”作為循環語句的保留字相比標點符號的“pun”對克隆檢測具有更大的權重。圖5 給出了行代碼中每個標記被賦予的注意力權重，可以看出“for”被賦予了更大的權重，而“pun”被賦予的權重較小，說明不同標記對克隆檢測所起的作用不同，而注意力機制能夠提升特定標記對克隆代碼檢測的影響。

圖5 不同標記的注意力權重分布Fig.5 Attention weight distribution of different tokens

以多行代碼對為例，代碼1 中各行代碼具體如下：line1 為“def string pun string pun string=None pun”；line2 為“string=pun pun”；line3 為“string=string pun string pun”；line4 為“for string in string pun”；line5 為“string”；line6 為“return string pun string pun string pun”；line7 為“except string as string”；line8 為“string pun string pun string pun”。代碼2 相比代碼1 在最后一行多出line9 為“raise string pun string pun string=string pun”。在克隆檢測過程中，前8 行作為克隆行應比最后一行非克隆行對檢測效果的影響更大，通過得到各行代碼的注意力權重并將其可視化，結果如圖6 所示，可以看出各行代碼權重不同，但前8 行的權重整體比第9 行大，說明注意力機制賦予重要的行代碼更大的注意力權重，可以提升特定行對克隆代碼檢測的影響。

4.2.2 檢測模型效果對比

將本文模型與雙層Bi-LSTM、基于注意力機制的雙層LSTM（AM-LSTM）、雙層LSTM 在同一數據集上進行實驗對比。為統一比較標準，所有模型的輸入向量均由標記轉換規則和標記向量化模型生成，所有網絡隱藏層節點數均設置為300。4 種模型的檢測結果如表3 所示，可以看出Bi-LSTM 比LSTM 體現出更好的性能，因為Bi-LSTM 考慮了標記間的前后信息和行間的上下文信息，提取的特征更有效，而本文模型相比傳統模型檢測效果更佳，主要原因為本文模型結合注意力機制，提升了關鍵標記對于克隆代碼檢測的影響，并且獲取了更多的上下文代碼語義信息。

表3 4 種模型的檢測結果對比Table 3 Comparison of detection results of four models

4.2.3 檢測方法效果對比

為驗證本文方法的有效性，將其與CCLearner［3］、NICAD［14］、CCIS［28］方法在相同數據集上進行實驗對比，其中，CCLearner 是一種基于標記的克隆檢測方法，NICAD 是一種被廣泛認可的克隆檢測方法，CCIS 是一種基于圖的代碼克隆檢測方法。這3 種方法可以檢測Python 語言中的克隆，且可檢測前3 種克隆類型。本文使用CCIS［28］中構建的數據集來比較3 種方法的效果。4 種檢測方法的精確度對比結果如圖7 所示，可以看出本文方法與NICAD、CCIS、CCLearner 方法對6 種項目的檢測精確度都較高，幾乎都可以達到100%，對于平均精確度而言，本文方法 與CCLearner 相同，CCIS 與NICAD 相 同，本文方法高于CCIS 與NICAD。4 種檢測方法的召回率對比結果如圖8 所示，可以看出根據平均召回率，CCLearner 的代碼克隆檢測召回率相比NICAD 高出7 個百分點，相比CCIS 高出2 個百分點；本文方法的代碼克隆檢測召回率相比CCLearner 高出2 個百分點。

圖7 4 種方法的精確度對比Fig.7 Comparison of precision of four methods

圖8 4 種方法的召回率對比Fig.8 Comparison of recall rate of four methods

上述實驗結果表明，本文提出的標記轉換規則有利于增強代碼克隆的類型，可在一定程度上規避不同變量名和函數名對檢測效果的影響，同時基于分層特征的代碼克隆模型進一步挖掘代碼間隱藏的深層信息，提升了克隆檢測效果。

5 結束語

本文提出一種基于分層特征的代碼克隆檢測方法，將代碼轉換成統一的標記表示，基于Siamese 框架建立分層特征代碼語義提取模型，提取代碼對的行級代碼特征和全局代碼特征，并引入注意力機制提升克隆檢測效果。實驗結果表明，該方法的代碼克隆檢測召回率相比基于標記的代碼克隆檢測方法高出2 個百分點，能更有效地檢測克隆代碼。后續將針對不同編程語言建立不同的語料庫，并利用遷移學習技術設計適用于多編程語言的代碼克隆檢測方法。