陳桌 張麗萍 王歡 張久杰 王春暉

摘要：針對Type3克隆代碼映射方法少且效率低等問題，提出了一種基于改進向量空間模型（VSM）的映射方法。該方法將改進的VSM引入到克隆代碼分析中，從而得到一種可有效映射Type1、Type2以及Type3克隆代碼的克隆群映射方法。首先，將克隆群文檔預處理得到去除無用詞的代碼文檔，同時提取克隆群文檔的文件名、函數名等特征項；其次，提取并構建克隆群詞頻向量空間，利用余弦算法計算出克隆群相似度；然后，通過克隆群相似度和特征項的匹配構建克隆群映射，最終得到克隆群映射結果。對5款開源軟件進行實驗并人工驗證，所提方法能在低時耗的前提下，保證查全率和查準率均不低于96.1%和97.1%。實驗結果表明了所提方法的可行性，為后期軟件演化分析提供數據支撐。

關鍵詞：

克隆代碼；克隆群映射；向量空間模型；特征項；詞頻

中圖分類號： TP311.5 文獻標志碼：A

0引言

在軟件開發(fā)和維護過程中，開發(fā)人員經常采用復制粘貼的方式修改代碼，導致重復的代碼片段出現，即克隆代碼[1]。以前的研究[2]已經表明，一個軟件系統中會有9%～15%的克隆代碼，有時甚至高達50%以上，相同或相似的代碼會增加軟件的維護費用。例如，如果一個bug在代碼片段中被檢測出來，所有和它相似的片段都應該被調查，檢查相同的錯誤，加強或調整這些代碼。所以對系統版本中的克隆進行追蹤非常有意義。

相鄰版本間的克隆群映射是研究克隆代碼演化[3]工作的關鍵步驟，克隆演化研究關注的是一段克隆代碼在軟件多個版本中的變化情況，而克隆群映射是整個演化過程的紐帶。本文提出的克隆群映射方法是根據自然語言領域中計算文章相似度的向量空間模型（Vector Space Model， VSM）改進的。向量空間模型[4]就是把對文本內容的處理簡化為向量空間中的向量運算，并且以空間上的相似度表達文本的相似度，直觀易懂。當文檔被表示為文檔空間的向量，就可以通過計算向量之間的相似性來度量文檔間的相似性。

在克隆代碼方面，改進的向量空間模型的基本思想是把每個版本中的克隆群簡化為以特征項（關鍵詞）的權重為分量的N維向量，結果用十分簡單的向量表示，使得模型具備了可計算性，有效衡量克隆群之間的相似性，并建立版本間的映射。

1相關工作

1.1克隆定義與分類

克隆代碼的定義目前廣受采納的是將具有相似語法及語義特征[5]的代碼段稱為克隆代碼。系統同一版本中的兩段相似代碼片段稱為克隆對。兩個或多個相似代碼片段組成一個克隆群。追蹤從前一版本到當前版本克隆群的變化過程稱為克隆群映射?，F有研究中，克隆主要有以下兩種分類方法[6]：一是相似程度，二是代碼段的粒度。按源代碼文本相似性將克隆分為Type1型至Type4型克?。ǘx見表1），其中Type1至Type3體現了語法上的相似程度，Type4體現了語義上的相似程度。按克隆關系中代碼段的粒度分為文件、塊、函數、類及語句等類型。

1.2克隆映射

克隆映射（Clone mapping）是對軟件版本間的兩個克隆建立映射關系，其映射條件是具有映射關系的兩個克隆具有同源性。如何計算這些相似關系，并找出最大相似的克隆實例對它們建立映射關系，是克隆映射過程需要解決的問題。

目前構建克隆映射的方法主要有7類[6]。

1）先檢測軟件第一個版本中的克隆，然后根據并發(fā)版本系統（Concurrent Version System， CVS）代碼庫中提供的修改日志，計算版本間的變化，最終得到映射關系[7]。由于以第一個版本中的克隆為映射源，因而無法研究在后期版本中引入的克隆。

2）檢測所有版本中的克隆，然后基于文本相似性及位置關系追溯映射[8-9]。此方法適用于多種不同的克隆演化研究，但時間復雜度高，且映射的最小閾值是經驗值，易受克隆中大變化的影響。

