張凡龍 蘇小紅 李智超 馬培軍

摘 要：克隆代碼是軟件中彼此相似的代碼片段。傳統(tǒng)觀點(diǎn)認(rèn)為克隆代碼是有害的，會(huì)降低軟件質(zhì)量，但最近研究發(fā)現(xiàn)克隆代碼不一定是有害的。如何評(píng)估克隆代碼的有害性是一個(gè)值得研究的問(wèn)題。本文提出了一種基于支持向量機(jī)的克隆代碼有害性評(píng)價(jià)方法，可以以較高的準(zhǔn)確性和查準(zhǔn)率評(píng)價(jià)其有害性。為驗(yàn)證方法有效性，本文在6個(gè)系統(tǒng)上進(jìn)行實(shí)驗(yàn)，結(jié)果表明本文方法可以有效地評(píng)價(jià)克隆代碼的有害性，并且所提出的靜態(tài)度量和演化度量對(duì)評(píng)價(jià)克隆代碼有效性具有積極意義。

關(guān)鍵詞：克隆代碼；克隆有害性評(píng)價(jià)；克隆度量；支持向量機(jī)；克隆演化

中圖分類(lèi)號(hào)：TP311.5 文獻(xiàn)標(biāo)識(shí)號(hào)：A文章編號(hào)：2095-2163（2015）06-

Abstract： Code clone （also known as duplicated code） has always been a popular research field in software engineering. Traditional view is that code clone is harmful， because clone can decrease the quality of software. However， considering the clone evolution， some studies find that not all the clones are harmful. So how to evaluate the clone harmfulness is a problem. This paper proposes a method which can evaluate the clone harmfulness based on support vectors machine， and makes several experiments on 6 open-source software system which were written in 3 kinds of programming languages. The results show that the proposed method has an applicability and higher accuracy. It is a meaningful attempt to evaluate the clone harmfulness.

Keywords： Code Clone； Harmfulness Evaluation； Clone Metrics； Support Vector Machine； Clone Evolution

0 引 言

克隆代碼是軟件系統(tǒng)中彼此相同或相似的代碼片段。大多數(shù)克隆代碼情況是通過(guò)拷貝粘貼活動(dòng)產(chǎn)生的[1]，編程語(yǔ)言局限、使用相似API和函數(shù)調(diào)用也會(huì)產(chǎn)生克隆代碼。在大型軟件系統(tǒng)中克隆代碼約占代碼總量的7-23%[2]。傳統(tǒng)觀點(diǎn)認(rèn)為克隆代碼是一種代碼壞味，意味著軟件質(zhì)量較差，可能會(huì)引入缺陷，需通過(guò)重構(gòu)消除克隆代碼[3-5]。有研究者使用克隆代碼信息進(jìn)行缺陷預(yù)測(cè)，如用歷史變化信息預(yù)測(cè)缺陷[6]，用克隆代碼上下文信息來(lái)預(yù)測(cè)缺陷[7]，用信息熵的概念來(lái)定義代碼變化復(fù)雜度來(lái)預(yù)測(cè)缺陷[8]。然而，通過(guò)對(duì)克隆演化模式的研究發(fā)現(xiàn)不是所有的克隆代碼都是有害的[9-12]。不足一半的克隆代碼在演化過(guò)程中發(fā)生變化，而導(dǎo)致額外維護(hù)開(kāi)銷(xiāo)的一致變化克隆比例則更少[13]，并且只有在少數(shù)情況下不一致變化而導(dǎo)致缺陷[14-15]。研究者將克隆代碼明確區(qū)分為有害和無(wú)害，采用啟發(fā)式方法映射多版本間克隆，提出并使用克隆氣味的概念幫助減少代碼中的潛在威脅[16-17]。有人使用貝葉斯網(wǎng)絡(luò)來(lái)預(yù)測(cè)克隆代碼的有害性[18]，可以評(píng)價(jià)克隆代碼的有害性，該方法具有一定啟發(fā)意義。

