一種基于貝葉斯理論的軟件可靠度評估方法

許金超，曾國蓀，王 偉

（1.同濟大學 電子與信息工程學院，上海201804；2.同濟大學 嵌入式系統(tǒng)與服務計算教育部重點實驗室，上海201804）

軟件測試是由人工或自動的方法來執(zhí)行或評價系統(tǒng)或系統(tǒng)部件的過程，以驗證它是否滿足規(guī)定的需求，或識別出期望的結果和實際結果之間有無差別.現(xiàn)代軟件工程中軟件測試是不可缺少的一個環(huán)節(jié).隨著軟件規(guī)模越來越大，軟件產(chǎn)品的邏輯功能和系統(tǒng)結構越來越復雜，有限的時間和資源范圍內(nèi)設計和選擇測試用例以獲得足夠的測試覆蓋率變得越來越難.通過分析軟件中的因果關系采用嚴格的測評方法評估軟件是否達到可靠性目標可以為測試人員提供決策支持，因此成為了學術界和工業(yè)界的一個重要研究方向.

貝葉斯方法利用先驗認識對參數(shù)進行估計這一特點使得該方法在軟件可靠性的估計中得到了廣泛的應用.Littlewood等［1］提出了基于貝葉斯方法的Littlewood－Verrall 模 型，Becker 和 Oikonomou等［2－3］各自給出了軟件失效估計的不同貝葉斯方法.Miller等［4］提出了基于輸入域的軟件可靠性評估的貝葉斯方法.Cukic等［5］討論了在利用或不利用對系統(tǒng)可靠性的主觀認識的情況下采用貝葉斯理論對可靠性進行估計的方法.張德平等［6］給出了一種基于先驗知識的快速學習算法，并利用此算法來優(yōu)化測試過程，從而降低測試成本.

已有的這些評估方法難以有效地收集與表示軟件失效時間數(shù)據(jù)，從而限制了這些方法在可靠性評估中的應用.并且方法都相對復雜、誤差較大，測試的持續(xù)期太長，導致某些高可靠性指標的驗證不易實現(xiàn).工程中實用的可靠性估計方法應該能夠簡化計算過程，最大化復用已有的測試數(shù)據(jù)，減少測試用例的數(shù)量，為何時進行單元測試、何時進行集成測試提供決策依據(jù).隨著面向?qū)ο蠹夹g的廣泛應用，大規(guī)模軟件通常劃分為多個模塊進行開發(fā)測試，這些模塊的測試結果和整個軟件的測試成敗有直接聯(lián)系.本文通過建立軟件內(nèi)部模塊影響關系圖利用貝葉斯方法計算出模塊需要的測試用例數(shù)目和每個模塊的可靠度，進而評估整個程序的可靠性.該評估方法能夠給出每一模塊的可靠程度的精確數(shù)值且計算簡單，可以直觀地為測試過程提供決策依據(jù)，減少測試用例數(shù)量，解決了已有可靠性估計方法中存在的部分問題.

1 模塊影響關系

軟件是由軟件模塊構成的集合，令P表示一個軟件，定義P＝｛M1，M2，M3，M4，…｝，其中M1，M2，M3，M4，…是P中的所有軟件模塊.

定義1 如果模塊M測試出錯，可能會導致模塊N出錯，則稱M影響N，記作如果M測試出錯不會導致模塊N出錯，則稱M不影響N，記作

定義2 給定軟件模塊M和N，如果不存在模塊K∈P，使得同時成立，則稱M直接影響N，記作

定義3 程序P的模塊影響關系圖是一個二元組＜V，E＞，其中V代表軟件中的所有模塊，E表示V中模塊間的直接影響關系.

