基于修改日志克隆代碼跟蹤及演化模式識別

葛廣帥，劉東升，張麗萍，侯 敏，包薩仁娜

GE Guangshuai,LIU Dongsheng,ZHANG Liping,HOU Min,BAO Sarenna

內蒙古師范大學 計算機與信息工程學院，呼和浩特 010022

College of Computer and Information Engineering,Inner Mongolia Normal University,Hohhot 010022,China

1 引言

為了使軟件更具競爭力，在軟件初始版本完成之后，仍然需要新功能擴充、問題修復等后期維護活動。有研究表明[1]，軟件維護約占軟件總勞動成本的80%左右。

軟件的維護成本受多種因素影響，其中一個重要因素就是克隆代碼。在軟件開發維護過程中，開發人員為了提高開發速度、節約時間成本，經常使用“復制-粘貼-修改”操作，導致系統中產生大量的克隆代碼。此外，由于設計模式、相似API等的使用，也會產生克隆代碼。有研究表明[2]，克隆代碼在軟件系統中普遍存在，并且占據了相當大的比例。

克隆代碼在軟件開發維護方面具有雙重影響。一方面，有些克隆代碼是有益的，例如某代碼片段經過測試無任何缺陷，那么復用該代碼片段可以節省開發時間，避免未知風險[3]。另一方面，有些克隆代碼是有害的，例如復用了未經測試的代碼片段，可能使得潛在的缺陷大量繁殖，并且開發人員對一段克隆代碼修改時也必須對相關的克隆代碼進行相應修改，增加了維護成本[4]。

為了更好地進行克隆代碼分析和管理，不僅要檢測出軟件系統中的克隆代碼，還需要了解克隆代碼隨版本迭代的演變情況[2]。研究者們通過分析克隆代碼在版本升級過程中的變化特點，為程序員理解、管理克隆代碼提供幫助。

2 相關研究工作

2.1 克隆代碼

克隆代碼（clone code）[2]是指軟件源碼中的一些代碼片段，它們之間存在著相同或相似的語法或語義特征，這些代碼片段被稱為克隆片段（clone fragment）。兩個相同或相似的克隆片段稱為克隆對（clone pair），所有相同或相似的克隆片段的集合稱為克隆群（clone class）。

現有研究中主要采用兩種方式定義克隆，根據代碼片段粒度，將克隆代碼分為語句克隆、塊克隆、函數克隆、類克隆、文件克隆五種類型[3]；根據文本及功能相似度，將克隆代碼分為Type-1克隆、Type-2克隆、Type-3克隆、Type-4克隆四種類型[3]。

圖1展示了Type-1、Type-2、Type-3、Type-4四種克隆類型的具體樣例。Type-1克?。?CF1與CF2）：除了空格、制表符、回車換行和注釋外完全相同的代碼片段；Type-2克?。–F1與CF3、CF5與CF6）：除了空格、制表符、回車換行、注釋、標識符、類型外句法結構完全相同的代碼片段；Type-3克隆（CF1與CF4、CF3與CF4）：除了空格、制表符、回車換行、注釋、標識符、類型外句法結構基本相同，但含有少量語句的增加、修改、刪除的代碼片段；Type-4克隆（CF1與CF5）：功能相似或相同但句法結構不同的代碼片段[2]。

圖1 四種克隆類型源代碼示例圖

2.2 克隆檢測

克隆檢測是指從源碼中找出克隆代碼，是克隆代碼研究的基礎工作。目前研究學者已提出多種克隆檢測方法，每種方法都有優缺點。

Johnson[5]使用基于文本的方法進行克隆檢測，首先將代碼片段哈希，然后使用增量哈希函數識別具有相同哈希值的代碼片段即為克隆代碼。該方法時空復雜度低，但是只能用來檢測Type-1克隆，對于其他類型克隆查全率較低。Baker[6]使用基于Token的方法進行克隆檢測，首先使用詞法分析工具將代碼片段轉化成Token串，然后使用后綴樹算法計算Token串的相似性得到克隆代碼。該方法能夠有效檢測Type-1、Type-2克隆，但是對于Type-3克隆查全率、查準率都不高。Baxter等人[7]使用基于抽象語法樹的方法進行克隆檢測，首先將源代碼解析成語法樹，然后將子樹哈希到N個桶中，對同一個桶中的子樹比較相似性得到克隆代碼。該方法能有效地處理Type-1、Type-2、Type-3克隆，但時空復雜度太高。Krinke[8]使用基于程序依賴圖的方法進行克隆檢測，首先將程序根據語句之間的數據流和控制關系建立程序依賴圖集合，然后在程序依賴圖中尋找同構子圖，同構子圖所對應的代碼片段即為克隆代碼。該方法能獲得程序的語義信息，可以處理順序被打亂的克隆代碼，但建立程序依賴圖和尋找同構子圖代價太高，很難應用在中大規模軟件。Roy等人[9]基于文本檢測的方法，同時集成了源代碼轉化、敏捷語法分析等技術，開發了一款克隆檢測工具NiCad，該工具能檢測C、Java等主流開發語言的Type-1、Type-2、Type-3克隆代碼，并且具有較高的查全率和查準率，時空復雜度較低。更多關于克隆代碼檢測研究可參見綜述性文獻[10-12]。

