软件可靠性测试充分性的多准则判定及应用

第35卷 第9期2007年 9月 华 中 科 技 大 学 学 报(自然科学版)

J.HuazhongUniv.ofSci.&Tech.(NatureScienceEdition)Vol.35No.9 Sep. 2007

软件可靠性测试充分性的多准则判定及应用

刘剑豪 刘晓明 黄 松

(解放军理工大学指挥自动化学院,江苏南京210007)

摘要:在分析软件可靠性测试充分性特点的基础上,提出一种多准则充分性判定方法.依据运行剖面构造系统的使用模型,通过假设检验和贝叶斯推断确定测试用例数量,建立差异函数判断测试模型与使用模型的偏离,根据软件失效情况进行多轮次充分性判定,并使用贝叶斯方法积累测试信息,同时利用测试结果开展软件可靠性的评价与预测.实例分析表明,多准则充分性判定方法对可靠性测试用例集要求更加严格,使得根据该测试用例集的测试结果开展可靠性评价与预测更具可信性.关 键 词:软件可靠性;可靠性测试;测试充分性;多准则判定

中图分类号:TP311.5 文献标识码:A 文章编号:1671-4512(2007)09-0129-04

Multiplecriteriadeterminationofsoftwarereliabilitytesting

adequacyanditsapplication

LiuJianhao LiuXiaoming HuangSong

(InstituteofCommandAutomation,PLAUniversityofScienceandTechnology,Nanjing210007,China)

Abstract:Testingadequacycharacteristicsinsoftwarereliabilityassessmentandpredictionwasana-lyzed.Amultiplecriteriadeterminationmethodisproposed.Usagemodelwasbuiltaccordingtooper-ationalprofile.ThestatisticalhypothesistestingandBayesianmethodwereusedinjudgingtestcasequantity,anddifferencefunctionwasusedtocalculatethedeviationbetweentestingmodelandusagemodel.Whensoftwarefailurewasfoundandcorrected,adequacywasanalyzedinthenextround.TestinginformationwascountedinthepriorBayesianparameters,andwasusedtoreliabilityassess-mentandprediction.Casestudyshowsthattheusedmethodismoreserious,andthereliabilityas-sessmentandpredictionareofmorecreditability.

Keywords:softwarereliability;reliabilitytesting;testingadequacy;multiplecriteriadetermination 如何评价软件的可靠性是计算机学科研究的一个重要方向.可靠性测试数据的选择和测试充分性的判定是进行可靠性评价的基础,其中测试充分性的判定将直接影响可靠性评价的可信性.因此,如何对可靠性测试的充分性进行判定成为开展软件可靠性评价的一个关键问题.本文综合考虑使用模型与测试模型的比较、统计假设检验和贝叶斯推断,给出一种多准则充分性判定的可靠性测试和可靠性度量方法.

1 测试充分性

测试的充分性要解决的问题是测试究竟进

行到什么程度可以停下来?目前采用的标准都是基于软件在有限多个测试用例上的行为特征可以代表软件所有情况下的行为特征的假设建立的.因此评价的可信性和准确性完全依赖于/有限多个测试用例0的选择.对于/选哪些,选多少?0采用不同的策略就形成不同的充分性判定准则.

[1]

收稿日期:2006-07-21.

作者简介:刘剑豪(1978-),男,博士研究生;南京,解放军理工大学指挥自动化学院(210007).E-mail:[email protected]

#130#

华 中 科 技 大 学 学 报(自然科学版)

s

e

j

第35卷

