⚡ electrical engineering

Quantitative Monitoring of Signal First-Order Logic

This paper introduces the first publicly available prototype for online quantitative monitoring of Signal First-Order Logic (SFO) by defining robustness-based semantics, transforming bounded-response formulas into an efficiently monitorable past-time fragment, and demonstrating the approach's practicality through benchmark evaluations.

Original authors: Marek Chalupa, Thomas A. Henzinger, N. Ege Saraç, Emily Yu

Published 2026-03-04

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Marek Chalupa, Thomas A. Henzinger, N. Ege Saraç, Emily Yu

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 self-driving car. The car's sensors are constantly feeding it data: "Speed is 60 mph," "Pedestrian is 5 meters away," "Road is curving left."

In the past, checking if the car was following the rules was like a strict teacher with a red pen. The teacher would look at the data and say only one of two things: "Pass" (you followed the rule) or "Fail" (you broke the rule).

But what if the car was almost safe? What if it was 10 centimeters too close to a pedestrian? A simple "Fail" doesn't tell the whole story. It doesn't tell the engineer how close the car was to disaster, or how much it would need to adjust to be safe.

This paper introduces a new way to monitor these systems called Signal First-Order Logic (SFO) with Quantitative Semantics. Here is the breakdown in simple terms:

1. The Problem: The "Red Pen" is Too Simple

The old way of checking rules (Boolean semantics) is like a light switch: it's either ON or OFF.

The Issue: Real life isn't a light switch. It's a dimmer. Sometimes a system is "mostly safe," sometimes it's "barely safe," and sometimes it's "dangerously unsafe."
The New Idea: Instead of just saying "Fail," the new system gives a score.
- A score of +10 means "You are very safe; you could be 10 units more aggressive."
- A score of -2 means "You are unsafe; you need to move back 2 units to be safe."
- This score is called Robustness. It tells you how much wiggle room you have.

2. The Language: SFO (The "Super-Translator")

The authors use a language called Signal First-Order Logic (SFO). Think of this as a super-powerful translator that can understand complex, real-world rules that other languages can't.

Old Languages (like STL): Can say, "Stay under 60 mph."
SFO: Can say, "If the car suddenly hits a bump, it must settle back to its original smooth speed within 10 seconds, and it must stay within a tiny 'comfort zone' of that speed for at least 8 seconds."

SFO can talk about specific moments, specific values, and relationships between different signals (like speed vs. distance) in a way that is very precise.

3. The Challenge: The "Crystal Ball" Problem

Here is the tricky part. To check a rule like "The car must settle down within 10 seconds," you usually need to look into the future.

If you are monitoring the car right now, you don't know what it will do in the next 10 seconds.
If you have to wait 10 seconds to see if the rule was broken, you are too late to fix it. This is called Offline Monitoring (checking the tape after the game is over).

