CS Paper Radar

Policy Change for Treelike Monitors

François Hublet, Dhruv Nevatia, Joshua Schneider

cs.LO ·submitted 2026-09-09 12:47 UTC · v2

Abstract

We study the policy change problem that arises in the runtime verification of long-running systems. The online monitors typically used in this context are generally treelike, in that they maintain substates that monitor subformulae of the target policy. We consider when and how the policy can be changed while the monitored system is running by only exploiting the information stored in the monitor's state. This is relevant, for example, to account for new system functionality or changes in regulatory requirements. We formally define the policy change problem in a general setting, independent of any specific (treelike) monitor implementation. We then show that policy change for past-time metric temporal logic (pMTL) is decidable but has tight non-primitive recursive lower and upper bounds, while with discrete-time semantics it is EXPSPACE-complete.

Comment
39 pages, 5 figures

Closest papers

Nearest neighbours by meaning across the whole index.

Practical Runtime Enforcement of First-Order Temporal Requirements

cs.SE ·2026-10-03 ·François Hublet, David Basin, Srđan Krstić
similarity 0.68
Abstract

Runtime enforcers observe a system's behavior and exert control over it to ensure that the system always adheres to its requirements. Many natural requirements not only formulate restrictions on the system's present behavior, but also impose obligations on its future behavior; for instance, agentic security may require personal data collected during a run to be erased by some deadline. In an ever-growing compliance landscape, real-world systems may be subject to hundreds of such requirements. However, existing enforcement mechanisms supporting complex policies are often too slow for production software; instead, developers may resort to non-temporal access control mechanisms and ad-hoc instrumentation, but these scale poorly with requirement complexity. To address this problem, we introduce an efficient algorithm and tool for enforcing complex temporal requirements and demonstrate its performance. Specifically, we identify a fragment of Metric First-Order Temporal Logic (MFOTL) that can be enforced with low runtime complexity while supporting a rich family of practically relevant requirements, including obligations. We then design an enforcement algorithm for this fragment and implement it in EnfFlash, a novel tool that enforces requirements with latency up to 44x lower than EnfGuard, the previous state-of-the-art enforcer, on standard benchmarks, and up to three orders of magnitude lower on security policies for LLM agents. This performance is achieved by compiling requirements into imperative programs that we efficiently interpret. We evaluate EnfFlash both standalone, on existing benchmarks, and integrated in web applications as an enforcement backend. We demonstrate that it can enforce a substantial 400-line MFOTL formula specifying the GDPR on a social network while adding under 15 ms to each page view, which is sufficient for most interactive and real-time applications.

0.19

Progression- vs Automata-based Anticipatory Monitoring of LTL over Finite Traces (Extended Version)

cs.LO cs.AI ·2026-09-26 ·Sarah Winkler, Toryn Klassen, Sheila McIlraith, Marco Montali
similarity 0.66
Abstract

When safety-critical systems are developed from a known internal specification, their correctness can be established by model checking. In the frequent case where such a specification is unknown or inaccessible, runtime verification presents an attractive alternative, e.g., to ascertain that autonomous and agentic systems as well as business processes satisfy desirable properties and/or comply with safety requirements. In this paper we study anticipatory monitoring, an advanced form of runtime verification, where the monitoring state is determined by both the trace prefix seen so far, and all its possible finite-length, future continuations. We focus on monitoring linear-time properties that may involve arithmetic constraints. Automata-based approaches, the de-facto standard in this setting, are notorious for their computational complexity. We propose an alternative approach based on progression and LTLf satisfiability checking, for both propositional and arithmetic settings. We experimentally compare the automata- and progression-based approaches, and a third method that combines the two. Our experiments suggest that the progression-based approach often succeeds in producing a verdict when the automata constructions do not terminate, especially for the arithmetic setting. For the propositional setting, the combined technique provides a good tradeoff.

0.03

Model Checking HyperRecHML is Decidable

cs.LO cs.FL ·2026-10-15 ·Elli Anastasiadi, Kim Guldstrand Larsen, Martin Zimmermann
similarity 0.66
Abstract

