💻 computer science

Synchronous Observers Revisited for Runtime Verification of Lustre Using STL

This paper presents a technique for compiling the synchronous fragment of Signal Temporal Logic (SSTL) into modular synchronous observers within the Lustre language, enabling both runtime and static verification of cyber-physical systems while supporting arbitrary nesting of bounded properties and a globally unbounded outer operator for online monitoring.

Original authors: Logan Kenwright, Partha Roop, Sobhan Chatterjee, Nathan Allen

Published 2026-08-14

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Logan Kenwright, Partha Roop, Sobhan Chatterjee, Nathan Allen

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 building a robot that drives a car, or a drone that delivers packages. These machines live in a world of continuous motion, but their brains are digital computers that think in tiny, discrete steps, like frames in a movie. To keep them safe, engineers write rules: "Never get closer than 6 meters to the car ahead," or "If you hit a bump, you must be back on track within 4 seconds." Checking if these rules are followed is tricky. You can't just look at the whole future at once because the robot doesn't know what's coming next. You have to watch it tick-by-tick, like a referee blowing a whistle only when a foul is certain, not when it's just a maybe.

This is where a field called "Runtime Verification" comes in. It's like having a super-vigilant co-pilot that watches the robot's every move in real-time. The rules are often written in a special language called Signal Temporal Logic (STL), which is great for describing time-based rules. However, there's a catch: most tools that check these rules are like separate auditors who look at a recording after the fact, or they use a different language than the robot's brain. This creates a gap. If the auditor speaks a different language, you can't be 100% sure the robot is actually following the rules while it's driving. You need a co-pilot that speaks the exact same language as the driver, thinks at the exact same speed, and can say "I'm sure it's safe," "I'm sure it's a crash," or "I'm still waiting to see" right in the moment.

This paper introduces a clever new way to build that perfect co-pilot. The authors, working with a language called Lustre (a standard tool for building safety-critical software), created a technique to turn complex, nested time-rules directly into code that runs alongside the robot. Think of it as translating a complicated set of instructions into a native app that lives inside the robot's brain.

The big breakthrough here is handling "nested" rules. Imagine a rule that says, "At every moment in the next 10 seconds, you must be able to find a safe spot within the next 4 seconds." This is a rule inside a rule. Previous tools struggled with this complexity or couldn't run them in real-time. The authors' method breaks these complex rules down into a team of tiny, simple watchers (called "leaves") that work together. Each watcher has a specific job: it watches for a specific event within a specific time window. If the event happens, it shouts "Yes!"; if the window closes and it didn't happen, it shouts "No!"; and if it's still waiting, it says "Unknown."

What makes this special is how they handle the "Unknown" state. Instead of getting stuck or guessing, the system uses a "three-valued" logic. It knows exactly when it has enough information to make a final decision. For example, if a rule requires a safe gap to be maintained for 5 seconds, the system doesn't have to wait until the full 5 seconds are up to know if a violation is impossible. If the car crashes at second 2, the system knows immediately it's a "No." If the car stays safe for 3 seconds but the window is still open, it says "Unknown" until the window closes. This allows the system to give a definitive answer earlier than the total time limit of the rule, which is a huge win for safety.

The authors tested this on two scenarios: a bouncing spring-mass system (like a car suspension) and a self-driving car following another car that slams on its brakes. They showed that their system could catch safety violations in real-time, often deciding the outcome several "ticks" (time steps) before the rule's deadline would have forced a decision. They also built a fun, interactive visualizer that lets you watch these nested rules unfold on a screen, showing exactly which part of the rule was satisfied and when.

Crucially, because this "co-pilot" is written in the exact same language as the robot, it can be checked by a model checker (a tool that mathematically proves software is bug-free) before the robot ever leaves the factory. This means the same piece of code serves two masters: it acts as a live safety monitor while the robot is running, and it acts as a mathematical proof of safety before it starts. The authors proved that their method is sound and complete, meaning it never misses a violation and never gives a false alarm, provided the rules stay within the "bounded" time limits they designed for. They even showed that while the system can't predict the infinite future, it can effectively watch for violations in systems that run forever by using a clever "shift register" trick that recycles old watchers for new moments in time.

In short, this paper bridges the gap between complex time-based rules and real-world execution. It turns abstract logic into a living, breathing part of the machine, allowing for safer, more reliable cyber-physical systems that can prove they are safe while they are actually working.

Technical Summary: Synchronous Observers Revisited for Runtime Verification of Lustre Using STL

Problem Statement
Signal Temporal Logic (STL) is a standard formalism for specifying temporal safety properties in cyber-physical systems (CPS), particularly for runtime verification. However, existing STL tooling typically operates on pre-recorded or simulated signals, or on abstract automaton models, rather than on the executable code actually deployed. Consequently, there is a lack of an executable, runtime-equivalent semantics for nested STL properties that runs in lock-step with the monitored system. Furthermore, while synchronous languages like Lustre use "synchronous observers" for static verification, the potential of these observers for runtime verification has been underexplored. A specific challenge lies in handling the "three-valued" nature of online monitoring: because bounded temporal operators look into the future, a monitor cannot always decide a property immediately upon a tick, leading to a delay before a definitive verdict is reached.

