Exploiting Assumptions for Effective Monitoring of Real-Time Properties under Partial Observability

Alessandro Cimatti, Thomas Møller Grosen, Kim G. Larsen, Stefano Tonetta, Martin Zimmermann

Abstract

Runtime Verification (RV) of real-time cyber-physical systems is often hampered by partial observability and timing uncertainty. This paper introduces a framework for Assumption-Based Runtime Verification (ABRV) that utilizes Timed Automata to model expected system behavior. By incorporating these assumptions, monitors can issue definitive success or failure verdicts significantly earlier than traditional, assumption-free methods. The framework employs a four-valued logic to handle cases where observations contradict the model. Evaluation across several case studies shows that ABRV effectively detects unobservable faults and improves monitoring decisiveness in continuous real-time settings.

Introduction

Traditional Runtime Verification (RV) treats systems as "black boxes," relying solely on observable outputs to check property satisfaction. However, real-world cyber-physical systems present significant challenges: critical events may be unobservable (such as internal software faults), and sensor data often contains noise or jitter, leading to timing uncertainty. Standard RV approaches are frequently reactive and remain indecisive under these conditions. This research proposes a proactive monitoring framework that uses domain knowledge—formal assumptions about system behavior—to fill observational gaps and predict future outcomes in real-time.

Methodology

The ABRV framework extends discrete-time monitoring to continuous real-time environments using several core components:

  • Property Specification: Properties are specified using Metric Interval Temporal Logic (MITL), which can be translated into Timed Büchi Automata (TBA) to represent the property and its negation.
Figure 1: A Timed Büchi Automaton (TBA) representing a real-time property and its negation.
  • Assumption Modeling: Timed Automata (TA) are used to model assumptions about how the system is expected to behave, linking observable events to unobservable internal states and specific timing patterns.
Figure 2: A Timed Automaton representing an assumption about system behavior, used to refine monitoring verdicts.
  • Rich Observation Model: Instead of exact event sequences, the monitor accepts "timed constraints." This allows it to process imprecise observations, such as an event occurring within a specific time window (e.g., between time 6 and 7).
  • Four-Valued Logic: The monitor outputs one of four verdicts: Satisfied ($\top$), Violated ($\perp$), Unknown ($?$), or Out-of-model ($\times$). The $\times$ verdict is a critical safety feature, indicating that the system's behavior contradicts the underlying assumptions.
  • Zone-Based Algorithm: An online monitoring algorithm was implemented using "zones" to represent sets of clock valuations, integrated with the UPPAAL tool suite.

Evaluation and Results

The approach was evaluated using three proof-of-concept case studies: a Task Sequence system, a Conveyor Belt model with unobservable faults, and a Jobshop Scheduling scalability test.

Key results include:

  • Earlier Verdicts: In the Task Sequence experiment, the assumption-based monitor provided definitive verdicts in 522 out of 1000 cases before the final event occurred. In contrast, an assumption-free monitor remained "Unknown" until the very end.
  • Fault Detection: In the Conveyor Belt case, the monitor successfully identified unobservable internal faults by detecting timing anomalies that were inconsistent with "healthy" behavior but consistent with "faulty" assumptions.
  • Real-Time Performance: The implementation, MoniTAal, achieved sub-millisecond response times for most scenarios. However, the Jobshop example revealed scalability challenges as the state space grows with concurrent processes.

Discussion and Future Work

The power of ABRV lies in its ability to anticipate outcomes. By knowing the system's "rules," the monitor can conclude a property will be violated long before a deadline passes. Furthermore, the ability to monitor unobservable states through their observable timing effects provides a significant advantage in complex systems.

Despite these strengths, state-space explosion remains a challenge for large networks of synchronized automata. Future work aims to provide diagnostic "why" explanations for verdicts and to further characterize what can be known about a system given specific sensor and assumption configurations.

Summary updated

BibTeX
@inproceedings{cimatti2024exploiting,
  author = {Alessandro Cimatti and Thomas Møller Grosen and Kim G. Larsen and Stefano Tonetta and Martin Zimmermann},
  title = {{Exploiting Assumptions for Effective Monitoring of Real-Time Properties under Partial Observability}},
  booktitle = {SEFM},
  year = {2024},
  doi = {10.1007/978-3-031-77382-2\_5},
}
Figure