陳秋遠,李善平,鄢 萌,夏 鑫

1(浙江大學(xué) 計算機科學(xué)與技術(shù)學(xué)院,浙江 杭州 310007)

2(Faculty of Information Technology,Monash University,Melbourne,VIC 3800,Australia)

1 引 言

代碼克隆(code clone),也稱為重復(fù)代碼(duplicate code)或相似代碼,指的是存在于代碼庫中兩個及以上的相同或者相似的源代碼片段.代碼克隆產(chǎn)生的原因有很多,主要是開發(fā)者為了提高效率而使用的復(fù)用技術(shù),包括復(fù)制粘貼已有的代碼片段并進行修改、使用開發(fā)框架、復(fù)用設(shè)計模式等.大量的實證研究表明[1–10],代碼克隆廣泛存在于各個開源與閉源代碼倉庫之中,并且占據(jù)了相當(dāng)比例,例如,有研究在 Linux系統(tǒng)中檢測到了 22.3%的代碼克隆[5,6,11],Kamiya等人發(fā)現(xiàn)在 JDK中存在 29%的代碼克隆[1],在某些軟件系統(tǒng)中代碼克隆甚至達到了50%[3].廣泛存在的代碼克隆一定程度上幫助了軟件系統(tǒng)的開發(fā),能夠產(chǎn)生正面的效益[7,12–15],比如可以利用克隆系統(tǒng)測試新增功能對原系統(tǒng)的影響[15],然而也有許多研究指出數(shù)量巨大的代碼克隆會對軟件系統(tǒng)造成負(fù)面的影響[4,16–19]:隨著軟件生命周期的進行,未得到良好克隆管理的軟件系統(tǒng)會因為代碼克隆造成代碼庫的不斷膨脹,從而增加維護成本.軟件缺陷也會因為代碼克隆而在系統(tǒng)中被傳播,降低了軟件系統(tǒng)的可靠性.所以,如果不及時控制代碼克隆的增長,對系統(tǒng)的管理、維護、修復(fù)等行為都會耗費額外的人力[20],導(dǎo)致軟件維護成本的提高.

鑒于此,研究者們致力于研究并解決代碼克隆衍生問題[2,4].其中,如何更快速、更準(zhǔn)確、更便捷地發(fā)現(xiàn)代碼克隆,是代碼克隆研究的核心問題,而利用人工的檢測代碼克隆效率低,成本高,準(zhǔn)確率也無法保證[20].圍繞這個問題,軟件工程研究者們提出代碼克隆檢測技術(shù),目的在于自動化定位軟件系統(tǒng)中的代碼克隆,能夠節(jié)省成本,減少出錯風(fēng)險[21].以此幫助開發(fā)人員和管理者及時發(fā)現(xiàn)代碼克隆,并采取修復(fù)措施[22],有助于更好地保證軟件質(zhì)量[23,24].代碼克隆檢測在剽竊檢測[25,26]、版權(quán)侵犯調(diào)查[27]、代碼重構(gòu)[5,28–30],以及管理代碼質(zhì)量[23]、尋找缺陷[11,27,31]、發(fā)現(xiàn)復(fù)用模式[32]等方面發(fā)揮了重要作用.除此之外,代碼克隆檢測也引起了工業(yè)界的注意[33,34].例如,微軟將克隆檢測工具應(yīng)用在了自己團隊的開發(fā)過程中,并取得了良好的效果[20],展示了代碼克隆檢測技術(shù)的實用性.

根據(jù)代碼克隆相似程度的不同,Bellon等人將代碼克隆分為4種類型[33],即完全相同的代碼(類型1)、重命名的代碼(類型 2)、幾乎相同的代碼(類型 3)和語義相似的代碼(類型4),從類型 1到類型 4,代碼克隆的相似程度逐漸降低,檢測的難度也逐漸增加.學(xué)界產(chǎn)出了一批優(yōu)秀的檢測方法[1,34–38],但依然難以對高難度的代碼克隆進行有效檢測[23],因此需要我們從新的角度提升對代碼克隆檢測的認(rèn)知.

為了認(rèn)識到代碼克隆檢測的本質(zhì)問題,我們對現(xiàn)有方法進行了梳理,不同的代碼克隆檢測方法之間的區(qū)別很大,但是它們都遵循著最基本的思路:即首先進行一定的預(yù)處理,然后進行信息抽取并對源代碼進行表征,最后設(shè)計相似度算法進行對比,從而檢測到代碼克隆.

在這些步驟中,如何對源代碼進行合適的表征是代碼克隆檢測的根本問題.宏觀來說,對源代碼的表征方式?jīng)Q定了對源代碼信息抽取程度的上限,進而影響了所能檢測的代碼克隆的程度;微觀來說,它決定了代碼克隆檢測技術(shù)的預(yù)處理方法、模型設(shè)計、部署方式、運行效率,并會影響最終結(jié)果.現(xiàn)有的代碼克隆檢測方法對源代碼有不同的表征方式,我們根據(jù)對源代碼信息的不同利用程度,將其分為基于文本、詞匯、語法、語義 4個層次:基于文本的表征方式僅利用源代碼作為文本編碼的信息,基于詞匯的表征方式利用源代碼符號序列化信息,基于語法的表征方式融入代碼語法知識信息,基于語義的表征方式除語法之外,還利用了源代碼控制流和數(shù)據(jù)流等信息.不同層次表征方式有各自的特征與優(yōu)缺點,因此也需要科學(xué)系統(tǒng)的方法對其進行驗證和評估.

目前尚無從源代碼表征方式角度對該領(lǐng)域的研究進展進行梳理和歸納的研究工作.鑒于此,本文擬針對當(dāng)前代碼克隆檢測研究進展,從源代碼表征方式角度進行梳理,歸納和總結(jié)現(xiàn)有的代碼克隆檢測技術(shù)和評估方法,總結(jié)當(dāng)前該領(lǐng)域存在的關(guān)鍵問題,并討論解決思路與研究發(fā)展趨勢.

本文第 2節(jié)介紹代碼克隆的相關(guān)概念以及克隆類型的定義,并介紹代碼克隆檢測的一般框架.第 3節(jié)介紹代碼克隆中表征方式的研究進展,從4個層次闡述并歸類現(xiàn)有的工作.第4節(jié)介紹代碼克隆檢測評估方法,主要從實驗驗證方法和評估數(shù)據(jù)集進行總結(jié)和歸納.第 5節(jié)提出代碼克隆分析研究的關(guān)鍵問題,包括科學(xué)問題、技術(shù)問題和工程實現(xiàn)3個方面.最后第6節(jié)對本文進行總結(jié).

2 代碼克隆相關(guān)概念與概況

2.1 代碼克隆基本概念

代碼克隆也稱作重復(fù)代碼或者相似代碼,為了方便論述,本文將統(tǒng)一使用以下基本概念定義.

(1) 代碼片段:代碼片段(clone fragement,簡稱 CF)是源代碼的一部分,它通常包含若干有含義的語句,代碼片段可以是類、函數(shù)、有開始結(jié)束標(biāo)識的代碼塊或者一個聲明的序列.

(2) 代碼克隆/克隆對:如果代碼片段 1(CF1)和代碼片段 2(CF2)的文本、語法或者語義相似,則其中一個就被稱作另一個的代碼克隆.如果這兩者有一定的聯(lián)系以至于兩者是可以類比的,則稱這兩個代碼片段為克隆對(CF1,CF2).

(3) 克隆類:一個克隆類是一系列的克隆對,這些克隆對之間有一定的關(guān)聯(lián),且關(guān)聯(lián)是對稱且對等的.

