一種基于馬爾可夫模型的軟件可靠性評(píng)估方法

劉志祥，劉杰，李丹，云雷

（工業(yè)和信息化部電子第五研究所，廣東 廣州 510610）

0 引言

軟件可靠性的研究起源于Hudson等人的工作，早期的研究主要針對(duì)軟件測(cè)試和現(xiàn)場(chǎng)運(yùn)行階段收集的軟件失效數(shù)據(jù)，建立可靠性增長(zhǎng)模型。對(duì)于軟件可靠性模型 （SRM：Software Reliability Model）發(fā)展首次起到較重要作用的兩個(gè)模型，發(fā)表于1971年。Shooman模型由M.L.Shooman發(fā)表，J-M模型由Z.Jelinski和P.B.Moranda發(fā)表。到80年代末，可靠性增長(zhǎng)模型的研究達(dá)到高潮[1-7]。

SRM的研究在20世紀(jì)70年代獲得較大的發(fā)展后，很多可靠性模型已經(jīng)投入使用?？梢哉f(shuō)，軟件可靠性建模己經(jīng)從研究階段發(fā)展到了工程階段。國(guó)內(nèi)外已提出100多種軟件可靠性評(píng)價(jià)模型，其中以J-M模型、G-O模型、Musa執(zhí)行時(shí)間模型、LV模型和Seeding模型等為典型代表[8-10]。David、Howden、Parnas等人提出了基于經(jīng)典統(tǒng)計(jì)假設(shè)理論的測(cè)試方法，為安全關(guān)鍵軟件的可靠性測(cè)評(píng)奠定了取樣理論基礎(chǔ)；而Little wood、Miller等人提出了基于Bayesian統(tǒng)計(jì)理論的測(cè)試方法。為了改善測(cè)試用例開(kāi)銷(xiāo)，Bojan Cukie提出了結(jié)合形式化證明和程序動(dòng)態(tài)測(cè)試的轉(zhuǎn)換方法。自1972年第一個(gè)軟件可靠性分析模型發(fā)表后的20多年以來(lái)，見(jiàn)之于文獻(xiàn)的SRM有近百種，與每個(gè)模型相應(yīng)的假設(shè)又有幾條甚至幾十條。這些可靠性模型大致可分為種子法、失效率類(lèi)、曲線擬合類(lèi)、可靠性增長(zhǎng)模型、程序結(jié)構(gòu)分析模型、輸入域分類(lèi)模型、執(zhí)行路徑分析方法模型、非齊次Poisson過(guò)程模型、馬爾可夫過(guò)程模型和貝葉斯模型等10類(lèi)[11-14]。

