侯 敏，張麗萍

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

0 引 言

在軟件開發(fā)和維護(hù)過程中復(fù)制代碼片段是常見的操作，這種重復(fù)使用的代碼被稱為克隆代碼(clone code)，其與軟件工程領(lǐng)域中各種問題密切相關(guān)，如：軟件質(zhì)量、演化、復(fù)雜性、架構(gòu)、復(fù)用，以及軟件授權(quán)、反剽竊等[1]。

研究人員發(fā)現(xiàn)克隆代碼可能會影響軟件系統(tǒng)的質(zhì)量，特別是對軟件的維護(hù)和閱讀理解[2]，也可能導(dǎo)致引入潛在Bug。因此大多數(shù)時候克隆被認(rèn)為對軟件的演化有負(fù)面影響，是一種壞氣味[3]。

檢測大型軟件系統(tǒng)的克隆代碼并進(jìn)行相應(yīng)的維護(hù)是非常重要的。大量的克隆代碼不僅增加了系統(tǒng)的規(guī)模且會降低軟件代碼質(zhì)量，如遺漏的繼承或缺失的程序抽象?，F(xiàn)有技術(shù)可以自動找到這些克隆代碼[4-5]，然后通過源代碼重構(gòu)等操作修改或刪除有害的克隆代碼。近年來，克隆代碼檢測的相關(guān)研究成為代碼分析領(lǐng)域中一個十分活躍的分支[4]。

文中對相關(guān)的克隆檢測技術(shù)進(jìn)行了總結(jié)，首先描述了文獻(xiàn)中常用的克隆術(shù)語，以及常用克隆類型；其次分析了現(xiàn)有的克隆檢測框架、檢測方法、檢測工具，并對不同檢測技術(shù)進(jìn)行了比較；然后指出了克隆檢測技術(shù)在軟件工程其他領(lǐng)域中的應(yīng)用。

1 相關(guān)概念

1.1 克 隆

克隆片段(clone fragment)：源代碼中一段連續(xù)的代碼序列(有或者無注釋)，可能是一個函數(shù)、方法或者代碼塊。兩個克隆片段之間的相似程度達(dá)到某一設(shè)定的閾值就構(gòu)成了克隆關(guān)系(clone relationship)。兩個具有克隆關(guān)系的片段組成一個克隆對(clone pair)，多個具有克隆關(guān)系的片段則形成了一個克隆群(clone group)，即克隆類(clone class)。在研究軟件中的克隆時，會按照不同的克隆粒度進(jìn)行分析，研究粒度[6-8]通常可分為文件、類、函數(shù)、語句和塊等。

1.2 克隆類型

盡管研究者將克隆代碼稱為相同或者相似的代碼，但并沒有給出明確的定義?，F(xiàn)有研究[6]根據(jù)代碼片段之間文本和功能的差異將克隆分為了Type-1、Type-2、Type-3以及Type-4，四種克隆類型的描述如表1所示。

表1 克隆類型描述

2 克隆檢測過程

一般來說，克隆檢測通常會遵循一定的步驟和階段(有些階段并不是必須的)，具體檢測過程如圖1所示。不同的檢測方法會側(cè)重其中某幾個階段。

圖1 克隆檢測過程

(1)預(yù)處理階段：在這個階段的克隆檢測過程包括三部分：①去除無關(guān)項(xiàng)：統(tǒng)一源代碼布局和去除檢測無關(guān)的字符串(如空白符、注釋)，為的是減少比較和計(jì)算次數(shù)從而降低無關(guān)項(xiàng)對檢測結(jié)果的影響；②確定源單元：剩余的源代碼分成一組不相交的片段稱為源單元，這些單元都參與了直接克隆關(guān)系的相互關(guān)系；③確定比較單元：根據(jù)所使用的源單元的比較算法，可能需要進(jìn)一步劃分成更小的單元。

(2)轉(zhuǎn)換階段：這一階段除了基于文本的方法都會用到，將源代碼的變量、標(biāo)識符轉(zhuǎn)換成一個相應(yīng)的中間表示形式進(jìn)行比較。①提取Tokens串：通過詞法分析器將源代碼進(jìn)行Token化，每行源代碼轉(zhuǎn)化為一組Token序列；②提取抽象語法樹(abstract syntax tree，AST)：將源代碼轉(zhuǎn)換為一組抽象語法樹，通過比較子樹獲取檢測結(jié)果；③程序依賴圖(program dependency graph，PDG)：一個程序依賴圖表示控制和數(shù)據(jù)圖，每個節(jié)點(diǎn)表示程序的語句和條件，通過語義技術(shù)從源代碼生成子圖進(jìn)行比較。

