Combinatorial methods can reduce costs for software testing significantly. They may also be one of the few practical approaches for assurance in AI and machine learning, especially for autonomous systems, where many conventional methods cannot be used.
Combinatorial methods have two primary applications in software engineering:
- Combinatorial or t-way testing is a proven method for more effective testing at lower cost. The key insight underlying its 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: 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.
- Metrology* and measurement of input space coverage. Sound engineering requires adequate measurement and analysis. Testing is the most commonly used approach for software assurance, yet it remains as much judgement and art as science. Structural coverage adds some rigor to the process by establishing formally defined criteria for some notion of test completeness, but even full coverage, however defined, may miss faults related to rare inputs not included in test vectors. Structural coverage measures must be supplemented with measures of input space coverage for verification that the input model is sufficient. See article on measurement of input space coverage. These measurements are also useful in assurance and verification of autonomous systems and explainable AI.
*Metrology is the science of measurement (NIST is the US national metrology institute).
Practical Examples and Case Studies - from some of the world's largest organizations, including Adobe, Avaya, Daimler AG, IBM, Jaguar Land Rover, Lockheed Martin, US Nuclear Regulatory Commission, Red Hat, Rockwell Collins, Siemens, the US Air Force, US Army, US Marine Corps, US Navy, and others.
- Industrial examples - - Autonomous systems - - Cybersecurity -
FREELY AVAILABLE SOFTWARE: tools used in more than 3,000 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 - email@example.com .
Please provide first and last name, and organization. For example : Rick Kuhn, NIST. We will send you a download link. No other information is required, but we like to be able to show our management where the software is being used.
- Version 3.2 of ACTS released Sept. 30, 2019
QUICK START - It's easy to learn the basics of this method!
Why Input Space Coverage Matters, IEEE Computer, January, 2020. We suggest that structural coverage measures must be supplemented with measures of input space coverage. Useful input space measures exist and have a relationship with structural coverage measures, providing a means of verifying that an adequate input model has been defined.
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. A U.S. patent (#10552300) has been issued for this method, but this patent does not apply to ACTS or any other tools on this site; these tools are public domain. For more information on the oracle-free testing method, please contact our Technology Partnerships Office.
SOME OF OUR ACCOMPLISHMENTS TO DATE INCLUDE:
- Empirical finding that software failures are triggered by interactions of only a 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 firstname.lastname@example.org, email@example.com
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.