2.2 代碼克隆類型定義

早期的研究并沒有對代碼克隆的類型進行明確的分類,直到 Bellon等人提出了 4種代碼克隆類型的定義[33],這樣的定義在后續(xù)的研究中獲得了廣泛認(rèn)可.

(1) 類型1(完全相同的代碼):除了空格、注釋之外,兩個代碼片段完全相同的代碼對.

(2) 類型2(重命名/參數(shù)化的代碼):除了變量名、類型名、函數(shù)名之外都相同的代碼對.

(3) 類型 3(幾乎相同的代碼):有若干語句的增刪,或使用了不同的標(biāo)識符、文字、類型、空格、布局和注釋,但是依然相似的代碼對.

(4) 類型4(語義相似的代碼):相同功能的異構(gòu)代碼,在文本或者語法上不相似,但在語義上有相似性.為了直觀地加以說明,圖1給出了4種類型代碼克隆的例子.

相較于原始代碼片段,代碼片段1刪除了注釋,代碼片段2對原始代碼變量名進行了替換,代碼片段3增加了一行計算語句,代碼片段4使用Switch語法代替了If-Else.這種代碼克隆的分類方式反映了代碼片段之間相似程度的不同[33],從類型1到類型4,代碼克隆的相似程度逐漸降低,檢測的難度也逐漸增加.然而,這種分類并沒有對代碼克隆進行詳盡、完備的定義,留下了一定的空間.其中,只有類型1和類型2代碼克隆有嚴(yán)格的定義;對于類型3代碼克隆,語句增刪數(shù)量比例沒有嚴(yán)格定義;對于類型4代碼克隆,相似程度只有寬松的抽象層次的定義.因此,當(dāng)需要具體描述時,不同論文用各自的方式進一步給出了嚴(yán)格定義[2,4,39].

2.3 代碼克隆研究概況

代碼克隆的研究至今已有超過20年的歷史[23],代碼克隆研究可以簡單總結(jié)為兩個問題:一是如何找到代碼克隆,二是找到代碼克隆之后如何分析與利用.第1個問題即研究代碼克隆檢測問題,第2個問題即研究代碼克隆的定性分析[3,6,7,9,16–18,23]與代碼克隆的管理[20,23,29,40]問題.代碼克隆的分析與管理離不開代碼克隆檢測研究的支撐[41],因此本文聚焦于代碼克隆檢測的研究.

早期的代碼克隆檢測技術(shù)只考慮使用文本對源代碼進行表征,這樣只能檢測到類型 1和類型 2的代碼克隆[1].然而這樣的技術(shù)難以滿足實際需求.例如,許多難以被檢測的類型3代碼克隆,是經(jīng)過復(fù)制粘貼然后進行一定增刪形成的,而這種修改方式是開發(fā)人員經(jīng)常使用的代碼復(fù)用技術(shù).為了解決這樣的問題,研究者們使用了比文本更高層次的對源代碼的表征方式,在詞匯、語法、語義層面,提出了能夠檢測類型 3甚至類型 4代碼克隆的檢測技術(shù)[38,42].

代碼克隆問題也引起了工業(yè)界的關(guān)注,一些克隆檢測工具被應(yīng)用到生產(chǎn)開發(fā)環(huán)節(jié)中以控制代碼質(zhì)量[20].研究表明,在實踐中項目不同時期對代碼克隆檢測的應(yīng)用不盡相同.比如,早期項目中克隆檢測可以幫助開發(fā)者及時進行克隆重構(gòu)[40],維護階段項目則利用克隆檢測工具以較低成本進行克隆缺陷管理[20],這種經(jīng)驗可以指導(dǎo)開發(fā)者與管理者更好地關(guān)注與管理代碼庫中的代碼克隆.

2.4 代碼克隆檢測一般框架

檢測代碼克隆是解決代碼克隆問題的關(guān)鍵一環(huán),不同的代碼克隆檢測方法之間的區(qū)別很大,但是它們都遵循著基本的思路,如圖2所示,為了展示一個克隆檢測算法的基本邏輯,本文給出檢測代碼克隆的一般框架.

Fig.2 Research framework of code clone detection圖2 代碼克隆檢測一般框架

(1) 源碼預(yù)處理與轉(zhuǎn)換.代碼預(yù)處理的步驟將移除無意義的代碼片段,將源代碼轉(zhuǎn)化成所需檢測的單元,并決定用于比較的單元.3個主要的預(yù)處理步驟如下:首先根據(jù)需要,將空格、不需要注釋和多余的語句等刪除.然后確認(rèn)源代碼單元,在移除不需要的信息之后,決定哪些是需要比較的單元,一般來說,有文件、類、方法、標(biāo)注開始結(jié)束的代碼塊或者語句級別的比較.最后確認(rèn)比較單元,比較單元一般是根據(jù)源代碼表征方式?jīng)Q定的.比如說,基于符號的算法需要將源代碼切分為符號,基于樹的方法則需要比較子樹等.

(2) 代碼表征.這一步驟可以將源代碼表征為文本,或者進一步利用符號進行表征,更深入的表征方式還包括將源代碼轉(zhuǎn)換成抽象語法樹等.

(3) 代碼相似度比較.在這一步驟中,每一個代碼片段都會與其他代碼片段進行對比來找到代碼的克隆.比對的結(jié)果將以克隆對列表的方式呈現(xiàn).其中,相似比較的算法很大程度上由源代碼表征方式?jīng)Q定.

(4) 代碼克隆結(jié)果過濾.并非所有技術(shù)都需要這一步驟,它的目的是過濾掉檢測錯誤的代碼克隆,過濾方法包括人工檢測或者使用啟發(fā)式算法等.

(5) 代碼克隆結(jié)果整合.這一個步驟主要是將前幾個步驟獲得的代碼克隆和原始的源代碼關(guān)聯(lián)起來并以適當(dāng)?shù)姆绞匠尸F(xiàn)以提供幫助,比如將克隆對聚合成為克隆類,因為作為組的克隆結(jié)果比作為克隆對更能幫助開發(fā)人員或者管理人員.

2.5 代碼克隆檢測評價指標(biāo)

在代碼克隆一般框架之下,不同代碼克隆檢測方法需要根據(jù)不同規(guī)模、結(jié)構(gòu)、編程語言的軟件系統(tǒng)進行不同的定制與改進,為了驗證對比模型效果,以下評價指標(biāo)可以作為參考以及指導(dǎo)方法繼續(xù)改進的方向.

精確度(precision):精確度是指克隆檢測算法所檢測到的候選代碼與克隆真實代碼克隆的比例:

召回率(recall):召回率是指所有被檢測到的代碼克隆數(shù)量占總體代碼克隆數(shù)量的比例:

可移植性:可移植性很大程度上與語言獨立性有關(guān),可移植性高的工具對不同編程語言有良好的支持.比如,一些基于文本或符號的方法因為可以獨立于編程語言,因此有良好的可移植性.基于詞法的方法需要詞法解析,可移植性一般.而基于指標(biāo)的方法和基于程序依賴圖的方法通常需要特定語言解釋器,所以其可移植性最差.

可拓展性:可拓展性主要是指算法可以在大型系統(tǒng)中進行應(yīng)用,并且開銷合理(運行時間、內(nèi)存等).

克隆類型:算法檢測 4種類型的代碼克隆中是評價一個代碼克隆工具的重要指標(biāo),將決定代碼克隆檢測工具的應(yīng)用場景.

克隆粒度:不同算法有不同的檢測粒度,比如逐行對比、符號對比、子樹對比、子圖對比.有研究比較了不同粒度下的克隆檢測算法[43],指出克隆比較粒度常由應(yīng)用場景來決定.