2.3 克隆跟蹤及演化模式

克隆檢測結果僅僅提供了克隆代碼的位置及克隆關系，克隆代碼跟蹤可以提供克隆代碼在版本迭代過程中變化的線索，克隆演化模式可以體現克隆代碼的變化特點。利用演化模式研究克隆變化，受到了學者的廣泛關注。

Kim等人[13]首次提出克隆譜系的概念，并利用版本管理工具中的修改日志信息，推算版本間的變化，實現克隆跟蹤，并且定義了六種克隆群演化模式描述相鄰版本克隆代碼變化情況，分別是：無變化、增加、去除、一致變化、不一致變化和位移演化模式。但是他們只對第一版本進行克隆檢測，不能分析后期版本新產生的克隆，并且定義的演化模式不分視角，區分不明確。Saha等人[14]首先進行函數映射，在此基礎上再進行克隆映射，最終實現克隆代碼跟蹤，研究開發了一款克隆譜系提取工具gCad，并將克隆譜系分為活譜系、死亡譜系、句法相似譜系、一致變化譜系四種類型，并且分析了它們所占的比例。但是如果函數重命名或者被移動，將影響克隆跟蹤效果。Bakota[15]使用基于抽象語法樹的克隆檢測工具從每款軟件中提取克隆代碼，然后結合文件名、位置信息等度量實現相鄰版本克隆片段映射，并且研究了四種不同的克隆片段演化模式，包括：消失克隆、發生克隆、移動克隆、遷移克隆。但是大規模軟件中克隆片段數量較多，時間復雜度過大，并且如果演化過程中發生文件重命名或克隆漂移，將導致克隆片段映射失敗。慈萌等人[16]改進克隆區域描述符（CRD）實現相鄰版本克隆映射，然后使用二元關系合成克隆譜系，最終實現在多版本跟蹤克隆。但是如果代碼某些部分被修改，將導致CRD失效，影響克隆跟蹤。G?de等人[17]利用增量算法將克隆檢測和克隆映射相結合實現克隆跟蹤，雖然時間復雜度和空間復雜度都很低，但是不能將后期版本中新產生的克隆群包含進來。Barbour等人[18]以克隆對為單位開展了后期演化模式的研究，根據克隆對分離、合并過程中克隆片段修改情況將后期演化模式分為八種類型，并分析了它們所占的比例。張久杰等人[19]基于主題信息實現相鄰版本克隆映射，并在克隆群生存視角和克隆片段數量視角研究九種短期演化模式，發現超過90%的克隆代碼穩定演化，但該研究使用的是軟件的發布版本，克隆代碼開發過程中的變化被忽略。更多關于克隆演化的研究可以參見綜述性文獻[10，20]。

2.4 總結

通過以上對“克隆檢測”、“克隆跟蹤及演化模式”國內外研究的分析，可以發現：

（1）克隆代碼檢測技術已經非常成熟，并且NiCad是一款非常優秀的檢測工具。

（2）克隆代碼跟蹤不夠細化，大多克隆演化研究都基于發布版本，忽略了開發過程中克隆代碼的變化情況。

（3）克隆跟蹤效果不好，相鄰版本克隆映射時間復雜度高或準確率低。

（4）克隆演化模式區分不明確、不分視角，并且大多研究都基于傳統的演化模式定義或研究部分演化模式。

