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

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

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

內(nèi)蒙古師范大學(xué) 計(jì)算機(jī)與信息工程學(xué)院，呼和浩特 010022

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

1 引言

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

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

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

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

2 相關(guān)研究工作

2.1 克隆代碼

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

現(xiàn)有研究中主要采用兩種方式定義克隆，根據(jù)代碼片段粒度，將克隆代碼分為語句克隆、塊克隆、函數(shù)克隆、類克隆、文件克隆五種類型[3]；根據(jù)文本及功能相似度，將克隆代碼分為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）：除了空格、制表符、回車換行、注釋、標(biāo)識(shí)符、類型外句法結(jié)構(gòu)完全相同的代碼片段；Type-3克隆（CF1與CF4、CF3與CF4）：除了空格、制表符、回車換行、注釋、標(biāo)識(shí)符、類型外句法結(jié)構(gòu)基本相同，但含有少量語句的增加、修改、刪除的代碼片段；Type-4克?。–F1與CF5）：功能相似或相同但句法結(jié)構(gòu)不同的代碼片段[2]。

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

2.2 克隆檢測

克隆檢測是指從源碼中找出克隆代碼，是克隆代碼研究的基礎(chǔ)工作。目前研究學(xué)者已提出多種克隆檢測方法，每種方法都有優(yōu)缺點(diǎn)。

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

2.3 克隆跟蹤及演化模式

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

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

2.4 總結(jié)

通過以上對“克隆檢測”、“克隆跟蹤及演化模式”國內(nèi)外研究的分析，可以發(fā)現(xiàn)：

（1）克隆代碼檢測技術(shù)已經(jīng)非常成熟，并且NiCad是一款非常優(yōu)秀的檢測工具。

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

（3）克隆跟蹤效果不好，相鄰版本克隆映射時(shí)間復(fù)雜度高或準(zhǔn)確率低。

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

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

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

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

圖2 整體工作流程圖

3.1 克隆代碼檢測

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

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

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

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

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

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

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

在克隆群映射的基礎(chǔ)上，結(jié)合版本修改日志實(shí)現(xiàn)克隆片段映射，既不會(huì)丟失克隆跟蹤信息，又減少了無關(guān)克隆片段匹配，大大提高了映射速度。

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

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

算法1位置區(qū)域起始行計(jì)算算法

函數(shù)功能：計(jì)算克隆片段在后期版本中位置區(qū)域的起始行

輸入?yún)?shù)：克隆片段、同文件代碼位置變化列表

輸出參數(shù)：克隆片段在后期版本中位置區(qū)域的起始行

算法2位置區(qū)域結(jié)束行計(jì)算算法

函數(shù)功能：計(jì)算克隆片段在后期版本中位置區(qū)域的結(jié)束行

輸入?yún)?shù)：克隆片段、同文件代碼位置變化列表

輸出參數(shù)：克隆片段在后期版本中位置區(qū)域的結(jié)束行

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

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

3.4 基于克隆片段映射結(jié)果修正克隆群映射

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

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

圖3 傳統(tǒng)克隆群映射結(jié)果與真實(shí)克隆映射對比

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

3.5 分視角識(shí)別克隆演化模式

克隆代碼演化模式可用于研究克隆代碼在相鄰版本迭代過程中演變特點(diǎn)，幫助開發(fā)人員及時(shí)了解克隆代碼動(dòng)態(tài)變化規(guī)律?；谝延醒芯恐醒莼Ｊ阶R(shí)別方法復(fù)雜、演化模式分類不清晰、模式識(shí)別不全面等問題，本研究在相鄰版本克隆映射的基礎(chǔ)上分三種視角進(jìn)行克隆代碼演化模式識(shí)別，并將演化模式以標(biāo)簽的形式標(biāo)記在前期版本克隆群上。三種視角分別是：克隆群視角、克隆片段視角、克隆代碼內(nèi)容視角。

