克隆代碼有害性預測中的特征選擇模型

王 歡,張麗萍,閆 盛,劉東升

內蒙古師范大學 計算機與信息工程學院,呼和浩特 010022)(*通信作者電子郵箱cieczlp@imnu.edu.cn)

克隆代碼有害性預測中的特征選擇模型

王 歡,張麗萍*,閆 盛,劉東升

內蒙古師范大學 計算機與信息工程學院,呼和浩特 010022)(*通信作者電子郵箱cieczlp@imnu.edu.cn)

為解決克隆代碼有害性預測過程中特征無關與特征冗余的問題,提出一種基于相關程度和影響程度的克隆代碼有害性特征選擇組合模型。首先,利用信息增益率對特征數據進行相關性的初步排序;然后,保留相關性排名較高的特征并去除其他無關特征,減小特征的搜索空間;接著,采用基于樸素貝葉斯等六種分類器分別與封裝型序列浮動前向選擇算法結合來確定最優特征子集。最后對不同的特征選擇方法進行對比分析,將各種方法在不同選擇準則上的優勢加以利用,對特征數據進行分析、篩選和優化。實驗結果表明,與未進行特征選擇之前對比發現有害性預測準確率提高15.2～34個百分點以上；與其他特征選擇方法比較,該方法在F1測度上提高1.1～10.1個百分點,在AUC指標上提升達到0.7～22.1個百分點,能極大地提高有害性預測模型的準確度。

克隆代碼;有害性預測;特征子集;信息增益率;特征選擇

0 引言

克隆代碼(Clone Code)是源代碼的一段拷貝或者重用,在軟件實踐開發中是一種非常普遍的現象[1]。由于克隆代碼對代碼質量的重要影響, 克隆代碼相關研究是代碼分析領域近年來一個非?；钴S的研究分支[2]。在發布軟件正式版本之前,提前找出隱含的有害克隆代碼,并反饋給開發維護人員，以便于他們及時修正由克隆引起的錯誤,提高代碼質量削減維護費用,增強軟件的可理解性和可靠性。而在有害性預測過程中,選擇克隆代碼有害性特征的優劣決定了整個預測過程的效果。

目前,研究人員已經進行了克隆代碼有害性預測的探索[3-6],已有從不同角度的多種特征度量被提出,并用于克隆代碼有害性自動預測研究中。但是對于不同的特征以及特征之間的影響關系缺乏較為全面的分析。例如,其中可能存在不相關和相互依賴的特征,導致訓練模型所需的時間加長,模型較復雜并且學習效果也會下降。因此,如果能對克隆代碼特征之間的相關程度和冗余程度進行更全面的分析,對表征有害性的特征進行優化與評估,將有利于提高克隆代碼有害性預測的性能與效果。

本文以解決克隆代碼中特征無關與特征冗余的問題,提高有害性預測性能為目標，將基于機器學習的自然語言處理中特征選擇方法引入克隆代碼有害性特征選擇當中,從特征數據自身的相關性以及對預測結果的影響程度兩個角度出發,基于信息增益率(Information Gain Ratio, IGR)和序列浮動前向選擇模型(Sequential Floating Forward Selection Model, SFFSM),提出一種混合式克隆代碼有害性特征選擇模型—— IGR-SFFSM。實驗結果表明本文方法能有效降低特征選擇對有害性預測的影響：一方面,該方法在時間效率和準確度方面表現更優,從而能達到優化特征空間,提高有害性預測準確度的目的；另一方面,選擇出4～5個真正相關的特征簡化了模型,使研究者更容易理解數據產生的過程。

1 相關工作

1.1 克隆代碼有害性定義

目前,對于克隆代碼的有害性界定非常模糊,相關的有害性預測研究中,也沒有一個標準的有害性界定范圍，因此,關于克隆代碼有害性方面的研究相對較少。

Wang等[3]通過收集克隆代碼的屬性特征及要粘貼的目標區域的上下文特征進行學習,預測克隆操作的有害性。李智超[4]基于機器學習中有監督學習方法支持向量機進行了克隆代碼有害性評價方法的研究。該研究認為“一致變化”的代碼是有害的,而國外大多數研究者們則認為“不一致變化”才是引起程序出錯的主要原因。例如Inoue等[7]研究發現通過檢測手機軟件中克隆代碼的不一致變化能有效地找出軟件中潛伏的bug。Juergens等[8]對四個系統的研究結果進行報告,發現克隆代碼中52%會發生不一致變化,28%的不一致變化被無意地引入,15%的不一致變化會引入錯誤,50%的無意不一致變化會導致程序錯誤。該研究同時也表明,幾乎任何對克隆代碼不經意的不一致修改,都可能會隱藏著一個bug。德國的Steidl等[9]使用機器學習領域的決策樹自動識別軟件的bug,他們認為無意的不一致修改是導致有害克隆的原因。國內外的大量研究都認為克隆代碼不一致變化非常頻繁并且大量的程序錯誤都是由這種不一致變化引起的。

