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

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

克隆代碼有害性預(yù)測(cè)中的特征選擇模型

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

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

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

克隆代碼;有害性預(yù)測(cè);特征子集;信息增益率;特征選擇

0 引言

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

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

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

1 相關(guān)工作

1.1 克隆代碼有害性定義

目前,對(duì)于克隆代碼的有害性界定非常模糊,相關(guān)的有害性預(yù)測(cè)研究中,也沒有一個(gè)標(biāo)準(zhǔn)的有害性界定范圍，因此,關(guān)于克隆代碼有害性方面的研究相對(duì)較少。

Wang等[3]通過(guò)收集克隆代碼的屬性特征及要粘貼的目標(biāo)區(qū)域的上下文特征進(jìn)行學(xué)習(xí),預(yù)測(cè)克隆操作的有害性。李智超[4]基于機(jī)器學(xué)習(xí)中有監(jiān)督學(xué)習(xí)方法支持向量機(jī)進(jìn)行了克隆代碼有害性評(píng)價(jià)方法的研究。該研究認(rèn)為“一致變化”的代碼是有害的,而國(guó)外大多數(shù)研究者們則認(rèn)為“不一致變化”才是引起程序出錯(cuò)的主要原因。例如Inoue等[7]研究發(fā)現(xiàn)通過(guò)檢測(cè)手機(jī)軟件中克隆代碼的不一致變化能有效地找出軟件中潛伏的bug。Juergens等[8]對(duì)四個(gè)系統(tǒng)的研究結(jié)果進(jìn)行報(bào)告,發(fā)現(xiàn)克隆代碼中52%會(huì)發(fā)生不一致變化,28%的不一致變化被無(wú)意地引入,15%的不一致變化會(huì)引入錯(cuò)誤,50%的無(wú)意不一致變化會(huì)導(dǎo)致程序錯(cuò)誤。該研究同時(shí)也表明,幾乎任何對(duì)克隆代碼不經(jīng)意的不一致修改,都可能會(huì)隱藏著一個(gè)bug。德國(guó)的Steidl等[9]使用機(jī)器學(xué)習(xí)領(lǐng)域的決策樹自動(dòng)識(shí)別軟件的bug,他們認(rèn)為無(wú)意的不一致修改是導(dǎo)致有害克隆的原因。國(guó)內(nèi)外的大量研究都認(rèn)為克隆代碼不一致變化非常頻繁并且大量的程序錯(cuò)誤都是由這種不一致變化引起的。

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

圖1 不一致的bug修復(fù)引發(fā)錯(cuò)誤

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

結(jié)構(gòu)化的不一致問(wèn)題屬于克隆代碼領(lǐng)域中的Type-4類型,而Type-4 克隆代碼則為功能相似或相同,但句法結(jié)構(gòu)不同的代碼段,目前國(guó)內(nèi)外對(duì)Type-4克隆代碼檢測(cè)的研究?jī)H處于探索階段,無(wú)法獲取,因此結(jié)構(gòu)化不一致問(wèn)題不作為本文研究?jī)?nèi)容。

最終本文將發(fā)生不一致變化的克隆代碼標(biāo)注為有害克隆代碼,如果克隆群經(jīng)歷了至少一次不一致變化,本文就認(rèn)為這種克隆操作是有害的。如果克隆群經(jīng)歷無(wú)變化或者一致性修改變化,本文認(rèn)為這種克隆操作就是無(wú)害的。對(duì)克隆代碼進(jìn)行修改時(shí),需要對(duì)克隆群內(nèi)所有克隆代碼作一致性修改,而遺漏群內(nèi)任何代碼的一致性修改操作都會(huì)導(dǎo)致克隆群中發(fā)生不一致改變,這會(huì)導(dǎo)致程序出現(xiàn)錯(cuò)誤,進(jìn)而給軟件系統(tǒng)帶來(lái)隱含的bug。

1.2 特征選擇

特征選擇作為機(jī)器學(xué)習(xí)和模式識(shí)別領(lǐng)域中非常重要的數(shù)據(jù)預(yù)處理技術(shù),在有害性預(yù)測(cè)中扮演著重要角色。而特征選擇的焦點(diǎn)是如何從輸入數(shù)據(jù)中選擇一個(gè)變量的子集,使這個(gè)子集能在有效描述輸入數(shù)據(jù)特性的同時(shí)也能減少一些不相關(guān)變量的噪聲干擾,最終達(dá)到提高預(yù)測(cè)結(jié)果準(zhǔn)確的目的[10]。

