基于支持向量機的克隆代碼有害性評價方法

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

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

關鍵詞：克隆代碼；克隆有害性評價；克隆度量；支持向量機；克隆演化

中圖分類號：TP311.5 文獻標識號：A文章編號：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ù)克隆代碼情況是通過拷貝粘貼活動產生的[1]，編程語言局限、使用相似API和函數(shù)調用也會產生克隆代碼。在大型軟件系統(tǒng)中克隆代碼約占代碼總量的7-23%[2]。傳統(tǒng)觀點認為克隆代碼是一種代碼壞味，意味著軟件質量較差，可能會引入缺陷，需通過重構消除克隆代碼[3-5]。有研究者使用克隆代碼信息進行缺陷預測，如用歷史變化信息預測缺陷[6]，用克隆代碼上下文信息來預測缺陷[7]，用信息熵的概念來定義代碼變化復雜度來預測缺陷[8]。然而，通過對克隆演化模式的研究發(fā)現(xiàn)不是所有的克隆代碼都是有害的[9-12]。不足一半的克隆代碼在演化過程中發(fā)生變化，而導致額外維護開銷的一致變化克隆比例則更少[13]，并且只有在少數(shù)情況下不一致變化而導致缺陷[14-15]。研究者將克隆代碼明確區(qū)分為有害和無害，采用啟發(fā)式方法映射多版本間克隆，提出并使用克隆氣味的概念幫助減少代碼中的潛在威脅[16-17]。有人使用貝葉斯網絡來預測克隆代碼的有害性[18]，可以評價克隆代碼的有害性，該方法具有一定啟發(fā)意義。

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

1 克隆代碼有害性分析

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

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

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

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

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

2克隆代碼有害性評價方法

2.1有害性評價模型

本文采用機器學習方法來評價克隆代碼有害性，該方法將問題看成一個機器學習中的分類問題，通過算法訓練已知樣本來對未知的樣本即克隆代碼片段進行分類?；谥С窒蛄繖C的有害性評價模型可分為三個步驟：預處理、數(shù)據(jù)集生成和有害性評價，具體則如圖2所示。

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

（1）預處理。檢測軟件克隆代碼，進行克隆群映射并構建克隆家系，獲得克隆演化模式；

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

（3）有害性評價。使用支持向量機模型在數(shù)據(jù)集上訓練評價模型，并在測試集上測試模型的有效性。

2.2預處理

首先，獲取連續(xù)多個版本的開源軟件源代碼，并使用NiCad工具對系統(tǒng)每一個版本都進行克隆代碼檢測，同時在此基礎上本文使用克隆描述符描述克隆代碼，包含了克隆代碼的其它基本信息，再將結果保存于xml文件中后，則根據(jù)檢測結果映射相鄰版本的克隆代碼和克隆群，生成克隆群映射文件和克隆家系文件。克隆群映射文件中包含了相鄰版本的所有克隆群的映射和演化關系，包括演化模式?？寺〖蚁滴募t給出了該軟件中所有克隆家系以及詳細信息。

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

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

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

（1）克隆粒度?？寺〈a片段的代碼行數(shù)。

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

（3）克隆相似度。是克隆群內克隆代碼之間的相似度。

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

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

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

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

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

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

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

2.4有害性評價

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

3 實驗結果與結論分析

3.1實驗設置

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

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

3.2實驗結果

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

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

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

4 結束語

本文提出了基于支持向量機的克隆代碼有害行性評價方法，在6個軟件上進行了實驗表明該方法可以以較高的準確率評價克隆代碼的有害性。提出一種基于演化的有害性評價標準：克隆代碼在生命周期內發(fā)生過不一致性變化即是有害的。經實驗驗證該評價標準具有一定的可信性，可以指導克隆代碼有害性評價。特征組對比試驗中其實際結果表明本文所提出克隆代碼度量可以有效地評價克隆代碼的有害性，所提取的度量值可以表示克隆代碼信息?？疾霧值實驗發(fā)現(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.