Achieving High Branch Coverage with Fewer Paths

Symbolic execution based test generation has made progress in recent years. However, in order to scale to larger programs there are some issues to be solved. Among them, generating a set of feasible paths to achieve high coverage gets more attention. In this paper, we focus on how to increase covering efficiency while maintaining high coverage. To achieve high branch coverage efficiently, we propose a path generation approach DYNASTY. A heuristic search strategy based on branch residual is used to guide branch selection. To avoid repetitive path exploration, a data structure named path trie is introduced to store paths generated. We have implemented our approach and conducted primary experiments. Our approach achieves high branch coverage quickly on the subjects.