測試有效性對軟件可靠性驗證測試量的影響

李秋英 李海峰 王 健

(北京航空航天大學 可靠性與系統工程學院，北京 100191)

測試有效性對軟件可靠性驗證測試量的影響

李秋英 李海峰 王 健

(北京航空航天大學 可靠性與系統工程學院，北京 100191)

針對傳統軟件可靠性驗證測試方法均不考慮軟件測試性可能會對驗證測試用例數量產生影響的現狀，提出一種引入測試有效性對軟件可靠性驗證測試最小量進行改進的方法.分析了軟件測試性的定義及其對軟件可靠性測試集合的影響，提出軟件測試有效性的概念.比較了考慮測試有效性前后軟件可靠性驗證測試集合在數量上的差異，證明經典統計方法和無先驗知識的Bayesian統計推斷方法確定的均為假定測試有效性為零情況下的保守估計.提出結合測試有效性的驗證測試量的量化表示模型和驗證測試方案的改進方法，基于統計故障注入的原理，提出測試有效性的定量評估方法，最后通過示例給出定量評估過程和方法.

軟件可靠性;驗證;測試;有效性;影響;評估

軟件可靠性驗證測試(SRDT，Software Reliability Demonstration Testing)作為驗證軟件可靠性指標的重要決策依據，國內外已取得了一系列研究成果，如TRW驗證測試、Bayesian無失效驗證測試、單風險序貫測試等［1］.由于需要數量龐大的測試用例或相當長的測試時間，影響了這些驗證測試方案在高可靠安全關鍵軟件中的應用.學者們試圖降低SRDT所需的測試量，如基于貝葉斯統計推斷的 SRDT［2］、分層抽樣［3］、程序切片［4］、實驗設計［5］、重要度抽樣［6］、提高軟件輸入嚴酷度［7］、調整 Markov 鏈使用模型的遷移概率［8］等.上述方法的目的均為在保證置信水平的同時，減少用例量或測試時間.但這些方案無一例外地均未考慮軟件測試性這一對軟件可靠性測試工作量可能會產生重要影響的因素.

軟件測試性是軟件的內在屬性，是對軟件進行有效測試難易程度的一個指標［9－11］.如果軟件的測試性好，則通過統計測試來保證軟件質量的效果就好;反之，則無法起到有效的保障作用.文獻［12－13］通過實驗驗證了軟件測試性對實現軟件可靠性目標所需測試用例數量的影響.

本文針對軟件測試性進行分析，通過將測試性對測試集合影響的外在表現定義為測試有效性，將測試性與測試集合建立起聯系，并將測試有效性引入軟件可靠性測試工作量的表示模型中，從理論上證明其對軟件可靠性測試工作量的影響，從而對已有驗證測試方案進行改進.

1 相關研究

1.1 軟件測試性定義

目前最具代表性的軟件測試性定義［9－11］是:軟件有效測試難易程度的指標，可表示［13］為

其中，s表示軟件規范;p表示程序實現;c表示測試準則;Pr表示概率.軟件測試性TAB可理解為:若根據c對軟件(s，p)進行充分測試時，軟件失效概率(或軟件缺陷的檢測概率)就是軟件測試性的體現.若設軟件中包含 r個缺陷 f1，f2，…，fr，則有

即不同缺陷具有不同的失效概率，此時使用單個缺陷的失效概率表示軟件測試性是不準確的，但目前尚未提供測試性的量化模型［13］.

1.2 對現有SRDT方案的分析

1.2.1 經典統計方法TRW的無失效考核方案

根據合同參數軟件失效概率指標p0、置信水平α及最大允許的失效數F，計算滿足可靠性指標要求所需的驗證測試用例數N.

無失效考核方案中不允許發生失效(即F=0)，對于給定的p0，當n個測試用例無失效運行后，對軟件失效概率不高于p0的置信度為

