International Journal on Software Tools for Technology Transfer Information Systems

AutoHyper: leveraging language inclusion checking for hyperproperty model-checking

Raven Beutner, Bernd Finkbeiner
Springer Nature · 2025-05-06 · DOI 10.1007/s10009-025-00801-5

Abstract

Abstract Hyperproperties are system properties that relate multiple execution traces, and naturally occur, e.g., in information-flow control, knowledge, robustness, mutation testing, path planning, and causality checking. HyperLTL is a temporal logic that can express complex temporal hyperproperties by extending LTL with quantification over execution traces. Thus far, complete model-checking tools for HyperLTL have been limited to alternation-free formulas, i.e., formulas that use only universal or only existential trace quantification. In this paper, we present , an explicit-state automata-based model checker for HyperLTL that is complete for formulas with an arbitrary quantifier prefix. On the theoretical side, we show how language inclusion checks between $\omega $ ω -automata can be integrated into HyperLTL verification. On the practical side, this allows to leverage a range of existing inclusion-checking tools for hyperproperty verification. We further extend our model-checking algorithm to support HyperLTL modulo theories, i.e., formulas where the atomic formulas consist of first-order formulas instead of Boolean atomic propositions. We show how we can model-check such formulas effectively by tracking partially evaluated first-order formulas within an automaton. We evaluate on a broad set of benchmarks drawn from different areas in the literature and compare it with existing (incomplete) methods for HyperLTL verification.

Read at publisher →