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

Combinatorial Methods in Software 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 what we refer to as the interaction rule, which is based on our analysis of thousands of software failures.  The interaction 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.  

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 used by hundreds of   organizations around the world for software and hardware testing of reliability, safety, and security. 
NEW ITEMS
Talks for 2013:  Carnegie Mellon U, Feb 12 (Kuhn), Loyola U.of Md., Feb 26 (Kuhn) ; IEEE ECS workshop seminar, Singapore, July 16 
Tool releases:  Version 2.7 of ACTS testing tool and Version 0.7 of CCM coverage measurement tool now available.
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.  Please consider submitting a paper!  Full details at the link.  

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  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,200 users as of January 2013, in nearly all major industries.  Here is a breakdown of our user base.

1) Combinatorial testing tool.  The tool, named 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.  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.  Interested in combinatorial methods but concerned about disrupting existing test practices?  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.   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) Comprehensive 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 21,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.  Slides and videos of the seminar are here. 
  • 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 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 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, suitable 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.