| Software testing is an important part of software engineering. In the software development process, the important role that software testing palys is now widely recognized. In general, the main task of software testing is proof, detection and prevention. According to a test criterion, it leads to the discovery of errors by measuring and evaluating the quality of software in order to improve the reliability of software.Nowadays most research has been focused on test generation for numeric data and string data. However, there are a few studies on test generation for programs with pointers and dynamic data structures. Besides, test data generation usually concerns using static approach to automatic program testing for programs in the presence of dynamic data structures. It is difficult to implement test generation for complex data structure and have a high efficiency of test generation.So, this paper proposes a concolic test generation approach for programs with binary tree structure as inputs, a widely used representative of dynamic data structure. The shape of binary tree structure is created using Genetic Algorithm, and simultaneously the values in the data fields are generated by means of the constraint solving. This paper proposes a chromosome representation of the shape with respect to binary tree structure, and actualizes a search algorithm for the shape generation arising from the constraints on the pointers along a given path. In the application of genetic operations, this paper adopts some strategies to generate the new shapes of binary tree structures to ensure that this process would not destroy the shape feature of binary tree structure. While the shapes of binary tree structure are improved and optimized, appropriate numerical values in the data fields of a given binary tree structure are generated by constraint solving technique to obtain an input that makes the target path executed.The experimental results show that the proposed method is promising and effective, and it not only can generate test data for programs with binary tree structure as inputs but also is obviously superior to the random method on the test generation performance. |