結(jié)果呈現(xiàn):在檢測到的結(jié)果中,相較于克隆對,克隆類能夠提供更多軟件系統(tǒng)中代碼克隆信息[4],比如,NICAD以克隆類進行結(jié)果的呈現(xiàn),獲得了良好結(jié)果[38].

3 克隆檢測中代碼表征方式

在代碼克隆檢測中,源代碼表征方式?jīng)Q定了對源代碼信息抽取程度的上限,會決定檢測方法的預(yù)處理方式、模型設(shè)計、部署方式、運行效率,并影響最終結(jié)果.比如,將源代碼表征為文本,其預(yù)處理過程主要為去除噪聲(如空格、注釋等),其比較算法可以利用文本相似的一系列方法,能夠檢測到文本相似的代碼克隆;而如果表征為抽象語法樹,則其預(yù)處理過程需要解釋器的參與,相似比較算法更多地考慮了結(jié)構(gòu)相似等,能夠檢測到語法層面相似的代碼克隆.因此,源代碼表征方式是代碼克隆檢測的關(guān)鍵步驟.

然而,尚未有研究工作以代碼表征視角研究克隆檢測問題,相關(guān)工作從使用的方法[4]或用途[23]歸納代碼克隆檢測.比如,Rattan等人從軟件工程領(lǐng)域的頂級會議和期刊中,收集了213篇代碼克隆檢測相關(guān)文章,以代碼克隆檢測相關(guān)技術(shù)為切入點,綜述了代碼克隆領(lǐng)域的發(fā)展情況,并介紹了代碼克隆管理等相關(guān)領(lǐng)域[10].然而他們的工作總結(jié)了早期的代碼檢測技術(shù),近期諸如深度學(xué)習(xí)等進展并沒有被討論到,且沒有對源代碼表征方式深入討論.與他們的工作不同,本文深入調(diào)研了代碼克隆檢測中源代碼表征方式,在前人工作的基礎(chǔ)上[4,8,10,23],我們從代碼表征方式角度重新看待問題,根據(jù)對源代碼信息的不同利用程度,將表征方式分為文本、詞匯、語法、語義 4個層次,并將現(xiàn)有的工作進行了歸納總結(jié),從而能夠幫助理解代碼克隆檢測問題的本質(zhì),為未來的研究提供新的視野.本節(jié)將對這4個層次的表征方式進行詳細的闡釋.

3.1 基于文本表征方式的研究

基于文本表征方式的檢測技術(shù)將源代碼當(dāng)作文本編碼,利用一系列文本相似度算法來檢測代碼克隆.文本相似的源代碼屬于相似程度較高的類型1到類型2代碼克隆,表1展示了基于文本表征方式的克隆檢測技術(shù)及其技術(shù)特征[4].這種根據(jù)源代碼的字符串來進行檢測的方法理論上只能檢測類型 1的代碼克隆(直接進行比較)和一些基本的類型 2代碼克隆(進行一些簡單的預(yù)處理,如隱去變量名等).源代碼有其特殊的含義,僅當(dāng)作文本處理會丟失大量的信息,所以基于文本的表征方式利用源代碼信息的程度最低,被劃分在了第1個層次.

Table 1 Characteristics of text-based clone detection approaches表1 基于文本的代碼克隆檢測的技術(shù)特征

知名的基于文本的檢測方法有 Roy和 James提出的 NICAD方法[38]以及 Lee等人提出的 SDD方法[45].NICAD使用了兩種技術(shù)檢測類型1到類型3的代碼克隆,這兩種技術(shù)分別是基于文本的和基于樹的,兩者可以獨立使用來互相補充不足.NICAD分為3個步驟:首先使用了一個解析器(Turing eXtender language,簡稱TXL)來將代碼段分割成行,然后利用一些轉(zhuǎn)換規(guī)則來進行轉(zhuǎn)換,接著將剩下的潛在的克隆對進行重命名,最后利用動態(tài)的模式匹配來找到最長的相同的子序列.NICAD之所以能夠檢測到類型3的克隆,是因為使用了唯一字符串比例(percentage of unique strings,簡稱PUS)來控制檢測松弛度,如果其值為0%,則兩段代碼為類型1完全相同,如果其在0%到某個閾值之間,則檢測出的結(jié)果為類型2或者類型3.NICAD能在代碼段和函數(shù)粒度進行檢測代碼克隆,它有著較高的精確度和召回率[46].NICAD的解析器讓其充分利用了抽象語法樹的技術(shù)的好處,但其利用文本行的比較而非子樹的比較,所以還是一個基于文本的檢測方法,擁有較低的空間復(fù)雜度和計算復(fù)雜度,能夠勝任大型系統(tǒng)的掃描.

SDD是一個Eclipse插件,它能夠在大型軟件系統(tǒng)中高效地檢測代碼克隆,對源代碼的利用是基于文本的表征方式.SDD使用了倒排索引和n近鄰算法,在算法運作時,它建立的倒排索引可以有效減少時間開銷,從而能夠在大型軟件系統(tǒng)中高效運作,幫助開發(fā)者在使用IDE時檢測代碼克隆.

Dup方法使用了后綴樹算法,檢測源代碼文本或者哈希后的相似子序列[27].具體的方法是匹配超過閾值長度的最大代碼段,其檢測步驟分為精確匹配和參數(shù)化匹配:精確匹配將完全相同的源代碼進行匹配檢測,參數(shù)化匹配將除了變量名不同的代碼預(yù)處理后進行匹配,比如,將所有變量替換成同一字符串.這種文本方法忽略了注釋和空格,基于文本行進行檢測,能夠檢測到類型1和類型2代碼克隆.

Duploc方法使用字符串操作對代碼行進行了簡單的預(yù)處理,然后使用基本的字符串方法來檢測最長相同子序列[44].這樣,基于純文本檢測方式讓 Duploc無需解析器或者詞法分析器,擁有較好的可移植性,獨立于不同編程語言,然而也限制了檢測的代碼克隆類型.Duploc一般能夠檢測類型1和類型2代碼克隆.

利用文本進行源代碼表征的檢測技術(shù)幾乎不會檢測到文本差異大的代碼克隆,因此精確度很高,很少會出現(xiàn)假陽率(錯誤地將非代碼克隆識別成克隆).因為只從文本方面考慮,這種表征方式獨立于編程語言,部署成本較低,計算開銷較小,有很強的可拓展性和易用性,因此空間復(fù)雜度和時間復(fù)雜度比較低.但是也有它的缺點和局限性,主要表現(xiàn)在:源代碼雖然以文本方式編碼,但是還保留有語法等信息,在檢測中如果只使用文本方式進行源代碼表征,會損失大量信息.

3.2 基于詞匯表征方式的研究

基于詞匯的檢測技術(shù)也叫作基于符號(token)的檢測技術(shù),這種技術(shù)利用了解析器將源代碼分成符號序列,然后這些符號序列會被組織成符號的語句,最后將這些符號組成的語句進行比較.基于詞匯的方法利用了更符合編譯原理的符號序列,對源代碼信息有了更進一步的利用,所以被劃分到了比單純的基于文本更深入的層次.

表2展示了基于詞匯的克隆檢測技術(shù)及其關(guān)鍵步驟的特征.知名的基于詞匯的克隆檢測技術(shù)有Kamiya等人提出的CCFinder[1]和針對大規(guī)模情景的基于分布式的D-CCFinder[47],以及Li等人提出的CP-Miner[37]等.