則對于規定的可靠性指標(p0，α)，驗證軟件達到可靠性指標的最小測試用例數為

其中，［·］表示對·取整

1.2.2 無先驗知識的Bayesian統計推斷方法

用β(a，b)來表示失效概率的先驗分布密度函數，則在Bayesian框架下，其后驗分布也是β分布，則失效概率的先驗密度分布函數［14］為

其中，a＞0;b＞0;β(a，b)為 Beta函數，即

當軟件執行完n個測試用例、發現r個失效，則失效概率的后驗分布為β(a+r，b+n－r)，即

對于無先驗的情況，有a=b=1，則有

對于給定(p0，α)，當無失效考核時所需要的最小用例數N為滿足下式中n的最小整數:

由式(8)可知，所需的最小用例數為

由式(2)和式(9)可知，無論是TRW方案還是Bayesian方案，在確定所需測試用例數時，只依據置信度和可靠性指標，與測試性無關.

2 軟件測試有效性定義和影響分析

2.1 軟件測試有效性的定義

借鑒文獻［15］給出的測試方法有效性定義，給出統計測試集合T的測試有效性的定義:T發現缺陷的測試有效性為在程序中有缺陷的情況下，T發現程序中有缺陷的概率.可表示為:ρT=Pr(測試集合T發現程序P中有缺陷/程序P中有缺陷)假設“程序中有缺陷”是恒成立的命題，則有

ρT=Pr(測試集合T發現程序P中有缺陷).

在一次測試中，該值可以表示為

顯然，T的測試有效性是受每一個缺陷fi的測試性影響的，但不同的T發現缺陷的能力常常不同，這點可由不同的T具有不同的覆蓋情況，從而發現不同的缺陷而簡單驗證.

2.2 測試有效性對SRDT測試量的影響分析

設Ω為所有程序P'組成的程序空間，P'是對程序P進行變異生成的任意程序，設PG為對P進行變異生成的完全無錯的程序版本.將Ω劃分成2個子域A1和A2，其中A1是具有下述屬性的程序集合:程序中包含缺陷，且任意缺陷都能被T發現或者程序是無錯的，即［16］

其中，fault∈P'表示 P'中的缺陷;failure∈T表示缺陷fault引起的失效failure能被T發現.

A2是具有下述屬性的程序的集合:程序包含缺陷，且所有缺陷都不能被T發現，即

圖1給出程序空間的劃分，結合測試有效性的概率形式的定義，得Pr(P∈A2|T)=1－ρT.

圖1 程序空間Ω的劃分

假定測試集合T測試程序P的結果為執行N個測試用例，發現0個失效，用符號o表示為:o={N個測試用例執行，發現了0個失效}.現象o出現，可能有下述2種情況:①P∈A1且 P=PG;②P∈A2且具有未知的失效概率∈［0，1］.

設f(θ|o，ρT)表示在出現現象o下的失效密度函數，則有

式中，f(θ|o，ρT)表示觀察到現象o、測試有效性為ρT下的條件失效密度函數;Pr(P∈A1)表示程序P屬于子域A1的概率，即程序P中有缺陷，且能被T發現的概率;Pr(P∈A2)表示程序P屬于子域A2的概率，即程序P中有缺陷，但不能被T發現的概率;δ(0)表示 delta函數［16］，delta分布本身是一個比較特殊的函數，表示如下:

其概率密度函數表示為

此處用于表示

即δ(0)表示此時的條件概率密度;β［1，N+1］(θ)表示N個測試用例執行下0個失效的后驗密度.

對于給定的(p0，α)，當不容忍失效時，所需最小用例數N為滿足下式中n的最小整數:

化簡上式可以得到

設 ρT=0，則有

不難看出式(16)與式(9)相同，這表明Bayesian方案中將測試有效性簡化為0.

下面對式(15)進行分析，令

兩邊同時對ρT求導，則有

