馬振宇,， 吳 緯， 張 威， 劉福勝， 韓 坤

(1. 裝甲兵工程學(xué)院技術(shù)保障工程系， 北京 100072； 2. 裝甲兵工程學(xué)院信息工程系， 北京 100072；3. 北京特種車輛研究所， 北京 100072)

基于斐波那契迭代算法的貝葉斯軟件可靠性驗(yàn)證測(cè)試方案

馬振宇1,2， 吳 緯3， 張 威2， 劉福勝1， 韓 坤3

(1. 裝甲兵工程學(xué)院技術(shù)保障工程系， 北京100072；2. 裝甲兵工程學(xué)院信息工程系， 北京100072；3. 北京特種車輛研究所， 北京100072)

針對(duì)軟件可靠性驗(yàn)證測(cè)試方案不能真實(shí)反映軟件可靠性水平的問題，首先，根據(jù)貝葉斯原理構(gòu)建了可靠性驗(yàn)證測(cè)試方案框架，并給出超參數(shù)的求解辦法；然后，分析斐波那契排序規(guī)律，提出了斐波那契迭代算法；最后，提出了基于斐波那契迭代算法的貝葉斯軟件可靠性驗(yàn)證測(cè)試方案，并對(duì)其進(jìn)行實(shí)例驗(yàn)證。結(jié)果表明：斐波那契迭代算法能夠真實(shí)地反映軟件實(shí)際失效概率；在相同的置信度條件下，基于斐波那契迭代算法的貝葉斯軟件可靠性驗(yàn)證測(cè)試方案能夠明顯減少測(cè)試所需的測(cè)試用例數(shù)。

斐波那契迭代算法； 貝葉斯方法； 可靠性驗(yàn)證測(cè)試； 軟件可靠性

軟件產(chǎn)品進(jìn)行驗(yàn)收時(shí)，為檢測(cè)軟件的可靠性指標(biāo)是否達(dá)標(biāo)，必須要通過軟件可靠性驗(yàn)證測(cè)試[1]。通常情況下，驗(yàn)證結(jié)果的置信度越高，軟件的可靠性越好，但會(huì)大幅增加測(cè)試人員的工作量。特別是針對(duì)一些技術(shù)復(fù)雜、成本高和可靠性高的軟件產(chǎn)品，驗(yàn)收時(shí)所產(chǎn)生的經(jīng)濟(jì)成本、人力成本和時(shí)間成本難以接受，導(dǎo)致軟件可靠性驗(yàn)證測(cè)試難以進(jìn)行。然而，使用貝葉斯方法(Bayesian method)可有效利用先驗(yàn)信息，在保證高置信度的條件下，能夠顯著減少可靠性驗(yàn)證測(cè)試的工作量。

目前，研究者針對(duì)貝葉斯軟件的可靠性驗(yàn)證測(cè)試方法進(jìn)行了大量工作。如：覃志東等[2-3]應(yīng)用構(gòu)造共軛分布的貝葉斯方法進(jìn)行可靠性驗(yàn)證，利用先驗(yàn)信息為后驗(yàn)提供大量的實(shí)驗(yàn)信息，進(jìn)而提出了基于先驗(yàn)動(dòng)態(tài)整合的可靠性驗(yàn)證測(cè)試方法，該方法可很好地應(yīng)用到實(shí)際工程中；王學(xué)成等[4]提出了基于減函數(shù)的先驗(yàn)分布構(gòu)造法進(jìn)行測(cè)試驗(yàn)證的方案，該方案在測(cè)試條件相同的情況下，可大幅縮短所需要的測(cè)試時(shí)長；劉廣等[5]提出了基于減函數(shù)的多層貝葉斯軟件可靠性驗(yàn)證測(cè)試方法，該方案通過雙層貝葉斯方法進(jìn)一步縮短了測(cè)試時(shí)長。

