惠子青, 劉曉燕, 嚴(yán) 馨

(昆明理工大學(xué) 信息工程與自動(dòng)化學(xué)院， 云南 昆明 650500)

軟件可靠性是軟件工程領(lǐng)域一個(gè)重要分支，在軟件保障中具有重要作用[1]。軟件可靠性是影響軟件質(zhì)量的最重要因素，評(píng)價(jià)軟件可靠性的方法之一是分析軟件的測(cè)試過程[2]。為了能夠準(zhǔn)確評(píng)估軟件的可靠性，現(xiàn)已開發(fā)出上百種應(yīng)用于實(shí)際項(xiàng)目的軟件可靠性增長模型(Software Reliability Growth Models，SRGM)。開發(fā)出的這些模型都是基于各種各樣的假設(shè)，所以模型的通用性和預(yù)測(cè)精度不高。其中最經(jīng)典的非齊次泊松過程(non-homogeneous Poisson process，NHPP)類軟件可靠性增長模型，它的假設(shè)條件[3]是：1)軟件失效遵循一個(gè)NHPP過程；2)在任何時(shí)刻軟件的失效都是由軟件中存在的故障引起的；3)在任何時(shí)間序列構(gòu)成的時(shí)間區(qū)間中檢測(cè)到的故障數(shù)是相互獨(dú)立的；4)在任何時(shí)刻軟件的失效強(qiáng)度與軟件中存在的故障數(shù)成正比。由于非參數(shù)化可靠性增長模型不需要估計(jì)參數(shù)，且不需要做出條件假設(shè)，只需要將歷史故障數(shù)據(jù)作為輸入，通過機(jī)器學(xué)習(xí)的相關(guān)算法訓(xùn)練非參數(shù)化模型，因此非參數(shù)化可靠性增長模型可以獲得更高的預(yù)測(cè)精度和更強(qiáng)的通用性。

非參數(shù)化的SRGM使用機(jī)器學(xué)習(xí)技術(shù)中的人工神經(jīng)網(wǎng)絡(luò)、遺傳編程和支持向量機(jī)(Support Vector Machine，SVM)相關(guān)的技術(shù)知識(shí)來深入了解和預(yù)測(cè)軟件可靠性。其中支持向量機(jī)是基于結(jié)構(gòu)風(fēng)險(xiǎn)最小化原則，尋求最小化泛化誤差(訓(xùn)練誤差和置信區(qū)間)的上界，這樣具有更高的泛化能力。而經(jīng)驗(yàn)風(fēng)險(xiǎn)誤差原則僅最小化訓(xùn)練誤差，支持向量機(jī)另一個(gè)重要特點(diǎn)是訓(xùn)練支持向量機(jī)等同于解線性約束的二次型規(guī)劃問題。這樣SVM有全局最優(yōu)的唯一解[4]。基于支持向量回歸(Support Vactor Regerssion，SVR)技術(shù)的非參數(shù)化SRGM在軟件測(cè)試領(lǐng)域已經(jīng)被廣泛應(yīng)用且展現(xiàn)出了良好的學(xué)習(xí)性能，但是在實(shí)際應(yīng)用時(shí)也存在一些局限性。第一個(gè)問題是在訓(xùn)練數(shù)據(jù)集很小的情況下，訓(xùn)練集不能充分學(xué)習(xí)和構(gòu)建正確的可靠性預(yù)測(cè)模型，這將會(huì)導(dǎo)致偏差較大甚至錯(cuò)誤的預(yù)測(cè)結(jié)果。第二個(gè)問題是在軟件測(cè)試過程中被檢測(cè)到的第一個(gè)故障對(duì)軟件可靠性的影響與最后一個(gè)不同。比如在軟件測(cè)試早期階段發(fā)現(xiàn)的故障大都是“簡(jiǎn)單”故障，對(duì)軟件可靠性影響不大，后期的故障如果盲目刪除，將有可能引入新的故障，會(huì)導(dǎo)致軟件發(fā)生實(shí)質(zhì)性變化，這與模型當(dāng)中失效次數(shù)獨(dú)立性的假設(shè)條件是相違背的。上述第一個(gè)問題的解決方法是假設(shè)訓(xùn)練集的元素是不均勻的概率分布，并將其用于最小化風(fēng)險(xiǎn)度量的優(yōu)化問題。第二個(gè)問題的解決方法是通過為訓(xùn)練集的元素分配不同的權(quán)重。其中一種簡(jiǎn)單的方法是分配排序權(quán)重，在軟件測(cè)試的初期將小權(quán)重分配給訓(xùn)練集的第一個(gè)元素，在軟件測(cè)試的后期將較大的權(quán)重分配給后面元素。