針對當前研究存在的不足，本研究提出一種基于修改日志克隆代碼跟蹤的方法，實現了更細致的克隆代碼跟蹤，并分視角識別了克隆演化模式。創新點包括：基于版本管理資源庫，將每次提交作為一個小版本，充分考慮每次修改變化；克隆檢測使用NiCad檢測工具檢測每一個小版本，避免丟失對新增克隆群的研究；相鄰版本基于“克隆群初步映射-克隆片段精準映射-克隆群映射修正”策略，快速準確地實現克隆跟蹤；克隆演化模式識別分克隆群、克隆片段、克隆代碼內容三種視角。

3 基于修改日志克隆代碼跟蹤及演化模式識別

本文提出的基于修改日志克隆代碼跟蹤及演化模式識別分為五個步驟：（1）克隆代碼檢測；（2）基于Token編輯距離相似度克隆群映射；（3）基于修改日志克隆片段精準映射；（4）基于克隆片段映射結果修正克隆群映射；（5）分視角克隆演化模式識別。整個方法的工作流程如圖2所示。

圖2 整體工作流程圖

3.1 克隆代碼檢測

克隆代碼檢測是研究克隆的基礎工作，并且克隆檢測結果直接影響后期克隆跟蹤、演化模式識別等研究，所以本研究使用目前較成熟的克隆檢測工具NiCad進行克隆檢測。NiCad檢測工具是由Queen’s University開發的克隆檢測工具，適用于C、java等主流開發語言，能夠檢測Type-1、Type-2、Type-3的克隆代碼，具有較高的查全率和查準率，而且時空復雜度很低。NiCad檢測工具可以設置functions和blocks兩種粒度進行克隆檢測，由于blocks更具一般性，因此本研究將檢測粒度設為blocks，其他設置還有rename為blind，threshold為0.3。

3.2 基于Token編輯距離相似度克隆群映射

克隆群是克隆片段的集合，對于Type1、Type2類型克隆，同一個克隆群內所有克隆片段的Token串完全相同；對于Type3類型克隆，同一克隆群內克隆片段的Token串之間也只是包含少量的增加、刪除或修改。本研究使用任意一個克隆片段的Token串代替其所在的克隆群，將克隆群映射轉化成Token串相似問題。通過計算Token串編輯距離相似度，實現克隆群映射。

首先，將克隆群中一個克隆片段源碼Token化。本研究參考了前期研究中Token化方法[21]，又考慮了克隆代碼類型定義、程序語言特征及源碼完整性，制定Token化規則主要包括：（1）去掉源碼中的空白符、注釋等非代碼部分；（2）關鍵字（除int、float等基本數據類型）替換成其大寫字母，例如if用I替換、For用F替換；（3）所有變量及數據類型用V替換；（4）浮點數、整數等數字使用D替換；（5）保留基本符號，例如{、}、=、（、）。

然后，計算Token串編輯距離相似度。公式（1）描述了計算Token串T1、T2編輯距離相似度的具體方法，其中 Levenshtein(T1,T2)表示 T1、T2的編輯距離，|T1|、|T2|分別表示T1、T2的長度。

相鄰版本的兩個克隆群，計算它們的相似度Token-Similarity，值越大表示它們的相似度越高，它們之間存在映射關系的可能性越高；值越小表示它們的相似度越低，它們之間存在映射關系的可能性越低。本研究根據實驗結果分析設定閾值為0.6，當兩個克隆群的相似度TokenSimilarity大于等于0.6時，將這兩個克隆群建立映射關系，加入到克隆群映射候選集合。

3.3 基于修改日志克隆片段映射

在克隆群映射的基礎上，結合版本修改日志實現克隆片段映射，既不會丟失克隆跟蹤信息，又減少了無關克隆片段匹配，大大提高了映射速度。

版本V(i)經過一次commit，修改了部分代碼，演變成版本V(i+1)，本研究使用正則表達式從修改日志中提取代碼變化情況，作為計算版本V(i)的克隆片段在版本V(i+1)中位置區域的依據。表1是jabref軟件的一次版本提交（commitid：11e4d9c）引起的代碼位置變化情況，例如第一條變化記錄“文件路徑：/src/…/JabRef-Preferences.java、代碼范圍：48～53、對應范圍：48～54、行增加數：1”表示文件/src/…/JabRefPreferences.java的48～53行進行了修改與下一版本的48～54行相對應，有1行的增加。代碼范圍為“0～0”表示該文件是此次提交新增文件，對應范圍為“0～0”表示該文件被刪除。

表1 commit引起的代碼位置變化示例

算法1位置區域起始行計算算法

函數功能：計算克隆片段在后期版本中位置區域的起始行

輸入參數：克隆片段、同文件代碼位置變化列表