SRM所要解決的問(wèn)題有兩個(gè)：改進(jìn)軟件開(kāi)發(fā)過(guò)程和軟件可靠性的度量。相應(yīng)地，針對(duì)可靠性模型及其應(yīng)用展開(kāi)的研究主要集中在兩個(gè)方面：1）關(guān)于軟件可靠性早期預(yù)測(cè)模型的研究；2）關(guān)于軟件可靠性預(yù)測(cè)模型的研究。其中，早期預(yù)測(cè)模型是指在不知失效數(shù)據(jù)的情況下，根據(jù)軟件產(chǎn)品及其開(kāi)發(fā)過(guò)程來(lái)度量、預(yù)測(cè)軟件可靠性；這種模型對(duì)于改進(jìn)軟件開(kāi)發(fā)過(guò)程、指導(dǎo)軟件測(cè)試、提高軟件可靠性具有重要意義。可靠性預(yù)測(cè)模型則著眼于未來(lái)，對(duì)軟件的可靠性進(jìn)行預(yù)計(jì)，預(yù)計(jì)軟件當(dāng)前失效強(qiáng)度、下次失效時(shí)間等。文獻(xiàn) [15]在基于模糊神經(jīng)網(wǎng)絡(luò)的基礎(chǔ)上，提出了一種新的軟件可靠性早期預(yù)計(jì)方法。通過(guò)分析軟件缺陷產(chǎn)生的原因，給出了導(dǎo)致軟件缺陷產(chǎn)生的因素。同時(shí)，深入討論了軟件可靠性早期預(yù)計(jì)的建模方法。文獻(xiàn) [16]依據(jù)軟件可靠性特征，提出以解決軟件開(kāi)發(fā)邏輯思維正確性為建模基本問(wèn)題的可靠性建模思想。為了在不降低安全關(guān)鍵軟件可靠性驗(yàn)證測(cè)試結(jié)果可信性的前提下減少測(cè)試用例量，文獻(xiàn) [17]在分析經(jīng)典統(tǒng)計(jì)假設(shè)測(cè)試和無(wú)先驗(yàn)貝葉斯統(tǒng)計(jì)方法的基礎(chǔ)上，提出了一種先驗(yàn)知識(shí)動(dòng)態(tài)整合的貝葉斯推斷統(tǒng)計(jì)測(cè)試方法。文獻(xiàn)[18-19]基于馬爾可夫鏈描述軟件系統(tǒng)控制轉(zhuǎn)移的動(dòng)態(tài)特性，研究了基于馬爾可夫鏈 （MC：Markov Chain） 分 析方法 ， 以 及 隨 機(jī) Petri網(wǎng) （SPN：Stochastic Petri Nets）、 失效相關(guān)性 （Failure Correlation)的可信軟件的可靠性建模問(wèn)題。系統(tǒng)在長(zhǎng)期運(yùn)行一段時(shí)間后會(huì)出現(xiàn)系統(tǒng)性能下降或停機(jī)的現(xiàn)象，這種情況被稱(chēng)為軟件老化 （SA：Software Aging）。為了抵消軟件老化造成的影響，Yennun Huang等提出了軟件再生 （SR：Software Rejuvenation）技術(shù)。這是一種預(yù)防性的軟件容錯(cuò)策略，能有效地提高軟件系統(tǒng)的可靠性和可用性。目前看來(lái)，要建立比較適用的SRM，必須改變傳統(tǒng)的可靠性建模思路，采用新的觀點(diǎn)、方法和新的數(shù)學(xué)工具來(lái)研究軟件故障過(guò)程。

由于目前國(guó)內(nèi)外軟件可靠性建模主要是對(duì)整個(gè)軟件系統(tǒng)進(jìn)行可靠性建模分析，而按照軟件運(yùn)行流程進(jìn)行狀態(tài)分析的可靠性建?？紤]得較少。本文擺脫傳統(tǒng)模型多種主觀假設(shè)的束縛，嘗試以軟件運(yùn)行流程的狀態(tài)為研究對(duì)象，結(jié)合軟件運(yùn)行流程特點(diǎn)，將基于統(tǒng)計(jì)測(cè)試的方法與軟件運(yùn)行流程聯(lián)系起來(lái)，結(jié)合馬爾可夫理論等工具進(jìn)行可靠性建模研究。

1 馬爾可夫模型

由時(shí)刻t0系統(tǒng)或過(guò)程所處的狀態(tài)，決定系統(tǒng)或過(guò)程在時(shí)刻t＞t0所處的狀態(tài)，并不需t0時(shí)刻以前系統(tǒng)或過(guò)程所處狀態(tài)的歷史資料，這類(lèi)確定性現(xiàn)象在物理學(xué)中出現(xiàn)頻繁。依照上述規(guī)律，當(dāng)一物理系統(tǒng)或過(guò)程遵循的是某種統(tǒng)計(jì)規(guī)律時(shí)，可引入以下特性：

t0時(shí)狀態(tài)已知，時(shí)刻t（t＞t0）的狀態(tài)只與該過(guò)程在t0時(shí)刻的狀態(tài)有關(guān)，而與其在t0時(shí)刻以前所處的狀態(tài)無(wú)關(guān)，這種特性被稱(chēng)為無(wú)后效性或馬爾可夫性。用分布函數(shù)表述馬爾可夫性如下：

a） 定義 1， 設(shè)隨機(jī)過(guò)程 {X （t），t∈T}的狀態(tài)空間為I。如果對(duì)時(shí)間t的任意n個(gè)數(shù)值 t1＜t2…tn， n ≥3， ti∈T， 在 條 件 X （ ti） =xi， xi∈I， i=1，2，…，n-1下，X （tn）的條件分布函數(shù)恰等于在條件X （tn-1）=xn-1下，X （tn） 的條件分布函數(shù)，即

這個(gè)過(guò)程為馬爾可夫過(guò)程。

