统计测试中操作剖面的一种优化设计方法.docx

1、第38卷第2期2008年3月Vol.38No.2Mar.2008东*大学学报(自然科学版)JOURNALOFSOUTHEASTUNIVERSITY(NaturalScienceEdition)统计测试中操作剖面的一种优化设计方法万晓民'张德平E聂长海'徐宝文'('东南大学计算机科学与工程学院.南京210096)3南京航空航天大学理学院.南京210016)摘要：为了提高软件统计测试的效率，使用较少的测试资源达到测试目的，对测试剖面进行优化成为必需.采用客户需求和测试需求作为约束，模型静态参数或其他统计质黄标准作为优化目标，提出了一种基于约束优化的测试剖面最优化计算

2、框架.通过扩展蚁群算法研究了一种求解优化测试剖面的方法.实验表明，相对于传统的函数最优化方法，使用启发式的蚁群算法具有更好的优化效果，并且更具通用性.在统计测试中使用经过优化的测试剖面可以生成统计意义上符合测试需要的用例集合，提高测试效率.关键词：软件测试；统计软件测试;操作剖面；测试剖面中图分类号：TP3II文献标识码：A文章编号：1001-0505(2008)02-0233-06OptimizingdesignmethodofoperationalprofileinstatisticaltestingWanXiaomin1ZhangDeping1,2NieChanghai1XuBaowen

3、1(*SchoolofComputerScienceandEngineering,SoutheastUniversity.Nanjing210096.China)(2CollegeofScience,NanjingUniversityofAeronauticsandAstronautics,Nanjing210016,China)Abstract:Inordertosufficientlyexploretheadvanceofstatisticaltestingandquicklyachievethetestinggoal,itisnecessarytooptimizethetestingpr

4、ofile.Customrequirementsandtestingrequirementsareusedasconstrains,andstatisticalstaticparametersofusagemodelorotherstatisticalqualitycriteriaareusedastheoptimizingaims.Thenanoptimizingframeworkoftestingprofileissetup.Byextendingtheantcolonyarithmetic,amethodbaseonconstrainoptimizingtocalculatethetes

5、tingprofileisdeveloped.Theexperimentresultsshowthatusingheuristicantcolonyarithmeticcanachievebetteroptimizingeffectthanconventionalfunctionalconstrainedoptimizationarithmetic,anditismoreuniversal.Usingoptimizedtestingprofileinsoftwarestatisticaltestingcangeneratebettertestcasesettosatisfytestrequir

6、ementonstatisticalmeaningtoimprovetestingefficiency.Keywords:softwaretesting；statisticalsoftwaretesting；operationalprofile；testingprofile软件测试是保证软件质量的最基本的手段之一.软件测试可分为静态测试和动态测试.动态测试包括:选取用例、执行测试、测试评估3个步骤.统计测试将上述测试流程视为统计抽样过程.统计测试在待测软件的全部可能操作中选取若干个操作作为测试用例集，这可视为对软件行为整体的抽样.统计测试使用特定的概率分布选择测试用例，然后执行测试用例得到以可

7、靠性为代表的质量信息.执行测试的目的是获取抽样质最，并由此推断软件自身的真实质量.这个步骤中需要根据采用的抽样方法以及选取的测试用例建立抽样和整体之间的质量关系，进而对软件的整体质量做出恰当的统计评价.广义上来讲，大部分软件测试都可以视为统计抽样过程.统计测试的特点在于将统计抽样和可靠性验证的过程显式引入到软件测试中，并且建立一套以统计抽样为核心的测试过程，最化测收稿日期：2007-09-21.作者简介：万晓民(I98I-),男，硕匕生;徐宝文(联系人)，男，博上.教授，博土生导师，bwxu.基金项目：国家杰出青年科学基金资助项目(60425206).国家门然科学基金资助项目(60373066

8、,60403016).?!苏省自然科学基金资助项n(BK2OO5O6O).引文格式：万晓民，张德平，聂K海，等.统计测试中操作剖面的一种优化设汁方法1J1.东南大学学报：自然科学版.2008.38(2):233-238.第38卷试中的各种决策.统计测试中使用测试剖面作为统计抽样的指导，测试剖面的优劣对统计测试的效率起着决定性作用.为了提高测试效率，使用较少的测试用例达到测试目的,需要对统计测试剖面进行优化.本文提出了统计测试剖面的优化框架并旦使用定量方法计算符合特定测试H的的最优测试剖面.1软件统计测试统计测试方法最初在软件可靠性工程以及净室软件开发中用于验证系统的可靠性.软件统计测试采用使用

