Lune

OOPSLA2024Top-tier venue

Finding ∀∃ Hyperbugs using Symbolic Execution

Arthur Correnson, Tobias Nießen, Bernd Finkbeiner, Georg Weissenbacher

Abstract

Many important hyperproperties, such as refinement and generalized non-interference, fall into the class of ∀∃ hyperproperties and require, for each execution trace of a system, the existence of another trace relating to the first one in a certain way. The alternation of quantifiers renders ∀∃ hyperproperties extremely difficult to verify, or even just to test. Indeed, contrary to trace properties, where it suffices to find a single counterexample trace, refuting a ∀∃ hyperproperty requires not only to find a trace, but also a proof that no second trace satisfies the specified relation with the first trace. As a consequence, automated testing of ∀∃ hyperproperties falls out of the scope of existing automated testing tools. In this paper, we present a fully automated approach to detect violations of ∀∃ hyperproperties in software systems. Our approach extends bug-finding techniques based on symbolic execution with support for trace quantification. We provide a prototype implementation of our approach, and demonstrate its effectiveness on a set of challenging examples.

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.

1 top-tier paper has cited it since. Know what they found before your reviewers do.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

  • Verifying Asynchronous Hyperproperties in Reactive Systems cites Reductions for safety proofs
  • Verifying Asynchronous Hyperproperties in Reactive Systems cites Software Verification of Hyperproperties Beyond k-Safety
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers1

  1. Verifying Asynchronous Hyperproperties in Reactive SystemsRaven Beutner, Bernd FinkbeinerOOPSLA 2025 · 2 citations

Builds on4

  1. Software Verification of Hyperproperties Beyond k-SafetyRaven Beutner, Bernd FinkbeinerCAV 2022 · 44 citations
  2. Reductions for safety proofsAzadeh Farzan, Anthony VandikasPOPL 2020 · 21 citations
  3. Engineering a Formally Verified Automated Bug FinderArthur Correnson, Dominic SteinhöfelFSE 2023 · 6 citations
  4. Hunting the Haunter - Efficient Relational Symbolic Execution for Spectre with Haunted RelSELesly-Ann Daniel, Sébastien Bardin, Tamara RezkNDSS 2021

Related papers

  1. Hypra: A Deductive Program Verifier for Hyper Hoare LogicThibault Dardinier, Anqi Li, Peter MüllerOOPSLA 2024 · 6 citations
  2. Hyper Separation LogicTrayan Gospodinov, Peter Müller, Thibault DardinierPLDI 2026 · 1 citation
  3. Hypertesting of Programs: Theoretical Foundation and Automated Test GenerationMichele Pasqua, Mariano Ceccato, Paolo TonellaICSE 2024 · 1 citation
  4. HyperLasso: Bounded Model Checking of ∀+∃>+-Liveness HyperpropertiesAlcino Cunha, Hugo Pacheco, Nuno MacedoCAV 2026
  5. Coinductive Proofs for Temporal HyperlivenessArthur Correnson, Bernd FinkbeinerPOPL 2025 · 5 citations
Dusk over the sea between two cliffs drawn in fine vertical lines