可靠性测试充分性准则主要可以分为4类:a.基于使用模型与测试模型差异比较的充分性准则(简称模型比较准则).b.基于传统统计学的充分性准则(简称统计准则[4,5]).c.基于贝叶斯统计推断的充分性准则(简称贝叶斯准则

[6,7]

[2,3]

Pi=(1-Ps+1)

eIc

j

Fp

i

i=1

EP.

i

(1)

此时的运行剖面可以用基本用例集表示为U={(c1,P1),(c2,P2),,,(cs,Ps),(Os+1,Ps+1)},该剖面代表了软件的使用方式,即为软件使用模型.

2.2 测试充分性的假设检验判定

在首轮可靠性测试时一般不具有先验信息,因此采用统计假设检验方法确定所需的测试用例数.给出系统失效概率H与系统可靠性要求H0之

H0:H[H0;

0,H1:H>H

).d.基于可靠性增长的充分性准则(简称

[8,9]

增长准则).这4类准则各有其优缺点.

2 可靠性测试充分性的多准则判定

仔细考虑可靠性测试的特点,利用各类准则从多个不同的角度建立判断标准,对充分性问题给出更全面更严格的判定,从而提高可靠性评价与预测的准确性和可信性.本文建立的可靠性测

试充分性判定流程如图1所示

.

同时假设系统每次运

行是否失效满足贝努利实验的统计独立性.因此,N个测试用例对应的N次系统运行中失效用例数R服从二项分布

r

P(R=r)=CrNH(1-H)N-r.

(2)

作为最后的性能评价,可靠性测试应该不发生失效.在N个用例执行中无失效时,要求犯第Ⅱ类错误的概率(H0为假时,接受H0的概率)不大于给定的显著水平A(对应的置信度C=1-A),则P{r=0|H}=(1-H)[(1-H0)

由此可得

N\lnA/ln(1-H0),

2.3 测试用例集的产生

图1 充分性判定流程

N

N

[A.

(3)

需要的最小用例数为满足式(3)的最小值Nmin.在马氏链表示的软件系统中,一个测试用例

代表一条从系统初始点到终止点的路径.因此,依马氏链和转移向量P随机产生从初始点到终止点的测试路径即为测试用例.以式(3)判定用例集中用例数量的充分性,产生的Nmin个测试用例和每个用例产生时的顺序共同构成待测用例序列集T={(li,qi)|1[i[Nmin},其中li是第i条路径,qi是路径li出现的序号.

2.4 测试充分性的模型差异判定

由于测试用例对应的测试路径是随机产生的,因此用例集T中可能存在大量重复路径,这种重复代表了测试用例集在各剖面上的测试比例.假设T中有非重复路径Nd条,每条路径出现nj次,则Tc={(li,nj/Nmin)|1[j[Nd}是待测用例集所代表的测试模型.将测试模型Tc中不属于Cs

的路径lj

E

j

j

2.1 使用模型的建立

根据软件系统组成部分的划分,利用马尔可夫链(简称马氏链)建立软件的使用模型,用组成部分间的有向转移图来表示.将马氏链看作传统结构性测试中的控制流,则采用正确性测试充分性准则中的控制流覆盖准则可以产生一组测试路径作为基本用例集,记为Cs={c1,c2,,,cs},共有s个用例.

假设系统中组成部分间的转移概率向量P={pi|1[i[N,0[pi[1},其中系统各组成之间共有Ne条转移边,pei为第i条边的转移概率.根

e

e

e

据基本用例集构造系统运行剖面,表示为U={(O1,P1),(O2,P2),,,(Os,Ps),(Os+1,Ps+1)}.Cs中的每个用例代表一类剖面Oi(i=1,2,,,s),未在Cs中出现的路径为单独的一类剖面Os+1(简称混合剖面类),Pi(i=1,2,,,s)为对应剖面类的发生概率.假设给定剖面Os+1的出现概率为Ps+1,则Pi可以通过马尔可夫有向图中

,合并为一个剖面类nj/Nmin,则测试模型Tc=

c

c

s

c

Ocs+1,Ps+1=

lIT,l|C

c{(c1,Pc1=nc/Nmin),(c2,P2=nc/Nmin),,,12

(cs,Ps=ncs/Nmin),(Os+1,Ps+1)}.

c

第9期

s+1

刘剑豪等:软件可靠性测试充分性的多准则判定及应用

#131#

D(U,Tc)=

i=1

Elog(P/P),

i

ci

(4)

f(H|0,N,a+r,b+M)=Ha+r-1(1-H)b+M+N-r-1/[B(a+r,b+M+N-r)].(7) 要求以C的置信度判定系统失效概率H小于或等于要求值H0,根据该后验分布,新一轮测试所需用例数N应满足P(H[H0)\1-A,即

差异函数D(U,Tc)越接近0,说明测试模型与使

用模型的差异越小,测试模型越能代表使用模型.根据式(4)的定义可知,当待测用例集不包含某个基本用例ci时,D(U,Tc)→].这说明当测试模型未能覆盖使用模型要求的基本剖面类型时,该测试模型严重不符合要求.当差异函数值较大,测试模型不满足要求时,可以考虑重新依转移概率产生待测用例集,但会浪费先前产生的用例.因此,可以在已经产生的待测用例集的基础上,依转移概率矩阵追加测试用例,并重新进行模型差异比较.在差异函数值较小,可以接受用例集T时,依据生成的顺序qi执行T中产生的用例(共Nmin个).

2.5 测试充分性的贝叶斯判定

当执行测试用例中发生失效时,需查找、纠正缺陷,并进行新一轮可靠性测试.采用贝叶斯统计推断的方法将失效概率H看作随机变量,利用该随机变量的后验分布与先验分布的关系来整合已有的测试信息.此时,式(2)表示的是样本x1,x2,,,xN中失效数R在条件为H时的条件分布.根据共轭分布原则,对于满足式(2)的样本条件分布,随机变量H的先验分布应该选择样本条件分布的共轭分布,即选B分布:f(H)=HH)b-1/B(a,b),式中B(a,b)=

a-1

Qf(H|0,N,a+r,b+M)dH\1-A.

H0

无其他先验信息的情况下,取a=b=1,化简得

Qf(H|0,N,1+r,1+M)dH=

H0

1-(8)

i=0

EC

r

i

M+1+N

H0(1-H0)

iM+1+N-i

\1-A.

依马氏链和转移向量产生新的测试用例,补充待测用例集.利用式(8)确定的最小用例数N(记为Nmin)判定用例集中用例数量的充分性,并

在满足模型差异判定后,开始执行新一轮可靠性测试.

2.6 可靠性评价与预测

在经过k轮测试后,前k-1轮共执行了Msum个用例,且发生rsum个失效,第k轮通过了由式(8)确定的N个测试用例(记为Nmin).此时,对软件系统的可靠性评价为:有C=1-A的置信度认为软件系统的失效概率H[H0.该可靠性评价是基于测试的历史信息对系统可靠性现状作出的评价.很多情况下需要对系统将来的可靠性进行预测,由式(7)的后验分布,将来Nf次软件使用中,发生rf次失效的概率

P(RF=rf|0,Nmin,1+rsum,1+Msum)=

end

end

next

(1-

Q

1

a-1b-1

H(1-H)dH0

是B函数,无其他先验信息时取a=b=1.

假设执行了M个用例,且发生r次失效(M[Nmin,1[r[M),显然系统未能连续无失效地通过Nmin个用例的测试,也达不到预期的可靠性要求,因此在纠正发现的缺陷后需要进行新一轮可靠性测试.对r个失效中发现的缺陷进行纠正后,由贝叶斯估计可得H的后验分布

f(H|r,M,a,b)=HH)

b+M-r-1

a+r-1

Q

1

r

f(1-HCNffH)Nf-rf#

r

Nend+M

-r

r

summinsumsum

dH.

B(1+rsum,1+Nmin+Msum-rsum) 由不发生失效的概率大于置信度要求值

end

P(RF=0|0,Nmin,1+rsum,

1+Msum)\1-Ac,

即

(5)

(9)

(1-

/[B(a+r,b+M-r)],

此后验分布与先验分布属同类分布,同时执行用例数M和发生失效数r整合为后验分布的参数.

显然

f(H|r,M,a,b)=f(H|0,0,a+r,b+M)=Ha+r-1(1-H)b+M-r-1/[B(a+r,b+M-r)].(6) 式(6)表明可以将已有测试信息(M,r)积累到先验分布参数(a,b)当中,而式(5)等号右端的形式在式(6)中保持不变.设新一轮要求系统连续无失效通过的测试用例数为N,根据式(6),此时Q

1

r

sum(1-H(1-H)Nf{H)Nmin+Msum-rsum/0

end

end

[B(1+rsum,1+Nmin+Msum-rsum)]}dH=

B(1+rsum,1+Nendmin+Msum-rsum+Nf)/

end[B(1+rsum,1+Nmin+Msum-rsum)]\1-Ac,

可以预测在Cc=1-Ac置信度下,系统最大不发生失效的软件使用次数Nf(记为Nf).

max

3 应用举例

[

#132#

华 中 科 技 大 学 学 报(自然科学版) 第35卷

个开始节点V0和一个结束节点V11.假设软件系统的结构与各组成部分之间的关系与该图一致,并假设边e0~e16的转移概率向量为{1.0,0.3,0.7,0.4,0.5,0.5,1.0,0.6,0.3,0.4,0.6,1.0,0.7,1.0,1.0,0.2,0.8},如图2所示

.

可以接受的情况下进行下一轮测试.假设第二轮测试全部通过,则对系统的可靠性评价为以C=0.99的置信度认为系统失效概率H[0.001.然而由式(9),预测的系统在同样的置信度下,最大不发生失效的使用次数Nmaxf=25.

由结果可知,预测的无失效使用次数25远远低于测试中系统最终通过的无失效用例数7541.这也说明基于/现状0的预测比基于/历史0的评价更加困难,只有系统更加稳定、更有规律才能预测系统较长时间的行为.

参

考

文

献

[1]GoodenoughJB,GerhertSL.Towardatheoryof

testdataselection[J].IEEETransactionsonSoft-wareEngineering,1975,1(2):156-173.

[2]WhittakerJA,ThomasonMG.AMarkovchain

modelforstatisticalsoftwaretesting[J].Transactions

on

Software

Engineering,

20(10):812-824.

[3]RosariaS,RobinsonH.Applyingmodelsinyourtes-tingprocess[J].InformationandSoftwareTechnolo-图2 系统转移概图

gy,2000,42(12):815-824.

[4]HowdenWE.Confidence-basedreliabilityandstatis-ticalcoverageestimation[C]MThe8thInternationalSymposiumonSoftwareReliabilityEngineering(IS-SRE1997).Albuquerque:ComputerSocietyPress,1997:283-291.

[5]HowdenWE.Goodenoughversushighassurance

softwaretestingandanalysismethods[C]MThe3rdInternationalHighAssuranceSystemsEngineeringSymposium.Washington:IEEEComputerSociety,1998:166-175.

[6]MillerKW,MorellLJ,NoonanRE,etal.Estima-tingtheprobabilityoffailurewhentestingrevealsnofailures[J].IEEETransactionsonSoftwareEng-ineering,1992,18(1):33-43.

[7]LittlewoodB,DavidW.Someconservativestopping

rulesfortheoperationaltestingofsafetycriticalsoft-ware[J].IEEETransactionsonsoftwareEngineer-ing,1997,23(11):673-683.

[8]LyuMR.Handbookofsoftwarereliabilityengineer-ing[M].NewYork:IEEEComputerSocietyandMcGraw-Hill,1996.

[9]StephenHK.Metricsandmodelsinsoftwarequality

engineering[M].Boston:AddisonWesley,2003.[10]毛澄映,卢炎生.分支测试中测试路径用例的简化

生成方法[J].计算机研究与发展,2006,43(2):321-328.

IEEE1994,

选择分支覆盖准则产生基本用例集,利用文献[6]的简化FTPS算法自动产生符合分支覆盖准则的测试路径集.假设产生的路径均可行,则由此路径集构成基本用例集Cs={c1,c2,c3,c4,c5,

c6}.假设剖面类O7对应的概率P7=0.45,由式(1)计算得各剖面类概率.因此使用模型为U={(c1,0.06),(c2,0.20),(c3,0.20),(c4,0.03),(c5,0.02),(c6,0.04),(O7,0.45)}.假设可靠性测试最初的基本目标是要求在A=0.01的显著水平下检验失效概率是否满足H[0.001,则根据式(3)得Nmin=4603.根据转移概率模拟产生Nmin条路径,即为Nmin个用例(限于篇幅,省略用例集).由测试用例集得测试模型Tc={(c1,247/4603),(c2,883/4603),(c3,905/4603),(c4,127/4603),(c5,131/4603),(c6,147/4603),(O7,2163/4603)}.根据式(4)可计算测试模型与使用模型的差异D(U,Tc)=0.06.若该差异函数值可以接受,则执行测试用例集T.

假设在执行了M=2500个用例,共发生3次失效,一并提交并纠正相应缺陷后,根据式(8)可得下一轮测试需通过N

nextmin

=7541个用例的测

试.由于当前用例集中还有4603-2500=2103个用例,因此至少需要依转移概率产生7541-2103=5438个用例.重新计算差异函数,在认为

第35卷 第9期2007年 9月 华 中 科 技 大 学 学 报(自然科学版)

J.HuazhongUniv.ofSci.&Tech.(NatureScienceEdition)Vol.35No.9 Sep. 2007

软件可靠性测试充分性的多准则判定及应用

刘剑豪 刘晓明 黄 松

(解放军理工大学指挥自动化学院,江苏南京210007)

摘要:在分析软件可靠性测试充分性特点的基础上,提出一种多准则充分性判定方法.依据运行剖面构造系统的使用模型,通过假设检验和贝叶斯推断确定测试用例数量,建立差异函数判断测试模型与使用模型的偏离,根据软件失效情况进行多轮次充分性判定,并使用贝叶斯方法积累测试信息,同时利用测试结果开展软件可靠性的评价与预测.实例分析表明,多准则充分性判定方法对可靠性测试用例集要求更加严格,使得根据该测试用例集的测试结果开展可靠性评价与预测更具可信性.关 键 词:软件可靠性;可靠性测试;测试充分性;多准则判定

中图分类号:TP311.5 文献标识码:A 文章编号:1671-4512(2007)09-0129-04

Multiplecriteriadeterminationofsoftwarereliabilitytesting

adequacyanditsapplication

LiuJianhao LiuXiaoming HuangSong

(InstituteofCommandAutomation,PLAUniversityofScienceandTechnology,Nanjing210007,China)

Abstract:Testingadequacycharacteristicsinsoftwarereliabilityassessmentandpredictionwasana-lyzed.Amultiplecriteriadeterminationmethodisproposed.Usagemodelwasbuiltaccordingtooper-ationalprofile.ThestatisticalhypothesistestingandBayesianmethodwereusedinjudgingtestcasequantity,anddifferencefunctionwasusedtocalculatethedeviationbetweentestingmodelandusagemodel.Whensoftwarefailurewasfoundandcorrected,adequacywasanalyzedinthenextround.TestinginformationwascountedinthepriorBayesianparameters,andwasusedtoreliabilityassess-mentandprediction.Casestudyshowsthattheusedmethodismoreserious,andthereliabilityas-sessmentandpredictionareofmorecreditability.

Keywords:softwarereliability;reliabilitytesting;testingadequacy;multiplecriteriadetermination 如何评价软件的可靠性是计算机学科研究的一个重要方向.可靠性测试数据的选择和测试充分性的判定是进行可靠性评价的基础,其中测试充分性的判定将直接影响可靠性评价的可信性.因此,如何对可靠性测试的充分性进行判定成为开展软件可靠性评价的一个关键问题.本文综合考虑使用模型与测试模型的比较、统计假设检验和贝叶斯推断,给出一种多准则充分性判定的可靠性测试和可靠性度量方法.

1 测试充分性

测试的充分性要解决的问题是测试究竟进

行到什么程度可以停下来?目前采用的标准都是基于软件在有限多个测试用例上的行为特征可以代表软件所有情况下的行为特征的假设建立的.因此评价的可信性和准确性完全依赖于/有限多个测试用例0的选择.对于/选哪些,选多少?0采用不同的策略就形成不同的充分性判定准则.

[1]

收稿日期:2006-07-21.

作者简介:刘剑豪(1978-),男,博士研究生;南京,解放军理工大学指挥自动化学院(210007).E-mail:[email protected]

#130#

华 中 科 技 大 学 学 报(自然科学版)

s

e

j

第35卷

可靠性测试充分性准则主要可以分为4类:a.基于使用模型与测试模型差异比较的充分性准则(简称模型比较准则).b.基于传统统计学的充分性准则(简称统计准则[4,5]).c.基于贝叶斯统计推断的充分性准则(简称贝叶斯准则

[6,7]

[2,3]

Pi=(1-Ps+1)

eIc

j

Fp

i

i=1

EP.

i

(1)

此时的运行剖面可以用基本用例集表示为U={(c1,P1),(c2,P2),,,(cs,Ps),(Os+1,Ps+1)},该剖面代表了软件的使用方式,即为软件使用模型.

2.2 测试充分性的假设检验判定

在首轮可靠性测试时一般不具有先验信息,因此采用统计假设检验方法确定所需的测试用例数.给出系统失效概率H与系统可靠性要求H0之

H0:H[H0;

0,H1:H>H

).d.基于可靠性增长的充分性准则(简称

[8,9]

增长准则).这4类准则各有其优缺点.

2 可靠性测试充分性的多准则判定

仔细考虑可靠性测试的特点,利用各类准则从多个不同的角度建立判断标准,对充分性问题给出更全面更严格的判定,从而提高可靠性评价与预测的准确性和可信性.本文建立的可靠性测

试充分性判定流程如图1所示

.

同时假设系统每次运

行是否失效满足贝努利实验的统计独立性.因此,N个测试用例对应的N次系统运行中失效用例数R服从二项分布

r

P(R=r)=CrNH(1-H)N-r.

(2)

作为最后的性能评价,可靠性测试应该不发生失效.在N个用例执行中无失效时,要求犯第Ⅱ类错误的概率(H0为假时,接受H0的概率)不大于给定的显著水平A(对应的置信度C=1-A),则P{r=0|H}=(1-H)[(1-H0)

由此可得

N\lnA/ln(1-H0),

2.3 测试用例集的产生

图1 充分性判定流程

N

N

[A.

(3)

需要的最小用例数为满足式(3)的最小值Nmin.在马氏链表示的软件系统中,一个测试用例

代表一条从系统初始点到终止点的路径.因此,依马氏链和转移向量P随机产生从初始点到终止点的测试路径即为测试用例.以式(3)判定用例集中用例数量的充分性,产生的Nmin个测试用例和每个用例产生时的顺序共同构成待测用例序列集T={(li,qi)|1[i[Nmin},其中li是第i条路径,qi是路径li出现的序号.

2.4 测试充分性的模型差异判定

由于测试用例对应的测试路径是随机产生的,因此用例集T中可能存在大量重复路径,这种重复代表了测试用例集在各剖面上的测试比例.假设T中有非重复路径Nd条,每条路径出现nj次,则Tc={(li,nj/Nmin)|1[j[Nd}是待测用例集所代表的测试模型.将测试模型Tc中不属于Cs

的路径lj

E

j

j

2.1 使用模型的建立

根据软件系统组成部分的划分,利用马尔可夫链(简称马氏链)建立软件的使用模型,用组成部分间的有向转移图来表示.将马氏链看作传统结构性测试中的控制流,则采用正确性测试充分性准则中的控制流覆盖准则可以产生一组测试路径作为基本用例集,记为Cs={c1,c2,,,cs},共有s个用例.

假设系统中组成部分间的转移概率向量P={pi|1[i[N,0[pi[1},其中系统各组成之间共有Ne条转移边,pei为第i条边的转移概率.根

e

e

e

据基本用例集构造系统运行剖面,表示为U={(O1,P1),(O2,P2),,,(Os,Ps),(Os+1,Ps+1)}.Cs中的每个用例代表一类剖面Oi(i=1,2,,,s),未在Cs中出现的路径为单独的一类剖面Os+1(简称混合剖面类),Pi(i=1,2,,,s)为对应剖面类的发生概率.假设给定剖面Os+1的出现概率为Ps+1,则Pi可以通过马尔可夫有向图中

,合并为一个剖面类nj/Nmin,则测试模型Tc=

c

c

s

c

Ocs+1,Ps+1=

lIT,l|C

c{(c1,Pc1=nc/Nmin),(c2,P2=nc/Nmin),,,12

(cs,Ps=ncs/Nmin),(Os+1,Ps+1)}.

c

第9期

s+1

刘剑豪等:软件可靠性测试充分性的多准则判定及应用

#131#

D(U,Tc)=

i=1

Elog(P/P),

i

ci

(4)

f(H|0,N,a+r,b+M)=Ha+r-1(1-H)b+M+N-r-1/[B(a+r,b+M+N-r)].(7) 要求以C的置信度判定系统失效概率H小于或等于要求值H0,根据该后验分布,新一轮测试所需用例数N应满足P(H[H0)\1-A,即

差异函数D(U,Tc)越接近0,说明测试模型与使

用模型的差异越小,测试模型越能代表使用模型.根据式(4)的定义可知,当待测用例集不包含某个基本用例ci时,D(U,Tc)→].这说明当测试模型未能覆盖使用模型要求的基本剖面类型时,该测试模型严重不符合要求.当差异函数值较大,测试模型不满足要求时,可以考虑重新依转移概率产生待测用例集,但会浪费先前产生的用例.因此,可以在已经产生的待测用例集的基础上,依转移概率矩阵追加测试用例,并重新进行模型差异比较.在差异函数值较小,可以接受用例集T时,依据生成的顺序qi执行T中产生的用例(共Nmin个).

2.5 测试充分性的贝叶斯判定

当执行测试用例中发生失效时,需查找、纠正缺陷,并进行新一轮可靠性测试.采用贝叶斯统计推断的方法将失效概率H看作随机变量,利用该随机变量的后验分布与先验分布的关系来整合已有的测试信息.此时,式(2)表示的是样本x1,x2,,,xN中失效数R在条件为H时的条件分布.根据共轭分布原则,对于满足式(2)的样本条件分布,随机变量H的先验分布应该选择样本条件分布的共轭分布,即选B分布:f(H)=HH)b-1/B(a,b),式中B(a,b)=

a-1

Qf(H|0,N,a+r,b+M)dH\1-A.

H0

无其他先验信息的情况下,取a=b=1,化简得

Qf(H|0,N,1+r,1+M)dH=

H0

1-(8)

i=0

EC

r

i

M+1+N

H0(1-H0)

iM+1+N-i

\1-A.

依马氏链和转移向量产生新的测试用例,补充待测用例集.利用式(8)确定的最小用例数N(记为Nmin)判定用例集中用例数量的充分性,并

在满足模型差异判定后,开始执行新一轮可靠性测试.

2.6 可靠性评价与预测

在经过k轮测试后,前k-1轮共执行了Msum个用例,且发生rsum个失效,第k轮通过了由式(8)确定的N个测试用例(记为Nmin).此时,对软件系统的可靠性评价为:有C=1-A的置信度认为软件系统的失效概率H[H0.该可靠性评价是基于测试的历史信息对系统可靠性现状作出的评价.很多情况下需要对系统将来的可靠性进行预测,由式(7)的后验分布,将来Nf次软件使用中,发生rf次失效的概率

P(RF=rf|0,Nmin,1+rsum,1+Msum)=

end

end

next

(1-

Q

1

a-1b-1

H(1-H)dH0

是B函数,无其他先验信息时取a=b=1.

假设执行了M个用例,且发生r次失效(M[Nmin,1[r[M),显然系统未能连续无失效地通过Nmin个用例的测试,也达不到预期的可靠性要求,因此在纠正发现的缺陷后需要进行新一轮可靠性测试.对r个失效中发现的缺陷进行纠正后,由贝叶斯估计可得H的后验分布

f(H|r,M,a,b)=HH)

b+M-r-1

a+r-1

Q

1

r

f(1-HCNffH)Nf-rf#

r

Nend+M

-r

r

summinsumsum

dH.

B(1+rsum,1+Nmin+Msum-rsum) 由不发生失效的概率大于置信度要求值

end

P(RF=0|0,Nmin,1+rsum,

1+Msum)\1-Ac,

即

(5)

(9)

(1-

/[B(a+r,b+M-r)],

此后验分布与先验分布属同类分布,同时执行用例数M和发生失效数r整合为后验分布的参数.

显然

f(H|r,M,a,b)=f(H|0,0,a+r,b+M)=Ha+r-1(1-H)b+M-r-1/[B(a+r,b+M-r)].(6) 式(6)表明可以将已有测试信息(M,r)积累到先验分布参数(a,b)当中,而式(5)等号右端的形式在式(6)中保持不变.设新一轮要求系统连续无失效通过的测试用例数为N,根据式(6),此时Q

1

r

sum(1-H(1-H)Nf{H)Nmin+Msum-rsum/0

end

end

[B(1+rsum,1+Nmin+Msum-rsum)]}dH=

B(1+rsum,1+Nendmin+Msum-rsum+Nf)/

end[B(1+rsum,1+Nmin+Msum-rsum)]\1-Ac,

可以预测在Cc=1-Ac置信度下,系统最大不发生失效的软件使用次数Nf(记为Nf).

max

3 应用举例

[

#132#

华 中 科 技 大 学 学 报(自然科学版) 第35卷

个开始节点V0和一个结束节点V11.假设软件系统的结构与各组成部分之间的关系与该图一致,并假设边e0~e16的转移概率向量为{1.0,0.3,0.7,0.4,0.5,0.5,1.0,0.6,0.3,0.4,0.6,1.0,0.7,1.0,1.0,0.2,0.8},如图2所示

.

可以接受的情况下进行下一轮测试.假设第二轮测试全部通过,则对系统的可靠性评价为以C=0.99的置信度认为系统失效概率H[0.001.然而由式(9),预测的系统在同样的置信度下,最大不发生失效的使用次数Nmaxf=25.

由结果可知,预测的无失效使用次数25远远低于测试中系统最终通过的无失效用例数7541.这也说明基于/现状0的预测比基于/历史0的评价更加困难,只有系统更加稳定、更有规律才能预测系统较长时间的行为.

参

考

文

献

[1]GoodenoughJB,GerhertSL.Towardatheoryof

testdataselection[J].IEEETransactionsonSoft-wareEngineering,1975,1(2):156-173.

[2]WhittakerJA,ThomasonMG.AMarkovchain

modelforstatisticalsoftwaretesting[J].Transactions

on

Software

Engineering,

20(10):812-824.

[3]RosariaS,RobinsonH.Applyingmodelsinyourtes-tingprocess[J].InformationandSoftwareTechnolo-图2 系统转移概图

gy,2000,42(12):815-824.

[4]HowdenWE.Confidence-basedreliabilityandstatis-ticalcoverageestimation[C]MThe8thInternationalSymposiumonSoftwareReliabilityEngineering(IS-SRE1997).Albuquerque:ComputerSocietyPress,1997:283-291.

[5]HowdenWE.Goodenoughversushighassurance

softwaretestingandanalysismethods[C]MThe3rdInternationalHighAssuranceSystemsEngineeringSymposium.Washington:IEEEComputerSociety,1998:166-175.

[6]MillerKW,MorellLJ,NoonanRE,etal.Estima-tingtheprobabilityoffailurewhentestingrevealsnofailures[J].IEEETransactionsonSoftwareEng-ineering,1992,18(1):33-43.

[7]LittlewoodB,DavidW.Someconservativestopping

rulesfortheoperationaltestingofsafetycriticalsoft-ware[J].IEEETransactionsonsoftwareEngineer-ing,1997,23(11):673-683.

[8]LyuMR.Handbookofsoftwarereliabilityengineer-ing[M].NewYork:IEEEComputerSocietyandMcGraw-Hill,1996.

[9]StephenHK.Metricsandmodelsinsoftwarequality

engineering[M].Boston:AddisonWesley,2003.[10]毛澄映,卢炎生.分支测试中测试路径用例的简化

生成方法[J].计算机研究与发展,2006,43(2):321-328.

IEEE1994,

选择分支覆盖准则产生基本用例集,利用文献[6]的简化FTPS算法自动产生符合分支覆盖准则的测试路径集.假设产生的路径均可行,则由此路径集构成基本用例集Cs={c1,c2,c3,c4,c5,

c6}.假设剖面类O7对应的概率P7=0.45,由式(1)计算得各剖面类概率.因此使用模型为U={(c1,0.06),(c2,0.20),(c3,0.20),(c4,0.03),(c5,0.02),(c6,0.04),(O7,0.45)}.假设可靠性测试最初的基本目标是要求在A=0.01的显著水平下检验失效概率是否满足H[0.001,则根据式(3)得Nmin=4603.根据转移概率模拟产生Nmin条路径,即为Nmin个用例(限于篇幅,省略用例集).由测试用例集得测试模型Tc={(c1,247/4603),(c2,883/4603),(c3,905/4603),(c4,127/4603),(c5,131/4603),(c6,147/4603),(O7,2163/4603)}.根据式(4)可计算测试模型与使用模型的差异D(U,Tc)=0.06.若该差异函数值可以接受,则执行测试用例集T.

假设在执行了M=2500个用例,共发生3次失效,一并提交并纠正相应缺陷后,根据式(8)可得下一轮测试需通过N

nextmin

=7541个用例的测

试.由于当前用例集中还有4603-2500=2103个用例,因此至少需要依转移概率产生7541-2103=5438个用例.重新计算差异函数,在认为