因為0≤ρT＜1，0 ＜p0＜1，所以 Y'ρT＜0，即 Y 是 ρT的減函數，隨著ρT增加Y減小.

工程實踐中進行無失效考核往往需要數目龐大的測試用例數量［17］，原因之一是:對于不同的軟件來說，測試有效性越高，測試用例的缺陷探測性能越好，此時所需的測試用例量就少;反之，所需的測試用例量就大.但現有方案不考慮軟件在測試性方面的不同，進而不考慮測試集合在不同軟件的測試有效性的不同，而是把所有測試集合在軟件上的測試能力都忽略為0，從而從最保守估計的角度確定測試集合量的大小，無疑在某些情況下浪費了大量的測試用例.

3 測試有效性的定量估計

3.1 基本原理

假設P是Ω的一個隨機實現，利用統計故障注入法來得到ρT的定量估計，具體內容包括:

1)在P 的基礎上生成若干變異程序［18－20］P'，令P'中的缺陷具有與P相同的統計分布特征，這樣P'中的缺陷就包括原程序P中的缺陷和新植入的缺陷.由于原P中的缺陷不能被測試集合T檢測出來，這樣原來的缺陷就不會對T的測試有效性產生貢獻，因此T在P'上的測試情況就相當于其在無錯版本PG基礎上加隨機新植入缺陷集合(記為FSi)上的測試情況，即PG+FSi.觀察T在FSi上的測試情況相當于T在以PG為基礎而隨機注入缺陷所得版本上的測試情況.由于P本身就是一個以無錯版本PG為基礎而包含隨機錯誤的程序，所以觀察T在FSi上的測試情況就相當于T在P上的測試情況.

2)將隨機注入缺陷FSi得到的變異程序P'的集合分為2個子集，其中子集B1表示能夠被T檢測出錯誤的變異程序的集合，B2表示不能夠被T檢測出錯誤來的變異程序的集合，依據圖1所示的程序空間的劃分，計算出變異程序P'落入B1的概率，即求得測試有效性的定量估計值.

3.2 基本假設

下面給出上述原理成立所需要的一些基本假設:①所有植入缺陷引起的失效都能夠在輸出端被清楚地觀測到;②在故障注入之前，原程序P中的缺陷不能被T檢測出來;③每一個植入缺陷都是相互獨立的，植入的缺陷是與失效現象一一對應的.

3.3 構造變異程序

依據統計分布規律在人為植入故障的基礎上構造變異程序P'，具體步驟如下:

1)假設原程序的故障數服從某一概率分布，具體可以依據一些先驗信息來確定;

2)根據分布特征，在所有植入故障的集合中按照該統計分布隨機抽樣得到Mi個缺陷;

3)通過故障注入法將這Mi個缺陷注入到原程序P中，則得到變異程序P'.

以泊松分布為例對上述過程進行說明:

1)設程序中的故障數服從泊松分布，根據泊松分布的特點，需要利用參數λ進行泊松分布函數的構造，此時的λ代表程序中潛藏缺陷數目的平均值M^.對于程序P來說，M^可以根據程序的規模、復雜度等信息事先估計得到［21］.

2)獲得參數λ的估計值后，可以得到此分布的概率密度函數，如下式所示:

4)得到Mi的一個隨機抽樣值m后，從所有植入缺陷集合中隨機抽取m個缺陷通過故障注入技術注入到程序P中.植入的過程為:假定已經事先設計了N個錯誤，且滿足N?λ，且對每一個故障進行編號 1，2，…，N.在［0，1］區間內，隨機生成 m 個隨機數 η1，η2，…，ηm，令 Ki= ［(N －1)ηi］+1，i=1，2，…，m.這樣便得到 m 個故障編號K1，K2，…，Km.如果m個故障編號中有重復編號Ki，且重復次數為k，則只保留一個這樣的故障編號，刪除其他重復故障編號，重新再生成k－1個隨機數，按上述方法重新得到k－1個故障編號，直到最后得到m個不同的故障編號為止.再根據這m個故障編號把對應故障注入程序，即得到變異程序P'.

