In traditional formal verification, we ask questions about a single execution of a system: "Does this program ever crash?" or "Will the request eventually receive a response?" These are trace properties, typically expressed in logics like LTL or PCTL. However, many critical requirements—especially in security and privacy—cannot be defined by looking at one execution in isolation.
Consider non-interference: a secret input should not affect the observable output. To prove this, you cannot look at one trace; you must compare two different traces (one with the secret, one without) and ensure their outputs are identical. These requirements are known as hyperproperties.
The challenge is that standard model-checking tools are designed for single traces. To bridge this gap, researchers have converged on a powerful mechanism: self-composition.
The Intuition: Parallel Universes
The core idea of self-composition is to transform a "multi-trace" problem into a "single-trace" problem. If you need to reason about the relationship between two executions of a system $M$, you construct a new system $M \times M$—the Cartesian product of the system with itself.
In this product system, a single state represents a pair of states from the original system. A single transition in the product system represents a simultaneous step in both "parallel universes." By running these instances in parallel, a hyperproperty that relates two traces (like "trace A and trace B must always have the same output") becomes a simple invariant on the single trace of the composed system ("in every state $(s_1, s_2)$, the output of $s_1$ equals the output of $s_2$").
As Bernd Finkbeiner explains in Model Checking Algorithms for Hyperproperties, this parallel self-composition allows us to reuse existing verification machinery to check complex policies expressed in HyperLTL.
From Logic to Synthesis
This approach extends beyond simple "yes/no" verification. In Synthesizing Reactive Systems from Hyperproperties, Bernd Finkbeiner, Christopher Hahn, and their colleagues demonstrate that we can automatically synthesize systems that are secure by design. By modeling multiple parallel instances, the synthesis algorithm can ensure that the choices the system makes in one execution path are consistent with the requirements of all other potential paths, effectively "building in" observational consistency.
Probabilistic and Strategic Dimensions
The power of self-composition is most evident when dealing with uncertainty and probability.
- Probabilistic Hyperproperties: In HyperPCTL: A Temporal Logic for Probabilistic Hyperproperties, Borzoo Bonakdarpour and Erika Ábrahám show that $n$-ary self-composition can verify properties like differential privacy. By creating a product of Markov chains, they can quantify the probabilistic distance between different execution sets. This is further extended to parameter synthesis by Ezio Bartocci and others in Parameter Synthesis for Probabilistic Hyperproperties, allowing designers to find the exact system configurations that satisfy privacy bounds.
- Information and Strategy: There is a deep link between what an agent knows and how different traces relate. Bernd Finkbeiner and Raven Beutner prove in Strategy Logic, Imperfect Information, and Hyperproperties that reasoning about imperfect information in multi-agent systems is expressively equivalent to reasoning about hyperproperties. Self-composition serves as the bridge: by restricting an agent's observations to specific instances in a parallel product, we can simulate the agent's inability to distinguish between different system runs.
Privacy as State Opacity
In the realm of discrete-event systems, self-composition takes the form of combining a system model with an "observer." Xiaoguang Han 0002 and colleagues apply this in Strong current-state and initial-state opacity of discrete-event systems. To ensure an intruder can never be sure a system visited a secret state, they track the actual system run alongside a "hypothetical" non-secret run. If the two ever become observationally distinct, the secret is leaked.
Summary
The shift from trace properties to hyperproperties represents a move toward verifying the intent and security of systems rather than just their functional correctness. Self-composition is the fundamental algorithmic tool that makes this possible, turning the complex comparison of infinite execution sets into a manageable search through a unified, albeit larger, state space.