設(shè)隨機(jī)過(guò)程 {Xn，n∈T}，其參數(shù)集T是離散的時(shí)間集合，即T={0，1，2…}，其相應(yīng)xn可能取值的全體組成的狀態(tài)空間是離散的狀態(tài)集I={i1，i2， i3…}。

b）定義2，若對(duì)于任意的整數(shù)n∈T和任意的i0， i1， i2…in+1∈I， 條件概率滿足

則稱(chēng) {Xn，n∈T}為馬爾可夫鏈。

馬爾可夫鏈?zhǔn)且环N以統(tǒng)計(jì)理論為基礎(chǔ)的統(tǒng)計(jì)模型，在軟件統(tǒng)計(jì)測(cè)試中得到了廣泛的應(yīng)用。它是一種遷移具有概率特征的有限狀態(tài)機(jī)，可以根據(jù)狀態(tài)間遷移概率自動(dòng)生成測(cè)試用例，還可以分析結(jié)果，對(duì)軟件性能指標(biāo)和可靠性指標(biāo)等進(jìn)行度量。另外，Markov鏈模型適用于對(duì)多種軟件進(jìn)行統(tǒng)計(jì)測(cè)試，它的產(chǎn)生基于軟件規(guī)范而不是程序代碼，它可以和軟件開(kāi)發(fā)同時(shí)進(jìn)行，并可以通過(guò)仿真得到狀態(tài)和遷移覆蓋的均期望時(shí)間，有利于在開(kāi)發(fā)早期對(duì)大規(guī)模軟件系統(tǒng)進(jìn)行測(cè)試費(fèi)用和時(shí)間的規(guī)劃。

由馬爾可夫鏈描述的軟件使用模型可以用隨機(jī)遷移矩陣或者帶遷移概率的狀態(tài)遷移圖表示。用狀態(tài)遷移圖表示的優(yōu)點(diǎn)是直觀易懂，通常只用于小型系統(tǒng)或大型系統(tǒng)的高端表示。用隨機(jī)遷移矩陣表示，行和列代表狀態(tài)，矩陣的單元值代表狀態(tài)間轉(zhuǎn)移概率。此種方法的優(yōu)點(diǎn)是較容易描述復(fù)雜系統(tǒng)，但不夠直觀。

一個(gè)測(cè)試用例就是一個(gè)文檔，描述輸入、動(dòng)作或者時(shí)間和期望的結(jié)果，其目的是確定應(yīng)用程序的某個(gè)特性是否正常工作。一個(gè)測(cè)試用例應(yīng)該有完整的信息，如：測(cè)試用例ID號(hào)、測(cè)試用例名字、測(cè)試的目的、測(cè)試條件、輸入數(shù)據(jù)需求、步驟和期望結(jié)果。

在基于使用模型的測(cè)試中，所有用例的目的，宏觀來(lái)講，就是看軟件在某一狀態(tài)得到激勵(lì)后，是否能轉(zhuǎn)向預(yù)期的下一狀態(tài)，每一狀態(tài)轉(zhuǎn)換所代表的具體功能宏觀上不予考慮。測(cè)試條件是指軟件的當(dāng)前狀態(tài)，輸入數(shù)據(jù)需求則是當(dāng)前狀態(tài)所對(duì)應(yīng)的激勵(lì)，期望結(jié)果則是正確地轉(zhuǎn)換至下一狀態(tài)。因此，在基于使用模型的測(cè)試用例生成中，一個(gè)測(cè)試用例是一個(gè)狀態(tài)、激勵(lì)序列。

基于馬爾可夫模型的統(tǒng)計(jì)測(cè)試方法按照充分性的測(cè)試用例原則，只能解決一部分的狀態(tài)概率問(wèn)題，同時(shí)目標(biāo)的可靠性計(jì)算方法需要更加詳細(xì)的理論依據(jù)，本文提出一種可靠性評(píng)估模型和方法，試圖解決這個(gè)問(wèn)題。

2 可靠性評(píng)估模型和方法

任何的軟件都會(huì)依照系統(tǒng)設(shè)計(jì)流程圖來(lái)編寫(xiě)，每個(gè)流程圖都會(huì)有該軟件所對(duì)應(yīng)的狀態(tài)。假設(shè)某一個(gè)復(fù)雜軟件中有 n個(gè)正常狀態(tài)，設(shè)為 A1，A2，……An，該軟件有1個(gè)異常狀態(tài)，在這個(gè)狀態(tài)下軟件功能失效，設(shè)為Q，同時(shí)加上開(kāi)始狀態(tài)和終止?fàn)顟B(tài)，則可以為該軟件建立一個(gè)狀態(tài)轉(zhuǎn)移模型，如圖1所示。

