屏蔽數(shù)據(jù)下帶變點的軟件可靠性增長模型

楊劍鋒 霍雨佳 蔡 靜

1(貴州理工學院大數(shù)據(jù)學院 貴州 貴陽 550003) 2(貴州理工學院電氣與信息工程學院 貴州 貴陽 550003) 3(貴州民族大學數(shù)據(jù)科學與信息工程學院 貴州 貴陽 550025)

0 引 言

軟件可靠性是軟件質量的一個主要屬性，在建立軟件可靠性增長模型時，通常假設軟件的失效過程服從非齊次泊松過程[1-5]。可疊加的NHPP類可靠性模型由一些獨立的非齊次泊松過程疊加而成[6-7]，它可以用于描述一些基于組件或者對象的大型軟件系統(tǒng)的失效過程。疊加模型能夠充分地利用組件的失效數(shù)據(jù)，來評估整個軟件系統(tǒng)的可靠性。由于可疊加模型中較多的未知參數(shù)，因此如何利用有效的算法求解模型的極大似然估計仍然是值得研究的問題。

屏蔽數(shù)據(jù)(Masked Data)是指引起系統(tǒng)失效的真實原因不得而知，即導致系統(tǒng)失效原因可能是系統(tǒng)中任意一個組件(對象、子系統(tǒng)、模塊)[8]。如今，屏蔽數(shù)據(jù)下硬件可靠性分析已經(jīng)取得了許多研究成果[9-13]，然而基于屏蔽數(shù)據(jù)的軟件可靠性研究成果較少。由于屏蔽失效數(shù)據(jù)的存在，導致可疊加模型中有較多的未知參數(shù)，因此如何利用有效的算法求解模型的極大似然估計仍然是值得研究的問題。

文獻[8]首次使用EM算法解決了可疊加模型中參數(shù)的極大似然估計問題，取得了較好的效果。文獻[14]利用免疫粒子群算法求解了屏蔽數(shù)據(jù)下可疊加模型的極大似然估計。然而，這些屏蔽數(shù)據(jù)下的軟件可靠性疊加模型，未考慮軟件失效過程中的變點問題。由于受到軟件測試過程中各種因素的影響，使得失效過程的統(tǒng)計特性有所變化，例如測試人員的改變等，如今在軟件變點可靠性模型上已經(jīng)取得了一些研究成果[15-18]。

然而，很少有相關文獻同時考慮軟件的屏蔽失效和失效過程中的變點問題。因此，本文是在同時考慮屏蔽失效數(shù)據(jù)和多變點的情況下，建立可疊加的軟件可靠性增長模型，利用C-Chart方法估計軟件失效過程中的變點位置，并給出參數(shù)的極大似然估計，利用EM算法對其求解。

1 模型設計

1.1 屏蔽數(shù)據(jù)

在實際軟件開發(fā)過程中，由于受軟件測試策略及測試費用等問題的影響，使得完整的失效數(shù)據(jù)很難獲得或者需要耗費大量的資源，因此失效數(shù)據(jù)中出現(xiàn)了屏蔽現(xiàn)象，即導致系統(tǒng)失效的原因不能確定或者某些失效類型不能判斷[8]。

對于一個三組間的軟件系統(tǒng)，其失效過程特例如圖1所示，可以看出，第一個時刻M表示發(fā)生失效的原因不知，第二個時刻是組件1導致系統(tǒng)失效。由于失效數(shù)據(jù)的不完整性，使得軟件可靠性模型的參數(shù)估計更加復雜。

圖1 屏蔽數(shù)據(jù)下軟件系統(tǒng)的失效過程

1.2 模型假設

為了建立屏蔽數(shù)據(jù)下帶變點的軟件可靠性增長模型，需要如下基本假設：

1) 軟件系統(tǒng)中有k個對象(子系統(tǒng)、模塊、組件)。

2) 每個組件i的失效過程服從NHPP{Ni(t),t≥0}，其均值函數(shù)分別為mi(t),i=1,2,…,k。

3) {Ni(t),t≥0},i=1,2,…,k相互獨立。

4) 軟件系統(tǒng)的累計失效數(shù)為N(t)，由下式計算：

(1)

因此，軟件系統(tǒng)的均值函數(shù)為：

(2)

進一步可得軟件系統(tǒng)的失效強度函數(shù)為：

