A Truly Robust Signal Temporal Logic: Monitoring Safety Properties of Interacting Cyber-Physical Systems under Uncertain Observation

Bernd Finkbeiner, Martin Fränzle, Florian Kohn, Paul KrögerAlgorithms 2022 · DOI · OpenReview

TL;DR

This paper introduces a novel approach to robustly monitor safety properties of cyber-physical systems (CPS) even when sensor data is imprecise and incomplete. By extending Signal Temporal Logic (STL) and employing advanced SMT-based verification techniques, they achieve more conclusive monitoring verdicts than traditional methods, especially in challenging real-world scenarios.

What Problem Does This Paper Address?

Monitoring the safety of cyber-physical systems (CPS) is crucial, especially for autonomous systems like drones. These systems rely on sensors to understand their environment, but sensor readings are often noisy, incomplete, and subject to various errors (e.g., fixed offsets, random fluctuations). Traditional monitoring approaches often assume perfect sensor data or use interval arithmetic that can lead to overly pessimistic and inconclusive verdicts when faced with uncertainty. This paper tackles the challenge of providing definitive safety judgments for CPS even when sensor information is inherently unreliable, aiming to bridge the gap between theoretical safety specifications and practical, noisy observations.

Methods

The core of this work lies in extending Signal Temporal Logic (STL) to handle metric uncertainty in sensor readings. The authors propose a new error model that decomposes measurement error into an unknown, fixed offset and an independent per-sample error. This is a refinement over previous interval-bounded error models.

To achieve robust monitoring, they leverage affine arithmetic and Satisfiability Modulo Theory (SMT) solving over linear arithmetic (SMT-LA). The key idea is to encode the STL formula, the system dynamics (if available), and the measurement error model into a single, unified linear constraint system. This allows for a holistic analysis that can exploit correlations between measurements and system states, leading to more precise verdicts.

Two main scenarios are addressed:

  1. Model-Free Monitoring: When no explicit model of the system's dynamics is available, the approach focuses solely on the sensor measurements and the STL formula.
  2. Model-Based Monitoring: When a linear model of the system's dynamics is known (even if uncertain), this information is incorporated into the constraint system to further refine monitoring.

The SMT-LA solver then determines the satisfiability of this constraint system, directly yielding conclusive monitoring verdicts (true, false, or inconclusive) that are proven to be optimal in terms of precision.

Datasets

Not discussed in the paper. The paper uses illustrative examples and figures to demonstrate its approach rather than relying on specific datasets for training or evaluation.

Key Insights and Ideas

  • Decomposing Measurement Error is Key: Moving beyond simple interval bounds to model measurement error as a combination of a fixed offset and random noise allows for a more accurate representation of real-world sensor behavior.
  • Holistic Analysis Outperforms Two-Step Approaches: Directly encoding the STL formula and error model into a single constraint system (single-step) is more powerful than traditional methods that first estimate states and then monitor (two-step). The former can exploit interdependencies that the latter misses, leading to more conclusive results.
  • SMT-LA is a Powerful Tool for Robust Monitoring: The paper demonstrates that SMT-LA solvers can effectively handle the complex logical and arithmetic constraints arising from uncertain CPS monitoring, providing optimal and decidable verdicts.
  • Uncertainty Doesn't Always Mean Inconclusive: Even with significant sensor uncertainty, this approach can often provide definitive safety judgments where simpler interval-based methods would fail.

Key Results

The paper presents algorithms that are proven to be exact monitors, meaning they are sound, complete, and conclusive. This implies they provide the most precise possible verdicts given the available information.

While specific quantitative results on benchmark datasets are not provided, the paper demonstrates the effectiveness of its approach through detailed examples. For instance, in a model-free scenario, their method can decide a monitoring condition that remains inconclusive with standard interval arithmetic. Similarly, in a model-based scenario with partial observation, their approach successfully resolves uncertainty that would otherwise lead to an inconclusive verdict. The computational complexity is shown to be NP-complete, but practical runtimes (e.g., ~300ms on a single core for a complex example) suggest feasibility for real-time applications.

Limitations and Future Work

  • NP-Completeness: The inherent NP-completeness of the problem means that for very complex formulas, large systems, or long time horizons, computational time might become a bottleneck.
  • Linear Dynamics and Error Models: The current work focuses on linear system dynamics and specific metric error models (absolute offset, independent per-sample error). Future work aims to extend this to non-linear dynamics and stochastic error models.
  • Real-World Applications: The paper uses prototypic examples. Future work will involve applying and validating the approach on real-life benchmark applications, such as those in the air taxi domain.
  • Runtime Efficiency: The authors plan to investigate structural SMT approaches and approximation algorithms to further improve runtime efficiency for online monitoring.
  • Handling Outliers: An interesting future direction is to incorporate tolerance for a fixed number of measurement outliers.

Summary updated

Abstract

Signal Temporal Logic is a linear-time temporal logic designed for classifying the time-dependent signals originating from continuous-state or hybrid-state dynamical systems according to formal specifications. It has been conceived as a tool for systematizing the monitoring of cyber-physical systems, supporting the automatic translation of complex safety specifications into monitoring algorithms, faithfully representing their semantics. Almost all algorithms hitherto suggested do, however, assume perfect identity between the sensor readings, informing the monitor about the system state and the actual ground truth. Only recently have Visconti et al. addressed the issue of inexact measurements, taking up the simple model of interval-bounded per-sample error that is unrelated, in the sense of chosen afresh, across samples. We expand their analysis by decomposing the error into an unknown yet fixed offset and an independent per-sample error and show that in this setting, monitoring of temporal properties no longer coincides with collecting Boolean combinations of state predicates evaluated in each time instant over best-possible per-sample state estimates, but can be genuinely more informative in that it infers determinate truth values for monitoring conditions that interval-based evaluation remains inconclusive about. For the model-free as well as for the linear model-based case, we provide optimal evaluation algorithms based on affine arithmetic and SAT modulo theory, solving over linear arithmetic. The resulting algorithms provide conclusive monitoring verdicts in many cases where state estimations inherently remain inconclusive. In their model-based variants, they can simultaneously address the issues of uncertain sensing and partial observation.
BibTeX
@article{finkbeiner2022truly,
  author = {Bernd Finkbeiner and Martin Fränzle and Florian Kohn and Paul Kröger},
  title = {{A Truly Robust Signal Temporal Logic: Monitoring Safety Properties of Interacting Cyber-Physical Systems under Uncertain Observation}},
  journal = {Algorithms},
  year = {2022},
  doi = {10.3390/a15040126},
}
Figure