3.5.1 克隆群視角短期演化模式識(shí)別

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

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

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

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

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

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

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

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

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

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

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

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

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

第五步：如果經(jīng)過前四步克隆群CG依然沒被標(biāo)注，那么發(fā)生了復(fù)雜模式，則為克隆群CG添加“復(fù)雜”標(biāo)簽。

3.5.2 克隆片段視角短期演化模式識(shí)別

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

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

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

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

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

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

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

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

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

3.5.3 克隆代碼內(nèi)容視角短期演化模式識(shí)別

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

圖6 克隆代碼內(nèi)容視角短期演化模式

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

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

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

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

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

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

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

4 實(shí)驗(yàn)與分析

4.1 實(shí)驗(yàn)數(shù)據(jù)

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

表2 實(shí)驗(yàn)軟件基本信息

4.2 評價(jià)方法

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

4.3 關(guān)鍵參數(shù)選取

本研究實(shí)現(xiàn)克隆映射，基于“克隆群初步映射-克隆片段精準(zhǔn)映射-克隆群映射結(jié)果修正”策略，因此克隆群初步映射的結(jié)果直接影響最終克隆映射的效果?？寺∪撼醪接成鋾r(shí)，如果Token編輯距離相似度閾值設(shè)置過大，會(huì)丟失部分克隆群映射，導(dǎo)致克隆跟蹤間斷，影響克隆的分析結(jié)果；如果Token編輯距離相似度閾值設(shè)置過小，會(huì)使得克隆群映射候選集合過大，不能達(dá)到提高克隆映射速度的目的。

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

表3 閾值選取實(shí)驗(yàn)軟件信息

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

表4 同克隆群內(nèi)克隆片段之間相似度分布

4.4 同類實(shí)驗(yàn)對比分析

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

表5 相鄰版本克隆映射對比實(shí)驗(yàn)軟件信息

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

表6 相鄰版本克隆映射同類實(shí)驗(yàn)結(jié)果對比

4.5 實(shí)驗(yàn)結(jié)果及分析

本研究在6款開源軟件近8 000個(gè)版本進(jìn)行了克隆代碼跟蹤實(shí)驗(yàn)。下面給出克隆代碼各演化模式的統(tǒng)計(jì)數(shù)據(jù)，并進(jìn)行簡要分析。

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

表7 克隆群視角短期演化模式統(tǒng)計(jì)結(jié)果 %

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

表8 克隆片段視角短期演化模式統(tǒng)計(jì)結(jié)果%

表9是在克隆代碼內(nèi)容視角對克隆演化模式的統(tǒng)計(jì)結(jié)果，可以發(fā)現(xiàn)：（1）超過98%的克隆代碼在版本迭代過程中均未發(fā)生修改。（2）發(fā)生一致變化模式和不一致變化模式的克隆代碼占比均不高于2%，并且一致變化模式的比例略多于不一致變化的比例。

表9 克隆代碼視角短期演化模式統(tǒng)計(jì)結(jié)果%

5 結(jié)語

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

參考文獻(xiàn)：

[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·卡恩，黨映農(nóng)，等.代碼克隆通知以及體系結(jié)構(gòu)改變可視化：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]史慶慶，孟繁軍，張麗萍，等.克隆代碼技術(shù)研究綜述[J].計(jì)算機(jī)應(yīng)用研究，2013，30（6）：1617-1623.

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

[12]曹羽中，金茂忠，劉超.克隆代碼檢測技術(shù)綜述[C]//中國計(jì)算機(jī)學(xué)會(huì)軟件工程專委會(huì)2006年年會(huì)，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]張久杰，翟曄，王春暉，等.基于版本間克隆映射的演化模式識(shí)別及譜系構(gòu)建[J].計(jì)算機(jī)應(yīng)用，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].計(jì)算機(jī)應(yīng)用，2015，35（12）：3536-3543.