Table 2 Characteristics of lexis-based clone detection approaches表2 基于詞匯的代碼克隆檢測的技術(shù)特征

CCFinder的檢測步驟分為4個部分:首先使用詞法分析器解析成為符號序列并去除所有空格和注釋,然后符號序列經(jīng)過一定的轉(zhuǎn)化規(guī)則進行變形,并進行參數(shù)替換將標(biāo)識符變成特殊的符號,接著匹配檢測階段使用后綴樹匹配算法檢測出代碼克隆對和克隆類,最后再將代碼克隆的行數(shù)映射到源代碼文件中.CCFinder也使用了一些指標(biāo)度量來檢測潛在的代碼克隆:如源代碼長度、克隆類的群體大小、代碼克隆的覆蓋率.在算法復(fù)雜度問題上,它優(yōu)化了源代碼程序的長度以減少計算復(fù)雜度.CCFinder雖然能夠獲得較高的召回率,但是準(zhǔn)確率卻不盡如人意[6].一次也只能接受一種編程語言來檢測.

CP-Miner致力于檢測大型系統(tǒng)中的代碼克隆以及與代碼克隆有關(guān)的軟件缺陷,它使用頻繁項挖掘[53]技術(shù)來達到這一目的.CPMiner首先使用解析器來將源代碼變成一個序列的集合,產(chǎn)生一個數(shù)據(jù)庫來表征每一段源代碼,然后使用改進的 CloSpan算法[53]來幫助達到頻繁項挖掘的間隔限制,最后的結(jié)果將會包含正確和錯誤的復(fù)制粘貼代碼段,最后會檢查相鄰的代碼段來進行過濾,得到最終的代碼克隆檢測結(jié)果.相比于 CCFinder,CPMiner能夠做到更高的準(zhǔn)確率,同時召回率也不會下降太多,但其問題在于很難確定頻繁項挖掘中子項的長度:如果太長,則會嚴(yán)重影響效率,如果太短,則會丟失非常多的信息,最終影響效果.

近期基于符號的方法還有Wang等人提出的CCAligner方法[51],在將源代碼進行預(yù)處理之后,他們使用了一個滑動的窗口,將窗口中的源代碼進行了哈希,最后進行多重對比,從而在符合閾值的范圍內(nèi)檢測到代碼克隆.CCAlingner對于有較大間隔的類型3取得了非常不錯的效果,其中,大間隔代碼克隆是指代碼片段1(CF1)行數(shù)與代碼片段(CF2)行數(shù)比值小于或等于0.7的代碼克隆對[51].

Li等人的 CCLearner工作采用了深度學(xué)習(xí)方法來學(xué)習(xí)符號層面的代碼信息.他們使用 BigCloneBench[54]作為訓(xùn)練樣本,抽取了其中方法級別的符號序列,用一個全連接神經(jīng)網(wǎng)絡(luò)數(shù)據(jù),對數(shù)集中標(biāo)注的克隆對和非克隆對進行訓(xùn)練,學(xué)習(xí)這些特征并用于檢測代碼克隆.需要注意的是,為了提高信息利用程度,他們也抽取了部分抽象語法樹的信息進行訓(xùn)練,但并不是模型的重點.

除此之外,Boreas方法使用了余弦相似度和一種按比例的相似度的方法來檢測代碼克隆;Murakami等人提出的 FRISC[49]將重復(fù)指令轉(zhuǎn)換成了一種特殊的格式,然后使用后綴數(shù)組的算法來檢測克隆,但其檢測出來的代碼克隆有更高的錯誤率;CDSW使用了Smith-Waterman算法[55]來檢測代碼克隆,其準(zhǔn)確度受到算法中的參數(shù)的影響,且有較大的波動.XIAO使用了與CP-Miner類似的預(yù)處理方法[34],但是根據(jù)實際情況加入了更多的指標(biāo)度量來幫助檢測代碼克隆,它將語句序列化并使用哈希后的值來進行比較,檢測軟件系統(tǒng)中的代碼克隆.

相對于基于文本的代碼表征方式來說,基于詞匯的代碼表征方式能夠匹配到許多代碼特有的信息.但從本質(zhì)上說,基于詞匯的代碼表征方式與文本一樣都是序列化的表征方法,只是對源代碼的利用程度有所提升,它有如下幾個缺點.

(1) 基于詞匯的代碼表征方式?jīng)]有考慮到代碼行的順序,如果代碼克隆的順序被改變了,代碼克隆將不會被檢測到.

(2) 基于詞匯的代碼表征方式對于增加刪改了符號的代碼語句比較敏感,容易漏檢特定細微差別的代碼克隆.

(3) 基于詞匯的代碼表征方式依然沒有充分利用源代碼的信息,比如它會忽略掉源代碼中的結(jié)構(gòu)信息.

3.3 基于語法表征方式的研究

基于語法的代碼表征方式更多地考慮到了源代碼的語法規(guī)則,從而能夠?qū)ζ渲刑N含的信息加以利用.基于語法的代碼表征方式主要有基于語法樹的方法和基于指標(biāo)的方法.

抽象語法樹(AST)是源代碼特有的一種表現(xiàn)形式,它是編譯源代碼的一個中間結(jié)果,以樹的形式包含了源代碼中的語法信息.在代碼克隆檢測中,基于樹的方法會將源代碼解析成抽象語法樹作進一步的處理并用于檢測.為了更加直觀,圖3展示了一段輾轉(zhuǎn)相除法代碼轉(zhuǎn)換而成的抽象語法樹,要檢測它的代碼克隆,可以利用樹匹配等算法進行子樹的比較,其中形狀完全相同的樹可以認(rèn)為是類型 1的代碼克隆,而如果忽略節(jié)點的標(biāo)識符或者進行一定程度的剪枝(例如,忽略某層節(jié)點下面的子節(jié)點),對剩余的結(jié)構(gòu)進行比較,經(jīng)過修改的代碼克隆也能夠被檢測到.

Fig.3 Represent source code with abstract syntax tree圖3 使用抽象語法樹表征源代碼

根據(jù)語法特性,一段源代碼擁有很多指標(biāo)度量(比如代碼行數(shù)、循環(huán)數(shù)量、變量數(shù)量等),這些指標(biāo)度量一定程度上能夠表征這段源代碼.因此,在代碼克隆檢測中,基于指標(biāo)的方法抽取目標(biāo)代碼段的指標(biāo)度量表征這段源代碼,然后進行比較,從而檢測出代碼克隆.

表3展示了基于語法的克隆檢測技術(shù)及其技術(shù)特征.知名的基于樹的檢測方法有 Baxter等人提出的CloneDR[35]和Jiang等人提出的Deckard[42]等.基于指標(biāo)來進行代碼克隆檢測的方法包括Mayrand等人[56]的工作和Kontogiannis等人[32]的工作,抽取了預(yù)先定義的代碼特征,然后進行比較并獲得代碼克隆.

Table 3 Characteristics of syntax-based clone detection approaches表3 基于語法的代碼克隆檢測的技術(shù)特征

CloneDR使用了基于語法樹的方法,能檢測到完全和幾乎相同的代碼克隆,并且能夠利用抽象語法樹來進行代碼重構(gòu).在CloneDR方法中,在源代碼被解析成抽象語法樹之后,它利用3種主要的算法來進行代碼克隆檢測:第1種算法能夠檢測整棵樹中的子樹的克隆,使用哈希方法將子樹分割然后比較這些子樹;第2種算法檢測子樹中變長序列的克隆;第 3種算法結(jié)合了其他檢測方法找到更多的代碼克隆.CloneDR雖然使用了抽象語法樹,能夠檢測到基于文本或者詞匯無法檢測到的代碼克隆,但卻不能檢測到語義相似的代碼克隆.

