Markov链使用模型的测试用例生成方法研究.pdf

《Markov链使用模型的测试用例生成方法研究.pdf》由会员分享，可在线阅读，更多相关《Markov链使用模型的测试用例生成方法研究.pdf（5页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 第 40 卷 第 5 期 电 子 科 技 大 学 学 报 V ol.40 No.5 2011年9月 Journal of University of Electronic Science and Technology of China Sep.2011 计算机工程与应用 Markov链使用模型的测试用例生成方法研究 雷 航1，陈丽敏2(1.电子科技大学信息与软件工程学院 成都 610054;2.电子科技大学计算机科学与工程学院 成都 610054)【摘要】采用基于马尔科夫链使用模型的软件测试，在状态与激励序列中，从“开始”状态到“结束”状态形成一个完整的测试案例。因此，输入和激励的选择对于产

2、生高效的测试案例十分重要。提出一种激励选择带概率约束的随机选择方法，以软件Markov链模型的状态迁移概率作为激励选择的约束条件，使用遗传算法中用于选择下一代种群的选择算子轮盘赌选择算子对激励进行选择。通过与以往的激励选择方法对比，验证了所提出的方法能提高生成测试用例的有效性。关 键 词 Markov链;轮盘赌算法;测试用例;测试输入;使用模型 中图分类号 TP311.5 文献标识码 A doi:10.3969/j.issn.1001-0548.2011.05.019 Test Case Generation Based on Markov Chain Usage Model LEI Hang

3、1 and CHEN Li-min2(1.School of Information and Software Engineering,University of Eleatronic Science and Technology of China Chengdu 610054;2.School of Computer Science and Engineering,University of Eleatronic Science and Technology of China Chengdu 610054)Abstract In software testing based on Marko

4、v chain usage model,the sequence of state and stimulus from state”Start”to state”Exit”is a complete test case.Therefore,test input,stimulus,is very important to generate effective test case.Focusing on this,a method for selecting stimulus is proposed in the paper,called a random selection algorithm

5、with probability constrained.This method uses the migrating probability between states of Markov chain usage model as constraints,selects stimulus by roulette selection operator,and then gets the next state.Roulette selection operator is used in genetic algorithm to select next generation of species

6、.In this paper,it is used to select stimulus at every state.Compared with the previous selection method,random selection algorithm with probability constrained can improve the effectiveness of test cases.Key words Markov chain;roulette algorithm;test case;test input;usage model 收稿日期：2009 12 23;修回日期：

7、2010 07 16 基金项目：国家自然科学基金(60973016)作者简介：雷 航(1960 )，男，博士，教授，博士生导师，主要从事实时软件工程和软件可靠性等方面的研究.软件测试是软件开发的重要步骤和软件质量保证的重要环节。就其目的而言，软件测试可以分为两类：1)通过测试发现错误，并不断改正错误，以期得到高质量的软件；2)统计学的方法测试软件的可靠性(reliability)。基于模型的软件测试属统计测试的范畴，要求基于软件的使用模型产生测试用例对软件系统进行测试。根据统计测试结果，可以估计被测软件的可靠性1，因此软件统计测试也称为软件可靠性测试。软件的使用模型以一种形式化的方式表现出来，

8、如有限状态机、UML模型和Markov链。模型是对软件使用情况的形式化建模，因此对测试的自动化起着重要作用。基于模型的软件测试，主要是面向测试的自动化。目前，基于模型的软件测试研究主要集中在软件测试模型本身的研究，即如何针对不同类型的软件提取专用模型，又可从专用模型中抽象通用模型。而在测试用例生成方面，由于在以往的测试用例生成中主要采用边界值、等价类划分等分析方法，用于手动生成测试用例，而该类分析生成测试用例的方法不利于测试用例的自动生成。本文针对上述问题，在基于模型的测试用例自动生成方法上进行研究。1 软件使用模型 1.1 概述 软件模型是对软件的行为和结构的一种抽象描述，软件行为的描述方式

9、有系统输入序列、活动、条件、输出逻辑和数据流等。软件结构可以使用组 第5期 雷航，等:Markov链使用模型的测试用例生成方法研究 733 件图、部署图进行描述。针对不同的测试任务，对软件结构和功能进行抽象，并且用易于理解的方式进行描述，所获得的模型即是对被测软件系统精确的建模2，可以用于软件测试。一般根据软件的不同行为，采用不同的模型对软件进行描述，如程序依赖图、数据流图和控制流图表达了程序和代码结构间的行为关系，决策表和状态机则可以描述软件的外部行为。基于模型的软件测试可以根据软件行为模型和结构模型生成测试用例。目前的软件规模庞大，使基于程序的测试十分困难，而基于模型的软件测试方法不仅可以