圖1是不一致的bug修復引發錯誤的例子,代碼1和代碼2已經被檢測出是一對克隆代碼。從圖1可以看出,第一對克隆代碼(#1)中,代碼1的代碼片段中strncmp接收三個參數,而代碼2的片段中strcmp只接收兩個參數。明顯在#1代碼2中存在一個邏輯錯誤。 第二對克隆代碼(#2)在變量命名上發生了不一致變化,#2左邊代碼中if條件對l_stride進行了空判斷,右邊代碼確并沒有對r_stride進行一個空值的檢測并且已經被GCC開發人員證實是一個需要快速修復的bug。

圖1 不一致的bug修復引發錯誤

不一致變化是指克隆類中的某個克隆片段發生了和其他片段不一樣的變化。不一致性檢驗是將源代碼轉換成Token表示形式,再利用最長公共子序列算法計算兩段克隆代碼Token序列之間的相似程度。算法實質就是基于文本的字符匹配算法與一般的基于字符對比算法的區別是能夠不受字符重命名、數據類型不同以及程序語言不同的影響。

結構化的不一致問題屬于克隆代碼領域中的Type-4類型,而Type-4 克隆代碼則為功能相似或相同,但句法結構不同的代碼段,目前國內外對Type-4克隆代碼檢測的研究僅處于探索階段,無法獲取,因此結構化不一致問題不作為本文研究內容。

最終本文將發生不一致變化的克隆代碼標注為有害克隆代碼,如果克隆群經歷了至少一次不一致變化,本文就認為這種克隆操作是有害的。如果克隆群經歷無變化或者一致性修改變化,本文認為這種克隆操作就是無害的。對克隆代碼進行修改時,需要對克隆群內所有克隆代碼作一致性修改,而遺漏群內任何代碼的一致性修改操作都會導致克隆群中發生不一致改變,這會導致程序出現錯誤,進而給軟件系統帶來隱含的bug。

1.2 特征選擇

特征選擇作為機器學習和模式識別領域中非常重要的數據預處理技術,在有害性預測中扮演著重要角色。而特征選擇的焦點是如何從輸入數據中選擇一個變量的子集,使這個子集能在有效描述輸入數據特性的同時也能減少一些不相關變量的噪聲干擾,最終達到提高預測結果準確的目的[10]。

評價標準在特征選擇過程中也扮演著重要的角色,它是特征選擇的依據。評價標準可以分為兩種:一種是用于單獨地衡量每個特征的預測能力的評價標準,用來衡量每個特征與輸出類別標簽之間的相關性;另一種是用于評價某個特征子集整體預測性能的標準。根據特征子集選擇過程中是否依賴于后續的學習分類方法來評價,可以將其具體分為過濾式(Filter)方法[11]和封裝型(Wrapper)方法[12]共兩大類。

Filter方法是采用一些基于信息統計的啟發式準則來評價特征的預測能力。例如,Guyon等[10]提出采用相關系數對特征進行排序。該研究對特征數據進行預處理,過濾掉排名等級較低的特征變量,最終把相關程度高的特征提供給機器學習模型使用,從而提高預測的效果。Menzies等[13]使用信息增益對特征進行排序,他們的結論發現使用前3個特征和使用全部特征的預測效果相差無幾。目前用得最多的評價準則有相關系數法、類間與類內距離測量法、信息熵法、信息增益率、一致性、Relief等。

Wrapper方法是根據一些搜索策略來選擇特征子集,并測試它在分類器上的性能表現來決定特征子集的優劣。當前搜索特征子集的算法分為完全搜索、啟發式搜索、隨機搜索三大類。常用的搜索算法有基于深度優先局部擇優的爬山算法、最好優先算法、基于枚舉加剪枝的分支限界搜索和遺傳算法等。當前有K近鄰、隨機森林、神經網絡、支持向量機等作為分類器。Kohavi等[14]使用啟發式特征選擇方法爬山算法,通過分析大類訓練結果來啟發式的重新組合特征,最終找到結果最好的特征子集。Janecek等[15]使用貪心加回溯的最好優先算法,搜索出最好的屬性空間子集,在特征減少90%以上的情況下,六種學習算法平均預測性能幾乎保持不變。

通過對上述方法的總結與分析可以發現:Filter方法獨立于后續的分類方法并且避免了Wrapper方法交叉驗證的過程，所以它是一種計算效率較高的方法且不依賴具體的學習算法來評價特征子集。但其主要問題是當特征和分類器關聯較大時,不一定找到規模較小的最優特征子集。例如Relief中的相關性方法使用樸素貝葉斯作為特征子集選擇器就不合適,因為在大多數情況下樸素貝葉斯提高表現是伴隨著相關特征的移除[10]。雖然Wrapper方法的效率不及Filter,但該方法使用一個預定義的分類器來評估特征質量并有效避免了特征選擇時依賴具體分類方法的缺點,同時所選的優化特征子集的規模相對要小一些。然而,這種方法需要多次運行分類器來評估選擇的特征子集,所以計算開銷較高。

因此,本文方法與上述方法主要不同之處有以下三點:

1)大多數基于機器學習的克隆代碼有害性特征的選擇都依賴于研究者或開發者的經驗。而本文提出了一種有害性特征選擇的理論模型,此模型以特征相關程度和模型預測的結果分析為依據選擇特征數據,為克隆代碼有害性預測方面的研究提供了更加科學和客觀的數據支持。

