Runtime verification acts as a real-time safety camera for software systems. Instead of trying to prove a system correct before it runs (which can be mathematically exhausting) or testing it on a few sample inputs, a runtime monitor watches the actual execution stream to ensure it complies with a formal specification.
However, traditional runtime monitors frequently run into a fundamental wall: inconclusive verdicts. Because a monitor only sees a finite prefix of an ongoing, potentially infinite execution, it often lacks the information needed to declare a definitive "pass" or "fail." The monitor gets stuck in an "unknown" state. This problem intensifies when dealing with real-time constraints, partial observability, or security policies that span multiple execution traces.
To make runtime verification practical for safety-critical systems, recent research focuses on breaking out of this black-box uncertainty. By redesigning logic semantics, incorporating system assumptions, and blending runtime monitoring with static analysis, these techniques turn inconclusive "unknowns" into actionable verdicts.
The Information Deficit of Black-Box Monitoring
To understand why monitors get stuck, consider a simple liveness property: "Every request must eventually receive an acknowledgment." If a monitor observes a request followed by ten seconds of silence, has the property been violated? Not necessarily—the acknowledgment might arrive in the eleventh second.
As noted by Alan Perotti et al. in Runtime Verification Through Forward Chaining, traditional verification tools struggle to resolve truth values incrementally on expanding data streams. They are forced to remain in an undecided state until the trace fully concludes. This lack of real-time resolution prevents early fault detection.
This issue is not just a quirk of simple temporal logics. Andrea Brunello et al. demonstrate in Learning What to Monitor: Using Machine Learning to Improve past STL Monitoring that many formal specifications are inherently unmonitorable in real-time because their verdicts depend on future events that have not yet occurred. When a monitor treats a system as a pure black box, it has no way to look ahead or infer whether a violation is truly inevitable.
The Multi-Trace Blindspot: Hyperproperties
The information deficit worsens dramatically when moving from standard properties (which look at a single execution trace) to hyperproperties (which compare relationships between multiple execution traces). Hyperproperties are essential for enforcing security and privacy policies like non-interference (ensuring secret inputs do not affect observable outputs).
Parallel Monitoring (Decidable)
Trace 1: ---A---B---X--->
Trace 2: ---A---B---Y---> <- Monitor sees both simultaneously
Sequential Monitoring (Undecidable)
Session 1: ---A---B---X---> (Stored in memory)
Session 2: ??? <- Monitor must guess if future traces will match
Monitoring hyperproperties introduces severe decidability hurdles. As Bernd Finkbeiner et al. explain in Monitoring hyperproperties, properties that contain alternating quantifiers—such as "for every execution trace, there exists a corresponding trace that masks its sensitive data"—are incredibly difficult to evaluate on sequential data streams.
If traces arrive one after another over time, how can a monitor validate an existential requirement? In Runtime Enforcement of Hyperproperties, the authors prove that runtime enforcement in sequential models is generally undecidable. Because the monitor or enforcer lacks knowledge of the total number and nature of future traces, it cannot guarantee that a correction or verdict made in the current session will remain consistent with an unknown number of future executions.
This boundary becomes even more restrictive when scaling to multi-agent systems. Raven Beutner et al. explore this in Monitoring Second-Order Hyperproperties, which reasons about sets of sets of traces (useful for verifying concepts like "common knowledge"). They show that when system traces arrive one by one indefinitely, determining whether a second-order property is satisfied is fundamentally undecidable, creating an absolute barrier for pure black-box monitors in open-ended environments.
Opening the Box: Gray-Box and Assumption-Based Monitoring
If a pure black-box monitor cannot collect enough information from a finite trace to issue a verdict, the logical solution is to give the monitor more context about the system it is watching.
One powerful manifestation of this idea is gray-box monitoring. In Gray-Box Monitoring of Hyperproperties, Sandro Stucki et al. bypass the black-box limitation by combining real-time runtime observations with a limited static analysis of the system's internal source code.
By knowing the internal control flow and potential behaviors of the system, the gray-box monitor can reason about paths the system could take in the future. This allows it to definitively verify complex privacy policies and alternating-quantifier hyperproperties that are completely unmonitorable from the outside. However, as the authors note in their follow-up work, Gray-box monitoring of hyperproperties with an application to privacy, this approach still faces limits: if the system's input domain is infinite, verifying absolute satisfaction remains impossible because the monitor cannot simulate an unbounded number of future behaviors.
Another way to inject context is through Assumption-Based Runtime Verification (ABRV). Instead of analyzing source code, this approach equips the monitor with a formal model of the environment or the system's expected behavior.
Black-Box RV: [Finite Trace] -------->? [Unknown Verdict]
Assumption RV: [Finite Trace] + [Timed Automata Model] ---> [Early Pass/Fail]
In Exploiting Assumptions for Effective Monitoring of Real-Time Properties under Partial Observability, Thomas M. Grosen et al. use Timed Automata to model expected system constraints. When a system is only partially observable, a traditional monitor stays stuck in an inconclusive state. An assumption-based monitor, however, uses the model to mathematically rule out impossible future paths, allowing it to issue definitive success or failure verdicts much earlier than assumption-free methods.
This strategy is equally effective at resolving physical real-time uncertainties. When communication networks introduce latency and jitter, a monitor might receive events with distorted timestamps, leading to false alarms or inconclusive states. Martin Fränzle et al. address this in Efficient Runtime Verification of Real-Time Systems under Parametric Communication Delays. By utilizing symbolic execution and zone-based clock tracking, their framework isolates delay-induced artifacts from genuine system violations, successfully extracting definitive pass or fail verdicts despite timing ambiguity.
Redefining Verdicts and Monitorability Boundaries
When structural changes to the monitor are not enough to eliminate uncertainty, researchers look to change the underlying mathematical language of the verdicts themselves.
If a binary "true/false" logic forces a monitor into a permanent "unknown" state during an infinite execution, why not use a more expressive logic? Corto Mascle et al. tackle this in From LTL to rLTL monitoring: improved monitorability through robust semantics. They replace standard Linear Temporal Logic (LTL) with Robust LTL (rLTL), which operates on a five-valued semantics. Instead of throwing its hands up with an "unknown" verdict, an rLTL monitor provides nuanced feedback—essentially "shades of violation"—giving operators actionable, safety-critical data even when the final outcome of an infinite execution remains technically uncertain.
Ultimately, these engineering solutions have driven a deeper theoretical question: How can we know, before running a system, whether a given property can ever be conclusively monitored?
Thomas Møller Grosen et al. provide a definitive answer to this in Time for Timed Monitorability. They map out the exact boundaries of "timed monitorability" within real-time systems. While the problem is completely undecidable for general, nondeterministic timed systems, the authors prove it is fully decidable for deterministic ones.
More importantly, they introduce the concept of time-horizon verdicts. This allows a monitor to analyze a property and predict exactly how much time must elapse before it can provide a useful answer. By calculating these horizons, engineers can finally determine whether a runtime monitor will be an effective real-time guardian or if it is mathematically doomed to remain silent.
Key Foundational Work
Gray-Box Monitoring of Hyperproperties (2019) — contributed 4 concept elements to this direction.
Monitoring hyperproperties (2019) — contributed 1 concept elements to this direction.
Runtime Verification Through Forward Chaining (2014) — contributed 1 concept elements to this direction.