3）對所有版本進行克隆檢測，將檢測到的克隆代碼抽象成克隆區(qū)域描述符（Clone Region Descriptor， CRD），然后在不同版本中跟蹤CRD，通過檢測CRD中的文本區(qū)別構建映射關系[10]。此方法映射的建立不受克隆位置信息的影響，易實現克隆的一致修改，但映射誤報率偏高。

4）使用增量的算法將克隆檢測與映射結合在一起[11]。該方法時間復雜度低，適合處理給定版本的軟件，但添加新版本時整個檢測與映射需重新執(zhí)行，空間復雜度高。

5）先映射相鄰版本間的函數，在此基礎上實現克隆映射[12]。該方法減少了運行時間，但易受重載函數與覆蓋的函數影響。

6）利用源代碼的文本和結構信息，將映射問題由高維的代碼空間轉化到低維的主題空間[13]上，通過映射主題來準確地構建相鄰版本克隆群的映射關系，但沒有考慮每個主題詞所占的整體比例。

7）先將克隆群源代碼Token化[14]，得到克隆群的Token序列，然后比較其Token串之間的相似度，并最終得到克隆群的映射關系，但無法準確映射Type3類型的克隆代碼，且演化過程中文件被重命名，可能無法準確追蹤。

1.3向量空間模型

向量空間模型（VSM）是由Salton等[15]于20世紀年代提出的一種文本表示模型，并應用于文本檢索系統。其基本思想就是將文本文檔以關鍵詞向量的形式表示，每個文本文檔可以表示成一個關鍵詞的特征向量，再計算得到關鍵詞的權重向量；最后計算權重向量中間的余弦相似度，并返回結果。

權重向量為：V（d）=（t1，w1（d）；t2，w2（d）；…；tn，wn（d）），其中：V（d）是文檔d的向量表示，ti表示文檔中的特征項，wi（d）表示特征項ti在文檔d中的權值，ti在文檔d中出現的頻率，即wi（d）=ψ（tfi（d））。

計算方法中每一個特征項的權重取決于兩個元素：特征項ti在文檔d中的詞頻（Term Frequency， TF）和在整個文檔集的逆向文件頻率（Inverse Document Frequency， IDF）。信息檢索中最常用到權重計算方法是TFIDF（Term FrequencyInverse Document Frequency）函數，此計算公式為：

ψ=tfi（d）×lb （N/ni）（1）

其中：N表示原文檔的數目，ni表示含有詞條ti的所有文檔的數目。計算公式：

wi（d）=tfi（d） lb （N/ni+0.1）∑ni=1（tfi（d））2×lb2（N/ni+0.1）（2）log的底是多少？是2吧？那么縮寫為lb？其上面的2是上標嗎？請明確。

一方面，在整個文檔集中包含文檔中某一詞的數量越多，則說明其重要程度代表性越低，其重要程度也就越??；另一方面，某一詞在文檔中出現的頻率越高，則說明其重要程度的代表性越強，其重要程度也就越大。一種常見的相似度測量是著名的余弦測量，當文檔向量與查詢向量被表示成向量時，它決定了兩者之間的角度，如式（3）：

Sim（di，dj）=cos θ=[∑nk=1ωk（di）×ωk（dj）]/（∑ni=1ω2k（di））（∑nj=1ω2k（dj））（3）

特征項的權重被確定以后，需要一個排名函數來測量查詢和文檔向量之間的相似度。一個文檔Di和一個查詢Q之間的相似度定義為：

1.4改進向量空間模型

基于TFIDF算法思想，本文將自然語言領域中的向量空間模型應用于代碼克隆領域，提出了一種新的克隆群映射方法。然而現有的向量空間模型并不完全適用于克隆代碼，TFIDF的核心思想為：某一特征項權重的高低依據的是在文檔中出現的頻率，出現頻率越高，并且包含此項的文檔數越少，表示其權重越高，關聯程度更強，但這些僅僅是經驗公式，并不能真實反映出每個特征項的重要程度。這種思想并沒有考慮每一個特征項的整體比例，所以在確定每一個特征項權重時存在缺陷。另外，和形式語言不同，代碼文檔中的詞在整個文檔集中的出現比例并不能反映其重要程度，所以IDF的計算在軟件代碼文檔中并不適用，因此在代碼克隆領域中，須引入其他能表示克隆代碼重要程度的度量值。

