Context and Precondition-Guided Search strategies in dynamic symbolic execution

Dynamic symbolic execution (DSE) or concolic testing is an automatic test input generation technique based on symbolic execution. Due to its low false positives and high branch coverage, DSE has received much interest both in industry and academia. However, one of the biggest challenges in DSE is path explosion. The number of execution paths increases exponentially to the number of branches in a program and exploring all paths with DSE becomes infeasible even for a medium sized program. To efficiently explore the search space of DSE, we present two search strategies. The Context Guided-Search (CGS) strategy aims to quickly achieve high branch coverage. The key idea behind CGS is to focus on exploring diverse states of the program by first selecting branches in a new context. We use dominator information to exclude irrelevant branches from the context information and incrementally increase the consideration level of the context. On the other hand, the Precondition Guided-Search strategy aims to generate input to cover a specific target branch. The PGS strategy calculates preconditions for not reaching the target branch from previous execution paths which failed to reach the target branch. The PGS strategy builds the preconditions in a bottom-up manner with incremental merge and uses the preconditions to reduce the search space. The evaluation results show that the CGS strategy can cover more branches than other search strategies on various subjects and the PGS strategy can cover the target branch which can not be covered easily by other strategies.