CS Paper Radar

Runtime Monitoring of Distributed Cyber-Physical Systems Without a Global Clock

Charles Koll, Houssam Abbas

cs.LO ·submitted 2026-08-13 17:15 UTC · v1
published

Abstract

We give the first theoretical characterization, and the first algorithm, for continuous monitoring of a distributed Cyber-Physical System (CPS) against a dense-time temporal logic specification. A distributed CPS is composed of multiple agents, each with a local clock; these clocks drift from each other, so there is no well-defined global time. When monitoring such a system's output signal against a temporal logic specification, it is not evident how to interpret the temporal constraints of the formula, and what satisfaction means. Yet CPS designers, like control engineers, typically think of their system's operation in terms of global time. Most existing techniques for monitoring distributed systems work with discrete-time specifications not suitable for CPS, and/or require an explicit mapping of temporal constraints to local clocks. We introduce an algorithm that addresses the above challenges for a fragment of Signal Temporal Logic (STL) that still includes all temporal operators. It relies on a novel extension of satisfaction signals to this partially synchronous setting (where clocks drift), and an analysis of the geometry of multi-dimensional partially synchronous time. The algorithm returns the set of all possible global moments that can satisfy the specification. Knowledge of these possible global moments is important for debugging distributed hybrid control systems such as fleets of drones and electrical grids. We derive the worst-case complexity of the algorithm, and implement a sound approximation of it that experimentally illustrates effective monitoring, even in scenarios of up to 50 agents.

Comment
Accepted to Runtime Verification 2026

Closest papers

Nearest neighbours by meaning across the whole index.

On the Time and Frequency Domain Representations of Signals for CPS Specification

cs.SE ·2026-08-21 ·Claudio Mandrioli, Drishti Yadav, Domenico Bianculli
similarity 0.71
Abstract

Specification languages are instrumental to the Verification \& Validation of Cyber-Physical Systems (CPSs). Most state-of-the-art specification languages use the time-domain representation of signals, which is not always suitable for describing signal shapes and dynamic behaviours. Instead, fields like control and robotics use the frequency-domain representation to characterise these behaviours. Time-frequency representations combine the capabilities of both domains. We investigate the use of time-frequency representations to specify CPS requirements. We analyse existing taxonomies of CPS requirements to identify which requirement classes can benefit from time-frequency representations. We derive the desiderata for a specification language that uses time-frequency representations and propose Signal-Spectrum Temporal Logic (S2TL), a language enabling assertions over frequency intervals and relations between frequency components. We operationalise the S2TL semantics for monitoring CPS traces, and implement a monitor. We define specification templates for the identified requirement classes and compare time- and time-frequency-domain formulations in terms of applicability, expression fidelity, and noise tolerance of monitoring. We observe that, while time-domain specifications are applicable only to input traces containing step-like changes or using constant interpolation, time-frequency specifications extend their evaluation to traces generated through linear interpolation, and improve tolerance to offset and high-frequency noise, while achieving comparable fidelity to the intended system properties.

0.13

Sound Compilation of Weighted Event Signal Temporal Logic to Timeless Geometric Control

eess.SY ·2026-09-07 ·Avinash Malik
similarity 0.70
Abstract · 14 pages

Cyber-Physical Systems (CPS) controllers synthesized from standard temporal logics rely on rigid global clocks, rendering them vulnerable to asynchronous timing anomalies like clock snaps, jitter, and network delays. To overcome these vulnerabilities, we introduce a fundamentally timeless geometric control paradigm alongside a novel specification language: Weighted Event-Based Signal Temporal Logic (weSTL+). This new weSTL+ logic combines the event triggered nature of Event-STL with weighted user preferences of weighted-STL making it suitable for specification of practical autonomous CPS. Using a two-pass compiler, our framework translates weSTL+ formulae directly into C^1-differentiable time-invariant geometric surrogate constraints via finite-time level-set inversion. By mapping temporal windows directly into physical time independent geometric boundaries, this approach entirely eliminates explicit runtime clock monitoring. Our autonomous robotics case study demonstrates that the proposed geometric architecture guarantees enforcement of safety and liveness under severe macroscopic timing discontinuities, succeeding where traditional time-indexed controllers fail.

0.20

Time-Invariant Control Barrier Functions for Bounded STL Safety

eess.SY ·2026-08-28 ·Avinash Malik
theory similarity 0.68
Abstract · 6 pages, 3 figures

Enforcing finite-time persistence specifications in Signal Temporal Logic typically requires formulating Control Barrier Functions within an extended state-time space. This introduces strict mathematical assumptions on global clock synchronization, rendering multi-agent execution brittle under asynchronous network delays, clock skew, and non-monotonic jitter. In this paper, we prove that for bounded-time safety tasks, explicit time dependency can be mathematically eliminated for general continuous-time nonlinear systems. By leveraging the reciprocal integral of worst-case system dissipation, we systematically compile temporal specifications into static, lower-dimensional spatial invariants. We formally prove that this time-invariant realization is strictly sound, removes the need for heuristic time-varying envelope tuning, and guarantees robust forward invariance even under severe network desynchronization.

0.18

MightyPPL : Towards model checking MTL

cs.LO ·2026-09-16 ·Hsi-Ming Ho, Shankara Narayanan Krishna, Khushraj Madnani, Rupak Majumdar, Paritosh Pandya
similarity 0.67
Abstract · Best paper Award at QEST+FORMATS 2026, nominated for Best Artifact Award at QEST+FORMATS 2026

