THESIS
2015
xii, 76 pages : illustrations ; 30 cm
Abstract
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...[
Read more ]
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.
Post a Comment