Compositional CLP-based Test Data Generation for Imperative Languages

June 15, 2010

José Miguel Rojas


Compositional CLP-based Test Data Generation for Imperative Languages

Time:   11:00am
Location:   Meeting room 302 (Mountain View), level 3

Glass-box test data generation (TDG) is the process of automatically generating test input data for a program by considering its internal structure. This is generally accomplished by performing symbolic execution of the program where the contents of variables are expressions rather than concrete values. The main idea in CLP-based TDG is to translate imperative programs into equivalent CLP ones and then rely on the standard evaluation mechanism of CLP to symbolically execute the imperative program. Performing symbolic execution on large programs becomes quickly expensive due to the large number and the size of paths that need to be explored. In this paper, we propose compositional reasoning in CLP-based TDG as a means of scaling up towards handling realistic programs. The idea in compositional TDG is that, when testing a method M which invokes P, the method is able to adapt test cases (given as preconditions on the input and postconditions in the output) available for P to the current context. Importantly, compositional reasoning also gives us a practical solution to handle native code, which may be unavailable or written in a different programming language. Namely, if P is a native method, we can model its behavior by means of test cases and compositional reasoning is able to use them. Both scaling techniques and handling native code are considered main challenges in the fields of symbolic execution and TDG.