2)將特征選擇方法引入克隆代碼有害性預測研究當中,利用Filter方法計算開銷較小以及Wrapper方法與分類器模型交互的優點,提出一種折中的方法,用前者作為分類的預選器,后者在預選特征集上作進一步的特征精選。實驗中采用信息增益率和序列浮動前向選擇算法確定最優特征子集。通過訓練特征數據集選擇前后的預測表現進行評估,發現準確率、F1測量和AUC都有明顯提升,證明了該方法的可行性。

3)將基于機器學習的自然語言處理中特征選擇方法引入克隆代碼有害性特征選擇當中,利用一般特征選擇方法處理形式化語言高效、準確的優勢,針對克隆代碼有害性特征數量多且不容易提取,質量粗糙的問題,提出一種有效的優化特征子集的方法,進而提高學習模型的性能。

2 IGR-SFFSM方法

本文提出的用于預測有害克隆代碼的組合特征選擇方法框架如圖2所示。在既有的克隆檢測、克隆家系和克隆有害性預測的研究基礎上,針對克隆代碼有害性預測過程中特征選擇這一核心問題展開深入研究。結合克隆代碼本身的靜態信息和克隆演化信息,提出兩大類有害性特征指標即靜態特征和演化特征。然后,進行有害性標注,由此形成原始特征數據集。在此基礎上,使用組合特征選擇方法構建特征選擇模型。首先通過信息增益率計算特征之間的相關程度,獲得特征相關性排名結果,過濾掉相關程度較低的特征。然后利用序列浮動前向選擇算法對初步篩選出來的特征進行最優特征子集的搜索。最后采用基本模型和集成模型兩大類分類器作為克隆代碼有害性評價的測試模型,將篩選出來的特征子集輸入模型進行影響程度的循環測試,找到對預測結果影響程度最高的特征子集。

圖2 IGR-SFFSM模型框架

2.1 特征評估指標——信息增益率

IGR-SFFSM方法使用信息論中的信息增益率來衡量每個特征給分類過程中所帶來的信息量大小。若特征信息增益率越大,則說明該特征與分類標簽之間的相關性越大,即特征區分所有類的能力越強。因此,在進行屬性選擇的過程中,通常選擇信息增益率大的特征作為分類的依據。

設訓練集S={S1,S2,…,Sn},其中Si包含一個屬性向量Xi=(x1,x2,…,xp)及分類標簽Li∈={L1,L2,…,Lm}。在預測中Xi和Li分別代表一個樣本數據的屬性和該樣本是否存在有害克隆的標記。設pi是S中屬于類別Li的比例,則信息熵的計算方法如式(1)所示:

(1)

每個屬性可以有多個不同的取值,假設Values(A)是屬性A中取不同值的集合,Sv指集合S中的所有屬性A取值為v的集合,則式(2)表示基于按A劃分后對S集合準確分類還需要的信息量。

(2)

定義IG(A)表示屬性A的信息增益,式(3)是未進行特征選擇劃分之前的數據熵與按照屬性A劃分之后數據熵的差值:

IG(A)=Entropy(S)-Entropy(S,A)

(3)

如果S和A是相互獨立的,IG(A)將會是0;如果大于0說明它們是相互依賴的。這個算法就是在針對特征數據劃分前后信息儲量發生的變化,這種變化稱為信息增益。計算出特征數據的信息增益,可以描述每個特征獨立提供信息的能力。一般情況下,信息增益最高的特征就是最好的特征選擇。

由于克隆代碼有害性特征數據的離散性質,僅考慮信息增益的值進行特征選擇,很可能會導致過度擬合。此外,信息增益作為分類選擇標準也存在不足之處，即易偏向于取值較多的屬性,會極大地降低分類精度?；谝陨峡紤],本文選擇信息增益率來作為特征評估指標,故引入了內在信息I(Intrinsic Information),它表示了訓練集S用A劃分后的數據S′繼續劃分所期望的信息總量,如式(4)所示:

(4)

那么就可以最終獲得特征屬性A的信息增益率,定義如下:

IGR(A)=IG(A)/I(A)

(5)

信息增益率作為一種補償措施解決了信息增益所存在的問題。通過信息增益率可以對特征進行相關性的初步排序,進而對原始數據集進行了降維且利于選擇出最優屬性子集。

2.2 特征選擇方法

本文針對的是Type-1和Type-2型的克隆代碼,檢測之后可以生成克隆代碼的基本信息,例如克隆行數、代碼位置、克隆相似度等,從這些基本信息中可以獲取克隆代碼的一些靜態特征;之后,在軟件多版本之間進行克隆群映射以及克隆家系的構建,又可以從某款軟件的長期演化歷史中分析這些克隆的發展情況,例如克隆壽命等動態演化特征。得到的這兩種特征就是一個初始的特征集合。

IGR-SFFSM方法分為兩個步驟:首先采用信息增益率對初始特征集合中的特征進行相關程度的排序,過濾掉排名靠后的特征,生成候選特征樣本集合;然后采用序列浮動前向選擇算法從候選特征子集中選出新特征集,并使用六種常用的學習算法進行分類預測,保留分類效果較好的特征子集,迭代測試并最終得到最優特征子集。代碼的數量級不同不會影響IGR-SFFSM方法,但最終選出的特征會有所不同。因為數量增加之后,不同特征的量化會發生變化，例如代碼行數、分支語言以及圈復雜度等都會發生變化。