針對(duì)上述問題，本文提出了一種基于SVR的非參數(shù)化的軟件可靠性增長模型(BT-SRGM)，其核心思想是通過一系列特殊規(guī)則產(chǎn)生的權(quán)重來代替分配給訓(xùn)練數(shù)據(jù)元素的精確權(quán)重。針對(duì)少量的訓(xùn)練數(shù)據(jù)集，根據(jù)極小極大策略，構(gòu)建一組可選擇的分布集合，并在選擇區(qū)間的上界進(jìn)行最小化計(jì)算，最終得到模型參數(shù)。

1 支持向量機(jī)回歸

回歸分析的目標(biāo)是估計(jì)Rm中一組采樣點(diǎn)x(x1,x2,…,xn)與目標(biāo)值y(y1,y2,…,yn)之間函數(shù)f(x)的依賴關(guān)系。首先假設(shè)數(shù)據(jù)集S={(x1,y1),(x2,y2),…,(xn,yn)}，其中xi∈Rm表示包含m個(gè)特征的特征向量，yi∈Rm表示映射輸出值，其中〈·,·〉表示內(nèi)積。支持向量機(jī)可以用(1)式所示的函數(shù)來擬合訓(xùn)練數(shù)據(jù)：

f(x)=〈a,φ(x)〉+b,

(1)

其中a=(a1,a2,…,am)和b是函數(shù)f(x)的參數(shù)。φ(x)是Rm→G的一個(gè)非線性映射,G表示一個(gè)高維特征空間。

經(jīng)驗(yàn)風(fēng)險(xiǎn)是對(duì)訓(xùn)練集中所有的樣本點(diǎn)損失函數(shù)的平均最小化，其中損失函數(shù)表示預(yù)測(cè)值f(x)與實(shí)際值y之間的差[5]。經(jīng)驗(yàn)風(fēng)險(xiǎn)越小說明模型f(x)對(duì)訓(xùn)練集的擬合程度越好。標(biāo)準(zhǔn)的SVR技術(shù)是假設(shè)訓(xùn)練點(diǎn)的概率分布為非參數(shù)的概率分布函數(shù)，其使用導(dǎo)致經(jīng)驗(yàn)預(yù)期風(fēng)險(xiǎn)為

(2)

其中l(wèi)是不敏感參數(shù)ε的損失函數(shù)，其定義為

(3)

(4)

這里給出不精確加權(quán)的兩個(gè)性質(zhì)：①權(quán)值是非負(fù)的;②w1+w2+…+wn=1。

C>0是一個(gè)常數(shù)且決定了f(x)的平滑度與ε的差量，通過系數(shù)a和b值的最小化來估計(jì)規(guī)范化風(fēng)險(xiǎn)函數(shù)：

(5)

(6)

支持向量機(jī)不直接求解φ(xi)和φ(xj)，而是用核函數(shù)代替它。核方法避免了非線性映射φ(·)的具體形式，而且不需要特征空間的內(nèi)積運(yùn)算。只要滿足Mercer條件[6]的函數(shù)都可作為核函數(shù)，這樣就可以轉(zhuǎn)化為對(duì)偶優(yōu)化問題：

(7)

(8)

其中σ是確定幾何結(jié)構(gòu)的內(nèi)核參數(shù)，回歸函數(shù)f(x)可以用拉格朗日乘數(shù)法表示：

(9)

(10)

如果固定系數(shù)a、b的值，變量w和約束條件P會(huì)有一個(gè)線性規(guī)劃集合。因?yàn)镻是凸的，所以在集合的極值點(diǎn)之間可以找到最優(yōu)解。如果極值點(diǎn)的個(gè)數(shù)為n個(gè),則可以將上述問題轉(zhuǎn)化為標(biāo)準(zhǔn)最優(yōu)化問題

(11)

(12)

2 權(quán)重的產(chǎn)生與分配方法

