基于智能水滴算法的软件路径测试用例生成方法

马竹根

摘 要： 提出基于智能水滴算法的测试用例生成方法，描述了如何把测试用例的生成问题转换成智能水滴在控制流图的各边之间寻找最优路径的问题，讨论了利用智能水滴算法发现控制流图中的测试路径的算法。该方法利用控制流图的圈复杂度和自然界水滴的基本属性，使用动态参数来发现控制流图中的独立路径，能通过自动生成测试路径保证完全的代码覆盖。

关键词： 控制流图； 圈复杂度； 独立路径； 智能水滴算法； 测试用例生成

中图分类号：TP301.6 文献标志码：A 文章编号：1006-8228（2016）05-73-05

Abstract： This paper proposes a automatic test case generation method based on intelligent water drop algorithm， and describes how to convert the problem of test case generation into the problem that intelligent water drop searches the optimal path in between the each side of the control flow graph. The method uses the cyclomatic complexity of the control flow graph and the basic properties of the water droplet， and uses the dynamic parameters to find the independent paths in the control flow graph， which can ensure the complete code coverage by automatic generation of test paths.

Key words： control flow graph； cyclomatic complexity； independent path； intelligent water drop algorithm； test case generation

0 引言

软件测试是保证软件质量的重要手段，软件测试在软件开发和维护过程中是花费最多的一个阶段。将软件测试环节自动化，将极大地降低开发成本和提高软件可靠性。实现软件自动测试的核心是生成能发现软件错误或缺陷的有效的测试数据，以满足既定的测试充分性准则。基于搜索的测试用例生成技术[1]可以利用适应度函数，将测试用例生成问题转化成函数优化问题，进而利用一些人工智能搜索算法寻找最优解，最终达到程序所要求的覆盖标准。人工智能搜索算法种类有很多，近年来，研究人员开始使用遗传算法[2]、粒子群优化算法[3-4]、蜂群算法[5]、神经网络[6]、蚁群算法[7]、模拟退火算法[8]等智能优化算法来解决软件测试中的测试用例的生成问题。

本文使用一种新的启发式算法——智能水滴算法（Intelligent Water Drops algorithms）[9]生成测试用例，使用基本路径作为测试充分性准则，从而使用较少的时间和花费得到有效的测试用例。

1 基本路径测试法

基本路径测试法是在程序控制流图的基础上，通过分析控制结构的圈复杂度，导出基本可执行的路径集合，从而设计测试用例的方法。通常基本路径测试法包括程序控制流图、计算程序圈复杂度、确定基本路径集、导出测试用例。

1.1 程序控制流图

程序控制流图是对程序流程图简化后得到的，它可以更加突出的表示程序控制流的结构。程序中的语句构成控制流图中的节点，并由带箭头的曲线将节点按照程序执行顺序进行连接。

1.2 圈复杂度

圈复杂度是一种代码复杂度衡量标准[10]，常用于评估一个模块判定结构的复杂程度，在数值上等价于独立运行的路径条数。圈复杂度是根据控制流图中的边和节点来计算的，圈复杂度计算公式有以下三种。

⑴ V（G）=E-N+2

其中V（G）表示圈复杂度，E表示控制流图的边的数量，N 表示控制流图的节点个数。

⑵ 圈复杂度等于控制流图中判定节点的数量加1。

V（G）=P+1，P表示判定节点数

⑶ 圈复杂度等于控制流图将平面划分成区域的数量。

V（G）=R，R表示区域数

1.3 基本路径集

基本路径集由独立路径组成。独立路径是指，程序中至少引进一个新的处理语句集合或一个新条件的任一路径，即独立路径必须至少包含一条在定义路径之前不曾用过的边的路径。对于一个复杂的程序，在使用基本路径测试时，其独立路径数量的上界是由程序的圈复杂度来确定的，而且这一独立路径数能够保证程序中所有语句至少被执行一次。

1.4 生成测试数据

为了确保基本路径集中每一条路径的执行，根据判断结点给出的条件，选择适当的数据以保证每一条路径可以被测试到。

2 智能水滴算法

智能水滴算法由Hamed Shah-Hosseini于2007年提出[9]。智能水滴（Intelligent Water Drop，IWD），它具有以下两个重要的属性：水滴携带的泥土量soil（IWD）和水滴的速度velocity（IWD），这两个属性会随着水滴流动而发生变化。水滴从当前位置i移动到下一个位置j，其速度值的增量定义为Δvelocity（IWD），水滴的速度增量非线性反比于从位置i到j路径上的泥土量soil（i，j）。

⑴

其中符号表示非线性正比关系，计算公式为：

⑵

其中av，bv，cv是用户选定的参数。

由于从位置i到位置j的路径中带走了部分泥土，智能水滴中携带的泥土量soil（IWD）也会相应增加。路径当中减少的泥土量和智能水滴中增加的泥土量是相等的，即：

⑶

泥土的增量非线性反比于水滴从当前位置i移动到下一位置j的时间time（i，j），其计算公式为：

⑷

其中as，bs，cs都是大于0的参数。

智能水滴移动时间正比于位置i到位置j之间的距离，反比于水滴的移动速度。

⑸

下面给出一种计算智能水滴由位置i到位置j的时间公式：

⑹

这里没有直接使用位置i到位置j的距离d（i，j），而是使用了更广义的反向启发函数 HUD（Heuristie undesirability）。HUD（i，j）表示了智能水滴拒绝从位置i移动到位置j的程度，在实际的优化问题中代表了优化依据的条件。

