Automated Combinatorial Testing for Software - beyond pairwise testing

Software developers frequently encounter failures that occur only as the result of an interaction between two components. Testers often use pairwise testing – all pairs of parameter values – to detect such interactions. Combinatorial testing beyond pairwise is rarely used because good algorithms for higher strength combinations (e.g., 4-way or more) have not been available, but empirical evidence shows that some errors are triggered only by the interaction of three, four, or more parameters (see graph).  These results have important implications for testing. If all faults in a system can be triggered by a combination of n or fewer parameters, then testing all n-way combinations of parameters can provide high confidence that nearly all faults have been discovered. We are producing methods and tools to generate tests for all n-way combinations of parameter values, using improved combinatorial testing algorithms for constructing covering arrays, and automated generation of test oracles using model checking. This work will have applications in high assurance software, safety and security, and combinatorial testing. Our focus is on empirical results and real-world problems.  For an easy to read intro to combinatorial and pairwise testing, see this article.   (updated 4 Sept 08)

Accomplishments

• Beta release of combinatorial testing tool available to testers.  The tool, named FireEye, can compute tests for 2-way through 6-way interactions.  An easy-to-use GUI is included.  More here.   To request a copy, send email to Rick Kuhn - kuhn@nist.gov.  (This software is provided free of charge.  NIST is an agency of the US Government.)
• Empirical data showing all faults triggered by relatively low level of interactions between variables (less than 6-way) across a variety of application domains.
• New algorithms to generate covering arrays that can produce optimal arrays for many applications and near optimal arrays for very large applications (several hundred variables).
• Proof-of-concept demonstration of integrating combinatorial testing with automated generation of test oracles using model checking.

This web site provides research, empirical data, and tools for pseudo-exhaustive and combinatorial testing. Contact: Rick Kuhn, kuhn@nist.gov or Raghu Kacker, raghu.kacker@nist.gov (please include "testing" in subject line to help avoid spam filter).

News

Software Development Times article: Automatically Automate your Automation, Apr. 29, 2008.

We made Network World's list of 25 Radical Network Research Projects You Should Know About.  Apr. 17, 2008.

Rick Kuhn gave an invited talk on combinatorial testing and our project at George Washington University, Mar. 10, 2008.

Jeff Lei interviewed in Dr. Dobb's Journal -  Conversations:  Pairwise and Combinatorial Testing.   Feb. 28, 2008. 

Open-source tool 'will boost software quality' - Computerworld UK, Dec. 14, 2007.

NIST Working on New Method for Finding Software Bugs - Government Computer News, Dec 13, 2007.

Briefings

• D.R. Kuhn, R. Kacker, "Automated Combinatorial Testing", VERIFY 2007, Crystal City, VA, Oct. 29-30, 2007.
• P. Black, "My Life with Bugs, or Why I Believe in Combinatorial Testing", American Society for Quality, Gaithersburg, MD Oct. 30, 2007.
  
• Y. Lei, "IPOG - A General Strategy for t-Way Software Testing", IEEE Engineering of Computer Based Systems conference, 2007.- describes generalized IPO algorithm for constructing t-way covering arrays.
• D.R. Kuhn, V. Okun, "Automated Combinatorial Testing for Software", ISSRE 06, Raleigh, Nov. 6, 2006.
• D. R. Kuhn, V. Okun, "Pseudo-exhaustive Testing For Software (ppt file), 30th NASA/IEEE Software Engineering Workshop, April 25-27, 2006 - proof-of-concept experiment on pseudo-exhaustive testing.
• J. Lei, "In Parameter Order: A Test Generation Strategy for Pairwise Testing", 6/21/05 - explains the IPO algorithm, one of the most widely used in combinatorial testing.
  
• D. R. Kuhn, "Software Fault Interactions", OWASP AppSec DC 2005 - reviews empirical results on fault interactions, suggesting a need for combinatorial testing.

Publications on Combinatorial Testing

