Research On Key Technology For Automatic Discovery And Verification Of Software Vulnerabilities

The characteristics of modern software,such as large scale,complex structure and diverse functions,lead to the inevitable existence of software vulnerabilities,posing a serious threat to software-centric information system security,and directly affecting national strategic security as well as personal privacy and property security.Quickly discover vulnerabilities in software and verify their exploitability can help to identify security flaws in information systems and protect against them as early as possible.Therefore,it is of great practical significance and academic value to study how to automate the discovery and verification of undisclosed vulnerabilities in software.The thesis investigates key techniques for the software vulnerability automatic discovery and verification.It is well known that current research techniques suffers from many problems.For software vulnerability discovery,the existing methods can only excavate the vulnerabilities located in the shallow state space,and it is difficult to test the deeper state space.For software vulnerability verification,the existing methods only support the vulnerability that can be exploited directly by single step,it is difficult to automate the processing of complex vulnerabilities.Therefore,the thesis takes the mainstream symbolic execution,the fuzz testing as the technical support,has carried on the thorough research to how to improve the vulnerability discovery efficiency and how to expand the verification ability for complex vulnerabilities.The main work and innovation of the thesis are as follows:1.An intelligent fuzzing method for open-sourced software vulnerability discovery is proposed.Firstly,this method dynamically collects the program runtime information by DBI,and realizes the fine-grained analysis of conditional branch coverage in the program.Then,for the conditional branch of semi-covered,the paper proposes a key field detection method based on operand aware analysis,and filters out the input fields related to branch constraints with less overhead.Finally,the paper transforms the breakthrough problem of the semi-covered branch into an optimization problem,and carries on the global optimal search in the reduced space,which can quickly penetrate over the complex conditional branch.Compared with the traditional coverage feedback fuzzing,our method can effectively improve the coverage of the target program and explore the vulnerabilities located in the deep state space.2.An improved hybrid testing method based on symbolic execution and fuzz testing is proposed.Aiming at the problem of state explosion caused by the execution of symbolic pointer and symbolic loop,the paper adopts the symbolic pointer model based on lazy forking and the symbolic cyclic boundary control method based on bucket to ensure the exploration of the virgin state space to the maximum extent while avoiding the excessive redundancy state.Aiming at the problem that the non-priority of fuzzing seed queue leads to the inefficiency of invoking symbolic execution,this paper proposes a method of seed file priority based on distance,and by calculating the relative distance of seed file in state space,the seed which is more likely to trigger the new path coverage is scheduled with higher priority.This ensures that symbolic execution within a limited test time can assist in generating more valid test cases.Compared with the existing bybrid test tools and other vulnerability dicovery tools,our method can effectively improve the path coverage and excavate more software vulnerabilities.3.A heap vulnerability exploitation pattern construction method based on state migration combination is proposed.The description method of the existing vulnerability exploitation process can only depict the simple,single-step vulnerability exploitation process,and cannot meet the requirements of the heap vulnerability exploitation process that contains multiple intermediate state transitions.Firstly,the paper uses the first-order predicate formula to express the properties,data relationship and structure replationship of highly structured memory objects,which supports the accurate analysis of the memory space layout of the intermediate steps.Then,on the basis of in-depth analysis of the typical manual exploitation heap vulnerability process,the key steps of the exploitation method are refined,and the description method of heap vulnerability exploitation based on state migration combination is studied.Finally,taking the typical heap vulnerability exploitation methods as examples,this paper introduces how to form a vulnerability exploitation model that can guide the exploitation code generation.4.An exploitation pattern directed automatic verification method of heap vulnerabilities is proposed.The paper first models typical memory operations as five primitives,i.e.,read,write,allocation,free,and execute.Then,aiming at the state migration in the process of vulnerability exploitation,the paper proposes a random searching method to generate possible migration paths betweern states.Then,the paper presents an automatic migration path driving method based on directed fuzz testing.Finally,the paper designs and implements a prototype system which can be used for the automatic generation of heap vulnerability,and the experimental results show that the system can automate the use of code generation for a variety of vulnerability exploitation methods,and support the dynamic expansion of more exploitation methods.