一句话：提出兼容分支覆盖驱动的符号执行，利用程序依赖分析剪枝冗余路径，加速缺陷发现。
符号执行能通过生成测试输入系统地探索可行路径来发现缺陷，但路径爆炸限制其实际应用。本文提出兼容分支覆盖驱动的符号执行，基于程序依赖分析构造兼容分支集，并据此引导符号执行探索可行分支，同时可靠地剪除对分支覆盖无新贡献的冗余路径。作者在 KLEE 上实现原型，并在 Siemens Suite、GNU Coreutils 及真实程序上评估。实验表明，与先进符号执行技术相比，该方法在取得相同或更高分支覆盖的同时，显著减少复现缺陷所需时间；在 GNU Coreutils 上平均减少超过 45% 路径并取得约 3 倍加速。
Symbolic execution is a powerful technique for bug finding by generating test inputs to systematically explore all feasible paths within a given threshold. However, its practical usage is often limited by the path explosion problem. In this paper, we propose compatible branch coverage driven symbolic execution for efficient bug finding. Our new technique owns a novel path-pruning strategy obtained from program dependency analysis to effectively avoid unnecessary explorations. Specifically, based on a Compatible Branch Set , our technique directs symbolic execution to explore feasible branches while soundly pruning redundant paths that have no new contributions to branch coverage. We have implemented our approach atop KLEE and conducted experiments on a set of programs from Siemens Suite, GNU Coreutils, and other real-world programs. Experimental results show that, compared with the state-of-the-art symbolic execution techniques, our approach always uses significantly less time to reproduce bugs while achieving the same or better branch coverage. On average, our approach got over 45% path reduction and 3x speedup on the GNU Coreutils programs
@article{YiYY24,
title = {Compatible Branch Coverage Driven Symbolic Execution for Efficient Bug Finding},
author = {Qiuping Yi and Yifan Yu and Guowei Yang},
journal = {Proceedings of the ACM on Programming Languages},
volume = {8},
number = {PLDI},
year = {2024},
doi = {10.1145/3656443}
}