(3)檢測匹配階段：源代碼預(yù)處理和轉(zhuǎn)換之后的結(jié)果作為此階段的輸入，并根據(jù)相應(yīng)的算法對源單元和比較單元進(jìn)行計(jì)算，之后將相鄰的小的單元合并成大的單元。匹配檢測的輸出是表示或聚集的轉(zhuǎn)化代碼中的匹配列表，形成一組候選克隆對。每個克隆對通常表示為變換后的代碼中每一個對應(yīng)相匹配的片段源坐標(biāo)。常見的匹配算法有動態(tài)模式匹配(dynamic pattern matching，DPM)[9]、最長公共子序列(longest common subsequence，LCS)[10]、后綴數(shù)組(suffix-trees)[11]等等。

(4)格式化階段：在這個階段中，將在上一階段通過比較算法所獲得的克隆對列表轉(zhuǎn)換成與原始源代碼相對應(yīng)的新克隆對列表。本階段實(shí)現(xiàn)的是從上一階段獲得的克隆結(jié)果與原始結(jié)果的映射，得到新克隆對和克隆類的位置之后，將其轉(zhuǎn)換成原始源文件上對應(yīng)的位置。

(5)后處理階段(過濾)。

此階段并不是所有克隆檢測工具必須的，通過使用手動分析[6]或自動啟發(fā)式的方式過濾或排名檢測出的克隆代碼，篩選出誤報(bào)或漏報(bào)的克隆。自動啟發(fā)式過濾根據(jù)多樣性、頻率、長度或克隆的其他特性自動排列和過濾候選克隆。此外，為了減少數(shù)據(jù)量，克隆對應(yīng)該被聚集成克隆類、克隆群或者集合。

(6)檢測結(jié)果可視化階段。

為了能夠讓研究人員更加直觀清晰地看到軟件系統(tǒng)中的克隆代碼，需要一種易于理解的方式對檢測結(jié)果進(jìn)行存儲和可視化。較為常用的存儲方式有超文本標(biāo)記語言(hypertext markup language，HTML)和可擴(kuò)展標(biāo)記語言(extensible markup language，XML)，它們都有相對應(yīng)的節(jié)點(diǎn)，可以清晰地表示克隆之間的鏈接關(guān)系和包含關(guān)系。此外還通過一些餅圖、散點(diǎn)圖、折線圖以及柱狀圖展示克隆片段的分布和數(shù)量。

3 克隆代碼檢測方法及工具

現(xiàn)有研究中存在較多不同的克隆檢測方法，這些技術(shù)都能夠找到軟件系統(tǒng)中的克隆代碼，絕大多數(shù)的克隆檢測技術(shù)被分為五種類型。這一部分主要闡述每一類克隆檢測技術(shù)的詳細(xì)細(xì)節(jié)。

3.1 基于文本的克隆檢測方法

基于文本的克隆檢測技術(shù)[12]將軟件系統(tǒng)中的源代碼看作字符序列，并去除源代碼中的注釋、空白符和新增行等無用部分，然后比較代碼中每個字符序列相似度并返回字符串匹配結(jié)果集。

研究者們研究和開發(fā)出了各種基于文本的克隆檢測工具。Baker[13]使用基于代碼行的字符匹配算法開發(fā)出了克隆檢測工具—Dup，但此工具不能檢測不同風(fēng)格的程序代碼。Cordy等[14]使用基于文本的方法檢測HTML網(wǎng)頁中的近似克隆，但它無法標(biāo)準(zhǔn)化所有的代碼，且使用的也是最小的比較單元?；谧址膭討B(tài)模式匹配算法由Ducasse等[15]提出，該算法可以獨(dú)立于程序設(shè)計(jì)語言使用，由于代碼的內(nèi)聚性，這種技術(shù)不能以獨(dú)立于程序設(shè)計(jì)語言的方式確定有意義的克隆代碼。此后，Roy等[16]開發(fā)的 NICAD應(yīng)用靈活的過濾和規(guī)范化機(jī)制對文本檢測進(jìn)行改進(jìn)，可有效檢測Type-1、Type-2以及Type-3克隆。

3.2 基于Token的克隆檢測方法

與基于文本的檢測方法類似，此方法在檢測之前先基于Token的轉(zhuǎn)換工具進(jìn)行解析，將源代碼轉(zhuǎn)化成一種中間表示形式—Token序列，基于Token的檢測工具會規(guī)定每個克隆片段的最小Token長度。在檢測過程中，利用匹配規(guī)則比較Token序列以便定位。

