Research On Memory Modeling Based Automatic Test Data Generation Technique

Software testing plays an important role in the process of guaranteeing software quality and reliability. Structural testing is an important technique of software testing, and most sutructural testing method such as statement coverage, branch coverage, condition converage can be come down to Path-oriented test data generation. Test data generation is a key element of software testing, and automatic generation of it can greatly improve the efficiency of software testing. A number of different automatic test data generation methods for structural testing have been investigated, and these methods can be divided into three categories:static method based on symbolic execution, dynamic method based on concrete execution and dynamic symbolic execution, but most of them are aiming at numerical variables.Complex structure, string and array are fundamental data type in C programming language, and have wide usage in practical application. However, it is hard to automaticly generate complex structure, string and array test data for a path. Symbolic execution is the main technology of static test data generation method, but traditional symbolic execution is hardly to simulate semantic operation of these kinds of variables. Dynamic test data generation method based on concrete execution is hardly to construct suitable fitness functions of these variables.So we propose a static memory-modeling based automatic test data generation method, which can automaticly generate complex structural, string and array test data for the tested path.Creative works in this dissertation are mainly focused on the following aspects: (1) We present an abstract memory model which contains four abstract memory tables:PMTable used to describe numerical variable, STMTable used to describe structural variable, SRMTable used to describe string variable and ARMTable used to describe array variable. The abstract memory model can exactly record the state of complex structure, string and array variable on execution of the tested program.(2) We make an rule of the operation of complex structure, string and array variable on the abstract memory model:the operation of pointers pointing to complex structure and string can be simulated by the operation on the abstract memory model; commonly used string library function’s operation can be mapped to the operation on the abstract memory model; the operation of array elements with dynamic subscript can be mapped to the operation on the abstract memory model.(3) We present the test data generation algorithm for complex structure, string and array variable based on the abstract memory model. The semantic operation of the statement of complex structure, string and array variable is mapped to the operation of abstract memory on symbolic execution of the path, and the constraint of the path is recorded exactly in the abstract memory. And we present a two-step constraint solving method which is used to solve path constraints on string and array variable, we firstly solve the constraints on string length, the location of special constrained char element in string, array lengh and array dynamic subscript variable, then solve the path constraints on char element in string and array element with fixed location, and this method improve the efficiency of constraint solving and solve the dynamic array subscript problem.(4) We analyze the algorithm with instance and implement the algorithm in an automatic unit test tool called UATS, and the results of experiments prove that this method is feasible.