5)重復3)，4)，直至得到F個變異程序.F可以盡可能的大，也可以根據實際情況進行確定，但理論上講，F越大，意味著最后計算得到的ρT值越接近于真實值.

3.4 利用測試結果確定P'的分類

設FSi表示最后得到的第i個P'i的植入缺陷集合，i=1，2，…，F.每個錯誤集合 FSi包含的錯誤數量為Mi.利用T對P'i進行測試時，測試過程中會出現以下3種情況:

1)順序執行T中的測試用例，直到有一個失效產生，并且這個失效可以追蹤到新植入的缺陷集合FSi中的某個缺陷，則說明FSi能夠被T檢測出來，即此P'i屬于B1，記φ(FSi)=1;

2)順序執行T中的所有測試用例，但是沒有失效產生.這樣，缺陷集合FSi不能被T檢測出來，即此 P'屬于 B2，記 φ(FSi)=0;

3)順序執行T中的測試用例，直到有一個失效產生，并且對這個失效追蹤時發現，它不是由新植入的缺陷集合FSi中的任何一個缺陷產生的，那么由假設可知，它一定是新植入的缺陷與原程序P中的一個真實缺陷之間相互作用產生的相關錯誤，不滿足統計故障注入獨立性的特點.因此，將此缺陷從N個缺陷組成的缺陷集合中排除，并重新生成一個新的缺陷，對N個缺陷重新進行編號，重復3.3節中的步驟3)～5)，重新生成F個P'，并重新利用T對P'i進行測試，利用測試結果確定P'的分類.

重復上述過程，直至T對所有F個變異程序都完成測試，則可得T的測試有效性ρT如下:

式中，分子表示能夠被T檢測出缺陷的變異程序的個數，即B1中包含的程序數目.

4 測試有效性對SRDT測試量改進

4.1 驗證測試方案的改進

綜上，考慮測試有效性的影響，對無失效考核的SRDT方案進行改進，內容如下:①通過操作剖面隨機生成n個測試用例，一般來說，n≥50;②用該n個測試用例執行軟件時，未發生任何失效;③根據3.3和3.4節介紹的方法，獲得測試有效性ρT的定量估計值;④利用式(15)確定考慮了測試有效性影響的可靠性驗證測試所需的測試用例數量N;⑤通過操作剖面隨機生成N個測試用例，并執行上述N個測試用例;⑥在測試執行過程中，如果N個測試用例中發生了失效，則拒收;否則接收.

4.2 可靠性參數的估計

離散型軟件的可靠性評估是通過失效概率或成功率來完成的，此處定義失效概率為

其中，n為發生失效的測試用例數;N為測試用例總數.p的置信水平為1－α的置信限［23］為

其中，v1=2(N －n+1);v2=2n.

其中，v1=2(N－n);v2=2(n+1).

當n=0時，失效概率單側置信上限［24］為

連續型軟件的可靠性評估是通過失效率來完成的，失效率的上限值［25］如下式所示:

4.3 考慮測試有效性的優越性

表1給出不同(p0，α，ρT)下無失效考核的測試用例量N.

如果待驗證的指標為(p0，α)=(10－4，0.99)，按照 TRW 方案需要的測試用例數為46050，Bayesian方案需要測試用例數為46 049.而對于考慮測試有效性的Bayesian方案，當假定測試有效性ρT=0.5時，所需要的測試用例數為39118，測試用例數減少了 15.1%;假定 ρT=0.9時，所需要的測試用例數為23024，測試用例數則減少50%;所需測試用例數顯著下降.所以，考慮測試有效性的Bayesian方案對于減輕測試負擔是非常有效的，尤其在P0非常小的情況下.

5 結 束 語

