Automatic test data generation using constraint solving techniques
Arnaud Gotlieb B, Bernard Botella, Michel Rueher · ACM SIGSOFT International Symposium on Software Testing and Analysis (ISSTA) · 1998
Automatic test data generation leads to identify input values on which a selected point in a procedure is executed. This paper introduces a new method for this problem based on constraint solving techniques. First, we statically transform a procedure into a constraint system by using well-known "Static Single Assignment" form and control-dependencies. Second, we solve this system to check whether at least one feasible control flow path going through the selected point exists and to generate test data that correspond to one of these paths.The key point of our approach is to take advantage of current advances in constraint techniques when solving the generated constraint system. Global constraints are used in a preliminary step to detect some of the non feasible paths. Partial consistency techniques are employed to reduce the domains of possible values of the test data. A prototype implementation has been developped on a restricted subset of the C language. Advantages of our approach are illustrated on a non-trivial example.
Cited by 229 works. doi:10.1145/271771.271790 Open-access PDF
Authors
References
- Compilers: Principles, Techniques, and Tools
- Consistency in networks of relations
- The program dependence graph and its use in optimization
- Symbolic execution and program testing
- Efficiently computing static single assignment form and the control dependence graph
- A System to Generate Test Data and Symbolically Execute Programs
- SELECT—a formal system for testing and debugging programs by symbolic execution
- Constraint logic programming: a survey
- Automated software test data generation
- Constraint-based automatic test data generation