周吴杰 张德平 徐宝文

(1东南大学计算机科学与工程学院，南京 210096)

(2南京大学软件新技术国家重点实验室，南京 210093)

(3南京航空航天大学信息科学与技术学院，南京 210016)

(4南京大学计算机科学与技术系，南京 210093)

组合测试是一种重要的软件测试方法，旨在用较少的测试用例有效地检测软件系统中各个因素间的交互作用对系统产生的影响.组合测试的一个关键问题是组合测试用例生成问题，即在保证因素组合覆盖能力的前提下，生成规模尽可能小的测试用例集，从而在保证测试用例错误检测能力的基础上尽可能节约测试成本.两两组合测试问题作为组合测试的简单情形已有大量的研究并在软件测试领域中获得广泛的应用.研究者们通过数学构造、贪心算法以及智能搜索等方法来生成规模尽可能小的测试用例集［1－7］，随后高维以及变强度的组合测试用例生成问题也得到研究［8－9］.由于两两组合测试用例生成问题的 NP－complete性质［1］，现有的近似算法均无法生成最优解.有些生成测试用例的启发式算法运行时间较长，只能在因素较少的测试场景中使用.本文提出一种简单快速的数学构造算法，该方法建立在二元的两两组合的最优测试数据集的生成算法基础上，在二元情形下能得到最优解.对于一般的待测软件系统，算法能确保得到的测试用例数据集规模是关于因素数目k对数阶增长的.算法的时间复杂性为O(klog k)，所以对于大规模的待……