對于模塊影響關系圖中不受其他模塊影響的節(jié)點稱為底層節(jié)點，除此之外的其他節(jié)點稱為上層節(jié)點.一般說來，一個模塊影響的模塊越多，則它的測試結果對整個程序的影響越大，對它的可靠性要求就更嚴格，這種節(jié)點的重要性更高.圖1給出了一個模塊影響關系圖的實例，實例中的模塊選自一個游戲軟件，圖中每個模塊對應游戲中的一個類，圖中AnimatePlayer直接影響3個模塊，因此上層節(jié)點AnimatePlayer的重要性比底層節(jié)點MPlayer高.

對于設計不好的軟件系統(tǒng)，會存在軟件模塊間高耦合的情況，從而造成模塊間出現(xiàn)循環(huán)依賴的影響關系，從而在模塊影響關系圖中出現(xiàn)環(huán)路.為了利用貝葉斯方法研究各個模塊的測試可靠度，需要消除圖中的環(huán)路.可以用2種方法消除圖中的環(huán)路.第1種方法是分析具體應用程序，修改其源代碼，改進程序的實現(xiàn)方式，消除代碼間的循環(huán)依賴關系，然后重新構建模塊影響關系圖.在不方便修改源代碼的情況下，可以采用第2種方法，這種方法將存在循環(huán)依賴關系的環(huán)上的所有節(jié)點視作一個整體，在圖中作為一個單獨的節(jié)點存在，然后將指向環(huán)上節(jié)點的邊統(tǒng)一指向該節(jié)點.循環(huán)這個步驟，直至圖中不出現(xiàn)回路.最終得到一個貝葉斯網(wǎng)絡.

圖1 模塊影響關系圖實例Fig.1 Example of module influence relation ship diagram

2 基于貝葉斯理論的軟件測試

程序的可靠度是對整個程序成功執(zhí)行的期望，而系統(tǒng)的成功執(zhí)行意味著程序的所有模塊必須全部按用戶的期望執(zhí)行.模塊M的可靠度可以通過下次測試是否成功的概率進行估值，記模塊M的可靠度為（M）.

2.1 單模塊的可靠度評估

對每個單獨的模塊來說，測試結果只有2種：成功或者失敗.單模塊的軟件測試是一個二項式分布，可以運用貝葉斯方法直接估計后驗測試成功概率.

命題1設M為軟件P中的一個模塊，如果用二項事件（成功／失?。┟枋鰷y試結果，當對M進行n次測試后，測試成功的次數(shù)為u，測試失敗的次數(shù)為v，則模塊M測試成功的后驗概率服從β分布，其密度函數(shù)為

式中，θ為模塊測試成功的概率，單模塊M的可靠度（M）可用M第n＋1次測試成功的概率給出

式中：E（·）表示數(shù)學期望；0＜θ＜1；參數(shù)u，v＞0.

命題1為單測試模塊的可靠性提供數(shù)值估算，式（2）給出了直接計算模塊可靠度方法.但是一個模塊可能只進行過很少幾次測試，不足以用來評估目標模塊的可靠度.為了擁有足夠的把握確認對的估計，需要度量的置信水平.令－ε，＋ε）為的置信度為γ的置信區(qū)間，ε代表了一個可以接受的錯誤水平，則可用如下公式計算的置信度：

由于區(qū)間估計的置信度與精度相互制約，當測試總次數(shù)n固定時，精度與置信度不可能同時提高，為此在保證置信度前提下盡量提高精度.即先選定一個置信度閾值γ0，然后通過增加總的測試次數(shù)n提高精度，當精度達到可接受的水平，即γ≥γ0時，可根據(jù)這時的測試結果進行可靠度計算.通過推導可得到需要的樣本容量n0同ε和γ0之間的關系

2.2 存在直接影響關系的2個模塊的可靠度評估

若M和N為P中的2個模塊，且且由命題1可以直接求得M的可靠度.觀察可知N的可靠度取決于M的可靠度（M）和M測試正確的前提下N自身的可靠度，為了表述方便，將依賴于影響模塊的可靠度稱作推薦可靠度，記作（N），則有（N）＝（M）；將不考慮影響模塊的時候自身的可靠度稱作直接可靠度，記作（N），這可由式（2）進行計算.合并這二者，可得N的可靠度，由以下公式給出：

