Research On Methods Of Applying Fuzzing To Binary-programs Vulnerabilities Discovery

Program vulnerability is one of root causes of network security issue. How to find vulnerabilities existing in programs as quickly as possible is currently a popular research hotspot of network security field. Especially, research about how to find binary program vulnerabilities is now at the cutting edge of vulnerability research because of its wide applicability and its high difficulty. Now techniques that have been used to find program vulnerabilities include static program analysis technique, dynamic program analysis technique and penetration testing technique. Among these techniques, fuzz testing method which can be categorized into dynamic program analysis technique has become one of the most popular techniques used by security researchers and hackers because of its high cost-effective, which can be reflected in fuzzing’s simple idea and a large number of vulnerabilities found with fuzzing. However, traditional fuzz testing has two key problems:(1) producing low-quality test data, which is reflected by low test-depth and test-widen of the produced test data;(2) requiring lots of manual work in the stage of vulnerability confirmation.To the fuzzing’s data-producing problem, the dissertation reduces it to formula satisfiability problem of logical field and takes dynamic symbolic execution as the means of reduction. The dissertation introduces the basic theory of dynamic symbolic execution applied to test-data generation and dynamic taint analysis which is used as an important optimization measure of performance of dynamic symbolic execution. The basic theory includes introduction of symbol, symbolic evaluation, search strategy, SMT solver, taint analysis strategy and main difficult issues. The dissertation designs and implements an offline dynamic symbolic execution engine-DSEE based on the introduced theory. Firstly, DSEE translates the trace which mainly consists of assembly instructions to program in BIL language; Secondly, DSEE evaluates the BIL program symbolically. BIL statements which are translated from the original system-call frames and taint-introduction frames in the trace introduce the initial symbolic variables, symbolic evaluation is executed based on the operation semantics of BIL statements and BIL expressions, as a result, a path formula expressed in the form of BIL expressions is produced; Thirdly, the produced path formula is converted to SMT2format supported by Z3and solved to get a solution which will be taken as the next input to repeat preceding procedures, how to select the next input from the input sets depends on the improved generation search algorithm. Besides, the dissertation also designs and implements a trace logging engine with taint analysis-TLET. This includes the design of trace model which learns from the animation model, the design of an container which is used to serialize the trace and randomly read from the serialized trace, modeling of Linux system-call that will introduce taint and modeling of taint propagation rules which are data dependent. The dissertation did experiments to test and verify DSEE and TLET, and the result shows the two can meet the requirements. To the problem of vulnerability confirmation, the dissertation reduces generation of stack-overflow exploits to logical formula satisfiability problem and implements automatic confirmation of stack-overflow vulnerabilities and automatic generation of exploits of stack-overflow vulnerabilities.The main contributions of this dissertation includes:(1)design the offline dynamic symbolic execution engine-DSEE and the trace logging engine with taint analysis-TLET, which are verified by experiments. The two will be the foundational platform for continuing research of this field in future;(2) improve the generation search algorithm by adding a heuristic factor in the hope of making the searching process go forward in the direction of high code coverage rate as soon as possible;(3) take dynamic taint analysis and dead code elimination as the optimization measures of performance of dynamic symbolic execution and the results of experiments show the two measures can largely reduce the amount of BIL statements which need to be executed by symbolic execution. As a result, the size of produced path formula can be reduced largely;(4) reduce the generation of exploits of stack-overflow vulnerabilities to logical formula satisfiability problems and implements automatic generation of vulnerabilities of such kind.