本文從軟件測試性的角度出發，分析了其對軟件可靠性測試用例集合的影響，提出了測試有效性的概念.分析了測試有效性對于SRDT方案中測試量的影響，給出了測試量的量化表示模型，并比較了具有不同測試有效性的測試集合在數量上的差距，證明了TRW方案和Bayesian方案給出的測試量都是在假定測試有效性為零的情況下的保守估計，給出了統計故障注入方法下的測試有效性的定量估計方法和在該方法指導下改進的可靠性驗證測試方案及可靠性評估方法.

本文認為測試有效性對于改進SRDT方法、優化測試集合、縮小驗證測試工作量，提高測試效率具有重要的意義，當然，如果在測試用例集合選擇時，能夠優先選用測試有效性高的測試用例集合，既可以大大降低測試工作量，也為一些超高可靠軟件的SRDT提供了可能.

References)

［1］李秋英，姜夢岑.軟件可靠性驗證測試最小測試量的必要條件［J］.北京航空航天大學學報，2010，36(2):239 －243 Li Qiuying，Jiang Mengcen.Analysis of necessary condition for minimal software reliability demonstration test suite［J］.Journal of Beijing University of Aeronautics and Astronautics，2010，36(2):239－243(in Chinese)

［2］覃志東，雷航，桑楠，等.連續執行軟件可靠性驗證測試方法［J］.計算機科學，2005，32(6):202 －207 Qin Zhidong，Lei Hang，Sang Nan，et al.Reliability demonstration testingmethod for continuous execution software［J］.Computer Science，2005，32(6):202 －207(in Chinese)

［3］ Andy P，Wassim M，Yolanda M.Estimation of software reliability by stratified sampling［J］.ACM Transactions on Software Engineering and Methodology，1999，8(3):263 －283

［4］ Cukic B.Accelerated testing for software reliability assessment［C］//Biljanovic P.21st Annual International Conference MIPRO'98.Washington DC:IEEE Com Soc，1998:124 －129

［5］ Alam S，Chen H，Ehrlich WK，et al.Assessing software reliability performance under highly critical but infrequent event occurrences［C］//Philip G.8th ISSRE.Los Alamitos:IEEE Comp Soc，1997:294 －303

［6］ Hecht M，Hecht H.Use of importance sampling and related techniques to measure very high reliability software［C］//Joel S.Aerospace Conference Proceedings.Montana:IEEE Aerospace and Electronics Systems Soc，2000:533 －546

［7］ Tang D，Hecht M，Miller J.MEADEP and its applications in evaluating dependability for air traffic control systems［C］//Schueppert.Proceedings of the Annual Reliability and Maintainability Symposium Anaheim.Washington DC:IEEE Reliability Society，1998:19 －22

［8］顏炯，王戟，陳火旺.基于重要度抽樣的軟件統計測試加速［J］.計算機工程與科學，2005，27(3):64 －66 Yan Jiong，Wang Ji，Chen Huowang.Software statistical test acceleration based on importance sampling ［J］.Computer Engineering and Science，2005，27(3):64 －66(in Chinese)

［9］ IEEE SA 610.12-1990 IEEE standard glossary of software engineering terminology，［S］

［10］ ISO/IEC9126-91 Software engineering-product quality［S］

［11］ Hamlet D，Voas J.Faultson its sleeve:amplifying software reliability testing［C］//Thomas O.1993 ACM SGSOFT.Cambridge:ACM Society，1993:89 －98

［12］ Chen W，Untch R H，Rothermel G.Can fault-exposure-potential estimates improve the fault detection abilities of test suites?［J］.Journal of Software Testing，Verification，and Reliability，2002，4(2):197 －218

［13］趙亮，王建民，孫家廣.軟件易測性和軟件可靠性關系研究［J］.計算機學報，2007，30(6):986 －991 Zhao Liang，Wang Jianmin，Sun Jiaguang.Study on the relationship between software testability and reliability［J］.Chinese Journal of Computers，2007，30(6):986 －991(in Chinese)