Temporal hyperlogics combine explicit quantification over traces with temporal requirements evaluated over the quantified traces. HyperRecHML is a temporal hyperlogic which allows for arbitrary mixing of trace quantification and the use of fixed points for expressing temporal requirements, which makes it very expressive in comparison to other first-order hyperlogics. HyperRecHML has already been successfully applied in runtime verification, but the decidability of its model checking problem remains open. We answer this question positively by providing two main contributions. Firstly, a normalization procedure that allows to reduce arbitrary HyperRecHML formulas to a normal form with restricted nesting of trace quantification and fixed points. Secondly, we provide an automata-based model checking algorithm for formulas of this normal form. The complexity of our algorithm is comparable to similar ones for other hyperlogics, despite the extra expressive power.

0.16

The Infinite, in Finite Time

cs.LO ·2026-08-24 ·Rayhana Amjad, Rob van Glabbeek, Liam O'Connor
publishedtheory similarity 0.65
Abstract · This paper contains the material of arXiv:2411.14581

Linear-time temporal properties, such as those described by Linear-time Temporal Logic, are typically modelled as sets of infinite traces. Yet, in a run-time verification context, such as when testing or monitoring a system, only a finite prefix of the system's behaviour can be observed. For some properties, these finite prefixes may be definitive---a yes or no answer can be given without further observation. By enriching the semantics of LTL with these definitive prefixes, we give a proper inductive accounting of the semantics of LTL$_3$, a multi-valued variant of Linear-time Temporal Logic for run-time verification applications. The semantic descriptions of LTL$_3$ in previous work are given only in terms of their relationship to conventional LTL. We show that the semantics of LTL and of LTL$_3$ are isomorphic. In addition, we formalise the formula progression evaluation technique, popularly used in runtime verification contexts, and show its soundness and completeness up to finite traces with respect to our semantics. Then, we turn to linear-time properties more generally: using our theory of definitive prefixes, we re-prove the well-known safety-liveness decomposition theorem, and reconstruct the topology of infinite traces. We define monitorability for properties, providing neat topological characterisations for various monitorability classes, and arrange them into a hierarchy. All of our definitions and proofs are mechanised in Isabelle/HOL.

0.16

Runtime Verification under Split Past and Future

cs.LO ·2026-08-21 ·Dogan Ulus
published similarity 0.65
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.31

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.65
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

On the monitorability of linear-time timed logics

cs.LO ·2026-11-18 ·Mouloud Amara, Mohammed Aristide Foughali, Giovanni Bernardi, Adrian Francalanza, Nicanora Ordoño Wallig
theory similarity 0.65
Abstract

In [10], we solved the monitorability problem for Tlin , a new expressive (linear-time) timed mu-calculus that we proposed. We showed that Tlin is strictly more expressive than MTL, the de facto timed extension of the well-known LTL. Moreover, we identified MTlin , the largest monitorable fragment of Tlin. The maximality of MTlin was proven modulo an expressive monitoring framework called Mon, yet under the assumption of reactivity. Our work in [10] was the first to solve the monitorability problem for such an expressive timed logic, and its theoretical results were accompanied with compilers (i) from MTL to Tlin and (ii) from Tlin formulae to monitors. This paper is an extension of [10] with the following new contributions. First, we generalise the maximality results to arbitrary monitors, which include both reactive and non-reactive monitors. Second, we extend the expressiveness results of Tlin . We completely revise the embedding of MTL into Tlin : we show that the syntax of MTL given in [10] was incomplete, and provide a new compiler from MTL, under its standard syntax with the strict Until operator and negation over arbitrary formulae, into Tlin . In passing, we demonstrate that Tlin is closed under complement and provide a fully syntactic complementation procedure. Moreover, we prove that Tlin is strictly more expressive than TPTL, a popular timed logic more expressive than MTL, and develop an automatic embedding from TPTL to Tlin . This gives Tlin and the machinery around it the power of a unified framework to reason on the monitorability of linear-time timed logics. Accordingly, we identify important monitorable fragments for both MTL and TPTL.

0.17

MightyPPL : Towards model checking MTL

cs.LO ·2026-09-16 ·Hsi-Ming Ho, Shankara Narayanan Krishna, Khushraj Madnani, Rupak Majumdar, Paritosh Pandya
similarity 0.63
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