Computer Security Resource Center

Computer Security Resource Center

Computer Security
Resource Center

Automated Combinatorial Testing for Software

Project Overview

Combinatorial testing is a proven method for more effective software testing at lower cost. Line Graph showing Cumulative percent of software failuresThe key insight underlying combinatorial testing’s effectiveness resulted from a series of studies by NIST from 1999 to 2004. NIST research showed that most software bugs and failures are caused by one or two parameters, with progressively fewer by three or more. This finding, referred to as the interaction rule, has important implications for software testing because it means that testing parameter combinations can provide more efficient fault detection than conventional methods. Multiple studies have shown fault detection equal to exhaustive testing with a 20X to 700X reduction in test set size.  New algorithms compressing combinations into a small number of tests have made this method practical for industrial use, making it possible to do better testing at lower cost. See articles on high risk software testing or security and reliability

Version 3.2 of ACTS released Sept. 30, 2019

QUICK START - It's easy to learn the basics of this method!    

FREELY AVAILABLE SOFTWARE:  testing tools used by hundreds of major corporations and universities 

  • Software on this site is free of charge and will remain free in the future. It is public domain; no license is required and there are no restrictions on use. You are free to include it and redistribute it in commercial products if desired. NIST is a US Government agency, doing research in advanced measurement and test methods. 
  • To obtain the tools, please send a request to Rick Kuhn - kuhn@nist.gov  including your name and the name of your organization. No other information is required, but we like to have a list of organizations so that we can show our management where the software is being used. We will send you a download link.

PRACTICAL EXAMPLES AND CASE STUDIES - summaries of a variety of industry applications of this test method, including bibliography of published papers from some of the world's largest organizations, including Adobe, Avaya, Daimler AG, IBM, Jaguar Land Rover, Lockheed Martin, Red Hat, Rockwell Collins, Siemens, the US Air Force, the US Marine Corps, and others. 

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
  • Developed sequence covering arrays, extending combinatorial methods to event sequence testing
  • Measurement science and tools for combinatorial coverage
  • Theorem relating (static) combinatorial input space coverage to (dynamic) structural code coverage, and
  • Methods for error detection without conventional test oracle

Contacts:  Rick Kuhn or Raghu Kacker  kuhn@nist.govraghu.kacker@nist.gov    

CURRENT RESEARCH:

Oracle-free testing - Software testing normally requires that for each test, there is an expected output, known as a test oracle.  Combinatorial methods make it possible to detect a significant number of faults without a conventional test oracle.  This seemingly impossible task is achieved using two layers of covering arrays with equivalence classes derived from specifications. Source code is not required.  Essentially, we are able to take advantage of the information latent in equivalence classes to do extensive consistency checking, revealing errors. 

  • Presentation on this method from the NSF Research Experience for Undergraduates
  • Paper - Intl. Workshop on Combinatorial Testing, 2015 - introduces this method; with illustrative examples
  • Paper - Intl. Workshop on Combinatorial Testing, 2016 - related method applied to access control rules

Combinatorial security testing - Combinatorial testing is especially effective for the complex challenges of secure software.

  • Cryptographic code
  • Security protocols 
  • Details of this effort
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 the purpose.

Created May 24, 2016, Updated October 07, 2019