評(píng)價(jià)標(biāo)準(zhǔn)在特征選擇過(guò)程中也扮演著重要的角色,它是特征選擇的依據(jù)。評(píng)價(jià)標(biāo)準(zhǔn)可以分為兩種:一種是用于單獨(dú)地衡量每個(gè)特征的預(yù)測(cè)能力的評(píng)價(jià)標(biāo)準(zhǔn),用來(lái)衡量每個(gè)特征與輸出類別標(biāo)簽之間的相關(guān)性;另一種是用于評(píng)價(jià)某個(gè)特征子集整體預(yù)測(cè)性能的標(biāo)準(zhǔn)。根據(jù)特征子集選擇過(guò)程中是否依賴于后續(xù)的學(xué)習(xí)分類方法來(lái)評(píng)價(jià),可以將其具體分為過(guò)濾式(Filter)方法[11]和封裝型(Wrapper)方法[12]共兩大類。

Filter方法是采用一些基于信息統(tǒng)計(jì)的啟發(fā)式準(zhǔn)則來(lái)評(píng)價(jià)特征的預(yù)測(cè)能力。例如,Guyon等[10]提出采用相關(guān)系數(shù)對(duì)特征進(jìn)行排序。該研究對(duì)特征數(shù)據(jù)進(jìn)行預(yù)處理,過(guò)濾掉排名等級(jí)較低的特征變量,最終把相關(guān)程度高的特征提供給機(jī)器學(xué)習(xí)模型使用,從而提高預(yù)測(cè)的效果。Menzies等[13]使用信息增益對(duì)特征進(jìn)行排序,他們的結(jié)論發(fā)現(xiàn)使用前3個(gè)特征和使用全部特征的預(yù)測(cè)效果相差無(wú)幾。目前用得最多的評(píng)價(jià)準(zhǔn)則有相關(guān)系數(shù)法、類間與類內(nèi)距離測(cè)量法、信息熵法、信息增益率、一致性、Relief等。

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

通過(guò)對(duì)上述方法的總結(jié)與分析可以發(fā)現(xiàn):Filter方法獨(dú)立于后續(xù)的分類方法并且避免了Wrapper方法交叉驗(yàn)證的過(guò)程，所以它是一種計(jì)算效率較高的方法且不依賴具體的學(xué)習(xí)算法來(lái)評(píng)價(jià)特征子集。但其主要問(wèn)題是當(dāng)特征和分類器關(guān)聯(lián)較大時(shí),不一定找到規(guī)模較小的最優(yōu)特征子集。例如Relief中的相關(guān)性方法使用樸素貝葉斯作為特征子集選擇器就不合適,因?yàn)樵诖蠖鄶?shù)情況下樸素貝葉斯提高表現(xiàn)是伴隨著相關(guān)特征的移除[10]。雖然Wrapper方法的效率不及Filter,但該方法使用一個(gè)預(yù)定義的分類器來(lái)評(píng)估特征質(zhì)量并有效避免了特征選擇時(shí)依賴具體分類方法的缺點(diǎn),同時(shí)所選的優(yōu)化特征子集的規(guī)模相對(duì)要小一些。然而,這種方法需要多次運(yùn)行分類器來(lái)評(píng)估選擇的特征子集,所以計(jì)算開銷較高。

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

1)大多數(shù)基于機(jī)器學(xué)習(xí)的克隆代碼有害性特征的選擇都依賴于研究者或開發(fā)者的經(jīng)驗(yàn)。而本文提出了一種有害性特征選擇的理論模型,此模型以特征相關(guān)程度和模型預(yù)測(cè)的結(jié)果分析為依據(jù)選擇特征數(shù)據(jù),為克隆代碼有害性預(yù)測(cè)方面的研究提供了更加科學(xué)和客觀的數(shù)據(jù)支持。

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

3)將基于機(jī)器學(xué)習(xí)的自然語(yǔ)言處理中特征選擇方法引入克隆代碼有害性特征選擇當(dāng)中,利用一般特征選擇方法處理形式化語(yǔ)言高效、準(zhǔn)確的優(yōu)勢(shì),針對(duì)克隆代碼有害性特征數(shù)量多且不容易提取,質(zhì)量粗糙的問(wèn)題,提出一種有效的優(yōu)化特征子集的方法,進(jìn)而提高學(xué)習(xí)模型的性能。

2 IGR-SFFSM方法

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

圖2 IGR-SFFSM模型框架

2.1 特征評(píng)估指標(biāo)——信息增益率

IGR-SFFSM方法使用信息論中的信息增益率來(lái)衡量每個(gè)特征給分類過(guò)程中所帶來(lái)的信息量大小。若特征信息增益率越大,則說(shuō)明該特征與分類標(biāo)簽之間的相關(guān)性越大,即特征區(qū)分所有類的能力越強(qiáng)。因此,在進(jìn)行屬性選擇的過(guò)程中,通常選擇信息增益率大的特征作為分類的依據(jù)。

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

(1)

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

(2)

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

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

