Proving hypersafety compositionally
Emanuele D'Osualdo, Azadeh Farzan, Derek Dreyer
Abstract
Hypersafety properties of arity 𝑛 are program properties that relate 𝑛 traces of a program (or, more generally, traces of 𝑛 programs). Classic examples include determinism, idempotence, and associativity. A number of relational program logics have been introduced to target this class of properties. Their aim is to construct simpler proofs by capitalizing on structural similarities between the 𝑛 related programs. We propose unexplored, complementary proof principles that establish hyper-triples (i.e. hypersafety judgments) as a unifying compositional building block for proofs, and we use them to develop a Logic for Hyper-triple Composition (LHC), which supports forms of proof compositionality that were not achievable in previous relational logics. We prove LHC sound and apply it to a number of challenging examples.
Many properties of interest about programs are properties not of individual program traces but rather of multiple program traces. For example, stipulating a bound on mean response time over all executions of a program cannot be specified as a property of individual traces, because the acceptability of delays in a trace depends on the magnitude of delays in all other traces. Clarkson and Schneider [2008] formally studied this class of properties, coining the term hyperproperties. In this paper, we focus on the verification problem of a class of generalized hyperproperties, which we will refer to as 𝑛-safety properties: these are safety hyperproperties (i.e. only concerned with partial correctness) that govern 𝑛 executions of potentially different programs. More formally, these 𝑛-safety properties have the form ∀(𝑠 1 , 𝑠 ′ 1 ) ∈ 𝑡 1 . . . ∀(𝑠 𝑛 , 𝑠 ′ 𝑛 ) ∈ 𝑡 𝑛 . 𝜑 (𝑠 1 , 𝑠 ′ 1 , . . . , 𝑠 𝑛 , 𝑠 ′ 𝑛 ), where 𝑡 denotes the set of input/output states of the traces of 𝑡. Examples of such properties are 1 commutativity (𝑛 = 2), associativity (𝑛 = 4), determinism (𝑛 = 2), noninterference (𝑛 = 2) and transitivity (𝑛 = 3). Input-output equivalences between two programs can also be proved as 2-safety properties (e.g. a compiler optimization preserves I/O behaviour).
One approach to proving 𝑛-safety properties is to obtain from 𝑡 a precise mathematical characterization 𝑅 of its functionality 𝑡 -i.e. 𝑡's strongest postcondition-and then prove using this mathematical characterization that the desired 𝑛-safety property 𝜑 is satisfied. This approach has a major drawback, however: functional correctness is in general a much stronger-thus more difficult to prove-property of 𝑡 than what proving 𝜑 requires.
Thus, the trend in research on this problem has been instead towards reasoning directly about 𝑛-safety, through a number of so-called relational program logics, e.g. [Barthe et al. 2016;Benton 2004;Sousa and Dillig 2016;Yang 2007]. These logics move away from the traditional Hoaretriple judgment and introduce 𝑛-ary relational Hoare-style judgments, which we will refer to as hyper-triples. In our syntax, a hyper-triple (of arity 𝑛) is a judgment of the form
For example, determinism of 𝑡 can be expressed as ⊢ vars 1 = vars 2 [1: 𝑡, 2: 𝑡] vars 1 = vars 2 , which asserts that 1 Intuitively, for instance, associativity f(𝑎, f(𝑏, 𝑐)) = f(f(𝑎, 𝑏), 𝑐) compares 4 runs of f.
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
- Hypra: A Deductive Program Verifier for Hyper Hoare Logic cites An Algebra of Alignment for Relational Verification
- Hypra: A Deductive Program Verifier for Hyper Hoare Logic cites Hyper Hoare Logic: (Dis-)Proving Program Hyperproperties
- Hypra: A Deductive Program Verifier for Hyper Hoare Logic cites Constraint-Based Relational Verification
- Hypra: A Deductive Program Verifier for Hyper Hoare Logic cites Mechanised Hypersafety Proofs about Structured Data
- An Algebra of Alignment for Relational Verification cites Alignment Completeness for Relational Hoare Logics
- An Algebra of Alignment for Relational Verification cites Constraint-Based Relational Verification
- Hyper Hoare Logic: (Dis-)Proving Program Hyperproperties cites An Algebra of Alignment for Relational Verification
- Hyper Hoare Logic: (Dis-)Proving Program Hyperproperties cites Constraint-Based Relational Verification
- Mechanised Hypersafety Proofs about Structured Data cites Hyper Hoare Logic: (Dis-)Proving Program Hyperproperties
Cited by top-tier papers13
- Hyper Hoare Logic: (Dis-)Proving Program HyperpropertiesThibault Dardinier, Peter MüllerPLDI 2024 · 28 citations
- An Algebra of Alignment for Relational VerificationTimos Antonopoulos, Eric Koskinen, Ton Chanh Le, Ramana Nagasamudram et al.POPL 2023 · 17 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
- Bluebell: An Alliance of Relational Lifting and Independence for Probabilistic ReasoningJialu Bao, Emanuele D'Osualdo, Azadeh FarzanPOPL 2025 · 6 citations
Builds on2
Related papers
- Coinductive Proofs for Temporal HyperlivenessArthur Correnson, Bernd FinkbeinerPOPL 2025 · 5 citations
- Hyper Separation LogicTrayan Gospodinov, Peter Müller, Thibault DardinierPLDI 2026 · 1 citation
- Software Verification of Hyperproperties Beyond k-SafetyRaven Beutner, Bernd FinkbeinerCAV 2022 · 44 citations
- Calculational Design of Hyperlogics by Abstract InterpretationPatrick Cousot, Jeffery WangPOPL 2025 · 3 citations
- Deciding Hyperproperties Combined with Functional SpecificationsRaven Beutner, David Carral, Bernd Finkbeiner, Jana Hofmann et al.LICS 2022 · 13 citations
