基于源文件可疑度的軟件缺陷定位方法研究

陸皖麟，王 梟，馮 超，武 劍

(1.中國人民解放軍66133部隊(duì)， 北京 100043； 2.中國人民解放軍66135部隊(duì)， 北京 100043)

軟件是由不同功能模塊組成的系統(tǒng)集合，其中包含了大量源文件。當(dāng)源文件中包含缺陷時，軟件系統(tǒng)的部分功能將會發(fā)生損壞或?qū)е抡麄€軟件系統(tǒng)癱瘓[1]。為對軟件質(zhì)量加以保證，規(guī)避其中潛藏風(fēng)險，缺陷定位成為必不可少的關(guān)鍵步驟[2]。

本文將缺陷定位理論和缺陷預(yù)測方法相結(jié)合，提出了新的可疑度概念及其計(jì)算方法，將缺陷定位到源文件。主要從關(guān)聯(lián)層—源文件和待定位缺陷的相關(guān)性，預(yù)測層—源文件的易錯程度兩個層次對每個源文件進(jìn)行度量，度量結(jié)果定義為源文件的可疑度，可疑度越高，作為缺陷修復(fù)對象的可能性越大。

1 源文件可疑度定位方法框架

通過軟件缺陷數(shù)據(jù)分析和缺陷定位相關(guān)理論[3]，構(gòu)建出基于源文件可疑度的缺陷定位方法框架，如圖1所示。其主要過程分為兩個層，關(guān)聯(lián)層首先依據(jù)缺陷數(shù)據(jù)的不同特征屬性分析待定位缺陷和歷史缺陷之間的相似關(guān)系，引入歷史缺陷數(shù)據(jù)的修復(fù)信息對待定位缺陷數(shù)據(jù)和源文件進(jìn)行相關(guān)性分析，并用相關(guān)度來度量源文件和待定位缺陷的相關(guān)性大小。預(yù)測層分析源文件的內(nèi)在屬性，例如代碼規(guī)模，函數(shù)圈復(fù)雜度，環(huán)路復(fù)雜度，文件修改次數(shù)等[4]，源代碼的不同度量元數(shù)據(jù)隱含著一定規(guī)律的缺陷信息，利用度量元數(shù)據(jù)構(gòu)建的預(yù)測模型可以預(yù)測源文件包含相關(guān)缺陷的傾向性，即源文件的易錯程度。

圖1 基于源文件可疑度定位的方法流程

通過相關(guān)度和易錯程度獲得源文件的可疑度，定義可疑度計(jì)算公式表示為

Score=(1-a)Score1+aScore2

其中:Score1表示源文件和待定位缺陷的相關(guān)度，Score2表示源文件的易錯程度，參數(shù)a用來調(diào)整相關(guān)度和易錯程度在可疑度定位過程中的權(quán)重，0

2 關(guān)聯(lián)層分析

關(guān)聯(lián)層分析的目的是標(biāo)記與待定位缺陷相關(guān)的源文件，并分析待定位缺陷和源文件之間的相關(guān)度[5]。主要分為3步：缺陷數(shù)據(jù)的相似度分析、歷史缺陷和源文件的關(guān)聯(lián)分析、待定位缺陷與源文件的相關(guān)度分析，過程如圖2所示。

圖2 關(guān)聯(lián)層分析過程

2.1 缺陷數(shù)據(jù)的相似度分析

根據(jù)軟件缺陷數(shù)據(jù)的特點(diǎn)，首先從缺陷記錄信息中提取能夠表征缺陷數(shù)據(jù)的特征屬性，依據(jù)向量空間模型思想將缺陷特征屬性抽象化處理，并建立缺陷數(shù)據(jù)的數(shù)學(xué)矩陣模型；其次，結(jié)合樣本之間的相似系數(shù)和距離系數(shù)構(gòu)建改進(jìn)后的模糊相似矩陣，通過傳遞閉包運(yùn)算得到模糊等價矩陣；最后利用模糊等價矩陣獲取待定位缺陷數(shù)據(jù)和歷史修復(fù)缺陷的相似度。該方法能夠同時對大規(guī)模的缺陷數(shù)據(jù)進(jìn)行處理，主要分為5個步驟：

1) 特征屬性提取及抽象化編碼。通過對軟件缺陷數(shù)據(jù)的分析，共提取10種特征屬性用于缺陷之間的相似度分析[6]，具體內(nèi)容如表1所示。

表1 軟件缺陷數(shù)據(jù)的特征屬性