(3)

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

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

(4)

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

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

(5)

信息增益率作為一種補(bǔ)償措施解決了信息增益所存在的問(wèn)題。通過(guò)信息增益率可以對(duì)特征進(jìn)行相關(guān)性的初步排序,進(jìn)而對(duì)原始數(shù)據(jù)集進(jìn)行了降維且利于選擇出最優(yōu)屬性子集。

2.2 特征選擇方法

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

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

2.2.1 生成候選特征集合

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

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

輸入：當(dāng)前的訓(xùn)練集S。設(shè)原始特征集合S={S1,S2,…,Sn}為全部特征構(gòu)成的集合,特征總數(shù)為n。 輸出：候選特征子集F。F為被選擇出來(lái)的特征構(gòu)成的子集,即F=?。

1)

對(duì)于訓(xùn)練集S

2)

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

3)

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

4)

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

5)

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

6)

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

7)

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

8)

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

9)

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

10)

存入字典dict[Key]=value

11)

對(duì)數(shù)組dict進(jìn)行降序排序

12)

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

13)

返回候選特征子集F

2.2.2 搜索最優(yōu)特征子集

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

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

算法2SFFS搜索最優(yōu)特征子集。

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

1

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

2)

對(duì)于每一個(gè)特征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)

對(duì)于每一個(gè)特征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ōu)特征子集Y

3 實(shí)驗(yàn)與分析

3.1 實(shí)驗(yàn)數(shù)據(jù)集

本文選擇了7款不同C語(yǔ)言軟件共164款發(fā)布版本作為實(shí)驗(yàn)軟件,這7款軟件功能不同,規(guī)模大小不一并且持續(xù)有更新維護(hù)。目標(biāo)軟件詳細(xì)信息如表1所示。

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

本文結(jié)合克隆代碼自身特征及其相鄰版本映射關(guān)系和在演化過(guò)程中隱含的存在、發(fā)展、變化規(guī)律,提出了兩大類能夠表征克隆代碼有害性的特征,將提出靜態(tài)特征和演化特征兩大類共17維特征作為克隆代碼有害性的度量指標(biāo)。靜態(tài)特征能夠反映代碼本身的一些語(yǔ)法語(yǔ)義特征,演化特征能夠表征克隆代碼的穩(wěn)定性和成熟性。特征匯總?cè)绫?所示。

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

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

表1 目標(biāo)軟件基本信息

表2 克隆代碼有害性特征

表3 實(shí)驗(yàn)數(shù)據(jù)集

3.3 分類器評(píng)估方法及指標(biāo)

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

有害性預(yù)測(cè)是一個(gè)典型的二分類問(wèn)題,現(xiàn)有的預(yù)測(cè)性能指標(biāo)多數(shù)都是基于表4所示的混淆矩陣。因?yàn)橛泻π灶A(yù)測(cè)的目的是識(shí)別出有害的克隆代碼模塊,本文認(rèn)為有害的類屬于正類,反之屬于負(fù)類。

表4 混淆矩陣

基于混淆矩陣,本文使用3種指標(biāo)評(píng)估預(yù)測(cè)模型,分別是準(zhǔn)確率(Accuracy)、F1-測(cè)度(F1-Measure)和AUC(Area Under ROC Curve)值：

(6)

(7)

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

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

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

圖3展示了兩款軟件基于信息增益率排名下前n個(gè)特征在六種機(jī)器學(xué)習(xí)方法預(yù)測(cè)的Accuracy平均值。從圖3中可以得出以下結(jié)論:

1)從圖3(a)中可以看到,當(dāng)特征數(shù)量增加時(shí)NaiveBayes的分類準(zhǔn)確率急劇下降,預(yù)測(cè)最好與最差表現(xiàn)相差4個(gè)百分點(diǎn)左右,而其他分類器結(jié)果都在可以接受的波動(dòng)范圍內(nèi)。當(dāng)特征個(gè)數(shù)n=6時(shí),Bagging分類的效果達(dá)到最佳,僅僅包含了6個(gè)特征,卻縮減了約70%的特征。

2)從圖3(b)中,隨著特征數(shù)目的逐漸增多,NaiveBayes的分類表現(xiàn)逐漸降低,分析原因可能是該算法基于特征條件獨(dú)立的假設(shè)下,而實(shí)際情況中特征相關(guān)性較強(qiáng),如果不考慮此因素預(yù)測(cè)準(zhǔn)確性會(huì)越來(lái)越低。對(duì)于KNN、C4.5、Bagging和RandomForest四個(gè)分類器,當(dāng)特征數(shù)量在4～6,準(zhǔn)確度提高10個(gè)百分點(diǎn)左右達(dá)到最佳表現(xiàn),之后隨著特征增多,兩者之間并不會(huì)呈現(xiàn)正相關(guān),相反結(jié)果趨于穩(wěn)定。

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

