陳 翔 , 趙英全 , 顧 慶 , 倪 超 , 王 贊

1(南通大學 信息科學技術學院,江蘇 南通 226019)

2(計算機軟件新技術國家重點實驗室(南京大學),江蘇 南京 210023)

3(廣西可信軟件重點實驗室(桂林電子科技大學),廣西 桂林 541004)

4(天津大學 軟件學院,天津 300072)

軟件產品在軟件開發(fā)生命周期內(例如需求分析、軟件設計和軟件實現)都存在引入缺陷的可能性,而含有缺陷的軟件產品在部署上線后可能會產生預期之外的行為,在嚴重的時候甚至會給企業(yè)帶來巨額經濟損失或威脅到產品用戶的生命安全.已有的項目管理經驗表明:在軟件開發(fā)生命周期中,檢測出項目內缺陷的時間越晚,修復該缺陷的代價也越高并且修復代價呈指數級增長,因此,測試人員希望能夠在軟件部署上線前盡可能早地預先識別出所有的缺陷程序模塊,并對這些缺陷模塊投入更多的軟件測試資源(即針對這些缺陷模塊設計更為充分的測試用例或展開更多的代碼審查工作等)[1].軟件缺陷預測(software defect prediction)[1?3]是可以預先識別出缺陷程序模塊的一種靜態(tài)分析方法,其通過挖掘和分析軟件庫(例如項目托管的缺陷跟蹤系統(tǒng)和版本控制系統(tǒng)),可以訓練出缺陷預測模型,并以此來提前識別出被測項目內的缺陷程序模塊.因此該方法可以有效優(yōu)化測試資源的分配,從而有助于提高最終部署上線的軟件產品的質量.

在實際軟件測試時,可以使用的測試資源是有限的,因此很難保障對被測項目內的所有程序模塊進行充分的軟件測試,因此軟件質量保障團隊希望構建出一個模型,其能夠將被測項目內的所有程序模塊,按照模塊含有缺陷的概率,從高到低進行排序.隨后開發(fā)人員可以根據該排序列表依次完成對程序模塊的代碼審查或者軟件測試.這樣,在測試資源存在約束的時候,軟件質量保障團隊可以完成對更多缺陷的檢測和修復.在上述測試場景中,研究人員常用代價感知(effort-aware)的評測指標對模型性能進行評估.基于代價感知的評測指標,有監(jiān)督學習方法與無監(jiān)督學習方法之間的性能比較是最近一個具有爭議性的問題.在基于代碼修改的軟件缺陷預測(change-level software defect prediction,簡稱CL-SDP)問題中,Yang等人驚奇地發(fā)現:存在一些無監(jiān)督學習方法,其預測性能要顯著優(yōu)于已有的經典有監(jiān)督學習方法[4].隨后,Fu等人[5]以及Huang等人[6]對Yang等人的研究工作[4]進行了重現,并得出了一些新的發(fā)現.我們關注了基于多目標優(yōu)化的有監(jiān)督學習方法MULTI,并在跨項目缺陷預測(cross-project defect prediction)場景、同項目缺陷預測(within-project defect prediction)場景和基于時序的缺陷預測場景下,深入分析了MULTI方法與Yang等人考慮的無監(jiān)督學習方法和有監(jiān)督學習方法之間的性能差異.結果表明,MULTI方法在這3個場景下均能取得更好的預測性能,從而說明有監(jiān)督學習方法仍然值得研究人員進行關注[7].

與CL-SDP問題不同,基于文件粒度(在面向對象程序實現的項目中,文件粒度也可以被稱為類粒度)的軟件缺陷預測(file-level software defect prediction,簡稱FL-SDP)問題將模塊粒度設置為文件,因此模塊內含有的代碼行數更多,考慮的度量元也并不相同.最近,Yan等人[8]針對FL-SDP問題,對Yang等人考慮的無監(jiān)督學習方法和有監(jiān)督學習方法進行了深入比較,并得到了相似的結論.但據我們所知:針對FL-SDP問題,在基于代價感知的評測指標下,并沒有研究人員將基于多目標優(yōu)化的MULTI方法[7]與Yan等人考慮的有監(jiān)督學習方法和無監(jiān)督學習方法的性能進行深入分析和比較.因此,我們針對上述問題設計并開展了大規(guī)模實證研究.基于代價感知的評測指標(例如ACC和POPT),我們發(fā)現MULTI方法在同項目缺陷預測場景和跨項目缺陷預測場景下均要顯著優(yōu)于Yan等人考慮的無監(jiān)督學習方法、有監(jiān)督學習方法以及最新提出的OneWay方法[5]和CBS方法[6].基于Huang等人提出的PMI和IFA評測指標[6],我們發(fā)現MULTI方法與代價感知的指標相比存在一定的折衷,但仍好于在ACC和POPT評測指標下表現最好的兩種無監(jiān)督學習方法.除此之外,基于F1評測指標的結果也進一步驗證了MULTI方法的優(yōu)越性.同時,通過分析模型構建的時間開銷,我們認為MULTI方法在模型訓練上花費的計算開銷處于開發(fā)人員可以接受的范圍之內.

本文的主要貢獻可以簡要總結如下:

(1) 我們基于代價感知的評測指標,深入分析了基于多目標優(yōu)化的MULTI方法在基于文件粒度的缺陷預測問題上的預測性能.

(2) 本文在實證研究中考慮了10個開源項目,在模型性能評估上考慮了同項目缺陷預測場景和跨項目缺陷預測場景.通過將MULTI方法與Yan等人考慮的無監(jiān)督學習方法和有監(jiān)督學習方法[8]、Wu和Menzies提出的OneWay方法[5]以及Huang等人提出的CBS方法[6]進行比較,發(fā)現MULTI方法在預測性能上均具有顯著性優(yōu)勢,從而表明MULTI方法在FL-SDP問題上同樣具有優(yōu)勢并值得關注.