基于向量空間模型的思想，利用TF概念以及代碼中的文件名、函數名等特征項，來表征克隆代碼的相似性。一方面，首先通過表示一個詞出現在文檔中的次數，統計詞頻建立詞頻向量，然后對其進行規(guī)范化，最終利用cosine定理得到兩個權重向量的相似度；另一方面，利用文件名以及函數名等特征項來匹配代碼片段的相似性權重。

2基于改進向量空間模型的克隆群映射方法

2.1算法框架

本文使用的是改進的向量空間模型克隆群映射方法，從檢測結果中提取克隆群文檔，再從克隆群文檔中抽取詞頻向量進行相似度計算，并匹配特征項，從而實現對版本間克隆群的映射?？寺∪河成涞牧鞒倘鐖D1所示。

本文映射算法的思路為：首先對軟件的前一版本和后一版本中的每一個克隆群計算詞頻，得到每個克隆群的詞頻字典，然后構建權重向量，得到克隆群相似度。同時提取克隆群中的特征項（文件名、函數名、起始行、結束行、代碼行數），通過特征項匹配得到特征相似度，最終得到克隆群映射結果，實現了從高維度的代碼文檔空間到低維度的向量空間的轉換?？寺∪河成渌惴ㄈ缦滤尽?/p>

有序號的程序——————————Shift+Alt+Y

程序前

輸入：FClones檢測結果。

輸出：克隆群映射結果。

1）

對后一版本Vn+1中的每一個克隆群CGn+1，i

2）

統計CGn+1，i中每個詞的詞頻，存入字典Dn+1，i

3）

提取每個CGn+1，i的特征項，存入特征字典Tn+1，i

4）

對詞頻字典規(guī)范化

5）

對前一版本Vn中的每一個克隆群CGn， j

6）

統計CGn， j中每個詞的詞頻，存入字典Dn， j

7）

提取每個CGn，i的特征項，存入特征字典Tn，i

8）

對詞頻字典規(guī)范化

9）

遍歷比較Dn+1，i和Dn， j之間相似度，存儲到數組cosin[]中

10）

遍歷匹配Tn+1，i和Tn， j，并存儲到數組T[]中

11）

IF cosin[k]>=t && T[k]==True

12）

THEN CGn+1，i映射到CGn， j

13）

即CGn+1，i → CGn， j

14）

ELSE

15）

CGn+1，i → NULL

16）

返回映射結果

程序后

2.2克隆群向量空間

2.2.1克隆群文檔預處理

預處理是克隆群映射的基礎工作。相比自然語言文本信息，形式語言中代碼不僅包括與其功能相關的信息，也包括大量的程序語言信息。與編程相關的信息在其領域內大多是相對獨立的，幾乎不包含代碼以及軟件的功能信息。為保證克隆群映射更加準確，須將源代碼中的編程相關信息進行過濾。

本文使用檢測結果是由本團隊開發(fā)的檢測工具Fclones[16]檢測得到，檢測結果存儲在可擴展標記語言（Extensible Markup Language， XML）文件中，存儲方式如圖2所示。

static void done_state_str （）

{

str_list_destroy （on_list）；

str_list_destroy （off_list）；

str_list_destroy （on_off_list）；

}

2.2.3構建詞頻向量空間并規(guī)范化

經過研究之后發(fā)現，假設版本中克隆群有i個詞頻：D=[D1，D2，…，Di]，每個目標都有相應的關鍵字。不同關鍵字之間的數量級差異可能很大，如果直接用詞頻計算余弦距離，就不能很好地平均反映出每個關鍵字的特性，所以必須對詞頻進行規(guī)范化。

詞頻規(guī)范化的方法如下：

ωi=Di/（∑ni=0Di）（5）

其中：Di是克隆群向量中詞頻的實際值；ωi為規(guī)范化后得到的權重值。

獲得克隆群目標權重向量：

ω=[ω1，ω2，…，ωi]