9、模型(usagemodel)来表示用户的使用特征(见图1).使用模型包括2个子模型，即状态子模型和用户概率子模型.状态子模型是对系统使用中状态的抽象表述，根据软件系统的输入和输出以及软件系统的功能和用户使用情况进行构建，一般描述为系统功能的有限状态机.用户概率子模型是对用户使用系统操作的概率描述，可以表示为转移矩阵或激励矩阵等形式.图1使用模型图形表示1.1使用模型使用模型从用户角度或系统角度描述系统的状态和行为.Prowell等提出了从软件规范说明构造统计测试的马尔nJ夫使用模型的方法.Walton等则给出了使用迭代方法建立使用模型的步骤.近年来，由于系统建模方法的发展，特别是UML建模方法

10、的广泛应用和标准化，从已有的模型或是先前的开发经验中自动或半自动的生成使用模型成为了重要的发展趋势.文献5给出了从UML序列图和用例图构造马尔可夫使用模型的方法.统计测试平台Matelo也支持从UML模型生成使用模型的转化.1.2操作剖面和测试剖面将用户在真实环境中的使用情景称为操作剖面.使用模型是表示操作剖面的一种方法.可以直接将操作剖面作为生成测试用例的指导，此时生成的测试用例集合代表了真实使用中的情况，可以用于可靠性估计.然而完全使用操作剖面进行测试也存在一些问题.典型的问题如部分使用率低的测试用例可能难以测试到，另外一些使用频率高而出错概率低的测试用例可能会过度测试，造成测试资源的浪费

11、.因此在测试计划中可以对操作剖面进行调整和优化，生成测试剖面来指导测试用例的生成.这样得到的测试剖面不仅反映了用户的使用习惯，也能体现测试的需求.2操作剖面相关研究统计测试的一个难点是如何准确地获取真实的操作剖面.通过系统分析或UML用例图可以很容易获取用户的操作.但是量化用户会有多大概率使用这些操作是非常困难的.目前获得用户操作剖面仍然主要依靠用户、开发者以及领域专家三方的估计和建议.在一些特殊的领域中，可以比较方便地获得用户操作的信息，如Kallepalli等从Web日志中提取出Web使用和失效信息，给出了基于Web的使用模型的构建方法.但是对于此类系统，仍需要对得到的状态和操作臆证其历史

12、无关性.在实际的测试中，不仅需要考虑用户的操作习惯，也要考虑到测试和管理需求对于操作剖面的需求.用户使用信息的缺失导致往往只能得到转移概率的范围和约束关系，而很难计算精确的值.这使得根据其他需求对操作剖面进行优化成为可能.Poore等提出了一个从约束中计算优化操作剖面的约束框架'I.本文在此基础上研究了以测试需求最优化为目标的操作剖面优化的框架的方法.通过测试剖面生成的测试用例不能直接用于估计软件的可靠性,Gutjahr提出了一种重要性抽样的可靠性估计方法，如果能够得到使用模型中边失效概率的先段信息，就可以使用测试剖面生成的测试用例来估计M靠性.3操作剖面优化框架传统的最优化间题可以使

