Abstract
Monitoring hyperproperties—properties that describe relationships between multiple execution traces—is essential for verifying security policies like observational determinism. However, existing monitoring frameworks largely assume a synchronous model where traces progress in lockstep, a condition rarely met in distributed or concurrent systems. This paper introduces prefix transducers, a deterministic automata-based formalism designed for the efficient runtime monitoring of asynchronous hyperproperties. By utilizing prefix-free expressions and multi-trace transducers, the proposed approach avoids the state-space explosion typical of non-deterministic methods. Experimental results demonstrate that this framework scales linearly with the number of traces and remains robust against significant trace misalignment.
Introduction
In traditional software verification, correctness is typically defined by properties of individual execution traces. For instance, a safety property might specify that a program never enters a forbidden error state. However, many critical policies, particularly in security, cannot be expressed by looking at a single trace in isolation. These are known as hyperproperties.
A hallmark example is Observational Determinism (OD). OD requires that if two separate executions of a program receive the same public (low-security) inputs, they must produce the same public outputs, regardless of any secret (high-security) data processed internally. To verify OD, a monitor must compare at least two traces simultaneously.
While frameworks like HyperLTL provide a logical basis for specifying these relationships, they generally assume synchronous execution. In real-world distributed systems, traces are often asynchronous, misaligned, or padded with irrelevant events. Existing logical approaches to asynchrony often rely on high levels of non-determinism, making them computationally prohibitive for real-time monitoring. This paper addresses this gap by shifting from logic-based specifications to an executable, deterministic transducer-based formalism.
The Prefix Transducer Framework
The authors propose a new method for monitoring $k$-safety hyperproperties—properties where a violation can be proven by a finite set of $k$ traces—using two primary components: Prefix Expressions and Multi-trace Prefix Transducers.
1. Prefix Expressions (PE)
To maintain efficiency, the monitor must be deterministic. Traditional regular expressions are often ambiguous due to the Kleene star ($*$). The authors introduce Prefix Expressions, which are designed to match the shortest possible prefix of a word deterministically. By replacing the Kleene star with a binary iteration operator (similar to the "until" operator in Linear Temporal Logic), they ensure that there is always a unique, unambiguous way to match a trace prefix.
2. Multi-trace Prefix Transducers (MPT)
Building on PEs, the Multi-trace Prefix Transducer is a finite state machine where transitions are guarded by multi-trace expressions. Unlike synchronous monitors, an MPT can look at $k$ different traces simultaneously and match prefixes of different lengths on each trace. This allows the monitor to "wait" for relevant events on one trace while others continue to progress, effectively handling asynchrony as a pattern-matching problem rather than a timing problem.
3. The Monitoring Algorithm
The monitoring process is implemented as an online algorithm within the VAMOS framework. It maintains a "workbag" of configurations, incrementally consuming events as they arrive from various sources. The algorithm checks logical conditions across the matched prefixes and can even act as a "filter," stripping away asynchronous noise to produce clean, synchronous output for legacy monitoring tools.
Experimental Evaluation
Because no standard benchmarks exist for asynchronous hyperproperty monitoring, the authors evaluated their C++ implementation using synthetic datasets designed to test various stress factors:
- Random Traces: Generated with a mix of low-input and low-output events (approximately 10% each) to simulate typical data processing.
- Periodic Traces: Designed to test "worst-case" synchronization, where relevant events occur at fixed intervals, forcing the monitor to manage large amounts of buffered data.
- Scale: The experiments involved processing hundreds of traces simultaneously, with individual trace lengths reaching up to 20,000 events.
Key Results
- Linear Scalability: In tests with random traces, the memory required to track potential violations (the "workbag" size) grew linearly with the number of traces. This suggests the approach is highly viable for large-scale system monitoring.
- Efficiency: The implementation successfully processed hundreds of traces in seconds, demonstrating that the deterministic nature of prefix transducers effectively prevents state-space explosion.
- Robustness: The monitor handled "misaligned" traces—where identical sequences of important events are separated by different amounts of irrelevant padding—without significant performance degradation.
Discussion and Future Work
The introduction of prefix transducers represents a significant step toward practical hyperproperty monitoring in the real world. By treating asynchrony as a deterministic matching problem, the authors provide a middle ground between the high-level expressivity of logic and the execution efficiency of automata.
However, several avenues for improvement remain. The current algorithm does not yet exploit symmetry optimizations; for example, if the monitor has already checked Trace A against Trace B, it should not need to redundantly check Trace B against Trace A. Additionally, while transducers are efficient, they are more difficult for humans to write than logical formulas. Future work includes developing a high-level logical language that can be automatically compiled into MPTs. Finally, while the current work focuses on safety properties, extending the framework to handle liveness properties (events that must eventually occur) remains a significant open challenge.
Summary updated