Combinatorial and Pairwise Testing  

Reducing the cost of testing: As part of NIST's mission to advance the science of testing and measurement, we are developing tools for a  method to significantly reduce the number of tests needed for high assurance.  The method, known as combinatorial testing, takes advantage of what we refer to as the interaction rule, which is based on extensive  empirical evidence (see graph).   The interaction rule states that: most failures are triggered by one or two parameters, and progressively fewer by three or more parameters. Therefore if all faults in a system can be triggered by a combination of t or fewer parameters, testing all t-way combinations of parameter values is pseudo-exhaustive and provides a very high rate of fault detection.

Our focus is on empirical results and real-world problems.  For a quick summary of combinatorial and pairwise testing, see this article or this one.

Tools provided freely on this site are being used by hundreds of major corporate and government organizations for software and hardware testing of reliability, safety, and security.

Version 2.4 of ACTS testing tool now available.

1st International Workshop on Combinatorial Testing  In association with 5th IEEE International Conference on Software Testing, Verification and Validation April 17-21, 2012, Montreal, Canada - The workshop was a great success, with more than 20 papers submitted, 10 presented, lots of lively discussion.  Presentations here.  Join us next year!

NIST/Carnegie Mellon University workshop, June 7, 2011, on software verification was a great success, with more than 150 participants local and via webcast.  Slides and videos of the seminar are here. 

Combinatorial and pairwise testing tutorial  (Oct. 2010) - a concise, easy to read tutorial, suitable for individual study or classroom use. Public domain, distribution unlimited; 81 pages.   Over 10,000 downloads in 8 months!

A survey by Gary Gack found that nearly everyone who tried combinatorial testing has found it useful!

Belorussian translation of our project summary here.

Our research program currently includes: improved covering array algorithms combinatorial coverage measurement cybersecurity testing fault localization distribution of interaction faults testing web apps application to modeling and simulation Some of our accomplishments to date include: empirical finding that software failures appear to be triggered by interaction of few variables (1 to 6) IPOG covering array algorithm and its variants, more efficient than other known algorithms demonstration of effectiveness of test prioritization demonstration of improved efficiency for modeling and simulation access control testing automation Rick Kuhn     or  Raghu Kacker kuhn@nist.gov,   raghu.kacker@nist.gov

2009 Excellence in  Technology Transfer  Federal Laboratory Consortium, Mid-Atlantic Region

FREELY AVAILABLE SOFTWARE:  Software available on this site is free of charge and will remain free in the future.  No license is required and there are no restrictions on use.  NIST is an agency of the United States Government .

Combinatorial testing tool.  The tool, named Advanced Combinatorial Testing System (ACTS), using Jeff Lei's IPOG algorithm, 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.  Combinatorial coverage measurement tool.  Interested in combinatorial methods but concerned about disrupting existing test practices?  This measurement tool can be used to analyze existing test suites to determine the level of combinatorial coverage they already have.   Who uses our combinatorial testing tools?  We have over 800 users as of Sept. 2011, in nearly all major industries.  Here is a breakdown of our user base.

Comprehensive tutorial on combinatoral testing.  Practical Combinatorial Testing, NIST SP800-142 (pdf  81 pages, 841Kb).   This publication provides a self-contained tutorial on using combinatorial testing for real-world software.  It introduces the key concepts and methods, explains use of software tools for generating combinatorial tests, and discusses advanced topics.  The material is accessible to an undergraduate student of computer science or engineering, and includes an extensive set of references to papers that provide more depth on each topic.  Oct. 2010.  Public domain, distribution unlimited; 81 pages.  Over 10,000 downloads in the first 8 months!

New: Security policy testing tool.  The Access Control Policy Test (ACPT) tool allows policy authors to conveniently specify access control models (such as RBAC and Multi-Level models) and rules as well as access control properties.  From the specified models and rules, the ACPT tool automatically synthesizes deployable policies in XACML and generates combinatorial tests to verify security policy implementations.  Complete test cases are generated, consisting of test inputs and expected output for each set of inputs. ACPT uses ACTS to provide 2-way to 4-way combinatorial testing of policies.   To request a copy, send email to Vincent Hu - vhu@nist.gov.

