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