13、用以下方法描述叫max/(x)xeR(r,s.t.G(x)=0i=1,m'G(x)N0i=+1，”在最优化问题中,x的取值范围称为可行域其中的解称为可行解.如果=maV(x)并且”。称为全局最优解.求解最优化问题的目标就是在约束条件下求解目标函数/<x)的全局最优解.要进行测试剖面的优化，首先需要在统计测试中找到对应于上述问题的约束和目标函数.3.1使用约束计算转移概率目前的操作剖面获取方法以直接给定转移概率的数值和评估概率等级的方法为主.然而，通过评估方法要给出精确的转移概率数值是非常困难的.在更加复杂的模型中，需要对大量来自用户和系统的需求进行综合考虑.此时要单独地给出某条边

14、的转移概率更是困难.为此,Poore等提出一个从约束中计算操作剖面的约束框架.使用测试中的约束关系主要可以分为3类：基本约束、用户约束和策略性约束无论是基本约束还是用户约束都nJ以通过约束的形式表示出来，正常情况下一般为线性约束，即=1，=1,2,*（1）Pix=2%（2）策略性约束源于模型性能、软件测试策略或开发管理中的特殊要求.3.2使用静态参数作为优化目标统计使用测试中的静态参数是估计测试统计性能的定量方法，可以用于计算众多测试中的性能相关问题，如单个测试用例测试到每条边/每个状态的概率，为了测试到某个状态/某条边所需要的测试用例数量.操作剖面优化过程是针对测试需求优化的过程，如果能够把

15、测试需求转换为静态参数的形式，使用静态参数作为优化目标是很自然的.静态分析过程是根据给定的操作剖面，计算或估计测试的统计性能.这里关心的是相反的问题，即如何修改或生成转移概率.保证得到的静态参数可以达到一定的性能或某种极值.在-般的最优化问题中，计算目标.函数的复杂度一般不高.然而如果使用静态统计参数作为目标函数，由于计算过程中用到了计算逆矩阵等高复杂的求解方法.逆矩阵的计算代价随着测试剖面的维数增K而快速增长.对待这个问题,一方面要避免把算法用于过于庞大的测试剖面，可以逋过恢套子模型的方法降低使用模型的规模;其次，对于目标函数的求解是无法避免的，在本文方法中要尽域使得目标函数的计算次数控制在

16、可以接受的范围内，如使用存储结构保存搜索的中间结论，并旦使用某种算法使得目标函数的搜索结果可以复用.3.3使用启发式算法使用传统的函数最优化在求解目标函数或可行域凸性不可知,并且存在多个极值点的情况下很容易陷入局部最优，难以满足需要.随机方法更适合于求解病态结构的问题.在随机搜索的基础上,发展出一些启发式的随机搜索方法，通过先验信息使得随机搜索可以更快收敛到最优值.本文使用一种改进的启发式蚁群算法来完成求解上面的最优化问题.4操作剖面优化方法4.1使用连续蚁群算法传统的蚁群算法是离散空间的搜索算法，必须修改传统的蚊群算法使其适用于连续空间.在测试剖面最优化问题的约束关系中大量存在线性约束.线性

17、约束在多维空间中表示为向量的形式.使用向量来模拟传统蚁群算法中的边和路径，在此基础上设计并实现了适用于测试剖面优化的最优搜索方法.4.1.1使用向量替代搜索边nJ行域中的每个点对应一个目标函数的解，称蚂蚁在搜索中停留的点为基点.从基点开始引出若干向量，蚂蚁沿着其中的某个向量进行搜索（见图2）.向量表示为|V|,v2,-",vJ,k为变量空间的维数.向量表示了搜索进行的方向，向量与所在的基点决定了多维空间中的一条直线.在一般的蚂蚁算法中，蚂蚁沿着边进行搜索.在每一个基点都有若干条边供蚂蚁选择.在连续空间中不存在这样的“边”，因此使用向量来创造“边”，使得蚂蚁可以沿着向量进行搜索，最终汇

18、聚到最优F1标.图2使用向量进行搜索4.1.2定义搜索半径搜索向量定义了搜索的方向，然而没有定义搜索的范围.使用搜索半径来描述搜索范围.假设在基点（Pl，P2,，Pk），蚂蚁选择搜索向量据|也，,，搜索半径用A表示，向虽局部的搜索点定义为一个点列（的，口2,，皿），其中的第i个点U,表示为Ui=（P|，P2,，Pa）+人Vk）0W人，W人（3）定义搜索半径来限制搜索范围使得在算法中容易表示线形测试约束.确定了基点和向量，如果给出搜索长度，通过式(3)惟一确定了多维空间中一个搜索点.测试剖面最优化问题中存在的等式约束可以在搜索前消去，而不等式约束通过代入式(3)可以表示成只含有变量A的形式，通过

19、求解A可以得到当前局部搜索中可行解的半径范围.4.1.3定义信息素算法通过信息素将搜索得到的信息留到下一代.信息素的调整包括2个部分，如果下一个基点具有比当前基点更优的解时需要增加到达下一个基点的向最的信息素浓度.另外，蚂蚁经过路径上的信息素浓度需要根据蚂蚁找到的最优解的大小进行调整.使用以下的公式表示一代蚂蚁完成移动后信息素的更新：r(/+1)=ar(t)S(r(t+1)=>1(4)式中,S(,(£)为蚂蚁经过路径上所有向量的信息素组成的数组为信息素更新参数，其中町表示使用最优解来调整信息素.当蚂蚁离开起点后，根据可以选择方向的信息素计算选择概率，然后随机选择移动方向.信息素

20、浓度高的方向比信息素浓度低的方向表示更高的搜索成功概率，需要提供更高的关心度.在蚁群算法中通过给与信息素浓度高的方向更多的选择概率使其得到更多的搜索.4.1.4半径缩减策略搜索算法使用搜索半径来控制搜索的范围.一开始使用比较大的搜索半径可以尽快获得搜索空间解的分布.然后减小搜索半径，增加搜索的精度，在局部获得更好的最优解最后在搜索半径小于一个固定值时停止搜索过程.搜索半径随着搜索过程的进行是一个逐步减小的过程.半径搜索策略表示为某种非增函数，如算法中使用以下函数表示半径缩减策略：fix)=航刀)a<1(5)4.1.5蚂蚁移动策略初始化时所有的蚂蚁放置在可行域的一个基点上.在到达新的基点后

21、，蚂蚁继续搜索周围的环境,然后选择一个方向进行转移，如果该基点是新的还没有其他蚂蚁到达过，则对任何方向的选择都是等概率的，等于一个初始值表示向虽的数量.蚂蚁根据选择概率选择一个方向进行转移,不同的是这次的搜索半径比前一次缩短了.蚂蚁移动、搜索，直到搜索半径降低到某个值时停止搜索.在这个过程中得到的最优值作为蚂蚁此次搜索的最优值.4.1.6算法停止策略在蚊群算法中另一个必须要考虑的是何时停止搜索.在算法中涉及到大敏的环境参数和策略，因此也有很多不同的停止方法.包括:大部分蚂蚁发现的最优点收敛到一点；到达最大的蚂蚁代数;连续若干代蚂蚁没有发现新的最优解.下面给出使用连续蚁群优化测试剖面的步骤：1)