2.2.1 生成候選特征集合

生成候選特征子集的偽代碼如算法1所示,主要包括兩個部分:第一部分(第1)～8)行)計算Entropy(S)和Entropy(S,A)進而計算出IG(A)和I(A),最終得到信息增益率IGR(A);第二部分(第9)～13)行)把上一步計算出的IGR(A)作為字典的值,特征A作為鍵存入一個字典,并對字典按值進行降序排序,從而篩選出排名靠前的特征并放入特征集合F中。

算法1 生成候選特征子集。

輸入：當前的訓練集S。設原始特征集合S={S1,S2,…,Sn}為全部特征構成的集合,特征總數為n。 輸出：候選特征子集F。F為被選擇出來的特征構成的子集,即F=?。

1)

對于訓練集S

2)

按式(1)計算S的信息熵Entropy(S)

3)

對于每一個特征A∈Si(i=1,2,…,n)

4)

按式(2)計算Entropy(S,A)

5)

計算特征A的信息熵IG(A)=Entropy(S)-Entropy(S,A)

6)

根據式(4)計算A的信息總量I(A)

7)

定義特征A的信息增益率IGR(A)

8)

如果I(A)!=0,計算IGR(A)值

9)

統計所有特征的信息增益率值,令Key=A,value=IGR(A)值

10)

存入字典dict[Key]=value

11)

對數組dict進行降序排序

12)

如果dict[Si]排名≥「n/2?,將特征Si放入集合F中,過濾其余特征

13)

返回候選特征子集F

2.2.2 搜索最優特征子集

序列前向選擇(SequentialForwardSelection,SFS)算法規定特征子集從空集開始,每次選擇一個能使評價函數取值達到最優的特征加入這個子集。其算法本質就是一種簡單的貪心算法,而這種算法只能加入特征而不能去除特征,容易出現局部最優解而非全局最優解。序列浮動前向選擇(SequentialFloatingForwardSelection,SFFS)算法是一個是自底向上的搜索過程,是在最基本的序列前向選擇過程中引入了一個額外的回溯步驟,有效地規避了SFS算法帶來的弊端。

基于信息增益率上一步生成的候選特征子集F。本文使用隨機森林等構建的克隆代碼有害性評價模型作為一個評估函數,采用序列浮動前向選擇搜索最優子集。 該算法結合正向選擇和反向選擇兩種算法實現特征選擇。正向選擇算法的含義是首先將特征數據集清空,之后每次把一維特征加入到數據集輸入測試模型進行循環測試,最后通過評價預測結果,選擇那些對結果影響最明顯的特征數據;而反向選擇算法的流程與之相反,首先構建包含所有特征的數據集,之后每次從中去除一維特征輸入測試模型進行循環測試,最后去除那些對結果影響最微小的特征數據而保留剩余的特征。選擇算法具體步驟偽代碼描述如下。

算法2SFFS搜索最優特征子集。

輸入：候選特征子集F,一組特征集合Fi(i=1,2,…,q),特征個數q=「n/2?,當前已選擇的特征個數k,初始化k=0。 輸出：最優特征子集Y。

1

初始化特征數據集Y為空,即Y=?,Y={yj|j=1,2,…,D,D≤q},J(Y)表示Y特征子集在評估函數的表現。

2)

對于每一個特征A∈Fi(i=1,2,…,q)

3)

選擇最好的特征A放入Y中

4)

X+=Max[J(Yk+A)],A∈F

5)

Yk=Yk+X+;k=k+1

6)

對于每一個特征x∈Yi(i=1,2,…,k)

7)

選擇Y中最壞的特征x剔除

8)

X-=Max[J(Yk-x) ],x∈Yk

9)

IfJ(Yk-x-)>J(Yk)then

10)

Yk=Yk-X-;k=k-1

11)

goto6)

12)

Else

13)

goto3)

14)

返回最優特征子集Y

3 實驗與分析

3.1 實驗數據集

本文選擇了7款不同C語言軟件共164款發布版本作為實驗軟件,這7款軟件功能不同,規模大小不一并且持續有更新維護。目標軟件詳細信息如表1所示。

3.2 克隆代碼有害性特征樣本收集

本文結合克隆代碼自身特征及其相鄰版本映射關系和在演化過程中隱含的存在、發展、變化規律,提出了兩大類能夠表征克隆代碼有害性的特征,將提出靜態特征和演化特征兩大類共17維特征作為克隆代碼有害性的度量指標。靜態特征能夠反映代碼本身的一些語法語義特征,演化特征能夠表征克隆代碼的穩定性和成熟性。特征匯總如表2所示。