輸出參數：克隆片段在后期版本中位置區域的起始行

算法2位置區域結束行計算算法

函數功能：計算克隆片段在后期版本中位置區域的結束行

輸入參數：克隆片段、同文件代碼位置變化列表

輸出參數：克隆片段在后期版本中位置區域的結束行

對于版本V(i)中克隆群CG的一個克隆片段CF，在相鄰后期版本V(i+1)中尋找映射克隆片段的過程如下：首先將版本V(i+1)中與克隆群CG存在映射關系的所有克隆群組成集合mappingCGSet。如果克隆群集合mappingCGSet為空，代表克隆群CG在下一版本消失，克隆片段CF在版本V(i+1)中自然不存在映射對象，結束程序。如果克隆群集合mappingCGSet不為空，那么使用修改日志信息計算克隆片段CF在版本V(i+1)中的位置區域，如算法1和算法2所示分別計算得到起始行和結束行。然后將mappingCGSet中所有克隆群包含的克隆片段匯集成候選克隆片段集合candidateCFSet。最后計算candidateCFSet中與CF同文件路徑的克隆代碼位置和CF在版本V(i+1)中位置區域的位置重疊率，找出最優匹配的映射克隆片段。當位置重疊率相同時，與CF的代碼編輯距離最小的勝出。位置重疊率計算如公式（2）所示，其中candCF.s、candCF.e分別表示候選克隆片段的起始行、結束行，CF.mbs、CF.mbe分別表示CF在版本V(i+1)的位置區域的起始行、結束行。

本研究使用算法1和算法2根據版本修改日志計算克隆片段CF在下一版本位置區域時，將位置區域的范圍盡可能小地擴大，例如，假設一個克隆片段文件路徑為/src/…/TablePrefsTab.java，起始行為20，結束行為35，由于20大于19且小于25，那么起始行的可能位置為20+8=28；由于35大于等于25且小于等于36，那么結束行的可能位置為55，最終根據Argorithm 1得到該克隆片段在后期版本的位置區域是[28行，55行]。如果克隆片段CF在版本V(i+1)中沒有邊緣擴展，那么由CF演變而來的克隆片段必定在計算的可能位置之內，使用公式（2）可以算得位置重疊率為1.0。并且本研究所采用的方法對于克隆片段并沒有修改，但因其上下文代碼修改發生位置偏移的現象，仍然可以以重疊率為1.0的相似度找到其演化克隆片段。經過千余版本實驗，人工驗證并未發現一例克隆片段邊緣擴展，因此本研究不考慮克隆片段邊緣擴展現象，將位置重疊率閾值設為1.0，當最優匹配克隆片段位置重疊率等于1.0時，才建立克隆片段映射。

3.4 基于克隆片段映射結果修正克隆群映射

相鄰版本克隆映射的準確性直接決定克隆跟蹤的效果，也是克隆演化模式識別的基礎。相鄰版本克隆映射包括克隆群映射和克隆片段映射。傳統的相鄰版本克隆映射都是先進行克隆群映射，再進行克隆片段映射，而克隆群映射有兩種方法：第一種，相鄰版本克隆群兩兩計算相似度，結果在閾值范圍之內就建立克隆群映射；第二種，相鄰版本中前期版本的克隆群在后期找一個最相似的克隆群建立映射，其他克隆群不再考慮。但是傳統的克隆群映射方法都存在弊端，使得最終得到的克隆映射結果不理想。第一種方法對于克隆群發生分離，后期獨立演化的情況，由于分離出的克隆群也極其相似，可能會出現多余克隆群映射，即雖然從克隆群角度分析極其相似，但兩個克隆群包含的克隆片段卻不存在映射關系；第二種方法對于克隆群分離的情況不能處理，即前后版本克隆群真實映射出現1∶n(n＞1)的情況，此方法只能將前期版本克隆群與后期版本一個克隆群建立映射關系，丟失映射信息。

圖3展示了傳統克隆群映射結果與真實克隆映射的對比，由于克隆群B、C、D、E均來源于克隆群A，四個克隆群非常相似，在版本V(i+1)與版本V(i+2)進行克隆群映射時，按照傳統克隆群映射方法一，會出現克隆群B與克隆群E、克隆群C與克隆群D的錯誤映射；從版本V(i)演化到版本V(i+1)過程中克隆群A分離成兩個克隆群B和C，按照傳統克隆群映射方法二，在版本V(i+1)中只選擇最相似的克隆群B與克隆群A建立映射，漏掉克隆群A與克隆群C的映射。

