Research On Test Case Generation Of Program Path Based On Polynomial Constraint Solving

As one of the basic processes of software engineering,software testing is an important method to assure the software quality.As part of the significant contents of software testing,the technology of automated test case generation can improve the accuracy and reduce the cost of testing,which has a tendency of wide application.Symbolic execution is a popular automated test case generation technique at present.However,symbolic execution based approaches are obviously limited by the constraint solver,which is difficult in processing non-linear constraints caused by the complexity and precision limitation.C language has been the most widely used programming language in the world.Therefore,it is of great value to generate test cases automatically of numerical programs written in C programming language.A test case generation approach based on polynomial constraint solving is proposed.Based on the approach,a test case automatic generation tool is developed for C language numerical program.The main contents of this thesis are as follows:? We study symbolic execution technique and extract path constraints based on KLEE-FP,a symbolic execution tool that supports C language and floating-point.Further,an approach to parse the path constraints and generate polynomial constraints is designed.? We research how to solve the polynomial constraints related to each path of C language program faster and more accurately.On the one hand,the approach to solve polynomial systems based on low-rank moment matrix completion is explored.For the complex polynomial systems of equations and inequalities,it is faster and more adaptable to large scale problems.On the other hand,the verification algorithm based on interval analysis is studied.In order to avoid the inaccuracy and exception of floating-point arithmetic,test cases are generated from the verified intervals that include accurate real roots.? We implement a tool called ATCase(Automatically generate Test Case),for analyzing the paths of C language numerical program and generating test cases that satisfy the path constraints.In summary,firstly we obtain polynomial constraints by extracting and parsing the program path constraints for a given C language numerical program based on symbolic execution,then compute the test cases which satisfy the constraints by the verification algorithm based on polynomial constraint solving.According to the process,we develop a tool ATCase and validate the efficiency and robust of ATCase by experiments.