Finding real bugs in big programs with incorrectness logic
Quang Loc Le, Azalea Raad, Jules Villard, Josh Berdine, Derek Dreyer, Peter W. O'Hearn
Abstract
Incorrectness Logic (IL) has recently been advanced as a logical theory for compositionally proving the presence of bugsÐdual to Hoare Logic, which is used to compositionally prove their absence. Though IL was motivated in large part by the aim of providing a logical foundation for bug-catching program analyses, it has remained an open question: is IL useful only retrospectively (to explain existing analyses), or can it actually be useful in developing new analyses which can catch real bugs in big programs?
In this work, we develop Pulse-X, a new, automatic program analysis for catching memory errors, based on ISL, a recent synthesis of IL and separation logic. Using Pulse-X, we have found 15 new real bugs in OpenSSL, which we have reported to OpenSSL maintainers and have since been fixed. In order not to be overwhelmed with potential but false error reports, we develop a compositional bug-reporting criterion based on a distinction between latent and manifest errors, which references the under-approximate ISL abstractions computed by Pulse-X, and we investigate the fix rate resulting from application of this criterion. Finally, to probe the potential practicality of our bug-finding method, we conduct a comparison to Infer, a widely used analyzer which has proven useful in industrial engineering practice.
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.
37 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
- Concurrent incorrectness separation logic cites Incorrectness logic
- Concurrent incorrectness separation logic cites Local Reasoning About the Presence of Bugs: Incorrectness Separation Logic
- Hyper Hoare Logic: (Dis-)Proving Program Hyperproperties cites Concurrent incorrectness separation logic
- Hyper Hoare Logic: (Dis-)Proving Program Hyperproperties cites Incorrectness logic
- Hyper Hoare Logic: (Dis-)Proving Program Hyperproperties cites Local Reasoning About the Presence of Bugs: Incorrectness Separation Logic
- Hyper Hoare Logic: (Dis-)Proving Program Hyperproperties cites Outcome Logic: A Unifying Foundation for Correctness and Incorrectness Reasoning
- Outcome Logic: A Unifying Foundation for Correctness and Incorrectness Reasoning cites Hyper Hoare Logic: (Dis-)Proving Program Hyperproperties
- Local Reasoning About the Presence of Bugs: Incorrectness Separation Logic cites Incorrectness logic
- Local Reasoning About the Presence of Bugs: Incorrectness Separation Logic cites Gillian, part i: a multi-language platform for symbolic execution
- Outcome Separation Logic: Local Reasoning for Correctness and Incorrectness with Computational Effects cites Concurrent incorrectness separation logic
- Outcome Separation Logic: Local Reasoning for Correctness and Incorrectness with Computational Effects cites Incorrectness logic
- Outcome Separation Logic: Local Reasoning for Correctness and Incorrectness with Computational Effects cites Hyper Hoare Logic: (Dis-)Proving Program Hyperproperties
- Outcome Separation Logic: Local Reasoning for Correctness and Incorrectness with Computational Effects cites Local Reasoning About the Presence of Bugs: Incorrectness Separation Logic
- Outcome Separation Logic: Local Reasoning for Correctness and Incorrectness with Computational Effects cites Gillian, part i: a multi-language platform for symbolic execution
- Outcome Separation Logic: Local Reasoning for Correctness and Incorrectness with Computational Effects cites Outcome Logic: A Unifying Foundation for Correctness and Incorrectness Reasoning
- Gillian, part i: a multi-language platform for symbolic execution cites Incorrectness logic
- Non-termination Proving at Scale cites Concurrent incorrectness separation logic
- Non-termination Proving at Scale cites Incorrectness logic
- Non-termination Proving at Scale cites Local Reasoning About the Presence of Bugs: Incorrectness Separation Logic
- Non-termination Proving at Scale cites Outcome Separation Logic: Local Reasoning for Correctness and Incorrectness with Computational Effects
- Non-termination Proving at Scale cites Outcome Logic: A Unifying Foundation for Correctness and Incorrectness Reasoning
- Calculational Design of [In]Correctness Transformational Program Logics by Abstract Interpretation cites Concurrent incorrectness separation logic
- Calculational Design of [In]Correctness Transformational Program Logics by Abstract Interpretation cites Local Reasoning About the Presence of Bugs: Incorrectness Separation Logic
- Calculational Design of [In]Correctness Transformational Program Logics by Abstract Interpretation cites Outcome Logic: A Unifying Foundation for Correctness and Incorrectness Reasoning
- Calculational Design of [In]Correctness Transformational Program Logics by Abstract Interpretation cites Polynomial reachability witnesses via Stellensätze
- Outcome Logic: A Unifying Foundation for Correctness and Incorrectness Reasoning cites Concurrent incorrectness separation logic
- Outcome Logic: A Unifying Foundation for Correctness and Incorrectness Reasoning cites Incorrectness logic
- Outcome Logic: A Unifying Foundation for Correctness and Incorrectness Reasoning cites Local Reasoning About the Presence of Bugs: Incorrectness Separation Logic
- Polynomial reachability witnesses via Stellensätze cites Incorrectness logic
Cited by top-tier papers37
- Outcome Logic: A Unifying Foundation for Correctness and Incorrectness ReasoningNoam Zilberstein, Derek Dreyer, Alexandra SilvaOOPSLA 2023 · 39 citations
- Hyper Hoare Logic: (Dis-)Proving Program HyperpropertiesThibault Dardinier, Peter MüllerPLDI 2024 · 28 citations
- Outcome Separation Logic: Local Reasoning for Correctness and Incorrectness with Computational EffectsNoam Zilberstein, Angelina Saliling, Alexandra SilvaOOPSLA 2024 · 16 citations
- Calculational Design of [In]Correctness Transformational Program Logics by Abstract InterpretationPatrick CousotPOPL 2024 · 11 citations
- Non-termination Proving at ScaleAzalea Raad, Julien Vanegue, Peter W. O'HearnOOPSLA 2024 · 10 citations
Builds on6
- Incorrectness logicPeter W. O'HearnPOPL 2020 · 122 citations
- Local Reasoning About the Presence of Bugs: Incorrectness Separation LogicAzalea Raad, Josh Berdine, Hoang-Hai Dang, Derek Dreyer et al.CAV 2020 · 70 citations
- Gillian, part i: a multi-language platform for symbolic executionJosé Fragoso Santos, Petar Maksimovic, Sacha-Élie Ayoun, Philippa GardnerPLDI 2020 · 38 citations
- Polynomial reachability witnesses via StellensätzeAli Asadi, Krishnendu Chatterjee, Hongfei Fu, Amir Kafshdar Goharshady et al.PLDI 2021 · 28 citations
- Concurrent incorrectness separation logicAzalea Raad, Josh Berdine, Derek Dreyer, Peter W. O'HearnPOPL 2022 · 24 citations
Related papers
- Revealing Sources of (Memory) Errors via Backward AnalysisFlavio Ascari, Roberto Bruni, Roberta Gori, Francesco LogozzoOOPSLA 2025 · 4 citations
- U-Turn: Enhancing Incorrectness Analysis by Reversing DirectionFlavio Ascari, Roberto Bruni, Roberta Gori, Azalea RaadPOPL 2026 · 2 citations
- On incorrectness logic for Quantum programsPeng Yan, Hanru Jiang, Nengkun YuOOPSLA 2022 · 27 citations
- Compositional Symbolic Execution for the Next 700 Memory ModelsAndreas Lööw, Seung Hoon Park, Daniele Nantes-Sobrinho, Sacha-Élie Ayoun et al.OOPSLA 2025 · 4 citations
- CULPA: Universal Detection of Memory-Safety Bugs in Unsafe Rust Through the Lens of Safety RequirementsHung-Mao Chen, Bo Lu, Xu He, Xiaokuan Zhang et al.USENIX Security 2026
