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

Automated Combinatorial Testing for Software  

Software developers frequently encounter failures that occur only as the result of an interaction between two components. Number of variables involved in software failureTesters often use pairwise testing – all pairs of parameter values – to detect such interactions. Combinatorial testing beyond pairwise is rarely used because good algorithms for higher strength combinations (e.g., 4-way or more) have not been available, but empirical evidence shows that some errors are triggered only by the interaction of three, four, or more parameters (see graph).  These results have important implications for testing. If all faults in a system can be triggered by a combination of n or fewer parameters, then testing all n-way combinations of parameters can provide high confidence that nearly all faults have been discovered. We are producing methods and tools to generate tests for all n-way combinations of parameter values, using improved combinatorial testing algorithms for constructing covering arrays, and automated generation of test oracles using model checking. This work will have applications in high assurance software, safety and security, and combinatorial testing. Our focus is on empirical results and real-world problems.  For an easy to read intro to combinatorial and pairwise testing, see this article or this one.

Our research program currently includes:
    • improved covering array algorithms
    • fault localization
    • distribution of interaction faults
    • integration into the development process
    • application to modeling and simulation

Some of our accomplishments to date include:
    • empirical finding that software failures appear to be triggered by interaction of few variables (1 to 6)
    • IPOG covering array algorithm and its variants, more efficient than other known algorithms
    • demonstration of effectiveness of test prioritization
    • demonstration of improved efficiency for modeling and simulation
Rick Kuhn     or  Raghu Kacker
kuhn@nist.gov,   raghu.kacker@nist.gov
2009 Excellence in 
Technology Transfer 

Federal Laboratory
Consortium,
Mid-Atlantic Region

Beta release of combinatorial testing tool available free to testers.  The tool, named Advanced Combinatorial Testing Suite (ACTS), using Jeff Lei's IPOG algorithm, 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.  This software is free of charge and will remain free in the future.  NIST is a US Government agency.
Please Note:  Prior to Feb 09, the name "FireEye" was used for the ACTS tool. In the papers and articles listed below, FireEye is discussed; this is the same tool now called ACTS.

Who uses our combinatorial testing tool?  We have approximately 230 users as of Oct. 2009, in IT, defense, finance, telecom, and many other industries.  Here is a breakdown of our user base.  

News

Presentations

Quick introductions to Combinatorial Testing
  • Combinatorial Testing Tutorial, Powerpoint file, National Defense Industrial Association, Reston, VA, Sept 16-17, 2009. (approx. 30 min.)
  • Video of talk on software fault interactions and combinatorial testing from Open Web Applications Security Project workshop AppSec DC 2005 (approx. 15 min. plus question period)

Conference Presentations

Combinatorial Testing for software

Combinatorial Methods for Modeling and Simulation

Empirical Results

Empirical data showing all faults triggered by relatively low level of interactions between variables (less than 6-way) across a variety of application domains.

Automated Test Generation Using Model Checking

  • V. Okun, P. E. Black, “Issues in Software Testing with Model Checkers”, Proceedings of the International Conference on Dependable Systems and Networks (DSN-2003), June 2003 - explains effective use of model checking to generate complete test cases. 
  • V. Okun, "Specification Mutation for Test Generation and Analysis", PhD Dissertation, U of Maryland Baltimore Co., 2004 - both theoretical and experimental methods for selecting the most effective mutation operators for test generation.
  • P. E. Black, V. Okun, Y. Yesha, "Testing with Model Checkers: Insuring Fault Visibility", WSEAS Trans. Sys., 2 (1): 77-82, Jan. 2003 - describes specification mutation methods using a model checker to guarantee propagation of faults to visible outputs.
  • P. E. Black, V. Okun, Y. Yesha, "Mutation Operators for Specfications", Automated Software Engineering, 2000 - sets of mutation operators that yield good test coverage at reduced cost compared with other operators.
Disclaimer: Certain software products are identified inthis document. Such identification does not implyrecommendation by NIST, nor does it imply that theproducts identified are necessarily the best available for thepurpose.