NIST Logo and ITL Banner Link to the NIST HomepageLink to the ITL HomepageLink to the NIST Homepage
Search CSRC:

Combinatorial Methods in Testing  

Combinatorial methods have been demonstrated to significantly reduce the cost and increase the quality of software and system testing  As part of NIST's mission to advance the science of testing and measurement, we have conducted extensive analyses of software failure in real-world systems. Combinatorial testing  takes advantage of the interaction rule, which is based on our analysis of thousands of software failures.  The rule states that most failures are induced by single factor faults or by the joint combinatorial effect (interaction) of two factors, with progressively fewer failures induced by interactions between three or more factors. Therefore if all faults in a system can be induced by a combination of t or fewer parameters, then testing all t-way combinations of parameter values is pseudo-exhaustive and provides a high rate of fault detection.  Two primary tools can be used: ACTS, to generate tests, and CCM, to measure combinatorial aspects of test quality.  

Our focus is on empirical results and real-world testing.  See:  summary and 5-pg overview.

This article explains how the approach is related to statistical Design of Experiments.  

Tools provided freely on this site are used by hundreds of organizations around the world for software and hardware testing of reliability, safety, and security. Our research collaborations include the U. of Texas Arlington, US Air Force, Carnegie Mellon, U. of North Texas, Johns Hopkins University Applied Physics Lab, U. of Maryland Baltimore County, the Centro Nacional de Metrologia of Mexico, NASA, and the U. of Maryland University College.  

Combinatorial testing poster summarizes the methodology.

Quick Start, for those new to combinatorial testing. It's easy to learn the basics of this approach.
1. 3-page summary of the method.
2. An extended how-to  tutorial that provides more depth (81 pgs.).
3. Briefing slides (approx. 60 min).

Workshop in 2014  T
he 3rd International Workshop  on Combinatorial Testing will be held in Cleveland, Ohio, USA, in association with the
IEEE International Conference on Software Testing, Verification and Validation (ICST) 2014.    
 

New book
 
We have published the first textbook on combinatorial methods in software testing, Introduction to Combinatorial Testing, Rick Kuhn, Raghu Kacker, Yu "Jeff" Lei, with chapter contributions from Renee Bryce, Eduardo Miranda, Sreedevi Sampath, and George Sherwood.  (CRC Press, ISBN
1466552298, June 2013; 319 pgs.).  The book provides software testers, developers, and students with a self-contained tutorial on how to use these methods for real-world software. "I thoroughly recommend it to anyone involved in the practice of software testing." - ACM Computing Reviews

Talks for 2014:  ICST keynote, Apr. 2 (Kuhn), ASTQB keynote, Mar. 26 (Kuhn), US Census Bureau, Mar 13 (Kuhn), Carnegie Mellon University, Feb 12 (Kuhn)

Tool releases, May 2013:  Version 2.8 of ACTS testing tool and Version 0.8 of CCM combinatorial coverage measurement tool now available.

1st Asian Workshop on Combinatorial Testing (PPT in zip file)
Combinatorial Coverage Measurement  - NIST IR 7878 (released Sept. 2012)
2nd International Workshop on Combinatorial Testing association with 5th IEEE International Conference on Software Testing, Verification and Validation (ICST 2013, March 18-22) Luxembourg.   

Our research program includes:
    • advanced 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  triggered by interactions of few variables (1 to 6)
    • IPOG covering array algorithm and its variants, more efficient than other known algorithms
    • demonstrating effectiveness of test prioritization
    • demonstrating improved efficiency for modeling and simulation
    • access control testing automation
    • measurement science and tools for combinatorial coverage
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 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.

We have over 1,400 users as of June 2013, in nearly all major industries.  Here is a breakdown of our user base.

1) Combinatorial testing tool, for generating test suites.   Advanced Combinatorial Testing System (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.  ACTS was developed by NIST and the University of Texas at Arlington. To request a copy, send email to Rick Kuhn - kuhn@nist.gov.  Please include your first and last name, and company or university name (this helps us with management support for the project!)

2) Combinatorial coverage measurement tool, for evaluating quality of test suites.  Useful for gaining the advantages of combinatorial testing without disrupting existing test practice.  The CCM measurement tool can analyze existing
tests for 2-way through 6-way interactions they already have.   An easy-to-use GUI is included.  CCM was developed by NIST and the Centro Nacional de Metrologia of Mexico.  To request a copy, send email to Rick Kuhn - kuhn@nist.gov.  Please include your first and last name, and company or university name (this helps us with management support for the project!)

3) Testing tutorial, 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 24,000 downloads!

4) 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.

5) 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.

Past Events

  • 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 10 presented, lots of lively discussion.  Presentations here.  
  • NIST/Carnegie Mellon University workshop, June 7, 2011, on software verification was a great success, with more than 150 participants locally and via webcast.   
  • A survey by Gary Gack found that nearly everyone who tried combinatorial testing has found it useful!
  • Combinatorial coverage measurement was presented to NASA developers and researchers at the NASA IV&V Workshop , Sept 11-13, 2012.  
  • We gave talks at East Carolina University and Carnegie Mellon University earlier this year.
  • ACTS team members presented three papers at the First Intl Workshop on Combinatorial Testing, April, 2012.
  • 1,000th organization acquired ACTS tool in March 2012. 
  • 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 MaintenanceICSM 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 EngineerInformation 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 and Talks


Quick introductions to Combinatorial Testing

Conference Presentations

Tutorial

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

Papers

Combinatorial Methods for Modeling and Simulation


Automated Test Generation Using Model Checking

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.Belorussian translation of our project summary here.