Combinatorial testing - background and fundamental papers
Fundamental background papers
- These papers established much of the basis for today's interest in combinatorial methods for testing and assurance.
- The first one provided empirical evidence, across a range of domains, that most failures are triggered by one or two factors interacting, with progressively fewer by three or more factors. Failures involving more than six factors were not seen, and have not been found since. Consequently, covering all 5-way or 6-way combinations can be thought of as "pseudo exhaustive" or "effectively exhaustive" since they cover all, or nearly all, inputs that matter with respect to triggering failures.
- The second paper documents the IPOG algorithm that generates covering arrays covering all t-way combinations. This algorithm makes it possible to provide the pseudo-exhaustive coverage of t-way combinations described previously. The algorithm also includes the ability to specify constraints among input parameter values, which are common in real-world applications, thus making combinatorial testing practical for industrial use.
- The third paper introduced the concept of combinatorial coverage, measuring the degree to which combinations are covered in a test or data set. Important properties are shown. Combinatorial coverage has applications in both software verification and autonomous systems or machine learning.
1. Empirical justification for combinatorial testing: Kuhn, D. Richard, Dolores R. Wallace, and Albert M. Gallo. Software Fault Interactions and Implications for Software Testing, IEEE Transactions on Software Engineering, vol. 30, no. 6, June 2004, pp. 418-421.Abstract; DOI: 10.1109/TSE.2004.24 Preprint. Investigates interaction level required to trigger faults in a large distributed database system.
2. IPOG algorithm used in construction of covering arrays: Lei, Yu, Raghu Kacker, D. Richard Kuhn, Vadim Okun, and James Lawrence. IPOG: a General Strategy for T-way Software Testing, 14th Annual IEEE International Conference and Workshops on the Engineering of Computer-Based Systems (ECBS’07), Tucson, Arizona, March 26-29 2007, pp. 549-556.Abstract; DOI: 10.1109/ECBS.2007.47; Preprint Defines the In Parameter Order algorithm for high strength covering arrays.
3. Combinatorial coverage: Kuhn, D. Richard, Itzel Dominguez Mendoza, Raghu N. Kacker, and Yu Lei. Combinatorial coverage measurement concepts and applications 2013 IEEE Sixth International Conference on Software Testing, Verification and Validation Workshops, pp. 352-361. IEEE, 2013. Abstract; DOI:10.1109/ICSTW.2013.77; Preprint