雖然前人[2-8]已進(jìn)行了許多相關(guān)研究，但均在事先設(shè)定軟件可靠性指標(biāo)的前提下開展軟件可靠性驗(yàn)證測(cè)試工作，這使得測(cè)試結(jié)果難以真實(shí)客觀地反映軟件實(shí)際的可靠性。盡管已有的二分(折半)查詢法可解決該問題，但斐波那契迭代算法的查詢平均性能更優(yōu)。因此，筆者通過斐波那契迭代算法，預(yù)期得到軟件的實(shí)際失效概率，并同時(shí)為軟件的驗(yàn)證方法提供可靠性驗(yàn)證測(cè)試方案。

1 基于貝葉斯方法的可靠性驗(yàn)證測(cè)試方案

1.1基于貝葉斯方法的可靠性驗(yàn)證測(cè)試方案框架

(1)

式中：p為被測(cè)軟件的可靠性參數(shù)。本文設(shè)定p為失效概率。

假設(shè)p的先驗(yàn)分布函數(shù)為π(p)，則由失效概率和失效次數(shù)構(gòu)成的聯(lián)合分布函數(shù)為

(2)

該函數(shù)將先驗(yàn)信息和樣本信息有效地結(jié)合在一起。為了對(duì)p做出統(tǒng)計(jì)決策，引入條件分布(后驗(yàn)分布)

(3)

將聯(lián)合分布函數(shù)進(jìn)行變形，則有

(4)

式中：

(5)

為邊緣分布函數(shù)。

設(shè)定軟件可靠性驗(yàn)證測(cè)試方案的指標(biāo)為(p0，c，rm)，其中p0為規(guī)定的軟件失效概率、c為置信度、rm為通過驗(yàn)證測(cè)試時(shí)的最大失效次數(shù)，則驗(yàn)證測(cè)試所需要的最小測(cè)試用例數(shù)nm為滿足下列不等式的最小整數(shù)解，即有

(6)

假設(shè)每次軟件測(cè)試均符合n重伯努利實(shí)驗(yàn)[9-10]，那么在軟件可靠性驗(yàn)證測(cè)試中，累計(jì)出現(xiàn)X次失效次數(shù)的概率符合二項(xiàng)分布，即

(7)

進(jìn)一步推導(dǎo)出失效概率的先驗(yàn)分布為貝塔分布，即

(8)

通常在結(jié)束軟件測(cè)試后，會(huì)得到n′個(gè)測(cè)試用例，其中共有r′次失效，則失效概率的后驗(yàn)分布應(yīng)為B(a+r′,b+n′-r′)，即

(9)

進(jìn)行軟件可靠性驗(yàn)證測(cè)試時(shí)，要求驗(yàn)證結(jié)果不能出現(xiàn)失效。在無失效的情況下，最少測(cè)試用例數(shù)應(yīng)為滿足下列不等式的最小整數(shù)解nm，即

(10)

1.2超參數(shù)求解

根據(jù)超參數(shù)的求解原理[3]，可得超參數(shù)的具體估計(jì)過程為：首先，選用以往測(cè)試過程中遺留下的最后m組測(cè)試記錄作為先驗(yàn)信息，每組含有l(wèi)個(gè)測(cè)試用例；然后，統(tǒng)計(jì)每組測(cè)試用例中造成軟件失效的數(shù)量，分別記作k1,k2,…,km；最后，求得失效概率的經(jīng)驗(yàn)值tj=kj/l(j=1,2,…,m)。

結(jié)合式(5)、(7)、(8)，根據(jù)樣本的邊緣分布，可得

(11)

進(jìn)而求得m(r)對(duì)應(yīng)的一階矩為

(12)

同理，可得h(r)的二階矩，即

(13)

將E(r)、E(r2)記作w1、w2，則有

(14)

式中：D=(n-1)w12+n(w1-w2)。

w1、w2可通過經(jīng)驗(yàn)樣本值的期望估計(jì)得到，即

(15)

將式(15)代入式(14)中，即可估計(jì)出超參數(shù)a、b的值。

2 基于斐波那契迭代算法的貝葉斯驗(yàn)證方案

2.1斐波那契迭代算法

