Formal Methods

Jan Baumeister, Bernd Finkbeiner, Florian Kohn, Frederik Scheerer, Rossi, MatteoLecture Notes in Computer Science 2024 · DOI · OpenAlex

Abstract

Stream-based runtime monitoring frameworks are safety assurance tools that check the runtime behavior of a system against a formal specification. This tutorial provides a hands-on introduction to RTLola, a real-time monitoring toolkit for cyber-physical systems and networks. RTLola processes, evaluates, and aggregates streams of input data, such as sensor readings, and provides a real-time analysis in the form of comprehensive statistics and logical assessments of the system's health. RTLola has been applied successfully in monitoring autonomous systems such as unmanned aircraft. The tutorial guides the reader through the development of a stream-based specification for an autonomous drone observing other flying objects in its flight path. Each tutorial section provides an intuitive introduction, highlighting useful language features and specification patterns, and gives a more in-depth explanation of technical details for the advanced reader. Finally, we discuss how runtime monitors generated from RTLola specifications can be integrated into a variety of systems and discuss different monitoring applications.

Introduction

Ensuring the safety of autonomous systems like drones, self-driving cars, and medical devices is a critical challenge. These cyber-physical systems (CPS) operate in real-time, where processing delays can be as dangerous as software bugs. RTLola is a specialized framework designed for real-time safety monitoring that treats system data as a series of interconnected "streams." This approach allows engineers to transform raw sensor data into real-time safety verdicts, handling complex temporal logic and asynchronous data while maintaining strict memory and timing guarantees.

The Challenge of Real-Time Monitoring

Traditional monitoring approaches often struggle with three specific challenges in CPS environments:

  1. Temporal Complexity: Reasoning about historical data versus current state.
  2. Asynchronicity: Sensors like GPS, Radar, and IMUs often provide data at different, unpredictable frequencies.
  3. Scalability: Monitoring a dynamic number of entities (e.g., multiple intruders in a crowded airspace) without exceeding memory limits.

The RTLola Framework: Stream-Based Logic

The core of RTLola is its domain-specific language (DSL) for Stream-based Monitoring. Instead of imperative code, users define equations relating input streams (raw data) to output streams (computed values) and triggers (safety alerts).

The conceptual model of RTLola: (a) interaction of input/output streams, (b) equations over inputs, (c) equations including outputs, and (d) equations over past values.

Key Technical Features

  • Stream Equations: Outputs are defined using operators like offset for past values and sliding window aggregations (e.g., tracking distance trends over time).
  • Pacing & Semantic Type Systems: These internal checkers ensure the monitor is logically sound, verifying that timing is consistent and data dependencies are met.
  • Dynamic Lifecycle Management: Using spawn, eval, and close commands, the monitor can dynamically manage "sub-monitors" for specific entities, such as new drones entering the airspace.
  • Static Memory Bounds: RTLola can determine the exact memory footprint of a monitor before execution by analyzing the dependency graph, a crucial feature for safety-critical hardware.

Applications and Evaluation

While RTLola is a general-purpose framework, its utility is demonstrated through complex "detect and avoid" scenarios. The framework has been validated using:

  • Synthetic Traces: Simulating interactions between a primary drone and multiple intruders.
  • Flight Simulation: Testing specifications against data from Microsoft Flight Simulator.
  • Industrial Case Studies: Successful deployments with the DLR ARTIS (Autonomous Rotorcraft Testbed) and Volocopter electric helicopters.

The framework enables the creation of sophisticated safety specifications that can calculate Euclidean distances in real-time, filter stale data, and trigger alerts only when objects are both close and approaching.

Limitations and Future Outlook

RTLola's "Semantic Type System" uses a sound over-approximation for decidability, which may occasionally reject complex but valid specifications. Additionally, while memory for individual parameters is statically bounded, the total memory for an unbounded number of concurrent entities is limited by physical RAM. Future work points toward expanding these capabilities into medical CPS and large-scale network monitoring.

Summary updated

Abstract

Stream-based runtime monitoring frameworks are safety assurance tools that check the runtime behavior of a system against a formal specification. This tutorial provides a hands-on introduction to RTLola, a real-time monitoring toolkit for cyber-physical systems and networks. RTLola processes, evaluates, and aggregates streams of input data, such as sensor readings, and provides a real-time analysis in the form of comprehensive statistics and logical assessments of the system's health. RTLola has been applied successfully in monitoring autonomous systems such as unmanned aircraft. The tutorial guides the reader through the development of a stream-based specification for an autonomous drone observing other flying objects in its flight path. Each tutorial section provides an intuitive introduction, highlighting useful language features and specification patterns, and gives a more in-depth explanation of technical details for the advanced reader. Finally, we discuss how runtime monitors generated from RTLola specifications can be integrated into a variety of systems and discuss different monitoring applications.
BibTeX
@inproceedings{baumeister2024formal,
  author = {Jan Baumeister and Bernd Finkbeiner and Florian Kohn and Frederik Scheerer and Rossi, Matteo},
  title = {{Formal Methods}},
  booktitle = {Lecture Notes in Computer Science},
  year = {2024},
  doi = {10.1007/978-3-031-71177-0},
}
Figure