2.2.4計算向量空間相似度

目前，克隆代碼領域內判斷相似程度的方法主要有基于文本和位置的映射方法?；谖谋镜南嗨贫扔嬎惴椒òǎ鹤铋L公共子序列（Longest common subsequence）、杰卡德距離（Jaccard distance）、編輯距離（Levenshtein distance）等。基于位置的相似度計算方法是位置重疊率（Location overlapping rate）的計算，其原理就是將克隆代碼的起止行號表示為克隆粒度的相對行號，然后依據特定的公式計算其重疊率。

本文使用的相似性計算方式是余弦距離。計算兩個文本相似度時采用的相似度計算公式如下：

CosSimilarity（ωi，ωj）=（∑ni， j=1（ωi*ωj））/∑ni=1ω2i∑nj=1ω2j（6）

其中：ωi*ωj指的是克隆群詞頻向量的內積；CosSimilarity（ωi*ωj）的取值范圍是[0，1]。當克隆群中的克隆片段在演化過程中發(fā)生了變化，CosSimilarity的值小于等于1，本文啟發(fā)式地設置一個閾值，把所有CosSimilarity≥t的克隆群對當作候選的具有映射關系的克隆群對。如果一個克隆群在相鄰版本中有多個克隆群可能與其具有映射關系，則分別計算源代碼的相似性，選取源代碼相似性符合閾值條件的那些克隆群作為具有映射關系的候選克隆群。

2.3克隆群特征項

2.3.1選取克隆群特征項

為了保證克隆群映射的準確度，須匹配克隆群中的函數名等多個特征項，本文選取了文件名、函數名、起始行、結束行以及代碼行數5個特征項來衡量一個克隆群的屬性信息。具體特征項如表3所示。

2.3.2提取特征項

確定克隆群特征項之后，需提取出所需的克隆群特征項，并放入特征項字典中。文件名的屬性字典表示為：File={“文件名”：FileName}，函數名屬性字典表示為：Fun={“函數名i”：FunName[i]}，每一個克隆群可能包含多個函數，所以字典中包含多個函數名，克隆群特征項提取算法如下所示。

有序號的程序——————————Shift+Alt+Y

程序前

輸入：XML文件。

輸出：文件名、開始行、結束行、函數名。

1）

定義函數getFeatures（XMLpath）

2）

ElementTree ← 將XML文件解析為元素樹

3）

root ← 獲取ElementTree的根節(jié)點

4）

遍歷查找根節(jié)點root下節(jié)點為source的所有內容

5）

查找并返回id、clones、sourcecode

6）

遍歷查找根節(jié)點root下節(jié)點為sourcecode的所有內容

7）

查找并返回FunName

程序后

將已提取的特征項字典存儲為XML文件，某克隆群的特征項字典如圖4所示。

3.2評價方法

從源代碼中映射克隆群可以看作一個分類問題，將相鄰版本的克隆群代碼之間進行分類，即分為有映射關系和無映射關系兩類。本文選取分類中的經典評價方法：從查準率（precision）、查全率（recall）以及F值三方面來評估映射方法的效果，定義如下。

1）準確率：

precision=|TP|/（|TP|+|FP|）（8）

2）查全率：

recall=|TP|/（|TP|+|FN|）（9）

3）F值：

F=2*precision*recall/（precision+recall）（10）

其中：TP表示發(fā)現的真映射克隆群個數；FP表示發(fā)現的假映射克隆群個數；FN表示未發(fā)現的真映射克隆群個數。

3.3實驗過程

3.3.1閾值選取實驗

閾值選取的好壞直接影響到克隆群映射的效果，本文選取并驗證閾值設置為0.6，0.65，0.7，0.75，0.8，0.85，0.9和0.95時映射結果的查全率和查準率。設置為不同閾值時查準率和查全率如圖5所示，其中：X軸表示選取的不同閾值t，Y軸表示不同閾值下的查全率和查準率。

從圖5可以看出，當閾值取0.85時克隆群相似度結果的查全率和查準率最高，即相似度在區(qū)間[0.85，1]范圍內并且特征項匹配成功后則認為具有映射關系。

3.3.2克隆群映射實驗