在位置i到位置j的路径上，由于智能水滴的移动而带走了一定量的泥土，路径当中的剩余的泥土量用soil（i，j）表示，它与路径中失去的泥土量Δsoil（i，j）成正比。

⑺

从位置i到位置j路径当中的泥土量通过由智能水滴带走的泥土量来更新，计算公式为：

⑻

而智能水滴中携带的泥土量soil（IWD）按照以下公式更新：

⑼

智能水滴在遇到多条可选路径时，会更倾向于选择泥土量较少的路径。对于智能水滴可能选择的多个下一位置，每个位置以一定的概率被选择。以p（i，j）代表智能水滴在位置i时选择j作为下一位置的概率，它与路径当中的泥土量成反比。

⑽

在位置i与位置j之间的路径上泥土量越少，则位置j越有可能被在位置i的智能水滴选择作为下一步移动的位置。一种可能的计算下一步位置概率的表达式如下：

⑾

其中

ε是很小的正数，用来防止函数f的分母为0。函数g用来确保将位置i与位置j之间的路径泥土量转换为正数，其表达式为：

⑿

函数min表示当前位置与所有可能选择的下一个位置之间泥土量的最小值。

3 智能水滴算法测试用例生成方法

许多软件测试问题可归结为基本路径测试数据生成问题，可描述为[13]：给定程序的一条目标路径，在程序的输入空间中寻找测试数据，使得以该数据为输入，所经过的路径为目标路径。测试数据的生成过程就是根据一定的规则，对被测试程序的输入空间进行抽样的过程。因此可以把测试数据生成问题转化为一个优化问题，利用智能优化算法来求解。智能水滴算法在很多优化问题中得到了应用，本文应用智能水滴算法来生成测试数据。

智能水滴算法生成测试用例的过程可分为二个主要阶段。第一阶段利用分析工具（如LEX和YACC）生成包含控制流图的输出文件。第二个阶段对控制流图进行处理，可分为以下三个步骤。

⑴ 分析控制流图中每一个结点的圈复杂度。

⑵ 利用智能水滴算法在控制流图中从开始结点到终端结点遍历得到所有可能的独立路径。

⑶ 对每一条独立路径生成测试数据。

算法：智能水滴算法获取控制流图中独立路径

初始化：

程序控制流图如图1所示。

表1中简要描述了路径的发现过程。从控制流图顶端结点1（Node-1）开始，它有二条可能的路径，即：结点2（Node-2）或结点7（Node-7），根据算法计算出概率适应度p（1，2）=0.9，p（1，7）=0.1。概率值越大选择这条路径的概率越大，因此选择路径p（1，2）。从Node-1到Node-2速度更新按算法中的第5步计算，Vel（IWD）=200.1，算法中第6步更新时间参数，计算公式为time（1，2）=HUD（2）/Vel（IWD）=90/200.1=0.45，这里HUD（2）=10（控制流图的圈复杂度）*9（Node-2的圈复杂度）=90。算法中第7步按公式计算泥土的变化Δsoil（1，2）=1.469，算法中第8步更新智能水滴从Node-1到Node-2带走的泥土Soil（IWD）=1.469。算法第9步更新Node-1和Node-2之间路径上的泥土：

5 结束语

测试用例的生成是软件测试的重要内容，高效的软件测试用例自动生成方法可以简化软件测试过程，减少软件测试时间和资源消耗，提高测试效率和测试质量。本文将面向路径的测试数据生成问题转化成最优化问题，提出了使用智能水滴算法自动发现测试路径的策略，算法的输出包含所有的独立路径。本文着重介绍了应用智能水滴算法解决软件测试数据生成问题的方法和技术，并给出了具体的应用实例。实验结果表明，基于智能水滴算法的测试实例能够在更小的迭代次数之内收敛，并得到最优结果。下一步的研究工作需对测试用例的生成进行优化，算法中可加入一些启发式算法来提高效率。

参考文献（References）：

[1] Harman M， Jones BF. Search based software engineering[J].Information and Software Technology，2001.43（14）：833-839

[2] Miller J， Reformat M， Zhang H. Automatic test datageneration using genetic algorithm and program dependence graphs[J]. Information and Software Technology，2006.48：586-605

[3] 姜淑娟，王令赛，薛猛等.基于模式组合的粒子群优化测试用例生成方法[J].软件学报，2016.27（4）：1-17

[4] 毛澄映，喻新欣，薛云志.基于粒子群优化的测试数据生成及其实证分析[J].计算机研究与发展，2014.51（4）：824-837

[5] 李云玮，孙忱，范玉顺.基于智能非信息素蜂群优化的软件测试研究[J].计算机应用研究，2014.31（8）：2399-2403

[6] 李鑫.基于神经网络的路径覆盖测试数据生成[D].中国矿业大学，2014.

[7] 傅博.基于蚁群算法的软件测试数据自动生成[J].计算机工程与应用，2007.43（12）：97-99

[8] 王博，王曙燕.一种新的基于模拟退火的测试用例生成与约简算法[J].计算机应用与软件，2013.30（2）：78-81

[9] H. S. Hosseini. Problem solving by intelligent water drops[A].IEEE Congress on Evolutionary Computation[C]， Washington， DC， USA： IEEE Computer Society，2007.3226-3231

[10] 陈梦云，高建华.基于圈复杂度的静态测试用例排序方法[J].计算机应用与软件，2016.33（1）：1-3

[11] 巩敦卫，姚香娟，张岩.测试数据进化生成理论及应用[M].科学出版社，2014.