Kamiya等[17]開發(fā)了一款名為CCFinder的克隆檢測工具。該工具將源代碼中每一行單獨(dú)轉(zhuǎn)化為Token序列，然后合并所有的Token序列，這樣做是因?yàn)榧词棺兞棵痛a結(jié)構(gòu)發(fā)生變化也不會影響檢測結(jié)果。Baker[18]也使用Token方法檢測克隆，但沒有使用任何轉(zhuǎn)化技術(shù)，導(dǎo)致較多的誤報(bào)率。更為靈活的Token化方法RTF[19]使用后綴數(shù)組(suffix array)而不是后綴樹(suffix tree)，后綴數(shù)組可以刪除不必要的Token序列從而降低虛假檢測次數(shù)，但此技術(shù)實(shí)現(xiàn)較為復(fù)雜。張久杰等[20]提出了基于Token編輯距離的檢測方法，并實(shí)現(xiàn)了一款名為FClones的原型工具。

3.3 基于樹的克隆檢測方法

基于語法樹的檢測方法在匹配定位克隆對之前也要進(jìn)行代碼解析。在解析過程中，檢測工具創(chuàng)建一棵解析樹或者抽象語法樹(abstract syntax tree，AST)來表示源代碼。

Baxter等[21]利用抽象語法樹開發(fā)出了一款檢測工具CloneDR，是基于樹的一款非常好的檢測工具，生成解析樹，然后通過哈希函數(shù)匹配子樹。但是這款工具不能夠識別類似的克隆。為了克服這一問題，Bauhaus等基于避免散列和相似性度量的方法開發(fā)了CCdiml[22]工具，但是不能夠識別重命名的標(biāo)識符。Wahler等[23]將源代碼解析成AST并存入可標(biāo)記擴(kuò)展語言(extensive markup language，XML)，然后通過數(shù)據(jù)挖據(jù)技術(shù)檢測并提取克隆。

3.4 基于程序依賴圖的檢測方法

基于程序依賴圖(program dependency graph，PDG)的技術(shù)利用靜態(tài)分析方法將源代碼抽取成控制流和數(shù)據(jù)流圖，再通過比較及匹配子圖定位并檢測克隆。由于程序依賴圖保留了源程序的語義特征，因此此類方法的準(zhǔn)確度相對較高并且能夠檢測出Type-4克隆代碼。

Komondoor等[24]使用一種名為PDG-DUP的技術(shù)，此技術(shù)使用程序切片(program slicing)的方法在不改變其語義的前提下識別克隆群。Gallagher等[25]擴(kuò)展了Komomdoor等的工作，將程序切片應(yīng)用到了所有的代碼變量，但是并沒有得到任何結(jié)論。Krinke[5]將PDG技術(shù)當(dāng)作一種迭代方法，以便尋找最相似的子圖，但卻不能給一個適用任何類型系統(tǒng)尋找克隆的公式。2008年，Gabel等[26]將PDG中的子圖同構(gòu)問題規(guī)約為子樹同構(gòu)問題，再利用DECKARD進(jìn)行檢測，以提高檢測的速度和可擴(kuò)展性。最近，Higo等[27]報(bào)告了一種基于啟發(fā)式策略的PDG檢測技術(shù)，較好地推進(jìn)了該類技術(shù)的實(shí)用性。

所有的研究人員使用PDG技術(shù)之后得出的結(jié)論是：雖然基于程序依賴圖的檢測技術(shù)可以找到非連續(xù)的克隆，但它不能應(yīng)用于大型系統(tǒng)。

3.5 基于度量的檢測方法

基于度量(metrics)的方法將源代碼分割成若干個小的度量單元(例如，一行，一種方法，一個類)，這種方法并沒有直接比較源代碼，而是計(jì)算度量單位之間的不同。若代碼段的計(jì)算值相同，則被確定為克隆。

Mayrand等[4]利用這一技術(shù)，根據(jù)代碼的名稱、布局的度量和控制流進(jìn)行計(jì)算，但是無法識別基于復(fù)制粘貼操作的代碼段。Kontogiannis等[28]利用馬爾可夫鏈模型進(jìn)行檢測，但此方法只能計(jì)算代碼之間的相似性而不是精確地尋找克隆。Lanubile Calefato使用eMetrics工具識別克隆，然后通過手動檢查來發(fā)現(xiàn)已提取的克隆正確與否，但顯然這種手動方法不適合大型系統(tǒng)[29]。Grant等[30]將數(shù)字信號處理領(lǐng)域的獨(dú)立分量分析(independent component analysis)技術(shù)用于代碼克隆的檢測，初步結(jié)果顯示該方法具有較好的效果。南京大學(xué)計(jì)算機(jī)軟件新技術(shù)國家重點(diǎn)實(shí)驗(yàn)室的董加星[31]針對C語言程序提出了一種面向功能類似程序的克隆檢測方法，通過提取代碼的度量特征進(jìn)行檢測。

