2.1.2 典型的测试用例生成技术
1.区间削减
1991年,Demillo和Offutt提出了一种叫作区间削减(domain reduction)的静态分析技术,来进行基于约束的测试用例自动生成[52]。基于约束的测试能够对于测试的目标建立起一个约束系统,而这个约束系统的解能够满足测试目标。作者进行基于约束测试的最初目标是为变异测试生成测试用例。在这个约束系统内,可达性约束(reachability constraints)描述了到达某个特定语句要满足的条件。必要性约束(necessity constraints)描述了杀死一个变异体要满足的条件。区间削减技术尝试在这个系统内进行求解。系统的输入是每个变量的区间,这个区间可以根据变量类型得到,也可以由测试人员指定。区间削减流程主要考虑两类约束:一类是由一个关系运算符、一个变量和一个常数组成的,另一类是由一个关系运算符和两个变量组成的。其余的约束可以通过反向替换进行化简。当无法再进行化简时,就选取区间最小的变量并给它赋一个随机值,这个随机值在系统内进行反向替换,然后就可以对其余变量进行类似操作。如果所有的变量都以这种方式成功地被赋值,则约束系统被满足,否则就重复变量赋值阶段的操作,并希望能够找到新的随机值使约束得到满足。文中提出了一个用于测试用例生成的工具Godzilla,其结构如图2-1所示。
图2-1 测试用例自动生成工具Godzilla的结构
使用基于约束的测试,必须在分析约束前对其进行计算。而这些约束是通过符号分析得到的,所以这个方法也会遇到符号分析的常见问题,如循环和过程调用。于是Offutt等人后来又提出了一种叫作动态区间削减(dynamic domain reduction)[53]的方法,试图解决上述问题。虽然叫作动态区间削减,但这个方法并没有实际执行变量的输入,因此仍然属于静态测试用例生成。与文献[52]的区间削减相比,文献[53]中变量的区间是在符号分析阶段根据待覆盖路径中所遇到的谓词“动态”削减的。如果分支谓词涉及变量之间的比较,那么在分支处参与比较的变量的区间就会在某个“分割点”处进行分裂,而不是随机地赋予一个值。例如,有两个输入变量y和z,它们的区间都是[-10,10],如果出现了分支谓词y＜z,并且需要覆盖其真分支,那么为了满足条件就会对变量的区间进行分裂,如令y的区间为[-10,0],z的区间为[1,10]。如果以这种方式进行的区间分裂遭遇了死端无法前进,则需要进行回溯操作纠正前面的区间分裂操作。
尽管这种方法试图解决符号分析所带来的问题,但是实际上类似循环之类的问题仍然没有得到解决。而且作者也没有提到对于其他类型变量如何进行区间削减,如枚举类型。总之,动态区间削减使用代数约束来描述测试用例,通过变量区间的比较和阈值的设定进行变量区间的缩减,使用二分搜索方法,但是缺乏启发信息引导搜索的方向。本书方法和动态区间削减有一些相似之处,但是由于10多年来静态分析技术的进步,以及本书中大量启发策略的应用,加上CTS抽象内存模型对复杂数据类型的支持和动静结合的循环处理模型,本书的方法更加高效和实用。
2.KLEE
2008年,斯坦福大学的Cadar等人开发了一个符号执行工具KLEE[54],使用了一系列的约束求解优化算法,通过分析约束和变量之间的相关性,将约束表达式划分为相互独立的子集来提高约束求解的效率,从而达到高覆盖率的目标。国防科技大学的李仁见等人[55]提出了一种链表抽象表示方法。该方法根据变量对链表节点的可达性质定义了变量可达向量,采用带计数的变量可达向量集描述链表的形态及数量性质,并定义了基本链表操作的抽象语义。通过简单扩展,该方法可以建模包括环形链表在内的所有单向链表。为了验证该链表抽象方法的正确性,采用KLEE作为基本的符号执行器,并对常见链表操作程序的运行时错误、长度相关性质等关键性质进行了分析与验证。(https://www.daowen.com)
3.静态单一赋值
Robschink方法先将程序静态转换成静态单一赋值(Static Single Assignment,SSA)形式,将程序切片与求解路径约束相结合,依据系统依赖图中的路径,确定并简化路径执行的必要条件,然后用约束求解器求解[56]。为了便于采用基于量词消解的约束求解器,该方法要求路径中所有变量都是存在量词。
该方法仅限于算术公式,而求解其他类型的公式则需要用到其他的约束求解技术。另外,该方法所建立的约束系统会很大,因为它需要将被测试的程序(路径上的语句)转换成SSA,甚至可能包括一些与求解问题无关的变量。该方法对于线性路径约束不是完备的。
4.基于抽象内存模型的方法
针对复杂数据类型变量的表示和存储问题,本书作者所在的北京邮电大学网络与交换技术国家重点实验室的CTS项目组提出了面向测试用例生成的抽象内存模型[57]来存储动态数据类型约束,模拟程序实际语义,可以解决指针的别名、数组的变下标等问题,并支持链表、树、字符串等动态数据类型。该模型的功能包括:①能准确记录在符号执行过程中字符串、复杂结构体和数组变量的状态;②通过对抽象内存模型的操作可以精确模拟指向字符串和复杂结构体的指针操作;③字符串库函数操作可以准确映射到对抽象内存模型的操作;④通过对抽象内存模型的操作可以模拟动态下标对应的数组元素的操作;⑤在符号执行过程中,被测路径的字符串、复杂结构体和数组变量的约束条件被准确记录到抽象内存模型中。
通过开源的约束求解器Choco,验证了这个模型对于数组、字符串等类型的支持[58-60]。而本书方法正是建立在这个模型基础上的,并开发出具有独立知识产权的测试用例生成工具。
5.其他方法
C.V.Ramamoorthy方法将输入变量排好序后,通过将解方程、回溯法和随机法结合起来的方式进行测试用例的求解[41];P.D.Coward将目标函数定义为各有关变量之和,用线性规划求解线性约束系统[61];Euclide系统则基于符号执行和数值分析,将约束传播、整数线性松弛和搜索算法结合起来进行约束求解[62]。南京大学的李宣东等人[63]提出面向对象的分层切片方法及其算法,并将其用于分析和理解程序;张健等人用后向替换法建立线性约束系统,用线性规划法进行求解[64]。
