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

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

作　　者：汤恩义[1,2] 周岩[1,3] 欧建生 陈鑫[1,3] 

机构地区：[1]计算机软件新技术国家重点实验室(南京大学),江苏南京210023 [2]南京大学软件学院,江苏南京210093 [3]南京大学计算机科学与技术系,江苏南京210023

出　　处：《软件学报》2016年第3期593-610,共18页Journal of Software

基　　金：国家自然科学基金(61402222;91318301;61561146394);国家重点基础研究发展计划(973)(2014CB340703);教育部高等学校博士学科点专项科研基金(20110091120058);江苏省产学研项目(BY2014126-03)~~

摘　　要：条件判定覆盖(condition/decision coverage,简称C/DC)准则是各种安全攸关软件测试中常用的测试覆盖准则,它要求软件测试覆盖程序中每个判定以及条件的真/假取值.现有的自动测试生成方法在针对该准则的测试用例生成过程中存在很多不足.例如:符号执行方法很难处理较为复杂的非线性条件约束,并在处理程序的规模上受到很大限制;希尔攀登法由于在搜索过程中易陷入局部最优,而难以达到满足C/DC准则的高覆盖率;模拟退火法和遗传算法依赖于用户使用过程中的复杂配置,测试用例生成效果具有一定的随机性.针对这一现状,提出了一种线性拟合制导测试用例生成方法.依据C/DC准则,该方法将程序中的每一个条件判定规范化为一个与零值比较的数值函数,并以插桩与执行获得该函数当前输入下的采样.通过拟合这些采样,能够逐步判断出程序中各个条件判定与输入的关系,并利用这些关系生成高覆盖率的测试用例.相对于传统方法,该方法具有参数配置简易、生成过程高效等优点,并且能够处理带非线性条件约束、逻辑复杂的程序.在3个开源软件库中的25个真实程序上运行的实验结果表明,所提出的方法比目前以覆盖率见长的遗传算法(genetic algorithm,简称GA)制导方法具备更好的覆盖能力与更高的执行效率.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; and simulated annealing and genetic algorithm need complicated configuration, which make the results unstable. In this paper, a novel test generation approach that is guided by linear fitting is proposed. The basis of the approach is to sample every decision and condition of numerical values with program instrumentation. The relationship of inputs and samples is then build with linear fitting functions. By searching the target inputs on the gradually refined functions, test case is generated with high coverage. Experiments on 25 real programs in open source projects show that the proposed approach is more effective and efficient than the genetic algorithm of test generation

关 键 词：测试用例自动生成 条件判定覆盖 线性拟合 关联路径 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]