面向条件判定覆盖的线性拟合制导测试生成

条件判定覆盖(Condition/Decision Coverage,C/DC)准则是各种安全攸关软件测试中常用的测试覆盖准则,它要求软件测试覆盖程序中每个判定以及条件的真/假取值.现有的自动测试生成方法在针对该准则的测试用例生成过程中存在很多不足:例如符号执行方法很难处理较为复杂的非线性条件约束,并在处理程序的规模上受到很大限制;希尔攀登法由于在搜索过程中易陷入局部最优而难以达到满足C/DC准则的高覆盖率;模拟退火法和遗传算法依赖于用户使用过程中的复杂配置,测试用例生成效果具有一定的随机性.针对这一现状,本文提出了一种新的线性拟合制导测试用例生成方法.依据C/DC准则,该方法将程序中的每一个条件判定规范化为一个与零值比较的数值函数,并以插桩与执行获得该函数当前输入下的采样.通过拟合这些采样,能够逐步判断出程序中各个条件判定与输入的关系,并利用这些关系生成高覆盖率的测试用例.相对于传统方法,本文方法具有参数配置简易,生成过程高效等优点,并且能处理带非线性条件约束,逻辑复杂的程序.在3个开源软件库中的25个真实程序上运行的实验结果表明,本文提出的方法比目前以覆盖率见长的遗传算法(Genetic Algorithm,GA)制导方法具备更好的覆盖能力与更高的执行效率.

Test Generation Approach Guided by Linear Fitting for Condition/Decision Coverage Crit

Condition/decision coverage (C/DC) is a frequently used coverage criteria for safety-critical software testing. It requires every decision and condition in the program have taken all possible outcomes (true or false). Existing approaches of automatic test generation for C/DC criteria are defective. For example, symbolic execution based approaches are limited by the constraint solver, which is difficult in processing non-linear constraints; Hill climbing often sticks at local optima, which limits yielding of high-coverage cases; Simulated annealing and genetic algorithm need complicated configuration, which make the results unstable. In this paper, we propose a novel test generation approach that is guided by linear fitting. The insight of our approach is that we sample every decision and condition of numerical values with program instrumentation. Then we build the relationship of inputs and samples with linear fitting functions. By searching the target inputs on the gradually refined functions, we generate test case with high coverage. Experiments on 25 real programs in open source projects show that our approach is more effective and efficient than the genetic algorithm of test generation.