The Design Of Performance Optimization For Dynamic Symbolic Execution

With the rapid development of computer sciences, the quality of software hasbecome a focus of research. It is important for a software vulnerability detectiontechnology to be able to accurately and comprehensively detect all the potentialvulnerabilities. Traditional static testing approaches fall far short of what is requirednow. Automate fuzz test is a popular weapon in the ongoing fight against softwaresecurity exploitation. But its inherent defects cannot satisfy the effective andcomprehensive testing requirements. Symbolic execution technology has been proposedas early as the70s, and that has found renewed interested in recent years. Dynamicsymbolic execution, short for DSE, is now the underling technique of several populartesting tools, which can automatically generating testcases that achieve high codecoverage of program executions.Dynamic symbolic execution still suffers from scalability issues due to the pathexplosion. Systematically execute all feasible program paths when testing largeapplications with hundreds of millions of instructions is still problematic within alimited search period. Although there are a series of solutions be put forward, such aspruning redundant paths, heuristics research and others, the challenge is still existed.In this thesis, through the further study of symbolic execution and path explosion, anovel path selection algorithm, called dominator algorithm, is proposed to improvingthe code coverage and execution performance. This algorithm depends on a globalsuperblock dominator graph, which is transformed from the control flow graph and thefunctions call relationship graph of the under test program based on the theory ofdomination. With the dominator algorithm to drive new path selection, the DSE tool canmaximize the number of new covered code each execution. In addition, a DSEprototype system, called DDse, was build under Linux OS to validate the new algorithm.DDse select Valgrind as instrumentation tool and Stp as constraints solver, and six pathselection methods include dominator algorithm are implement in. Severalmiddle-to-large sized open source applications under Linux system are tested, throughthe tests and the analysis result proved that the dominator algorithm has realized the proposed target that effectively improved the performance of DSE system.