Quantitative Weakest Hyper Pre: Unifying Correctness and Incorrectness Hyperproperties via Predicate Transformers
Linpeng Zhang, Noam Zilberstein, Benjamin Lucien Kaminski, Alexandra Silva
Abstract
We present a novel weakest pre calculus for reasoning about quantitative hyperproperties over nondeterministic and probabilistic programs . Whereas existing calculi allow reasoning about the expected value that a quantity assumes after program termination from a single initial state , we do so for initial sets of states or initial probability distributions . We thus (i) obtain a weakest pre calculus for hyper Hoare logic and (ii) enable reasoning about so-called hyperquantities which include expected values but also quantities (e.g. variance) out of scope of previous work. As a byproduct, we obtain a novel strongest post for weighted programs that extends both existing strongest and strongest liberal post calculi. Our framework reveals novel dualities between forward and backward transformers, correctness and incorrectness, as well as nontermination and unreachability.
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.
2 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
- Probabilistic Concurrent Reasoning in Outcome Logic: Independence, Conditioning, and Invariants cites A Demonic Outcome Logic for Randomized Nondeterminism
- Probabilistic Concurrent Reasoning in Outcome Logic: Independence, Conditioning, and Invariants cites Outcome Logic: A Unifying Foundation for Correctness and Incorrectness Reasoning
- A Logic for Locally Complete Abstract Interpretations cites Local Reasoning About the Presence of Bugs: Incorrectness Separation Logic
- A Demonic Outcome Logic for Randomized Nondeterminism cites Outcome Logic: A Unifying Foundation for Correctness and Incorrectness Reasoning
- Local Reasoning About the Presence of Bugs: Incorrectness Separation Logic cites Incorrectness 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 A Logic for Locally Complete Abstract Interpretations
- Outcome Logic: A Unifying Foundation for Correctness and Incorrectness Reasoning cites Local Reasoning About the Presence of Bugs: Incorrectness Separation Logic
Cited by top-tier papers2
- A Demonic Outcome Logic for Randomized NondeterminismNoam Zilberstein, Dexter Kozen, Alexandra Silva, Joseph TassarottiPOPL 2025 · 5 citations
- Probabilistic Concurrent Reasoning in Outcome Logic: Independence, Conditioning, and InvariantsNoam Zilberstein, Alexandra Silva, Joseph TassarottiPOPL 2026 · 4 citations
Builds on12
- 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
- The next 700 relational program logicsKenji Maillard, Catalin Hritcu, Exequiel Rivas, Antoine Van MuylderPOPL 2020 · 41 citations
- Outcome Logic: A Unifying Foundation for Correctness and Incorrectness ReasoningNoam Zilberstein, Derek Dreyer, Alexandra SilvaOOPSLA 2023 · 39 citations
- A Logic for Locally Complete Abstract InterpretationsRoberto Bruni, Roberto Giacobazzi, Roberta Gori, Francesco RanzatoLICS 2021 · 34 citations
Related papers
- Quantitative strongest post: a calculus for reasoning about the flow of quantitative informationLinpeng Zhang, Benjamin Lucien KaminskiOOPSLA 2022 · 14 citations
- Supermartingales for Unique Fixed Points: A Unified Approach to Lower Bound VerificationSatoshi Kura, Hiroshi Unno, Takeshi TsukadaPLDI 2026
- An Expressive Assertion Language for Quantum ProgramsBonan Su, Yuan Feng, Mingsheng Ying, Li ZhouPOPL 2026 · 1 citation
- A Deductive Verification Infrastructure for Probabilistic ProgramsPhilipp Schröer, Kevin Batz, Benjamin Lucien Kaminski, Joost-Pieter Katoen et al.OOPSLA 2023 · 22 citations
- Relatively complete verification of probabilistic programs: an expressive language for expectation-based reasoningKevin Batz, Benjamin Lucien Kaminski, Joost-Pieter Katoen, Christoph MathejaPOPL 2021 · 33 citations
