论文投稿_医学论文投稿_核心期刊,职称论文投稿发表_论文部落

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

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

　　引言

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

　　本文使用一种新的启发式算法——智能水滴算法（IntelligentWaterDropsalgorithms）[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智能水滴算法

　　智能水滴算法由HamedShah-Hosseini于2007年提出[9]。智能水滴（IntelligentWaterDrop，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（Heuristieundesirability）。HUD（i，j）表示了智能水滴拒绝从位置i移动到位置j的程度，在实际的优化问题中代表了优化依据的条件。

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

　　⑺

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

　　⑻

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