如何綜合考慮克隆代碼本身屬性及其演化過(guò)程建立克隆代碼有害性評(píng)價(jià)模型是亟待解決的問(wèn)題。為了解決該問(wèn)題，本文結(jié)合軟件度量、克隆代碼演化分析和機(jī)器學(xué)習(xí)方法，提取了克隆代碼靜態(tài)度量和演化度量，使用支持向量機(jī)建立克隆代碼有害性的評(píng)價(jià)模型，快速地識(shí)別出有害的克隆代碼，幫助開(kāi)發(fā)人員對(duì)克隆代碼進(jìn)行維護(hù)。

1 克隆代碼有害性分析

本文使用克隆家系和演化模式描述其演化過(guò)程?？寺∪菏悄骋粋€(gè)版本內(nèi)彼此相似的克隆片段集合，克隆家系是軟件所有的克隆群在演化過(guò)程中衍生的直系克隆的集合。一個(gè)克隆代碼屬于一個(gè)克隆群，一個(gè)克隆群屬于一個(gè)克隆家系。演化模式（Evolution Pattern，EP）是前一版本的克隆群與下一版本的新克隆群間的關(guān)系。無(wú)變化是新克隆群中相對(duì)于原克隆群沒(méi)發(fā)生任何變化；增加是新克隆群中至少增加了一個(gè)克隆代；減少是原克隆群中的至少一個(gè)克隆消失了；一致變化是原克隆群中所有的克隆發(fā)生同樣的變化，而且仍然屬于新克隆群；不一致變化是原克隆群中至少有一個(gè)克隆代碼片段發(fā)生了不一致地變化?？寺〖蚁等鐖D1所示，圖中描述了一個(gè)直系克隆的克隆代碼、克隆群和克隆家系在連續(xù)四個(gè)版本間的演化情況?？寺〗M在圖中第3個(gè)版本家系發(fā)生了分裂，一個(gè)新的克隆群出現(xiàn)了并在后續(xù)版本中繼續(xù)演化下去。

本文給出一種克隆害性定義。克隆代碼相關(guān)的缺陷是克隆代碼有害的最直觀表現(xiàn)，而克隆演化中的克隆群的不一致變化是導(dǎo)致缺陷的最重要原因，因此可利用克隆群的一致性變化來(lái)判定克隆有害性。根據(jù)是否發(fā)生一致性變化將克隆分為兩類(lèi)：

（1）克隆代碼連同其隸屬克隆群，在演化過(guò)程中從未發(fā)生過(guò)變化或一直發(fā)生不一致變化；

（2）克隆代碼連同其隸屬的克隆群，某一克隆片段發(fā)生變化，其它克隆片段并未改變。

對(duì)第一類(lèi)克隆，在開(kāi)發(fā)過(guò)程中不需要做一致性維護(hù)操作，可忽略其對(duì)程序的影響認(rèn)為是無(wú)害的。對(duì)第二類(lèi)克隆，每一次一致性修改操作都導(dǎo)致額外維護(hù)開(kāi)銷(xiāo)，而遺忘一致性修改會(huì)導(dǎo)致克隆群的不一致變化，會(huì)引入缺陷。從而認(rèn)為第二類(lèi)克隆代碼是有害的。根據(jù)克隆演化情況，給出克隆代碼有害性的定義：設(shè)在版本 中的克隆代碼片段 ，且 隸屬于克隆群 ，即 ，克隆群 從版本 至 的演化模式序列EP， ，其中 表示克隆群從第i-1版本到第i版本的演化模式，則克隆代碼片段 的有害性H為：

2克隆代碼有害性評(píng)價(jià)方法

2.1有害性評(píng)價(jià)模型

本文采用機(jī)器學(xué)習(xí)方法來(lái)評(píng)價(jià)克隆代碼有害性，該方法將問(wèn)題看成一個(gè)機(jī)器學(xué)習(xí)中的分類(lèi)問(wèn)題，通過(guò)算法訓(xùn)練已知樣本來(lái)對(duì)未知的樣本即克隆代碼片段進(jìn)行分類(lèi)。基于支持向量機(jī)的有害性評(píng)價(jià)模型可分為三個(gè)步驟：預(yù)處理、數(shù)據(jù)集生成和有害性評(píng)價(jià)，具體則如圖2所示。

由圖2可知，模型中各部分的功能實(shí)現(xiàn)分析可概述如下：

