Automated test data generation using iterative relaxation methods

This dissertation addresses the problem of automated test data generation for commonly used coverage based criteria. A new program execution based approach to automated test data generation using iterative relaxation methods has been developed. In this approach, test data generation is initiated with an arbitrarily chosen input, which is iteratively refined using a relaxation technique to generate the desired input. New algorithms to generate test data for statement, branch, data flow and path coverage have been developed. They are general in their applicability as they can generate test data for programs with branch predicates that compute linear and nonlinear functions of input. They can detect linear infeasible paths and can handle programs using arrays, records, pointers and loops. A new code transformation method to handle test data generation for functions with pointer inputs has been developed. A new method called Unified Numerical Approach has also been developed to compute a real and an integer feasible solution of a set of linear constraints. It enables the test data generation algorithms developed in this dissertation to handle programs that have both integer and floating point inputs. The experimental evaluation reveals that these methods automatically generated test data that covers a large percentage of coverage elements. The average time taken to generate a test case was of the order of a few seconds. The experiments also revealed their power in detecting infeasible linear paths as well as in indicating potentially infeasible nonlinear paths