抽象化編碼具體規(guī)范：如果屬性f取離散化的數(shù)值，且0<|f|<∞，則把屬性取值編碼為“1”，“2”，…；如果屬性f取連續(xù)的數(shù)值，且0<|f|<∞，則把屬性取值編碼為“1”，“2”，…；如果屬性f值缺失(即缺陷i或j缺少屬性f的度量值)，則xif=xjf=0。根據(jù)上述抽象化編碼規(guī)范，得其編碼方式如表2所示。

表2 缺陷數(shù)據(jù)的抽象編碼

當(dāng)存在n個缺陷數(shù)據(jù)時，全部進(jìn)行抽象化編碼后可映射為n個缺陷特征向量，進(jìn)一步表示為一個多維矩陣模型，矩陣的每個行向量表示一個缺陷數(shù)據(jù)，每個列向量表示缺陷數(shù)據(jù)的一個特征屬性，元素xij表示第i個缺陷數(shù)據(jù)的第j個特征屬性的編碼值，其數(shù)學(xué)形式表示為

(1)

2) 數(shù)據(jù)規(guī)范化處理。缺陷數(shù)據(jù)的相似度分析過程中，缺陷集合X={x1,x2,…,xn}表示的是包含10個特征屬性的所有n個缺陷對象。為了消除缺陷屬性編碼值數(shù)量級或單位的差別，需要對抽象化的缺陷數(shù)據(jù)進(jìn)行規(guī)范處理，將每一特征屬性的編碼值規(guī)范到[0,1]，消除不同量綱帶來的影響，進(jìn)一步提升缺陷數(shù)據(jù)相似度分析方法的效果。筆者采用平移極差變換的方法將缺陷數(shù)據(jù)規(guī)范化處理，如式(2)：

(2)

3) 模糊相似矩陣的構(gòu)建。對于缺陷數(shù)據(jù)的非空集合X(x1,x2…,xn)，為計(jì)算集合X中缺陷xi和缺陷xj之間的模糊相似關(guān)系,定義X和X之間的模糊關(guān)系R滿足R∈f(X×X)，為X和X的直積，即X×X={(xi,xj)|xi∈X,xj∈X}。其中，R(xi,xj)表示元素xi和元素xj之間的相似度，且滿足R(xi,xj)→[0,1]。則集合X中缺陷之間的模糊關(guān)系可表示為m×n的模糊相似矩陣：

(3)

簡記為R=(rij)n×n，矩陣中rij=R(xi,xj)表示X中缺陷i和缺陷j之間的相似關(guān)系。

通過規(guī)范化后的缺陷數(shù)據(jù)建立上述模糊相似矩陣，考慮10種缺陷數(shù)據(jù)特征屬性對距離貼近程度和相關(guān)關(guān)系程度的影響不同，采用距離系數(shù)描述缺陷屬性之間的距離貼近程度，相似系數(shù)描述缺陷屬性之間的相關(guān)關(guān)系程度。因此將相關(guān)系數(shù)和距離系數(shù)結(jié)合共同構(gòu)建缺陷數(shù)據(jù)之間的模糊相似矩陣R= (rij)n×n，進(jìn)一步提高相似度分析結(jié)果的準(zhǔn)確性。

相似系數(shù)的計(jì)算公式為

(4)

距離系數(shù)計(jì)算公式為

(5)

最終相似度計(jì)算公式為

rij=δ1sij+δ2dij

(6)

其中，i,j=0,…,n，sij和dij分別表示缺陷數(shù)據(jù)xi和xj的相似系數(shù)和距離系數(shù)，δ1，δ2表示相似系數(shù)和距離系數(shù)各占比重，其中δ1+δ2=1，筆者將相似系數(shù)和距離系數(shù)賦予相同的比重，即δ1=δ2=0.5，由此可以構(gòu)造出模糊相似矩陣R= (rij)n×n。

如果模糊相似矩陣R= (rij)n×n滿足自反性、對稱性、傳遞性，則rij能夠準(zhǔn)確表示缺陷i和缺陷j之間的相似度，通過模糊相似矩陣R= (rij)n×n的構(gòu)建方法分析，其滿足自反性和對稱性，但是不滿足傳遞性，所以需進(jìn)行下一步模糊等價矩陣的構(gòu)建。

4) 模糊等價矩陣的構(gòu)建。為了使rij能夠如實(shí)反映缺陷i和缺陷j之間的相似關(guān)系，需要對模糊相似矩陣進(jìn)行改造，即構(gòu)建模糊等價矩陣T。筆者采用求傳遞閉包t(R)的經(jīng)典算法—平方法計(jì)算模糊等價矩陣。