本文第1節(jié)介紹軟件缺陷研究背景,以及無監(jiān)督學習方法和有監(jiān)督學習方法在缺陷預測問題上的已有研究成果.第2節(jié)深入分析本文重點考察的基于多目標優(yōu)化的MULTI方法以及Yan等人考慮的有監(jiān)督學習方法和無監(jiān)督學習方法.第3節(jié)給出本文的實驗設計,包括本文考慮的評測對象、評測指標、模型性能評估場景、實驗流程以及結果分析時使用的顯著性檢驗方法等.第4節(jié)分別針對實證研究結果和有效性影響因素進行了深入分析.第5節(jié)總結全文,同時針對未來值得關注的多個研究點進行了展望.

1 軟件缺陷研究背景和相關工作

1.1 研究背景

軟件缺陷預測[1?3]通過分析和挖掘軟件庫(例如項目托管的缺陷跟蹤系統(tǒng)和版本控制系統(tǒng)),訓練出缺陷預測模型,并使用訓練出的模型來提前識別出被測項目內的缺陷程序模塊,隨后開發(fā)人員可以針對這些識別出的缺陷程序模塊展開更為充分的軟件測試或投入更多的代碼審查工作量,借助這種方式可以優(yōu)化測試資源的分配并且有助于提高部署上線的軟件產品質量.具體來說,首先可以通過分析軟件模塊的代碼復雜度或軟件開發(fā)過程中的特點,設計出與軟件缺陷存在一定相關度的度量元(metrics)[9,10].其中,軟件模塊的代碼復雜度可以通過分析代碼行數(line of code)、Halstead科學度量、McCabe環(huán)路復雜度或CK度量元等進行度量,而軟件開發(fā)過程的特點則可以通過分析模塊間的控制/數據依賴性、代碼修改的特征、開發(fā)人員的編程經驗和領域熟悉程度以及項目團隊的組織構架等[1]進行度量.隨后,通過分析軟件庫,抽取出所有的程序模塊(其模塊粒度可以根據應用場景設置為代碼修改、文件或類等),借助手工設計的度量元可以對這些抽取出的模塊進行度量,隨后通過分析代碼修改、修改日志信息和相關缺陷報告[11]可以對這些模塊進行標記(即將模塊類型標記為有缺陷或者無缺陷).基于對模塊的度量和類型標記可以構造出用于模型訓練的數據集.最后,借助某一分類方法(例如神經網絡、支持向量機、樸素貝葉斯或隨機森林等[12])來構建出缺陷預測模型.

1.2 無監(jiān)督學習方法與有監(jiān)督學習方法間的性能比較

近年來,研究人員提出了大量的缺陷預測建模方法[1],無監(jiān)督方法和有監(jiān)督方法是軟件缺陷預測研究中常見的兩類方法.其中,大部分方法屬于有監(jiān)督學習方法,但這類方法需要基于已標記的訓練數據集來構建模型,因此需要花費大量的人力和物力來完成標記數據集的搜集.而無監(jiān)督學習方法則不需要搜集已標記的訓練數據集,可以直接對測試集進行預測,因此可以緩解上述不足,并更容易與企業(yè)實際開發(fā)流程相結合.

在基于代碼修改的軟件缺陷預測問題(在一些文獻中,該問題也被稱為just-in-time軟件缺陷預測[13?16])中,其具有模塊粒度細、可以迅速找到缺陷相關開發(fā)人員等優(yōu)點.Kamei等人[13]從代碼修改的規(guī)模、目的、分散度、修改歷史以及開發(fā)人員經驗等角度對抽取出的代碼修改進行度量,并提出了基于有監(jiān)督的EALR(effort-aware linear regression)方法.Yang等人[4]基于代價感知的評測指標,在性能評估時意外地發(fā)現:存在一些簡單的無監(jiān)督方法,其比已有的有監(jiān)督方法(包括Kamei等人提出的EALR方法[13])可以取得更好的性能.Fu等人[5]對Yang等人的實證研究進行了重現,他們發(fā)現:并不是所有的無監(jiān)督方法的預測性能都可以顯著優(yōu)于有監(jiān)督方法.因此,他們提出了OneWay方法,其可以自動選出更好的無監(jiān)督學習方法.隨后,Huang等人[6]發(fā)現:在給定相同的測試成本時,有監(jiān)督學習方法需要審查更多的代碼修改.Liu等人[17]則提出一種新的無監(jiān)督學習方法CCUM(code churn based unsupervised method),該方法將代碼修改涉及到的刪除代碼量和新增代碼量相加,構成CHURN度量元,并根據該度量元完成對代碼修改的排序.結果表明,CCUM方法[17]相比于Yang等人考慮的方法,可以取得更好的預測性能.

與CL-SDP問題不同,基于文件粒度的軟件缺陷預測問題將模塊粒度設置為文件,因此模塊內含有的代碼量更大.Yan等人在最近的一個研究工作中[8]針對FL-SDP問題,對Yang等人考慮的無監(jiān)督學習方法和有監(jiān)督學習方法的性能進行了比較和分析,并得到了相似的結論.

在我們之前針對CL-SDP的研究工作[7]中發(fā)現:基于多目標優(yōu)化的方法MULTI在3種不同的場景(即同項目缺陷預測場景、跨項目缺陷預測場景和基于時序的缺陷預測場景)下,都要顯著優(yōu)于Yang等人考慮的有監(jiān)督學習方法和無監(jiān)督學習方法.基于上述研究工作,我們希望繼續(xù)分析基于多目標優(yōu)化的MULTI方法在FL-SDP問題中,其性能是否能夠顯著優(yōu)于Yan等人考慮的有監(jiān)督學習方法和無監(jiān)督學習方法.

