Research On Test Case Generation Based On Dynamic Symbolic Execution

Software testing is the main technical approach to improve the reliability, security and robustness of the software in the industry, and it is also a key part of the software engineering cycle. With the increasing of software size and importance of software in various application areas, the proportion of the budget for software testing in the software development cycle is also rising, reaching50%-80%. Therefore, how to improve the level of test automation and reduce test cost has become an important issue of concern in industry and academia. Automatic test case generation, as an important technology of automatic software testing, can significantly reduce the cost of software testing, shorten the software development cycle. However, there are still some problems about the technology of automatic test case generation. It is of great significance to research on how to resolve these problems.This paper focuses on the technology of test case generation based on dynamic symbolic execution. For the path combinatorial explosion problem and the inaccuracy of constraint solving in dynamic symbolic execution, the paper proposes a search strategy for exploring path space of programs and presents a novel algorithm to improve the process of solving non-linear arithmetic constraints in dynamic symbolic execution. Then a prototype tool is built based on both of these technologies. The main research content of the paper include:1) proposing a search strategy guided by uncovered branches, which calculates the approximate mathematic expectation of uncovered branches for each branch’s successors, then the expectation is used as a weight to guide the search process:covered branches are recorded during the process of dynamic symbolic execution, the branch weight is updated based on its successors’ coverage, the appropriate branch is select to make up the path condition; finally the test cases that could cover many branches is generated.2) proposing an algorithm to improve the process of solving non-linear arithmetic constraints in dynamic symbolic execution. By exploiting the similarity between the path constraints to solve in succession, the proposed approach makes the best of the last solution when solving the current non-linear arithmetic path constraint to avoid errors and reduce the time cost of solving non-linear constraints.3) implementing the prototype tool and evaluating the proposed strategy and algorithm. The proposed search strategy is compared with other strategies on three test benchmarks. The paper also evaluates the time cost of the proposed algorithm for improving the process of solving non-linear arithmetic constraints.The proposed strategy and algorithm improved the performance of the technology of test case generation based on dynamic symbolic execution. Experimental results show that compared to other search strategies the proposed strategy can significantly reduce the required test cases to cover the feasible branches, in the best case93%of the test cases can be reduced. The proposed algorithm for solving constraints can solve non-linear constraints in less time. Compared with the traditional dynamic symbolic execution tool, the proposed algorithm for solving non-linear arithmetic constraints can reduce about8%to18%of the solving time.