（1）預(yù)處理。檢測(cè)軟件克隆代碼，進(jìn)行克隆群映射并構(gòu)建克隆家系，獲得克隆演化模式；

（2）數(shù)據(jù)集生成。從預(yù)處理結(jié)果中提取克隆代碼的度量值，包括靜態(tài)度量和演化度量，根據(jù)演化模式序列進(jìn)行有害性標(biāo)注，獲得支持向量機(jī)的數(shù)據(jù)集。

（3）有害性評(píng)價(jià)。使用支持向量機(jī)模型在數(shù)據(jù)集上訓(xùn)練評(píng)價(jià)模型，并在測(cè)試集上測(cè)試模型的有效性。

2.2預(yù)處理

首先，獲取連續(xù)多個(gè)版本的開(kāi)源軟件源代碼，并使用NiCad工具對(duì)系統(tǒng)每一個(gè)版本都進(jìn)行克隆代碼檢測(cè)，同時(shí)在此基礎(chǔ)上本文使用克隆描述符描述克隆代碼，包含了克隆代碼的其它基本信息，再將結(jié)果保存于xml文件中后，則根據(jù)檢測(cè)結(jié)果映射相鄰版本的克隆代碼和克隆群，生成克隆群映射文件和克隆家系文件?？寺∪河成湮募邪讼噜彴姹镜乃锌寺∪旱挠成浜脱莼P(guān)系，包括演化模式?？寺〖蚁滴募t給出了該軟件中所有克隆家系以及詳細(xì)信息。

2.3 數(shù)據(jù)集生成

克隆代碼片段無(wú)法作為支持向量機(jī)的輸入，為向其提供數(shù)據(jù)集樣本，同時(shí)也可以充分地表示克隆代碼有害性信息，本文提取靜態(tài)度量和演化度量?jī)山M度量值表示克隆代碼。在此基礎(chǔ)上生成表示克隆代碼的向量，并根據(jù)其演化模式對(duì)其進(jìn)行有害性標(biāo)注獲得本文的數(shù)據(jù)集。

靜態(tài)度量是指僅通過(guò)單一版本的分析即可提取的克隆代碼特征?？梢詮念A(yù)處理的輸出文件進(jìn)行提取，預(yù)處理使用改進(jìn)的克隆代碼描述符表示克隆代碼，該文件包含了克隆代碼幾乎所有的靜態(tài)屬性。具體來(lái)說(shuō)，分別是：

（1）克隆粒度。克隆代碼片段的代碼行數(shù)。

（2）文件分布。研究表明分布在不同文件中的克隆代碼更易于被開(kāi)發(fā)人員疏忽而產(chǎn)生缺陷?？寺〈a的文件分布情況會(huì)影響克隆代碼的有害性。

（3）克隆相似度。是克隆群內(nèi)克隆代碼之間的相似度。

（4）上下文信息。完整包含該克隆片段的最近控制結(jié)構(gòu)語(yǔ)句（條件分支、函數(shù)定義、循環(huán)等）。

（5）參數(shù)個(gè)數(shù)?？寺〈a片段中函數(shù)包含的參數(shù)個(gè)數(shù)，體現(xiàn)著代碼間的耦合度、函數(shù)體復(fù)雜性等。

（6）Halstead度量。從詞法角度上表征克隆代碼的復(fù)雜情況，共有13個(gè)Halstead度量，其實(shí)際對(duì)應(yīng)內(nèi)容為：不同操作符個(gè)數(shù)、不同操作數(shù)個(gè)數(shù)、所有操作符出現(xiàn)次數(shù)、所有操作數(shù)出現(xiàn)次數(shù)、程序詞匯量、程序長(zhǎng)度、計(jì)算程序長(zhǎng)度、容量、難度、精力、程序時(shí)間、交付錯(cuò)誤數(shù)量。

演化度量描述了克隆代碼的演化屬性，表示克隆的演化過(guò)程。克隆代碼的演化特征從預(yù)處理中映射文件與克隆家系文件中提取，克隆群映射文件包含了相鄰版本間克隆群和克隆代碼的映射關(guān)系。包括：