斐波那契(Fibonacci)算法是依據(jù)對(duì)有序表進(jìn)行斐波那契查找[11]演變而來，而斐波那契查詢法是在原有的二分(折半)查詢法基礎(chǔ)上改進(jìn)而來，該方法在計(jì)算過程中只進(jìn)行加減運(yùn)算，不進(jìn)行除法運(yùn)算，因此斐波那契迭代算法查詢平均性能要比二分查詢法更優(yōu)。

首先構(gòu)造斐波那契序列，即

0,1,1,2,3,5,8,13,21,34,…。

(16)

由于任意一個(gè)有序序列的2個(gè)端點(diǎn)和中位點(diǎn)均與斐波那契數(shù)有聯(lián)系。根據(jù)斐波那契排列規(guī)律提出如下定義：

(17)

假設(shè)一個(gè)有序序列內(nèi)共有m′個(gè)元素，且元素的個(gè)數(shù)等于某一個(gè)斐波那契數(shù)減去1，即m′=F(k)-1。若m′≠F(k)-1,則將該有序序列的最后1個(gè)元素重復(fù)填充到該序列，直到填充后序列中元素的個(gè)數(shù)與鄰近的斐波那契數(shù)減1相等為止。

斐波那契迭代算法的基本原理為：對(duì)于一個(gè)序列中元素個(gè)數(shù)為F(k)-1的有序序列，令中位點(diǎn)為Fmid=Fmin+F(k-1)-1，(其中Fmin為該有序序列中最小元素的值)，得到分割以后的序列，其中左子序列中元素的個(gè)數(shù)為F(k-1)-1，右子序列中元素的個(gè)數(shù)為(F(k)-1)-(F(k-1)-1)-1=F(k-2)-1。由此可以看出：2個(gè)子序列中元素的個(gè)數(shù)依舊滿足某一個(gè)斐波那契數(shù)減1，因此能夠反復(fù)對(duì)該序列進(jìn)行分割。具體過程如下：

1)對(duì)相關(guān)變量進(jìn)行初始化。Fmin=a′;Fmax=F(k),為該有序序列中最大元素的值，其中F=F(k)-1為該有序序列的長度;b′=F(k-1)-1，為中位點(diǎn)的相對(duì)偏移量。

2)若Fmin>Fmax，則查詢失??；否則，F(xiàn)mid=Fmin+b′。

3)若F(k)Fmid，則F=F-b′-1,b′=b′-F-1,Fmin=Fmid+1，繼續(xù)轉(zhuǎn)入步驟2)；若F(k)=Fmid，則表示查尋成功，結(jié)束該迭代過程。

2.2算法實(shí)現(xiàn)

一般來說，基于貝葉斯方法的軟件可靠性驗(yàn)證測(cè)試均提前對(duì)其失效概率進(jìn)行了假設(shè)，通常未考慮軟件本身實(shí)際的失效概率。為此，筆者在進(jìn)行貝葉斯驗(yàn)證之前，通過斐波那契算法來確定被測(cè)軟件的實(shí)際失效概率，這樣既可使用軟件實(shí)際的失效概率代替原來假設(shè)的失效概率，使軟件可靠性驗(yàn)證測(cè)試過程更貼近實(shí)際；也可很好地利用先驗(yàn)貝葉斯的優(yōu)勢(shì)，在不降低試驗(yàn)結(jié)果置信度的前提下，有效減少所需測(cè)試用例數(shù)。

首先，對(duì)軟件可靠性進(jìn)行評(píng)估，可通過以往經(jīng)驗(yàn)估計(jì)出該軟件失效概率大致的取值范圍，并設(shè)定兩端的閾值；然后，通過斐波那契迭代算法找到實(shí)際失效概率的大致范圍(誤差不會(huì)超過1個(gè)數(shù)量級(jí))；最后，確定軟件的實(shí)際失效概率。圖1為基于貝葉斯驗(yàn)證的斐波那契迭代算法實(shí)現(xiàn)步驟，具體過程如下：

圖1 基于斐波那契迭代算法的貝葉斯驗(yàn)證實(shí)現(xiàn)步驟

2)將(phigh,c)代入式(10)。若未出現(xiàn)失效，則p實(shí)

