Checking Satisfiability of Hyperproperties using First-Order Logic
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912793843728384 |
|---|---|
| author | Beutner, Raven Finkbeiner, Bernd |
| author_facet | Beutner, Raven Finkbeiner, Bernd |
| contents | Hyperproperties are system properties that relate multiple execution traces and occur, e.g., when specifying security and information-flow properties. Checking if a hyperproperty is satisfiable has many important applications, such as testing if some security property is contradictory, or analyzing implications and equivalences between information-flow policies. In this paper, we present FOLHyper, a tool that can automatically check satisfiability of hyperproperties specified in the temporal logic HyperLTL. FOLHyper reduces the problem to an equisatisfiable first-order logic (FOL) formula, which allows us to leverage FOL solvers for the analysis of hyperproperties. As such, FOLHyper is applicable to many formulas beyond the decidable $\exists^*\forall^*$ fragment of HyperLTL. Our experiments show that FOLHyper is particularly useful for proving that a formula is unsatisfiable, and complements existing bounded approaches to satisfiability. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_23332 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Checking Satisfiability of Hyperproperties using First-Order Logic Beutner, Raven Finkbeiner, Bernd Logic in Computer Science Hyperproperties are system properties that relate multiple execution traces and occur, e.g., when specifying security and information-flow properties. Checking if a hyperproperty is satisfiable has many important applications, such as testing if some security property is contradictory, or analyzing implications and equivalences between information-flow policies. In this paper, we present FOLHyper, a tool that can automatically check satisfiability of hyperproperties specified in the temporal logic HyperLTL. FOLHyper reduces the problem to an equisatisfiable first-order logic (FOL) formula, which allows us to leverage FOL solvers for the analysis of hyperproperties. As such, FOLHyper is applicable to many formulas beyond the decidable $\exists^*\forall^*$ fragment of HyperLTL. Our experiments show that FOLHyper is particularly useful for proving that a formula is unsatisfiable, and complements existing bounded approaches to satisfiability. |
| title | Checking Satisfiability of Hyperproperties using First-Order Logic |
| topic | Logic in Computer Science |
| url | https://arxiv.org/abs/2512.23332 |