New:  Web app testing tool.  CPUT (Combinatorial-based Prioritization of User-session-based Testsuites) applies combinatorial methods to testing web applications.  Test prioritization is used to make web app testing much more manageable.  The tool allows testers to easily collect, prioritize, and reduce user-session-based test cases. CPUT provides (1) guidance to users on how to configure their web server to log important usage information, (2) automated parsing of web logs into XML formatted test cases that can be used by test replay tools, (3) automated prioritization of test cases by length-based and combinatorial-based criteria, and (4) automated reduction of testcases by combinatorial coverage.

News

• We did a half-day tutorial on combinatorial methods at ICSM 2011 and lecture at Verify/ATI in September. 
• Rick Kuhn and Raghu Kacker are presenting a half-day tutorial on combinatorial methods at the IEEE International Conference on Software Maintenance,  ICSM 2011, Sept. 26 in Williamsburg, Virginia. 
• Rick Kuhn and Sreedevi Sampath are speaking at the Verify/ATI conference  on Sept. 27, in Arlington, Virginia. 
• Raghu Kacker presented seminars on combinatorial testing and ACTS at Fraunhofer Institute for Open Communication Systems (FOKUS) and Technical University of Berlin June 27 and 28, 2011.
• Advanced test methods seminar in Pittsburgh at Carnegie Mellon University with Prof. Eduardo Miranda in June, drew over 150 attendees in person and via internet.  
• ACTS profiled in IEEE Computer,, Feb. 2011, News Briefs.
• Seminars and talks  : NASA IV&V, Aug. 31; Fraunhofer Center - UMD, Aug. 15; NASA IV&V, July 14; Carnegie Mellon Univ., June 7, Johns Hopkins University Applied Physics Lab, Apr 27; Institute for Defense Analyses, Apr 6; Army Test and Evaluation Command, Mar 30;  Institute for Defense Analyses Feb 25;Carnegie-Mellon University Feb 9.
• Raghu Kacker gave invited talks at Indian Institute of Technology, Madras, and Infosys Corp., January 2011.
• November issue of Logigear magazine features an interview (Rick Kuhn) and an article on combinatorial testing.
• ACTS featured in SIGNAL, the flagship publication of the Armed Forces Communications and Electronics Association.
• Rick Kuhn speaking on combinatorial testing at Dept of Energy modeling and simulation workshop Dec 1, 2010.
• "New Help on Testing for Common Cause of Software Bugs", Government Computer News, Nov 1, 2010. ACTS also featured in The Engineer,  Information Week and TMC.net.
• ACTS project featured in October issue of Logigear Magazine.
• NIST initiated a Cooperative Research and Development Agreement with Lockheed Martin Corp. in Aug. 2010.
• 500th organization acquired ACTS tool in November 2010 
• Rick Kuhn, Raghu Kacker, and Sreedevi Sampath conducted a workshop on combinatorial testing for the US Army Test and Evaluation Command in May.
• 300th organization acquired ACTS tool in February 2010 
• Rick Kuhn gave an invited talk on combinatorial testing at Carnegie Mellon Univ. in January.
• ACTS received 2009 Excellence in Technology Transfer Award from the Federal Laboratory Consortium Mid-Atlantic Region.
• Our new introductory article on combinatorial testing was featured as one of the "Highlights" for the August 2009 issue of IEEE Computer, the flagship publication of the IEEE Computer Society.

Seminars

Note:  As US Government work, the work of Kuhn, Kacker, and Black is not subject to US copyright.  You are welcome to use any or all of these slides freely (but we always appreciate it if you cite NIST!)
Quick introductions to Combinatorial Testing

• Combinatorial Testing and Design of Experiments, TU Berlin, June 28, 2011.
• Combinatorial Testing, Institute for Defense Analyses, 6 April 11. (approx. 2 hours)
• Combinatorial Testing Seminar, US Army Test & Evaluation Command, Aberdeen Proving Ground, 17 May 10. (approx. 3 hours).
• Combinatorial Testing, Carnegie-Mellon University 26 Jan 10. (approx. 60 min.)
• Combinatorial Testing Tutorial, National Defense Industrial Association, Reston, VA, Sept 16-17, 2009. (approx. 30 min.)

Conference Presentations

• Rick Kuhn, Combinatorial Methods for Discrete Event Simulation of a Grid Computer Network, ModSim World 2009,  Oct. 14-17 2009, Virginia Beach, Virginia.
• Rick Kuhn, Raghu Kacker, Combinatorial Testing Tutorial, Military Test and Evaluation, McLean, VA, June 24-25, 2009.  (approx. 45 min.)
• 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.
  