10、有效地提高测试效率3及测试用例生成的自动化程度，进行测试失效辨识，也有利于评价测试结果。1.2 Markov链使用模型 软件测试中使用的典型模型包括有限状态机、UML模型4和Markov链等模型。Markov链5是一种以统计理论为基础的统计模型，在软件统计测试中得到了广泛的应用。它是一种迁移具有概率特征的有限状态机，可以根据状态间迁移概率自动生成测试用例，还可以分析结果，对软件性能指标和可靠性指标等进行度量6-7。另外，Markov链模型适用于对多种软件进行统计测 试8，并可以通过仿真得到状态和迁移覆盖的平均期望时间，有利于在开发早期对大规模软件系统进行测试费用和时间的规划。本文涉及的Mark

11、ov链均为“有限状态、离散参数、时间齐次”。由Markov链描述的软件使用模型可以用随机迁移矩阵或带迁移概率的状态迁移图表示。一个简单的软件Markov链模型如图1所示，该模型以迁移带概率特征的状态迁移图表示。c,1/4 e,1/2 a,1/4 c,1/2 e,1/4 b,1/2 a,1 f,1/4 b,1/2 (初始)Enter A C B (结束)Exit 图1 Markov使用模型 图1中的节点代表使用状态(状态是指软件在t时刻的运行状态)向弧表示状态之间的转移，每条弧上都有一个激励(输入)与之对应，并指定了对应的概率，表明在当前的状态下输入激励，使软件转移到下一个状态，转移概率之和应为

12、1。每一个使用模型都有唯一的初态和终态。初态是每一次模型使用的开始状态，终态是模型使用的终止状态，是软件每一次使用的终结。软件的每一次使用即每一次操作都从初态开始，经过若干个中间状态，最后到达终态。一条从最初的起始状态到终止状态的路径(历经的状态和弧序列)反映了软件的一次运行。每一状态转移对应一次输入，即一次激励。由于模型中可能有循环，会产生无穷序列。输入序列可以通过遍历状态转移图得到。利用软件的Markov链使用模型可以获得大量的输入序列。一个测试输入就是根据Markov链使用模型从输入域中随机产生的一个有限输入序列。2 基于模型的测试用例生成 在基于模型的软件测试中，测试用例的生成方法取决

13、于所采用的模型。以有限状态机模型为例，被遍历路径中弧的标记构成的序列即是测试用例。在构造满足测试准则的路径时，必须考虑约束条件，如路径长度限制，统计测试时还要考虑迁移概率3。在Markov链表示的软件使用模型中，生成测试用例是在每一状态处不断选择激励，从而选择下一个输出状态的过程。常用的激励选择方式采用完全随机方法选择当前激励。运用该方法，理论上生成的激励均匀分布。假设已得到某软件的Markov链模型，在常用的随机方法的基础上，考虑Markov链的状态迁移概率，在激励随机选择时加入一定的约束，使激励选择更符合软件的实际使用，使测试用例更有效。该算法将遗传算法中用于选择种群的选择算子轮盘赌选择算

14、子用于对激励进行选择，根据使用模型中状态间的转移概率选择激励，从而得到软件的下一 状态。根据Markov链的测试充分性准则9要求，测试过程中测试用例的迁移覆盖率与Markov链使用模型中的迁移概率相同10。轮盘赌选择算子对激励进行的随机性选择符合软件实际使用的随机性，使所选激励出现的概率与软件实际使用中该输入产生的概率一致，本文采用理论方法对此进行了证明。因此，该算法从根本上保证了基于Markov链的测试充分性准则要求。2.1 轮盘赌算法 文献11提出的轮盘赌选择算子，是遗传算法中选择算子的一种。它是基于比例的选择(proportional model)，利用各个个体适应度所占比例的大小决定

15、电 子 科 技 大 学 学 报 第 40 卷 734 其子孙保留的可能性。轮盘赌的整个赌盘被分为大小不同的一些扇面，分别对应着价值各不相同的一些赌博物品。当旋转着的赌盘自然停下时，其指针所指扇面上的物品就归赌博者所有。虽然赌盘的指针具体停在哪个扇面无法预测，但指针指向各个扇面的概率却是可以估计，它与各个扇面的圆心角大小成正比。圆心角越大，停在该扇面的可能性越大；圆心角越小，停在该扇面的可能性越小。与此类似，在遗传算法中，整个种群被各个个体所分割，各个个体的适应度在全部个体的适应度之和中所占比例也大小不一，该比例值瓜分了整个赌盘盘面(盘面设为1)，它们也决定了各个个体被遗传到下一代群体中的概率。

