Official websites use .gov
A .gov website belongs to an official government organization in the United States.

Secure .gov websites use HTTPS
A lock ( ) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.

Combinatorial Methods for Trust and Assurance

Combinatorial testing - background and fundamental papers

Fundamental background papers

  • These two 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. 

1. Empirical justification for combinatorial testing:  D.R. Kuhn, D.R. Wallace, A.M. Gallo, Jr., Software Fault Interactions and Implications for Software Testing, IEEE Transactions on Software Engineering, vol. 30, no. 6, June 2004, pp. 418-421.AbstractDOI: 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:  Y.Lei, R. Kacker, D.R. Kuhn, V. Okun and J. 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.AbstractDOI: 10.1109/ECBS.2007.47Preprint    Defines the In Parameter Order algorithm for high strength covering arrays. 

Contacts

Rick Kuhn
kuhn@nist.gov
Address: https://www.nist.gov/people/d-richard-kuhn

Raghu Kacker
raghu.kacker@nist.gov
301-975-2109
Address: http://math.nist.gov/~RKacker/

M S Raunak
raunak@nist.gov

Topics

Security and Privacy: assurance, modeling, testing & validation

Technologies: software & firmware

Created May 24, 2016, Updated June 13, 2024