2.3　动静结合的测试用例自动生成方法

在静态和动态方法的基础上,研究人员提出了动静结合的方法,即动态符号执行(dynamic symbolic execution)方法或者concolic(concrete symbolic)方法[9]。这种方法是动态方法和静态方法的折中,使各自的优势最大化。动态符号执行方法输入值的表现形式与静态符号执行方法不同,它是以具体数值来执行程序代码的。在执行过程中,首先启动代码模拟器进行符号执行,在当前路径分支语句的谓词中进行符号约束的收集;然后对该符号约束进行修改得到一条新的可行路径约束,并对其进行求解得出新的可行具体输入,继续对该输入进行新一轮的分析。这种方法相比于静态符号执行的优点是:它使用具体输入进行执行,当符号执行遇到问题时(如难处理的复杂表达式或代码不可见的函数调用),会用具体执行所得结果来代替这些难处理的符号表达式,从而使得求解过程更加容易。

贝尔实验室的Patrice Godefroid是动态符号执行方法研究方面的佼佼者[8,10,11]。他在2005年首次提出基于动态符号执行的测试用例生成方法DART[8]。这种方法首先随机生成一个输入用例,通过执行用例记录执行的程序路径,然后静态符号执行此路径获取路径上的约束集合,把约束集合中最后的分支取反,得到另一条路径和此路径的约束集合,求解此约束得到对应路径的测试用例。DART将动态测试用例生成和模型检测相结合,试图生成覆盖所有程序路径的测试用例,并通过运行时的检测工具如Purify发现程序错误。(https://www.daowen.com)

DART只处理整型约束。当符号执行无法进行的时候,则采用随机测试。Koushik Sen作为DART的开发者之一,对此方法进行了扩展,提出了对指针指向的结构体类型的测试用例生成方法。而CUTE[9]扩展了其指针处理方式,能够处理非和非空这类约束的指针表达式。

动静结合法近年来被广泛应用,研究人员不断对其进行改进以提高其性能[125-126],但依然存在一些问题。2009年,Kiran Lakhotia对动静结合的CUTE和AUSTIN工具通过大型的实际开源应用工程进行测试[127]。实验结果表明,这些方法在一些条件下确实对一些小的程序有很高的覆盖率,但对于实际工程的效果却不甚理想。实际工程的高覆盖率要求对于测试用例生成技术仍然是个很大的挑战。