Computer Security Resource Center

Computer Security Resource Center

Computer Security
Resource Center

Automated Combinatorial Testing for Software

Our Research Program

This research 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. Surprisingly, although "pairwise" testing had been popular for many years, no one had looked at the actual distribution of failures by number of interacting factors. We continued this work and published other papers finding 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  our research areas. If you'd like to find out more on any of these topics, please email me: kuhn@nist.gov.

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.  

Combinatorial security testing - Combinatorial testing is especially effective for the complex challenges of secure software.

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

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. 

People

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
  • Mohammad Raunak - Loyola University Maryland
  • Dimitris Simos - SBA Research
  • Itzel Dominquez Mendoza - Centro Nacional de Metrologia, Mexico

Combinatorial testing is a growing field! The graph below charts research papers on the theory and application of combinatorial testing published each year since 1994.

Combinatorial testing papers by year

 

Created May 24, 2016, Updated October 07, 2019