（1）克隆壽命。壽命較長(zhǎng)的克隆大多數(shù)都是無(wú)變化克隆，壽命較長(zhǎng)的克隆長(zhǎng)期存在于系統(tǒng)中，通常表明是無(wú)害的。克隆代碼壽命可以反映克隆代碼有害性。

（2）變化復(fù)雜度。為克隆代碼在歷史版本中經(jīng)歷的改變次數(shù)。本文選擇兩種變化復(fù)雜度：整體版本周期中該克隆代碼片段經(jīng)歷改變次數(shù)與近1/2版本周期中該克隆代碼片段經(jīng)歷改變次數(shù)。前者是歷史整體變化次數(shù)在調(diào)整參數(shù)階段。

度量值提取完成后，即獲得了克隆代碼有害性評(píng)價(jià)的數(shù)據(jù)集。支持向量機(jī)是有監(jiān)督學(xué)習(xí)算法，需對(duì)數(shù)據(jù)集進(jìn)行有害性標(biāo)注，需通過(guò)人工行為將樣本劃分為有害或者無(wú)害，獲得最后數(shù)據(jù)集。有害性的標(biāo)注是依據(jù)有害性定義進(jìn)行標(biāo)注，根據(jù)克隆家系文件中演化模式人工標(biāo)記所有的克隆代碼是否有害，獲得數(shù)據(jù)集。

2.4有害性評(píng)價(jià)

使用支持向量機(jī)在數(shù)據(jù)集訓(xùn)練評(píng)價(jià)模型，并進(jìn)行有害性評(píng)價(jià)給出克隆代碼有害性結(jié)果。將數(shù)據(jù)集劃分為訓(xùn)練集和測(cè)試集：將軟件系統(tǒng)中前4/5個(gè)周期版本的克隆代碼用作訓(xùn)練集，后1/5個(gè)周期版本作測(cè)試集。使用SVM模型對(duì)其進(jìn)行訓(xùn)練，經(jīng)過(guò)交叉驗(yàn)證、調(diào)整參數(shù)等過(guò)程建立基于SVM的克隆代碼有害性評(píng)價(jià)模型，為了對(duì)SVM模型的性能進(jìn)行比較，同時(shí)加入了邏輯回歸模型。

3 實(shí)驗(yàn)結(jié)果與結(jié)論分析

3.1實(shí)驗(yàn)設(shè)置

本文使用六個(gè)開(kāi)源軟件作為實(shí)驗(yàn)系統(tǒng)，系統(tǒng)信息如表1所示。DNSJava是Java語(yǔ)言實(shí)現(xiàn)的DNS協(xié)議，jEdit是Java語(yǔ)言實(shí)現(xiàn)的面向軟件開(kāi)發(fā)的文本編譯器，wget是C語(yǔ)言實(shí)現(xiàn)的命令行下載工具，conky是C語(yǔ)言實(shí)現(xiàn)的用于X視窗系統(tǒng)的系統(tǒng)監(jiān)視器，ProcessHacker是C#實(shí)現(xiàn)的windows系統(tǒng)進(jìn)程管理程序，itextsharp是C#實(shí)現(xiàn)的用來(lái)生成PDF文檔庫(kù)。

本文使用臺(tái)灣大學(xué)林智仁教授開(kāi)發(fā)的支持向量機(jī)工具包LibSVM 3.14，核函數(shù)選擇高斯核函數(shù)，在訓(xùn)練時(shí)調(diào)整懲罰因子 和高斯核函數(shù)的均方差 ，在訓(xùn)練集上執(zhí)行10-交叉驗(yàn)證。分類(lèi)器的分類(lèi)情況可以用混合矩陣表示（如表2）：實(shí)際正例P，實(shí)際反例N，實(shí)際正例數(shù) ，實(shí)際反例數(shù) ，實(shí)例總數(shù) 。根據(jù)混合矩陣，本文使用查準(zhǔn)率、查全率、F值作為評(píng)價(jià)本文方法的指標(biāo)。查準(zhǔn)率為 。查全率為 。F值為 ，是查準(zhǔn)率和查全率的綜合指標(biāo)，越高說(shuō)明效果越好。