22、 选择蚁群的起点，初始化搜索参数和存储结构.2) 使用第g代蚂蚁从起点开始全局搜索.3) 使用小只蚂蚁独立进行方向的选择，搜索局部最优位置并且移动到新的基点，减小搜索半径，直到搜索半径缩减到最小停止搜索，其中使用到下列算法:方向选择策略;向量局部搜索策略;蚂蚊移动策略;半径缩减策略.4) 第g代的蚂蚁搜索结束，计算每只蚂蚁找到的最优解和全局最优解，更新路径上的信息素浓度.5) 判断算法是否停止，若达到收敛条件，停止搜索;否则返回步骤3)产生下一代蚂蚁继续搜索.4.2实验启发式算法的性能依赖于解空间的结构，特别是在连续性空间中，解空间的结构对算法的收敛速度和最优解有重要的影响.算法假设目标函数具

23、有某种程度上的连续性.因此在全局搜索阶段可以发现较优解的地区，然后通过在该区域逐步增加搜索精度来获得更好的解算法的性能需要通过实验来证明,通过使用蚁群算法解决Poore给出的一个优化测试剖面的实例来验证本文的优化算法.首先给出Poore实验中的使用模型图3,这个使用模型描述了一个通用的窗口系统操作的使用模型.通过系统分析方法，给出未完成的操作剖面(见图4).在模型中使用凡表示的转移概率是在系统分析中没有确定的概率.这些转移概率需要满足下列等式表示的基本约束和用户约束：万晓民，等：统计测试中操作剖面的一种优化设计方法237图3窗口操作的使用模型12345678910111213141510100

24、00000000000200七X)00刀3工400000为0301000000000000040000100000000005000001000000000600000000000000070000000010000008000000001000000900000000Xi刀8%*10001000000000000000II00000000100000012000000001000000130000000010000001400000000000000115100000000000000未完成的操作剖面结论.表1给出了使用每代100只蚂蚁，10代蚂蚁的搜索结果.表1使用10代蚂蚊群搜索到的最大