16、若某个个体为i，其适应度为F，种群大小为M，则该选择算子的具体执行过程为：1)先计算个体的相对适应度iiFF，记为Pi；1iP，1,2,iM。2)根据选择概率Pi，将一个圆盘分成M份，其中第i个扇形的中心角为2Pi。3)模拟轮盘操作，即生成一个0,1之间的随机数，若P1+P2+P3+Pi1rP1+P2+P3+Pi，则选择个体i。2.2 测试用例生成算法 步骤1)步骤3)为对轮盘赌算法改进。在根据软件使用模型生成测试用例时：1)对输入状态的下一个相邻状态即输出状态集进行映射。根据每一个输出状态对应的转移概率，将输出状态映射到区间(因为转移概率和为1，则区间选在01)。定义输入状态A和激励p的函数

17、F(A,p)，pP，P(A)为当前输入状态为A时的激励集合。由函数F(A,p)可得输出状态集E(A)。(|)P pA为A状 态时，选择激励p的概率，(|)p PP pA=1。如输入状 态为A，A的输出状态集E(A)=B,C,D，激励集合P(A)=b,c,d，F(A,b)=B，F(A,c)=C，F(A,d)=D,P(b|A)=0.3，P(c|A)=0.5，P(d|A)=0.2；则将区间0.00,1.00分为3个区间，分别为0.00,0.30、0.30,0.80、0.80,1.00。2)产生01随机数序列，选取一种随机数生成方法，如利用计算机产生伪随机数序列。3)统计随机数落在各个子段的频率，频率

18、最高的子段对应的元素被选中，即与子段对应的输出状态被选中。至此，转移的下一个状态被选出，即输出状态被选出。4)在下一输出状态处继续步骤1)步骤3)，直到终止状态停止。测试用例是从起始状态开始到达终止状态的状态和边(或激励)的序列。不断从软件使用模型的初始状态开始，执行以上测试用例的生成过程，直到覆盖从起始状态到终止状态各路径的测试用例数目与状态转移概率相似时，停止测试用例生成。2.3 算法有效性分析 根据伯努利大数定律：设X1,X2,Xn,相互独立都服从(0-1)分布随机变量。PXi=1=p，PXi=0=q(0p1，p+q=1)，则对0，有：11lim1niniPXpn 假设xi表示激励，软件

19、目前状态为A，该状态的激励为一随机变量X，其取值为x1,x2,x33种。激励的概率为Pk=PX=xk,k=1,2,3，以此类推。假设在N次随机数选择事件中，激励xk(k=1,2,3)被选中的次数为ak,ak/N为事件X=xk的频率。按照伯努利大数定理，当N充分大时，ak/N接近于Pk的概率等于1。因此，由模型得到的频率ak/N近似等于所求量Pk，说明频率收敛于概率。按该算法生成随机数序列，选中某一激励。在N次激励选择中，当N趋于某一值时，使该激励被选中的频率与期望概率近似相等，符合Markov链的测试充分性准则要求。3 实验分析 3.1 实验过程 下面通过某软件的Markov链使用模型进行实例

20、研究。以图1为例，该Markov链使用模型由初始Enter、A、B、C、结束Exit共5个状态组成。1)Enter状态仅有一个激励a，其概率为1，状态Enter输出状态集合为A。该激励映射区间为0.00，1.00。产生的0-1随机数序列均落在0.00，1.00区间内，因此其输出状态只能为A。此时的软件输出状态为A。2)对应A状态有b和c两个不同激励，其概率均为0.5。A状态的输出状态集合为B,C，将输出状态映 射 到 0.00,1.00 区 间，具 体 为B 对 应 区 间 为0.00,0.50，C对应区间为0.50,0.10。第5期 雷航，等:Markov链使用模型的测试用例生成方法研究 7

21、35 3)随机生成10个0.00,1.00区间的随机数，分别为0.389 697，0.294 927，0.225 976，0.150 322，0.358 294，0.688 660，0.122 489，0.905 322，0.844 990，0.766 531。4)统计得出落在0.00,0.50区间中的随机数为60%，落在0.50,0.10区间的随机数为40%。区间0.00,0.50被选中的频率最高，所以选择B为输出状态。5)在输出状态B上执行步骤2)和步骤3)。对应B状态有b、c和e共3个不同激励，其概率分别为0.50、0.25、0.25。B状态的输出状态集合为B,C,Exit；将输出状态映

