Empirical evidence suggests that nearly all software errors are triggered by the interaction of one to six parameters. 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.
Applying combinatorial testing to real world software presents a number of challenges. For one of the best algorithms, the number of tests needed for combinatorial coverage of n parameters with v values each is proportional to v^t log n, where t is the interaction strength. For example, unit testing of a small module with 12 parameters requires only a few dozen tests for 2-way combinations, but approximately 12,000 for 6-way combinations. But a large number of test cases will not be a barrier if they can be produced with little human intervention, thus reducing cost. To apply combinatorial testing, it is necessary to find a set of test inputs that covers all t-way combinations of parameter values, and to match up each set of inputs with the expected output for these input values. These are both difficult problems, but they can now be solved with new algorithms on currently available hardware.
Our research program currently includes:
Lead Organizational Unit:ITL
Related Programs and Projects:
For more information regarding the Automated Combinatorial Testing for Software (ACTS) plus downloadable software and publicationsrelated to this project, please visit the Computer Security Resource Center (CSRC).
100 Bureau Drive