圖3 傳統克隆群映射結果與真實克隆映射對比

鑒于克隆群粒度太大，本研究以克隆片段映射為基準，根據版本修改日志進行克隆片段精確映射?？紤]到軟件中克隆片段數量太多，首先采用傳統克隆群映射方法一構造克隆群映射候選集合，在此基礎上進行細致克隆片段映射，最終根據克隆片段映射結果修正克隆群映射，即檢查有映射關系的克隆群包含的克隆片段是否存在映射，如果映射的克隆群包含的克隆片段沒有任何關系，將取消克隆群的映射。

3.5 分視角識別克隆演化模式

克隆代碼演化模式可用于研究克隆代碼在相鄰版本迭代過程中演變特點，幫助開發人員及時了解克隆代碼動態變化規律?；谝延醒芯恐醒莼Ｊ阶R別方法復雜、演化模式分類不清晰、模式識別不全面等問題，本研究在相鄰版本克隆映射的基礎上分三種視角進行克隆代碼演化模式識別，并將演化模式以標簽的形式標記在前期版本克隆群上。三種視角分別是：克隆群視角、克隆片段視角、克隆代碼內容視角。

3.5.1 克隆群視角短期演化模式識別

根據相鄰版本具有映射關系克隆群數量比例及交叉程度，從克隆群角度識別克隆演化模式，可以分為六種演化模式（如圖4所示）。

圖4 克隆群視角短期演化模式

新生演化模式：版本V(i)與版本V(i+1)之間具有映射關系的克隆群數量之比為0∶1，即版本V(i+1)中有新克隆群產生。

死亡演化模式：版本V(i)與版本V(i+1)之間具有映射關系的克隆群數量之比為1∶0，即版本V(i+1)中有克隆群消失。

成長演化模式：版本V(i)與版本V(i+1)之間具有映射關系的克隆群數量之比為1∶1。

分離演化模式：版本V(i)與版本V(i+1)之間具有映射關系的克隆群數量之比為1∶n(n＞1)。

合并演化模式：版本V(i)與版本V(i+1)之間具有映射關系的克隆群數量之比m∶1(m＞1)。

復雜演化模式：版本V(i)與版本V(i+1)之間具有映射關系的克隆群數量之比m∶n(m＞1且n＞1)。

為了方便演化模式存儲，將演化模式以標簽的形式標注在前期版本克隆群上，且新生模式是一個克隆群從無到有，并不包含其修改變化信息，本研究不予考慮，只標注死亡、成長、分離、合并、復雜五種演化模式。對版本V(i)中的克隆群CG從克隆群角度識別短期演化模式，添加群標簽步驟如下：

第一步：如果克隆群CG無后繼，即版本V(i)迭代到版本V(i+1)過程中由于修改或刪除使得克隆群CG不再存在，發生了死亡模式，則為克隆群CG添加“死亡”標簽。

第二步：如果克隆群CG只有一個后繼，并且該后繼克隆群只有一個前驅（肯定是克隆群CG），那么發生成長模式，則為克隆群CG添加“成長”標簽。

第三步：如果克隆群CG存在多個后繼，但是所有的后繼克隆群都只有一個前驅（肯定是克隆群CG），那么發生分離模式，則為克隆群CG添加“分離”標簽。

第四步：如果克隆群CG只有一個后繼，并且該后繼克隆群有多個前驅（即除了克隆群CG還有其他克隆群），但是所有前驅克隆群都只有一個后繼（肯定是克隆群CG的后繼），那么發生合并模式，則為克隆群CG添加“合并”標簽。

第五步：如果經過前四步克隆群CG依然沒被標注，那么發生了復雜模式，則為克隆群CG添加“復雜”標簽。

3.5.2 克隆片段視角短期演化模式識別

根據相鄰版本迭代過程中克隆片段延續性，從克隆片段角度識別短期演化模式，可以分為三種演化模式（如圖5所示）。

圖5 克隆片段視角短期演化模式

去除演化模式：版本V(i)到版本V(i+1)的過程中，版本V(i)的克隆群中包含無后繼的克隆片段。

新增演化模式：版本V(i)到版本V(i+1)的過程中，版本V(i+1)的克隆群中包含無前驅的克隆片段。

保持演化模式：版本V(i)到版本V(i+1)的過程中，版本V(i)的克隆群包含的所有克隆片段都有后繼，版本V(i+1)的克隆群包含的所有克隆片段都有前驅。