平方法的主要過程是將模糊相似矩陣R不斷自乘[7]，當(dāng)自乘過程首次出現(xiàn)Rk·Rk=Rk時，所得到的傳遞閉包Rk即為模糊等價矩陣T。因?yàn)槟：葍r矩陣滿足自反性，對稱性和傳遞性，所以模糊等價矩陣T中的元素tij能夠準(zhǔn)確表示缺陷i和缺陷j之間的相似度，根據(jù)模糊等價矩陣T中能夠得到任一缺陷和其他缺陷的相似度。

5) 截矩陣的構(gòu)建。給定任意α∈[0,1]的閾值，對于X和X之間的模糊關(guān)系T，截集Tα表示為Tα={(xi,xj)∈X×X|tij≥α}。對于二元組(xi,xj)∈Tα，表示缺陷xi和缺陷xj滿足閾值α水平的相似關(guān)系。

定義：設(shè)給定模糊等價矩陣T=(tij)n×n，對任意α∈[0,1]，記

Tα=(αtij)n×n

(7)

其中：

(8)

則稱Tα=(αtij)n×n為T的α截矩陣。

模糊等價矩陣的α截矩陣是一個布爾矩陣，通過缺陷數(shù)據(jù)集合建立模糊等價矩陣T之后，就能夠依據(jù)截矩陣將某行或某列為1的對象劃歸到一類。

假設(shè)，缺陷數(shù)據(jù)1，2，3之間的模糊等價矩陣為

設(shè)置閾值α=0.5，則T的α截矩陣為

為確定與缺陷2相似的缺陷，只需提取Tα中的第2行或第2列中為1的元素，其中，t23或t32為1表示與缺陷2和缺陷3滿足閾值水平的相似關(guān)系。

設(shè)置不同的α閾值，缺陷之間的相似關(guān)系提取結(jié)果也不同。在α從0～1的變化過程中，模糊等價矩陣T的α截矩陣也會隨之改變，α越大提取的缺陷之間的相似度也越高。

2.2 歷史缺陷和源文件的關(guān)聯(lián)

歷史缺陷信息不僅包含缺陷的各種特征屬性，還包括缺陷修復(fù)的源文件位置信息等，根據(jù)其修復(fù)信息可以追溯每個缺陷所變更的程序源文件，歷史修復(fù)缺陷和源文件的相關(guān)性分析就是建立歷史缺陷及其修復(fù)的源文件的鏈接關(guān)系。

定義(缺陷修復(fù)位置關(guān)系圖)：把缺陷和源文件抽象化在圖中用各個節(jié)點(diǎn)表示，位置關(guān)系G=(S，F(xiàn))表示缺陷和源文件的位置關(guān)系，其中S代表所有缺陷數(shù)據(jù)，F(xiàn)代表程序源文件。如圖3所示，缺陷s1所修改的源文件為f2，缺陷s2所修改的源文件為f4，連接線表示缺陷和源文件之間的鏈接關(guān)系。

圖3 缺陷修復(fù)位置關(guān)系

2.3 待定位缺陷和源文件的相關(guān)度分析

當(dāng)一個待定位缺陷B提交時，首先需要對其相似的歷史修復(fù)缺陷和歷史缺陷所變更的源文件進(jìn)行分析，然后構(gòu)造一個3層異構(gòu)圖，如圖4所示。第1層的節(jié)點(diǎn)表示待定位缺陷B；第2層表示歷史修復(fù)缺陷中與待定位缺陷B相似的歷史修復(fù)的缺陷數(shù)據(jù)集S，其相似程度依據(jù)閾值大小進(jìn)行設(shè)置；第3層表示歷史修復(fù)缺陷所變更的程序源文件集合F，通過對歷史缺陷數(shù)據(jù)的修復(fù)信息進(jìn)行查詢，建立歷史修復(fù)缺陷數(shù)據(jù)和源文件的鏈接關(guān)系，表示這些源文件對第2層的歷史缺陷數(shù)據(jù)產(chǎn)生影響。

圖4 待定位B缺陷和源文件的關(guān)聯(lián)關(guān)系

因此，待定位缺陷和程序源文件的相關(guān)度分析過程中，首先需要對待定位缺陷和歷史修復(fù)缺陷進(jìn)行相似度分析，建立第1層和第2層的關(guān)聯(lián)；然后根據(jù)歷史修復(fù)缺陷所變更的源文件信息建立第2層和第3層的關(guān)聯(lián)；最后得到第1層待定位缺陷和第3層程序源文件的相關(guān)度。其中，待定位缺陷和程序源文件的相關(guān)度Score1的計(jì)算公式如下：

