💬 NLP

Synchronous Signal Temporal Logic for Decidable Verification of Cyber-Physical Systems

This paper introduces Synchronous Signal Temporal Logic (SSTL), a decidable fragment of Signal Temporal Logic that leverages the Signal Invariance Hypothesis and translation to LTL_P to enable static verification of safety and liveness properties in cyber-physical systems, as demonstrated on a human heart model.

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

Published 2026-03-27

📖 4 min read☕ Coffee break read

CC BY 4.0

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

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 trying to write a rulebook for a very complex, life-saving machine, like a digital heart or a self-driving car. You want to make sure it never does something dangerous (Safety) and that it always keeps doing its job forever (Liveness).

The problem is that the real world is continuous. Time flows like a smooth river, and signals (like heartbeats or speed) change constantly. Trying to write a perfect rulebook for a smooth, flowing river using a computer is mathematically impossible to solve completely. It's like trying to count every single drop of water in a waterfall to prove the river will never run dry; there are too many drops, and the math gets stuck.

This paper introduces a clever solution called SSTL (Synchronous Signal Temporal Logic). Here is how it works, using simple analogies:

1. The Problem: The "Infinite River"

Traditional logic (STL) tries to check the machine's behavior at every single instant of time.

The Analogy: Imagine you are a security guard watching a river. You need to check if a dangerous fish appears at any point in the water. Since the water is continuous, you would have to check an infinite number of points. Your brain (the computer) would freeze trying to check them all. This is why the old method is "undecidable"—it can't give a yes/no answer.

2. The Solution: The "Stop-Motion Camera"

The authors propose switching from a smooth river to a Stop-Motion Movie.

The Analogy: Instead of watching the river flow smoothly, you take a photo of it every 1/1000th of a second. You only look at the water in those specific snapshots.
The Magic Trick (SIH): To make this fair, they introduce a rule called the Signal Invariance Hypothesis (SIH). This is like saying: "Between two photos, the water doesn't change enough to hide a monster."
- If you take photos fast enough (like a high-speed camera), you can be 100% sure that if a fish wasn't in the photo, it wasn't in the water between the photos either.
- This turns the "impossible" infinite river into a "solvable" list of discrete snapshots (ticks).

3. The Translation: Speaking "Computer"

Now that we have a list of snapshots, we need to check if the rules are followed. But computers speak a specific language (Model Checking).

The Analogy: The authors built a Translator.
- They take the complex rules written for the "smooth river" (STL).
- They translate them into a language the computer understands perfectly (called LTLP), which works with the "snapshots" (SSTL).
- It's like translating a poem written in flowing water into a checklist of bullet points. The meaning stays the same, but now a robot can read it.

4. The Test: The "Heart" and the "Traffic Light"

To prove this works, they tested it on three real-world scenarios:

