The Research Of Path Exploring Strategy Of Dynamic Symbolic Execution

With the development of computer technology,significant fields such as economy,industry and military have witnessed a widespread application of software in them.Meanwhile,the demand for software security becomes more and more urgent as well.Dynamic symbol execution has received a wide concern as an effective software defect analysis technique,which helps significantly improve the security of the software by detecting software defects.As dynamic symbol execution continues expanding the coverage of the program path,the exploration space will also grow.Therefore,selecting an appropriate exploratory path under the given time budget directly affects the efficiency of the dynamic symbol implementation in finding software defects.At present,the major way used to deal with path explosion is heuristic path exploration strategy,which pays excessive concern about node coverage and fails to achieve a good defects mining effect.What's worse,the exploration strategy aiming at loops increases the computational complexity while solving the loop problem,and reduces the efficiency of dynamic symbolic execution.For the purpose of solving the above-mentioned problems,this paper compares and analyzes the widely used path exploration strategy of dynamic symbolic execution nowadays,designs a new path exploration strategy based on path tuple and a partial path exploration strategy for cyclic,and implements the CarFast Exploration strategies,Context-Guided exploration strategies,exploration strategies based on path tuples,and partial path-to-cycle exploration strategies.The four specific aspects of the work are as follows:1)This paper studies and analyzes the widely used dynamic symbolic execution path exploration strategies at present,as well as summarizes the primary methods,major models they use and the prior knowledge they rely on.It also summarizes the advantages and disadvantages of various path selection algorithms and provides support for the optimal design of path exploration strategies.2)This paper chooses the path tuple which contains both the path node information and the path topology information as the criterion and designs an exploration strategy based on it.Making the path tuple as the key to perform the coverage calculation for dynamic symbol execution helps not only fulfill the purpose of calculating the program coverage,but also achieve the comprehensive use of the program topology information to avoid the duplicate path and simplify the operation.Since security vulnerabilities are often associated with unexpected or incorrect state transitions,tuple-based exploration strategies also increase the likelihood of finding program vulnerabilities.3)Aiming at the problem of conditional judgment in the cycle,this paper puts forward the path exploration strategy of partial path execution.First,the loops are dynamically positioned by the path tuples in the program.Then,the loops in the dynamic symbol execution are processed by appropriate partial path execution method,which will reduce the possibility of path explosion and improve the efficiency of dynamic symbol execution.Since the partial path execution only changes the execution order of the paths,no additional calculations are performed,and the execution efficiency of the execution of the dynamic symbols is not reduced.4)This paper conducted research regarding the angr binary analysis platform,based on which the CarFast exploration strategy,Context-Guided exploration strategy,exploration strategy based on the path tuple and exploration strategy for the partial path of the loop are implemented on the angr platform.The LAVA-M test set is selected to compare the four kinds of path exploration strategies employed in this paper,meanwhile,related experimental results are analyzed and the next work is prospected.