基于分类树和蚁群算法的测试用例设计

何 斌 王敏帅

（中国人民解放军91404部队，河北 秦皇岛 066000）

0 引言

软件测试是保证软件质量最为重要的一种手段，有效的软件测试可以发现软件中存在的绝大部分问题。所以，软件测试项目的终级目标是100%测试覆盖，发现软件中尽可能多的问题，为靠近这一目标测试项目组会尽可能多设计测试用例以达到最佳测试效果。因为不可能进行穷尽的测试，测试一般会在保证测试覆盖率同时尽可能精简测试集，相应的方法一直是测试工程师研究的重点课题。

基于不同测试方法设计的测试用例集会有很大的差异。在软件的系统测试阶段，分类树方法是一种非常有效的测试用例集设计方法，分类树方法是由Grochtmann和Grimm在1993年提出的，是在软件功能测试方面一种有效的测试方法，通过分类树把测试对象的整个输入域分割成独立的类。通过组合各种不同分类的结果来形成测试用例。使用分类树方法的一个重要的好处是：它把测试用例设计转变成一个组合若干结构化和系统化的测试对象组成部分的过程使其容易把握，易于理解，当然也易于文档化。但分类树设计方法并未根据测试覆盖标准对测试用例集进行约束，测试用例集往往很庞大。本文针对功能测试用例集生成，提出使用变异因子的蚁群算法对采用分类树生成的测试用例集进行优化，使测试用例集达到测试覆盖率与规模的最优化。

1 分类树方法用于测试用例设计

分类树方法的基本原理是：首先把测试对象的可能输入按照不同的分类方式进行分类，每一种分类要考虑的是测试对象的不同的方面。然后把各种分开的输入组合在一起产生测试用例，同时又能覆盖测试对象的整个输入域。

分类树方法设计测试用例的过程分为三大步骤：

1）识别出测试对象并分析输入空间。

2）对测试对象的输入空间进行分类。

3）画出分类树、组合成测试用例。

以Windows操作系统自带标准计算器为例演示分类树的测试用例设计过程：

如图1所示对计算器的输入进行划分，以一个二元运算式为例输入操作为：

把计算器输入划分成运算数、运算符、内存操作（属于扩展功能）。按等价类方法把各种分类细化各种输入可能。例如，运算数可能的输入是负数最小值、负数正常值、负数最大值、零、正数最小值、正数正常值、正数最大值、无操作等；运算符可能的输入是/、*、-、+、1/x、sqrt、%、=；内存操作的可能的操作是 MC、MR、MS、M+、无操作。 最后，测试用例由不同分类的类组合形成，在组合类时交集不能为空。测试人员组合类形成需要的测试用例，以便覆盖测试一个二元等式的所有方面并充分考虑各种可能。

从例子中可以看出测试人员如果要考虑所有组合进行用例设计，最后用例集将十分大。在实际的测试工作中，被测软件的规模及复杂程度也比例子软件大的多，采用分类树设计的测试用例数将十分巨大。事实上若无特殊要求的情况下，在满足充分性同时会考虑最精简的测试用例集，以达到测试效益的最优。

2 蚁群算法优化测试用例设计

20 世纪 90 年代意大利学者 M．Dorigo，V．Maniezzo，A．Colorni等从生物进化的机制中受到启发，通过模拟自然界蚂蚁搜索路径的行为，提出来一种新型的模拟进化算法——蚁群算法(Ant Colony Optimization,ACO)，是群智能理论研究领域的一种主要算法。

在分类树测试用例集的优化中蚁群算法可这样描述。设节点r为分类树的根节点，节点1－m分别代表分类树的叶子（测试输入值），任何一个测试用例可看成根节点到叶子j(j≠0)的路径。

将r作为蚂蚁寻优的起点，输入值j看作蚂蚁选择的食物源,dj可以理解为从寻优起点到食物源的距离。对任任意一只蚂蚁k从节点r观到节点j的概率为：

τrj（t）表示路径上残留的信息素强度，该参数表明了系统从节点r转移到j的后天演化过程中得到受益度；ηrj（t）表示先天性的启发性，该起始信息是由要解决的问题给出的即表示转移对于蚂蚁k的吸引度。α表示残留信息的相对重要程度；β表示期望值的相对重要程度。在计算器的例子中一个用例是由一组蚂蚁转移寻找食物源完成的，如完成一个二元计算式是至少由4只蚂蚁同时寻找路径完成的。在使用蚁群算法过程中每设计一个用例完成一次求解，每求解一次对路径中的信息素强度进行更新，更新的方程式为：

ρ为挥发系数，为了防止信息的无限累积，ρ必须小于1。

在实际中主要有两种应用：首轮测试用例与回归用例设计。首轮测试用例设计需要在满足覆盖率的基本上有好的发散性；回归用例设计一般的做法是首轮用例加新增用例，新增用例要求对有错误的模块有重点增加测试用例。所以，首轮测试用例设计参数选择原则：ρ挥发系数设置应适当偏大，dm可以忽略为近似。算法结束条件为分类树分支覆盖。

回归测试新增设计主要由上一轮测试问题启发，所以在其它参数不变的情况下适当增大β值并重新调整：更改为：,其中w为上一轮这一路径涉及模块发现问题数。

3 验证

为验证本文的方法进行编程实验，以上文计算器测试为例，演算达到块覆盖率的用例数。 在实验中，取 Q=1，ρ=0.8，α=0.5，β=0.7，共 39个叶子（输入值），启动5只蚂蚁，得到实验结果如表所示：

表1 得到测试用例数

以上结果表明，本方法在实践中可行。由于计算器软件没有首轮测试未发现问题，回归测试用例实验未进行。

4 结束语

本文提出以分类树为基础并以蚁群算法优化进行用例设计，可以使用例的设计更加科学化、规范化，以此基础可以进一步研究测试用例设计的自动化生成与实现，必将为软件测试带来新的技术革新。基于现有工作，下一步研究：（1）算法的通用性及自适应能力；(2)方法的工程实现可能。

［1］Dorigo M，Gambardella L M.Ant colony system：a cooperative learning approach to the traveling salesman problem [J].IEEE Transactions on Evolutionary Computation，1997，1（1）：53-66.

［2］傅博.基于蚁群算法的软件测试数据自动生成[J].计算机工程与应用,2007(12).

［3］尹文洁，崔冬华.测试用例集的方法研究[J].电脑开发与应用，2011：5.

［4］吴启迪,汪镭著.智能蚁群算法及应用[M].上海科技教育出版社,2004：4-6.

［5］朱少民.全程软件测试[M].电子工业出版社,2007,9.