测试是软件开发过程中的重要环节,是工业界常用的质量保障手段。为满足测试充分覆盖的要求,测试人员需要花费大量的时间和精力来设计测试用例。测试用例自动生成技术针对给定的测试覆盖准则自动生成有效的测试用例,从而减少测试人员的工作量,降低软件生产成本,是软件测试技术研究的一个重要方向。在白盒测试中,条件判定覆盖(CDC)和改进的条件判定覆盖(MCDC)是各种安全攸关软件测试中常用的测试覆盖准则。由于非线性运算的存在,相应的测试用例自动生成问题已经被理论证明是NP问题。目前的研究工作主要采用符号执行技术和启发式搜索方法探寻满足程序约束条件的解。符号执行技术受制于当前的约束求解器不能有效求解非线性约束条件;启发式搜索方法(主要代表是基于遗传算法的搜索和基于模拟退火算法的搜索)的主要问题在于搜索区间不可扩展且搜索的效能受到多个参数的影响,从而针对一个具体程序找到最优的参数设定是非常困难的。分量线性拟合法也是一种启发式搜索方法,但是不同于基于遗传算法的搜索和基于模拟退火算法的搜索,分量线性拟合法不采用适应度函数,而是借鉴了程序中的条件是关于程序输入的函数这一特性,通过线性拟合关于条件的输入分量函数来预测问题的解,具有搜索空间可扩展、可以处理非线性约束和浮点型计算、参数设定简单等特点,已经被应用于解决面向路径的测试用例生成问题。本文面向条件判定覆盖和改进的条件判定覆盖准则,研究基于分量线性拟合法的测试用例自动生成技术,主要工作包括以下两个方面:·针对条件判定覆盖和改进的条件判定覆盖准则,提出基于边界区间上分量线性拟合函数的区间扩展法和基于可变区间的搜索机制,在此基础上提出了基于分量线性拟合方法的CDC/MCDC测试用例自动生成算法。该算法能够处理复合约束条件、非线性条件以及浮点型条件。它首先设定一个分量作为自变量,然后随机的生成一组输入来执行待测程序,记录执行过程经过条件语句的点集合,紧接着以这些点为样本来计算条件关于自变量的分量线性拟合函数,并用该函数预测条件的变化趋势,进而获得可能的输入。算法不断地重复执行程序和拟合分析可能输入,在搜索到所求的解或达到搜索阈值后停止。·设计并实现了原型工具:CLF-CDC,该工具为一款eclipse插件,能够为C函数自动生成满足CDC覆盖准则的测试用例。为了评价CLF生成测试用例的能力和性能,本文从数学包Numerical Recipes和开源网站选取了 25个基准C程序,将CLF算法与GA算法生成的测试用例的覆盖率和生成测试用例的时间进行对比了实验。基于统计性检验方法检测两种方法的覆盖效果和性能是否具有显著性差异。实验结果表明,CLF在生成测试用例的能力上优于GA,特别地,CLF能够覆盖更多的极值条件。从性能上看,CLF覆盖一个条件所花费的时间和最优参数下的GA相当,但CLF算法不需要寻找最优的参数设定。