• V. Hu, D.R. Kuhn, T. Xie, "Property Verification for Generic Access Control Models",  IEEE/IFIP International Symposium on Trust, Security, and Privacy for Pervasive Applications, Shanghai, China, Dec. 17-20, 2008.
• D.R. Kuhn, R. Kacker, Y. Lei, "Automated Combinatorial Test Methods:  Beyond Pairwise Testing", Crosstalk, Journal of Defense Software Engineering, vol. 21, no. 6, June 2008  - a fairly comprehensive tutorial on combinatorial testing and automated test generation, with a worked example.
• D.R. Kuhn Y. Lei, R. Kacker, "Practical Combinatorial Testing – Beyond Pairwise Testing", IEEE IT Professional, vol. 10, no. 3, June 2008  - quick introduction to combinatorial testing. 
• Y. Lei, R. Kacker, D. Kuhn, V. Okun, J. Lawrence, ``IPOG/IPOD: Efficient Test Generation for Multi-Way Software Testing," accepted for publication in Journal of Software Testing, Verification, and Reliability, 2007. (Published Online: Nov 29 2007, DOI: 10.1002/stvr.381)
• Y. Lei, R. Carver, R. Kacker, D. Kung, ``A Combinatorial Strategy for Testing Concurrent Programs," Journal of Software Testing, Verification, and Reliability, 17(4):207-225, 2007.
• Y.Lei, R. Kacker, D.R. Kuhn, V. Okun, J. Lawrence, "IPOG - a General Strategy for t-way Testing", IEEE Engineering of Computer Based Systems conference, 2007.
• R.C. Bryce, C.J. Colbourn, D.R. Kuhn, "Finding Interaction Faults Adaptively Using Distance Based Strategies" (submitted for publication)
• R. Bryce, C.J. Colbourn. Prioritized Interaction Testing for Pairwise Coverage with Seeding and Avoids, Information and Software Technology Journal (IST, Elsevier), (October 2006), 48(10):960-970.
• R. Bryce, A. Rajan, M.P.E. Heimdahl, "Interaction Testing in Model-Based Development:  Effect on Model Coverage, 13th Asia-Pacific Software Engineering Conf. Bangalore, India, 2006.
• J. Lei, "In Parameter Order: A Test Generation Strategy for Pairwise Testing", 6/21/05 - introduces IPO and outlines extension to > pairwise test.
  Performance comparison with other tools here.
• R. Bryce, C.J. Colbourn, M.B. Cohen, "A Framework of Greedy Methods for Constructing Interaction Tests", 27th Intl. Conf. on Software Engineering, 2005.
• M. Grindal, J. Offutt, S. Andler, "Combination Testing Strategies: a Survey", Software Testing, Verification and Reliability, Vol. 15, No. 3, pp. 167-199, 2005 - a survey of combinatorial testing methods and results.

Empirical Results

Empirical data showing all faults triggered by relatively low level of interactions between variables (less than 6-way) across a variety of application domains.

• D. R. Kuhn, V. Okun, "Pseudo-exhaustive Testing For Software (conf. paper), 30th NASA/IEEE Software Engineering Workshop, April 25-27, 2006 - proof-of-concept experiment on pseudo-exhaustive testing, integrating automated test generation with combinatorial testing.
• D.R. Kuhn, D.R. Wallace, A.J. Gallo, Jr., "Software Fault Interactions and Implications for Software Testing", IEEE Trans. on Software Engineering, vol. 30, no. 6, June, 2004) - investigates interaction level required to trigger faults in a large distributed database system.
• D.R. Kuhn, M.J. Reilly, "An Investigation of the Applicability of Design of Experiments to Software Testing", 27th NASA/IEEE Software Engineering Workshop, NASA Goddard Space Flight Center, 4-6 December, 2002 - investigates interaction level required to trigger faults in open source browser and server.
• D.R. Wallace, D.R. Kuhn, "Failure Modes in Medical Device Software: an Analysis of 15 Years of Recall Data ," International Journal of Reliability, Quality, and Safety Engineering, Vol. 8, No. 4, 2001 - categorizes failures by their symptoms and faults, including interaction level required to trigger faults in medical device software.

Automated Test Generation Using Model Checking

• V. Okun, P. E. Black, “Issues in Software Testing with Model Checkers”, Proceedings of the International Conference on Dependable Systems and Networks (DSN-2003), June 2003 - explains effective use of model checking to generate complete test cases. 
• V. Okun, "Specification Mutation for Test Generation and Analysis", PhD Dissertation, U of Maryland Baltimore Co., 2004 - both theoretical and experimental methods for selecting the most effective mutation operators for test generation.
• P. E. Black, V. Okun, Y. Yesha, "Testing with Model Checkers: Insuring Fault Visibility", WSEAS Trans. Sys., 2 (1): 77-82, Jan. 2003 - describes specification mutation methods using a model checker to guarantee propagation of faults to visible outputs.
• P. E. Black, V. Okun, Y. Yesha, "Mutation Operators for Specfications", Automated Software Engineering, 2000 - sets of mutation operators that yield good test coverage at reduced cost compared with other operators.