Concurrent $$\forall \exists $$-Hyperproperties

Bernd Finkbeiner, Ernst-Rüdiger OlderogLecture Notes in Computer Science 2026 · DOI · OpenAlex

Abstract

Hyperproperties are system properties that relate multiple traces (executions) of a system, with typical applications in information flow security. In this work, we explore concurrent hyperproperties by generalizing traces to concurrent traces, defined as partially ordered multisets, using Petri nets as the basic semantic model. To check concurrent hyperproperties, we extend the testing of processes to the setting of concurrent traces using the parallel composition of Petri nets. We present new results on the decidability and undecidability of may and must testing for universal and existential concurrent hyperproperties, specifically analyzing the impact of quantifier alternation.

Introduction: Beyond Linear Traces

In formal verification, most properties are trace properties, which describe the behavior of a single execution (e.g., "the system never reaches an error state"). However, security policies often require hyperproperties, which compare multiple executions. For instance, noninterference—a core security concept—states that a low-security observer should see the same outputs regardless of high-security inputs. This requires comparing executions across different secret contexts.

While traditional hyperproperties are defined over linear sequences of events, modern systems are inherently concurrent. Events can happen simultaneously without a fixed order. This paper investigates concurrent hyperproperties, which model executions as partially ordered multisets (pomsets) using Petri nets. The central question is: can we automatically verify these complex properties?

Methodology: Testing Concurrent Systems

The authors utilize safe Petri nets to model concurrent systems. To verify properties, they adapt the "testing" framework originally developed for process calculi. A "test" is another Petri net designed to reach a "success" state if the system satisfies a certain condition. By composing the system net and the test net in parallel, the verification problem becomes a reachability problem.

Petri net system and testing process.

Two primary modes of testing are evaluated:

  • May testing: The system passes if at least one possible execution of the combined net reaches a success state.
  • Must testing: The system passes if every possible maximal execution reaches a success state.

Key Insight: Concurrency vs. Interleaving

A critical contribution of this framework is its ability to distinguish between "true concurrency" and "non-deterministic interleaving." In many models, concurrent events are simplified into all possible linear sequences (interleavings). However, for security, this distinction is vital. Asynchronous systems might exhibit behaviors that interleaving models miss, potentially leading to security vulnerabilities.

Concurrency vs. interleaving in Petri nets.

Decidability and the Quantifier Barrier

The paper provides a comprehensive map of what is and isn't computable in this domain. The results highlight a significant challenge: quantifier alternation.

  • Decidable: Purely existential "may" testing ($\exists$ may). This can be reduced to reachability problems in safe Petri nets, which are PSPACE-complete.
  • Undecidable: Existential "must" testing ($\exists$ must). The authors prove this by showing it can simulate the undecidable infinite Post Correspondence Problem ($\omega$-PCP).
  • Undecidable: Any property involving quantifier alternation, such as $\forall\exists$ (for every execution, there exists another...). This is particularly problematic because many sophisticated security policies, like generalized noninterference, rely on this structure.

Conclusion and Future Directions

The inherent undecidability of $\forall\exists$ hyperproperties presents a major hurdle for general-purpose automated verification. However, the authors identify a "deterministic escape hatch": if the parallel composition of the system and the test results in a deterministic net, the distinction between "may" and "must" vanishes, making $\forall\exists$ properties decidable.

Future research aims to find more flexible conditions. While deterministic testers are a start, they are quite restrictive. Expanding the class of decidable concurrent hyperproperties to include more practical, non-deterministic scenarios remains a key goal for securing concurrent systems.

Summary updated

Abstract

Abstract Hyperproperties are system properties that relate multiple traces (executions) of a system. Typical applications of hyperproperties are found in information flow security. In a previous paper, we introduced concurrent hyperproperties, by generalizing traces to concurrent traces, defined as partially ordered multisets. We take Petri nets as the basic semantic model. To check concurrent hyperproperties, we extended the testing of processes due to De Nicola and Hennessy to the setting of concurrent traces, using the parallel composition of Petri nets. In this paper, we present new results on decidability and undecidability of may and must testing of universal and existential concurrent hyperproperties, and analyze the case of concurrent hyperproperties with quantifier alternation.
BibTeX
@inproceedings{finkbeiner2026concurrent,
  author = {Bernd Finkbeiner and Ernst-Rüdiger Olderog},
  title = {{Concurrent $$\textbackslash\{\}forall \textbackslash\{\}exists $$-Hyperproperties}},
  booktitle = {Lecture Notes in Computer Science},
  year = {2026},
  doi = {10.1007/978-3-032-13711-1\_9},
}
Figure