軟件的每一次運(yùn)行流程都從Begin開(kāi)始，經(jīng)過(guò)若干個(gè)中間狀態(tài)，最后到達(dá)Exit狀態(tài)。每一狀態(tài)轉(zhuǎn)移對(duì)應(yīng)一次輸入，即一次激勵(lì)。由于模型中可能有循環(huán)，可能會(huì)產(chǎn)生無(wú)窮序列，所以輸入序列可以通過(guò)遍歷狀態(tài)轉(zhuǎn)移圖來(lái)得到。利用Markov鏈?zhǔn)褂媚Ｐ停憧梢垣@得大量的輸入序列。一個(gè)測(cè)試輸入，就是根據(jù)Markov鏈?zhǔn)褂媚Ｐ蛷妮斎胗蛑须S機(jī)產(chǎn)生的一個(gè)有限輸入序列。由圖1看出，軟件的狀態(tài)轉(zhuǎn)移從Begin開(kāi)始，經(jīng)過(guò)輸入a到達(dá)A1狀態(tài)，從A1狀態(tài)開(kāi)始，狀態(tài)開(kāi)始分為兩路：當(dāng)輸入b時(shí)，軟件正常運(yùn)行，到達(dá)A2狀態(tài)，如果輸入c，那么軟件直接到達(dá)Q狀態(tài)。從A2，A3，到An-1的n-2個(gè)狀態(tài)經(jīng)過(guò)不同的輸入，可以出現(xiàn)3個(gè)不同的狀態(tài)轉(zhuǎn)移情況，以An-1為例，當(dāng)輸入為h時(shí)，軟件正常運(yùn)行，達(dá)到An狀態(tài)，當(dāng)輸入為g時(shí)，軟件會(huì)達(dá)到Q狀態(tài)，當(dāng)輸入為j時(shí)，軟件返回到A2狀態(tài)。An和Q不用經(jīng)過(guò)任何輸入，直接到達(dá)Exit狀態(tài)。

圖1 軟件狀態(tài)轉(zhuǎn)移

依據(jù)馬爾可夫鏈的無(wú)后向性特點(diǎn)，結(jié)合軟件運(yùn)行流程的狀態(tài)轉(zhuǎn)移情況，我們定義軟件的異常概率為：

式 （1）中：q——Q所在的狀態(tài)；

Ai——軟件運(yùn)行過(guò)程中的各狀態(tài)。

通過(guò)公式 （1）可以看出，軟件異常的概率等于各狀態(tài)的概率乘以每個(gè)狀態(tài)的異常概率之和。那么軟件的可靠性為：

式 （2）中：r——軟件的正常狀態(tài)。

由于公共利益的軟件需要可靠性，因此我們定義當(dāng)P（r）≥99.5%時(shí)，則該軟件是可靠的。

根據(jù)使用模型，可以手動(dòng)或自動(dòng)產(chǎn)生測(cè)試用例。從Enter狀態(tài)開(kāi)始，生成狀態(tài)和激勵(lì)的序列，到達(dá)Exit狀態(tài)，然后通過(guò)不同的激勵(lì)生成下一個(gè)馬爾可夫鏈，直至滿足一定的測(cè)試充分性準(zhǔn)則，便可停止測(cè)試用例的生成。在模型存在循環(huán)時(shí)，需規(guī)定循環(huán)次數(shù)，避免產(chǎn)生無(wú)限長(zhǎng)的測(cè)試用例。通過(guò)充分的測(cè)試用例可以統(tǒng)計(jì)出關(guān)鍵的數(shù)據(jù)值：P（q|Ai）和 P （Ax|Ay）， 其中 i， x， y∈T， T={1， 2， 3， …n}。由于馬爾可夫的無(wú)后向性，可得如下公式：