靜態特征的提取建立在克隆代碼檢測的基礎上,本文使用的是自主開發的檢測工具FClones[16],這款工具是基于Token編輯距離的方法檢測克隆,并以最長公共子序列相似度計算模型對克隆對再進行一次源代碼的相似度計算,便于找到更合適的相似度閾值。該工具可以檢測C語言的Type-1、Type-2和Type-3函數粒度克隆,檢測過程中不考慮編程人員的編程風格,如果存在變量和算法在表達式上的差異,Token形式化抽象之后這個差異就不存在了。針對不同程序語言的特點,本文方法具有自然語言通用性,只需要在檢測的過程中對不同自然語言分析詞法層面的信息,制定不同的Token化替換規則。最終都能得到克隆代碼檢測信息,然后通過代碼度量工具SourceMonitor提取克隆代碼行數和注釋比例等部分靜態特征,通過詞法分析提取參數個數等剩余靜態特征。

演化特征的提取必須依賴于克隆家系結果。本文采用克隆家系提取工具FCGE[17]根據克隆代碼映射關系和演化信息自動構建克隆家系,能夠快速準確地提取出軟件中存在的Type-1及Type-2型的克隆家系信息。獲取以上兩種特征之后,得到有害性特征樣本數據集D,列出部分數據見表3。

表1 目標軟件基本信息

表2 克隆代碼有害性特征

表3 實驗數據集

3.3 分類器評估方法及指標

為了評估有害性預測模型的預測效果,需要將數據集分成訓練集和測試集兩部分,其中訓練集用來構建模型,測試集用來評估模型。由于數據集中的數據序列會影響預測模型的預測效果,所以只作一次檢驗會存在很大的偶然性，因此本文選擇K折交叉驗證(K-fold cross-validation)的方法來評估模型效果。K-折交叉檢驗將數據分成K組,使用其中的一組數據作測試集,使用剩余的K-1組數據作訓練集。該測試過程重復K次,每次使用不同的數據作測試集,然后取K次測試效果的平均值作為最終的預測結果。交叉驗證重復K次以確保每個子集都有機會成為一個測試子集。實驗采取K=10,即10折交叉驗證來評估預測模型的性能。這個方法的優勢在于評估結果和數據劃分方式關系不大,每一組數據都有一次機會作為測試數據,并有K-1次機會作為訓練數據,故模型測試誤差中方差的成分變小且過擬合可能性小。

有害性預測是一個典型的二分類問題,現有的預測性能指標多數都是基于表4所示的混淆矩陣。因為有害性預測的目的是識別出有害的克隆代碼模塊,本文認為有害的類屬于正類,反之屬于負類。

表4 混淆矩陣

基于混淆矩陣,本文使用3種指標評估預測模型,分別是準確率(Accuracy)、F1-測度(F1-Measure)和AUC(Area Under ROC Curve)值：

(6)

(7)

其中:TP表示將有害的實例正確預測為有害的實例數量；TN表示將無害的實例正確預測為無害的實例數量；FP表示將無害的實例錯誤預測為有害的實例數量；FN表示將有害的實例錯誤預測為無害的實例數量。AUC是指ROC(Receiver Operating Characteristic Curve)曲線下面包括的面積[18],即ROC曲線的積分。ROC曲線的X軸表示負正類率,Y軸表示真正類率。AUC值介于0～1,值越大,即代表分類效果越好。

3.4 實驗結果與分析

本文基于Weka學習平臺使用不同的機器學習方法來評估分類器的整體表現。實驗中使用基于貝葉斯定理與特征條件獨立假設的樸素貝葉斯(NaiveBayes)算法,不同k(1～9)值的k近鄰分類器(KNN),修剪決策樹作為基分類器的裝袋集成學習器(Bagging),基于C4.5決策樹算法的J48決策樹,隨機森林分類器(RandomForest),Java實現的命題規則學習算法RIPPER(JRip)。

圖3展示了兩款軟件基于信息增益率排名下前n個特征在六種機器學習方法預測的Accuracy平均值。從圖3中可以得出以下結論:

1)從圖3(a)中可以看到,當特征數量增加時NaiveBayes的分類準確率急劇下降,預測最好與最差表現相差4個百分點左右,而其他分類器結果都在可以接受的波動范圍內。當特征個數n=6時,Bagging分類的效果達到最佳,僅僅包含了6個特征,卻縮減了約70%的特征。

2)從圖3(b)中,隨著特征數目的逐漸增多,NaiveBayes的分類表現逐漸降低,分析原因可能是該算法基于特征條件獨立的假設下,而實際情況中特征相關性較強,如果不考慮此因素預測準確性會越來越低。對于KNN、C4.5、Bagging和RandomForest四個分類器,當特征數量在4～6,準確度提高10個百分點左右達到最佳表現,之后隨著特征增多,兩者之間并不會呈現正相關,相反結果趨于穩定。

從圖3(a)和圖3(b)中發現,針對某一款軟件,采用任何一種學習方法預測,可以很直觀地選擇出能使該數據集達到最好分類效果的特征個數n。在選擇n值的過程中,并不是n值較小,預測效果就不好,也并不是n值越大,分類效果就越好;相反,最好的n個候選特征子集是根據信息增益率排名計算得出。

從上述結論中可以得到:本文方法依據信息增益率對上述兩款軟件的特征進行排名,通過關鍵參數特征n的選取實驗,給出了本文方法中關鍵參數的最佳取值,從而為有害性預測結果提供了更簡潔和準確的特征范圍。同時,針對不同軟件,特征n數目并非固定不變,本文方法的實現也支持參數n的調節。