λ的選擇由測試人員對兩者的重要性判斷給出.一般說來，對于上文中的M和N的關系，可以直觀認為計算時（N）比（N）更重要.因此λ由下式給出：

式中：le為N中受M影響的代碼行數(shù)；la為N中總代碼行數(shù).

2.3 多模塊可靠度評估

若L，M，N是P中的3個模塊此時L的可靠度取決于M和N的可靠度以及M，N測試通過前提下的可靠度.因此有

式中：（L）可以由式（2）計算得出，而（L）即M，N的聯(lián)合可靠度（M，N）的評估又分2種情況.

命題2 設對M和N的總測試次數(shù)為n1和n2，其中測試成功次數(shù)為u1和u2，測試失敗的次數(shù)為v1和v2.則（M，N）的估計為

當直接影響L的模塊不止一個時，不難對式（8）進行推廣，同時結合前面對模塊可靠度準確性分析可得

這里為了保證聯(lián)合可靠度的置信水平，首先要求每個單獨的模塊都應該滿足γ≥γ0.

這種情況下L的可靠度不僅取決于L自身的可靠度和M，N本身的可靠度，另外還和影響M，N從而間接影響L的模塊的可靠度有關系.因此這種情況下對式（8）進行擴展得

式中：m為滿足條件的K的個數(shù)；λ′為M，N中除K以外的代碼行數(shù)與M，N中總代碼行數(shù)的比值.類似的有，當影響模塊多于2個時式（10）推廣為

2.4 可靠度評估在測試過程中的應用

式（1）～（11）給出了利用貝葉斯理論對軟件模塊可靠度進行估值的計算方法.在實際測試過程中，必須做好測試記錄，它是可靠度評估的基本依據(jù).整個測試過程描述如下：測試一個程序，首先根據(jù)程序分解后的模塊間影響關系構建貝葉斯網(wǎng)絡，統(tǒng)計每個模塊的影響模塊數(shù)量，對每個模塊根據(jù)其重要程度確定置信度和置信區(qū)間，然后根據(jù)這些參數(shù)確定每個模塊的用例數(shù)量并進行測試，并使用測試結果對模塊的可靠度進行估值，如果可靠度達到了模塊的測試要求，則認為該模塊測試成功，否則對軟件進行修復并產(chǎn)生新的測試用例繼續(xù)測試.在保證程序的每個底層模塊測試成功的前提下再對上層模塊進行測試和可靠度計算.重復這一過程，直至所有模塊可靠度都達到其設計指標.

3 應用和實驗

3.1 應用示例

該框架曾應用在一款Android平臺手機游戲的自動化測試中，測試游戲由Java開發(fā)，共有25個模塊組成，根據(jù)各個節(jié)點間影響關系構建的貝葉斯網(wǎng)絡有8個底層節(jié)點，17個上層節(jié)點.測試過程中，設定所有模塊的置信度閾值為0.98，設定模塊AnimatePlayer，NpcPlayer和Effect可以接受的錯誤水平ε＝0.12，則由式（4）可計算出n0＝159.896，即需要的測試用例至少為160個；模塊EnemyPlayer的ε＝0.08，至少需要測試用例360個；其他模塊的ε＝0.15，至少需要測試用例103個.選擇其中的一部分模塊來描述模塊可靠度的計算過程，選擇的部分模塊之間的影響關系如圖1.表1給出了最底層節(jié)點的測試成功次數(shù)和失敗次數(shù)以及計算出的底層節(jié)點可靠度.可以看到全部滿足可靠度閾值，因此可以繼續(xù)進行上層節(jié)點的可靠度計算.

表1 底層節(jié)點測試數(shù)據(jù)和可靠度Tab.1 Test data and reliability of bottom nodes