實驗以版本號為時間線，往后追溯映射關系，查找克隆變化。為使得實驗結果更加有效，本文進行了大量的對比實驗并選取了bluefish1.0.5版本和bluefish1.0.6版本進行結果展示，圖6顯示了bluefish1.0.5版本和bluefish1.0.6兩個相鄰版本的克隆群映射結果。

圖6中第1行表示版本的名稱以及所對應的版本號；第一列表示當前版本中的克隆群id號，前一版本bluefish1.0.5中含有32個克隆群，后一版本bluefish1.0.6中含有32個克隆群；第2列的箭頭表示具有映射關系；第3列的數據表示下一版本克隆群中與當前版本具有映射關系的克隆群以及相似度。例如，bluefish1.0.5版本中13號克隆群和bluefish1.0.6版本中13號和15號克隆群具有映射關系，在代碼維護中可能作了一致性的修改。bluefish1.0.5版本中4號克隆群沒有找到與其具有映射關系的克隆群，可能是因為從上一版本到下一版本的演化過程發(fā)生了較大的變化而未達到閾值的范圍，或者被去除。

另外，從圖6中也可以看出，絕大多數具有映射關系的克隆群的相似度為1.0，這說明版本中的克隆群在演化過程中沒有發(fā)生變化，很少一部分的相似度值接近1.0，這說明克隆群中的克隆代碼在演化過程中只是作了一定程度上的微調，即語句的修改和增刪。

3.4實驗結果與分析

本文對5款開源軟件中的471個克隆群進行實驗，這些克隆群為已知映射關系的克隆群，將映射結果和已知數據進行人工比對，找出實驗中的誤檢數和漏檢數。表6展示了目標軟件中的471個克隆群映射結果（誤檢數和漏檢數）。

在進行大量的實驗之后，進行了人工驗證，得到了克隆群映射的查全率和查準率。針對實驗映射結果，本實驗查準率為471/484=0.973，查全率為471/490=0.961。在實驗中查準率相對較高的原因是克隆群特征項匹配時函數名匹配不成功，導致原本具有映射關系的部分克隆群被過濾掉，具體驗證結果見表7。

從表7可以看到，本文提出的映射方法整體查準率以及查準率都能達到96%以上，而且F值也達到了96%以上。說明本文克隆群映射方法能達到預期效果。上述實驗在5款開源軟件的62個版本上進行了對比實驗以及人工驗證，證明本文提出的基于改進的向量空間模型克隆群映射方法有效可行。

經過進一步的分析發(fā)現，影響本文映射方法的有以下3方面原因。

1）克隆檢測工具的選取。

克隆檢測結果是進行克隆映射的基礎數據，克隆檢測工具的性能直接影響克隆群映射的結果，因此，選取準確高效的克隆檢測工具是本文研究的重要前提。

2）映射方法閾值的界定。

本文的映射方法閾值的選取是通過人工驗證得到的，所以在一定程度上會影響映射的準確率。另外，軟件的開發(fā)語言不同，版本間的差異程度也不同，相同的閾值不能很好地表示不同的軟件，可能會影響映射效果。

3）版本開發(fā)方式的差異。

本文分析的是連續(xù)多版本軟件的映射信息，若版本經過較大變動，會導致映射結果超過閾值，從而影響映射準確度，因此選擇穩(wěn)定更新的連續(xù)版本進行克隆群映射效果最佳。

4結語

針對當前Type3克隆代碼映射存在的問題，本文提出了基于改進向量空間模型的克隆群映射方法，通過相鄰版本間克隆群詞頻向量的計算，將映射內容由高維度的代碼空間簡化為向量空間中的向量運算；同時提取克隆群的特征項，匹配計算特征項，進而實現連續(xù)版本間克隆群的映射，實現原型克隆群映射工具，該工具能高效映射Type1、Type2以及Type3克隆代碼。最后對5款開源軟件進行對比實驗，并進行人工驗證，發(fā)現本文提出的克隆群映射方法的查全率和查準率都能達到0.96以上，充分驗證了本文映射方法的有效性。

