Computer Security Resource Center

Computer Security Resource Center

Computer Security
Resource Center

This is an archive
(replace .gov by .rip)

Automated Combinatorial Testing for Software

Our Research Program

This research program grew out of our 2001 paper on failures in medical device software, which found that the failures were triggered by only 1 to 4 variables interacting. Subsequent research was consistent with this original finding, suggesting that all, or nearly all, software failures involve interactions among a small number of variables, no more than 6, in thousands of failure reports. 

Below are some of  the research areas we're working on now. If you'd like to find out more on any of these topics, please email me:

Covering array algorithms - better algorithms to produce 2-way through 6-way arrays. These include:

  • IPOG - very fast, producing compact arrays. IPOG is the primary algorithm used in our ACTS tool.
  • PRMI - implemented on a Linux cluster. Currently being used to tackle problems larger than are practical with other algorithms.

Fault localization - When combinatorial tests are run, some may detect faults in the application under test, but which particular combination of parameters is responsible for triggering the fault? 

Distribution of interaction faults - What proportion of faults observed in real-world software are caused by a single parameter, 2-way interactions, 3-way interactions, etc.? So far, data that we have been able to obtain suggest that the overwhelming majority of faults are caused by interactions of three or fewer parameter values, with a rapidly decreasing percentage involving 4-way to 6-way interactions. 

Integration into the development process - Tools and methods to integrate combinatorial testing into industrial software development, including methods to deal with the oracle problem and tools to link the input and output of our covering array generator with other software tools. 

Application to modeling and simulation - combinatorial methods have potential for increasing the efficiency of simulations, detecting errors, and for analysis of simulation results. 


We have friendly, formal and informal collaborations with an ever-growing number of researchers, who include:

  • Rick Kuhn and Raghu Kacker are NIST PIs
  • Jeff (Yu) Lei - University of Texas Arlington
  • Jim Lawrence - George Mason University and NIST Faculty Associate
  • Renee Bryce - University of North Texas
  • Sreedevi Sampath - University of Maryland Baltimore County
  • Tao Xie - North Carolina State University
  • Itzel Dominquez Mendoza - Centro Nacional de Metrologia, Mexico

Combinatorial testing is a growing field! The graph below charts research papers discussing combinatorial testing since 1995. (Information technology only, excludes combinatorial chemistry.) 

Bar Graph Chart: Combinatorial Testing Papers by Year

Created May 24, 2016, Updated April 19, 2018