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

Abstract

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:

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.