Deckard使用了基于樹的方法和歐式距離相似度,它的主要步驟如下:首先使用一個語法解析器將源代碼解析成解析樹,然后解析樹被用來生成一個向量集用于承載解析樹中的結(jié)構(gòu)信息,接著,這些向量被局部敏感哈希算法進行了聚類,從而可以尋找一個向量的近鄰,最終一些后續(xù)操作將結(jié)果轉(zhuǎn)化為檢測到的代碼克隆.Decard能夠檢測到改變了順序的代碼克隆和不相鄰的代碼克隆.拋開解析器的不同僅比較樹的相似度,Deckard能夠做到一定程度的語言獨立.但是Decard的比較速度比較慢,其解析過程也會消耗非常多的時間.

Mayrand等人的工作計算了源代碼函數(shù)的名稱、層次、表達式和控制流抽取出來的指標(biāo)度量,如果兩個指標(biāo)是相似的,這兩個函數(shù)則被認(rèn)為是代碼克隆.他們的工作著眼于定位相似函數(shù)而非相似代碼段,但在真實情況下,相似的代碼片段要比單純的相似函數(shù)出現(xiàn)的頻率高很多.

Kontogiannis等人的工作用了兩個步驟來檢測代碼克隆相似度:第 1種方法抽取了源代碼中的指標(biāo)度量,然后使用簡單的數(shù)值比較.第 2種方法使用了動態(tài)程序來計算,并使用了最小的編輯距離來測量兩個代碼段的相似度.這種方法只能給出初步的結(jié)果,用戶還需要自行作進一步的人工檢查來確定代碼克隆的正確性.

Wei等人的CDLH[39]使用了深度學(xué)習(xí)方法來學(xué)習(xí)代碼克隆的特征.CDLH將代碼克隆檢測問題轉(zhuǎn)化為學(xué)習(xí)源代碼的哈希特征的有監(jiān)督學(xué)習(xí)問題,主要分為 3步:首先將源代碼用抽象語法樹表征之后用一定的編碼規(guī)則進行編碼,然后將編碼后的數(shù)據(jù)輸入一個修改過的卷積神經(jīng)網(wǎng)絡(luò)當(dāng)中進行訓(xùn)練,最后用訓(xùn)練到的特征進行代碼克隆檢測.CDLH可以檢測到類型1到類型4的代碼克隆,而且做到了非常高的精確度和召回率.

除此之外,基于樹的方法還有Wahler等人的工作[57],將抽象語法樹用XML形式進行了轉(zhuǎn)換然后進行比較與檢測,但是只能檢測到類型1和類型2的代碼克隆.基于度量的方法還有Kodhai[60]等人的工作,但是只能檢測類型1和類型2的代碼克隆;Abdul-El-Hafiz等人的工作[61]使用了數(shù)據(jù)挖掘中幾何聚類的算法,但是沒有具體的精確度和召回率,也不能檢測類型4的代碼克隆;Raheja等人的工作[62]利用了字節(jié)碼進行檢測,進而映射到源代碼中,它可以檢測到一部分語義相似的源代碼,然而需要編譯器進行編譯,部署成本比較高,且只對一種語言有效.White等人的工作[58]人工采樣了398個文件級別和480個方法級別的克隆對作為訓(xùn)練樣本,將源代碼轉(zhuǎn)換為其定義的樹的結(jié)構(gòu),采用卷積神經(jīng)網(wǎng)絡(luò)進行訓(xùn)練,最后用學(xué)習(xí)到的特征檢測代碼克隆.

基于語法的代碼表征方式能夠考慮到源代碼的結(jié)構(gòu)特性,從而對信息的利用更加充分,相比于文本和詞匯是更加深入的一個層次.它對源代碼的順序變換更加不敏感,對于細微修改的代碼克隆也可以做到檢測.但是信息利用程度的增加也帶來了一些弊端,基于語法的方法有如下缺點.

(1) 基于樹的方法不能識別出標(biāo)識符和文本值的不同.

(2) 基于樹的方法由于需要遍歷樹,計算開銷比較大.

(3) 基于指標(biāo)的方法在獲取特定指標(biāo)時需要解釋器或者程序依賴圖來獲得.

(4) 基于指標(biāo)的方法難以保證較高的精確度,即使是兩個代碼片段的指標(biāo)是相同的,這兩段代碼也有可能是不相似的.

3.4 基于語義表征方式的研究

基于語義的代碼表征方式,不僅考慮了源代碼的語法,還要利用其語義信息,其中,語義信息是指能夠反映一段代碼功能的信息,比如代碼的控制流和數(shù)據(jù)流.在代碼克隆檢測問題下,基于語義表征源代碼的技術(shù)可以分為基于圖的技術(shù)和混合技術(shù)兩類.

基于圖的檢測技術(shù)使用由程序生成的數(shù)據(jù)流圖和控制流圖來組成程序依賴圖(PDG),數(shù)據(jù)流代表了源代碼中數(shù)據(jù)的走向,控制流代表了源代碼中邏輯的走向,它們組成的程序依賴圖不僅是基于語法的,也表征了一段源代碼的語義信息.為了直觀說明,圖4展示了使用包含控制流和數(shù)據(jù)流的程序依賴圖表征源代碼的例子,其中,每一個節(jié)點代表一個語句或者一個斷言,每一條邊則代表數(shù)據(jù)流(實線)或者控制流(虛線).將源代碼用圖的方式表征,只比較圖的相似度,能夠?qū)栴}轉(zhuǎn)化為檢測相似圖的問題,最終檢測到代碼克隆.

基于混合技術(shù)的克隆檢測不再是單一的技術(shù),而是利用多種技術(shù)的混合來達到語義檢測的目的.比如說,可以利用基于文本的方法結(jié)合基于指標(biāo)度量的方法先后表征一段代碼,從兩種不同的維度刻畫它的特征,從而能夠得到其更精確的語義特征[63].

表4展現(xiàn)了基于語義的檢測方法及其技術(shù)特征.知名的基于圖的檢測技術(shù)有Komondoor和Horwitz提出的利用同構(gòu)程序依賴圖的切片來檢測克隆的方法[64]和 Krinke等人提出的 Duplix[36].知名的混合技術(shù)則有Hummel等人提出的ConQAT[65]方法,它利用了符號化代碼和哈希等方法,結(jié)合了第1層次和第2層次的源代碼語義表征來進行代碼克隆的檢測.

Komondoor等人提出的方法使用了程序切片來尋找同構(gòu)的程序依賴圖的子圖,切片的克隆檢測算法分為3個步驟:首先將程序依賴圖中的節(jié)點劃分到同等的類當(dāng)中,在每個類中,每兩個節(jié)點都是相對應(yīng)的,然后它會去掉節(jié)點中包含的其他子節(jié)點,這樣就不會有父節(jié)點與子節(jié)點被重復(fù)檢測的問題,最后將克隆對進行聚合給出檢測的結(jié)果.

Krink提出的 Duplix方法使用的是類似于抽象語法樹和傳統(tǒng)的程序依賴圖,因此,它使用的程序依賴圖的頂點和邊代表了語句的組件,也包含了控制流的邊.Duplix的檢測方法與Komondoor等人的工作類似,它們在檢測最大相似程序依賴圖上取得了較高的精確度和召回率.

