Deciding Hyperproperties Combined with Functional Specifications

Raven Beutner, David Carral, Bernd Finkbeiner, Jana Hofmann, Markus Krötzsch

Abstract

HyperLTL is a powerful logic for specifying hyperproperties—requirements that relate multiple execution traces, such as non-interference in security. However, the satisfiability problem for the $\forall^*\exists^*$ fragment of HyperLTL is known to be highly undecidable ($\Sigma^1_1$-complete). This paper investigates the boundaries of decidability by conceptually splitting specifications into a hyperproperty component and a functional trace specification. We characterize the complexity of various safety and liveness fragments and introduce LMHyper, a novel algorithm for $\forall\exists^*$-HyperLTL that searches for the largest satisfying model to detect both satisfiability and unsatisfiability.

Introduction

In formal verification, properties are traditionally categorized as trace properties, which describe the behavior of individual executions (e.g., "the system never crashes"). Modern requirements, particularly in security and privacy, often demand the comparison of multiple executions. These are known as hyperproperties. For instance, Non-interference dictates that variations in high-security inputs should not result in observable changes in low-security outputs across different runs.

HyperLTL extends Linear Temporal Logic (LTL) with trace quantifiers ($\forall, \exists$) to express these relationships. While expressive, HyperLTL's $\forall^*\exists^*$ fragment is notoriously difficult to reason about. In practical applications, developers do not just require a system to satisfy a hyperproperty; they also require it to meet a functional specification (e.g., "every request eventually receives a response"). This research explores the computational landscape that emerges when these two types of requirements are combined.

The Conceptual Split: Hyperproperties and Functional Specifications

The authors propose a systematic study of the $\forall^*\exists^*$ fragment by partitioning formulas into a hyperproperty and a functional (trace) specification. This approach allows for a granular analysis of how different types of temporal requirements affect decidability.

Fragment Classification

The study categorizes formulas based on their temporal nature:

  1. Temporal Safety: Properties where any violation can be identified in finite time.
  2. Temporal Liveness: Properties where a "good" event is guaranteed to happen eventually.

By mapping these fragments, the researchers identified exactly where the complexity of the satisfiability problem jumps from manageable classes (like coRE) to the analytical hierarchy ($\Sigma^1_1$).

Complexity and Decidability Insights

A significant finding of this work is the "Safety/Liveness Divide." In standard LTL, safety properties are generally easier to verify than liveness properties. In HyperLTL, the researchers discovered a surprising nuance: while general temporal liveness is highly undecidable, a specific fragment—$\forall\exists^*$ with simple eventualities ($\diamond$)—remains decidable even when combined with complex functional specifications.

This represents the first known decidability result for a HyperLTL fragment capable of enforcing models with infinitely many traces. Conversely, the study shows that adding even a basic LTL functional specification to a simple hyperproperty often triggers a massive jump in complexity, rendering the problem as difficult as the most challenging problems in logic.

The LMHyper Algorithm

To address the $\forall\exists^*$ fragment, the authors developed LMHyper. This algorithm leverages the observation that models for these formulas are closed under union. Consequently, if a formula is satisfiable, there exists a unique largest model.

Unlike existing tools like MGHyper, which search for the smallest finite model (a bounded model checking approach), LMHyper uses an iterative fixed-point algorithm. It begins with the set of all possible traces and systematically prunes those that lack the "witness" traces required by existential quantifiers. This allows LMHyper to prove unsatisfiability, a feat impossible for tools that only search for finite satisfying models.

Experimental Results

The effectiveness of LMHyper was evaluated against two benchmark sets:

  • Random Formulas: Using 100 formulas from the randltl tool, LMHyper achieved a 100% success rate, outperforming MGHyper (92-97%).
  • Hand-crafted Specifications: In tests designed to challenge solvers—such as formulas requiring at least $n$ traces (Enforce-n) or those that are subtly unsatisfiable (Unsat-n)—LMHyper demonstrated superior performance. For example, it solved Enforce-5 in under 500ms while MGHyper timed out. Most importantly, it successfully identified unsatisfiable cases like Unsat-9 that bounded approaches could never definitively resolve.

Conclusion

This research provides a comprehensive atlas of HyperLTL complexity, identifying new decidable fragments that support infinite models. While the LMHyper algorithm is an incomplete approximation for the broader $\forall\exists^*$ fragment, its ability to find largest models offers a powerful new tool for both satisfiability and unsatisfiability checking. Future work will explore further restrictions on temporal operators, such as the "Next" operator ($\bigcirc$), to expand the known boundaries of decidability.

Summary updated

Abstract

We study satisfiability for HyperLTL with a $\forall^*\exists^*$ quantifier prefix, known to be highly undecidable in general. HyperLTL can express system properties that relate multiple traces (so-called hyperproperties), which are often combined with trace properties that specify functional behavior on single traces. Following this conceptual split, we first define several safety and liveness fragments of $\forall^*\exists^*$ HyperLTL, and characterize the complexity of their (often much easier) satisfiability problem. We then add LTL trace properties as functional specifications. Though (highly) undecidable in many cases, this way of combining "simple" HyperLTL and arbitrary LTL also leads to interesting new decidable fragments. This systematic study of $\forall^*\exists^*$ fragments is complemented by a new (incomplete) algorithm for $\forall\exists^*$-HyperLTL satisfiability.
BibTeX
@inproceedings{beutner2022deciding,
  author = {Raven Beutner and David Carral and Bernd Finkbeiner and Jana Hofmann and Markus Krötzsch},
  title = {{Deciding Hyperproperties Combined with Functional Specifications}},
  booktitle = {LICS},
  year = {2022},
  doi = {10.1145/3531130.3533369},
}
Figure