软件结构化测试用例自动生成方法

软件结构化测试用例自动生成方法樊玮;朱贺【摘要】软件测试和软件开发对软件质量具有同等重要的意义，其工作量很大，且其许多过程又适于自动化，于是软件测试自动化应运而生.测试用例的生成是软件测试过程的重要环节,近年来，人们开始尝试将人工智能技术运用于测试用例生成问题中,产生进化测试思想方法.文中对基于结构化的测试用例自动生成方法研究现状作了介绍，重点介绍了进化测试并对其基于不同进化计算算法的应用情况进行了比较和总结.应用结果表明进化测试方法是当前最为高效的软件测试用例自动生成方法最后对进化测试进一步的研究方向提出了看法.【期刊名称】《计算机技术与发展》【年(卷)，期】2010(020)005【总页数】4页(P26-28,33)【关键词】软件测试;进化测试;测试用例生成;进化算法【作者】樊玮;朱贺【作者单位】中国民航大学，计算机科学与技术学院，天津,300300;中国民航大学，计算机科学与技术学院，天津,300300【正文语种】中文【中图分类】TP311.56软件测试是保证软件可靠性的主要手段，其目的是发现软件错误、提高软件质量。通常，软件测试的工作量很大，且许多操作是重复性的、非智力性的和非创造性的，并要求精确，计算机适合代替人工去完成这样的任务。测试用例生成是软件测试过程的重要环节彳艮长时间，测试人员根据经验采用手工方法设计测试用例，测试用例的自动生成将有效地减轻测试人员的劳动强度，降低软件开发成本。根据估算［1］,对于一个典型的大型软件项目若能自动生成测试用例，大约能节省整个软件开发费用的4%。文中首先介绍结构化测试的一般方法;然后详细介绍结构化测试的最新方法——进化测试;之后，将介绍几种用于进化测试的进化算法;最后对结构化测试用例自动生成方法进行总结。1结构化测试方法基于程序结构的测试用例自动生成方法包括随机法、符号执行法和基于程序执行的方法。1.1随机法D.Bird［2］等采用随机法自动生成测试用例，随机法是最简单的动态生成测试数据的方法，在实际运用中甚至可以产生几乎任何一种类型的测试数据。因为任何数据类型在计算机中的表示归根到底都是一组二进制串，它的基本思想是对输入数据域进行随机取样，可以用于黑盒测试启前很多测试工具用的就是这种随机法。1.2符号执行法C.Ramanmoorthy［3］、Clarke［4］和P.D.Coward［5］及王言志等人［6］提出的都是符号执行法。该方法的主要思想是使用符号值，如变量的名称，而不是实际的数据来代表程序输入，并在执行过程中产生关于输入符号的代数表达式。它建立约束系统的方式主要有两种：从前向后替换和从后向前替换［3］。但是随着程序规模的增大，符号表达式变得很长，求解一般比较困难。1.3Korel法与前面的静态方法对应的是动态法。所谓动态法是要从变量的最小定义域中选取一组值作为程序的输入，然后运行程序并根据运行情况修改输入的值。Korel［7］所提出的方法就是动态法的一种：从输入域D中任选一组数据，按步进的方式运行程序p,即一次前进一个分支谓词。若当前分支谓词的值不符合要求，就建立一个分支函数，然后用函数最小化方法调整输入变量值,使得在仍能经过已成功经过的子路径的前提下,适应值f为负数（或0）。该方法先用探测性搜索确定前进方向,再用模式性搜索使分支函数值尽快达到最小值，并采用动态数据流分析技术确定影响分支谓词的变量减小搜索的盲目性。1.4进化测试方法近年来，人们开始尝试将人工智能技术运用于软件测试。首先选择输入数据并执行程序，然后根据执行结果〃进化”出新的输入数据继续试探，直至找到正确的解。其优点是不受搜索空间限制性条件的约束并且不需要其它辅助性信息（如导数）,所以对于一些传统方法难于处理的大空间、全局优化等复杂度较高的问题，该方法具有独特的优势和高效性。具有全局寻优能力而又有较高鲁棒性的进化算法应用在这个空间中进行测试用例的搜索成为最佳选择,即进化测试。2进化测试进化测试即利用现代启发式组合优化技术来产生软件测试用例的方法，基于进化测试思想的优化方法已成功应用于大规模集成电路测试（Cornoetal.1996）。进化测试系统遵从一种动态测试用例产生策略。系统存在一个适值函数，每一步选择一个实体作为实际的测试目标,执行测试用例，若该测试用例完成该目标，适值函数取最小值,否则根据被测代码的执行信息按比例赋予适值函数一个近似值。然后，搜索算法通过当前一组测试用例的适值函数值来产生下一组测试用例。进化测试用例产生模式［8］如图1所示，每一次循环都包含两个连续的过程：选择和优化。图1进化测试模式尽管存在多种不同的选择策略，但其共同的方式都是通过能够反映被测代码结构性质的图形来决定目标实体，即控制流图。在控制流图中,程序分支可以由每一个出度为1的结点向量来定义。按图1所示模式，接下来要解决的是一个优化问题，具体来说就是给定一个由程序输入空间所限定的一个搜索空间Q和一个适值函数h:Q->IR,搜索x*eQ使h(x*)<h(x)对xeQ。当输入到达目标实体时，函数h为最小值。下面介绍进化测试模式的两个核心过程。优化过程。这个过程主要来解决前面所提到的优化问题。一个0-1串代表一个输入，它的适应值由函数h计算。计算适应值h所需的一些信息通过被测代码实际执行来获取。每个分支绑定一个输入集，用于存储那些对该分支取得较好适应值的输入。在优化过程中，尽管每次都有一个系统目标，但同时考虑当前输入对每一个未被覆盖的分支的适用性，若该分支被覆盖到了则该分支确定为已覆盖，否则该输入的适应值好于该分支参考集中的最差个体，则用该输入替换那个最差的个体。选择过程。候选分支是那些未被覆盖到的分支。目标分支是其参考集中个体的平均适应值最差的分支。当出现均值相等时，则通过深度优先策略来决定选取哪个分支为目标。3用于测试用例生成的进化算法本质上进化算法是不依赖具体问题的直接搜索方法，算法和进化测试系统框架通过种群和适值函数联结起来［9］。下面将简要介绍进化测试的几种进化算法。3.1遗传算法遗传算法进行进化测试［10~13］的实践中，常常遇到数据收敛过慢的问题，直接导致测试数据生成速度不高乃至最终无法生成。因为交叉点位置为随机选择，因此常常会选择不当，导致交叉后生成新的数据的适应度值反而有所下降。3.2模拟退火算法模拟退火算法在测试用例生成问题上［14~17］,其一般是作为遗传算法的一个协作算法来使用。引入模拟退火算法当中的Metropolis准则，并且根据实际情况对个体邻域的构造加以改进，采用新方法构造个体的邻域。这样可以在一定程度上保持物种的多样性，使得算法不至于陷入局部最优化解当中，并且可以提高算法整体收敛速度。3.3蚁群算法蚁群算法生成软件测试用例是在知识表示的基础上,应用蚁群算法完成知识推理，其关键是设计表示用例的蚂蚁路径。在测试用例生成问题上［18~21］由于搜索初期信息素相对匮乏,导致算法的搜索效率降低,正反馈机制容易产生停滞早熟现象。为了克服蚁群算法的不足，多数作法往往引入遗传算子，利用其变异操作,增加搜索的随机性、快速性和全局收敛性。3.4禁忌搜索禁忌搜索思想最早由Lover(1986)提出，它是对局部邻域搜索的一种扩展，是一种全局逐步寻优算法，是对人类智力过程的一种模拟。在测试用例生成问题上［22-24］,其通过设置近期操作的禁忌表，以当前解邻域中未在禁忌表中出现或满足藐视规则的最佳状态来替换当前状态，而并不在乎其性能是否优于当前解,按此原则产生一定的突跳性以避免局部极小，同时也避免迂回搜索的出现。3.5免疫算法免疫算法是模拟生物免疫系统智能行为的仿生算法。在进化测试过程中［25］,免疫系统利用多样性产生和维持机制，来保持解群体的多样性,从而克服一般寻优过程尤其是多峰值函数中最难应付的〃早熟”问题，最终求得全局最优解。而且可以引入疫苗接种机制，即利用先验知识来引导寻优过程，进一步提高算法的快速性和有效性。3.6粒子群算法粒子群算法源于鸟群捕食行为的研究。在测试用例生成问题上[26,27],其优势是算法收敛速度快，但由于其易于陷入局部最优且搜索精度不高，所以通常要与其它优化算法协作来发挥其优势,弥补其不足。3.7分布估计算法分布估计算法提出了一种全新的进化模式[28],它由遗传算法演化而来，没有了传统的交叉、变异等操作，取而代之的是概率模型的学习和采样。在进化测试[8,29]中，其通过一个概率模型描述候选解空间的分布，采用统计学习手段从上一代种群选择优秀个体来更新解分布的概率模型，然后利用概率模型随机采样产生新的种群，上一代的优秀个体的特性能很好地体现到下一代中，故其收敛速度较快。4结束语软件测试用例生成经历了从测试人员根据经验采用手工设计方法到借助计算机自动生成,自动生成方法又经历了从静态方法到动态方法，从人工智能技术的引入又产生了进化测试方法，每一次发展都使测试用例生成效率得到了极大的提高。人们的应用结果表明进化测试方法是当前最为高效的软件测试用例自动生成方法。通过进化测试模式可见，测试用例自动生成问题也是一个多目标优化问题，且程序中的条件可能是多个参数的复合表达式,故进化算法中所产生的用例个体可能是多变量相关的。诚然,将更多的适于求解多目标优化和多变量相关的算法引入进化测试中是值得尝试和研究的。参考文献：黄锡滋.软件可靠性、安全性与质量保证[M].北京：电子工业出版社,2004:1516.BirdD,MunozC.Automaticgenerationofrandomselfcheckingtestcases[J].IBMSystem,1983,22(3):229-245.RamamoorthyCV,HoSBF,ChenWT.Ontheautomatedgenerationofprogramtestdata[J].IEEETransonSoftwareEngineering,1976,SE-2(4):293-300.ClarkeLA.ASystemtoGenerateTestDataSymbolicallyandExecutePrograms[J].IEEETransactionSoftwareEngineering,1976,2(3):215-222.CowardPD.Symbolicexecutionandtesting[J].InformationandSoftwareTechnology,1991(2):53-64.王言志,刘椿年.区间算术在软件测试中的应用[J].软件学报,1998,9(6):438-443.KorelB.AutomatedSoftwareTestDataGeneration[J].IEEETransactionsonsoftwareengineering,1990,16(8):870-879.SagarnaR,LozanoJ.OnthePerformanceofestimationofdistributionalgorithmsappliedtosoftwaretesting[J].AppliedArtificialIntelligence,2005,19(5):457-489.王凌.智能优化算法及其应用[M].北京：清华大学出版社,2001.BalujaS.Population-basedincrementallearning:Amethodforintegratinggeneticsearch-basedfunctionoptimizationandcompetitivelearning[R].Pittsburgh:CarnegieMellonUniversity,1994.SthamerJBH,EyresD.Automaticstructuraltestingusinggeneticalgorithms[J].SoftwareEngineeringJournal,1996,11(5):299-306.SthamerH.TheAutomaticGenerationofSoftwareTestDataUsingGeneticAlgorithms[D].Pontyprid,Wales,GreatBritain:UniversityofGlamorgan,1996.PargasR,HaroldM,PeckR.Test-datagenerationusinggeneticalgorithms[J].JournalofSoftwareTesting,VerificationandReliability,1999,9(4):263-282.TraceyN,ClarkJ,ManderK,etal.AnAutomatedFrameworkforStructuralTest-DataGeneration[C]//InProceedingsoftheInternationalConferenceonAutomatedSoftwareEngineering.[s.l.]:IEEE,1998.LiBin,LiZhishu,ChenYanhong.AutomaticTestDataGenerationToolBasedonGeneticSimulatedAnnealingAlgorithm[C]//InternationalConferenceonComputationalIntelligenceandSecurityWorkshops.[s.l.]:IEEE,2007:183-186.马敏，陈光，陈东义.基于Petri网和模拟退火遗传算法的并行测试研究[J].仪器仪表学报,2007(2):331-336.傅博.基于模拟退火遗传算法的软件测试数据自动生成[J].计算机工程与应用2005(12):82-84.陈路远.基于蚂蚁算法的路径测试数据自动生成方法研究[D].天津：河北工业大学,2007.胡先智.基于遗传蚂蚁融合算法的测试用例生成研究[D].西安：西安理工大学,2008.傅博.基于蚁群算法的软件测试数据自动生成[J].计算机工程与应用,2007(12):97-100.陈明师，刘晓杰，李涛.基于多态蚁群的测试用例自动生成[J].计算机应用研究,2009,26(6):2347-2348.DiazaE,TuyaaJ,BlancoaR,etal.Atabusearchalgorithmforstruct