Constructing interaction test suites for highly-configurable systems in the presence of constraints: A greedy approach
Constructing interaction test suites for highly-configurable systems in the presence of constraints: A greedy approach
复制标题
DOI：
10.1109/tse.2008.50
复制
发表时间：
2008-09-01
影响因子：
7.4
通讯作者：
Shi, Jiangfan
中科院分区：
文献类型：
--
作者：
Cohen, Myra B.;Dwyer, Matthew B.;Shi, Jiangfan
研究人员探索了组合交互测试（CIT）方法的应用，以构建样品以驱动软件系统配置的系统测试。在许多这样的系统中，将CIT应用于高度可配置的软件系统是复杂的，即在许多此类系统中，特定配置参数之间存在限制，使某些组合无效。许多CIT算法缺乏避免这些算法的机制。在最近的工作中，自动化约束解决方法已与基于搜索的CIT构造方法结合使用，以解决约束问题，并有希望的结果。但是，这些技术可能会产生非平凡的开销。在本文中，我们基于以前的工作，以开发一种贪婪的CIT样品生成算法，这些算法利用了现代布尔满意度（SAT）求解器进行的计算，以修剪CIT问题的搜索空间。我们对这些算法在四个现实世界中高度可配置的软件系统以及具有共享这些系统特征的合成示例的群体上进行了比较评估。结合起来，我们的技术在存在约束的情况下将CIT的成本降低到不牺牲解决方案质量的广泛使用的无约束的CIT方法的30％。
Researchers have explored the application of combinatorial interaction testing (CIT) methods to construct samples to drive systematic testing of software system configurations. Applying CIT to highly-configurable software systems is complicated by the fact that, in many such systems, there are constraints between specific configuration parameters that render certain combinations invalid. Many CIT algorithms lack a mechanism to avoid these. In recent work, automated constraint solving methods have been combined with search-based CIT construction methods to address the constraint problem with promising results. However, these techniques can incur a nontrivial overhead. In this paper, we build upon our previous work to develop a family of greedy CIT sample generation algorithms that exploit calculations made by modern Boolean satisfiability (SAT) solvers to prune the search space of the CIT problem. We perform a comparative evaluation of the cost effectiveness of these algorithms on four real-world highly-configurable software systems and on a population of synthetic examples that share the characteristics of those systems. In combination, our techniques reduce the cost of CIT in the presence of constraints to 30 percent of the cost of widely used unconstrained CIT methods without sacrificing the quality of the solutions.