基于SVR技術(shù)的非參數(shù)化SRGM在實(shí)際應(yīng)用中存在兩種缺陷：1)在訓(xùn)練數(shù)據(jù)集較少的情況下，ε-污染模型的產(chǎn)生可以加強(qiáng)非參數(shù)化模型的學(xué)習(xí)深度；2)在軟件測(cè)試過程中被檢測(cè)到的第一個(gè)故障對(duì)軟件可靠性的影響與最后一個(gè)不同，在調(diào)試過程中通過權(quán)重的分配凸顯獲得數(shù)據(jù)的重要性。利用數(shù)學(xué)中取交集的思想，將ε-污染模型和動(dòng)態(tài)權(quán)值分配方法相結(jié)合，這樣就構(gòu)建了一種通用性更好、預(yù)測(cè)精度更高的非參數(shù)化的SRGM，我們將這種新結(jié)合的SRGM命名為BT-SRGM。

2.1 不確定ε-污染模型

不確定ε-污染模型產(chǎn)生的權(quán)重集合P(ε,w)，其中w=(w1,…,wn)：

wi=(1-ε)pi+εhi，

(13)

2.2 比較產(chǎn)生的權(quán)重

我們給出兩個(gè)條件：①w1≤w2≤…≤wn；②w1+w2+…+wn=1。

由以上式子可知，將權(quán)重w(w1,…,wn)的集合定義為M，則其有以下性質(zhì)：①wi-wi-1≥0，i=2,…,n；②wi≥0,i=1,…,n。

需要特別說明的兩種情況：①只有一個(gè)非零權(quán)重分布集合，最后一個(gè)加權(quán)向量起決定性作用；②權(quán)重分布呈現(xiàn)均勻分布。

2.3 兩個(gè)權(quán)重的交集

圖1 單純形中兩組權(quán)重的交點(diǎn)為n=3

在研究P(ε)和M的交集之前，用標(biāo)準(zhǔn)單位單純型來考慮n=3時(shí)的交集，圖1說明了單位單純形中每個(gè)點(diǎn)都可能是加權(quán)向量，(w1,w2,w3)這個(gè)集合對(duì)應(yīng)三角形ABC的限制區(qū)域。P(ε)是小三角形限制區(qū)域。它們的交叉點(diǎn)受陰影區(qū)的限制，由圖可看出兩個(gè)單獨(dú)權(quán)重要比權(quán)重集大得多。交集的權(quán)重向單純形的最后一個(gè)頂點(diǎn)移動(dòng)，這就意味著最后一個(gè)元素要獲得最大的權(quán)重，對(duì)于P(ε)來說，小單純形限制了最后一個(gè)元素獲得過大的權(quán)重值[8]。

上面給出了兩個(gè)權(quán)重P(ε)和M的極值點(diǎn)交集，它們的交集保留了兩組元素的共同優(yōu)點(diǎn)，這是求解s=n規(guī)劃問題的必要條件。每一個(gè)優(yōu)化問題都由一個(gè)極值點(diǎn)w(k)(k=1,…,n)定義，因此，使用n個(gè)標(biāo)準(zhǔn)加權(quán)的SVR很容易求解極值點(diǎn)。

3 BT-SRGM的算法

用偽代碼描述了BT-SRGM的工作過程，如下所示：

要求：S(訓(xùn)練集)，參數(shù)ε,σ=(σ1,…,σn)，C=(C1,…,Ct)

令f(Xn+1)

{S訓(xùn)練集，S測(cè)試集}：S←S訓(xùn)練集∪S測(cè)試集

i←1;j←1

Repeat

k←1

Repeat

w←wk

w,σi,Cj和S訓(xùn)練集代入(11)式中

k++

Untilk>n

MSE(i,j)←MSE(kopt(i,j),S測(cè)試集,σi,Cj,wkopt(i,j))i++；j++

Untili>r;j>t

(i,j)opt←arg min(i,j)MSE(i,j)

4 實(shí) 驗(yàn)

4.1 性能評(píng)價(jià)標(biāo)準(zhǔn)

參數(shù)估計(jì)中均方誤差是指參數(shù)估計(jì)值與參數(shù)真值之差平方的期望值(Mean Square Error，MSE)，記為MSE[9]：

(14)

其中yi、f(xi)分別為實(shí)際失效故障數(shù)據(jù)和預(yù)測(cè)失效故障數(shù)據(jù)，ntest表示樣本故障數(shù)據(jù)集中劃分的測(cè)試數(shù)據(jù)集的大小，MSE值越小，模型的擬合性能和預(yù)測(cè)性能越好。這里需要指出的是，上述性能評(píng)價(jià)標(biāo)準(zhǔn)僅用于比較不同模型對(duì)同一數(shù)據(jù)集的應(yīng)用。傳統(tǒng)非參數(shù)化SRGM和BT-SRGM算法的相應(yīng)誤差表示為MSEst和MSEbt。將MSE之間的相對(duì)差值定義為RAMSE，公式為

