Verifying Security and Privacy through Multi-Trace Hyperproperties

You are reading version 1 of this direction, frozen 2026-10-04. The latest version is version 2.

Version 1 of 2181 papers291 conceptsfrozen 2026-10-04

In traditional formal verification, we ask questions about a single execution of a system: "Does this program ever crash?" or "Does the request eventually receive a response?" These are trace properties, where the correctness of a system is determined by checking every individual execution path in isolation.

However, many of the most critical requirements in modern computing—security, privacy, and fairness—cannot be expressed this way. Consider non-interference: a security policy stating that a system's public outputs should not reveal anything about its secret inputs. To prove this, you cannot look at one execution in a vacuum. You must compare at least two: one where the secret is 'A' and one where the secret is 'B'. If the public outputs are identical in both cases, the secret is safe.

This shift from analyzing single traces to analyzing relationships between sets of traces is the core of hyperproperties.

The Logic of Relationships: HyperLTL

To reason about these relationships formally, researchers led by Bernd Finkbeiner and Christopher Hahn developed HyperLTL. As detailed in Deciding Hyperproperties, HyperLTL extends standard Linear Temporal Logic (LTL) by adding trace variables ($\pi_1, \pi_2, \dots$) and quantifiers ($\forall, \exists$).

In standard LTL, a property like "output is always zero" is written as $\square (out = 0)$. In HyperLTL, observational determinism—the requirement that low-security observers see the same behavior regardless of high-security inputs—is expressed as: $$\forall \pi_1. \forall \pi_2. \square (in_{low}[\pi_1] = in_{low}[\pi_2] \implies out_{low}[\pi_1] = out_{low}[\pi_2])$$

This formula explicitly links two different executions, $\pi_1$ and $\pi_2$, requiring their outputs to match whenever their low-security inputs match. This expressive power allows for the formalization of complex concepts like hyperliveness, which Bernd Finkbeiner and Norine Coenen describe as properties where one execution's existence depends on another, such as in generalized non-interference [Verifying Hyperliveness].

The Complexity of Multi-Trace Reasoning

The primary challenge in verifying hyperproperties is the "exponential blowup" caused by quantifier alternation. While checking a single trace is relatively simple, checking a property that says "for every trace, there exists another trace..." requires exploring the interaction between all possible pairs of executions.

To handle this, researchers have moved beyond simple SAT solvers. Tzu-Han Hsu and Borzoo Bonakdarpour introduced HyperQube, a bounded model checker that reduces HyperLTL verification to Quantified Boolean Formulas (QBF) [Bounded Model Checking for Hyperproperties]. By using QBF solvers, the tool can natively handle the nested "for all" and "there exists" structures inherent in security policies.

For infinite-state systems, such as smart contracts or dynamical control systems, the problem becomes even harder. Mahathi Anand and Ashutosh Trivedi proposed using Augmented Barrier Certificates, which define safety regions over the product space of multiple executions, providing a mathematical guarantee that the combined state of two traces never diverges in a way that leaks information [Formal Verification of Control Systems against Hyperproperties via Barrier Certificates].

Monitoring and Synthesis

Verification isn't just for design time; it's also for runtime. However, monitoring hyperproperties is difficult because a monitor must remember past executions to compare them with the current one. Marvin Stenger and Leander Tentrup addressed this in RVHyper by using prefix trees (tries) to compress trace history [Efficient monitoring of hyperproperties using prefix trees]. This structure allows the monitor to quickly identify if a new execution violates a relationship with any previously seen run without storing redundant data.

Beyond checking existing systems, researchers are working toward correct-by-design systems. By reframing verification as a game—where a system designer tries to find a strategy that satisfies the hyperproperty against an adversarial environment—Raven Beutner and Bernd Finkbeiner have developed methods to synthesize reactive systems and smart contracts that are mathematically guaranteed to be secure [On Hyperproperty Verification, Quantifier Alternations, and Games under Partial Information].

Expanding the Horizon: Probability and Fairness

The hyperproperty framework is now expanding to address probabilistic systems and machine learning. Borzoo Bonakdarpour and Erika Ábrahám introduced HyperPCTL to reason about relationships between probability distributions, which is essential for verifying differential privacy [HyperPCTL: A Temporal Logic for Probabilistic Hyperproperties]. Similarly, Yasser Shoukry demonstrated that individual fairness in neural networks is a hyperproperty: it requires that two similar individuals (two traces/inputs) receive similar outcomes [CertiFair: A Framework for Certified Global Fairness of Neural Networks].

By treating security, privacy, and fairness as relational properties rather than isolated events, this research direction provides the mathematical tools necessary to build systems that are not just functional, but fundamentally trustworthy.

Papers in this version

Showing 60 of 181 papers.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 163 papers
  2. Version 1 · 2026-10-04 · 181 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_hyperproperty_verification_7bc55afd,
  title = {hyperproperty verification},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/hyperproperty-verification/rdr_7bc55afdd10a4f70be15e4dec8fee2cb},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 1, frozen text):

@misc{lacuna_verifying_security_and_privacy_through_m_7bc55afd_v1,
  title = {Verifying Security and Privacy through Multi-Trace Hyperproperties},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/verifying-security-and-privacy-through-multi-trace-hyperproperties/rdr_7bc55afdd10a4f70be15e4dec8fee2cb/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}