Hummel等人提出的ConQAT使用了一種混合方法來檢測代碼克隆.它分為3個步驟:首先將源代碼進行預(yù)處理,然后將其變?yōu)榉柣蛄?所有的符號都被整理到一個聲明中,然后在后續(xù)的工作中尋找相同的子字符串,最后使用了克隆的索引在所有的文件中尋找類似的代碼克隆.在ConQAT中,序列化的方法使用了MD5的哈希算法[48,66],相同哈希值的兩個序列被認(rèn)為是相同的代碼克隆對.

Fig.4 Represent source code with program dependency graph圖4 使用程序依賴圖表征源代碼

Table 4 Characteristics of semantic-based clone detection approaches表4 基于語義的代碼克隆檢測的技術(shù)特征

基于圖的方法還有 GPLAG[67],它也使用了同構(gòu)的程序依賴圖的子圖的對比算法,能夠在小數(shù)據(jù)集上有著不錯的效率,但是隨著數(shù)據(jù)集的變大,計算復(fù)雜度將會呈指數(shù)增長;Higo等人的工作[68,71]使用了簡化的方法,能夠檢測非相鄰的代碼克隆對,比一般的基于程序依賴圖的方法更快.

近期使用了混合方法的工作有Saini等人提出的方法Oreo[70].Oreo是一個代碼克隆檢測的框架,在它提出的流程中,使用了基于指標(biāo)度量的方法在預(yù)處理過程中進行了初步篩選與分組,然后進一步從函數(shù)中抽取語義,并使用了基于哈希的方法進一步篩選,能夠?qū)︻愋?1和類型 2的代碼克隆進行較好的覆蓋,在流程的最后加入了深度學(xué)習(xí)的方法,提升了對類型3代碼克隆的檢測能力.其中,輸入數(shù)據(jù)以對(pair)的形式輸入是代碼克隆檢測的一個技術(shù)特點,Oreo在深度學(xué)習(xí)結(jié)構(gòu)中使用的Siamese結(jié)構(gòu)[72]很好地解決了代碼克隆輸入的對稱性問題,即(CF1,CF2)與(CF2,CF1)在作為輸入時是等效的,值得借鑒.

混合方法還有 Funaro等人的工作[69],綜合了基于文本的方法和符號的方法,能夠做到對類型 3克隆的檢測;Agrawal[63]等人的工作綜合了基于文本和指標(biāo)度量的方法,但是只能檢測C的代碼克隆.

綜上所述,基于語義的方法能夠在深入的層次利用源代碼的信息,從而檢測代碼克隆,這些方法充分利用了源代碼不同于一般的自然語言文本的特性,包括了結(jié)構(gòu)、順序以及特殊的語法等信息,也能夠獲得一定程度的語義信息.但其還具有如下缺點.

(1) 基于圖的技術(shù)需要一個程序依賴圖的生成器.而對于不同的語言會產(chǎn)生技術(shù)隔閡.

(2) 基于圖的圖匹配檢測技術(shù),計算的開銷非常大.

(3) 基于混合技術(shù)表征源代碼語義步驟繁雜,難以部署.

4 克隆檢測評估方法

不同層次表征方式有各自的特征與優(yōu)缺點,因此也需要科學(xué)、系統(tǒng)的方法對其進行驗證和評估.為了評估代碼克隆對軟件系統(tǒng)的影響,在早期研究中,主要報告檢測到的代碼克隆在軟件系統(tǒng)中的比例[2,23,73–75].這樣的實證研究能夠為后續(xù)研究提供證據(jù)支撐,啟發(fā)思維.在提出克隆檢測方法的過程中,為了驗證和對比模型效果,研究者需要對檢測模型進行實驗驗證.其中,評價指標(biāo)中重要的精確度和召回率需要已知克隆對這樣的先驗知識,然而,面臨未知軟件系統(tǒng)卻難以預(yù)先獲得代碼克隆準(zhǔn)確數(shù)量.評估代碼克隆檢測的關(guān)鍵是收集客觀、有效的先驗數(shù)據(jù)集,因此,研究者們使用數(shù)據(jù)標(biāo)注方法和數(shù)據(jù)生成方法獲取代碼克隆先驗知識以評估模型.

4.1 標(biāo)注數(shù)據(jù)收集方法

一些研究者們在提出方法時會自己搜集若干代碼庫[30,33,76–78],利用上下文,修改歷史和人工檢查等標(biāo)注代碼克隆,并用于評估自己的檢測模型,然而不同的系統(tǒng)有不同的規(guī)模和結(jié)構(gòu)等,這樣的缺陷是代碼庫規(guī)模不夠大[54],難以形成統(tǒng)一的評價基礎(chǔ).為了解決這樣的問題,Svajlenko等人提出了 BigCloneBench[54].BigCloneBench是一個Java代碼集,它包含了從類型1到類型4的大量的人工標(biāo)注的克隆對,包含10個功能,耗費了8個專家216個小時標(biāo)注 600萬對代碼克隆和 26萬對負(fù)樣本.很多后續(xù)的工作基于這個數(shù)據(jù)集評估它們自己的方法[39,51,52],BigCloneBench推進了代碼克隆檢測的研究.但是這樣的數(shù)據(jù)集有兩個缺陷:第一,它只有 10個功能,這不符合真實的軟件系統(tǒng)的情況;第二,這個數(shù)據(jù)集的構(gòu)建方法是基于啟發(fā)式的搜索加上人工標(biāo)注,而啟發(fā)式搜索在某種程度上限制了代碼克隆的模式.

4.2 評估數(shù)據(jù)生成方法

在代碼克隆檢測中,召回率需要已知軟件系統(tǒng)中的所有代碼克隆,然而這難以在每一個新的軟件系統(tǒng)中實現(xiàn).Roy等人借鑒軟件測試中的變異測試[79],提出了一種變異插入的測試代碼克隆的方法[46],其思想是在一段源碼中插入一段人工代碼,從而人為制造出不同類型的代碼克隆對,以此作為測試集進而評估代碼克隆檢測工具的效果.這樣的數(shù)據(jù)生成方法能夠有效獲得召回率,比如,Wang等人在評估CCAligner針對大間隔代碼克隆的召回率時使用了這種方法[51].雖然這樣操作部分解決了代碼克隆評價指標(biāo)的問題,但是人工構(gòu)造的代碼克隆對不是真實數(shù)據(jù)集,難以從科學(xué)和工程上證明有效性,因此只能作為一種輔助測試方式.

5 代碼克隆檢測關(guān)鍵問題與解決思路

雖然代碼克隆檢測的研究已經(jīng)有超過20年的歷史,獲得了非常多的成果,但是現(xiàn)有的研究與工業(yè)界的期望還有一定的距離,這是作為研究者需要正視的問題.本節(jié)首先討論代碼克隆檢測研究中的關(guān)鍵問題,然后討論針對這些問題的解決思路.

5.1 關(guān)鍵問題

雖然代碼克隆檢測以往獲得了大量研究者的關(guān)注,取得了較大進展,但仍然存在一些亟待解決的關(guān)鍵問題.本節(jié)將從科學(xué)問題、實用性、技術(shù)難點和工程實踐3個方面闡述目前代碼克隆研究中存在的問題.

5.1.1 代碼克隆檢測研究的科學(xué)問題

代碼克隆檢測研究的科學(xué)問題分為3個方面.

(1) 代碼克隆產(chǎn)生的歸因分析與檢測技術(shù)的有機結(jié)合.即分析所檢測到的代碼克隆產(chǎn)生的具體原因,以及研究如何進一步提高代碼克隆檢測的準(zhǔn)確性相關(guān)研究,從歷史角度研究了代碼演進過程,從克隆族譜的角度研究了代碼克隆的形成過程[6],以及形成后的更替與傳播[78],然而現(xiàn)有歸因分析僅僅對代碼克隆的影響進行了定性研究[16].進一步地,研究者需要針對代碼克隆形成原因,設(shè)計相關(guān)克隆檢測技術(shù),提高克隆代碼檢測技術(shù)對克隆代碼的預(yù)防能力和時效性.

