Hyper Hoare Logic: (Dis-)Proving Program Hyperproperties
Thibault Dardinier, Peter Müller
Abstract
Hoare logics are proof systems that allowone to formally establish properties of computer programs. Traditional Hoare logics prove properties of individual program executions (such as functional correctness). Hoare logic has been generalized to prove also properties of multiple executions of a program (so-called hyperproperties, such as determinism or non-interference). These program logics prove the absence of (bad combinations of) executions. On the other hand, program logics similar to Hoare logic have been proposed to disprove program properties (e.g., Incorrectness Logic), by proving the existence of (bad combinations of) executions. All of these logics have in common that they specify program properties using assertions over a fixed number of states, for instance, a single pre- and post-state for functional properties or pairs of pre- and post-states for non-interference. In this paper, we present Hyper Hoare Logic, a generalization of Hoare logic that lifts assertions to properties of arbitrary sets of states. The resulting logic is simple yet expressive: its judgments can express arbitrary program hyperproperties , a particular class of hyperproperties over the set of terminating executions of a program (including properties of individual program executions). By allowing assertions to reason about sets of states, Hyper Hoare Logic can reason about both the absence and the existence of (combinations of) executions, and, thereby, supports both proving and disproving program (hyper-)properties within the same logic, including (hyper-)properties that no existing Hoare logic can express. We prove that Hyper Hoare Logic is sound and complete, and demonstrate that it captures important proof principles naturally. All our technical results have been proved in Isabelle/HOL.
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.
20 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
- Hypra: A Deductive Program Verifier for Hyper Hoare Logic cites Incorrectness logic
- Hypra: A Deductive Program Verifier for Hyper Hoare Logic cites Finding real bugs in big programs with incorrectness logic
- Hypra: A Deductive Program Verifier for Hyper Hoare Logic cites Constraint-Based Relational Verification
- Hypra: A Deductive Program Verifier for Hyper Hoare Logic cites Outcome Logic: A Unifying Foundation for Correctness and Incorrectness Reasoning
- Hypra: A Deductive Program Verifier for Hyper Hoare Logic cites Mechanised Hypersafety Proofs about Structured Data
- Hypra: A Deductive Program Verifier for Hyper Hoare Logic cites Software Verification of Hyperproperties Beyond k-Safety
- Coinductive Proofs for Temporal Hyperliveness cites Software Verification of Hyperproperties Beyond k-Safety
- Local Reasoning About the Presence of Bugs: Incorrectness Separation Logic cites Incorrectness 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 Local Reasoning About the Presence of Bugs: Incorrectness Separation Logic
- Outcome Separation Logic: Local Reasoning for Correctness and Incorrectness with Computational Effects cites Finding real bugs in big programs with incorrectness logic
- Outcome Separation Logic: Local Reasoning for Correctness and Incorrectness with Computational Effects cites Outcome Logic: A Unifying Foundation for Correctness and Incorrectness Reasoning
- Finding real bugs in big programs with incorrectness logic cites Incorrectness logic
- Finding real bugs in big programs with incorrectness logic cites Local Reasoning About the Presence of Bugs: 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
- Outcome Logic: A Unifying Foundation for Correctness and Incorrectness Reasoning cites Finding real bugs in big programs with incorrectness logic
- Software Verification of Hyperproperties Beyond k-Safety cites Constraint-Based Relational Verification
Cited by top-tier papers20
- Outcome Logic: A Unifying Foundation for Correctness and Incorrectness ReasoningNoam Zilberstein, Derek Dreyer, Alexandra SilvaOOPSLA 2023 · 39 citations
- Outcome Separation Logic: Local Reasoning for Correctness and Incorrectness with Computational EffectsNoam Zilberstein, Angelina Saliling, Alexandra SilvaOOPSLA 2024 · 16 citations
- Mechanised Hypersafety Proofs about Structured DataVladimir Gladshtein, Qiyuan Zhao, Willow Ahrens, Saman P. Amarasinghe et al.PLDI 2024 · 10 citations
- Hypra: A Deductive Program Verifier for Hyper Hoare LogicThibault Dardinier, Anqi Li, Peter MüllerOOPSLA 2024 · 6 citations
- Coinductive Proofs for Temporal HyperlivenessArthur Correnson, Bernd FinkbeinerPOPL 2025 · 5 citations
Builds on13
- 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
- Finding real bugs in big programs with incorrectness logicQuang Loc Le, Azalea Raad, Jules Villard, Josh Berdine et al.OOPSLA 2022 · 52 citations
- Constraint-Based Relational VerificationHiroshi Unno, Tachio Terauchi, Eric KoskinenCAV 2021 · 47 citations
- Software Verification of Hyperproperties Beyond k-SafetyRaven Beutner, Bernd FinkbeinerCAV 2022 · 44 citations
Related papers
- Hyper Separation LogicTrayan Gospodinov, Peter Müller, Thibault DardinierPLDI 2026 · 1 citation
- Proving hypersafety compositionallyEmanuele D'Osualdo, Azadeh Farzan, Derek DreyerOOPSLA 2022 · 16 citations
- Encode the ∀∃ Relational Hoare Logic into Standard Hoare LogicShushu Wu, Xiwei Wu, Qinxiang CaoOOPSLA 2025 · 1 citation
- Calculational Design of [In]Correctness Transformational Program Logics by Abstract InterpretationPatrick CousotPOPL 2024 · 11 citations
- Revealing Sources of (Memory) Errors via Backward AnalysisFlavio Ascari, Roberto Bruni, Roberta Gori, Francesco LogozzoOOPSLA 2025 · 4 citations
