| Nowadays,software vulnerability is positively concerned by both attackers and defenders being identified as a kind of strategic resource.Binary program analysis technology is an important method of vulnerability discovery by analyzing the structure,semantics and behavior of binary code to automatically discover the characteristics of programs.This dissertation focuses on the binary program analysis techniques related to vulnerability discovery,such as value set analysis,patch comparison and dynamic symbolic execution,etc.Aiming at the insufficient accuracy and high time consuming of these techniques,the corresponding optimization methods are proposed.The main research contents and innovations of this dissertation are as follows:1.A path-sensitive value set analysis refinement method aiming at the precision loss caused by unconditional state merging and ignoring path constraints in traditional value set analysis techniques is proposed.This method firstly separates the paths with identical variable dependencies into the same subsets using variable dependence analysis technology,then formulates the conditional merging strategy based on path division to merge the states whose paths belong to the same subset at the control-flow merge point,reducing the precision loss caused by unconditional state merging.Finally,this method introduces constraint solver to solve the path constraints of states,reducing the precision loss caused by ignoring path constraints.Compared with the value set analysis of angr,the false positive rate of vulnerability discovery of this method is reduced by 12.82%,and 25 undisclosed vulnerabilities are found in the Netgear router firmware,indicating that this method can effectively improve the precision of value set analysis.2.A non-structural difference patch analysis method based on value set analysis aiming at the problem that non-structural difference patch cannot be found by the mainstream structural patch comparison method is proposed.Considering the non-structural difference patch mainly leading to the change of function stack frame and constant value in the program,this method utilizes value set analysis technique to recover function stack frame,extracting the constants of function parameters and comparison operations.Then,the stack frame matching algorithm and constant matching algorithm are designed to find the non-structural difference patch.Compared with state-of-the-art binary diffing tools,the false negative rate of patch is reduced from 11.02% to 1.63% in the CGC dataset,and 20 1-day vulnerabilities that Bindiff could not detect are found in the Netgear router firmware,indicating that this method can effectively improve the precision of patch comparison.3.A symbolic emulation execution optimization method based on basic block summary aiming at the problem of repeated analysis of basic blocks in symbolic emulation execution is proposed.This method utilizes live variable analysis technique and symbolic expression pregeneration technique to obtain basic block summary information like live output variables of each basic block on the path,relationship between input and output variables,etc.Then the summary execution engine is built to implement the fast symbolic emulation execution according to the basic block summary information,avoiding the repeated analysis of basic block.Compared with the dynamic symbolic execution of angr,the speed of this method is increased by 45.35% in the CGC dataset,and 21 undisclosed vulnerabilities were found in the firmware of several wireless router devices,indicating that this method can effectively improve the efficiency of symbolic emulation execution.4.A constraint solving optimization method based on field inference aiming at the inefficiency of the constraint solving optimization methods with symbolic variable as granularity is proposed.This method firstly infers the finer-grained field information contained in symbolic variables,and then designs three constraint solving optimization techniques using field information: the first one is the field-level constraint independence optimization technique,which can discard field-independent constraints;the second one is the field-level concretization technique,which can simplify the overly complex constraints;the third one is the design of a simple constraint set solver,which can replace SMT solver to solve simple constraint set.Compared with the constraint solving of angr,the speed of this method is increased by75.01% in the CGC dataset,and 6 undisclosed vulnerabilities were found in the firmware of several wireless router devices,which indicates that this method can effectively improve the efficiency of constraint solving. |
PDF Full Text Request