3.2實(shí)驗(yàn)結(jié)果

實(shí)驗(yàn)結(jié)果如表3所示。表3第6列是本文使用支持向量機(jī)的有害性評(píng)價(jià)結(jié)果。從表中可以看出，本文方法具有較高的查準(zhǔn)率和查全率。全部6個(gè)系統(tǒng)的查準(zhǔn)率都比較高，其中DNSJava、wget以及conky實(shí)驗(yàn)的查準(zhǔn)率超過(guò)90%，JEdit和Proc超過(guò)了81%，查準(zhǔn)率達(dá)到了較高的性能。同時(shí)，6個(gè)系統(tǒng)查全率也具有較好的結(jié)果，其中DNSJava最高達(dá)到93.75%，wget次之則達(dá)85%。

表3的第6和7列是支持向量機(jī)和邏輯回歸方法的對(duì)比實(shí)驗(yàn)，結(jié)果表明支持向量機(jī)實(shí)驗(yàn)結(jié)果明顯優(yōu)于邏輯回歸的實(shí)驗(yàn)結(jié)果。除Proc的查準(zhǔn)率之外，支持向量機(jī)在6個(gè)系統(tǒng)上的查準(zhǔn)率、查全率和F值均高于邏輯回歸模型。表3的第3～6列是特征組對(duì)比實(shí)驗(yàn)，結(jié)果表明全部特征結(jié)果明顯優(yōu)于特征組合結(jié)果。首先是無(wú)內(nèi)容組的對(duì)比。所有查全率和查全率值均低于全部特征組，表明內(nèi)容組的度量值有積極作用。然后是無(wú)內(nèi)容組的對(duì)比。除conky在查全率高于全部特征之外，6個(gè)系統(tǒng)的無(wú)容量組的查全率和查全率值均低于全部特征組，同樣也表明內(nèi)容組的度量值有積極作用。最后是無(wú)演化組的對(duì)比。JEdit、conky和iTextsharp無(wú)演化組的查全率和查全率值均低于全部特征組，也可以說(shuō)明同樣問(wèn)題；DNSJava的查全率相近，但查準(zhǔn)率卻遠(yuǎn)低于全部組；wget和Proc情況類(lèi)似，查準(zhǔn)率稍微高于全部特征組，但查全率卻遠(yuǎn)低于全部特征組；這表明演化度量同樣具有積極的影響。

實(shí)驗(yàn)的F值如圖3所示。從圖中可以看出，各個(gè)系統(tǒng)的全部屬性組的F值最高，說(shuō)明本文提出的各種度量對(duì)有害性評(píng)價(jià)都有積極的影響。而無(wú)演化組F值最低，說(shuō)明演化度量對(duì)有害性評(píng)價(jià)結(jié)果的影響最大。綜上，本文的度量值對(duì)有害性評(píng)價(jià)都具有積極影響，演化組作用尤為突出，容量組和內(nèi)容組作用次之。

4 結(jié)束語(yǔ)

本文提出了基于支持向量機(jī)的克隆代碼有害行性評(píng)價(jià)方法，在6個(gè)軟件上進(jìn)行了實(shí)驗(yàn)表明該方法可以以較高的準(zhǔn)確率評(píng)價(jià)克隆代碼的有害性。提出一種基于演化的有害性評(píng)價(jià)標(biāo)準(zhǔn)：克隆代碼在生命周期內(nèi)發(fā)生過(guò)不一致性變化即是有害的。經(jīng)實(shí)驗(yàn)驗(yàn)證該評(píng)價(jià)標(biāo)準(zhǔn)具有一定的可信性，可以指導(dǎo)克隆代碼有害性評(píng)價(jià)。特征組對(duì)比試驗(yàn)中其實(shí)際結(jié)果表明本文所提出克隆代碼度量可以有效地評(píng)價(jià)克隆代碼的有害性，所提取的度量值可以表示克隆代碼信息?？疾霧值實(shí)驗(yàn)發(fā)現(xiàn)，演化度量在評(píng)價(jià)克隆代碼有害性方面的作用尤為突出，說(shuō)明了克隆代碼的演化對(duì)克隆代碼的維護(hù)有指導(dǎo)意義。

