惠子青, 劉曉燕, 嚴 馨

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

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

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

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

1 支持向量機回歸

回歸分析的目標是估計Rm中一組采樣點x(x1,x2,…,xn)與目標值y(y1,y2,…,yn)之間函數(shù)f(x)的依賴關(guān)系。首先假設(shè)數(shù)據(jù)集S={(x1,y1),(x2,y2),…,(xn,yn)}，其中xi∈Rm表示包含m個特征的特征向量，yi∈Rm表示映射輸出值，其中〈·,·〉表示內(nèi)積。支持向量機可以用(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表示一個高維特征空間。

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

(2)

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

(3)

(4)

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

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

(5)

(6)

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

(7)

(8)

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

(9)

(10)

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

(11)

(12)

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

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

我們給出兩個條件：①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。

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

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

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

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

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

3 BT-SRGM的算法

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

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

令f(Xn+1)

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

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測試集,σi,Cj,wkopt(i,j))i++；j++

Untili>r;j>t

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

4 實 驗

4.1 性能評價標準

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

(14)

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

(15)

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

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

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

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

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

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

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

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

5 結(jié) 語

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