5.1.1　背景介绍

覆盖测试的目的是为所有的程序逻辑元素生成测试用例。在所有自动覆盖测试方法中,基于约束的(constraint-based)技术和基于搜索的(search-based)技术是两种应用广泛的技术。当程序中包含输入相关的循环时,程序的路径规模可能很大,这会导致基于约束的技术无法在有限时间内完成测试,以及基于搜索的技术丢失精度。

此前,在解决由函数调用所引起的路径爆炸问题上,V.Chipounov和P.Godefroid等人提出选择执行[1]和组合执行[2]的思想,用以实现在程序空间的某一部分利用符号执行进行全路径搜索,与此同时在其余部分进行单路径的具体执行。这样的策略兼顾了分析的效率以及分析复杂系统的完整性。

循环结构可以抽象成一段具有输入和输出的代码,其输入是循环结构中读取的变量,输出是在循环结构中改变的变量,因此循环结构在逻辑上可被看作一个函数调用,由此以循环结构为单位采用不同的处理策略。为了解决覆盖测试中由于循环结构导致的路径爆炸问题,受到选择性执行思想的启发,本节提出了启发式引导的动静结合的k+1循环处理模型,对程序中的循环结构进行分类,采用不同的路径生成策略,对于循环结构内的覆盖目标生成测试用例;并且利用启发式的策略在路径生成的过程中引导子路径选择。此模型由以下模块组成。

①根据循环结构相对于覆盖目标的位置对循环结构进行分类,对不同的循环结构采取不同的路径生成策略。(https://www.daowen.com)

②对于包含目标的循环结构利用符号执行技术进行全路径搜索,在其余的循环结构利用动态执行技术生成一条可达的部分路径。

③利用启发式策略引导动态执行过程中的路径选择过程。

下面首先介绍选择性执行技术和启发式搜索技术的原理,然后描述启发式引导的k+1循环处理模型,最后使用一个实例分析展示应用此技术进行自动用例生成的过程。