參考文獻(xiàn)：

[1] THUMMALAPENTA S， CERULO L， AVERSANO L， et al. An empirical study on the maintenance of source code clones[J]. Empirical Software Engineering. 2010，15（1）： 1-34

[2] ROY C K， CORDY JR， KOSCHKE R. Comparison and evaluation of code clone detection techniques and tools： A qualitative approach[J]. Science of Computer Programming. 2009，74： 470-495

[3] CHOI E， YOSHIDA N， ISHIO T， et al. Extracting code clones for refactoring using combinations of clone metrics[C]//Proceedings of the 5th International Workshop on Software Clones， New York， USA： ACM， 2011： 7-13.

[4] BOUKTIF S， ANTONIOL G， MERLO E， et al. A novel approach to optimize clone refactoring activity[C]//Proceedings of the 8th annual conference on Genetic and evolutionary computation， New York， USA： ACM， 2006： 1885-1892.

[5] BALAZINSKA M， MERLO E， DAGENAIS M， et al. Advanced clone-analysis to support object-oriented system refactoring[C]//Reverse Engineering， 2000. Proceedings. Seventh Working Conference on， Brisbane： IEEE， 2000： 98-107.

[6] GRAVES T L， KARR A F， MARRON J S， et al. Predicting fault incidence using software change history[J]. Software Engineering， IEEE Transactions on， 2000， 26（7）： 653-661.

[7] JIANG L， SU Z， CHIU E. Context-based detection of clone-related bugs[C]// Proceedings of the the 6th joint meeting of the European software engineering conference and the ACM SIGSOFT symposium on The foundations of software engineering，New York： ACM， 2007： 55-64.

[8] Hassan A E. Predicting faults using the complexity of code changes[C]// Proceedings of the 31st International Conference on Software Engineering，Washington： IEEE Computer Society， 2009： 78-88.

[9] AVERSANO L， CERULO L， DI P M. How clones are maintained： An empirical study[C]// Software Maintenance and Reengineering， 2007. CSMR'07. 11th European Conference on，Amsterdam： IEEE， 2007： 81-90.

[10] G?DE N， KOSCHKE R. Frequency and risks of changes to clones[C]//Proceedings of the 33rd International Conference on Software Engineering， New York， USA： ACM， 2011： 311-320.

[11] THUMMALAPENTA S， CERULO L， AVERSANO L， et al. An empirical study on the maintenance of source code clones[J]. Empirical Software Engineering. 2010，15（1）： 1-34

[12] Cai D， Kim M. An empirical study of long-lived code clones[M]// Mauro Pezzè：Fundamental approaches to software engineering. Berlin Heidelberg ： Springer ， 2011： 432-446.

[13] BETTENBURG N， SHANG W， IBRAHIM W M， et al. An empirical study on inconsistent changes to code clones at the release level[J]. Science of Computer Programming， 2012， 77（6）： 760-776.

[14] BAKOTA T， FERENC R， GYIMOTHY T. Clone smells in software evolution[C]//Software Maintenance， 2007. ICSM 2007. IEEE International Conference on，Paris： IEEE， 2007： 24-33.

[15] KIM M， SAZAWAL V， NOTKIN D， et al. An empirical study of code clone genealogies[C]//ACM SIGSOFT Software Engineering Notes，New York， NY， USA： ACM， 2005， 30（5）： 187-196.

[16] G?DE N， HARDER J. Clone stability[C]//Software Maintenance and Reengineering （CSMR）， 2011 15th European Conference on，Oldenburg： IEEE， 2011： 65-74.

[17] KAPSER C， GODFREY M W. " Cloning considered harmful" considered harmful[C]//Reverse Engineering， 2006. WCRE'06. 13th Working Conference on，Benevento： IEEE， 2006： 19-28.

[18] WANG X， DANG Y， ZHANG L， et al. Can I clone this piece of code here？[C]//Proceedings of the 27th IEEE/ACM International Conference on Automated Software Engineering， New York， USA： ACM， 2012： 170-179.

[19] CORTES C， VAPNIK V. Support vector machine[J]. Machine learning， 1995， 20（3）： 273-297.