Automatic Unit Test Data Generation Using Mixed-Integer Linear Programming and Execution Trees

This paper presents an approach to automatic unit test data generation for branch coverage using mixed-integer linear programming. execution trees, and symbolic execution. This approach can be useful to both general testing and regression testing after software maintenance and reengineering activities. Several strategies, including original algorithms, to move towards practical test data generation have been investigated in this paper. Methods include: the analysis of minimum path-length partial execution trees for unconstrained arcs, thus increasing the generation performance and reducing the difficulties originated by infeasible paths; the reduction of the difficulties originated by non-linear path conditions by considering alternative linear paths; the reduction of the number of test cases, which are needed to achieve the desired coverage, based on the concept of unconstrained arcs in a control flow graph; the extension of symbolic execution to deal with dynamic memory allocation and deallocation, pointers and pointers to functions. Execution trees are symbolically executed to produce Extended Path Constraints (EPC), which are then partially mapped by an original algorithm into linear problems whose solutions correspond to the test data to be used as input to cover program branches. Partially mapping this problem into a linear optimization problem avoids infeasible and non-linear path problems, if a feasible linear alternate path exists in the same execution tree. The presented approach has been implemented in C++ and tested on C-language programs on a Pentium/Linux system. Preliminary results are encouraging and show that a high percentage of the program branches can be covered by the test data automatically produced. The approach is flexible to branch selection criteria coming from general testing as well as regression testing