25、状态墉图4gl3）=X,+x2+%3+%4+x5-1=0g2（X）=X6+X7+Xg+x9+x10-1=0g3（x）=x5-3x4=0g4（x）=*6-4%7=0g5（«）=Xg-23=0g6（x）=-«2=0进行优化搜索前，首先要消除所有的等式约束.通过消除变量3，与/5，&/8/，。），可以得到把原来10个变做的搜索空间降低到变量（知，%7，与0）的四维搜索空间.同时，把等式代入基本约束的不等式中，可以得到四维空间的可行域.在计算模型状态炳时需要计算状态的占有率,此时得到的目标函数需要计算逆矩阵，传统的最优化方法没有办法求解这样的问题.因此一般选用各个状态烯的平

26、均值作为模型状态墉的近似值.使用牛顿方法给出r问题的解.蚁群算法没有这样的限制，在下面的实验中分别以状态嫡的平均值和模型的状态炳为目标函数，给出2种情况下的优化吗蚊代数最大状态烧BP(*2,%4，*7，*10)11.0092(0.2331.0.0915,0.0541,0.1730)21.0123(0.2419,0.0878,0.0471,0.1966)31.0131(0.2438,0.0860,0.0502,0.1937)41.0129(0.2499,0.0840,0.0491,0.1850)51.0126(0.2450,0.0852,0.0508,0.1841)61.0119(0.2412,

27、0.0863,0.0515,0.1834)71.0126(0.2438,0.0848,0.0500,0.1887)81.0124(0.2484,0.0856,0.0563,0.1868)91.0131(0.2520,0.0833,0.0507,0.1826)10L0131(0.2409.0.0876,0.0491,0.2074)Poore通过近似估计得到的模型状态嫡最大值为0.9058.在实验中通过随机搜索找到了更好的解1.0131.证明了连续蚊群搜索算法在优化测试剖面问题上具有比传统方法更好的计算能力.可以计算出表1中的得到最优悄况下的确定转移概率（如七，S豹。），进而得到完整的测试剖面，即

28、X）=0.2409,x2=0.2409,x3=0.1678x4=0.0876,x5=0.2628,x6=0.1964x7=0.0491,x8=0.3356,x9=0.2115xl0=0.20745结语在统计使用测试基础上,研究了测试剖面的优化框架和基于连续蚁群算法的优化方法.作为对传统测试剖面设计方法的补充和优化，测试剖面优化增强了对统计测试过程的控制能力.以往的统计静态分析只能在测试后观察测试质量，测试剖面优化则把对测试质量的干预提早到测试前，从而提高测试效率.本文通过扩展蚁群算法设计了新的测试剖面优化算法.对比传统的函数最优化方法,使用启发式的蚁群算法更具有通用性，使用同样的算法可以针对不

29、同的目标函数计算优化测试剖面来满足不同的测试需求.将优化方法用于改进统计测试效率仍存在多方面的问题，将在以下儿方面开展进一步的工作：使用测试剖面优化中目标函数的研究.本文使用测试剖面优化使用静态参数作为目标函数.然而静态参数无法表示所有的测试需求，仍需要进一步研究如何把不同的测试需求转化为可以计算或估计的目标函数.对启发式优化算法的进一步研究.随着解空间维数的tl升，使用基于向量的蚁群算法的可能方向会快速增加，而降低算法的性能.这方面的改进依赖于蚁群算法的进一步研究或者使用其他的启发式方法来帮助搜索最优解测试剖面优化算法和统计测试工具的整合.测试剖面优化算法改进了传统的统计测试过程，如果把这种

30、改进和已有的统计测试工具家进行整合以提高测试的效率需要进一步的研究.参考文献(References)(1ProwellSJ,TrammellCJ,LingerRC,etal.Cleanroomsoftwareengineering:technologyandprocessM.NewYork：McGrawHill,1998.2 MusaJD.Operationalprofilesinsoftware-reliabilityengineeringJ.IEEESoftware,1993,10(2)：14-32.3 ProwellSJ,PooreJH.Computingsystemreliabilityu-singMarkovchainusagemodels