🤖 AI

Runtime Enforcement of Hybrid System Properties

This paper proposes a runtime enforcement framework for hybrid systems that utilizes Hybrid Automata and online reachability analysis to synthesize corrective actions—such as event suppression, delay, or insertion—ensuring safety compliance in real-time reactive systems like Adaptive Cruise Control with minimal computational overhead.

Original authors: Mir Md Sajid Sarwar, Srinivas Pinisetty, Rajarshi Ray, Thierry Jéron

Published 2026-06-11

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Mir Md Sajid Sarwar, Srinivas Pinisetty, Rajarshi Ray, Thierry Jéron

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are driving a high-tech car that has a very smart, but sometimes reckless, autopilot. This autopilot (the "controller") is constantly telling the car to speed up, slow down, or cruise. However, the autopilot doesn't always know the exact distance to the car in front of it, or it might make a mistake that causes a crash.

This paper introduces a safety guardian that sits between the reckless autopilot and the road. Its job isn't just to watch and say, "Oh no, you crashed!" (that's just a camera recording a crash). Instead, this guardian actively intervenes to stop the crash before it happens.

Here is how the paper explains this guardian, using simple analogies:

1. The Problem: The "Stop-and-Go" Guardian vs. The "Smooth Flow" Guardian

Most existing safety systems work like a stop-and-go traffic light. They only check the car's speed and distance at specific, fixed moments (like every second). If the car is safe at 1:00 and safe at 2:00, they assume it was safe the whole time.

But cars move continuously. Between 1:00 and 2:00, the car could have zoomed forward and hit the car in front, then slowed down again. A "stop-and-go" guardian misses this.

This paper proposes a new kind of guardian that works like a smooth-flowing river. It doesn't just check at the ticks of the clock; it watches the car's movement continuously in between the ticks. It understands that the car is a "hybrid" system: it has digital commands (like "press brake") and physical reality (speed, distance, and acceleration happening all at once).

2. The Tool: The "Hybrid Automaton" Map

To do this, the authors use a mathematical map called a Hybrid Automaton.

Think of this map as a rulebook for a video game.
The game has different "modes" (like Accelerating, Cruising, or Braking).
The map has strict rules for each mode. For example, in Accelerating mode, you can only go fast if you are far away from the car in front.
If the car gets too close, the map says, "STOP! You are entering the 'Crash Zone' (the Sink)."

The guardian uses this map to predict the future. It asks: "If I let the autopilot's command happen right now, will we slide off the map into the Crash Zone?"

3. The Magic Tricks: How the Guardian Fixes Mistakes

When the guardian sees the autopilot about to make a mistake, it has three magic tools to fix it instantly:

The Pause Button (Delay): The autopilot says, "Speed up!" at 1.0 seconds. The guardian says, "Not yet! Wait until 1.29 seconds when the car in front is far enough away." It holds the command in a buffer and releases it at the perfect moment.
The Eraser (Suppression): The autopilot says, "Speed up!" at 9.0 seconds, but the car is too close. The guardian says, "Nope," and simply deletes that command. It replaces it with a "do nothing" command (called a stutter), letting the car coast safely instead.
The Ghost Driver (Insertion): Sometimes, the autopilot is silent, but the car is drifting toward danger. The guardian doesn't wait for a command; it inserts a new one. It says, "Since you aren't doing anything, I will tell the car to 'Cruise' or 'Brake' right now to keep us safe."

4. The Real-World Test: Adaptive Cruise Control

The authors tested this on a Self-Driving Car's Cruise Control.

The Scenario: The car's main computer was faulty and kept telling the car to accelerate even when it was getting dangerously close to the car ahead.
The Result: Without the guardian, the car crashed (the distance dropped below 10 meters).
With the Guardian: The guardian watched the speed and distance continuously. It delayed some acceleration commands, erased others, and inserted braking commands in between the regular checks. The car stayed safe, never getting closer than 10 meters to the car in front.

5. Why It Matters

The paper claims this system is incredibly fast. It adds almost no delay to the car's thinking process (only about 4.67 milliseconds per check). This means it can be used in real-time on actual cars without slowing them down.

In summary: This paper builds a "smart safety net" for complex machines like self-driving cars. Unlike older systems that only check the rules at fixed times, this net watches the machine move continuously, predicting danger and instantly editing the machine's commands (pausing, deleting, or adding actions) to ensure it never breaks the safety rules.

Technical Summary: Runtime Enforcement of Hybrid System Properties

Problem Statement

Autonomous and cyber-physical systems (CPS) operate in uncertain, dynamic environments where traditional design-time verification (formal verification, simulation) is often insufficient to guarantee safety. While Runtime Verification (RV) can detect property violations during execution, it is passive and does not prevent them. Runtime Enforcement (RE) addresses this by actively intervening to modify system behavior. However, existing RE frameworks face significant limitations when applied to complex reactive systems:

Discrete vs. Continuous Dynamics: Most frameworks rely on untimed or discrete-time specifications (e.g., Discrete Timed Automata). These are inadequate for systems exhibiting complex continuous dynamics, as they cannot model dense-time evolution or intervene between discrete sampling points.
Intervention Granularity: Existing approaches are often restricted to delaying or suppressing events at discrete time instants. They lack the capability to insert events at arbitrary time instants or perform continuous-time monitoring, which is critical for maintaining safety in systems with continuous state trajectories.
Reactive System Constraints: Many enforcement mechanisms (e.g., halting execution or long buffering) are infeasible for reactive systems that require instantaneous responses to maintain liveness and meet strict timing constraints.

