2.2.2　分支函数极小化法

1990年,Korel对Webb Miller和David L.Spooner的研究进行了扩展,他提出了应用于Pascal语言的最具代表性的一种动态方法[5]。该方法先试探性搜索前进方向,再用模式性搜索使分支函数值尽快达到最小,为了尽量减少盲目搜索还采用动态数据流分析技术确定影响分支谓词的变量。该方法最适合处理数值型变量,在搜索过程中可能受限于局部最优解,从而无法找到满足路径约束的测试用例。对于非线性路径约束,该方法只能找到局部极小值,当谓词函数有多个局部极小值时难以找到解。因此,该方法对于非线性路径约束不是完备的。

1992年Korel发表的论文提出了面向目标的方法[66],其中所有的技术都集中在对于某条路径的执行上。之前为了满足某种覆盖准则如语句覆盖,需要首先选出一条覆盖每一个待覆盖元素的路径。而面向目标的方法省去了这个步骤,这是由于该方法依据目标节点,将分支分为3类:关键的、半关键的、非必需的。这种分类可以在控制流图上自动进行。

随着研究的深入,这种方法暴露出越来越多的问题,很多研究人员开始尝试其他搜索方法。但是Korel方法包括其对于分支函数的定义(如表2-1所示)对后来的研究产生了深远的影响,很多方法的分支函数都是对于Korel方法的改进。奚红宇等人将该方法用于Ada软件的测试用例生成[67]。1996年,这种方法被扩充为面向目标的链方法[68],链方法被应用于面向断言的测试用例生成[69]和回归测试用例自动生成[70]。(https://www.daowen.com)

表2-1　Korel方法的分支函数定义方法