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.   

Our research program currently includes:
  - improved covering array algorithms
  - fault localization
  - distribution of interaction faults
  - integration into the development process
  - application to modeling and simulation.

Contact: Rick Kuhn, kuhn@nist.gov or Raghu Kacker, raghu.kacker@nist.gov                         (updated 30 July 09)

>>> free beta release of combinatorial testing tool available to testers.  The tool, named Advanced Combinatorial Testing Suite (ACTS), can compute tests for 2-way through 6-way interactions.  An easy-to-use GUI is included.  More here.   A comparison of ACTS with similar tools shows that ACTS produces smaller test sets (with the same degree of coverage) and is faster than others.  To request a copy, send email to Rick Kuhn - kuhn@nist.gov.  This software is provided free of charge and will remain free in the future.  NIST is an agency of the US Government.
Please Note:  Prior to Feb 09, the name "FireEye" was used for the ACTS tool. In the papers and articles listed below, FireEye is discussed; this is the same tool now called ACTS.

Who uses our combinatorial testing tool?  We have approximately 200 users as of July 2009, in IT, defense, finance, telecom, and many other industries.  Here is a breakdown of our user base.  

News

Rick Kuhn and Raghu Kacker will give invited talks on combinatorial methods for cyber security testing at the DHS Software Assurance working group forum, June 16 - 18, 2009; and the  Military Test and Evaluation Summit, June 24-25, McLean, VA.

Oct. 2008: Testing expert Elfriede Dustin talked about ACTS at the Google Test Automation Conference Oct 24, 2008.  Video here.

Oct. 2008:  ACTS covering array tool is being used by W3C DOM Level 3 Events working group to test conformance.   Using 4-way covering arrays, strong testing is being provided with 1,833 tests, as compared with over 36,000 before.

We have established a database of covering arrays here.

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 was 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.

Proof-of-concept demonstration of integrating combinatorial testing with automated generation of test oracles using model checking.  Tutorial on this method here. 

Briefings

• Rick Kuhn, Raghu Kacker, Combinatorial Testing Tutorial, Military Test and Evaluation, McLean, VA, June 24-25, 2009.
• 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.

Combinatorial Testing for software

• R. Kuhn, R. Kacker, Y. Lei, J. Hunter, "Combinatorial Software Testing", IEEE Computer (to appear, 2009).
• 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.
• M. Ellims, D. Ince, M. Petre, "The Effectiveness of T-Way Test Data Generation", SAFECOMP 2008, Springer LNCS 5219, pp.16–29.
• M. Forbes, J. Lawrence, Y. Lei, R.N. Kacker, and D.R. Kuhn   "Refining the In-Parameter-Order Strategy for Constructing Covering Arrays", NIST Journal of Research, Vol. 113, No. 5 (Sept/Oct 2008), pp. 287 - 297.
• 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, vol. 18, pp. 125-148, 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.

Combinatorial Methods for modeling and simulation

• R. Kessel, R. Kacker, "A Test of Linearity Using Covering Arrays for Evaluating Uncertainty in Measurement",  Advanced Mathematical and Computational Tools in Metrology and Testing, Paris (France) 23-25 June, 2008.
• D.R. Kuhn,R. Kacker, Y. Lei, "Combinatorial and Random Testing Effectiveness for a Grid Computer Simulator" NIST Tech. Rpt. 24 Oct 2008.

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.

Disclaimer: Certain software products are identified inthis document. Such identification does not implyrecommendation by NIST, nor does it imply that theproducts identified are necessarily the best available for thepurpose.