paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Greybox Fuzzing for Concurrency Testing

并发测试的灰盒模糊测试
ASPLOS Proceedings of the 29th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 22024匹配度 2/10 · 该论文研究并发测试中的灰盒模糊方法,属于程序分析与测试领域,但未涉及用户核心关注的静态分析、LLM/Agent、浮点程序分析或贝叶斯程序分析,也不属于PL与AI交叉方向。引用 19 inbox
Dylan Wolff, Zheng Shi, Gregory J. Duck, Umang Mathur, Abhik Roychoudhury
crossref: 2026-09-12dblp: 2026-09-12

AI 速览

一句话:提出利用 reads-from 关系引导偏置随机搜索的并发测试灰盒模糊方法,高效发现并发缺陷。

并发程序的线程交错空间呈指数级增长,传统并发测试要么依赖随机采样交错(乐观式),要么依赖对约简或有界搜索空间的系统探索(悲观式),均存在局限。本文提出一种务实的折中方案:采用偏置随机搜索,将探索导向更可能暴露新行为的邻域,其思想类似在顺序程序中发现缺陷效果显著的灰盒模糊测试。为在交错域中识别新行为,作者利用 reads-from 关系对搜索空间进行剪枝与导航。在广泛使用的并发数据集上的实验表明,该方法在单位调度执行下发现缺陷的效率显著优于现有最先进的并发测试工具,并且相较随机基线调度算法能更均匀地探索调度空间,带来严格改进。作者还开源了并发测试基础设施 RFF,以支持后续研究与社区使用。

问题
并发程序的线程交错搜索空间巨大,现有并发测试方法或依赖随机采样交错,或依赖有界系统探索,难以在有限调度内高效发现缺陷。
方法
将灰盒模糊测试思想引入并发测试,利用 reads-from 关系剪枝并导航交错搜索空间,通过偏置随机搜索引导探索更可能暴露新行为的调度邻域。
评估
在广泛使用的并发数据集上,与现有最先进并发测试工具及随机基线调度算法比较,评估单位调度执行发现缺陷的效率与调度空间探索的均匀性。
原文摘要(Abstract)

Uncovering bugs in concurrent programs is a challenging problem owing to the exponentially large search space of thread interleavings. Past approaches towards concurrency testing are either optimistic --- relying on random sampling of these interleavings --- or pessimistic --- relying on systematic exploration of a reduced (bounded) search space. In this work, we suggest a fresh, pragmatic solution neither focused only on formal, systematic testing, nor solely on unguided sampling or stress-testing approaches. We employ a biased random search which guides exploration towards neighborhoods which will likely expose new behavior. As such it is thematically similar to greybox fuzz testing, which has proven to be an effective technique for finding bugs in sequential programs. To identify new behaviors in the domain of interleavings, we prune and navigate the search space using the "reads-from" relation. Our approach is significantly more efficient at finding bugs per schedule exercised than other state-of-the art concurrency testing tools and approaches. Experiments on widely used concurrency datasets also show that our greybox fuzzing inspired approach gives a strict improvement over a randomized baseline scheduling algorithm in practice via a more uniform exploration of the schedule space. We make our concurrency testing infrastructure "Reads-From Fuzzer" (RFF) available for experimentation and usage by the wider community to aid future research.

链接与引用

DOI 原文 · PDF(开放获取) · DBLP

BibTeX
@inproceedings{WolffSD0R24,
  title = {Greybox Fuzzing for Concurrency Testing},
  author = {Dylan Wolff and Zheng Shi and Gregory J. Duck and Umang Mathur and Abhik Roychoudhury},
  booktitle = {ASPLOS},
  year = {2024},
  doi = {10.1145/3620665.3640389}
}