在表5中,將本文提出的IGR-SFFSM方法選擇出的特征子集應用在六款不同的機器學習預測模型中。從表5的實驗結果得出,IGR-SFFSM方法選擇出來的特征數據集在六種分類算法中都比保留所有特征的原數據集D上分類效果好,提高的范圍從15.2～34個百分點,平均表現提高了25.08個百分點。同時發現,不同特征選擇策略的準確度對數據集的類型有很高的敏感性。例如,fdisk數據集在經過IGR-SFFSM方法篩選之后,平均準確度僅僅提高了2個百分點左右,而smalltalk分類效果平均提高了28個百分點。最后發現J48+IGR-SFFSM、RIPPER+IGR-SFFSM組合的分類效果有明顯提高,其中RandomForest+IGR-SFFSM組合的效果較差。

表5 特征選擇前后不同分類算法預測的Accuracy值對比

注：D代表原始數據集;D*代表使用IGR-SFFSM方法進行特征選擇之后的數據集;

AVG表示一種分類方法采用D和D*數據集進行預測得出的Accuracy值平均提高的百分點。

將IGR-SFFSM方法與同類一些比較常用的特征選擇方法進行比較,這些方法有基于皮爾森系數的相關性計算準則(Correlation)、基于信息熵的信息增益率和采用最好優先搜索策略(BestFirst)的Wrapper方法。表6中呈現了不同特征選擇相關算法的分類結果。從表6可看出,Wrapper+BestFirst和IGR-SFFSM在三種衡量指標上都要遠優于其他類方法,IGR-SFFSM比其他方法Accuracy提升7.7～17.5個百分點,F1-Measure提升3.6～10.1個百分點,AUC值提高7.0～22.1個百分點。最后,本文提出的IGR-SFFSM方法與Wrapper+BestFirst方法相比在三類性能指標上稍有提升,平均提高約為1.5個百分點。

表6 特征選擇相關算法的分類結果對比

表7列出了本文方法在7款開源軟件上篩選特征子集的過程。表中數字所代表的特征名稱和具體描述在表2中有詳細的說明,例如序號0代表代碼行數、序號1代表計算程序長度、序號16代表改變頻率,其他序號含義以此類推。這些數字所表示的特征必須數值化成表3所示的具體數字后才能應用到有害性預測中。由表7可知,FullSets列表示初始特征子集經過信息增益率評估之后的排名序列； IGR-Sets列表示根據前一步計算之后,選擇出來的候選特征子集,去除FullSets中一些與分類相關程度非常小的特征；SFFSM-Sets列表示在IGR-Sets方法提供的候選集上,進行子集搜索應用到分類器上,得出的預測效果最好的特征集合?？梢缘贸鼋Y論,本文方法平均篩選出的特征個數為4～5個,縮減了將近70%的特征,效果依然優于使用全部特征進行預測的表現。特別地,多款軟件中特征1、7、8、10號特征被選中次數最多,說明這四個特征對分類結果影響較大；而0、11、12號特征似乎都被篩掉(表2詳細說明了序號表示的意義),這也只能說明針對這幾款軟件來說這幾個特征用來表征有害性的程度微小一些,對有害無害的分類結果影響較小。

表7 特征子集生成過程

從表5～7的結果中可以得出:本文方法使用基于信息論的信息增益率對特征n這個關鍵參數進行合理的選取,即針對不同軟件參數n會有不同的調節，最終可用較少的特征來提高有害性分類的準確度、F1值和AUC三種衡量指標,體現了本文方法在預測結果的高效性。本文認定有害克隆代碼的出發點就是基于大多數的不一致變化會引入bug這個觀點。從標注為發生不一致變化的克隆代碼中提取眾多特征,希望能挖掘出真正和有害代碼行為相關的特征行為。而實際這些特征中存在一些和有害克隆代碼無關或冗余的特征影響發現有害代碼的可能性，因此,本文方法對這些特征之間和特征與有害性之間的關系進行了分析,最終選擇出與有害分類相關程度最高的特征,實驗結果表明這些精選出來的特征確實能提高預測的精確度。所以,特征選擇可以提高發現有害克隆代碼的高效性和可能性。

3.5 實驗結果說明

根據不同編程語言的特性,比如不同語言有不同的關鍵字、不同的函數定義方式等，依據詞法分析就能分析出來詞法成分并制定不同的Token化替換規則進行替換。例如:針對C語言,用r統一替換數組名,使用D替換基本數據類型, for替換為F等替換規則。對于不同粒度的代碼也一樣,在于詞法分析這個預處理過程,預處理時識別出來代碼范圍就一樣可以進行Token化。其他語言的Token化規則類似,考慮具體語言特性即可,最終都能得到克隆代碼檢測信息。

