Abstract
Runtime verification of autonomous systems often requires monitoring data-aware traces containing numerical values. This paper introduces ALTLf, an extension of Linear Temporal Logic on finite traces that incorporates linear arithmetic constraints and lookahead capabilities. While general monitoring of such properties is undecidable, the authors propose a "finite summary" abstraction that enables automated monitor construction for several practical classes of constraints, including monotonicity and periodicity.
Introduction
Traditional Runtime Verification (RV) typically relies on propositional Linear Temporal Logic (LTL) to check system behavior. However, real-world autonomous systems generate data-rich traces featuring sensor readings, timestamps, and financial values. Monitoring these systems requires expressing arithmetic relationships, such as ensuring a new bid is a certain percentage higher than the previous one.
A significant challenge in this domain is "lookahead," where a property's current validity depends on future values. Mixing arithmetic with temporal operators often leads to undecidability. This paper addresses the gap by providing a framework for monitoring arithmetic temporal properties on finite traces, identifying decidable fragments that can be effectively monitored using SMT solvers.
Methodology: The ALTLf Framework
The authors define ALTLf, combining $LTL_f$ with linear arithmetic over integers and rationals. To handle lookahead, they employ a "back" transformation, converting future-dependent properties into equivalent "lookback" properties that reference past values as the trace unfolds.
To manage the infinite data domain, the framework uses a finite summary abstraction. Instead of tracking exact values, the monitor maintains a "constraint graph" that captures essential relationships between variables. This symbolic approach allows grouping infinitely many data configurations into a finite set of monitor states.
Decidability and Monitoring Fragments
The paper proves that monitoring is decidable for any ALTLf property possessing a finite summary. Three key monitorable fragments are identified:
- Monotonicity Constraints (MC): Simple comparisons like $x < y$.
- Integer Periodicity Constraints (IPC): Constraints involving modular arithmetic.
- Bounded Lookback (BL): Properties where the required memory of past states does not grow indefinitely.
The monitoring procedure is implemented in a prototype tool that leverages the Z3 and CVC5 SMT solvers for efficient constraint checking and quantifier elimination.
Key Results and Evaluation
The approach was evaluated using a synthetic "suspicious bidding" scenario in an online auction. The monitor successfully tracks complex dependencies and issues four standard RV-LTL verdicts: permanently satisfied (PS), currently satisfied (CS), currently violated (CV), and permanently violated (PV).
As shown in the evaluation trace, the monitor can anticipate future violations or satisfactions based on the current constraints. For instance, a property might move from "currently satisfied" to "permanently violated" as soon as the data makes future satisfaction impossible.
Conclusion and Future Work
While ALTLf is undecidable in its most general form, this work provides a robust path forward for monitoring practical data-aware properties. By identifying safe fragments and using symbolic abstractions, the authors enable the creation of anticipatory monitors for complex autonomous systems. Future research will explore extending this framework to first-order traces with more complex object relations and richer quantification across time.
Summary updated