Canary: practical static detection of inter-thread value-flow bugs
Yuandao Cai, Peisen Yao, Charles Zhang
Abstract
Concurrent programs are still prone to bugs arising from the subtle interleavings of threads. Traditional static analysis for concurrent programs, such as data-flow analysis and symbolic execution, has to explicitly explore redundant control states, leading to prohibitive computational complexity.
This paper presents a value-flow analysis framework for concurrent programs called Canary that is practical to statically find diversified inter-thread value-flow bugs. Our work is the first to convert the concurrency bug detection to a source-sink reachability problem, effectively reducing redundant thread interleavings. Specifically, we propose a scalable thread-modular algorithm to capture data and interference dependence in a value-flow graph. The relevant edges of value flows are annotated with execution constraints as guards to describe the conditions of value flows. Canary then traverses the graph to detect concurrency defects via tracking the source-sink properties and solving the aggregated guards of value flows with an SMT solver to decide the realizability of interleaving executions. Experiments show that Canary is precise, scalable, and practical, detecting over eighteen previously unknown concurrency bugs in large, widely-used software systems with low false positives.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
13 top-tier papers have cited it since. Know what they found before your reviewers do.
Lune can draw on
the full paper · the top-tier papers that cite it · related work
Free to start. No credit card required.
Lineage
- Controlled Concurrency Testing via Periodical Scheduling cites Razzer: Finding Kernel Race Bugs through Fuzzing
- Controlled Concurrency Testing via Periodical Scheduling cites Krace: Data Race Fuzzing for Kernel File Systems
- Controlled Concurrency Testing via Periodical Scheduling cites MUZZ: Thread-aware Grey-box Fuzzing for Effective Bug Hunting in Multithreaded Programs
- Krace: Data Race Fuzzing for Kernel File Systems cites Razzer: Finding Kernel Race Bugs through Fuzzing
- SmartTrack: efficient predictive race detection cites Fast, sound, and effectively complete dynamic race prediction
- Unleashing the Power of Type-Based Call Graph Construction by Using Regional Pointer Information cites Krace: Data Race Fuzzing for Kernel File Systems
- Unleashing the Power of Type-Based Call Graph Construction by Using Regional Pointer Information cites Peahen: fast and precise static deadlock detection via context reduction
- Unleashing the Power of Type-Based Call Graph Construction by Using Regional Pointer Information cites MUZZ: Thread-aware Grey-box Fuzzing for Effective Bug Hunting in Multithreaded Programs
- Peahen: fast and precise static deadlock detection via context reduction cites Razzer: Finding Kernel Race Bugs through Fuzzing
- Peahen: fast and precise static deadlock detection via context reduction cites Controlled Concurrency Testing via Periodical Scheduling
- Peahen: fast and precise static deadlock detection via context reduction cites Krace: Data Race Fuzzing for Kernel File Systems
- Peahen: fast and precise static deadlock detection via context reduction cites SmartTrack: efficient predictive race detection
- Peahen: fast and precise static deadlock detection via context reduction cites MUZZ: Thread-aware Grey-box Fuzzing for Effective Bug Hunting in Multithreaded Programs
- MUZZ: Thread-aware Grey-box Fuzzing for Effective Bug Hunting in Multithreaded Programs cites Razzer: Finding Kernel Race Bugs through Fuzzing
- Plankton: Reconciling Binary Code and Debug Information cites Unleashing the Power of Type-Based Call Graph Construction by Using Regional Pointer Information
- Plankton: Reconciling Binary Code and Debug Information cites Peahen: fast and precise static deadlock detection via context reduction
Cited by top-tier papers13
- Context Sensitivity without Contexts: A Cut-Shortcut Approach to Fast and Precise Pointer AnalysisWenjie Ma, Shengyuan Yang, Tian Tan, Xiaoxing Ma et al.PLDI 2023 · 29 citations
- Controlled Concurrency Testing via Periodical SchedulingCheng Wen, Mengda He, Bohao Wu, Zhiwu Xu et al.ICSE 2022 · 25 citations
- Unleashing the Power of Type-Based Call Graph Construction by Using Regional Pointer InformationYuandao Cai, Yibo Jin, Charles ZhangUSENIX Security 2024 · 16 citations
- Peahen: fast and precise static deadlock detection via context reductionYuandao Cai, Chengfeng Ye, Qingkai Shi, Charles ZhangFSE 2022 · 16 citations
- Plankton: Reconciling Binary Code and Debug InformationAnshunkang Zhou, Chengfeng Ye, Heqing Huang, Yuandao Cai et al.ASPLOS 2024 · 11 citations
Builds on5
- Razzer: Finding Kernel Race Bugs through FuzzingDae R. Jeong, Kyungtae Kim, Basavesh Shivakumar, Byoungyoung Lee et al.S&P 2019 · 202 citations
- Krace: Data Race Fuzzing for Kernel File SystemsMeng Xu, Sanidhya Kashyap, Hanqing Zhao, Taesoo KimS&P 2020 · 131 citations
- Fast, sound, and effectively complete dynamic race predictionAndreas PavlogiannisPOPL 2020 · 46 citations
- SmartTrack: efficient predictive race detectionJake Roemer, Kaan Genç, Michael D. BondPLDI 2020 · 28 citations
- MUZZ: Thread-aware Grey-box Fuzzing for Effective Bug Hunting in Multithreaded ProgramsHongxu Chen, Shengjian Guo, Yinxing Xue, Yulei Sui et al.USENIX Security 2020
Related papers
- Conquering the extensional scalability problem for value-flow analysis frameworksQingkai Shi, Rongxin Wu, Gang Fan, Charles ZhangICSE 2020 · 15 citations
- Reorder Pointer Flow in Sound Concurrency Bug PredictionYuqi Guo, Shihao Zhu, Yan Cai, Liang He et al.ICSE 2024 · 1 citation
- Precise and efficient atomicity violation detection for interrupt-driven programs via staged path pruningChao Li, Rui Chen, Boxiang Wang, Tingting Yu et al.ISSTA 2022 · 9 citations
- Pipelining bottom-up data flow analysisQingkai Shi, Charles ZhangICSE 2020 · 14 citations
- Detecting Blocking Errors in Go Programs using Localized Abstract InterpretationOskar Haarklou Veileborg, Georgian-Vlad Saioc, Anders MøllerASE 2022 · 12 citations