從上述結(jié)論中可以得到:本文方法依據(jù)信息增益率對(duì)上述兩款軟件的特征進(jìn)行排名,通過(guò)關(guān)鍵參數(shù)特征n的選取實(shí)驗(yàn),給出了本文方法中關(guān)鍵參數(shù)的最佳取值,從而為有害性預(yù)測(cè)結(jié)果提供了更簡(jiǎn)潔和準(zhǔn)確的特征范圍。同時(shí),針對(duì)不同軟件,特征n數(shù)目并非固定不變,本文方法的實(shí)現(xiàn)也支持參數(shù)n的調(diào)節(jié)。

在表5中,將本文提出的IGR-SFFSM方法選擇出的特征子集應(yīng)用在六款不同的機(jī)器學(xué)習(xí)預(yù)測(cè)模型中。從表5的實(shí)驗(yàn)結(jié)果得出,IGR-SFFSM方法選擇出來(lái)的特征數(shù)據(jù)集在六種分類算法中都比保留所有特征的原數(shù)據(jù)集D上分類效果好,提高的范圍從15.2～34個(gè)百分點(diǎn),平均表現(xiàn)提高了25.08個(gè)百分點(diǎn)。同時(shí)發(fā)現(xiàn),不同特征選擇策略的準(zhǔn)確度對(duì)數(shù)據(jù)集的類型有很高的敏感性。例如,fdisk數(shù)據(jù)集在經(jīng)過(guò)IGR-SFFSM方法篩選之后,平均準(zhǔn)確度僅僅提高了2個(gè)百分點(diǎn)左右,而smalltalk分類效果平均提高了28個(gè)百分點(diǎn)。最后發(fā)現(xiàn)J48+IGR-SFFSM、RIPPER+IGR-SFFSM組合的分類效果有明顯提高,其中RandomForest+IGR-SFFSM組合的效果較差。

表5 特征選擇前后不同分類算法預(yù)測(cè)的Accuracy值對(duì)比

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

AVG表示一種分類方法采用D和D*數(shù)據(jù)集進(jìn)行預(yù)測(cè)得出的Accuracy值平均提高的百分點(diǎn)。

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

表6 特征選擇相關(guān)算法的分類結(jié)果對(duì)比

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

表7 特征子集生成過(guò)程

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

3.5 實(shí)驗(yàn)結(jié)果說(shuō)明

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

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

在有害性預(yù)測(cè)問(wèn)題中存在誤判現(xiàn)象。因?yàn)榭寺〈a有害性預(yù)測(cè)這個(gè)研究領(lǐng)域是基于克隆檢測(cè)、克隆映射和克隆家系等多個(gè)基礎(chǔ)研究之上,每個(gè)階段的方法都會(huì)存在一定的誤差；即使是每個(gè)階段使用效果最好的方法,也會(huì)存在一定的誤差。另外一個(gè)誤差原因,鑒定克隆代碼有害無(wú)害的研究和觀點(diǎn)沒有統(tǒng)一標(biāo)準(zhǔn),而判斷有害無(wú)害的標(biāo)準(zhǔn)是以國(guó)內(nèi)外的大量研究為基準(zhǔn),他們都認(rèn)為克隆代碼不一致變化非常頻繁并且大量的程序錯(cuò)誤都是由這種不一致變化引起的。

4 結(jié)語(yǔ)

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

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

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] 梅宏, 王千祥, 張路, 等. 軟件分析技術(shù)進(jìn)展[J]. 計(jì)算機(jī)學(xué)報(bào), 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] 李智超. 基于支持向量機(jī)的克隆代碼有害性評(píng)價(jià)方法研究[D]. 哈爾濱:哈爾濱工業(yè)大學(xué), 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] 張麗萍, 張瑞霞, 王歡, 等. 基于貝葉斯網(wǎng)絡(luò)的克隆代碼有害性預(yù)測(cè)[J]. 計(jì)算機(jī)應(yīng)用, 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] 尹麗麗. 基于主題模型的克隆代碼有害性預(yù)測(cè)研究[D]. 呼和浩特:內(nèi)蒙古師范大學(xué), 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編輯距離檢測(cè)克隆代碼[J]. 計(jì)算機(jī)應(yīng)用, 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]. 計(jì)算機(jī)應(yīng)用, 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。

國(guó)家自然科學(xué)基金資助項(xiàng)目(61363017,61462071);內(nèi)蒙古自治區(qū)自然科學(xué)基金資助項(xiàng)目(2014MS0613,2015MS0606)。

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

1001- 9081(2017)04- 1135- 08

10.11772/j.issn.1001- 9081.2017.04.1135

TP311.5

A