Random or heuristic? An empirical study on path search strategies for test generation in KLEE
Random or heuristic? An empirical study on path search strategies for test generation in KLEE
复制标题
随机还是启发式？
DOI：
10.1016/j.jss.2022.111269
复制
发表时间：
2022-02
影响因子：
3.5
通讯作者：
Zhiqiu Huang
中科院分区：
文献类型：
--
作者：
Zhiyi Zhang;Ziyuan Wang;Fan Yang;Jiahao Wei;Yuqian Zhou;Zhiqiu Huang
随机性可能是最直接的策略，并且在软件工程中被广泛使用。对随机策略的一个批评是它的任务目标不明确。因此，人们提出了许多启发式策略来改进随机策略。然而，无法从理论上证明启发式比随机性更好，特别是对于软件测试生成。这个开放性的问题总是留给实证研究，研究者期望在实践中总结出一些指导方针。本文研究了测试生成的关键技术——路径搜索策略。我们对KLEE提供的10种具体路径搜索方法进行了实证评估和比较，其中2种方法属于随机搜索策略，8种方法属于启发式搜索策略，53个GNU coretils应用程序。我们还研究了使用和不使用约束优化技术生成基于klei的测试的两种情况。实验结果表明，在没有优化的情况下，随机策略中的一种方法——random-path——在完成路径的数量、语句覆盖率和分支覆盖率方面比其他技术表现得更好。这些结果表明，在大多数情况下，随机策略可以更好地用于测试生成，而启发式策略需要进一步研究。然而，当与优化相结合时，搜索策略的选择取决于所应用的具体优化。我们进一步分析了统计结果背后的原因，并提供了在实践中选择合适的路径搜索策略进行测试生成的指南。
Randomness may be the most straightforward strategy and has been widely used in software engineering. One criticism for random strategy is its aimless for tasks. Therefore, many heuristic strategies have been proposed to improve the random strategy. However, it is impossible to prove that heuristics are better than randomness in theory, especial for software test generation. This open question is always left to empirical study and researchers expect to conclude some guidelines in practice. This paper studies a key technique, path search strategies, of test generation. We conducted an empirical evaluation and comparison among ten concrete path search approaches provided by KLEE, where two approaches belong to random search strategy and eight belong to heuristic search strategy, with 53 GNU Coreutils applications. We also investigated both cases with and without constraint optimization techniques for KLEE-based test generation. The experimental results show that without optimization, one approach from random strategy –random-path– performs better than other techniques in terms of the number of completed paths, statement coverage and branch coverage. These results indicate that random strategy can be a better choice for test generation in most cases without optimization, and heuristic strategies need further investigation. However, when combined with optimization, the selection of search strategy depends on the specific optimization applied. We further analyze the reasons behind the statistical results and provide guidelines to select the appropriate path search strategy for test generation in practice.
登录
查看更多内容
DOI：
10.1145/3243176.3243207
发表时间：
2018-11
期刊：
Proceedings of the 27th International Conference on Parallel Architectures and Compilation Techniques
影响因子：
--
作者：
Wei Zhang;Houjun Tang;S. Byna;Yong Chen
通讯作者：
Wei Zhang;Houjun Tang;S. Byna;Yong Chen
DOI：
10.1016/j.future.2012.02.006
发表时间：
2013-09-01
影响因子：
7.5
作者：
Chen, Ting;Zhang, Xiao-song;Wu, Yue
通讯作者：
Wu, Yue
影响因子：
7.3
作者：
David Brumley;J. Newsome;D. Song;Hao Wang;S. Jha
通讯作者：
David Brumley;J. Newsome;D. Song;Hao Wang;S. Jha
DOI：
10.1016/j.infsof.2018.11.006
发表时间：
2019-03
期刊：
Inf. Softw. Technol.
影响因子：
--
作者：
A. Sabbaghi;H. Kanan;M. Keyvanpour
通讯作者：
A. Sabbaghi;H. Kanan;M. Keyvanpour
影响因子：
7.4
作者：
Hyunsook Do;G. Rothermel
通讯作者：
Hyunsook Do;G. Rothermel