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.
Lune can draw on
the full paper · the top-tier papers that cite it · related work
Free to start. No credit card required.
Lineage
Cited by top-tier papers1
Builds on4
- Software Verification of Hyperproperties Beyond k-SafetyRaven Beutner, Bernd FinkbeinerCAV 2022 · 44 citations
- Reductions for safety proofsAzadeh Farzan, Anthony VandikasPOPL 2020 · 21 citations
- Engineering a Formally Verified Automated Bug FinderArthur Correnson, Dominic SteinhöfelFSE 2023 · 6 citations
- Hunting the Haunter - Efficient Relational Symbolic Execution for Spectre with Haunted RelSELesly-Ann Daniel, Sébastien Bardin, Tamara RezkNDSS 2021
Related papers
- Hypra: A Deductive Program Verifier for Hyper Hoare LogicThibault Dardinier, Anqi Li, Peter MüllerOOPSLA 2024 · 6 citations
- Hyper Separation LogicTrayan Gospodinov, Peter Müller, Thibault DardinierPLDI 2026 · 1 citation
- Hypertesting of Programs: Theoretical Foundation and Automated Test GenerationMichele Pasqua, Mariano Ceccato, Paolo TonellaICSE 2024 · 1 citation
- HyperLasso: Bounded Model Checking of ∀+∃>+-Liveness HyperpropertiesAlcino Cunha, Hugo Pacheco, Nuno MacedoCAV 2026
- Coinductive Proofs for Temporal HyperlivenessArthur Correnson, Bernd FinkbeinerPOPL 2025 · 5 citations