Methodology
The authors propose a technique to compile the synchronous fragment of STL (SSTL) directly into synchronous observers within the dataflow language Lustre. The core of the methodology involves "unrolling" nested formulas into a finite collection of non-nested obligations, each monitoring a fixed window of discrete time ticks.

Three-Valued Streaming Semantics: The approach adopts a Kleene three-valued semantics (def_true, def_false, unknown). At each tick, the observer emits a verdict based on the prefix observed so far. Unknown indicates that the formula horizon has not yet elapsed. This is implemented using a pair of Boolean signals (pos, neg) representing definitive truth and definitive falsehood, respectively.
Primitive Construction (until_leaf): The authors synthesize a single reusable Lustre node, until_leaf, which implements the bounded "until" operator ( $U_{[a,b]}$ ). This primitive tracks a precondition (the "alive" signal) and a postcondition (the "found" signal) over a specific window. It emits def_true upon finding a witness and def_false either via early termination (precondition failure) or window expiry.
Recursive Synthesis: Nested formulas are synthesized bottom-up. The system instantiates copies of the until_leaf primitive for every starting tick required by the outer operators. These copies are wired together using Kleene logic rules for conjunction, disjunction, and negation.
- For bounded operators ( $\square_{[a,b]}$ , $\diamond_{[a,b]}$ ), the synthesis unrolls the formula into a set of leaves corresponding to each start offset within the interval.
- For the unbounded Globally operator ( $\square$ ), which is common in free-running systems, the authors introduce a shift-register construction. Instead of instantiating infinite observers, a register of size $H+1$ (where $H$ is the inner horizon) recycles state, allowing the monitor to track the "alive" copies of the inner formula indefinitely.
Visualisation: An interactive, browser-based tool is provided to render the three-valued verdicts of nested observers over editable traces, aiding in the debugging and intuition of complex, nested temporal behaviors.

Key Contributions

Executable Online Monitoring: The technique synthesizes observers that are compiled together with the system in the same synchronous language (Lustre), running in lock-step with the actual executable code rather than on simulated data.
Arbitrary Nesting with Modular Compilation: Unlike prior work (e.g., Bellanger et al.) which was limited to non-nested operators, this method supports arbitrary nesting of bounded SSTL properties.
Unbounded Outer Operator: The approach admits a globally unbounded outer operator ( $\square$ ) suitable for monitoring free-running systems, while keeping the inner structure bounded.
Dual Utility: The resulting observers serve a dual purpose: they function as runtime monitors and, as a by-product, serve as static verification obligations for the Kind2 model checker without requiring a separate model.
Three-Valued Semantics for Runtime: The implementation provides causal Kleene verdicts, allowing monitors to commit to definitive answers as early as the trace permits, often before the full formula horizon is reached.

Results and Evaluation
The authors evaluated the technique on two case studies: a spring-mass system and a car-following adaptive cruise control (ACC) scenario with emergency braking.

Correctness: All synthesized observers were verified against the Kind2 model checker. Runtime and static verdicts agreed on every property, including the mutual-exclusion invariant ( $pos \land neg = \text{false}$ ).
Performance: The observers were compiled to C and executed via the lv6 interpreter. Per-tick execution costs were measured in nanoseconds (ranging from ~6.7 ns to ~206.5 ns depending on complexity), well below typical millisecond-scale control periods, confirming feasibility for online deployment.
Early Termination: The three-valued semantics proved effective; in the case studies, bounded properties settled to definitive verdicts strictly before their theoretical horizons. For instance, a deeply nested property ( $P3$ ) settled 15 ticks early.
Unbounded Behavior: The unbounded $\square$ operator functioned as a falsification-only mechanism, correctly latching to def_false when violations occurred (e.g., gap dropping below safety thresholds) and remaining unknown otherwise.

Significance and Claims
The paper claims to bridge the gap between formal specification and executable runtime monitoring for synchronous CPS. By synthesizing observers directly in the system's language, the authors eliminate the "modelling gap" often found when verifying abstract models against deployed code. The work demonstrates that complex, nested temporal properties can be monitored online with low latency and high reliability. The authors position their work as an extension of Bellanger et al. [5], specifically addressing the limitations regarding nesting depth and the orientation toward static-only verification. The contribution is presented as a systematic synthesis technique that is sound and complete with respect to the explicit three-valued semantics, validated through both runtime execution and static model checking.

Limitations
The authors acknowledge three primary limitations:

State Explosion: The number of leaves is the product of window widths, which can cause the observer size to grow exponentially with large intervals (e.g., $\diamond_{[0,100]}$ ).
Closed-System Assumption: The case studies modeled the plant within Lustre as a closed system. Monitoring genuine open systems with external sensor inputs remains a future step.
Discrete Domain: The current approach operates strictly within the sampled, discretized domain and does not yet support continuous STL robustness semantics.

More like this