此公式 （3）中含有n個(gè)未知數(shù)，分別為P（A1）， P （A2）， …， P （An）。 同時(shí)由于 P （Ax｜Ay）是可測(cè)試統(tǒng)計(jì)值，為已知數(shù)，其中x，y∈T，T={1，2，3，…n}。則由線性代數(shù)可知n個(gè)方程，n個(gè)未知數(shù)，可以解出該線性方程，則得到：

其中，a1，a2，……an為已知數(shù)。由于軟件異常性概率等于每個(gè)過(guò)程的狀態(tài)概率乘以每個(gè)過(guò)程在此狀態(tài)下有異常的概率之和。經(jīng)過(guò)上面的分析可知，每個(gè)狀態(tài)的概率為已知數(shù)，而每個(gè)狀態(tài)發(fā)生異常的概率同樣是已知數(shù)，那么，軟件異常概率則是可計(jì)算的。則P（r）同樣是可計(jì)算的。至此，軟件可靠性計(jì)算方式可行。

3 實(shí)例分析

本節(jié)將針對(duì)圖2所表示的某A軟件系統(tǒng)的運(yùn)行流程，結(jié)合本文提出的可靠性評(píng)估模型和方法，給出可靠性評(píng)估的示例，計(jì)算出系統(tǒng)的可靠性并對(duì)其結(jié)果加以分析，以考察本文所提出方法的正確性和有效性。

圖2 A軟件運(yùn)行流程

A軟件的運(yùn)行流程從Begin開(kāi)始，經(jīng)過(guò)4個(gè)中間狀態(tài) （正常），最后到達(dá)Exit狀態(tài)。每一狀態(tài)轉(zhuǎn)移對(duì)應(yīng)一次輸入，即一次激勵(lì)。由于模型中從A2到達(dá)A3狀態(tài)自后，可能A3狀態(tài)又返回A2狀態(tài)，所以通過(guò)規(guī)定，此種情況時(shí)，循環(huán)次數(shù)不超過(guò)2次。利用馬爾可夫鏈模型，每次通過(guò)一個(gè)測(cè)試輸入，即得到一種狀態(tài)流程圖，最后達(dá)到Exit狀態(tài)。同時(shí)，利用輸入大量的測(cè)試用例，可以得到大量的統(tǒng)計(jì)數(shù)據(jù)。從該數(shù)據(jù)中可以統(tǒng)計(jì)得出每個(gè)狀態(tài)下通過(guò)一種輸入之后的異常概率P（q|Ai），其中i={1，2，3，4}和每個(gè)狀態(tài)下下一個(gè)狀態(tài)的概率P（Ax|Ay）， 其中， x，y∈T， T={1，2， 3，4}。

依據(jù)馬爾可夫鏈的無(wú)后向性特點(diǎn)，結(jié)合軟件運(yùn)行流程的狀態(tài)轉(zhuǎn)移情況，我們定義軟件的異常概率為：

其中，q表示Q所在的狀態(tài)，Ai表示軟件運(yùn)行過(guò)程中的各狀態(tài)。可以看出，P（q|Ai）是已知的，關(guān)鍵點(diǎn)在于計(jì)算 P （Ai）， 其中 i={1， 2， 3， 4}。通過(guò)公式 （3）可知：

通過(guò)之前的分析，假設(shè)：P（q|A1）=0.07，P（q|A3） =0.01， P （q|A2） =0， P （q|A4） =0； 同時(shí)通過(guò)統(tǒng)計(jì)測(cè)試，假設(shè)P（A2|A1）=0.93，P（A3|A2）=1， P （A2|A3） =0.05， P （A4|A3） =0.94， 則將數(shù)據(jù)代入公式可得：

可得： P （A1） =1， P （A2） =P （A3） =0.98， P（A4）=0.92。軟件異常的概率等于各狀態(tài)的概率乘以每個(gè)狀態(tài)的異常概率之和。那么該軟件的異常概率為：

則根據(jù)公式P（r）=1-P（1）得軟件可靠性概率為： （1-0.08）*100%=92%。

當(dāng)需求定義P（r）≥99.5%時(shí)，則該軟件是可靠的。依據(jù)這個(gè)判別方法，可得該軟件是不可靠的。

4 結(jié)束語(yǔ)

