Runtime Verification under Split Past and Future

summary

The gist

Runtime Verification under Split Past and Future proposes a formal framework that combines monitoring of observed execution with analysis of multiple predicted continuations to support runtime…

In short

The framework combines monitoring observed execution with analyzing multiple predicted futures to ensure autonomous system safety. It introduces SplitLTL, a logic separating past and future requirements, allowing monitors to filter predictions based on history. This enables runtime assurance by only accepting continuations that satisfy both historical and future constraints.

Key concepts

SplitLTL
A temporal logic that splits specifications into past (PastLTL) and future (FutureLTL) requirements. A rule is satisfied if the system satisfies the past requirement OR the future requirement, which is equivalent to saying it must satisfy both in sequence.
Monitoring Architecture
An architecture where separate monitors handle past and future checks. Past-time monitors track observed history incrementally, while future-time monitors evaluate a set of predicted behaviors against their corresponding requirements at each time step.
Temporal Symmetry
The idea that future-time formulas can be transformed into past-time formulas by reversing the temporal direction. This symmetry allows the system to reuse monitoring infrastructure efficiently for both past and future checks using the same underlying tools.

Terminology used across episodes

This episode discusses

The paper

Runtime Verification under Split Past and Future · Read on arXiv

Bogazižci University

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.

DOI: 10.4204/EPTCS.457.4

Transcript

Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.

Tom: I'm Tom.

Jane: And I'm Jane, here with Lu, Meng and our in-house large language model, Lalam.

Tom: We're looking at the paper: "Runtime Verification under Split Past and Future".

Paper summary: Tom: We’ve talked about the setup, but I want to get back to the basics of what this paper is actually trying to achieve with "Runtime Verification under Split Past and Future." It claims that traditional verification only checks the history, so this new approach combines monitoring observed execution with analyzing multiple predicted continuations >

Jane: Right. The main innovation is Split Linear Temporal Logic, which gives a single specification both past and future requirements evaluated relative to the current time point >

Lu: They define a SplitLTL rule as a pair of formulas where one is in PastLTL and the other is in FutureLTL, with the satisfaction defined as an "or" relationship between them >

Meng: So, when you look at a specific time point, say t over behavior w, it's satisfied if either the past component holds for the actual execution up to that point or if one of the predicted futures holds against its future requirement >

Lalam: They outline this framework by assuming the system provides one or more predicted trajectories describing its future states and environment over a finite prediction horizon at each time point >

Tom: The key action they take is evaluating each of those predicted trajectories against the future-time requirements only for those rules whose past-time requirements are already satisfied by the actual execution prefix >

Jane: This means they filter out any predicted trajectories that violate the requirements, leaving you with a set of continuations that are consistent with the specified assurance conditions >

Lu: The semantics for these time points, like "Y" and "X," are defined relative to immediately preceding and succeeding time instants respectively >

Meng: They use reflexive semantics for modalities like "S" and "U," meaning the current time instant can act as the witness if it meets the conditions >

Lalam: The paper shows that common temporal modalities, like "P" for sometime in the past or "G" for always, are treated as syntactic abbreviations that you can use directly in your specification >

Tom: So, to summarize: they use SplitLTL to separate past and future needs and filter predicted futures based on what's already happened >

Jane: It really matters because it allows you to verify safety properties not just against what has occurred, but also against the set of behaviors the system is currently planning >

Conclusion: Tom: So wrapping up this paper, "Runtime Verification under Split Past and Future" by Dogan Ulus. It’s about moving beyond just checking the past to actively using predicted futures to ensure safety during runtime >

Jane: It’s a framework that introduces SplitLTL to handle those two temporal aspects in one go, which is a general pattern for integrating monitoring with prediction-based decision making >

Lu: The implication is that you can create a specification-based layer that operates between prediction, monitoring, and the actual decision making process in autonomous systems >

Meng: For deployment at scale, they’re focusing on how efficient the monitoring infrastructure is because modern systems generate a lot of candidate behaviors over long horizons >

Lalam: The work suggests that runtime verdicts from these predicted behaviors can serve as feedback to guide or refine the prediction mechanisms in subsequent control cycles >

More episodes

← Home