(3)

根據(jù)模型的基本假設和非齊次泊松過程的性質，可得軟件系統(tǒng)的可靠性函數(shù)為：

R(t)=P{N(t)-N(0)=0}=

exp{-[m(t)-m(0)]}=

(4)

另外，軟件系統(tǒng)在(t,t+Δt)時間區(qū)間里不發(fā)生失效的概率為：

R(Δt|t)=exp{-[m(t+Δt)-m(t)]}

(5)

1.3 模型建立

1.3.1屏蔽數(shù)據(jù)下帶變點的可靠性模型一般性框架

(6)

從而可得軟件的失效強度函數(shù)為：

(7)

1.3.2屏蔽數(shù)據(jù)下帶變點的G-O可靠性模型

可疊加的G-O模型[19]由Ohba提出[20]，該模型的均值函數(shù)為每個組件均值函數(shù)的和，具體如下：

(8)

式中：k為系統(tǒng)組件(子系統(tǒng))的個數(shù)；ai、ri分別是組件i的故障數(shù)和故障檢測率。由式(6)和式(8)可得G-O模型下軟件系統(tǒng)的均值函數(shù)m(t)為：

(9)

式中：ali和rli分別是組件i在第l個變點區(qū)間上的初始故障數(shù)和故障檢測率。

由式(7)和式(9)可得G-O模型下軟件的失效強度函數(shù)為：

(10)

2 參數(shù)估計與模型評估準則

本文采用C-Chart技術估計軟件失效過程中的變點位置，使用EM算法解決似然函數(shù)的最大化問題。

2.1 基于C-Chart的變點估計

(11)

(12)

(13)

式中：fi為第i個觀測區(qū)間上的故障數(shù)。假定有連續(xù)至少8個觀測值位于中心線的同一側，可能會有一個變點產(chǎn)生[15]。因此，通過C-Chart方法可以估計變點的位置。

2.2 模型參數(shù)的極大似然估計

觀測到的系統(tǒng)屏蔽失效數(shù)據(jù)可以表示為：

(14)

易知,在時間區(qū)間[tj-1,tj]?(τl-1,τl]上觀測值成功發(fā)生的事件為：

(15)

其中：

(16)

(17)

式中：

(18)

(19)

(20)

(21)

將式(18)和式(20)代入式(17)得：

(22)

因此，可得似然函數(shù)如下：

(23)

可以在不同的變點區(qū)間上分別求似然函數(shù)的最大值，從而得到參數(shù)的極大似然估計。但是，從似然函數(shù)公式可以看出，屏蔽數(shù)據(jù)下參數(shù)的似然函數(shù)非常復雜，通過數(shù)值算法也是很難求出極大似然估計。本文將采用EM算法解決極大似然估計的問題。下面分別討論完全屏蔽失效和無屏蔽失效兩種特殊情況下的似然函數(shù)。

1) 完全屏蔽失效情形。

(24)

2) 無屏蔽失效情形。

(25)

(26)

此種情形下，我們只需要在不同的變點區(qū)間(τl-1,τl]和不同的組件i(i=1,2,…,k)下分別求對數(shù)似然函數(shù)的最大值即可。

2.3 模型評估準則

均方誤差(MSE)是一種常見的模型評估準則，由于本文考慮帶變點的屏蔽失效問題，因此模型的MSE定義為：

(27)

3 極大似然估計的EM算法

當屏蔽數(shù)據(jù)存在時，系統(tǒng)的失效數(shù)據(jù)包含可觀測的數(shù)據(jù)xobs和缺失的數(shù)據(jù)xmiss兩個部分，可以采用EM算法解決似然函數(shù)過于復雜的關鍵性問題，EM算法的過程如下：

E步驟：對于未知參數(shù)向量θ當前的估計值θ(s)，計算對數(shù)似然函數(shù)的條件期望：

Q(θ(s),θ)=Eθ(s){log(θ|xobs,xmiss)|xobs}

(28)

M步驟：通過計算Q(θ(s),θ)的最大值，找到參數(shù)θ的新估計θ(s+1)。

