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

Read more


Our focus is on empirical results and real-world testing.

Quick Start - It's easy to learn the basics of this method!

  1. 3-page summary
  2. Combinatorial and pairwise testing tutorial (81 pgs.)
  3. Overview slides (approx. 60 min).

FREELY AVAILABLE SOFTWARE:

  • Our combinatorial testing tools are used by hundreds of major corporations and universities, with over 3,000 copies released.
  • 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. NIST is an agency of the United States Government. 
  • To obtain the tools, please send a request to Rick Kuhn - kuhn@nist.gov We will send you a download link from our secure server. Please include 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.

Practical Examples and Case Studies - summaries of a variety of industry applications of this test method

Introducing Combinatorial Testing in a Large Organization:  Experience Report, (poster); full paper in IEEE Computer, April 2015.J. Hagar. D.R. Kuhn, R.N. Kacker, T. Wissink. An extensive evaluation of combinatorial testing by one of the world's largest aerospace firms.  Describes the experience of Lockheed Martin applying combinatorial methods in eight pilot projects, with roughly 20% cost savings and 20% to 50% better coverage. Extended abstract. Presented at 3rd International Workshop on Combinatorial Testing, Cleveland, Mar. 31, 2014.


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

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


Recent Talks:

  • Hot Topics in the Science of Security, April 10, 2018
  • Loyola University, Nov 9, 2017
  • NASA/DoD Science of Test workshop, Apr 4, 2017
  • IEEE Internet of Things workshop, April 7, 2017

Video of 2013 NASA IV&V conference briefing on application of combinatorial coverage measurement. (Charley Price and Rick Kuhn)

Combinatorial Coverage Measurement - NIST IR 7878 (released Sept. 2012)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, Centro Nacional de Metrologia of Mexico, NASA, and the U. of Maryland University College. This article explains how the approach is related to statistical Design of Experiments. Combinatorial testing poster summarizes the methodology.

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    


Back To Top

We have over 3,000 users as of 2018, 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. 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. Please include your first and last name, and company or university name (this helps us with management support for the project!) ACTS won the 2009 Excellence in Technology Transfer Award from the Federal Laboratory Consortium Mid-Atlantic Region.

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. Please include your first and last name, and company or university name (this helps us with management support for the project!)

3) Combinatorial testing tutorial, Practical Combinatorial Testing, NIST SP 800-142 (81 pages). 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.

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

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.

 

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 July 26, 2018