The core problem addressed is the lack of a runtime enforcement framework capable of handling safety properties specified as Hybrid Automata (HA), enabling continuous-time monitoring and proactive, fine-grained corrective interventions (suppression, delay, and insertion) for reactive systems.

Methodology

The paper proposes a runtime enforcement framework where safety requirements are modeled using Safety Hybrid Automata (HA). This formalism captures both discrete execution steps (via transition guards) and continuous dynamics (via differential equations and state invariants).

Core Components

Safety Hybrid Automaton (S): The property $\phi$ is formalized as an HA with a unique non-accepting "Sink" (trap) location. Transitions to the Sink occur whenever a safety invariant (e.g., minimum distance) is violated. All other locations are accepting.
Enforcer Function ( $E_\phi$ ): The enforcer acts as a layer between the System under Monitor (SuM) and the environment. It receives a stream of input events and environmental states at discrete synchronization points (clock ticks, denoted as $ptick$).
Corrective Actions: The enforcer synthesizes a corrected output stream by:
- Suppressing: Dropping an unsafe event and emitting a "stutter" event to maintain the previous state.
- Delaying: Postponing an event to a later time when the guard condition is satisfied.
- Inserting: Proactively inserting a new event at an arbitrary time instant (even between $pticks$) to prevent an imminent invariant violation.
Online Algorithm: The enforcement algorithm operates in a synchronous reactive loop:
- Initialization: The HA is initialized based on the current environmental state.
- Time Elapse: The algorithm simulates the continuous evolution of the system state over the time interval until the next event or $ptick$.
- Invariant Checking: It verifies if the continuous trajectory remains within the current location's invariant.
- Decision Logic:
  - If the invariant holds and the guard for the incoming event is satisfied, the event is passed through.
  - If the invariant holds but the guard is not satisfied, the event is suppressed (delayed).
  - If the invariant is violated, the algorithm checks for enabled delayed actions. If none exist, it synthesizes and inserts a new action (from the set of enabled transitions) to steer the system back to a safe state before the next $ptick$.

Formal Constraints

The enforcer is defined to satisfy four key constraints:

Soundness: The output sequence must always satisfy the safety property $\phi$ .
Instantaneity: The enforcer must react immediately to inputs and can insert events proactively.
Monotonicity: The output for an extended input sequence must be a continuation of the output for the prefix.
Transparency: The enforcer intervenes minimally; if the system behavior is safe, the enforcer acts as an identity function.

Key Contributions

Novel Framework: A runtime enforcement framework for reactive CPS based on Hybrid Automata specifications, enabling continuous-time monitoring and corrective intervention.
Formal Definition: A formal definition of the runtime enforcement problem for safety properties specified via Safety Hybrid Automata, extending RE beyond untimed and discrete-time formalisms.
Enforceability Conditions: The establishment of conditions for enforceability, requiring that from every non-violating state, an accepting state must be reachable via enabled transitions.
Online Algorithm: An algorithm capable of synthesizing safe execution traces through event suppression, delay, and insertion while respecting system timing constraints.
Case Study: A detailed application to an Adaptive Cruise Control (ACC) system, demonstrating the synthesis of safe traces from potentially faulty controller outputs.

Results and Evaluation

The proposed framework was evaluated using an Adaptive Cruise Control (ACC) scenario where the primary controller was assumed to be faulty, potentially issuing commands that violate a minimum safe distance constraint ( $d > 10$ meters).

Scenario: The system monitored variables including acceleration ( $a$ ), velocity ( $v$ ), and relative distance ( $d$ ). The controller generated a sequence of events (accelerate, cruise, etc.) that, without intervention, led to a collision (distance $< 10$ m).
Enforcement Outcome: The enforcer successfully intercepted the unsafe event stream. It suppressed unsafe acceleration commands, delayed others, and inserted deceleration commands at precise time instants (e.g., $t \approx 10.67$ ) to maintain the safety invariant.
Performance:
- Latency: The average response time per event was 4.67 milliseconds.
- Overhead: The framework introduced negligible computational overhead, processing the entire trace in 15.098 seconds on standard hardware (Intel Core i5, 8GB RAM).
- Conclusion: The results confirm the framework's ability to operate effectively in high-frequency reactive environments without violating strict timing constraints.

Significance and Claims

The paper claims that its primary significance lies in bridging the gap between discrete-time enforcement and the continuous nature of cyber-physical systems. By utilizing Hybrid Automata, the framework:

Enables dense-time monitoring between discrete sampling points, a capability missing in Discrete Timed Automata (DTA) approaches.
Allows for proactive intervention (insertion of events) at arbitrary time instants, rather than being restricted to discrete ticks.
Provides finer-grained control over system behavior, ensuring continuous compliance with safety requirements in real-time.

The authors assert that, to their knowledge, no existing enforcement framework supports expressive HA specifications suitable for reactive systems. They position this work as a step toward stronger safety guarantees for autonomous systems operating in uncertain environments, moving beyond passive verification to active, continuous-time enforcement.

The paper remains modest regarding its scope, acknowledging that the current approach is limited to safety properties (prefix-closed specifications) and decidable subclasses of hybrid automata. Future work is identified as necessary for handling liveness properties, non-linear dynamics, stochastic uncertainty, and distributed multi-agent systems.