現(xiàn)有軟件系統(tǒng)的運(yùn)行環(huán)境逐漸朝著更加開(kāi)放的方向發(fā)展，在這種情況下如何對(duì)軟件的可靠性進(jìn)行快速、有效的衡量成為一個(gè)急需解決的問(wèn)題。本文基于馬爾可夫鏈模型研究軟件可靠性評(píng)估方法，通過(guò)建立目標(biāo)函數(shù)模型，分析目標(biāo)函數(shù)的計(jì)算方法，給出目標(biāo)的判別方法，得出基于馬爾可夫鏈的迭代算法來(lái)評(píng)估軟件可靠性是可行的。該方法不但能夠充分、準(zhǔn)確地得到評(píng)估結(jié)果，同時(shí)還能指導(dǎo)軟件可靠性的分析，為以后的系統(tǒng)優(yōu)化提供更多的參考。在今后的工作中，還需要通過(guò)實(shí)際項(xiàng)目的應(yīng)用來(lái)進(jìn)一步檢驗(yàn)該方法的有效性和可操作性；同時(shí)，利用軟件可靠性研究方法進(jìn)行優(yōu)化和改進(jìn)軟件是一個(gè)可以深入研究的方法。

[1]MUSA J D.Softward reliability engineering[M].New York： McGraw-Hill， 1998： 1-142.

[2]DOWNS T，GARRONE P.Some new methods of software testing with performance comparisons[J].IEEE Trans.Relia， 1991， 40 （3）： 322-337.

[3]WHITTAKER J A，POORE J H，Markov.Analysis of software specification[J].ACM Trans.Software Engineering and Methodology， 1993， 2 （2）： 93-103.

[4]CHEN Huo-wang， WANG Ji， DONG Wei.High confidence software engineering technologies[J].Acta Electronica Sinica， 2003， 31 （12A）： 1933-1938.

[5]SELDING P B.Faulty software caused Ariane 5 failure[J].Space News， 1996， 25 （7）： 24-30.

[6]LEVE SON NG，TURNER CS.An investigation of the Therac-25 accident[J].IEEE Computer， 1993， 26 （7）：18-41.

[7]ZHANG YQ， SUN SJ.Software reliability modeling based on unascertained theory[J] .JournalofSoftware，2006， 17 （8）： 1681-1687.

[8]趙瑋，楊莉.軟件模塊測(cè)試中的動(dòng)態(tài)資源分配問(wèn)題 [J].運(yùn)籌學(xué)學(xué)報(bào)，2000，4（3）：88-94.

[9]劉云.計(jì)算機(jī)系統(tǒng)可靠性若干問(wèn)題研究 [M].西安：西安電子科技大學(xué)出版社，1998.

[10]陳麗敏.基于馬兒可夫鏈模型的軟件可靠性測(cè)試方法研究 [D].成都：電子科技大學(xué)，2010：22-25.

[11]DAVID L P， JOHN A， KWAN S P.Evaluation of safetycritical software[J].Communica-tion of ACM，1990，33（6）： 636-648.

[12]PARNAS D L， ASMIS GJ K， MADEY J.Assessment of safety-critical software in nuclear power plants[J].Nuclear Safety， 1991， 32 （2）： 189-198.

[13]HOWDEN W E.Good enough versus high assurance software testing and analysis methods[C]//In:Regina S Sed.Proceedings of the Third IEEE International High Assurance Systems Engineering Symposium.Washington D C：IEEE ComputerSociety， 1998： 166-175.

[15]劉斌，陸民燕，阮鐮.基于模糊神經(jīng)網(wǎng)絡(luò)的軟件可靠性早期預(yù)計(jì)方法 [J].北京航空航天大學(xué)學(xué)報(bào)，2001，27（2）： 237-240.

[16]吳超，林家駿，俞嶺.軟件可靠性建模研究 [J].計(jì)算機(jī)工程，2008，34(11)：52-54.

[17]QIN Zhi-dong， LEI Hang， SANG Nan， et al.Study on the reliability demonstr-ation testing method for safetycritical software[J].Acta Aeronautica et AstronauticaS-inica， 2005， 26 （3）： 334-338.

[18]朱連章，李妍深.用于軟件可靠性分析的分解方法 [J].計(jì)算機(jī)工程與設(shè)計(jì)，2007，28（24）：5835-5837.

[19]MILLER W M， MORELL L J， NOONAN R E， et al.Estimating the probability of failure when testing reveals no failures [J].IEEE Trans On Software Engineering，1992， 18 （1）： 33-43.