22、射到0.00,1.00区间，具体为B对应区间为0.00,0.50，C对应区间为0.50,0.75，Exit对应区间为0.75,1.00。随机生成10个0.00,1.00区间的随机数，分别为0.061 545，0.974 183，0.217 532，0.072 705，0.358 106，0.953 033，0.662 193，0.856 298，0.439 755，0.104 917。落在0.00,0.50区间中的随机数为60%，落在0.50,0.75区间的随机数为10%，落在0.75,1.00区间的随机数为30%。区间0.00,0.50被选中的频率最高，所以选择B为输出状态。6)在B状态继续

23、执行步骤2)和步骤3)。随机生成10个0.00,1.00区间的随机数，分别为0.668 492，0.483 965，0.092 351，0.996 575，0.273 176，0.409 635，0.890 488，0.638 671，0.736 871，0.884 251。落 在 0.00,0.50 区 间 中 的 随 机 数 为 40%，落 在0.50,0.75区间的随机数为30%，落在落在0.75,1.00之间的随机数为30%。区间0.00,0.50被选中的频率最高，所以仍然选择B为输出状态。7)在B状态继续执行步骤2)和步骤3)。随机生成10个0.00,1.00区间的随机数，分别为0.

24、825 414，0.495 734，0.086 770，0.710 631，0.050 235，0.939 459，0.853 754，0.584 155，0.704 494，0.837 837。落 在 0.00,0.50 区 间 中 的 随 机 数 为 30%，落 在0.50,0.75区间的随机数为30%，落在0.75,1.00区间的随机数为40%。区间0.75,1.00被选中的频率最高，所以选择C为输出状态。8)在C状态执行步骤2)和步骤3)，具体步骤略。最后选择Exit为输出状态。至此，产生了一个完整的测试用例，如表1所示。以上方法仅是示例，在实际生成测试用例过程中，可在0.00,1.0

25、0区间生成更多数目的随机数，根据选中区间选择激励，以便更准确地体现转移概率。表1 测试用例示例 序号 激励 下一状态 1 a A 2 b B 3 b B 4 b B 5 c C 6 e Exit 3.2 结果分析 以 图 1 中 C 状 态 为 例，E(C)=A,Exit；P(C)=a,e,f；F(C,a)=A，F(C,e)=Exit，F(C,f)=Exit；P(a|C)=1/4，P(e|C)=1/2，P(f|C)=1/4。利用完全随机方法和带概率约束的随机方法选择当前激励，激励被选中的频率如表2所示。表2 结果对照 激励 完全随机 带概率约束的随机 a 34/100 24/100 e 34/

26、100 49/100 f 32/100 27/100 采用完全随机方法，激励被选择的概率比为34/100:34/100:32/100=1:1:0.941 2，采用带概率约束的随机算法，激励被选择的概率比为22/100:49/100:29/100=1:2.227 3:1.318 2。与P(a|C):P(e|C):P(f|C)=1/4:1/2:1/4=1:2:1相比，后者更接近软件Markov链使用模型中的转移概率比，由此可知，采用带概率约束的随机算法生成的测试用例更符合软件的实际 使用。4 结 束 语 测试自动化的意义重大，基于模型的测试用例生成为测试自动化打下了基础。本文通过采用轮盘赌选择算子

27、，根据状态转移概率对激励进行选择，使生成的测试用例符合软件的实际使用。测试用例具有针对性，对提高软件可靠性具有重要的意义。参 考 文 献 1 JOHN D M.Software reliability engineeringM.New York:The McGraw-Hill Companies,Inc.,1999.2 李军义.软件测试用例自动生成技术研究D.湖南:湖南大学,2007.LI Jun-yi.Research on techniques for software test case automatic generationD.Hunan:Hunan University,2007.

28、3 AVRITZER A,WEYUKER E J.The automatic generation 电 子 科 技 大 学 学 报 第 40 卷 736 of load test suites and the assessment of the resulting softwareJ.IEEE Transaction on Software Engineering,1995,21(9):705-715.4 颜炯,王戟,陈火旺.基于UML的软件Markov链使用模型构造研究J.软件学报,2005,16(8):1386-1394.YAN Jiong,WANG Ji,CHEN Huo-wang.De

29、riving software markov chain usage model from uml modelsJ.Journal of Software,2005,16(8):1386-1394.5 HU Hai,JIANG Chang-hai,CAI Kai-yuan.Adaptive software testing in the context of an improved controlled Markov chain modelJ.IEEE on Computer Software and Applications,2008,32:853-858.6 STACY J P,CARME