經(jīng)觀察，MPlayer共56行，MSprite共有代碼132行，和MSpriteData類相關代碼15行.可以求得λ1＝0.886，故（MSprite）＝0.114×1＋0.886×0.990＝0.991.AnimatePlayer類中共有代碼1 543行，和MPlayer和MSprite相關的代碼有116行，因此其他模塊可靠度見表2，最終得（GameCenter）＝0.981，可知這部分模塊和整個程序的可靠度全部大于閾值，測試通過.

表2 上層節(jié)點測試數(shù)據(jù)和可靠度Tab.2 Test data and reliability of upper layer nodes

3.2 實驗分析

為了驗證本文的可靠度評估方法用于指導軟件測試時的優(yōu)勢及是否能夠有效提高軟件測試的效率和成本，進行了該方法與隨機測試策略、學習策略［6］的比較.在隨機測試策略中測試用例根據(jù)均勻分布隨機地在測試用例集中選取，也就是說，每一個可行的測試用例行動在測試中都以相同的機會被選取.學習策略是一種基于Markov決策過程的策略，它運用交叉嫡的方法搜索最優(yōu)的測試剖面，從而優(yōu)化軟件測試，減少測試用例數(shù).實驗中測試目標是目標程序最終測試失敗的概率低于3%，實驗過程中采用10個不同的測試用例集分別進行了10次測試，10次測試中分別達到這一要求時3種方法分別使用的最小用例數(shù)目如圖2所示.

圖2 3種測試策略的測試成本Fig.2 Test cost of three testing strategies

10次測試實驗中本文方法的平均測試用例數(shù)為242.9，和學習策略基本持平，隨機測試的平均測試成本在三者中最高為608.3.測試結果表明，本文給出的方法在用于軟件測試時雖然不能保證每次測試成本都比隨機測試小，但其平均測試成本會遠遠低于隨機測試的平均成本.實驗過程中得知，同學習策略相比，盡管在測試成本上并不占太大優(yōu)勢，然而本文方法實現(xiàn)更為簡單，計算快速直觀，測試用例數(shù)目相對保持穩(wěn)定，能夠縮短測試的總時間.

在整個項目的測試過程中使用該評估方法能夠準確把握各模塊的可靠程度，從而有針對性地設計測試用例，減少了不必要的測試，縮短了項目的交付時間.

4 結語

通過分析軟件模塊間的影響關系，基于測試數(shù)據(jù)，利用貝葉斯方法為各個軟件模塊計算一個數(shù)值表示的可靠度.通過模塊間的影響關系，并對可靠度進行排序，可以確定測試過程中要重點測試的模塊，減少不必要的測試.該方法不但能快速準確地得到評估結果，也可以為模塊的測試用例數(shù)量提供參考.

［1］Bev Littlewood，John Verrall.A Bayes reliability model with a stochastically monotone failure rate［J］.IEEE Transaction on Reliability，1976，23：108.

［2］G Becker，L Camarinopoulos.A Bayesian estimation method for the failure rate of a possibly correct program［J］.IEEE Transaction on Software Engineering，1990，16：1307.

［3］Kostas Oikonomou.Predictive with the dynamic Bayesian gamma mixture model［J］.IEEE Transaction on Systems，Man and Cybernetics，1997，27：529.

［4］Keith Miller，Larry Morell，Noonan Park，et al.Estimating the probability of failure when testing reveals no failures［J］.IEEE Transactions on Software Engineering，1992，18（1）：33.

［5］B Cukic，D Chakravarthy.Bayesian framework for reliability assurance of a deployed safety critical system［C］／／Proceedings of the 5th IEEE International Symposium on High Assurance Systems Engineering.New York：Computer Society，2000：321－329.

［6］張德平，聶長海，徐寶文.基于Markov決策過程用交叉熵方法優(yōu)化軟件測試［J］.軟件學報，2008，19（10）：2770.ZHANG Deping，NIE Changhai，XU Baowen.Cross－entropy method based on Markov decision process for optimal software testing［J］.Journal of Software，2008，19（10）：2770.