克隆片段視角分析克隆演化模式，實際就是將克隆片段演化規律標注在其所在的克隆群上。因此片段標簽與群標簽不同，一個克隆群上可能同時出現兩個片段標簽，例如，一個克隆群在演化過程中刪除了一個克隆片段同時在其他地方又新增一個克隆片段，這種情況更應該值得關注。對版本V(i)中的克隆群CG從克隆片段角度識別短期演化模式，添加片段標簽步驟如下：

第一步：如果克隆群CG包含的克隆片段存在一個無后繼的，即版本V(i)迭代到版本V(i+1)過程中一個克隆片段從克隆群CG中消失。那么發生了去除模式，為克隆群CG添加“去除”標簽。

第二步：如果版本V(i+1)中與克隆群CG有映射關系的克隆群包含無前驅的克隆片段，那么該克隆片段為新增的，發生了新增模式，為克隆群CG添加“新增”標簽。

第三步：如果經過前兩步克隆群CG沒有被標注“去除”、“新增”標簽，那么它包含的所有克隆片段都被完好地保持了下來，為克隆群CG添加“保持”模式。

3.5.3 克隆代碼內容視角短期演化模式識別

根據克隆代碼修改影響，從克隆代碼內容角度識別短期演化模式，可以分為三種演化模式（如圖6所示）。

圖6 克隆代碼內容視角短期演化模式

無變化演化模式：版本V(i)到版本V(i+1)的過程中，克隆群中包含的克隆片段均無變化。

一致變化演化模式：版本V(i)到版本V(i+1)的過程中，克隆群中包含的克隆片段有變化，但所有克隆片段仍在一個克隆群中。

不一致變化演化模式：版本V(i)到版本V(i+1)的過程中，克隆群中包含的克隆片段有變化，克隆片段不完全在同一個克隆群中。

克隆代碼內容視角分析克隆演化模式，主要考察克隆群包含的克隆片段是否被修改，被修改之后引起什么影響，同在一個克隆群的克隆代碼經過修改之后是否還在同一克隆群中。對版本V(i)中的克隆群CG從克隆代碼內容角度識別短期演化模式，添加內容標簽步驟如下：

第一步：如果克隆群CG包含的所有克隆片段均未被修改，那么為克隆群CG添加“無變化”標簽。

第二步：如果克隆群CG包含的克隆片段有修改，但是在版本V(i+1)中依舊保持在同一個克隆群中，那么為克隆群CG添加“一致變化”標簽。

第三步：如果克隆群CG包含的克隆片段有修改，并且克隆群CG包含的克隆片段在后期版本V(i+1)中不再屬于同一個克隆群，那么為克隆群CG添加“不一致變化”標簽。

4 實驗與分析

4.1 實驗數據

本研究選取的6款開源軟件分別是jabref、make、nginx、ant、freecol、argouml，這些軟件的基本信息見表2所示。

表2 實驗軟件基本信息

4.2 評價方法

為了驗證本研究中關鍵參數選取及克隆映射同類實驗對比的有效性，采用人工驗證的方法從查準率、查全率、F 值三方面進行衡量。如公式（3）、（4）、（5）所示，其中TT表示識別的正確映射的數量，(TT+TF)表示識別的所有映射的數量，(TT+FT)表示實際存在的映射的數量。precision表示查準率，recall表示查全率，F-Measure表示F值。

4.3 關鍵參數選取

本研究實現克隆映射，基于“克隆群初步映射-克隆片段精準映射-克隆群映射結果修正”策略，因此克隆群初步映射的結果直接影響最終克隆映射的效果。克隆群初步映射時，如果Token編輯距離相似度閾值設置過大，會丟失部分克隆群映射，導致克隆跟蹤間斷，影響克隆的分析結果；如果Token編輯距離相似度閾值設置過小，會使得克隆群映射候選集合過大，不能達到提高克隆映射速度的目的。