本文實驗部分的特征角度對比是從靜態特征和演化特征兩個維度進行分析的。以上分析結果說明對表征有害性的特征進行篩選,確實可以提高有害性預測準確度,也能剔除一些無關緊要的特征(這些不必要特征的提取會耗費很大一部分時間精力)。結果發現衡量有害克隆代碼的特征指標很多,但其實只有一部分特征會影響代碼的有害無害程度。例如:圈復雜度和分支語句比例過高的代碼,有害可能性非常大,相反代碼行數的多與少對于代碼有害程度的影響較小。最終發現有害克隆代碼是真實存在的,其造成的原因是克隆代碼中一小段代碼由于bug修復或者新功能引入而發生了改變,其他與其相似的克隆代碼需要獲得同樣的處理和檢查,如果無意中遺漏了某一段代碼,也就是說這些克隆代碼之間沒有保持一致性而發生了不一致變化,這就可能給程序中帶來隱含的bug。

在有害性預測問題中存在誤判現象。因為克隆代碼有害性預測這個研究領域是基于克隆檢測、克隆映射和克隆家系等多個基礎研究之上,每個階段的方法都會存在一定的誤差；即使是每個階段使用效果最好的方法,也會存在一定的誤差。另外一個誤差原因,鑒定克隆代碼有害無害的研究和觀點沒有統一標準,而判斷有害無害的標準是以國內外的大量研究為基準,他們都認為克隆代碼不一致變化非常頻繁并且大量的程序錯誤都是由這種不一致變化引起的。

4 結語

針對克隆代碼有害性預測中存在特征無關與冗余的問題,本文采用一種基于序列浮動前向搜索和信息增益率組合的特征選擇算法——IGR-SFFSM。實驗結果表明,IGR-SFFSM方法選擇出來的特征預測表現更好,在本文采用的準確率、F1值、AUC三類指標上都有明顯的提升。特征選擇結果表明使用機器學習進行有害性預測并不是特征越多包含的信息越多,預測結果更好，一定程度上科學合理地削減一些不重要的特征,不但能減少模型構建的時間,還能節省提取無關特征耗費的時間和精力。本文的研究結果僅提供給維護人員來預測即將發布的軟件版本中是否存在這種不一致的變化,大多數的不一致變化會存在bug,有的不一致變化存在也不會對整個軟件有任何危害。本文的預測結果作為一個測試/維護人員的推薦和參考,但是要客觀精確衡量每一段克隆代碼有害或者無害,還需要在人工觀察之后,決定是否有害以及是否需要重構或修改。此外,該方法可以擴展到克隆代碼管理方面,在構建模型評估克隆代碼的質量時，面對選擇特征集工作量大,特征分散等問題,本文提出的對于特征優化篩選的方法對解決這些問題都有借鑒意義。

本文的研究工作目前表現仍有不足:一方面是文中所用到的克隆有害性特征包括靜態與動態特征共17維,僅對克隆代碼部分特征進行分析并得到不同結論,并沒有從其他角度分析和收集一些特征,例如耦合特征、上下文特征、克隆特征等。如果能夠從不同的特征度量元來考慮對克隆代碼有害性預測能力的影響會更全面。另一方面是在研究中發現有害性預測數據集上存在數據分類不平衡的問題,這種數據不平衡會影響特征和類標簽之間的相關程度計算。所以,在未來的研究工作中擬從多維特征角度對比分析以及將特征選擇和數據不平衡問題結合起來進行研究,進一步提高有害性預測效果。

References)

[1] WAGNER S, ABDULKHALEQ A, KAYA K, et al. On the relationship of inconsistent software clones and faults: an empirical study [C]// Proceedings of the 23rd International Conference on Software Analysis, Evolution, and Reengineering. Washington, DC: IEEE Computer Society, 2016:79-89.

[2] 梅宏, 王千祥, 張路, 等. 軟件分析技術進展[J]. 計算機學報, 2009, 32(9): 1697-1710.(MEI H, WANG Q X, ZHANG L, et al. Software analysis technology progress[J]. Chinese Journal of Computers, 2009, 32(9): 1697-1710.)

[3] 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. Piscataway, NJ: IEEE, 2012: 170-179.

[4] 李智超. 基于支持向量機的克隆代碼有害性評價方法研究[D]. 哈爾濱:哈爾濱工業大學, 2013:32-34.(LI Z C. Research on SVM-based evaluation method of clone code harmfulness [D]. Harbin: Harbin Institute of Technology, 2013: 32-34.)

[5] 張麗萍, 張瑞霞, 王歡, 等. 基于貝葉斯網絡的克隆代碼有害性預測[J]. 計算機應用, 2016, 36(1):260-265.(ZHANG L P, ZHANG R X, WANG H, et al. Harmfulness prediction of clone code based on Bayesian network[J]. Journal of Computer Applications, 2016, 36(1):260-265.)

[6] 尹麗麗. 基于主題模型的克隆代碼有害性預測研究[D]. 呼和浩特:內蒙古師范大學, 2014:6-7.(YIN L L. Research on predicting harmfulness of code clones based on the topic model[D]. Hohhot: Inner Mongolia Normal University, 2014:6-7.)

[7] INOUE K, HIGO Y, YOSHIDA N, et al. Experience of finding inconsistently-changed bugs in code clones of mobile software[C]// IWSC 2012: Proceedings of the 6th International Workshop on Software Clones. Piscataway, NJ: IEEE, 2012:94-95.

