Official websites use .gov
A .gov website belongs to an official government organization in the United States.

Secure .gov websites use HTTPS
A lock ( ) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.

Combinatorial Methods for Trust and Assurance

Overview

Combinatorial methods reduce costs for testing, and have important applications in software engineering:  

ACTS - award winning tool for combinatorial testing, used in thousands of organizations worldwide. 
The ACTS tool was the subject of the Most Influential Paper award at ICST 2023 (Practical category), Yu, L., Lei, Y., Kacker, R. N., & Kuhn, D. R. "ACTS: A combinatorial test generation tool" 2013 IEEE Sixth International Conference on Software Testing, Verification and Validation (ICST)
- ACTS development team received the Excellence in Technology Transfer Award, 2009, Federal Laboratory Consortium Mid-Atlantic Region

Examples and Case Studies - from some of the world's largest organizations, including Adobe, Avaya, Bosch, IBM, Jaguar Land Rover, Lockheed Martin, Mercedes Benz, 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    More than 4,500 corporate and university users   --Version 3.2 of ACTS released Sept. 30, 2019 
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.  Please provide first and last name, and organization.  We will send you a download link. 

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

New papers:

  • Kuhn, D. R., Raunak, M. S., Kacker, R. N., Chandrasekaran, J., Lanus, E., Cody, T., & Freeman, L. (2024). Assured Autonomy Through Combinatorial Methods. Computer, 57(5), 86-90.
  • M S Raunak, D R Kuhn, R N Kacker, Jeff Y Lei, Combinatorial Testing for Reliable Systems, IEEE Reliability Magazine, vol 1, issue 1, Feb 2024, DOI: 10.1109/MRL.2024.3355874
  • M. Olsen, M S Raunak, D.R. Kuhn, Predicting ABM Results with Covering Arrays and Random Forests, International Conference on Computational Science,  Prague, Czech Republic, 3-5 July, 2023.
  • D. R. Kuhn, M S Raunak, R.N. Kacker, Ordered t-way Combinations for Testing State-based Systems, IEEE 16th Intl Conf on Software Testing, Verification and Validation Workshops, 2023
  • K. Khadka, J. Chandrasekaran, J.Y. Lei, R. Kacker, R. Kuhn, Synthetic Data Generation Using Combinatorial Testing and Variational Autoencoder,  IEEE 16th Intl Conf on Software Testing, Verification and Validation Workshops, 2023 
  • B. Garn, D. Schreiber, D. Simos, R. Kuhn, J. Voas, R. Kacker, Summary of Combinatorial Methods for Testing Internet of Things Smart Home Systems, IEEE 16th Intl Conf on Software Testing, Verification and Validation Workshops, 2023

ORACLE-FREE TESTING  
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  - kuhn@nist.gov, or Raghu Kacker - raghu.kacker@nist.gov  or M S Raunak - ms.raunak@nist.gov

Disclaimer: Software products are identified in this document. Such identification does not imply recommendation by NIST, or that the products identified are necessarily the best available for the purpose.

Contacts

Rick Kuhn, NIST
Address: https://www.nist.gov/people/d-richard-kuhn

Raghu Kacker, NIST
301-975-2109
Address: http://math.nist.gov/~RKacker/

M S Raunak, NIST

Topics

Security and Privacy: assurance, modeling, testing & validation

Technologies: semiconductors, software & firmware

Created May 24, 2016, Updated November 01, 2024