本文研究工作依然存在一定的缺陷和不足，例如設置閾值參數時是人工進行驗證設置，無法自動根據軟件自動調整。另外匹配規(guī)則仍需改善，比如當函數名發(fā)生變化時可能影響匹配準確度。這些問題將是下一步研究工作中的重點。

參考文獻：

[1]

NGUYEN H A， NGUYEN T T， PHAM N H， et al. Clone management for evolving software [J]. IEEE Transactions on Software Engineering， 2012， 38（5）： 1008-1026.

[2]

ZIBRAN M F， ROY C K. The road to software clone management： a survey [R]. Saskatoon， SK： The University of Saskatchewan， 2012： 1-66.

[3]

ROY C K， ZIBRAN M F， KOSCHKE R. The vision of software clone management： past， present， and future [C]// Proceedings of the 2014 IEEE Conference on Software Maintenance， Reengineering & Reverse Engineering. Piscataway， NJ： IEEE， 2014： 18-33.

[4]

SIDOROV G， GELBUKH A， GóMEZADORNO H， et al. Soft similarity and soft cosine measure： similarity of features in vector space model [J]. Computación Y Sistemas， 2014， 18（3）：491-504.

[5]

BETTENBURG N， SHANG W， IBRAHIM W， et al. An empirical study on inconsistent changes to code clones at release level [J]. Science of Computer Programming， 2009， 77（6）： 85-94.

[6]

史慶慶，孟繁軍，張麗萍，等.克隆代碼技術研究綜述[J].計算機應用研究，2013，30（6）：1617-1623.（SHI Q Q， MENG F J， ZHANG L P， et al. Survey of research on code clone technique [J]. Application Research of Computers， 2013， 30（6）： 1617-1623.）

[7]

THUMMALAPENTA S， CERULO L， AVERSANO L， et al. An empirical study on the maintenance of source code clones [J]. Empirical Software Engineering， 2010， 15（1）： 1-34.

[8]

DUALAEKOKO E， ROBILLARD M P. Tracking code clones in evolving software [C]// Proceedings of the 2007 International Conference on Software Engineering. Washington， DC： IEEE Computer Society， 2007： 158-167.

[9]

CANFORA G， CERULO L， PENTA M D. Identifying changed source code lines from version repositories [C]// Proceedings of the Fourth International Workshop on Mining Software Repositories. Washington， DC： IEEE Computer Society， 2007： 14-14.

[10]

DUALAEKOKO E， ROBILLARD M P. Clone region descriptors： Representing and tracking duplication in source code [J]. ACM Transactions on Software Engineering and Methodology， 2010， 20（1）： 483-496.

[11]

GDE N， KOSCHKE R. Incremental clone detection [C]// Proceedings of the 13th European Conference on Software Maintenance and Reengineering. Piscataway， NJ： IEEE， 2009： 219-228.

[12]

KAMIYA T， KUSUMOTO S， INOUE K. CCFinder： a multilinguistic tokenbased code clone detection system for large scale source code [J]. IEEE Transactions on Software Engineering， 2002， 28（7）： 654-670.

[13]

張瑞霞，張麗萍，王春暉，等.基于主題建模技術的克隆群映射方法[J].計算機工程與設計，2015，36（6）： 1524-1529.（ZHANG R X， ZHANG L P， WANG C H， et al. Clone group mapping method based on topic modeling [J]. Computer Engineering and Design， 2015， 36（6）： 1524-1529.）

[14]

涂穎，張麗萍，劉東升，等.基于軟件多版本演化提取克隆譜系[J].計算機應用，2015，35（4）：1169-1173.（TU Y， ZHANG L P， LIU D S， et al. Clone genealogies extraction base on software evolution over multiple versions [J]. Journal of Computer Applications， 2015， 35（4）： 1169-1173.）

[15]

SALTON G， WONG A， YANG C S. A vector space model for automatic indexing [J]. Communications of the ACM， 1975， 18（11）： 613-620.

[16]

張久杰，王春暉，劉東升，等.基于Token編輯距離檢測克隆代碼[J].計算機應用，2015，35（12）：3536-3543.（ZHANG J J， WANG C H， LIU D S， et al. Code clone detection based on Levenshtein distance of token [J]. Journal of Computer Applications， 2015， 35（12）： 3536-3543.）