其中，Similarity(B,Si)表示待定位缺陷B和歷史修復(fù)缺陷Si的相似度；m表示所有與程序源文件Fi相關(guān)聯(lián)的缺陷Si的數(shù)量；n表示Si相關(guān)的源文件個數(shù)。

3 預(yù)測層分析

預(yù)測層分析是通過缺陷預(yù)測方法對關(guān)聯(lián)層標(biāo)記的源文件進(jìn)行易錯程度分析的過程。將缺陷密度[8]作為源文件易錯程度的度量，首先選取對缺陷密度影響較大的度量元構(gòu)建源文件缺陷密度預(yù)測模型，然后對源文件的缺陷密度進(jìn)行預(yù)測，獲得源文件易錯程度的度量。主要思路是將源文件的度量元作為預(yù)測過程的輸入，將源文件的缺陷密度作為預(yù)測過程的輸出，通過相應(yīng)的預(yù)測方法建立度量元和缺陷密度之間的關(guān)系，用于下一步的預(yù)測，如圖5所示。

圖5 缺陷定位的預(yù)測層分析框架

3.1 源文件度量元的選擇

為保證源文件缺陷密度預(yù)測的準(zhǔn)確性，需對缺陷密度和度量元進(jìn)行相關(guān)性分析，選擇對缺陷密度影響較大的度量元作為預(yù)測模型的輸入。采用Spearman秩相關(guān)系數(shù)的分析方法，用來計(jì)算度量元和缺陷密度之間的相關(guān)系數(shù)。

給定度量元和缺陷密度的n組源文件數(shù)據(jù)，可表示為X(x1,x2,…,xn)和Y(y1,y2,…,yn)。其中，xi表示第i個源文件的度量元的值，yi表示第i個源文件的缺陷密度。首先將和中數(shù)據(jù)進(jìn)行組對，即(x1,y1),(x2,y2),…,(xn,yn)。然后將xi和yi分別按照數(shù)值大小進(jìn)行排列，獲得和各自所占名次(即秩)，記作Ri和Si。由此可以得到數(shù)據(jù)組(x1,y1)，(x2,y2)，…，(xn,yn)的n對秩，即(R1,S1),(R2,S2),…,(Rn,Sn)。利用Spearman等級相關(guān)系數(shù)衡量度量元X和缺陷密度Y之間的相關(guān)程度，可表示為

(9)

標(biāo)準(zhǔn)的相關(guān)系數(shù)和相關(guān)關(guān)系的評價指標(biāo)如表3所示，選取滿足相關(guān)系數(shù)閾值的源文件度量元，構(gòu)建源文件的缺陷密度預(yù)測模型。

3.2 預(yù)測模型構(gòu)建

支持向量機(jī)(Support Vector Machine，SVM)在小樣本、非線性和高維度空間的模式識別中具有獨(dú)特優(yōu)勢[9-10]，通過支持向量回歸(Support Vector Regression，SVR)構(gòu)建源文件缺陷密度預(yù)測模型。

表3 相關(guān)關(guān)系評價指標(biāo)

源文件缺陷密度預(yù)測就是給定數(shù)據(jù)樣本集合{(x1,y1),…,(xi,yi),…,(xl,yl)}，其中，xi表示源文件的度量元向量，yi表示源文件缺陷密度，xi∈Rn,yi∈R，i=1，2，…，l。在Rn上尋找f(x)=w·x+b來擬合，使集合點(diǎn)與超平面的誤差較小，定義正則化的誤差函數(shù):

假設(shè)允許模型的預(yù)測值與真實(shí)值有一定的偏差ε，則在模型中定義一個損失函數(shù)，用于調(diào)和預(yù)測值和實(shí)際值的誤差，這種類型的函數(shù)就是ε不敏感損失函數(shù)。

ε不敏感損失函數(shù)定義為

Lε=|yi-f(xi)|ε=max{0,|yi-f(xi)|-ε}

利用定義的ε不敏感損失函數(shù)忽略一定范圍內(nèi)的誤差，當(dāng)樣本點(diǎn)位于兩條虛線內(nèi)的管道時，認(rèn)為該點(diǎn)沒有損失，兩條虛線構(gòu)成的管道為ε-管道。處于虛線上的樣本決定了ε-管道的位置，這部分樣本稱為“支持向量”，如圖6所示。

圖6 非線性回歸函數(shù)的不敏感帶