一般情況下，序列{θ(s)，l=1,2,…}將收斂于參數(shù)的極大似然估計值[13,14]。假設在失效過程中用C-Chart方法估計到了L個變點，在每個區(qū)間(τl-1,τl]上用EM算法求解參數(shù)的極大似然估計。下面將描述在區(qū)間(τl-1,τl]上的EM算法步驟，其他變點區(qū)間可以類似計算。

Q((θ(l))(s),θ(l))=

(29)

Qi((θ(l))(s),θ(l))=

(30)

i=1,2,…,k

(31)

下面給出在某個變點區(qū)間(τl-1,τl]上使用EM算法估計參數(shù)的步驟：

步驟5重復步驟2至步驟4，直到滿足條件為止。

因此，根據(jù)上面的EM算法步驟，可以求出所有變點區(qū)間(τl-1,τl],l=1,2,…,L+1上的參數(shù)估計值θ(l)。

4 案例分析

4.1 故障數(shù)據(jù)

本文所需的故障數(shù)據(jù)來源于Tomcat 5的用戶缺陷跟蹤系統(tǒng)https://bz.apache.org/bugzilla/。Tomcat 5的缺陷跟蹤系統(tǒng)中組件字段共包含Catalina、Connector、Jasper、Native、Servlets、Webapps、Unknown等屬性。根據(jù)不同的組件分類，分別提取了每個組件長達65個月的失效數(shù)據(jù)，如表1所示。表1中觀測的時間區(qū)間為2004年8月至2009年12月共計65個月(1～65代表第1個月到第65個月)，F(xiàn)1代表Catalina組件的失效數(shù)，F(xiàn)2代表Connector組件的失效數(shù)，F(xiàn)3代表Jasper組件的失效數(shù)，F(xiàn)4代表Native、Servlets和Webapps三個組件的失效數(shù)，M代表Masked或者Unknown(屏蔽失效數(shù))。

表1 Tomcat 5軟件屏蔽失效數(shù)據(jù)

續(xù)表1

續(xù)表1

4.2 模型性能對比分析

根據(jù)2.1節(jié)的變點估計方法，使用Tomcat 5失效數(shù)據(jù)畫出C-Chart圖，如圖2所示。可以看出，從第33個月開始，超過8個失效數(shù)據(jù)連續(xù)出現(xiàn)在中心線的同一側，因此我們確定該數(shù)據(jù)的變點位置為τ=33。因此，下面我們將65個月的失效觀測時間分為兩個區(qū)間[0,33]∪(33,65]分別進行參數(shù)估計。

圖2 軟件失效的C-Chart圖

通過上面建立的模型、極大似然估計方法以及EM算法步驟，使用上面的真實數(shù)據(jù)可以得到表2所示的參數(shù)估計結果及模型的均方誤差。可以看出，有屏蔽失效的G-O模型的MSE(353.8177)和有變點的G-O模型的MSE(66.4551)比傳統(tǒng)G-O模型的MSE(671.4083)都要小，這說明考慮變點和屏蔽失效情況，比傳統(tǒng)的G-O模型都有所改進，擬合效果更好。從表2可以進一步看出，屏蔽失效下帶變點的G-O模型的MSE(64.0518)比有屏蔽失效的G-O模型的MSE(353.8177)和有變點的G-O模型的MSE(66.4551)都要小，這說明本文提出的可靠性模型具有較好的效果。

表2 參數(shù)估計結果及均方誤差

圖3給出了傳統(tǒng)G-O模型、有變點的G-O模型、有屏蔽失效的G-O模型和屏蔽失效下帶變點的G-O模型(本文提出的模型)4個模型下的失效數(shù)據(jù)擬合圖。

圖3 各模型的失效擬合圖

5 結 語

本文在考慮屏蔽失效和多變點的情況下，建立了基于非齊次泊松過程的軟件可靠性增長模型，詳細推導了模型參數(shù)的極大似然過程，并利用EM算法解決似然函數(shù)極其復雜的問題。為了驗證模型的有效性，本文從Tomcat 5缺陷報告系統(tǒng)中提取了65個月的屏蔽失效數(shù)據(jù)，并利用該真實數(shù)據(jù)，對提出的模型進行性能對比分析。實驗結果表明本文提出的屏蔽數(shù)據(jù)下帶變點的G-O可靠性模型擬合效果最好，其次是帶變點的G-O模型和屏蔽數(shù)據(jù)下的G-O模型，傳統(tǒng)的G-O模型效果最差。