The theoretical foundation for model checking timed systems against Metric Interval Temporal Logic (MITL) was established in the early 1990s, yet the first practical tool supporting future MITL (MightyL) did not emerge until 2017. Recently, there has been growing interest in extending this toolchain to support more expressive logical operators, including past modalities, Pnueli modalities, and limited use of singular intervals. MightyPPL is one such toolchain. We introduce an upgraded version of MIghtyPPL that enables for the first time, the model checking of Metric Temporal Logic (MTL) properties of the form (whenever an event p occurs, it is eventually followed by some event q after exactly some k time units) in addition to Pnueli and Past modalities. We discuss the tool's underlying architecture and implementation, and present a performance evaluation against the Tempora tool across diverse satisfiability and model checking benchmarks, demonstrating that MightyPPL delivers significantly better performance.

0.22

Synchronous Observers Revisited for Runtime Verification of Lustre Using STL

cs.LO cs.FL ·2026-08-13 ·Logan Kenwright, Partha Roop, Sobhan Chatterjee, Nathan Allen
published similarity 0.67
Abstract

Signal Temporal Logic (STL) is a popular formalism for the temporal safety properties of cyber-physical systems, most often used for runtime verification. In the synchronous family of languages, safety properties are instead expressed as synchronous observers, modules composed with a program for static verification, which are also runnable specifications suitable for runtime verification, though this use is rarely explored. We present a technique for compiling the synchronous fragment of STL (SSTL) into synchronous observers in the dataflow language Lustre. Unlike previous work, we allow arbitrary nesting of bounded SSTL properties via modular compilation, and admit a globally unbounded outer operator for online monitoring; the resulting observers serve both runtime verification and, as a by-product, static verification with the Kind2 model checker. We further contribute an interactive visualiser that renders a property's three-valued verdict over an editable trace, and evaluate on two case studies from the literature: a spring-mass system and a car-following cruise controller.

0.23

Runtime Verification under Split Past and Future

cs.LO ·2026-08-21 ·Dogan Ulus
similarity 0.67
Abstract

Runtime assurance for autonomous systems increasingly requires reasoning not only about observed executions but also about anticipated future behaviors. Traditional runtime verification, however, primarily evaluates the execution observed so far and does not directly account for predicted continuations. We propose a formal framework for runtime assurance that combines monitoring of the observed execution with analysis of multiple predicted continuations. To support this integration, we introduce Split Linear Temporal Logic (SplitLTL), a linear-time temporal logic that assigns complementary roles to past and future temporal specifications within a single specification. The past component uses the observed history to determine the assurance requirements applicable at the current point of execution, while the future component evaluates predicted continuations against those requirements. The framework therefore filters predicted continuations according to the requirements induced by the observed history, identifying admissible continuations that can support subsequent decision making. We formally define the syntax and semantics of SplitLTL and present an online monitoring architecture for evaluating observed executions together with predicted continuations.

0.20

Execution-Time Opacity Logic: A Logic for Ensuring ET-Opacity in Timed Systems

cs.FL ·2026-09-09 ·Jean Leneutre, Dylan Marinho, Vadim Malvone, James Ortiz
hot direction similarity 0.65
Abstract

Ensuring confidentiality in Cyber-Physical Systems is critical, especially when attackers exploit execution times to infer sensitiveinformation. Traditional opacity models are inadequate for timed systems, as verifying opacity in Timed Automata is undecidable. To address this challenge, we propose Execution-Time Opacity Logic (ETOL), a new formalism that specifies opacity by requiring that for every execution satisfying a secret formula, there exists another execution of the same duration that does not satisfy it. ETOL guarantees that timing observations cannot reveal confidential agent activities. We present a decidable and efficient verification framework based on zone-based model checking, supported by a dedicated algorithm that systematically identifies duration-equivalent executions. Our approach is validated through an ATM case study, showing that ETOL enables efficient verification of execution-time confidentiality under timing attacks. We also developed a prototype tool for the ETOL logic that supports symbolic model checking over timed systems. It allows users to verify ETOL formulas based on clock-constrained execution paths.

0.29

Privacy-Preserving Robust Monitoring of Dense-Time Temporal Logic

cs.LO ·2026-10-19 ·Charles Koll, Mike Rosulek, Houssam Abbas
published similarity 0.65
Abstract · 13 pages, 8 figures, presented at Formal Methods in Computer-Aided Design (FMCAD) 2026

Motivated by the use of third-party testing, this paper presents a privacy-preserving implementation of the robustness monitoring of Signal Temporal Logic (STL). STL is a specification language for systems whose output traces have real-valued timestamps -- most prominently, cyber-physical systems. Its robust semantics, which assign real rather than binary truth values, are an essential ingredient of systems testing and runtime monitoring. In a number of system testing scenarios, the designer and the tester are separate parties. This testing-as-a-service model is common in software, avionics, and semiconductors, and is growing in importance in the red-teaming of machine learning models. In such a model, the designer seeks to preserve the privacy (or secrecy) of its design, while the tester seeks to preserve the privacy of its collateral, including the detailed specification suite. This paper presents a secure multi-party implementation of the robust semantics using arithmetic circuits. This implementation allows one party, which provides a secret trace, and a second party which provides a secret formula, to jointly compute the robustness without either party being able to learn the other party's secret input. We present a number of algorithmic modifications to the robustness computation to enable an efficient multi-party robustness computation. We also present new, semi-linear, robust semantics for STL that take advantage of the efficiencies of arithmetic circuits. The experimental results demonstrate that not only is this privacy-preserving monitor efficient on its own, but also that it can be used in a testing loop without affecting the speed at which bugs are found during robustness-guided system testing.

0.62