(2) 代碼克隆檢測中數(shù)據(jù)標(biāo)注的準(zhǔn)確性.準(zhǔn)確的有標(biāo)注的代碼克隆數(shù)據(jù)對于代碼克隆檢測的研究至關(guān)重要,是檢測模型訓(xùn)練、評估及技術(shù)對比的基準(zhǔn).雖然,類型1和類型2代碼克隆因為定義具體而易于準(zhǔn)確標(biāo)注,然而,類型3和類型4代碼克隆卻難以準(zhǔn)確標(biāo)注,特別是沒有具體定義的類型4,一般是指功能相似的異構(gòu)代碼(即結(jié)構(gòu)不相同的代碼)[4,33],如何對異構(gòu)代碼進行標(biāo)注是代碼克隆數(shù)據(jù)標(biāo)注中的一大難點.現(xiàn)有的 BigCloneBench對類型 4代碼克隆的標(biāo)注采用人工審查代碼的方法[54],而如果從功能和需求出發(fā),結(jié)合代碼功能或需求描述文檔,將有助于提高代碼克隆標(biāo)注的準(zhǔn)確性.例如,在針對文件級克隆進行標(biāo)注時,可參考需求文檔中的功能描述;在針對方法級或片段級克隆進行標(biāo)注時,可參考代碼注釋中的功能描述.

(3) 代碼克隆檢測的可拓展性.如今在代碼大數(shù)據(jù)[80]的環(huán)境下,軟件系統(tǒng)的規(guī)模日益變大,這也給代碼克隆檢測帶來了新的挑戰(zhàn).近期的研究表明,一些早期的代碼克隆檢測技術(shù)[38,42]已經(jīng)難以勝任千萬行級別甚至上億行級別的代碼檢測任務(wù)[41,51],因此,未來的代碼克隆檢測技術(shù)研究不僅要考慮精確度和召回率等檢測指標(biāo),還需提升對大規(guī)模代碼檢測的能力.此外,代碼增加與迭代速度也日益變快,比如開源倉庫Github中每天都會有成千上萬的貢獻者貢獻代碼,在這樣的情況下,如果每次都進行全量的代碼克隆檢測將花費較高的代價[68,81,82].因此,在未來的研究中,代碼克隆檢測的可拓展性,即能否將檢測范圍拓展到大規(guī)模代碼倉庫中,能否在高頻率增量代碼的場景下達到開銷與性能的平衡,是研究者需要考慮的問題.

5.1.2 克隆研究的實用性

現(xiàn)有代碼克隆研究主要在于以克隆對或者克隆類的形式給出結(jié)果,不同的研究給出了不同的粒度屬性.克隆對或者克隆類僅僅只有源代碼的指向,沒有更進一步的分析與展示;在研究工作中選擇的粒度也僅僅根據(jù)現(xiàn)有數(shù)據(jù)的方便程度而非工程中的實用程度.針對軟件開發(fā)或者維護過程中如何有效利用代碼克隆檢測的結(jié)果尚未有統(tǒng)一的觀點,因此,需要展開深入的實證研究,結(jié)合開發(fā)過程,以調(diào)研開發(fā)者實際需要哪種類型的代碼克隆結(jié)果,如何能夠更加有效地利用代碼克隆檢測結(jié)果等問題.

5.1.3 技術(shù)難點

如何更準(zhǔn)確地標(biāo)注代碼克隆對是代碼克隆檢測中的技術(shù)難點之一.一方面,雖然有變異插入的標(biāo)注方法可以大量生成代碼克隆對,但是這種方法難以保證在真實的代碼庫中奏效;另一方面,雖然有研究者花費人力標(biāo)注了大量的數(shù)據(jù)集,但是這樣的數(shù)據(jù)集有其本身的局限性,在這個基礎(chǔ)上設(shè)計的模型,特別是機器學(xué)習(xí)模型,一旦用到一個新的軟件系統(tǒng)中,難以表現(xiàn)出良好的泛化性能.因此,研究者們在針對新進項目獲取標(biāo)注數(shù)據(jù)時面臨著實際應(yīng)用上的挑戰(zhàn).

源代碼的表征方法也是一個技術(shù)難點,從文本到詞匯、語法、語義,對于源代碼信息的利用程度會逐漸增高,但是帶來的副作用是對于語言的獨立性逐漸下降,對于如解釋器等的額外工具的需求也會逐漸增加,大大提高了算法開發(fā)與實際應(yīng)用的門檻.所以考量多個維度,在適當(dāng)?shù)膶哟纬槿≡创a,考慮它們之間的易用性、關(guān)聯(lián)性也是一大技術(shù)難點.

現(xiàn)有代碼克隆檢測技術(shù)在模型構(gòu)建上存在著不同的策略:在源代碼的表征方法方面,基于文本、詞匯、語法、語義等方式有多種選擇;預(yù)處理可以進行不同的抉擇,而只做簡單的消除或者復(fù)雜變形;模型中相似度的計算則受到前面階段選擇的局限;最后結(jié)果的呈現(xiàn)也有克隆對克隆類,甚至考慮重新設(shè)計可視化界面等多種選擇.但是正因為選擇太多,所以需要權(quán)衡各種策略的利弊,這也給模型的設(shè)計增添了困難.因此,針對場景,選擇合適的模型是代碼克隆檢測設(shè)計的一大難點.最后,工業(yè)界對于類型 4有著較大的需求,但是現(xiàn)有的工具難以滿足這一需求,因此也是需要研究突破的方向.

5.2 解決思路

針對上一節(jié)所總結(jié)的關(guān)鍵問題,本節(jié)圍繞數(shù)據(jù)標(biāo)注、表征方法、模型構(gòu)建和工程實踐 4個方面,闡述問題可能得以解決的思路和研究的未來發(fā)展趨勢.

5.2.1 綜合考慮多源軟件制品,提出更準(zhǔn)確的數(shù)據(jù)標(biāo)注方法

現(xiàn)代大型軟件項目都會使用多個系統(tǒng)對軟件開發(fā)和維護中產(chǎn)生的數(shù)據(jù)進行存儲和管理,例如代碼版本控制系統(tǒng)(如Git)、代碼審查系統(tǒng)(如Gerrit)等.這些不同系統(tǒng)中存儲著不同的軟件制品,代碼克隆的產(chǎn)生是一個復(fù)雜過程,并與多種軟件制品相關(guān),包括源代碼、需求報告、代碼審查、代碼靜態(tài)掃描等,現(xiàn)在還缺乏這方面的研究.綜合考慮多源異構(gòu)的軟件制品,有助于更立體地獲得真實軟件系統(tǒng)中標(biāo)注的代碼克隆數(shù)據(jù).同時也應(yīng)該注意,從多個源頭的軟件制品獲取代碼克隆也會引入噪音,比如從需求映射到代碼中的噪音問題[83]、代碼靜態(tài)掃描中的誤報問題[84]、代碼注釋與代碼的不匹配問題等[85],需要謹(jǐn)慎甄別,以保證標(biāo)注數(shù)據(jù)的準(zhǔn)確性不受干擾.

5.2.2 綜合考慮實際需求,選擇或提出更加合適的代碼表征方法

