一種非參數(shù)化SRGM預測能力的研究

惠子青, 劉曉燕, 嚴 馨

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

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

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

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

1 支持向量機回歸

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

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

(1)

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

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

(2)

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

(3)

(4)

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

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

(5)

(6)

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

(7)

(8)

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

(9)

(10)

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

(11)

(12)

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

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

2.1 不確定ε-污染模型

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

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

(13)

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

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

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

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

2.3 兩個權重的交集

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

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

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

3 BT-SRGM的算法

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

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

令f(Xn+1)

{S訓練集，S測試集}：S←S訓練集∪S測試集

i←1;j←1

Repeat

k←1

Repeat

w←wk

w,σi,Cj和S訓練集代入(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ù)和預測失效故障數(shù)據(jù)，ntest表示樣本故障數(shù)據(jù)集中劃分的測試數(shù)據(jù)集的大小，MSE值越小，模型的擬合性能和預測性能越好。這里需要指出的是，上述性能評價標準僅用于比較不同模型對同一數(shù)據(jù)集的應用。傳統(tǒng)非參數(shù)化SRGM和BT-SRGM算法的相應誤差表示為MSEst和MSEbt。將MSE之間的相對差值定義為RAMSE，公式為

(15)

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

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

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

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

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

圖4 兩種SRGM故障預測結果 圖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ù)的變化相當大。而且，可靠性增長幾乎是沒有增長的。由于訓練數(shù)據(jù)集很大，兩個模型(傳統(tǒng)非參數(shù)化SRGM和BT-SRGM)的預測結果很接近。但觀察圖7，表明MSE對參數(shù)ε的依賴性，當ε=0.5時，MSE的差值最大，最大RAMSE為15.6%，因此與傳統(tǒng)非參數(shù)化SRGM相比，BT-SRGM提供了相當大的改進。

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

5 結 語

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