(15)

4.2 數(shù)據(jù)處理

使用三個(gè)公開發(fā)表且已經(jīng)被廣泛接受的軟件失效故障數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，將每個(gè)數(shù)據(jù)集分為兩個(gè)子集(訓(xùn)練集=80%，測(cè)試集=20%)，第一個(gè)子集(后文圖中虛線左邊部分)用于擬合訓(xùn)練模型，第二個(gè)子集(虛線右邊部分)用于驗(yàn)證模型的預(yù)測(cè)能力。

第一組故障數(shù)據(jù)集(DS1)來自NTDS[10]，包含34個(gè)故障數(shù)據(jù)集，如圖2所示。對(duì)于大多數(shù)調(diào)試時(shí)間數(shù)據(jù)并不表示可靠性增長，甚至可以觀察到可靠性略微有所降低，在調(diào)試的后期階段，數(shù)據(jù)才顯示可靠性增長，數(shù)據(jù)顯示出非常大的異方差性，當(dāng)時(shí)用成對(duì)比較的權(quán)重集時(shí)可以更好地?cái)M合故障結(jié)果，圖3表明MSE對(duì)參數(shù)ε的依賴性，當(dāng)ε=0.5時(shí)，MSE的差值最大，最大的RAMSE為15.2%，因此BT-SRGM的性能明顯優(yōu)于傳統(tǒng)非參數(shù)化SRGM。

圖2 兩種SRGM故障預(yù)測(cè)結(jié)果 圖3 MSE對(duì)參數(shù)ε的依賴性

第二組故障數(shù)據(jù)集(DS2)來自IBM開發(fā)的入門軟件數(shù)據(jù)包[11]。該數(shù)據(jù)集包含15個(gè)觀測(cè)值。結(jié)果如圖4所示。圖5表明MSE對(duì)參數(shù)ε的依賴性，當(dāng)ε=0.4時(shí)，MSE的差值最大，最大的RAMSE為15.2%，雖然只是一個(gè)小數(shù)據(jù)集，但有明顯的可靠性增長。

圖4 兩種SRGM故障預(yù)測(cè)結(jié)果 圖5 MSE對(duì)參數(shù)ε的依賴性

第三組故障數(shù)據(jù)集(DS3)是使用直升機(jī)主旋翼葉片部件代碼的數(shù)據(jù)，基于1995年10月至1999年9月收集的系統(tǒng)數(shù)據(jù)庫[10]。該數(shù)據(jù)集包含52個(gè)觀測(cè)值，如圖6所示。通過觀察發(fā)現(xiàn)失敗次數(shù)的變化相當(dāng)大。而且，可靠性增長幾乎是沒有增長的。由于訓(xùn)練數(shù)據(jù)集很大，兩個(gè)模型(傳統(tǒng)非參數(shù)化SRGM和BT-SRGM)的預(yù)測(cè)結(jié)果很接近。但觀察圖7，表明MSE對(duì)參數(shù)ε的依賴性，當(dāng)ε=0.5時(shí)，MSE的差值最大，最大RAMSE為15.6%，因此與傳統(tǒng)非參數(shù)化SRGM相比，BT-SRGM提供了相當(dāng)大的改進(jìn)。

圖6 兩種SRGM故障預(yù)測(cè)結(jié)果 圖7 MSE對(duì)參數(shù)ε的依賴性

5 結(jié) 語

本文提出了一種新的非參數(shù)化的軟件可靠性增長模型(BT-SRGM)，它可以看作是傳統(tǒng)非參化模型的改進(jìn)。通過三組被廣泛應(yīng)用的失效故障數(shù)據(jù)集(DS1、DS2和DS3)將所提出的BT-SRGM與現(xiàn)有的傳統(tǒng)非參數(shù)化模型做了比較，實(shí)驗(yàn)結(jié)果顯示了BT-SRGM的性能明顯優(yōu)于傳統(tǒng)SRGM。該領(lǐng)域的研究仍處于初級(jí)階段，未來我們將嘗試將該方法擴(kuò)展到傳統(tǒng)的基于泊松過程的軟件可靠性增長模型，用以改善NHPP類軟件可靠性增長模型的預(yù)測(cè)精度和通用性。