A Systematic Review of Search Strategies in Dynamic Symbolic Execution

摘要

One of the major concerns of dynamic symbolic execution (DSE) based automated test case generation is its huge search space which restricts its usage for industrial-size program testing. In fact, DSE performs test case generation by exploring paths of the program, and the number of program paths is exponential in the number of branch conditions encountered during execution. Thus, by increasing the number of branches, the search space will be extremely large and without applying an effective and efficient technique to explore the search space, DSE would fail to achieve the predesignated goals in the given budget. To this end, different search strategies have been proposed to prioritize program paths and to select the most promising ones with respect to the testing goal. In this paper, we conduct a comprehensive systematic review of search strategies in DSE. We collect different techniques and methods concerning the topic, classify and summarize them, highlight their advantages and drawbacks, and provide a complete comparison of the methods in each category. The classification is carried out according to the type of search and also the information source exploited by the strategies to direct DSE. We also analyze the evaluation methodologies of experiments reported on this subject, give a general overview of them, perform a set of experiments and provide a set of guidelines for conducting future experiments in this area of research.