Research And Implementation On Pipelined Symbolic Execution

With the rapid development of information technology,network attacks and malware become ever-growing.On the basis of vulnerabilities in software's coding and design,these attacks can be achieved.If we can dig out and fix these vulnerabilities early,security incident will be effectively curbed.In industry,fuzzing has been widely used to exploit vulnerabilities.However,it is not able to traverse all paths,affecting efficiency of vulnerability discovery.Therefore,researchers propose dynamic symbolic execution,which is with bright prospect in field of vulnerability discovery.Nevertheless,path explosion is still the main obstacle to its development.To alleviate memory pressure caused by exponential growth of path in dynamic symbolic execution,we firstly optimize the path exploration algorithm of dynamic symbolic execution engine —Angr.With the in-depth analysis of source code in Angr,this dissertation figures out an idea which improves path selection strategy in Angr.The idea selects one branch to execute instead of taking all active branches at same time.Then,this dissertation analyzes differences between branches' intermediate representation.Other branches are established by using the differences to replace state information of the selected one.Finally,other branches continue exploring path.This dissertation implements the algorithm on Angr and tests nine programs in detail.The experiments demonstrated that the algorithm reduces the number of path in dynamic symbolic execution,decreasing memory overhead.Next,we propose two kinds of piecewise parallel path exploration algorithms: partitioned parallel algorithms and pipelined algorithms.Path explosion in dynamic symbolic execution is mainly caused by the rapid growth of deep path.So if only one part of the program is explored at a time,it can greatly alleviate the path growth which is the result of a large number of branches.On the basis of this idea,the two algorithms both construct the segmentation standard on dominators and use target to drive path exploration.The difference is that the former completely avoids context of the part and mosaics adjoining parts later.However,the latter uses state information of previous part as input to the next part,avoiding overhead of path merging.Finally,the two path exploration algorithms are both implemented and tested in a dynamic symbolic execution engine.By means of comparing with another algorithm in time usage and memory consumption,the validity of the two algorithms are confirmed and the degree of performance boost are evaluated.