The Heart: They modeled a 33-node human heart. They checked if the electrical signals (the heart's rhythm) happened at the right time.
- Result: The computer successfully verified that a healthy heart beats correctly and even detected when a "sick" heart (with a blockage) failed the rules.
Traffic Lights: They checked if two lights never turned green at the same time (Safety) and if cars eventually got a green light (Liveness).
Pedestrian Crossings: They checked if the wait time for a pedestrian was reasonable.

Why This Matters

Before this paper, we could only check safety rules for these systems if we made big, risky guesses (approximations). We couldn't check if the system would always keep working forever (Liveness) without getting stuck in math.

The Big Takeaway:
This paper gives us a way to turn the "impossible" math of continuous time into a "solvable" list of steps. By assuming the system is sampled fast enough (like a high-speed camera), we can use powerful computer tools to prove, with 100% certainty, that our cyber-physical systems (like pacemakers, self-driving cars, and robots) are safe and will keep working forever.

In short: They turned a smooth, uncountable river into a manageable set of stepping stones, allowing us to walk across it and check every single step for safety.

1. Problem Statement

Cyber-Physical Systems (CPS), such as autonomous vehicles and medical devices, operate in safety-critical environments where formal verification is essential. Signal Temporal Logic (STL) is the standard formalism for specifying temporal properties over continuous-time signals in CPS. However, the paper identifies a fundamental limitation:

Undecidability: Static verification of STL properties over continuous-time signals is generally undecidable.
Limitations of Existing Approaches:
- Runtime Verification: Only checks specific execution traces, missing potential failures in unexplored paths.
- Controller Synthesis: Often faces scalability issues for large systems.
- Over-approximation: While useful for safety properties, it struggles with liveness properties (ensuring "something good eventually happens") and often loses precision.
The Gap: There is a lack of a method that allows for decidable, static verification of both safety and liveness properties for CPS, bridging the gap between continuous physical reality and discrete digital implementation.

2. Methodology: Synchronous Signal Temporal Logic (SSTL)

The authors propose Synchronous Signal Temporal Logic (SSTL), a decidable fragment of STL designed for systems operating under discrete time steps (ticks). The methodology relies on three core pillars:

A. Time Discretization and the Signal Invariance Hypothesis (SIH)

Discretization: Continuous time $t \in \mathbb{R}_{\ge 0}$ is projected to discrete ticks $k \in \mathbb{N}_{\ge 0}$ via $[t] = \lfloor t / \Delta t \rfloor$ , where $\Delta t$ is the sampling period.
Signal Invariance Hypothesis (SIH): This is the crucial theoretical assumption. It posits that a signal remains invariant (constant) between two consecutive discrete ticks.
- Justification: Inspired by the "synchrony hypothesis" in synchronous programming and the Nyquist-Shannon sampling theorem. If the sampling rate is high enough (satisfying Nyquist) and the system reacts fast enough relative to the plant, no critical information is lost between samples.
- Implication: Under SIH, the discrete trace is a sound and complete abstraction of the continuous trace.

B. Syntax and Semantics of SSTL

SSTL redefines STL operators to operate over discrete time intervals.
Syntax: Formulas are constructed using predicates over signal values at discrete ticks, combined with logical operators ( $\neg, \land$ ) and temporal operators with bounded intervals (e.g., $U_{[[a],[b]]}$ , $\Diamond_{[[a],[b]]}$ ).
Equivalence: The paper proves (Theorem 3.6) that if a signal satisfies SIH, an STL formula $\varphi$ is satisfied by the continuous signal if and only if its SSTL counterpart $[\varphi]$ is satisfied by the discrete trace.

C. Translation to LTLP and Model Checking

To enable automated verification, SSTL is translated into Linear Temporal Logic with Predicates (LTLP), which can be verified using the SPIN model checker.

Translation Function ( $\tau$ ):
- Unbounded operators (e.g., $\Diamond$ , $\Box$ ) map directly to standard LTL operators.
- Bounded Operators: To handle time constraints (e.g., "within 180ms to 240ms"), the translation introduces a guard predicate within[a,b]. This predicate tracks the current tick $j$ relative to the entry tick $j_0$ of a temporal obligation: $(j_0 + a \le j \le j_0 + b)$ .
- Nested formulas are handled recursively, with each bounded operator maintaining its own $j_0$ counter.
Decidability: Since LTLP over finite-state systems is decidable, and SSTL maps to LTLP under SIH, SSTL verification is proven to be decidable (Lemma 4.10).
Implementation: The system is modeled in Promela (SPIN's language) with embedded C code for continuous dynamics. Variables are discretized (e.g., floating-point values scaled to integers) to ensure a finite state space for SPIN.

3. Key Contributions

First Synchronous Abstraction of STL: Introduction of SSTL, the first discrete-time logic specifically designed to provide a sound and complete abstraction of STL for CPS.
Formal Equivalence Proof: Proof that under the Signal Invariance Hypothesis (SIH), SSTL is equivalent to STL, enabling the verification of continuous-time properties using discrete methods.
Decidable Verification Framework: A complete pipeline translating SSTL to LTLP, enabling the use of existing, robust model checkers (SPIN) for both safety (nothing bad happens) and liveness (something good eventually happens) properties.
Case Study Validation: Successful application of the framework to a complex 33-node human heart model, verifying critical physiological timing constraints (AV conduction, refractory periods) and liveness properties.

4. Results and Evaluation

The authors evaluated SSTL on three case studies of increasing complexity:

Case Study	System Type	Key Findings	Verification Time
Traffic Light Controller	Finite State Machine	Verified safety (mutual exclusion) and liveness. Detected a fairness violation in the model.	~1.5s
Pedestrian Crossing	Discrete with Integer Signals	Verified mixed boolean/integer signals and queue bounds. Identified faults in bounded response properties quickly.	2s – 309s
33-Node Heart Model	Continuous Dynamics (C)	Verified AV conduction delays (180-240ms) and refractory periods. Successfully distinguished between healthy and diseased (conduction block) models.	6.4s – 65.9s

Disease Detection: The framework successfully identified that specific heart diseases (AV block, LBB, RBB) violated the AV conduction safety property while maintaining liveness, demonstrating its diagnostic utility.
Performance: Verification times were practical (seconds to minutes). Memory usage was high for complex models (up to 9GB) but manageable with SPIN's optimization features.
Correctness: All properties satisfied by the "healthy" model were satisfied; properties violated by "diseased" models were correctly flagged.

5. Significance

Solving Undecidability: The paper provides a practical solution to the long-standing problem of undecidable static verification for STL by leveraging the discrete nature of digital controllers and the SIH.
Unified Safety and Liveness: Unlike previous over-approximation methods that often fail for liveness, SSTL handles both safety and liveness properties rigorously.
Practical Applicability: By translating to LTLP and using SPIN, the approach is immediately applicable to existing industrial verification workflows without requiring new, complex theorem provers.
Medical and Safety Critical Impact: The successful verification of a heart model demonstrates the potential for SSTL to be used in the certification of medical devices (pacemakers, defibrillators) and autonomous systems where timing precision is life-critical.

In conclusion, SSTL bridges the theoretical gap between continuous physical systems and discrete digital verification, offering a decidable, sound, and complete framework for ensuring the reliability of next-generation Cyber-Physical Systems.