2.2.5 MHS方法
近年来,基于搜索的软件工程(Search-Based Software Engineering,SBSE)[78-80]受到越来越多的关注,其最重要的特点就是将元搜索(Metaheuristic Search,MHS)方法引入软件工程。而使用MHS方法生成测试用例,即基于搜索的软件测试(Search-Based Software Testing,SBST)[5,81-84]就是MHS方法中最重要的应用。
为了便于将一个元搜索方法具体应用于一个问题,需要考虑一些决策机制,例如,如何将潜在的解进行编码从而便于搜索技术的实施。一种好的编码方案能够确保即便未被编码,但是潜在解仍在目前解空间的邻域内。这样搜索将会在具有类似属性的相邻集合内很方便地推进。在推进的过程中,需要对候选解进行评估,通常使用的评估方法是目标函数。根据目标函数的返回值,依据已有的知识和过去候选解提供的启发策略找到更好的解。因此,目标函数的制订对于搜索能否成功至关重要。在某种意义上来说,如果一个解比其他候选解更优,则它就应该具有更好的返回值;反之,如果一个解比其他解更差,则它的返回值也较差。而至于这个更优指的是返回值更大还是更小,取决于搜索是在找目标函数的最大值还是最小值。下面列举了一些比较常见的用于测试用例生成的MHS方法。
1.爬山法
爬山法也叫作逐个修改法、瞎子摸象法,是一个著名的局部搜索算法,也属于一种启发式方法[85-91]。爬山法类似于确定性问题中的一维搜索算法,它采用逐步试探的方法,这个过程类似于在目标函数的曲线上爬山。在这座山上,山峰代表局部最优解,而洼处则代表较差的局部解。在没有启发策略的爬山法中,对当前解的邻域是随机进行评估的,而更好的爬山法则应该通过一定的评估函数来确定下一步的方向,如算法2-1所示。
算法2-1从一个随机选取的初始值开始搜索,对这个初始值的邻域进行评估,检查是否有更好的候选解。如果有,则用更好的候选解替换当前解,同时对于新的当前解的邻域进行评估。如果发现更好的候选解,则继续进行替换,直到再无更好的候选解可以替换当前解。爬山法执行过程简单并能快速给出结果。但是使用爬山法的搜索容易陷入局部极值,而非全局最优解。这种情况说明搜索结束于并非最优解的一个山峰,而放弃了其他解空间的搜索。此时认为邻域内再无比当前解更好的解。由此可见爬山法对于初始值的依赖很严重。对此有一个改进方法,就是选取多个初始值,来尝试不同的搜索空间。
2.模拟退火算法
该算法的执行过程类似于在热浴槽中冷却某种物质的物理过程(这个物理过程叫作退火)。该算法最早由Metropolis等人[92]提出,后来由Kirkpatrick等人[93]发展成为一种搜索方法。模拟退火算法的基本原理类似于爬山法,但是它对于初始值的依赖要弱于爬山法,它对于搜索步骤的约束没那么严格。它接受下一个候选解的概率为p并通过下面的公式计算:
其中,δ是当前解和邻域内下一个候选解之间的差距,t是一个叫作温度的控制参数。温度根据冷却规则会冷却下来。一开始,为了能够在搜索空间中较大范围内自由移动,会设置较高的初始温度,在搜索的过程中,温度逐渐冷却。但是如果冷却过快,导致没有足够大的搜索空间被搜索到,则陷入局部极值的概率变大。最小化目标函数的模拟退火算法如算法2-2所示。
Tracey等人[94-96]的研究使用模拟退火算法进行动态测试用例生成,并希望在求解的过程中克服局部搜索的问题。在使用模拟退火算法时,必须为不同类型的输入变量定义一个合适的邻域。对于整型和实型变量来说,这个邻域可以简单定义成在一个个数值周围的取值范围。而由于布尔型和枚举型变量对于变量值的顺序要求不高,因此可以认为所有的值都在邻域内。目标函数可以简单定义为距离目标路径上指定分支的分支距离,或距离某一关键路径的目标的距离。为了避免陷入局部极值,Tracey使用了新的目标函数定义方式(如表2-2所示),他的方法需要保证新产生的候选解一定要覆盖曾经成功覆盖的子路径。
表2-2 Tracey方法的目标函数
3.遗传算法
演化算法是对于候选解模拟演化过程进行搜索的过程,其搜索方向由遗传算子和自然选择算子控制。遗传算法就是一种演化算法,它是在20世纪60年代末由美国的John Holland[97](被称为遗传算法之父)提出的。遗传算法涉及很多演化策略,几乎就在同一时期德国的Ingo Rechenburg和Hans-Paul Schwefel提出了这些策略。对于遗传算法来说,搜索过程基本上是通过一种候选解之间交换信息并进行重新组合的机制来完成的,并以此“繁育”后代;而演化策略却主要依靠变异完成,也就是随机改变候选解的一个过程。上述理论都是各自独立的,后来的研究[98-100]逐渐将这些理论进行了整合并缩小了它们之间的差异。遗传算法采用编码技术将变量区间映射到基因空间,其搜索方向是通过交叉、选择、变异等遗传操作和优胜劣汰的自然选择来决定的。遗传算法维护的不是一个当前解,而是一个候选解的种群。因此,遗传算法搜索的初始点不止一个,在搜索过程中对于搜索空间的探索范围要比局部搜索大得多。这个种群不停地迭代重组和变异,进行持续的繁衍。所以,遗传算法是一种全局搜索算法。遗传算法描述如算法2-3所示。(https://www.daowen.com)
Holland的最早专著[97]提到了一种等比例的适应度选择策略(fitness-proportionate selection)。在这种选择策略中,一个个体被选择用来繁殖的次数和种群中的其他个体是等比例的。因为其过程类似于赌场中轮盘赌的选择过程,所以也叫作轮盘赌选择(roulette wheel selection)。这种方法是遗传算法中最简单也最常用的选择方法。
遗传算法已经被应用于很多领域,本书主要关心其在测试用例生成中的应用。提出遗传算法可以应用于测试用例生成的记载最早可以追溯到文献[101-103]的研究。后来也有很多学者在这方面进行了研究[104-107]。国内薛云志等人提出基于Messy GA的测试用例自动生成方法[7],把覆盖率表示成测试输入集的函数F(X),通过Messy GA不需要染色体模式排列的先验知识即可对F(X)进行迭代寻优,提高了搜索的并行性,最终提高了覆盖率。荚伟等人[108]在进行基于路径覆盖的Ada软件测试用例自动生成时采用了遗传算法,并对它和爬山法以及随机法进行了生成测试用例效率的对比实验。
CPU的运算时间在使用遗传算法时随着输入变量取值范围的增大呈亚线性增长,而随机法则为超线性增长,所以遗传算法比随机法更适合用于大型程序[109]。遗传算法本身很复杂,作为其理论基石之一的隐性并行性的证明还存在严重缺陷[110]。另外,文献[111]在计算评价函数时,只考虑产生分支分歧的那部分分支谓词,而考虑路径上所有分支谓词才能更好地反映当前输入数据的适应程度。
在2007年的ICTAI国际会议上,Sofokleous等人提出了一种用遗传算法生成测试用例的方法[112]。在实验部分,作者通过构造的程序对算法的效果进行了验证,其中代码行从20行到2 000行不等,结果如表2-3所示。第一列是被测代码行数;第二列是生成的用例数;第三列是被测程序中包含了if语句的个数;第四列是覆盖率;第五列是嵌套if的个数;第六列是每个表达式的复杂程度,Simple指包含一个表达式,Medium指通过一个逻辑运算符连接两个表达式,High指使用两个以上逻辑运算符连接3个以上表达式;最后一列是生成测试用例所用时间。以最后一行推算,作者为一条包含40个左右表达式的路径生成测试用例的时间大概是4 min。随着代码行的增加,覆盖率下降明显。本书在第5章也做了类似的实验。本书给出的算法可以在100%覆盖率的基础上处理更大规模的表示式。
表2-3 文献[112]方法的实验结果
续表
4.蚁群算法
遗传算法和模拟退火算法是在动态测试用例生成领域应用最多的两类MHS方法。蚁群优化(Ant Colony Optimization,ACO)算法,又称蚁群算法、蚂蚁算法,在管理和工业上应用较多,可以用来寻找最优解。它由Marco Dorigo[113]提出,其灵感来自蚂蚁在寻找食物过程中发现路径的行为。蚁群算法是一种模拟进化算法,初步研究表明,该算法具有许多优良的性质。Marco Dorigo的数值仿真结果表明,蚁群算法具有一种新的模拟进化优化方法的有效性和应用价值。
世界各地的研究人员多年来对蚁群算法进行了大量的研究和应用开发,该算法现已被大量应用于众多领域。究其原因,是因为蚁群算法的求解模式结合了问题求解的快速性、全局优化特征和有限时间内答案的合理性。经过相关领域研究人员的努力,这种优越的问题分布式求解模式已在最初的算法模型基础上得到了很大的拓展和改进。现在也出现了将其用于测试用例生成的研究[114]。在文献[114]中,作者详细描述了用ACO算法进行测试用例生成的过程,发现在某些benchmark的对比实验中,该算法的性能超过了遗传算法和模拟退火算法。
5.粒子群算法
粒子群优化(Particle Swarm Optimization,PSO)算法,简称粒子群算法,是近年来发展起来的一种新的进化算法。PSO算法是一种进化计算技术,源于对鸟群捕食的行为研究,于1995年由Eberhart和Kennedy提出[115]。类似于遗传算法,PSO算法也是一种基于迭代的优化算法。系统先初始化一组随机解,再经过迭代搜索最优值。但是它没有使用遗传算法使用的交叉(crossover)以及变异(mutation),而是粒子在解空间追随最优粒子进行搜索。相比于遗传算法,PSO算法的优势是容易实现且没有必要调整许多参数。PSO算法以其实现容易、精度高、收敛快等优点引起了学术界的重视,并且在解决实际问题中展现了其优越性。近些年大量研究将PSO算法应用到测试用例生成[116,117]中,并在一些小型的benchmark上获得了不错的实验效果。
除了以上介绍的方法,南京大学徐宝文等人[118-120]将演化测试和组合测试技术用于测试用例的自动生成,研发了一个演化测试框架(ETF),为演化测试研究提供了实验平台。北京化工大学的赵瑞莲等人提出面向EFSM路径的测试数据生成方法[121,122],利用禁忌搜索(TS)策略实现了EFSM测试数据的自动生成,并使用前向分析的动态程序切片技术提高基于路径的测试用例生成效率[123]。湖南大学的李军义等人[124]利用分支函数线性逼近和极小化方法生成测试用例,并基于选择性冗余思想提高测试性能。动态方法有自身的固有问题,例如,如何处理指针变量的适应值函数等。目前大多数动态方法也仅能处理基本数值类型。