[8] JUERGEBS E, DEISSENBOECK F, HUMMEL B, et al. Do code clones matter?[C]// ICSE 2009: Proceedings of the 31st International Conference on Software Engineering. Piscataway, NJ: IEEE, 2009:485-495.

[9] STEIDL D, GODE N. Feature-based detection of bugs in clones[C]// IWSC 2013: Proceedings of the 2013 7th International Workshop on Software Clones. Piscataway, NJ: IEEE, 2013: 76-82.

[10] GUYON I, ELISSEEFF A. An introduction to variable and feature selection [J]. Journal of Machine Learning Research, 2002, 3(6):1157-1182.

[11] BONEV B, ESCOLANO F, CAZORLA M. Feature selection, mutual information, and the classification of high-dimensional patterns [J]. Formal Pattern Analysis & Applications, 2008, 11(3/4):309-319.

[12] MOUSTAKIDIS S P, THEOCHARIS J B. A fast SVM-based wrapper feature selection method driven by a fuzzy complementary criterion [J]. Formal Pattern Analysis & Applications, 2012, 15(4):379-397.

[13] MENZIES T, GREENWALD J, FRANK A. Data mining static code attributes to learn defect predictors [J]. IEEE Transactions on Software Engineering, 2007, 33(1):2-13.

[14] KOHAVI R, JOHN G H. Wrappers for feature subset selection [J]. Artificial Intelligence, 1997, 97(1/2):273-324.

[15] JANECEK A, GANSTERER W N, DEMEL M, et al. On the relationship between feature selection and classification accuracy [EB/OL]. [2016- 05- 10]. http://www.jmlr.org/proceedings/papers/v4/janecek08a/janecek08a.pdf.

[16] 張久杰, 王春暉, 張麗萍, 等.基于Token編輯距離檢測克隆代碼[J]. 計算機應用, 2015, 35(12): 3536-3543.(ZHANG J J, WANG C H, ZHANG L P, et al. Clone code detection based on Levenshtein distance of Token [J]. Journal of Computer Applications, 2015, 35(12):3536-3543.)

[17] 涂穎, 張麗萍, 王春暉, 等.基于軟件多版本演化提取克隆譜系[J]. 計算機應用, 2015, 35(4): 1169-1173.(TU Y, ZHANG L P, WANG C H, et al. Clone genealogies extraction based on software evolution over multiple versions[J]. Journal of Computer Applications, 2015, 35(4): 1169-1173.)

[18] FAWCETT T. An introduction to ROC analysis [J]. Pattern Recognition Letters, 2006, 27(8):861-874.

This work is partially supported by the National Natural Science Foundation of China (61363017, 61462071), the Natural Science Foundation of Inner Mongolia Autonomous Region (2014MS0613, 2015MS0606).

WANG Huan, born in 1991, M. S. candidate. His research interests include code analysis.

ZHANG Liping, born in 1974, Ph. D., professor. Her research interests include software engineering, software analysis.

YAN Sheng, born in 1984, M. S., lecturer. His research interests include software analysis, parallel computing.

LIU Dongsheng, born in 1956, professor. His research interests include software analysis, computer education.

Feature selection model for harmfulness prediction of clone code

WANG Huan, ZHANG Liping*, YAN Sheng, LIU Dongsheng

(College of Computer and Information Engineering, Inner Mongolia Normal University, Hohhot Nei Mongol 010022, China)

To solve the problem of irrelevant and redundant features in harmfulness prediction of clone code, a combination model for harmfulness feature selection of code clone was proposed based on relevance and influence. Firstly, a preliminary sorting for the correlation of feature data was proceeded by the information gain ratio, then the features with high correlation was preserved and other irrelevant features were removed to reduce the search space of features. Next, the optimal feature subset was determined by using the wrapper sequential floating forward selection algorithm combined with six kinds of classifiers including Naive Bayes and so on. Finally, the different feature selection methods were analyzed, and feature data was analyzed, filtered and optimized by using the advantages of various methods in different selection critera. Experimental results show that the prediction accuracy is increased by15.2-34 percentage pointsafter feature selection; and compared with other feature selection methods,F1-measure of this method is increased by 1.1-10.1 percentage points, and AUC measure is increased by 0.7-22.1 percentage points. As a result, this method can greatly improve the accuracy of harmfulness prediction model.

clone code; harmfulness prediction; feature subset; information gain ratio; feature selection

2016- 08- 24;

2016- 09- 30。

國家自然科學基金資助項目(61363017,61462071);內蒙古自治區自然科學基金資助項目(2014MS0613,2015MS0606)。

王歡(1991—),男,內蒙古巴彥淖爾人,碩士研究生,主要研究方向:代碼分析; 張麗萍(1974—),女,內蒙古呼和浩特人,教授,博士,CCF會員,主要研究方向:軟件工程、軟件分析; 閆盛(1984—),男,內蒙古包頭人,講師,碩士,主要研究方向:軟件分析、并行計算;劉東升(1956—),男,內蒙古呼和浩特人,教授,主要研究方向:軟件分析、計算機教育。

1001- 9081(2017)04- 1135- 08

10.11772/j.issn.1001- 9081.2017.04.1135

TP311.5

A