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:
- 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.