［14］ Miller KW，Morell L J，Noonan R E.Estimating the probability of failure when testing reveals no failures［J］.IEEE Transactions on Software Engineering，1992，18(1):33 －43

［15］ Kuball S，Hughes G，May J，et al.The effectiveness of statistical testing when applied to logic systems［J］.Safety Science，2004，42(5):369－383

［16］ Kuball S，May J.Test-adequacy and statistical testing combining different properties of a test-set［C］//Stephanie K.15th ISSRE.Washington DC:IEEE Com Soc，2004:161 －172

［17］覃志東，雷航，桑楠，等.安全關鍵軟件可靠性驗證測試方法研究［J］.航空學報，2005，26(3):334 －339 Qin Zhidong，Lei Hang，Sang Nan，et al.Study on the feliability demonstration testing method for safety critical software［J］.Acta Aeronautica et Astronautica Sinica，2005，26(3):334 － 339(in Chinese)

［18］ Woodward M R，Halewood K.From weak to strong，dead or alive，an analysis of some mutation testing issues［C］//2nd Workshop on Software Testing，Verification and Analysis.Washington DC:IEEE Com Soc，1988:152 －158

［19］ Agrawal H，Demillo R，Hathaway B，et al.Design of mutant operators for the C programming language［R］.SERC-TR-41-P，2006

［20］趙性頌，顧斌.變異測試在嵌入式軟件中的應用［J］.微計算機信息，2009，25(11－2):87－88 Zhao Xingsong，Gu Bin.The application of mutation testing in embedded software ［J］.Microcomputer Information，2009，25(11－2):87－88(in Chinese)

［21］ Lyu M R.Handbook of software reliability engineering［M］.New York:McGraw Hill，1996

［22］楊為民，盛一興.系統可靠性數字仿真［M］.北京:北京航空航天大學出版社，1990:52－54 Yang Weimin，Sheng Yixing.System reliability digital simulation［M］.Bejing:Beijing University of Aeronautics and Astronautics Press，1990:52 －54(in Chinese)

［23］GB/T 4087.2-1983 數據的統計處理和解釋［S］GB/T 4087.2-1983 Statistical interpretation of data［S］(in Chinese)

［24］GB 4087.3-85 數據的統計處理和解釋二項分布可靠度單側置信下限［S］GB 4087.3-85 Statistical interpretation of data One-sided reliability confidence lower limit［S］(in Chinese)

［25］ Kececioglu D.Reliability and life testing handbook［M］.NJ:Prentice Hall，Englewood Cliffs，1993:722 － 724

(編 輯:婁 嘉)

Effects of software test efficiency on software reliability demonstration testing effort

Li Qiuying Li Haifeng Wang Jian

(School of Reliability and Systems Engineering，Beijing University of Aeronautics and Astronautics，Beijing 100191，China)

To solve the problem that in the traditional software reliability demonstration testing(SRDT)，software testability was not considered as one of the possible influence factors on test effort，a method which introduced test efficiency to improve the quantity model of minimal sample size in SRDT was put forward.The definition of software testability and its effect on software reliability test suite were analyzed.The concept of test efficiency was proposed.The difference between the numbers of test cases with different test efficiency and whether efficiency is considered were compared.It was demonstrated in detail that the traditional method and the Bayesian method with no prior knowledge are all the conditions where the testefficiency equaled to zero，so both the methods gave the most conservative value.The improved method combined with the testefficiency was recommended.Based on the principle of statistical fault injection，the quantitative estimation method of testefficiency was proposed and the process and the estimation method were shown by a case study.

software reliability;demonstrations;testing;efficiency;effects;estimation

TP 311

A

1001-5965(2011)03-0325-06

2010-10-11

國防科技工業技術基礎科研項目(Z132010B001)

李秋英(1973 －)，女，黑龍江大慶人，講師，li_qiuying@buaa.edu.cn.