30、N J T,RICHARD C L,et al.净室软件工程:技术与过程M.贲可荣,张志祥,张秀山,等译.北京:电子工业出版社,2001.STACY J P,CARMEN J T,RICHARD C L,et al.Cleanroom software engineering:Process and technologyM.Translated by BI Ke-rong,ZHANG Zhi-xiang,ZHANG Xiu-shan,et al.Beijing:Publishing House of Electronics Industry,2001.7 POORE J H.Introduct

31、ion to the special issue on:model-based statistical testing of software intensive systemsJ.Information and Software Technology,2000,42(12):797-799.8 沙晓婷.统计方法在软件测试中的研究与实现D.北京:北京交通大学,2008.SHA Xiao-ting.Research and implementation on software testing with statistical methodD.Beijing:Beijing Jiaotong Un

32、iversity,2008.9 高海昌,冯博琴,曾明,等.基于Markov链路径使用模型的软件统计测试J.计算机工程,2006,32(19):20-22.GAO Hai-chang,FENG Bo-qin,ZENG Ming,et al.Statistical software test based on Markov chain path usage modelJ.Computer Engineering,2006,32(19):20-22.10 沈海华,卫文丽,陈云霁.覆盖率驱动的随机测试生成技术综述J.计算机辅助设计与图形学学报,2009,21(4):419-431,441.SHEN H

33、ai-hua,WEI Wen-li,CHEN Yun-ji.A survey on coverage directed generation technologyJ.Journal of Computer-aided Design&Computer Graphics,2009,21(4):419-431,441.11 王小平,曹立明.遗传算法理论,应用与软件实现M.西安:西安交通大学出版社,2002.WANG Xiao-ping,CAO Li-ming.Genetic algorithm-theory,application and software implementationM.Xian:

34、Xian Jiaotong Universiy Press,2002.12 马春燕,胡飞,张云鹏.基于Markov链使用模型的组件复用的统计测试J.计算机应用研究,2008,25(4):1051-1053,1056 MA Chun-yan,HU Fei,ZHANG Yun-peng.Statistical testing of component reuse using Markov chain usage modelJ.Application Research of Computers,2008,25(4):1051-1053,1056 编 辑 黄 莘-(上接第705页)2 RAO Yun-

35、jiang.In-fibre Bragg grating sensorsJ.Meas Sci Technol,1997,8:355-375.3 RAO Yun-jiang.Recent progress in application of in-fiber Bragg grating sensorsJ.Opt&Laser in Eng,1999,31:290-297.4 鲍吉龙,章献民,陈抗生,等.FBG传感网络技术研究J.光通信技术,2001,25(2):84-89.BAO Ji-long,ZHANG Xian-min,CHEN Kang-sheng,et al.The research o

36、f FBG sensing network technologyJ.Optical Communication Technology,2001,25(2):84-89.5 饶云江,王义平,朱涛.光纤光栅原理及应用M.北京:科学出版社,2006.RAO Yun-jiang,WANG Yi-ping,ZHU Tao.The principle and application of fiber grantingM.Beijing:Science Press,2006.6 PENG P C,TSENG H Y,CHI S.Long-distance FBG sensor using a linear-

37、cavity fiber Raman laser schemeJ.IEEE Photon Technol Lett,2004,16:575-580.7 PENG P C,FENG K M,PENG W R,et al.Long-distance fiber grating sensor system using a fiber ring laser with EDWA and SOAJ.Opt Commun,2005,252:127-131.8 LEE J H,HAN Y G,CHANG Y M,et al.Raman amplifier based long-distance,remote

38、FBG strain sensor with EDF broadband source recycling residual Raman pumpJ.Electron Lett,2004,40(18):1106-1107.9 RAO Yun-jiang,RAN Zeng-ling,CHEN R R.A long-distance FBG sensor system with high optical SNR based on a tunable fiber ring laser configurationJ.Opt Lett,2006,31(18):2684-2686.10 饶云江,罗小东,冉

39、曾令.基于扫描激光器和光放大的100 km光纤布拉格光栅传感系统J.中国激光,2007,34(5):680-683.RAO Yun-jiang,LUO Xiao-dong,RAN Zeng-ling.100 km FBG sensing system based on scan laser and optical amplificationJ.Chinese Journal of Lasers,2007,34(5):680-683.11 TAKANORI S,KENICHI N,YOSHIFUMI T,et al.Ultra-long-distance(230 km)FBG sensor systemC/Proc of 19th Internationl Conference on Optical Fibre Sensors.Perth,Western Australia:David Sampson,2008,7004:70046C-70046C4.12 吴健,严高师.光学原理教程M.北京:国防工业出版社,2007.WU Jian,YAN Gao-shi.Optical principle tutorialM.Beijing:National Defence Industry Press,2007.编 辑 张 俊