2 基于文件粒度的軟件缺陷預測方法

該節(jié)首先簡要分析本文考慮的基于多目標優(yōu)化的MULTI方法,隨后依次介紹需要與MULTI方法比較的基準方法[8],這些基準方法可分為兩類:有監(jiān)督學習方法和無監(jiān)督學習方法.

2.1 基于多目標優(yōu)化的MULTI方法

MULTI方法針對FL-SDP問題設置了兩個不同的優(yōu)化目標:其中第1個優(yōu)化目標被設置為模型需要盡可能多地識別出缺陷模塊數,第2個優(yōu)化目標被設置為模型需要盡可能地減少代碼審查工作量.不難看出,模型設置的這兩個優(yōu)化目標之間存在一定程度的折衷關系.即如果訓練出的模型需要識別出更多的缺陷模塊數,則需要投入更多的代碼審查工作量;與此相反,若需要減少代碼審查工作量,則訓練出的模型有可能會遺漏掉一些缺陷模塊[7].

本文借助Logistic回歸方法來訓練預測模型,假設程序模塊用n個特征(即軟件缺陷預測的度量元)進行度量,則預測模型的系數可以表示為一維向量w={w1,w2,…,wn}.給定預測模型的系數向量w和需要預測的程序模塊mi,其中,程序模塊mi的第j個特征取值用vi,j表示,則可以使用公式(1)計算出該程序模塊包含缺陷的概率為

本文將FL-SDP問題建模為經典的二元分類問題,同時將模塊分類閾值設置為0.5,即若預測出的含有缺陷的概率取值大于0.5,則將該程序模塊預測為有缺陷;否則,將該程序模塊預測為無缺陷.其計算公式如下所示.

隨后依次給出兩個優(yōu)化目標的計算公式.假設需要進行預測的模塊用集合M來表示,候選解用w來表示,則針對模型設置的第1個優(yōu)化目標,可將其計算公式定義如下.

其中,buggy(mi)用于表示程序模塊mi是否包含缺陷:如果該模塊內含有缺陷,其取值為1;否則,其取值為0.

針對模型設置的第2個優(yōu)化目標,可將其計算公式定義如下.

其中,LOC(mi)表示文件模塊內含有的代碼行數,在該研究工作中,我們假設模塊含有的代碼行數越多,則需要投入的代碼審查量越大(即需要投入更多的軟件測試資源).

我們通過一個虛擬實例對這兩個優(yōu)化目標的具體計算過程進行解釋.表1展示了訓練集中含有的文件和各個文件在某個模型下對應的預測類型Y(?)、實際類型buggy(?)以及代碼審查代價LOC(?).則第1個優(yōu)化目標的值可借助公式(0×1+1×0+...+1×1)計算出,第2個優(yōu)化目標的值可借助公式(1×50+0×80+...+1×20)計算出.

Table 1 A synthesized instance表1 虛擬實例

基于上述分析,本文將FL-SDP問題建模為經典的雙目標優(yōu)化問題,為了方便后續(xù)描述,我們首先對與多目標優(yōu)化相關的概念進行定義.

定義1(Pareto支配關系).假設用于訓練FL-SDP模型的兩個候選解分別用wa和wb進行表示,則waPareto支配wb,當且僅當:

(benefit(wa)>benefit(wb) andcost(wa)≤cost(wb)) or (benefit(wa)≥benefit(wb) andcost(wa)

定義2(Pareto最優(yōu)解).一個候選解w被認為是Pareto最優(yōu)解,當且僅當不存在其他候選解w*,該解能夠Pareto支配w.

定義3(Pareto最優(yōu)解集).所有Pareto最優(yōu)解可以構成Pareto最優(yōu)解集.

定義4(Pareto前沿).所有Pareto最優(yōu)解對應的不同優(yōu)化目標值在空間內形成的曲面被稱為Pareto前沿.

針對多目標優(yōu)化問題,研究人員已經提出了大量不同類型的算法,這些算法主要基于演化算法來構造出Pareto前沿.目前,多目標優(yōu)化算法在軟件工程問題中已經取得了較多的成功應用[7,18].本文考慮的MULTI方法[7]主要基于一種經典的多目標優(yōu)化算法NSGA-II[19],NSGA-II算法本身具有一定的機制(即基于分層的快速非支配排序算法、染色體的擁擠度計算方法和精英保留機制)可以有效避免種群的過早收斂問題.具體來說:NSGA-II算法在每次進行種群演化時,首先使用演化算子產生新的染色體,隨后將這些新產生的染色體與上一輪種群內的染色體進行合并,并使用基于分層的快速非支配排序算法來完成染色體的排序,同時,對于每個非支配層中的染色體依次計算出各個染色體的擁擠度,最后同時考慮非支配關系和染色體的擁擠度,選出指定數量的高質量染色體并形成新的種群..MULTI方法將種群中的染色體編碼為預測模型的系數向量,在訓練集上可以借助染色體對應的系數向量來訓練出預測模型,并隨后分別使用benefit函數(見公式(3))和cost函數(見公式(4))依次計算出該預測模型設置的兩個優(yōu)化目標取值.其偽代碼如算法1所示.

算法1.MULTI方法.

輸入:種群規(guī)模N,最大迭代次數T;

輸出:Pareto最優(yōu)解集.

MULTI方法的具體執(zhí)行過程可以總結如下:首先對種群進行初始化(步驟2),染色體對應的向量內元素被隨機賦值.隨后,使用交叉算子和變異算子可以生成新的染色體(步驟4).具體來說,變異算子會基于指定的變異概率隨機挑選出一個染色體,對其進行變異并產生一個新的染色體.交叉算子會基于指定的交叉概率隨機選出兩個染色體,對其進行交叉并產生兩個新的染色體.隨后,MULTI方法基于選擇算子并通過分析Pareto支配關系,從當前種群內的染色體中選出一定數量的高質量染色體到下一輪種群.具體來說,首先將當前種群內的染色體和基于兩種演化算子生成的新染色體合并到集合Bt中(步驟5).然后使用fastNondominateSort函數計算出Bt中的每個染色體的NDR(non-dominated rank)取值(步驟6).該計算過程總結如下,首先從Bt中選出所有不能被Pareto支配的染色體,將它們的NDR值設置為1,同時將它們從集合Bt移到集合F1.隨后,繼續(xù)從Bt中選出所有不能被Pareto支配的染色體,將它們的NDR值設置為2,同時將它們從集合Bt移到集合F2.重復執(zhí)行上述過程,直到集合Bt不再含有任何染色體.不難看出,基于染色體的NDR取值,MULTI方法會優(yōu)先選擇NDR取值更小的染色體到下一輪種群(步驟7～步驟15).除此之外,MULTI方法還通過擁擠距離[19]來避免選出高相似度染色體,從而確保種群內的染色體具有一定的多樣性.當達到指定的最大迭代次數MaxT后,MULTI方法將返回當前種群中的所有Pareto最優(yōu)解.這里值的注意的是,MULTI方法僅基于訓練集來計算出Pareto最優(yōu)解集,隨后基于該集合內的每個最優(yōu)解訓練出缺陷預測模型,并在測試集上計算出該對應模型的預測性能.

2.2 基準方法

2.2.1 有監(jiān)督學習方法

Ghotra等人[12]最近深入分析了大量有監(jiān)督學習方法的性能在軟件缺陷預測上是否存在顯著性差異.本文考慮的31種無監(jiān)督學習方法主要來自于Ghotra等人[12]在實證研究中考慮的方法,具體見表2.

Table 2 Overview of supervised methods表2 本文考慮的有監(jiān)督學習方法

這些方法也被廣泛用于其他文獻中[4,6?8].這31種無監(jiān)督學習方法可以細分為6類.具體來說,function類型包括4種方法,Lazy類型包括1種方法,Rule類型包括2種方法,Bayes類型包括1種方法,Tree類型包括3種方法.集成學習類方法根據集成方式的不同又細分為4個子類(bagging對應的簡稱為BG、adaboost對應的簡稱為AB、rotation forest對應的簡稱為RF、random subspace對應的簡稱為RS),每個子類各包括5種方法.以BG+LMT為例,其表示該方法采用LMT方法作為基方法,以BG作為集成學習方法.不難看出,這些方法基本上可以覆蓋目前機器學習領域中比較經典的有監(jiān)督方法.

2.2.2 無監(jiān)督學習方法

與有監(jiān)督學習方法相比,無監(jiān)督學習方法具有不需要已標記訓練數據、計算開銷小以及實現簡單等的優(yōu)點,因此成為當前軟件缺陷預測研究中的一個關注熱點.Koru等人[20,21]發(fā)現,模塊的代碼規(guī)模與其含有缺陷的概率呈正比,因此,代碼規(guī)模越小的模塊,越需要優(yōu)先給他分配測試資源.這樣才能在給定的測試資源下,檢測出更多的缺陷.Menzies等人[22]基于Koru等人的發(fā)現提出了ManualUp模型,隨后,Zhou等人[23]在他們的實證研究中對ManualUp模型的有效性進行了驗證.本文重點考慮了Yan等人[8]提出的無監(jiān)督方法,具體來說,對某個度量元M,其相應的建模方法為R(c)=1/M(c),其中,c表示文件模塊,R為預測的缺陷概率.不難看出,在該方法中,度量值較小的模塊將排在更前面.

3 實驗設計

本文在實證研究中重點分析如下實驗問題.

· RQ1:在同項目缺陷預測場景下,基于多目標優(yōu)化的MULTI方法的預測性能是否好于基準方法?

· RQ2:在跨項目缺陷預測場景下,基于多目標優(yōu)化的MULTI方法的預測性能是否好于基準方法?

· RQ3:若基于PMI和FIA指標,基于多目標優(yōu)化的MULTI方法與基準方法相比,表現如何?

前兩個實驗問題基于代價感知的評測指標來比較多目標優(yōu)化方法MULTI與Yan等人考慮的基準方法的性能差異.后兩個指標則由Huang等人[6]提出,重點從測試的模塊數以及模塊測試時的誤報問題這兩個角度進行比較,其具體含義見第3.2節(jié).

3.1 評測對象

本文考慮的評測對象來自PROMISE數據集[24],這些評測對象來自于開源項目,具有代碼規(guī)模大、項目較為有名、項目活躍時間長等特點.除此之外,這些項目也覆蓋了不同類型的應用領域,因此具有一定的典型性.如Ant屬于程序構建工具、Tomcat屬于Web服務器.這些評測對象在度量文件模塊時考慮的度量元的類型、名稱和具體含義件表3.

基于這些評測對象搜集到的數據集的統(tǒng)計特征見表4,包括項目的名稱和版本號、含有的文件數、缺陷文件數以及缺陷文件數所占的比例.不難看出,這些數據集都存在一定的類不平衡問題,缺陷文件占所有文件的比例介于6.6%～34.1%之間.

Table 3 Metrics used by experimental subjects表3 評測對象考慮的度量元

Table 4 Statistics of datasets表4 數據集的統(tǒng)計特征

3.2 評測指標

本文重點考察測試代價感知的評測指標,Mende等人[25]首次將測試代價引入到缺陷預測的建模過程,Kamei等人[26]則將傳統(tǒng)指標下的實證研究結論在代價感知的評測指標下進行了重新驗證.與已有研究工作[4,13]保持一致,本文重點考慮了兩個評測指標:ACC和POPT.這兩個指標均考慮了軟件測試代價,并且都是取值越大,對應的模型性能就越好.本文將程序模塊的規(guī)模視為測試代價,其中,ACC指標計算的是當使用了指定比例(一般該比例被設置為20%)的測試資源后,模型針對缺陷模塊的查全率;而POPT指標則可以認為針對基于測試開銷的指標進行了歸一化處理,其計算示意圖如圖1所示,圖中共有3條曲線,分別對應預測模型m、最優(yōu)模型optimal和最差模型worst.

在最優(yōu)模型中,模塊按照其實際的缺陷密度從高到低進行排序,在最差模型中,模塊則按照其實際的缺陷密度從低到高進行排序.Area(optimal),Area(worst)和Area(m)分別表示模型optimal,worst以及m對應曲線下的面積.最終POPT指標的計算公式如下所示.

Fig.1 Illustration of Popt performance metric圖1 Popt 指標的示意圖

除此之外,本文還考慮了 Huang等人[6]提出的兩種新評測指標.具體來說,PMI(proportion of modules inspected)指標計算在花費20%的測試資源后,測試的模塊所占比例.其取值越高,表示在相同的測試成本下進行測試的模塊數越多,這意味著需要開發(fā)人員進行更多的上下文切換,并可能對他們的開發(fā)效率產生影響[27].IFA(number of initial false alarms)指標返回開發(fā)人員依次審查模塊時,當遇到第1個真正缺陷模塊之前需要測試的模塊數.該指標在軟件缺陷定位研究中[28]經常被用到,其取值越高,表示誤報問題越嚴重,并可能會對開發(fā)人員的信心和耐心造成影響.

3.3 模型性能評估場景

與Yan等人的研究工作[8]保持一致,本文同樣考慮了兩種模型性能評估場景:同項目缺陷預測場景和跨項目缺陷預測場景.已有的研究工作大部分集中于同項目缺陷預測場景,即基于一個項目的部分數據來訓練預測模型,并用該項目內的剩余數據來評估訓練出的模型的預測性能.目前,一般采用10折交叉驗證方式,即將數據集借助分層采樣方法劃分為10等份,輪流將其中的9份作為訓練集,剩余1份作為測試集.重復上述過程10次,以確保每個模塊都能被預測到1次.同時為了避免數據集中實例次序對預測結果的影響,在實驗中,我們將10折交叉驗證重復了10次,每次執(zhí)行前使用不同的隨機種子將數據集中的模塊進行隨機打亂,論文將上述模型性能驗證方式稱為10×10折交叉驗證.

但在實際軟件開發(fā)的時候,需要進行預測的項目(即目標項目)可能是一個全新啟動項目,或這個項目已搜集的標記數據不多,一種解決方法是使用搜集自其他項目(即源項目)的標記數據來訓練模型.本文將這種模型驗證方式稱為跨項目缺陷預測[29?31].假設數據集內含有n個項目,則總共可構成n×(n?1)個跨項目缺陷預測場景.由于本文共考慮了10個項目,因此最終可構成90個跨項目缺陷預測場景.

3.4 實驗流程極其方法參數設定

根據多目標優(yōu)化算法在數值問題上的參數設置經驗[32],本文在實驗時將MULTI方法的參數和具體取值分別設置如下:種群規(guī)模被設置為200,系數向量內元素的有效取值區(qū)間被設置為[?10000,10000],在種群初始化時,系數向量內元素的有效取值區(qū)間被設置為[?10,10],最大迭代次數被設置為400,變異概率被設置為0.05,交叉概率被設置為0.5.

考慮到MULTI方法內部存在多個隨機因素,我們會獨立運行MULTI方法10次并每次會設置不同的隨機種子.每次運行時,MULTI方法基于訓練集會計算出一組Pareto最優(yōu)解集.因此獨立運行10次后,會累計計算出10組Pareto最優(yōu)解集.最終,MULTI方法會返回這10組Pareto最優(yōu)解集中能夠在測試集上取的最好性能的解.其具體運行過程如圖2所示.

Fig.2 Experimental process of MULTI method圖2 MULTI方法的實驗流程

對需要比較的有監(jiān)督學習方法,其超參數取值的設定與Yan等人[8]保持一致.針對FL-SDP問題,本文主要考慮了19種無監(jiān)督學習方法(每種度量元對應一種方法,未考慮LOC度量元的原因是因為本文需要使用LOC值來度量模塊的測試代價).

除此之外,針對多目標優(yōu)化方法和有監(jiān)督學習方法,我們進行了如下數據預處理.

(1) 已有研究表明,數據集內含有的冗余特征會降低隨后構建出的模型的預測性能[33].如果一個特征重復了其他單個或多個特征含有的信息,則稱該特征為冗余特征.因此,借助Yan等人[8]考慮的特征選擇方法移除具有高冗余性的特征.這樣可以保證本文所提的方法與Yan等人考慮的方法進行公平的比較.

(2) 對所有數值型特征取值進行Log轉換處理,以緩解特征取值的偏斜(skew)問題.

(3) 在訓練集上應用隨機欠采樣方法來解決搜集的數據集內存在的類不平衡問題.該處理方式與文獻[8]保持一致.即會在訓練集上隨機移除無缺陷程序模塊,直至無缺陷程序模塊的數量與有缺陷程序模塊的數量相等.

除此之外,為了保證結果比較的公平性,針對無監(jiān)督學習方法,我們僅基于測試集內的程序模塊來訓練預測模型.

3.5 顯著性檢驗方法

本文借助Scott-Knott檢驗[34]為本文考慮的所有方法(總共51種)進行排序和分組.Scott-Knott檢驗嘗試將這些不同的方法劃分到具有顯著性差異的秩中(α=0.05).具體來說,Scott-Knott檢驗使用分層聚類分析為每個方法設置不同的秩.其首先將所有方法基于平均性能(基于ACC或POPT指標)劃分成兩組.如果處在一組內的方法仍存在顯著差異性,則其會迭代使用上述過程將該組內的方法繼續(xù)分組,直至組內的方法之間不存在顯著差異性為止.

為了分析基于多目標優(yōu)化的MULTI方法相比其他基準方法是否具有顯著性優(yōu)勢,本文考慮了Benjamini-Hochberg(BH)修正后的p值[35],并將其顯著水平設置為0.05.如果MULTI方法具有顯著優(yōu)勢,則進一步采用Cliff’sδ來度量這種差異程度.其差異程度及建議取值范圍與文獻[35]保持一致,具體見表5.具體比較過程總結如下:如果MULTI方法顯著優(yōu)于/差于指定的基準方法,需要BH修正后的p值小于0.05,同時,其差異程度不是negligible的;如果MULTI方法與指定的基準方法不存在顯著性差異,則BH修正后的p值不小于0.05,或者雖然BH修正后的p值小于0.05,但其差異程度是negligible的.

Table 5 Magnitude of effectiveness level of Cliff’S δ and its thresholds表5 Cliff’s δ的差異程度及其建議取值范圍

4 實證研究結果的分析

首先,我們通過將MULTI方法與兩種簡單的搜索方法相比,來驗證FL-SDP問題的求解難度.求解難度是指在問題對應的搜索空間內搜索到高質量解的難度.如果問題對應的搜索空間比較簡單,則僅使用本文考慮的兩種簡單搜索方法就可以找到高質量解,這樣就不需要求助更加復雜的搜索方法(例如本文提出的基于多目標優(yōu)化的MULTI方法)了.第1種簡單搜索方法是基于單目標優(yōu)化的遺傳算法(SIMPLE-GA).給定需要預測的程序模塊集M和候選解w,其搜索優(yōu)化目標可以通過如下公式進行計算.

不難看出,該簡單搜索方法將MULTI方法考慮的兩個不同優(yōu)化目標擬合成一個單一優(yōu)化目標(這里僅簡單地將這兩個優(yōu)化目標的權重各自設置為0.5),同時,在擬合時我們將兩個不同優(yōu)化目標的取值歸一到同一取值區(qū)間[0,1]內.

另一種簡單搜索方法是基于多目標優(yōu)化的隨機搜索算法(RANDOM),與MULTI方法相比,其使用隨機搜索代替了其中的遺傳算法.

由于這兩種簡單搜索方法的內部均含有隨機因素,因此我們同樣獨立運行10次,并返回其中最好的結果和平均的結果.同時,將這兩種簡單搜索方法的參數取值(例如種群規(guī)模、最大迭代次數、系數向量成員的有效取值區(qū)間)與MULTI方法保持一致.基于跨項目缺陷預測場景下的比較結果如圖3所示.不難看出,MULTI方法相對于兩種簡單搜索方法在ACC和POPT指標上均可以取的更好的預測性能.除此之外,我們在同項目缺陷預測場景下也得到了相似的結論,由此驗證了FL-SDP問題的求解難度.

Fig.3 Comparision between MULTI with two simple search methods in cross-project defect prediction scenario圖3 跨項目缺陷預測場景下MULTI方法與兩種簡單搜索方法的比較

隨后,我們使用hypervolume(HV)指標來比較MULTI方法與RANDOM方法生成的Pareto前沿的質量.HV指標是多目標優(yōu)化算法評估中常用的一種經典指標[36],其可以很好地衡量Pareto前沿覆蓋的目標空間的容量,因此HV取值越大,表示對應的Pareto前沿質量越高.我們同樣基于跨項目缺陷預測場景,將MULTI方法與RANDOM方法生成的Pareto前沿基于HV值進行了比較,最終結果如圖4所示.通過圖4不難看出,MULTI方法生成的Pareto前沿質量更高.

4.1 針對RQ1的結果分析

同項目缺陷預測場景下,不同方法的Scott-Knott檢驗結果如圖5所示.其中,虛線用于分隔不同的分組,所有方法按照他們的秩進行排序.藍色表示無監(jiān)督學習方法,黑色表示有監(jiān)督學習方法.從圖中不難看出:無論是基于ACC指標還是基于POPT指標,MULTI方法均顯著優(yōu)于Yan等人考慮的無監(jiān)督學習方法和有監(jiān)督學習方法.

Fig.4 Comparision between MULTI with RANDOM based on HV in cross-project defect prediction scenario圖4 跨項目缺陷預測場景下MULTI方法與RANDOM方法在HV值上的比較

Fig.5 Result of Scott-Knott test in within-project defect prediction scenario圖5 同項目缺陷預測場景下的Scott-Knott檢驗結果

隨后,我們基于每個項目來將MULTI方法與基準方法進行比較.我們從基準方法中選出性能最好的兩種有監(jiān)督方法和兩種無監(jiān)督方法.最終結果見表6和表7.

Table 6 MULTI vs.top two supervised and unsupervised methods in within-project defect prediction scenario using ACC表6 同項目缺陷預測場景下MULTI方法與最好的兩種有監(jiān)督方法和無監(jiān)督方法的比較(基于ACC)

Table 7 MULTI vs.top two supervised and unsupervised methods in within-project defect prediction scenario using POPT表7 同項目缺陷預測場景下MULTI方法與最好的兩種有監(jiān)督方法和無監(jiān)督方法的比較(基于POPT)

表中記錄的是對應方法在每個數據集上進行10×10折交叉驗證時,所有預測值中的中位數.這兩個表中的倒數第行表示各個方法在不同數據集上的均值,最后一行的Win/Draw/Loss(簡稱W/D/L)表示MULTI方法顯著優(yōu)于/相似/差于對應方法的數據集的數量.具體來說:

(1) 若基于ACC評測指標,平均來說,MULTI方法與最好的無監(jiān)督方法AMC和RFC相比,其性能有105.81%和118.52%的提高;MULTI方法與最好的有監(jiān)督方法EALR和AB+LMT相比,其性能有123.34%和200.00%的提高.

(2) 若基于Popt評測指標,平均來說,MULTI方法與最好的無監(jiān)督方法AMC和RFC相比,其性能有35.61%和34.97%的提高;MULTI方法與最好的有監(jiān)督方法EALR和AB+J48相比,其性能有38.70%和65.95%的提高.

W/D/L分析結果也進一步確認了MULTI方法的優(yōu)越性.

4.2 針對RQ2的結果分析

跨項目缺陷預測場景下,不同方法的Scott-Knott檢驗結果如圖6所示.從圖中不難看出:無論是基于ACC指標還是基于POPT指標,MULTI方法均要顯著優(yōu)于Yan等人考慮的無監(jiān)督學習方法和有監(jiān)督學習方法.

隨后,我們基于每個跨項目缺陷預測場景來將MULTI方法與基準方法進行比較.我們從基準方法中選出性能最好的兩種有監(jiān)督方法和兩種無監(jiān)督方法.由于篇幅所限,這里并不羅列出具體結果,總體來說:

(1) 若基于ACC評測指標,平均來說,MULTI方法與最好的無監(jiān)督方法AMC和RFC相比,其性能有22.42%和25.66%的提高;MULTI方法與最好的有監(jiān)督方法EALR和RBFN相比,其性能有34.95%和60.81%的提高.

(2) 若基于Popt評測指標,平均來說,MULTI方法與最好的無監(jiān)督方法AMC和RFC相比,其性能有11.45%和10.80%的提高,MULTI方法與最好的有監(jiān)督方法EALR和RBFN相比,其性能有17.92%和37.28%的提高.

Fig.6 Result of Scott-Knott test in cross-project defect prediction scenario圖6 跨項目缺陷預測場景下的Scott-Knott檢驗結果

4.3 針對RQ3的結果分析

在該實驗問題中,我們基于PMI和IFA評測指標,將MULTI方法與基準方法進行比較.由于基于ACC和POPT指標,可能MULTI方法返回的最優(yōu)模型并不一樣,所以本文用MULTI_A和MULTI_P分別表示基于ACC指標和POPT指標下得到的最優(yōu)模型.最終,基于同項目缺陷預測場景和跨項目缺陷預測場景下的結果分別如圖7(a)和圖7(b)所示.不難看出,在考慮20%的測試資源時,MULTI方法需要審查的程序模塊數較多,但在同項目缺陷預測場景中要低于無監(jiān)督學習方法RFC、AMC、WMC、MAX_cc和AVG_cc.在跨項目缺陷預測場景下,要低于無監(jiān)督學習方法RFC和AMC.

IFA指標返回是模型在遇到第1個缺陷模塊時,審查過的無缺陷模塊的數量.最終,基于同項目缺陷預測場景和跨項目缺陷預測場景下的結果分別如圖 8(a)和圖 8(b)所示.在同項目缺陷預測場景中,MULTI_A和MULTI_P分別排名第5和第4.在跨項目缺陷預測場景中,MULTI_A和MULTI_P分別排名第3和第4.

綜上所述,不難看出ACC指標和POPT指標與Huang等人提出的PMI指標和IFA指標之間存在一定的折衷,即MULTI方法雖然在ACC指標和POPT指標上性能更好,但在PMI指標和IFA指標上則取值稍高,因此需要開發(fā)人員根據自己的實際需求做出合理的選擇.但我們也發(fā)現:與最好的兩種無監(jiān)督學習方法(即RFC和AMC)相比,MULTI方法能夠取得更好的ACC值和POPT值;同時,PMI值和IFA值都要好于這兩種無監(jiān)督學習方法.因此,體現了MULTI方法具有一定的競爭性.

Fig.7 Result of Scott-Knott test for PMI圖7 基于PMI指標的Scott-Knott檢驗結果

Fig.8 Result of Scott-Knott test for IFA圖8 基于IFA指標的Scott-Knott檢驗結果

Fig.8 Result of Scott-Knott test for IFA (Continued)圖8 基于IFA指標的Scott-Knott檢驗結果(續(xù))

4.4 進一步討論

4.4.1 與OneWay方法和CBS方法的比較

OneWay[5]是Fu等人提出的最新的一種有監(jiān)督學習方法,其基于訓練集自動從已有的無監(jiān)督方法中選出最好的方法.CBS(classify-before-sorting)方法[6]是Huang等人提出的最新的一種簡單的改進型有監(jiān)督學習方法,其首先對數據集進行一定的預處理(例如特征選擇、類不平衡學習以及對特征取值進行l(wèi)og取值轉化);隨后,基于Logistic回歸建模方法構建模型,在測試集上,根據模型的預測結果將模塊分為兩類:有缺陷的和無缺陷的;隨后,根據模塊代碼規(guī)模將預測為有缺陷類中的模塊按照代碼規(guī)模從小到大進行排序.

和第2.2節(jié)提到的一系列基準方法一樣,OneWay方法和CBS方法均可用于CL-SDP問題和FL-SDP問題.除此之外,作為有監(jiān)督方法,這兩種方法均采用了第 3.4節(jié)所示的同樣的數據預處理方法.MULTI方法與OneWay和CBS方法的比較結果如圖9所示.從圖中不難看出,無論是基于同項目缺陷預測場景還是基于跨項目缺陷預測場景,MULTI方法在ACC評測指標和POPT評測指標上,其性能均要顯著優(yōu)于OneWay方法和CBS方法.

Fig.9 Comparision among MULTI,OneWay and CBS圖9 MULTI方法與OneWay和CBS方法的比較

4.4.2 基于F1指標的比較結果

除了ACC和POPT評測指標以外,本文也考慮缺陷預測研究中經常使用的F1評測指標[1,31].具體來說,假設僅能使用20%的測試資源,則使用precision表示審查到的模塊中缺陷模塊所占的比例,使用recall(即ACC)表示審查到的缺陷模塊占所有缺陷模塊的比例,F1則是precision值和recall值的調和均值.以跨項目缺陷預測場景為例,本文將MULTI方法與Yan等人采用的方法[8]、OneWay方法[5]以及CBS方法[6]進行了比較,結果如圖10所示.不難看出,MULTI方法均要顯著優(yōu)于這些基準方法.

Fig.10 Result of Scott-Knott test in cross-project defect prediction scenario based on F1圖10 跨項目缺陷預測場景下的Scott-Knott檢驗結果(基于F1評測指標)

4.4.3 時間開銷分析

我們進一步分析MULTI方法的模型構建時間開銷.由于無監(jiān)督方法實現簡單,因此其運行時間極短,本文主要將MULTI方法與不同的有監(jiān)督學習方法(包括Yan等人考慮的方法、OneWay方法和CBS方法)進行比較.這些方法運行在MAC OS High Sierra操作系統(tǒng)上(CPU 2.3 GHz Intel Core i5,內存8GB),最終結果見表8.

Table 8 Model construction time of different FL-SDP supervised methods (s)表8 不同FL-SDP有監(jiān)督方法的構建時間 (秒)

Table 8 Model construction time of different FL-SDP supervised methods (Continued) (s)表8 不同FL-SDP有監(jiān)督方法的構建時間(續(xù)) (秒)

通過表8不難發(fā)現:MULTI方法的模型構建時間雖然都高于基準方法,但處于可接受的范圍之內(介于10s～17s之間),其主要計算開銷集中在種群演化階段,即每一輪中,種群內染色體適應值的計算以及常見演化算子的計算開銷等.

4.5 有效性影響因素分析

這一節(jié)主要分析可能影響到本文實證研究結論有效性的影響因素,具體說明如下.

(1) 內部有效性主要涉及到可能影響到實驗結果正確性的內部因素.第一個有效性影響因素是代碼實現是否正確,為了減少該影響因素的影響,我們參考了Yang等人[4]、Wu和Menzies[5]、Yan等人[8]提供的代碼,并確保與他們實證研究的結果保持一致.除此之外,我們使用了第三方提供的成熟框架,例如來自Matlab和R中的機器學習包.其次,在ACC指標和PMI指標設定時,我們假設可用的測試資源比例是20%,該設定與已有研究工作保持一致[4,13].

(2) 外部有效性主要涉及到實驗研究得到的結論是否具有一般性.為了確保實證研究結論的一般性,我們選擇了FL-SDP問題研究中經常使用的PROMISE數據集,該數據集累計搜集了10個開源項目,選擇的這些項目是開源項目中具有一定代表性的項目,同時,這些項目也覆蓋了不同類型的應用領域,可以確保研究結論具有一定的代表性.

(3) 結論有效性主要涉及到使用的評測指標是否合理.本文重點考慮了測試代價感知的評測指標POPT,ACC和F1指標;除此之外,我們也深入分析Huang等人[6]提出其他兩個評測指標PMI和IFA.

5 總結和展望

本文針對FL-SDP問題,將基于多目標優(yōu)化的MULTI方法與Yan等人考慮的基準方法[8]、Wu和Menizes提出的OneWay方法[5]以及Huang等人提出的CBS方法[6]進行了深入的分析和比較.結果表明:無論在同項目缺陷預測場景還是跨項目缺陷預測場景,若考慮代價敏感的評測指標,MULTI方法的預測性能均要顯著優(yōu)于這些基準方法,從而表明MULTI方法在FL-SDP問題上同樣值得關注.

本文仍存在很多值得探討的下一步工作:首先,我們希望能夠從開源項目和商業(yè)項目中搜集更多的數據集,來驗證本文所得的實證研究結論是否具有一般性;其次,本文考慮的數據集預處理方法較為簡單,未來可以考慮更為有效的特征選擇方法或者類不平衡學習方法[33,37];接著,需要考慮與最新提出的FL-SDP方法進行比較,例如Nam等人提出的CLA和CLAMI方法[38]以及Zhang等人提出的基于譜聚類(spectral clustering)的方法[39]等;最后,本文僅簡單使用模塊規(guī)模來度量模塊的測試開銷,該假設較為簡單[40],在下一步工作中,需要考慮更為合理的測試開銷度量方法.

為了方便研究人員重現本文的實證研究,我們將相關代碼和實驗結果進行了共享,其訪問網址是https://github.com/Hecoz/FL-SDP.