通過對表3中四款軟件開展相鄰版本克隆群映射實驗，得到如圖7所示選取不同的Token編輯距離相似度閾值時克隆群映射查準率、查全率的變化情況，分析發現：（1）Token編輯距離相似度閾值在0.4到0.7的變化過程中克隆群映射查準率有顯著提升；（2）克隆群映射查全率幾乎全為1.0，Token編輯距離相似度閾值變化對其影響不大?？紤]到研究版本的細化程度，相鄰版本間克隆代碼變化可能很小，而選取的代表克隆群的克隆片段可能是同一個并且幾乎未發生變化，因此出現Token編輯距離相似度閾值變化而克隆群映射查全率始終為1.0的現象。但是在版本演化過程中，可能出現克隆片段被刪除，代表克隆群的克隆片段換成了其他克隆片段等情況?；诖?，本研究統計每個版本中同一個克隆群所包含的克隆片段之間的最低Token編輯距離相似度，得到同克隆群內克隆片段之間最低Token編輯距離相似度分布如表4所示。通過對表4分析，可以發現：（1）同克隆群內Token編輯距離相似度最低值全部大于等于0.6；（2）同克隆群內Token編輯距離相似度最低值大于等于0.7的超過85%。綜合考慮圖7和表4的統計數據，在保證克隆群映射查全率為1.0的情況下，盡可能減小克隆群映射候選集合，整體提升相鄰版本克隆映射速度，將Token編輯距離相似度閾值設置為0.6。

表3 閾值選取實驗軟件信息

圖7 克隆群映射查準率、查全率隨Token編輯距離相似度閾值變化情況

表4 同克隆群內克隆片段之間相似度分布

4.4 同類實驗對比分析

目前已有不少克隆跟蹤工具被開發，其中Saha等人開發的克隆譜系提取工具gCad影響力最大。鑒于本研究與gCad識別的演化模式不完全一致，僅對克隆映射做對比實驗。其中檢測階段都使用NiCad且參數設置相同，實驗平臺同為操作系統Ubuntu14.04 64位，內存4 GB，CPU 2核。選取的實驗軟件分別是ant、freecol、openssh，版本信息如表5所示。

表5 相鄰版本克隆映射對比實驗軟件信息

通過對比實驗，配合人工驗證，結果如表6所示。從映射結果分析，ant軟件相鄰版本克隆映射，OurTool和gCad的查全率都是100%，但是由于克隆檢測結果中存在兩個克隆群非常相似，導致gCad的結果中存在錯誤映射，查準率降低，而OurTool基于修改日志信息，避免了錯誤映射。freecol軟件相鄰版本克隆映射，OurTool依然完美地完成映射，而gCad的結果中出現了錯亂映射，導致查全率、查準率都有所降低。openssh軟件選取的相鄰版本克隆檢測結果一致，對比克隆檢測結果和修改日志發現克隆代碼并沒有發生任何修改，OurTool和gCad都非常好地完成了相鄰版本克隆映射。從時間分析，在三款軟件上，OurTool的速度都要快于gCad，而且克隆群數量越多，效果越明顯。綜上OurTool的查全率、查準率、F值明顯高于gCad，而且運行時間也較短。

表6 相鄰版本克隆映射同類實驗結果對比

4.5 實驗結果及分析

本研究在6款開源軟件近8 000個版本進行了克隆代碼跟蹤實驗。下面給出克隆代碼各演化模式的統計數據，并進行簡要分析。

表7是在克隆群視角對克隆演化模式的統計結果，可以發現：（1）克隆代碼在相鄰版本間幾乎都是以成長模式演化的（比重均超過98%）。（2）死亡模式所占的比重均小于2%，發生死亡模式的這些克隆代碼在軟件開發過程中可能被刪除或者大幅度修改，導致不再具備克隆關系。（3）分離模式、合并模式、復雜模式所占的比例小于等于0.01%，甚至有的演化模式在開發過程中并不出現，雖然這些演化模式發生得很少，但由于其不“規矩”，可能與Bugs有關，更應該值得關注。

表7 克隆群視角短期演化模式統計結果 %

表8是在克隆片段視角對克隆演化模式的統計結果，去除模式指僅發生了去除，新增模式指僅發生了新增，不包含去除新增同時發生時的數據。分析表8中數據可以發現：（1）保持模式占的比例均超過97%。（2）去除模式、新增模式、去除&新增模式的比例都不高，并且去除模式遠遠多于其他兩種，去除新增同時發生的情況也比僅新增模式略多。說明克隆片段在版本迭代過程中也幾乎都被保留了下來，并且克隆代碼被再次重用得并不多，反而在演化過程中被修改失去克隆關系的占一定比例。

表8 克隆片段視角短期演化模式統計結果%

表9是在克隆代碼內容視角對克隆演化模式的統計結果，可以發現：（1）超過98%的克隆代碼在版本迭代過程中均未發生修改。（2）發生一致變化模式和不一致變化模式的克隆代碼占比均不高于2%，并且一致變化模式的比例略多于不一致變化的比例。

