一句话：提出节点中心视角，以线性时间最优算法选取最少基本块进行插桩，大幅降低路径覆盖追踪开销并提升 fuzzing 漏洞检测效率。
路径覆盖追踪支撑测试、调试等动态分析，但插桩带来高运行时开销；最小化插桩点为 NP-hard，现有边中心方法在精度与效率间权衡。本文提出节点中心视角：寻找能区分所有边与路径的最少基本块，而非最少边。洞见是只需在未区分路径汇聚的块处区分，由此得到对任意控制流图线性时间、可证正确且最优的算法，并实现为 InsOpt。在 Magma 上，InsOpt 仅插桩 17% 基本块，插桩量减少 2.8 倍，获 1.6 倍加速和 2.4 倍开销降低；与 AFL++ 集成后漏洞检测加速 5.0 倍、性能提升 1.5 倍，并发现 5 个未知漏洞。
Path coverage tracing is one of the fundamental components for supporting a wide range of dynamic program analyses, such as testing, debugging, profiling, and many others. Since one needs to insert code into a program to trace its coverage, runtime overhead becomes the main bottleneck for scalability. As finding the minimum number of instrumentation points is NP-hard, extensive work has focused on reducing the number of instrumented edges under diverse assumptions, and thus suffers from the trade-off between precision and efficiency. Departing from this edge-centric view, we introduce, in this work, a novel perspective, namely the node-centric view, where we aim to find the minimum number of blocks, rather than edges as in existing work, that can differentiate all edges and paths in the program. This new perspective allows us to design a linear-time algorithm that is provably correct and optimal—it finds the minimum set of blocks for correctly differentiating edge/path coverage for arbitrary control-flow graphs. Our key insight is that optimal node-level instrumentation only needs to distinguish undifferentiated paths at the block where they converge, enabling our algorithm to have linear-time complexity regarding the number of basic blocks. We implement our algorithm as InsOpt and compare it against state-of-the-art edge-coverage instru- mentation techniques on the real-world vulnerability-detection benchmark, Magma. Our evaluation results demonstrate significant improvements: InsOpt needs 2.8x less instrumentation with only 17% basic blocks instrumented. This reduced instrumentation yields a 1.6x speedup and a substantial 2.4x reduction in runtime overhead. Moreover, we also demonstrate substantial potential for InsOpt across other applications. Specifically, our integration of InsOpt with AFL++, a state-of-the-art fuzzer, shows a 5.0x speedup in vulnerability detection and a 1.5x performance improvement. Notably, this efficiency gain further benefits InsOpt in detecting five previously unknown bugs in frequently evaluated projects by other state-of-the-art tools.
@article{paperbot12134,
title = {Revisiting Path Coverage Tracing from a Node-Centric View},
author = {Heqing Huang and Zhendong Su},
journal = {Proceedings of the ACM on Programming Languages},
volume = {10},
number = {OOPSLA2},
year = {2026},
doi = {10.1145/3839464}
}