Automated Combinatorial Testing for Software (ACTS)

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:

• improved covering array algorithms
• fault localization
• distribution of interaction faults
• integration into the development process
• application to modeling and simulation.

• Extensively cited (two of top three) papers covering empirical research on combinatorial testing.
• Freely available testing tool that has been obtained by over 170 organizations, including most major software development firms and other Fortune 500 companies.