克隆代碼檢測(cè)技術(shù)研究

侯 敏，張麗萍

(內(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)克隆代碼可能會(huì)影響軟件系統(tǒng)的質(zhì)量，特別是對(duì)軟件的維護(hù)和閱讀理解[2]，也可能導(dǎo)致引入潛在Bug。因此大多數(shù)時(shí)候克隆被認(rèn)為對(duì)軟件的演化有負(fù)面影響，是一種壞氣味[3]。

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

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

1 相關(guān)概念

1.1 克 隆

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

1.2 克隆類型

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

表1 克隆類型描述

2 克隆檢測(cè)過程

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

圖1 克隆檢測(cè)過程

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

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

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

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

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

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

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

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

3 克隆代碼檢測(cè)方法及工具

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

3.1 基于文本的克隆檢測(cè)方法

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

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

3.2 基于Token的克隆檢測(cè)方法

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

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

3.3 基于樹的克隆檢測(cè)方法

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

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

3.4 基于程序依賴圖的檢測(cè)方法

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

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

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

3.5 基于度量的檢測(cè)方法

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

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

3.6 其他檢測(cè)方法

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

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

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

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

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

4.1 克隆重構(gòu)

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

4.2 抄襲檢測(cè)

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

4.3 克隆避免

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

4.4 Bug檢測(cè)

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

5 結(jié)束語

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

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