The authors wanted Online Monitoring (checking the game while it's happening). But you can't check the future!

4. The Solution: The "Time-Traveling" Trick

The authors came up with a clever trick called Pastification.

Imagine you are watching a movie. You want to know if the hero will survive the explosion in 10 seconds.

The Old Way: Wait 10 seconds, then check. (Too slow!)
The New Way: Shift your perspective. Instead of asking "Will the hero survive 10 seconds from now?", you ask, "Did the hero survive 10 seconds from then?"

By shifting the "reference time" backward, they turn a rule about the future into a rule about the past.

Instead of: "In the next 10 seconds, the car must stop."
They rewrite it as: "Looking back 10 seconds from now, did the car stop?"

This allows the computer to check the rule instantly using only the data it has already seen. It's like checking your bank balance for the last month to see if you overspent, rather than waiting to see if you will overspend next month.

5. The Engine: Polyhedra (The "Shape-Shifting Calculator")

How do they actually calculate these scores? They use a mathematical concept called Polyhedra.

Imagine the data (speed, time, distance) as a 3D shape made of clay.

When the car speeds up, the shape stretches.
When the car slows down, the shape squishes.
The "Robustness Score" is like measuring the volume of this shape.

The authors built a calculator that can slice, dice, and reshape these clay models instantly.

Negation (Not): Flips the shape inside out.
OR: Merges two shapes together.
Quantifiers (For all/There exists): Squeezes the shape to find the "best" or "worst" possible outcome.

This allows them to calculate the exact "safety score" for every single moment in time, symbolically, without needing to guess.

6. The Result: A Practical Tool

The authors built a prototype tool (a piece of software) and tested it on two scenarios:

A Delivery Drone: Flying through a city with other drones. They checked if it stayed safe, smooth, and far enough from obstacles.
A Fighter Jet: Checking if it stayed at a safe altitude and recovered quickly if it dipped too low.

The Verdict:
The tool worked! It could calculate these complex safety scores fast enough to keep up with the sensors.

For simple rules, it was lightning fast.
For complex rules (like the "settle down within 10 seconds" rule), it was a bit slower but still fast enough to give a warning to a pilot or a control system before a crash happened.

Summary Analogy

Think of the old monitoring system as a security guard who only yells "STOP!" when someone crosses a line.

This new system is like a smart GPS that says:
"You are 50 meters from the line. You have a 'safety buffer' of 50 meters. If you speed up, your buffer shrinks. If you slow down, your buffer grows. Here is your exact distance to the danger zone right now."

This gives engineers and AI controllers much more information to make better, safer decisions in real-time.

1. Problem Statement

Runtime verification involves checking system executions against formal specifications. While Signal Temporal Logic (STL) is widely used for continuous signals, it lacks the expressiveness to model complex hybrid system behaviors, such as bounded stabilization properties (e.g., "after a disturbance, the signal must return to a specific value within a time window"). Signal First-Order Logic (SFO) was introduced to address this by combining first-order logic with linear arithmetic and uninterpreted function symbols, allowing quantification over both time and value variables.

However, two critical gaps existed in SFO:

Lack of Quantitative Semantics: Existing SFO definitions were purely Boolean (satisfied/violated). In continuous systems, binary outcomes are often insufficient; engineers need to know how well a specification is satisfied (robustness) to make better control decisions.
Lack of Online Monitoring Tools: Full SFO formulas often depend on unbounded future behavior, making them unsuitable for online (real-time) monitoring. Furthermore, no tool existed to perform online monitoring for SFO, let alone quantitative monitoring.

2. Methodology

The authors propose a framework for online quantitative monitoring of SFO. Their approach consists of four main technical pillars:

A. Robustness-Based Quantitative Semantics

The paper defines a new semantics for SFO that assigns a robustness value $\mu(w, \nu, \phi) \in \mathbb{R} \cup \{-\infty, +\infty\}$ to a signal trace $w$ and valuation $\nu$ .

Interpretation: A positive value indicates satisfaction (magnitude = degree of satisfaction), while a negative value indicates violation (magnitude = degree of violation).
Recursive Definition:
- Atomic predicates ( $\theta_1 < \theta_2$ ): Robustness is the difference $\llbracket \theta_2 \rrbracket - \llbracket \theta_1 \rrbracket$ .
- Negation ( $\neg \phi$ ): Robustness is $-\mu(\phi)$ .
- Disjunction ( $\phi_1 \lor \phi_2$ ): Robustness is $\max(\mu(\phi_1), \mu(\phi_2))$ .
- Existential Quantification ( $\exists x \in I. \phi$ ): Robustness is the supremum of $\mu(\phi)$ over the interval $I$ .
Soundness: The semantics is proven sound with respect to Boolean semantics: $\mu > 0 \implies$ satisfied; $\mu < 0 \implies$ violated.

B. Past-Time Fragment and Pastification

To enable online monitoring, the authors identify a Past-Time SFO (pSFO) fragment. A formula is in pSFO if all signal accesses at time $t$ refer only to times $\le t$ .

Bounded-Response Formulas: The authors focus on formulas where time quantifiers are bounded (e.g., $\exists s \in [0, 10]$ ).
Pastification Procedure: They introduce an algorithm to transform a bounded-response SFO formula into an equisatisfiable pSFO formula. This involves calculating a forward horizon ( $H^+$ ), which is the maximum future offset required by the formula. By shifting the reference time backward by $H^+$ , future signal accesses are converted into past accesses, allowing the monitor to operate without looking ahead.

C. Polyhedral Online Monitoring Algorithm

The core algorithm computes robustness values symbolically using convex polyhedra.

Representation: Signals and formulas are represented as lists of convex polyhedra defined by linear constraints over time and value variables.
Symbolic Operations:
- Arithmetic: Translated into intersections and projections of polyhedra.
- Boolean Connectives: Handled via case-splitting (e.g., $v_1 \ge v_2$ vs. $v_1 < v_2$ ) to compute the maximum robustness.
- Quantifiers: Handled via parametric maximization. To compute $\sup_{x \in I} \mu(\phi)$ , the algorithm eliminates the quantified variable by finding the maximum of an affine objective function over a polyhedral domain. This is achieved using a specialized procedure (PlpMaximize) that analyzes the slope of the objective function relative to the bounds of the polyhedron.
Memory Management: The monitor maintains a sliding window of signal history corresponding to the backward horizon ( $H^-$ ) of the formula, discarding old data to ensure bounded memory usage.

D. Implementation

The authors implemented a prototype tool in Python using SymPy for symbolic math and Parma Polyhedra Library (PPL) for polyhedral operations. The tool supports parsing SFO, performing pastification, and executing the online monitoring algorithm on piecewise-linear signals.

3. Key Contributions

First Quantitative Semantics for Full SFO: Generalizes Boolean SFO to a robustness-based framework, enabling nuanced evaluation of real-valued signals.
Pastification Procedure: A novel method to transform bounded-response SFO formulas into past-time fragments, bridging the gap between expressive logic and online feasibility.
Efficient Online Algorithm: A symbolic monitoring algorithm that computes robustness values for pSFO formulas over piecewise-linear signals using polyhedral representations.
Prototype and Benchmarks: The first publicly available prototype for online quantitative SFO monitoring, validated against real-world cyber-physical system benchmarks.

4. Experimental Results

The authors evaluated their tool on two benchmarks:

Dynamic Obstacle Avoidance: A drone navigating an urban environment with obstacles.
- Properties: Safe velocity, motion smoothness (derivative constraints), and obstacle separation.
- Performance: The monitor computed robustness values in 0.002s to 0.021s per segment (sampling period 0.1s). This is significantly faster than the control loop, proving feasibility for real-time control decisions.
Altitude Control: A simplified F-16 fighter jet model.
- Properties: Safe altitude, safe airspeed, and altitude recovery (a complex bounded-stabilization property with nested quantifiers).
- Performance: For the complex recovery property (requiring a 20-second horizon), the monitor took ~0.21s per segment (sampling period 0.033s). While slightly slower than the control loop, it is fast enough for runtime warnings and supervision.
Scalability: The results demonstrate that the approach scales well with specification complexity, including nested quantifiers and Boolean combinations, though runtime increases with the size of the backward horizon.

5. Significance

This paper represents a significant advancement in the field of runtime verification for hybrid systems:

Expressiveness: It enables the monitoring of complex properties (like bounded stabilization and relative timing constraints) that are impossible to express in STL or quantifier-free logics.
Practicality: By providing the first online quantitative monitor for SFO, it moves the logic from theoretical expressiveness to practical application in cyber-physical systems (CPS).
Feedback for Control: The quantitative output (robustness values) provides actionable feedback that can be used for controller synthesis, reinforcement learning rewards, or runtime enforcement (shielding), going beyond simple pass/fail verification.
Foundation for Future Work: The paper establishes a semantic and algorithmic foundation for integrating SFO into broader frameworks like runtime enforcement and decentralized monitoring.