Traditional software engineering relies heavily on design-time validation. We write tests, run simulations, and sometimes use formal methods to mathematically prove that a system's design meets its specifications. However, when complex systems—such as autonomous aircraft, self-driving cars, or medical devices—encounter the open world, this design-time safety net begins to fray.
Static analysis cannot easily predict hardware glitches, unexpected interactions in multi-vendor device networks, or the unpredictable distribution shifts of machine learning models. As argued by David Garlan in Software engineering for self-adaptive systems:research challenges in the provision of assurances, autonomous and adaptive systems require a shift toward perpetual assurance—a continuous process of evidence gathering and verification integrated directly into the system's operational lifecycle.
This is the core intuition behind runtime verification: instead of trying to prove that a system will never fail under any future circumstance, we deploy a lightweight, independent observer alongside the running system. This observer continuously monitors live execution traces against formal specifications, acting as a dynamic safety net that can trigger fallbacks or safe handovers the moment a violation occurs.
The Reality Gap and Why Static Proofs Fall Short
To understand why runtime verification is necessary, consider a cyber-physical system (CPS) verified using traditional formal models. A mathematical proof of safety is only as good as the assumptions it makes about the physical world.
Stefan Mitsch et al. describe this as a fundamental gap in ModelPlex: verified runtime validation of verified cyber-physical system models. A controller might be provably safe under the assumption that a vehicle's brakes always provide a specific deceleration rate. If the road is icy or the hardware degrades, the physical system drifts away from its verified mathematical model.
Similarly, in concurrent programming, Jiannong Cao et al. note in Run-Time Fault Detection in Monitor Based Concurrent Programming that properties like external consistency depend entirely on the unpredictable sequences of calls made by external users, making dynamic observation a necessity.
+--------------------------------------------------------+
| DESIGN-TIME PROOFS |
| [Formal Model] ---> Mathematically Provable Safety |
+--------------------------------------------------------+
|
| The "Reality Gap" (Icy roads,
v hardware glitches, AI shifts)
+--------------------------------------------------------+
| RUNTIME EXECUTION |
| [Physical System] ---> Real-time Behavior Deviates |
+--------------------------------------------------------+
|
v
+--------------------------------------------------------+
| RUNTIME VERIFICATION |
| [Active Monitor] ---> Detects Deviation & Intervenes |
+--------------------------------------------------------+
This gap widens dramatically when machine learning is introduced. As highlighted by David Fernández Llorca et al. in Testing autonomous vehicles and AI: perspectives and challenges from cybersecurity, transparency, robustness and fairness, the opacity and sensitivity to environmental noise of "black-box" AI components necessitate a transition from static certification to continuous, in-service monitoring. When exhaustive design-time verification is impossible due to environmental unpredictability, active observers must track execution in real-time to manage dynamic system behavior (Stefan Wagner et al. in Verlässliche Software im 21. Jahrhundert).
How It Works: Stream and Trace Monitoring
A runtime monitor operates by consuming a stream of events generated by the target system and evaluating whether this stream satisfies a formal property. To be practical for safety-critical applications, the monitor must satisfy two strict constraints:
- Zero or negligible overhead: It must not disrupt the timing or performance of the primary controller.
- Deterministic resource bounds: It must operate within constant memory and time bounds so it cannot cause system crashes.
Incremental State Transitions
Instead of storing an ever-growing history of execution traces, efficient monitors use automata-based or stream-based representations to evaluate properties incrementally. For instance, Marek Chalupa et al. introduce prefix transducers in Monitoring Hyperproperties With Prefix Transducers to maintain a dynamic collection of active configurations that consume incoming events step-by-step. This allows the system to check complex logical conditions across multiple traces linearly as the system evolves.
To feed data into these monitors, the underlying system is instrumented to emit atomic propositions as events whenever specific code locations are hit or state variables change (Ruijie Meng et al. in Finding Counterexamples of Temporal Logic properties in Software Implementations via Greybox Fuzzing).
System Execution: (State A) --[Event 1]--> (State B) --[Event 2]--> (State C)
| |
v v
Monitor Pipeline: [Emit Prop 1] [Emit Prop 2]
| |
v v
Incremental Update Incremental Update
(Constant Memory) (Constant Memory)
| |
v v
Verdict: SATISFIED Verdict: VIOLATION!
Stream-Based Specification Languages
A prominent approach to implementing this is through stream-based monitoring languages like Lola and RTLola. As demonstrated by Florian‐Michael Adolf et al. in Stream Runtime Monitoring on UAS, these frameworks formalize system requirements into executable monitors that process high-frequency data streams with constant memory usage.
To achieve complete isolation from the primary system, Bernd Finkbeiner et al. demonstrated in RTLola Cleared for Take-Off: Monitoring Autonomous Aircraft that these stream-based specifications can be translated directly into dedicated FPGA hardware. This hardware-level monitoring guarantees zero timing interference with the flight controller while continuously checking for sensor failures or geo-fencing violations.
Synthesizing Correct-by-Construction Monitors
If the runtime monitor is responsible for system safety, how do we ensure the monitor itself is correct? Writing monitor logic by hand introduces human error. The field solves this by automatically compiling monitors directly from formal specifications or design-time models.
Compiling Proofs into Monitors
In the ModelPlex framework (Stefan Mitsch et al.), runtime monitors are derived directly from offline differential dynamic logic safety proofs. The monitor acts as a verified compliance checker: if the physical system behaves in a way that violates the assumptions of the mathematical proof, the monitor immediately flags it.
As shown by Megan Strauss et al. in Slow Down, Move Over: A Case Study in Formal Verification, Refinement, and Testing of the Responsibility-Sensitive Safety Model for Self-Driving Cars, these formally derived monitors can identify violations of safety logic before a physical collision occurs, serving as an early diagnostic layer that bridges high-level models and real-world code.
Similarly, global architectural or trace-based constraints can be decomposed into local, incremental state machines. Adwait Godbole et al. demonstrate this in Automated Conversion of Axiomatic to Operational Models: Theory and Practice, converting axiomatic rules into operational "axiom automata" that track state transitions during execution to catch violations early.
Predictive and Model-Based Monitoring
Monitors can also leverage predictive models to look a few steps into the future. In Model predictive monitoring of dynamical systems for signal temporal logic specifications, Xiang Yin et al. utilize a known model of system dynamics to check whether the current state belongs to a pre-computed "feasible set" for the active specification. If the state drifts outside this set, a future violation is guaranteed, buying the system precious time to react.
Where explicit models are missing, they can be mined on the fly. Ayan Banerjee et al. in Toward Operational Safety Verification of AI-Enabled CPS (Student Abstract) propose periodically mining new behavioral Hybrid Automata models from real-time execution traces and comparing them against manufacturer baselines to detect unverified states caused by distribution shifts.
Enforcing Safety: Shields and Fallbacks
Detecting a violation is only half the battle; a runtime verification framework must also know how to respond. Depending on the architecture, monitors can act passively (reporting bugs without halting execution, as explored in Integrating Interobject Scenarios with Intraobject Statecharts for Developing Reactive Systems) or actively (intervening to enforce safety).
Shielding and Recoverability
In active monitoring, the verification layer acts as a "shield" or a parallel safety net. This is particularly valuable for protecting learning-enabled components. Anna Lukina in Combining Runtime Monitoring and Machine Learning with Human Feedback describes using an independent monitoring component to evaluate system behavior against formal properties in parallel, avoiding the need to formally prove the primary controller's entire complex state space.
+-----------------------+
| Human / Environment |
+-----------------------+
|
v (Current State)
+-----------------------------------------------------------------+
| SHIELDED ARCHITECTURE |
| |
| +--------------------+ |
| | Primary Controller | ---(Proposed Action)---> [ SHIELD ] |
| | (e.g., Black-box | | |
| | Neural Network) | | Evaluates safety/ |
| +--------------------+ | recoverability |
| v |
| Safe Action? |
| / \ |
| (Yes) (No) |
| / \ |
| v v |
| Execute Action Override with |
| Fallback Strategy|
+-----------------------------------------------------------------+
This concept is formalized by Osbert Bastani et al. in Safe Reinforcement Learning via Statistical Model Predictive Shielding. Instead of restricting a robot's performance with overly conservative static boundaries, their framework evaluates safety at each individual time step based on the current state. By performing real-time recoverability checks, the shield allows the high-performance black-box policy to run unimpeded unless it proposes an action that would lead to an irrecoverable state, at which point the shield overrides it with a safe fallback strategy.
Asynchronous Monitoring and State Compensation
When synchronous shielding is too computationally expensive, systems can use asynchronous monitoring. As outlined by Oleg Sokolsky et al. in Introduction to the special issue on runtime verification, asynchronous monitoring allows the primary system to continue executing high-throughput tasks while property checking occurs in parallel. If the monitor discovers a violation retroactively, it utilizes a state compensation mechanism to "unroll" or compensate for the unsafe state transitions, offering a tunable balance between system performance and safety assurance.
Dynamic and Scenario-Based Certification
The ultimate realization of runtime verification is a shift in how safety-critical systems are certified by regulators. In highly dynamic environments—such as smart hospitals or edge-cloud networks—components change constantly, making static, one-time deployment certificates obsolete (Achim P. Karduck et al. in Editorial).
To solve this for medical settings, Insup Lee 0001 et al. propose scenario-based certification in Challenges in the regulatory approval of medical cyber-physical systems. Instead of certifying a static combination of hardware devices, regulators certify the clinical scenario itself. When heterogeneous devices are connected dynamically at a patient's bedside, a centralized software supervisor monitors the network at runtime, continuously verifying that the connected components adhere to the certified scenario's safety assumptions.
By moving the enforcement of formal specifications from design-time abstractions to real-time execution streams, runtime verification provides the mathematical machinery necessary to keep autonomous, adaptive, and complex systems operating safely in an unpredictable world.
Key Foundational Work
Run-Time Fault Detection in Monitor Based Concurrent Programming (2001) — contributed 2 concept elements to this direction.
Reflective Analysis and Design for Adapting Object Run-Time Behavior (2002) — contributed 1 concept elements to this direction.