Research On Vulnerability Detection Techniques Of Binary Program Based On Program Analysis And Testing

With the development of information technology,software has become an important element of the world economy,culture,science&technology,education and military de-velopment.As one of the core infrastructures of information system,software is widely used in communication,finance,medicine,etc.However,with the increasing software function and the increasing scale,the software defects and security vulnerabilities are unavoidable,which brings serious threat to the reliability and security of the information system.In the military field,the information and communication system represented by C~4ISR is the nerve center of the modern army,which plays a vital role in winning the information war under modern conditions.The vulnerabilities,if mastered by the enemy,will cause incalculable damage in wartime.At present,many countries are competing to develop the field of cyberspace,the United States,Russia,Japan and other countries treat the cyberspace as the fifth dimension of war space after the land,sea,air and space.One of the key elements of cyberspace attack and defense is vulnerability,vulnerability detection and exploitation for both sides of offense and defense has important value,the appearance of the Stuxnet virus indicates that the software vulnerabilities have been applied to cyberspace operations.It is of great practical significance to study the techniques of vulnerability detection and discover the vulnerabilities in software.After many years of research,software vulnerability detection techniques have been put forward,such as static analysis,fuzzing test,symbolic execution and so on.But each technique has different advantages and disadvantages.The static analysis has high coverage and can detect many kinds of vulnerabilities,but its false positive rate is high.Fuzzing has low false positive rate but low code coverage and low efficiency,a large number of test cases may repeat the same program path.Symbolic execution is considered to be the most promising technique in vulnerability detection.The symbolic execution is path sensitive,so the false positive rate is low,and it can theoretically traverse all the paths of the program with constraint solver and once each path,the code coverage and execution efficiency is high,but the biggest problem that plagued symbolic execution is the path explosion problem.This thesis analyzes the main problems of current software vulnerability detection,and proposes a new framework of vulnerability detection technique targeting binary pro-gram,which uses the static analysis to locate suspected vulnerabilities and post-dynamic testing to verify the suspected vulnerabilities.The combination of program analysis and testing techniques can learn from each other and improve the efficiency of vulnerability detection.Based on the translation of the binary code to the intermediate code,the thesis locates the vulnerabilities on the intermediate code through the dataflow analysis and abstract interpretation,and then verifies the suspected vulnerabilities through program slicing,backward symbolic execution and guided fuzzing test.The main work and innovations are as follows:This thesis presents a method to exploit data flow analysis and abstract interpretation to locate the vulnerabilities in intermediate code.Based on LLVM IR,this thesis presents a method based on boundary-based vulnerability model,which exploits data flow analysis and abstraction to perform vulnerabilities location and screening,and the located vulnerabilities can direct the program slicing,symbolic execution and fuzzing test.With the translation from binary code to intermediate code,on the hand it avoids the direct analysis of the complexity of the binary assembly code,on the other hand it ensures the universality of the static analysis algorithm,that is,any platform code can be converted to intermedi-ate code and then use existing algorithms to analyze,to avoid re-design algorithm for each platform.Based on the theory of data flow analysis,this thesis studies the algorithm of detecting UAF and double free vulnerabilities.Based on the theory of abstract inter-pretation,this thesis studies the method of interval analysis of key variables of memory vulnerabilities.This thesis proposes a vulnerability-related intermediate code slicing method.In order to reduce the pressure of symbolic execution and follow-up fuzzing test,and improve the efficiency of vulnerability detection,this thesis studies the vulnerability-related program slicing technique,which slices backward on the intermediate code according to suspected vulnerabilities,deletes non-related codes regarding vulnerabilities.The slicing procedure can not only guarantee the normal execution of the program but also remove the redundant codes which are not related to the suspected vulnerabilities,thus reducing the path space and input space of the program under test to a certain extent,and alleviating the pressure of symbolic execution and fuzzing test.Experimental results show that the vulnerability-related program slicing can effectively reduce the code number of the pro-gram,while significantly improving the performance of symbolic execution in detecting suspected vulnerabilities.In this thesis,we present an algorithm for symbolic state merging in symbolic execution.To further alleviate the problem of path explosion in symbolic execution,the thesis analyzes the redundancy of the branches in the symbolic execution from the correspondence between input space and path space,and studies the local writing branches merging algorithm.By merging the writing branches states,the local redundant branches can be eliminated and the resource consumption caused by the path explosion is relieved to a certain extent.In this thesis,an example is given to illustrate the effectiveness of the writing branches merging algorithm.In this thesis,a backward symbolic execution method based on call graph is proposed.As a complement to the technique of forward symbolic execution,this thesis studies the backward symbolic execution method based on call graph,and avoids the unnecessary overhead caused by blind symbolic execution from program entry.According to sus-pected vulnerabilities located by the static analysis,backward symbolic execution based on the call graph starts from the function including suspected vulnerabilities,symbolicly executes backward along the function call graph toward the program entry point.Experimental results show that the backward symbolic execution method based on call graph can effectively alleviate the problem of path explosion in symbolic execution,and can find out if the suspected vulnerability is unreachable and eliminate false positives as soon as possible.This thesis presents a vulnerability-oriented fuzzing test method.Because the program size is too large,the function call graph is not complete and the constraint solving ability is limited,the reachability of the suspected vulnerabilities can not be verified by the symbolic execution and backward symbolic execution.For this reason,the thesis studies the method of verifying the reachability of the vulnerabilities using the guided fuzzing test,and proposes a vulnerability-oriented fuzzing test method.Vulnerability-oriented fuzzing test is different from the traditional code-coverage-oriented fuzzing test.Without having to test the entire code area,vulnerability-oriented fuzzing test conducts fuzzing test on the code area by instrument codes on the path to the suspected vulnerabilities and the code area of?the suspected vulnerabilities.Experimental results show that compared with code-coverage-oriented fuzzing test,vulnerability-oriented fuzzing test significantly improves the efficiency of vulnerability detection and can detect vulnerabilities that can not be found by code-coverage-oriented fuzzing test in the same amount of time.