3)將(plow,c)代入式(10)。若未出現(xiàn)失效，則p實(shí)

4)令Fmid=Fmin+F(k-1)-1，將(pmid,c)代入式(10)。(1)若出現(xiàn)失效，則pmid≤p實(shí)

5)令Fmin=Fmin-1,phigh=10-Fmin，將(phigh,c)代入式(10)。若未出現(xiàn)失效，再將(0.1phigh-ε,c)、(0.1phigh+ε,c)分別代入式(10)，若結(jié)果分別是未失效、失效，則p實(shí)=0.1phigh，否則p實(shí)=phigh，此時(shí)迭代結(jié)束，求出最少測(cè)試用例數(shù)nm；若出現(xiàn)失效，則繼續(xù)重復(fù)執(zhí)行步驟5)。

6)令Fmax=Fmax+1,plow= 10-Fmax,將(plow,c)代入式(10)。若出現(xiàn)失效，再將(plow-ε,c)、(plow+ε,c)分別代入式(10)，若結(jié)果分別是未失效、失效，則p實(shí)=plow，否則p實(shí)=10plow，此時(shí)迭代結(jié)束，求出最少測(cè)試用例數(shù)nm；若未出現(xiàn)失效，則繼續(xù)重復(fù)執(zhí)行步驟6)。

3 實(shí)例驗(yàn)證

試驗(yàn)數(shù)據(jù)來自特種車輛軟件測(cè)評(píng)中心對(duì)某項(xiàng)目進(jìn)行實(shí)測(cè)得到的數(shù)據(jù)結(jié)果。首先，根據(jù)斐波那契迭代算法求解出實(shí)測(cè)軟件的失效概率，假設(shè)Fmin=1,Fmax=12，構(gòu)造一個(gè)差值為1的等差數(shù)列，那么phigh=10-1、plow=10-12，軟件自身的失效概率計(jì)算結(jié)果如表1所示；然后，收集軟件可靠性測(cè)試過程中最后10組數(shù)據(jù)作為先驗(yàn)信息的歷史數(shù)據(jù)，每組測(cè)試用例數(shù)均為100000，每組出現(xiàn)的失效次數(shù)如表2所示；最后，依據(jù)本文提出的軟件可靠性驗(yàn)證測(cè)試方案所得到的實(shí)驗(yàn)結(jié)果，驗(yàn)證該方法的有效性。

表1 基于斐波那契迭代算法的軟件自身失效概率計(jì)算結(jié)果

表2 先驗(yàn)信息失效數(shù)據(jù)

由表1可知：在置信度為99%的條件下，實(shí)測(cè)軟件的失效概率為0.001。根據(jù)表2中的歷史信息，并結(jié)合式(12)-(15)，算出超參數(shù)a=1,b=2 067。

根據(jù)求得的軟件本身實(shí)際的失效概率值以及超參數(shù)的估計(jì)值，設(shè)定軟件可靠性驗(yàn)證測(cè)試方案的可靠性指標(biāo)(p0，c，rm)=(0.001，0.99，0)，即置信度為99%，失效概率為0.001，最大允許失效次數(shù)為0。結(jié)合式(10)可得：在有先驗(yàn)信息的條件下，軟件可靠性測(cè)試所需測(cè)試用例數(shù)為2 536，在無先驗(yàn)信息條件下所需測(cè)試用例數(shù)為4 602。這說明在保證置信度不變的條件下，所需測(cè)試用例數(shù)減少了2 066個(gè)，即可完成軟件可靠性驗(yàn)證測(cè)試，論證了該方案的有效性。

4 結(jié)論

筆者基于斐波那契迭代算法求得被測(cè)軟件的自身實(shí)際失效概率，且客觀真實(shí)地反映出實(shí)測(cè)軟件的實(shí)際可靠性。另外，在保證相同的置信度條件下，基于斐波那契迭代算法的貝葉斯軟件可靠性驗(yàn)證測(cè)試方案能夠顯著降低可靠性驗(yàn)證測(cè)試所需測(cè)試用例數(shù)量。然而，對(duì)測(cè)試用例的選用如何做到完全隨機(jī)性選擇，還需要在以后的研究中進(jìn)一步完善。