3.6 其他檢測方法

國外在克隆檢測方面的研究較多，Sudhamani等[32]提出了一種基于控制語句順序和內(nèi)容的克隆代碼檢測方法。該方法獨(dú)立于程序設(shè)計(jì)語言，并能夠檢測多種類型的克隆代碼；Sheneamer等[33]提出一種基于粗粒度和細(xì)粒度混合的克隆代碼檢測方法，提高了準(zhǔn)確率。國內(nèi)的相關(guān)研究中，哈爾濱工業(yè)大學(xué)的邊奕心等提出一種使用哈希值和標(biāo)識符沖突率來消除克隆代碼檢測的部分誤檢的方法[34]；復(fù)旦大學(xué)的王海等在2013年提出了基于分組的代碼克隆增量檢測方法[35]。另外，北京大學(xué)的王浩宇等在2014年提出一種基于代碼檢測技術(shù)的Android應(yīng)用重打包檢測方法[36]。

3.7 克隆檢測技術(shù)小結(jié)

現(xiàn)有研究中有較多克隆檢測技術(shù)以及對應(yīng)的檢測工具，文中從抽象過程、表示形式、代表工具、優(yōu)缺點(diǎn)等幾個方面對上述檢測技術(shù)進(jìn)行分析比較，具體如表2所示。

表2 克隆檢測技術(shù)比較

4 克隆檢測技術(shù)應(yīng)用

4.1 克隆重構(gòu)

克隆代碼重構(gòu)是一種重組現(xiàn)有的克隆代碼而不改變其外部行為或功能的技術(shù)，它能夠提高設(shè)計(jì)、靈活性和簡單性，而不改變程序的外部行為。克隆代碼重構(gòu)或去除是用來提高系統(tǒng)的可維護(hù)性和可理解性的一種技術(shù)[38]。Kim等[39]在克隆檢測的基礎(chǔ)上分析了克隆代碼的重構(gòu)性，發(fā)現(xiàn)克隆代碼的生命周期較短，且對于被修改的長壽命克隆代碼處在同一類中，認(rèn)為克隆代碼重構(gòu)并不是提高軟件質(zhì)量的完美方式。Meng等[40]設(shè)計(jì)并實(shí)現(xiàn)了一款名為RASE的自動重構(gòu)代碼工具，RASE包括四種不同類型的克隆重構(gòu)方法。

4.2 抄襲檢測

克隆代碼檢測方法可用于軟件代碼的抄襲檢測。DUP[41]是一個用來發(fā)現(xiàn)軟件代碼部分相似的匹配技術(shù)。JPlag[42]是另一種能夠通過文本和程序結(jié)構(gòu)的字節(jié)比較，找到C，C++，Java程序語言編寫的相似之處的工具。

4.3 克隆避免

現(xiàn)有研究中有三種方法，兩種方法主要討論如何檢測克隆和如何去除克隆，另一種為如何避免克隆。Lague等[43]在軟件開發(fā)中使用兩種方式的克隆代碼檢測工具，第一種方法是使用代碼克隆檢測作為預(yù)防性控制，即在系統(tǒng)寫入代碼片段之前，檢查任何附加的代碼片段是否是任何現(xiàn)有代碼片段的復(fù)制版本；第二種方式為問題挖掘，在系統(tǒng)中搜索并修改相互之間類似的代碼片段。

4.4 Bug檢測

克隆檢測和軟件缺陷檢測也有密切的關(guān)系。特別是可以通過克隆檢測工具檢測到復(fù)制粘貼的軟件Bug?，F(xiàn)有的可用于查找代碼缺陷的檢測工具有CPMiner[44]。Higo等提出了一種有效地檢測由復(fù)制粘貼編程引起錯誤的方法。他們的算法都是使用現(xiàn)有的克隆檢測工具，如CCFinderX[17]。然而，目前還不清楚錯誤檢測技術(shù)如何幫助克隆檢測研究。

5 結(jié)束語

克隆檢測是一個活躍的研究領(lǐng)域，并已經(jīng)應(yīng)用于大中型軟件系統(tǒng)中。文中從克隆代碼的定義及分類、克隆檢測過程入手，通過對比已經(jīng)應(yīng)用的檢測技術(shù)闡述了克隆檢測的研究現(xiàn)狀以及克隆檢測的相關(guān)應(yīng)用研究。在保持現(xiàn)有優(yōu)勢的同時，需要進(jìn)一步改進(jìn)或混合更多的方法以克服克隆檢測技術(shù)的局限性。

本研究的結(jié)果可以給克隆檢測人員提供參考，同時也有助于確定后續(xù)的開放性研究問題和未來的研究途徑。