Research On Source Code Vulnerability Mining Based On Hybrid Symbolic Execution And Genetic Algorithm

The Internet has brought so much convenience to our daily life, while it is accompanied by a variety of viruses, network attacks and other security issues at the same time. According to the data from relevant security department, it shows that 75% of the hacker attacks occur in the application layer. The main means of the hacker attack is using a variety of loopholes of the system to penetrate, and the statistics data of NIST shows that 92% of the vulnerabilities happened in the application layer rather than the network layer. In order to enable people to use the Internet safely and relieved, the security maintaining of network application softwares becomes the core issue of network security.Vulnerability mining technology is the important technology to solve the security of application software. According to the different test objects, it can be divided into the source code vulnerability mining technology and the binary code vulnerability mining technology. In recent years, the software vulnerability mining technology research has made remarkable progress. While relating to so many techniques such as the dynamic tracing, symbolic execution, path constraints collection and problem solving and there are still many problems, which mainly including: the path explosion problem, constraint solving problem and testing efficiency. Firstly, the path explosion problem is due to in the implementation process of symbols, the code execution path will generate the corresponding path constraints. If the software is too larger or a large number of cyclic operations occur, it may result in huge path constraints and even explosive growth appears; Secondly, the symbolic execution process will generate a lot of constraint conditions, if there are a large number of symbols or existence of nonlinear constraints, the solver will not be able to solve; Finally, testing efficiency problem. In the process of symbolic execution, program instruction execution process is needed to monitor dynamically. The sign value will be introduced and generate symbolic constraints and solving. When the software, instruction count and the number of symbols are very large, testing efficiency will be relatively low. According to the security of network application software and the nonlinear constraints solving problems in vulnerability mining technology, this thesis focuses on the source code vulnerability mining technology based on mixed symbol execution and genetic algorithm:1. The thesis gives an overview of the key technology of hybrid symbolic execution, system framework and applications in automated testing for software security. We introduce the symbolic execution techniques of the software security testing tools Klee, the realization, llvm framework, memory model and constraint solvers of KLEE.2. The traditional genetic algorithm is improved to solve the problem that the KLEE is unable to solve the nonlinear constraint condition. The genetic algorithm is improved from three aspects: encoding mode, fitness function and Newton iteration termination condition. The accuracy and convergence rate of the solution of nonlinear constraint conditions are improved.3.The improved genetic algorithm is introduced to solve the nonlinear constraint conditions of STP solver and improved genetic algorithm in KLEE. Design of the genetic algorithm for solving module, realizes to solve the interface module of the genetic algorithm, the parallel solving module in KLEE, and KQuery abstract analytic layer. And we eventually use KLEE to call parallel computation module to generate test cases.4.In view of the feasibility of the improved KLEE in the solving of nonlinear constraint condition, the experimental verification is carried out on the LLVM framework in Linux system. The llvm framework is builded, and KLEE used upon the llvm framework to test programs which containing nonlinear constraints. Based on genetic algorithm and hybrid symbolic execution, the improved KLEE is used to call parallel computation module to solve the nonlinear constraints. And coverage path is obtained and the test cases is generated automatically.The experimental results demonstrate that the improved KLEE can solve the nonlinear constraint condition of the original KLEE, and generate the test case which can cover the path of the nonlinear constraint condition. At last, the application of the improved KLEE in memory leak detection is realized.