The dynamic domain reduction procedure for test data generation

Test data generation is one of the most technically challenging steps of testing software, but most commercial systems currently incorporate very little automation for this step. This paper presents results from a project that is trying to nd ways to incorporate test data generation into practical test processes. The results include a new procedure for automatically generating test data that incorporates ideas from symbolic evaluation, constraint-based testing, and dynamic test data generation. It takes an initial set of values for each input, and dynamically \pushes " the values through the control- ow graph of the program, modifying the sets of values as branches in the program are taken. The result is usually a set of values for each input parameter that has the property that any choice from the sets will cause the path to be traversed. This procedure uses new analysis techniques, o ers improvements over previous research results in constraint-based testing, and combines several steps into one coherent process. The dynamic nature of this procedure yields several bene ts. Moving through the control ow graph dynamically allows path constraints to be resolved immediately, which is more e cient both in space and time, and more often successful than constraint-based testing. This new procedure also incorporates an intelligent search technique based on bisection. The dynamic nature of this procedure also allows certain improvements to be made in the handling of arrays, loops, and expressions; language features that are traditionally di cult to handle in test data generation systems. The paper presents the test data generation procedure, examples to explain the working of the procedure, and results from a proof-of-concept implementation