Dynamic Symbolic Execution With Segmented Analysis

Dynamic symbolic execution (DSE) is a testing approach which combines symbolic execution and concrete execution. With the development of computer applications, the structure of software systems becomes more and more complex. As long as the complexity of the system under testing increases, the dynamic symbolic execution encounters a bottleneck in its development. As a result, the coverage rate is difficult to be improved, which affects the integrity completeness of test data and therefore affect the quality and safety of software. Path explosion and the limitation of complex path conditions on the symbolic constraint solvers are two classic problems in affecting dynamic symbolic execution moving on. On one hand, the path explosion refers to the case that the huge number of programs paths in all but the smallest programs, which is usually exponential in the number of static branches in the code. The path explosion caused by loop not only increases the memory cost, but also generate test cases which do not contribute to the coverage rate of the system under testing. On the other hand, the complex path conditions may exceed the solving capability of constraint solver, which may lead to the suspension of testing processes and affect the effectiveness of test.This paper aims to relieve the above two problems in terms of the segmented analysis approach. In general, the idea of this paper is to enable the uncovered segment tested by traditional dynamic symbolic execution, divided into a number of dependent executable segments. We will give a regression analysis of these dependent executable segments to get substitution functions, which can generate valid testing cases by the deepening of testing process. At the same time, considering the effectiveness problem caused by regression deviation, this paper considers to analyze the coverage of the generated test cases over the original program, and give the segmented analysis of the uncovered segment in the former round due to the analysis results. After several times of iteration, with the deepening of testing process, the limitation of dynamic symbolic execution in dealing path explosion and complex path condition can be alleviated.In order to verify the validity of proposed method, this paper provides an iterative model for segmented dynamic symbolic execution and implements a prototype framework KCOV based on KLEE which is a traditional dynamic symbolic execution tool. Moreover, we have given a test on a number of widely used open source programs. The experimental results show that the test cases generated by the proposed method in this paper can execute more program paths and improve the branch coverage rate of the tested program.