表9 克隆代碼視角短期演化模式統計結果%

5 結語

本研究提出一種基于修改日志克隆代碼跟蹤方法，并分視角識別克隆演化模式，分析了各模式所占比例。發現超過97%的克隆穩定演化，分離演化模式、合并演化模式、復雜演化模式均不超過0.01%，一致變化演化模式、不一致變化演化模式均不超過2%。并且在多款軟件上與領域內較優秀的同類工具gCad做對比實驗，結果查全率（提高了2%）、查準率（提高了2%）明顯高于gCad，而且同環境下速度比gCad快。本文的研究內容與實驗仍然存在一些不足之處，例如演化模式以克隆群為粒度太粗。本文在后續研究中陸續改進、完善不足之處，以克隆對為粒度分析克隆演化。

參考文獻：

[1]Alkhatib G.The maintenance problem of application software：An empirical analysis[J].Journal of Software Maintenance Research&Practice，1992，4（2）：83-104.

[2]Zibran M F，Saha R K，Asaduzzaman M，et al.Analyzing and forecasting near-miss clones in evolving software：An empirical study[C]//IEEE International Conference on Engineering of Complex Computer Systems，2011：295-304.

[3]Roy C K.Detection and analysis of near-miss software clones[C]//IEEE International Conference on Software Maintenance，2009：447-450.

[4]D·張，S·卡恩，黨映農，等.代碼克隆通知以及體系結構改變可視化：CN，CN 102681835 A[P].2012.

[5]Johnson J H.Identifying redundancy in source code using fingerprints[C]//Conference of the Centre for Advanced Studies on Collaborative Research，Toronto，Ontario，Canada，1993：171-183.

[6]Baker B S.On finding duplication and near-duplication in large software systems[C]//Proceedings of 2nd Working Conference on Reverse Engineering，1995：86-95.

[7]Baxter I D，Yahin A，Moura L，et al.Clone detection using abstract syntax trees[C]//International Conference on Software Maintenance，1998：368-377.

[8]Krinke J.Identifying similar code with program dependence graphs[C]//Eighth Working Conference on Reverse Engineering，2001：301-309.

[9]Cordy J R，Roy C K.The NiCad clone detector[C]//The IEEE International Conference on Program Comprehension，ICPC 2011，2011：219-220.

[10]史慶慶，孟繁軍，張麗萍，等.克隆代碼技術研究綜述[J].計算機應用研究，2013，30（6）：1617-1623.

[11]Koschke R.Survey of research on software clones[C]//Proc Duplication Redundancy&Similarity in Software，2006.

[12]曹羽中，金茂忠，劉超.克隆代碼檢測技術綜述[C]//中國計算機學會軟件工程專委會2006年年會，2006.

[13]Kim M，Sazawal V，Notkin D，et al.An empirical study of code clone genealogies[J].Acm Sigsoft Software Engineering Notes，2005，30（5）：187-196.

[14]Saha R K，Roy C K，Schneider K A.gCad：A near-miss clone genealogy extractor to support clone evolution analysis[C]//IEEE International Conference on Software Maintenance，2013：488-491.

[15]Bakota T.Tracking the evolution of code clones[C]//Sofsem 2011：Theory and Practice of Computer Science，Conference on Current Trends in Theory and Practice of Computer Science，Novy Smokovec，Slovakia，January 22-28，2011：86-98.

[16]Meng C，Su X H，Wang T T，et al.A new clone group mapping algorithm for extracting clone genealogy on multi-version software[C]//Third International Conference on Instrumentation，Measurement，Computer，Communication and Control，2013：848-853.

[17]G?de N，Koschke R.Studying clone evolution using incremental clone detection[J].Journal of Software Evolution&Process，2013，25（2）：165-192.

[18]Barbour L，Khomh F，Zou Y.Late propagation in software clones[C]//IEEE International Conference on Software Maintenance，2011：273-282.

[19]張久杰，翟曄，王春暉，等.基于版本間克隆映射的演化模式識別及譜系構建[J].計算機應用，2016，36（7）：2021-2030.

[20]Pate J R，Tairas R，Kraft N A.Clone evolution：A systematic review[J].Journal of Software Maintenance&Evolution Research&Practice，2013，25（3）：261-283.

[21]張久杰，王春暉，張麗萍，等.基于Token編輯距離檢測克隆代碼[J].計算機應用，2015，35（12）：3536-3543.