Tutorial

Combinatoral and pairwise testing tutorial  Practical Combinatorial Testing, NIST SP800-142, (Oct. 2010) - a concise, easy to read tutorial, suitable for individual study or classroom use. Public domain, distribution unlimited; 81 pages. 

Papers

• V.C. Hu, D.R. Kuhn, T. Xie, J. Hwang, "Model Checking for Verification of Mandatory Access Control Models and Properties", Intl. J. of Software Eng. and Knowledge Eng., vol. 21, no. 1, 2011, pp. 103-127. - demonstrates use of combinatorial methods for testing access control rules. 
• J. Lawrence, R.N. Kacker, Y.Lei, D.R. Kuhn, M. Forbes, "A Survey of Binary Covering Arrays", Electronic Journal of Combinatorics, vol. 18  n. 84, 
• D.R. Kuhn, R.N. Kacker, Y. Lei, "Advanced Combinatorial Test Methods for System Reliability", 2010 Annual Technical Report of the IEEE Reliability Society, Jan. 2011.
• D.R. Kuhn, J.M. Higdon, J.F. Lawrence, R.N. Kacker, Y. Lei, "Combinatorial Methods for Event Sequence Testing", 8 Oct 2010 (submitted for publication).
• C. Montanez, D.R. Kuhn, M. Brady, R. Rivello, J. Reyes, M.K. Powers, "An Application of Combinatorial Methods to Conformance Testing for Document Object Model Events", NIST-IR 7773.  25 Jan 2011. 
• R.C. Bryce, C.J. Colbourn, D.R. Kuhn, "Finding Interaction Faults Adaptively using Distance-Based Strategies", 16th IEEE International Conference on Engineering of Complex Computer Systems, Las Vegas, Apr. 27-29, 2011.
• J.R. Maximoff, M.D. Trela, D.R. Kuhn, R. Kacker, "A Method for Analyzing System State-space Coverage within a t-Wise Testing Framework", IEEE International Systems Conference 2010, Apr. 4-11, 2010, San Diego.
• D.R. Kuhn, R. Kacker, Y.Lei, "Random vs. Combinatorial Methods for  Discrete Event Simulation of a Grid Computer Network", Proceedings, Mod Sim World 2009,  Oct. 14-17 2009, Virginia Beach, pp. 83-88,  NASA CP-2010-216205, National Aeronautics and Space Administration.
  ModSim World paper is a condensed version of this tech report:  
  D.R. Kuhn,R. Kacker, Y. Lei, "Combinatorial and Random Testing Effectiveness for a Grid Computer Simulator" NIST Tech. Rpt. 24 Oct 2008.
• R. Kuhn, R. Kacker, Y. Lei, J. Hunter, "Combinatorial Software Testing", IEEE Computer, vol. 42, no. 8 (August 2009).
• R. Bryce, Y. Lei, D.R. Kuhn, R. Kacker, "Combinatorial Testing", Chap. 14, Handbook of Research on Software Engineering and Productivity Technologies: Implications of Globalization,  Ramachandran, ed. , IGI Global, 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.
• 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 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.
• 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.
• Y. 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.
• 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.

Combinatorial Methods for Modeling and Simulation

• D.R. Kuhn, R. Kacker, Y.Lei, "Random vs. Combinatorial Methods for  Discrete Event Simulation of a Grid Computer Network", Proceedings Mod Sim World 2009,  Oct. 14-17 2009, Virginia Beach, Virginia.  Proceedings published as NASA CP-2010-216205.(see tech report below for more detailed presentation of these results)
  D.R. Kuhn,R. Kacker, Y. Lei, "Combinatorial and Random Testing Effectiveness for a Grid Computer Simulator" NIST Tech. Rpt. 24 Oct 2008.
• 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.

Automated Test Generation Using Model Checking

• V.C. Hu, D.R. Kuhn, T. Xie, J. Hwang, "Model Checking for Verification of Mandatory Access Control Models and Properties", Intl. J. of Software Eng. and Knowledge Eng., vol. 21, no. 1, 2011, pp. 103-127.
• 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.
• 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 in this document. Such identification does not imply recommendation by NIST, nor does it imply that the products identified are necessarily the best available for thepurpose.