[1] 李海峰,劉暢,鄭軍.安全關(guān)鍵軟件可靠性驗(yàn)證測(cè)試研究[J].航空標(biāo)準(zhǔn)化與質(zhì)量,2013(3):46-50,58.

[2] 覃志東,雷航,桑楠,等.連續(xù)執(zhí)行軟件可靠性驗(yàn)證測(cè)試方法[J].計(jì)算機(jī)科學(xué),2005,32(6):202-205.

[3] 覃志東,雷航,桑楠,等.安全關(guān)鍵軟件可靠性驗(yàn)證測(cè)試方法研究[J].航空學(xué)報(bào),2005,26(3):334-339.

[4] 王學(xué)成,陸民燕,李海峰,等.帶減函數(shù)的連續(xù)型軟件可靠性驗(yàn)證方案[J].重慶大學(xué)學(xué)報(bào)(自然科學(xué)版),2012,35(10):136-143.

[5] 劉廣,黃百喬,劉暢,基于減函數(shù)的多層貝葉斯離散型軟件可靠性驗(yàn)證測(cè)試方案[J].計(jì)算機(jī)應(yīng)用研究,2017,33(3):761-764.

[6] 張文杰,楊華波,張士峰.基于Bayes混合驗(yàn)前分布的成敗型產(chǎn)品可靠性評(píng)估[J].兵工學(xué)報(bào),2016,37(3):505-511.

[7] 劉解放,劉思峰,方志耕.成敗型產(chǎn)品可靠性評(píng)價(jià)的加權(quán)Bayes方法[J].中國機(jī)械工程,2013,24(24):3371-3374.

[8] 馮文哲,劉琦.成敗型產(chǎn)品的Bayes可靠性驗(yàn)證試驗(yàn)設(shè)計(jì)[J].航空動(dòng)力學(xué)報(bào),2012,27(1):110-117.

[9] 劉海濤,張志華,董理.成敗型產(chǎn)品可靠性的Bayes驗(yàn)收方案研究[J].兵工學(xué)報(bào),2016,37(3):565-569.

[10] 劉琦,王囡,唐旻.成敗型產(chǎn)品基于驗(yàn)后概率的Bayes序貫檢驗(yàn)技術(shù)[J].航空動(dòng)力學(xué)報(bào),2013,28(3):494-500.

[11] 齊悅,夏克儉,姚琳.數(shù)據(jù)結(jié)構(gòu)、算法與應(yīng)用[M].北京：清華大學(xué)出版社,2015.

(責(zé)任編輯: 尚菲菲)

BayesianSoftwareReliabilityDemonstrationTestingSchemeBasedonFibonacciIterationAlgorithm

MA Zhen-Yu1,2, WU Wei3, ZHANG Wei2, LIU Fu-Sheng1, HAN Kun3

(1. Department of Technical Support Engineering, Academy of Armored Force Engineering, Beijing100072, China；2. Department of Information Engineering, Academy of Armored Force Engineering, Beijing100072, China;3. Beijing Special Vehicle Research Institute, Beijing100072, China)

The software reliability demonstration testing cannot really reflect the software reliability level. To solve that problem, the framework of software reliability demonstration testing is constructed according to the Bayesian principle, and the solution of parameters is also given. Then the Fibonacci sort principle is analyzed, and Fibonacci iteration algorithms proposed. Finally, a Bayesian software demonstration testing scheme based on Fibonacci iterative algorithms put forward and verified. Examples show that the Fibonacci iterative algorithm can reflect the actual software failure probability, Bayesian software demonstration testing scheme based on Fibonacci iterative algorithm can obviously reduce the number of testing cases at the same confidence level.

Fibonacci iteration algorithm; Bayesian method; reliability demonstration testing; software reliability

1672-1497(2017)04-0116-05

2017-05-04

軍隊(duì)科研計(jì)劃項(xiàng)目

馬振宇(1991-)，男，博士研究生。

O213.2；TP311.5

：ADOI：10.3969/j.issn.1672-1497.2017.04.022