Scalable automated test generation using coverage guidance and random search

摘要

Dynamic symbolic execution has been shown to be an effective technique for automated test input generation. When applied to large-scale programs, its scalability however is limited due to the combinatorial explosion of the path space and the high cost of computation. Several sophisticated search strategies have been proposed to better guide dynamic symbolic execution towards achieving high code coverage. While confirmed effective, these techniques may deteriorate in practical situations because of the large computation cost involved. In this paper, we propose a search heuristic which is directed by coverage information and interleaved with random search to perform dynamic symbolic execution for coverage improvements and cost-effectiveness. We conducted two evaluations to evaluate the effectiveness of our proposed approach and to study the impact of computation costs on its practical capabilities.