在自然語言處理領(lǐng)域,表征學(xué)習(xí)是一個被關(guān)注的熱點,同時在軟件工程領(lǐng)域,如何將源代碼進行適當(dāng)?shù)谋碚饕彩谴罅抗ぷ鞯幕A(chǔ),從而引起了研究者們的關(guān)注[86]:將源代碼進行適當(dāng)?shù)谋碚?就可以增強對代碼克隆的檢測能力.與此同時,也要結(jié)合已有的表征方法,對優(yōu)缺點進行權(quán)衡,比如基于語義表征代碼中基于圖的表征方式,早期利用圖表征源代碼進行代碼克隆檢測的研究使用了傳統(tǒng)的圖匹配算法[36,64,68],算法的可移植性和可拓展性都比較差,但是如果考慮圖嵌入[87]技術(shù),用嵌入向量的相似比較完成代碼克隆檢測,既利用了以圖為基礎(chǔ)的代碼中的語義信息,又能夠兼顧算法的可用性.雖然基于圖的表征方式中圖的定義與構(gòu)建都需要許多研究工作來探索[67,86],但依然是一個可以嘗試的方向.因此,使用針對源代碼的方法,提取多維特征來增強源代碼的表征能力,將是代碼克隆研究的一個發(fā)展方向.

5.2.3 研究更先進的建模技術(shù),取得建模技術(shù)上的突破

近年來,深度學(xué)習(xí)成為機器學(xué)習(xí)的熱點研究領(lǐng)域,被大量應(yīng)用到如圖像處理、語音識別等研究中.相比傳統(tǒng)的機器學(xué)習(xí)技術(shù),研究者發(fā)現(xiàn)深度學(xué)習(xí)在這些領(lǐng)域的應(yīng)用可以取得更好的性能[39,52].將目前機器學(xué)習(xí)領(lǐng)域大量研究與應(yīng)用的技術(shù),如遞歸神經(jīng)網(wǎng)絡(luò)應(yīng)用到代碼克隆檢測技術(shù)中,將有可能進一步提升代碼克隆研究的性能.在現(xiàn)有的工作中,深度學(xué)習(xí)已經(jīng)展現(xiàn)了一定的能力,例如CCLearner以基于符號的方式學(xué)習(xí)代碼克隆[52],CDLH利用了源代碼的抽象語法樹結(jié)構(gòu)[39],Oreo提出的深度學(xué)習(xí)框架解決了代碼克隆輸入的對稱問題,并能在初步檢測的基礎(chǔ)上進一步提高檢測性能[70],這些方法都在對類型 3和類型4的代碼克隆檢測中取得了一定成效,但是由于標(biāo)注數(shù)據(jù)集本身限制的問題,例如被廣泛使用的BigCloneBench,只標(biāo)注了10個功能的代碼克隆[54],不足以滿足現(xiàn)實需求.要更好地研究深度學(xué)習(xí)模型,一方面,需要大量準(zhǔn)確的標(biāo)注數(shù)據(jù),雖然研究者提出的變異測試方法[46]可以生成大量的訓(xùn)練數(shù)據(jù),但是真實、準(zhǔn)確的標(biāo)注代碼克隆也是不可或缺的.另一方面,代碼表征的復(fù)雜性需要被充分探索,相關(guān)研究使用到了詞匯[52]和語法[39]的方式用于研究,本文歸納的基于文本、詞匯、語法、語義的表征方式都可以作為輸入應(yīng)用于深度學(xué)習(xí)的檢測中,如何有效地將這些表征技術(shù)應(yīng)用到代碼克隆檢測中需要未來工作進一步分析與研究.

5.2.4 知識圖譜的技術(shù)也是解決類型4克隆檢測的手段之一

對于類型 4的代碼克隆來說,功能相同但是結(jié)構(gòu)不同是其主要的特點,這個特點背后的邏輯是它們都擁有相同的業(yè)務(wù)性或者系統(tǒng)性的知識,如果能夠建立起一個軟件系統(tǒng)的知識圖譜,就能夠幫助跨過符合類型 4定義的代碼克隆之間天然的語義鴻溝,自上而下地檢測編碼方式不同但是實現(xiàn)了相同功能或業(yè)務(wù)的不同粒度的源代碼.比如說,有研究將Java的API知識引入了代碼檢索領(lǐng)域[88],其主要思想是利用額外的API文檔作為知識庫提高檢索的準(zhǔn)確率,類似地,借助構(gòu)建的或已有的外部知識,可以增強對源代碼的表征能力,提高對類型4的代碼克隆檢測能力.解決實踐中的工程問題,推動代碼克隆的廣泛應(yīng)用.

在目前的技術(shù)中,代碼克隆檢測技術(shù)能夠?qū)︻愋?1到類型 3的代碼克隆的檢測有不錯的效果,但卻并不能完全應(yīng)用到工業(yè)界之中.首先,這些工具有自己的局限性,不能完全滿足第5.2節(jié)中提到的特性.其次,代碼克隆的相關(guān)問題在工業(yè)界的應(yīng)用場景中需要更多的實踐才能凸顯其價值,比如Dang等人[20]評估了XIAO[34]這一工具在微軟不斷迭代取得的成功:XIAO的主要成就在于集成到了Visual Studio并且在微軟開發(fā)團隊的日常運作中被廣泛使用.從中我們可以得到兩個方面的啟示:(1) 技術(shù)方面,在開發(fā)技術(shù)原型時要結(jié)合初步的調(diào)查,考慮到在實際中它們的使用情況(即使這樣的設(shè)想有時候不如預(yù)期),第二則是要考慮交互問題,第三是要考慮模型的效率和可靠性.(2) 社會方面,首先,對于目標(biāo)的用戶要有內(nèi)部知情人來幫助交互,從而能夠協(xié)調(diào)兩邊的信息;第二要能夠真誠地與生產(chǎn)團隊交互;第三是要有良好的反饋機制,幫助產(chǎn)品的迭代與優(yōu)化;第四是要有高效的協(xié)作處理過程;最后則是要能夠積極、主動地去尋找、拓展產(chǎn)品的領(lǐng)域.除此之外,一個科研原型的落地有兩種模式:pull模式和push模式,pull模式就是根據(jù)已有的問題來進行科研并提出解決方案;而push模式則是根據(jù)科研問題和初步調(diào)查,結(jié)合科研直覺開發(fā)出原型工具,并嘗試將原型進行“推銷”,在與早期使用者的交互中獲得更多反饋并加以改進.

6 總 結(jié)

代碼克隆對軟件系統(tǒng)的開發(fā)、維護產(chǎn)生一定程度的影響,其中負(fù)面影響包括降低軟件穩(wěn)定性、造成代碼庫的冗余和軟件缺陷的傳播.學(xué)術(shù)界對代碼克隆的研究有超過 20年的歷史,但是尚有許多問題,特別是代碼克隆的檢測問題需要研究.本文基于當(dāng)前研究進展,重新梳理歸納了代碼克隆檢測研究,也總結(jié)討論了當(dāng)前代碼克隆研究面臨的關(guān)鍵問題及未來發(fā)展趨勢.主要工作總結(jié)如下:(1) 從源代碼表征方式這種不同于以往研究該問題的角度闡述并歸類了現(xiàn)有的克隆檢測方法;(2) 總結(jié)了模型評估中使用的實驗驗證方法與性能評估指標(biāo);(3) 從科學(xué)性、實用性和技術(shù)難點3個方面歸納總結(jié)了代碼克隆研究的關(guān)鍵問題,圍繞數(shù)據(jù)標(biāo)注、表征方法、模型構(gòu)建和工程實踐4個方面,闡述了問題的可能解決思路和研究的未來發(fā)展趨勢.