回歸問題則等價于最優(yōu)化問題：

在上述模型中，需要事先確定損失函數(shù)中的參數(shù)ε，筆者基于上述原理構(gòu)建出ν-SVR的缺陷密度預(yù)測模型，將ε的值自動最小化，并使用非負(fù)常數(shù)ν控制支持向量的數(shù)目。另外選擇合適的核函數(shù)K(xi,xj)，把上述回歸問題轉(zhuǎn)化為最優(yōu)化問題：

(10)

對偶問題為

(11)

其中，ν和C為常數(shù)。最終建立的SVR預(yù)測模型為

(12)

4 實(shí)驗(yàn)及分析

4.1 實(shí)驗(yàn)設(shè)計(jì)

為了體現(xiàn)本文缺陷定位方法的通用性，選用Eclipse平臺的開源項(xiàng)目AspectJ中的缺陷數(shù)據(jù)。該項(xiàng)目中有完整的缺陷數(shù)據(jù)庫和歷史變更記錄，并具有不同數(shù)量的缺陷和源代碼文件。將AspectJ項(xiàng)目中的缺陷數(shù)據(jù)作為歷史缺陷，并從中選取2002年7月至2006年10月的286個缺陷數(shù)據(jù)作為待定位缺陷，其中的源文件共有6 485個。

實(shí)驗(yàn)提取286個缺陷數(shù)據(jù)，將每個缺陷數(shù)據(jù)進(jìn)行抽象化編碼。通過關(guān)聯(lián)分析和預(yù)測分析，獲取每個缺陷數(shù)據(jù)所對應(yīng)的源文件可疑度排序，完成每個缺陷的定位工作。最后通過分析驗(yàn)證上述缺陷數(shù)據(jù)實(shí)際所修復(fù)的源文件位置，對定位結(jié)果的準(zhǔn)確性進(jìn)行評估。

4.2 結(jié)果分析

為評估本文缺陷定位方法的效果，依據(jù)現(xiàn)階段普遍采用的TopN(TopN Rank)、MRR(Measurement Result Recording) 、MAP(Mean Average Precision)3項(xiàng)評估指標(biāo)對該方法的實(shí)驗(yàn)結(jié)果進(jìn)行對比。實(shí)驗(yàn)對比4種缺陷定位方法，方法1采用VSM定位方法[11]；方法2采用BugScout定位方法[12]；方法3為本文缺陷定位方法中僅采用待定位缺陷和源文件的相關(guān)度(a=0)，相似度閾值為0.55時的定位結(jié)果。方法4為本文基于源文件可疑度(a=0.2)，核函數(shù)為徑向基函數(shù)(RBF)的定位結(jié)果，上述4種方法的定位結(jié)果如表4所示。

表4 不同方法的缺陷定位結(jié)果

本文針對TOP1，TOP5，TOP10的準(zhǔn)確率對上述4種方法進(jìn)行對比分析，對比結(jié)果如圖7所示。

圖7 開源項(xiàng)目AspectJ中不同缺陷定位方法結(jié)果

通過圖7對比結(jié)果可知，基于可疑度的缺陷定位方法總體效果較好。TOPN表示可疑度排序的前N個源文件中包含需要修復(fù)的源文件的準(zhǔn)確率，從TOP1的角度分析，四種方法的定位效果基本相似，因?yàn)槎ㄎ粏栴}本身的復(fù)雜性，相對來說TOP1的準(zhǔn)確性仍處在較低的水平，本文定位方法的優(yōu)勢并未得到突顯。從TOP5和TOP10的角度分析，方法4相比于方法1和方法2具有較為明顯的優(yōu)勢，其中方法1和方法2的定位過程是從信息檢索的角度出發(fā)，檢索缺陷報告和源文件中代碼的文本相似度，但是一般情況下缺陷報告采用自然語言描述，源文件采用程序語言描述，因?yàn)樵次募腿毕輬蟾娴恼Z言空間不同，所以對定位效果有一定影響，容易產(chǎn)生不理想的結(jié)果。

方法3所得的源文件可疑度排序列表，雖然能夠定位到程序源文件，但是忽略了缺陷修復(fù)的行為規(guī)律和源代碼自身代碼質(zhì)量。方法4既考慮了源文件和待定位缺陷之間的相關(guān)度，又考慮了源文件的內(nèi)在結(jié)構(gòu)和歷史修復(fù)信息即對源文件易錯程度的預(yù)測。上述實(shí)驗(yàn)表明：采用本文方法對缺陷進(jìn)行定位能夠取得較好的效果。