Research on Parallel Symbolic Execution through Program Dependence Analysis

Through program dependence analysis, the method of parallel symbolic execution based on reduction about program execution path family was proposed. Firstly, instruction statements which affect on the symbolic value were extracted according to data dependency. then the key branch conditions controlling these statements were located and connected. Thus the reduction algorithm from multiple paths of which symbolic values are all the same to path families was was designed and implemented. Finally, path family chain was built and parallel symbolic execution was realized. the experimental results show that the method promotes parallel processing ability and test efficiency, compared with common parallel scheduling policy of allocating program execution path.

I. Introduction

At present, the symbolic execution^[1] in the field of vulnerability detection has been get increasingly widespread attention and application. Compared with fuzzing randomly to generat test cases, the target software is understood futher deeply, code coverage of software testing is significantly improved, and thus pertinence test cases are generated, through using symbolic execution. But the serious problem of the symbolic execution is that because of the software branch number and a huge number of cycles, there is the exponential growth of execution path, and the test coverage can be not effectively improved. It has become the biggest bottleneck of the application of symbolic execution.