Cutting Corners on Uncertainty: Zonotope Abstractions for Stream-based Runtime Monitoring

Bernd Finkbeiner, Martin Fränzle, Florian Kohn (✉) {}^{\text{({\char 0\relax})}}, Paul Kröger · 2026

Read Cutting Corners on Uncertainty: Zonotope Abstractions for Stream-based Runtime Monitoring by Bernd Finkbeiner, Martin Fränzle, Florian Kohn (✉) {}^{\text{({\char 0\relax})}}, Paul Kröger (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-11358.txt.

Introduction

Bernd Finkbeiner, Martin Franzle, Florian Kohn, and Paul Kroger guard runtime monitors. Their 2026 preprint deals with stream-based health checks. Such monitors read sensor streams and give a verdict stream. Safety-critical systems lean on those verdicts to stay safe.

Sensors are flawed, though monitors treat their data as exact. Calibration and measurement errors ride along with each value. Errors grow as the monitor's math runs on the stream. The final verdict can warp far from the truth. The team uses zonotope abstractions to track the doubt. A zonotope is a shape that bounds where values may lie. Tracking bounds keeps verdicts honest about sensor error.

Catalog record

CREATORBernd Finkbeiner, Martin Fränzle, Florian Kohn (✉) {}^{\text{({\char 0\relax})}}, Paul Kröger
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE44 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2601-11358

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Cutting Corners on Uncertainty: Zonotope Abstractions for Stream-based Runtime Monitoring Thanks: This work was partially supported by the German Research Foundation (DFG) as part of PreCePT (FI 936/7-1; FR 2715/6-1). Bernd Finkbeiner, Martin Fränzle, Florian Kohn (✉) {}^{\text{({\char 0\relax})}}, Paul Kröger Abstract Stream-based monitoring assesses the health of safety-critical systems by transforming input streams of sensor measurements into output streams that determine a verdict. These inputs are often treated as accurate representations of the physical state, although real sensors introduce calibration and measurement errors. Such errors propagate through the monitor’s computations and can distort the final verdict. Affine arithmetic with symbolic slack variables can track these errors precisely, but independent measurement noise introduces a fresh slack variable upon each measurement event, causing the monitor’s state representation to grow without bound over time. Therefore, any bounded-memory monitoring algorithm must unify slack variables at runtime in a way that generates a sound approximation. This paper introduces zonotopes as an abstract domain for online monitoring of RLola specifications. We demonstrate that zonotopes precisely capture the affine state of the monitor and that their over-approximation produces a sound bounded-memory monitor. We present a comparison of different zonotope over-approximation strategies in the context of runtime monitoring, evaluating their performance and false-positive rates. 1 Introduction Stream-based runtime monitoring is a safety assurance mechanism for cyber-physical systems. A monitor observes system behavior and checks it against a given specification. In stream-based specifications, observations appear as input streams that capture sensor data or other system outputs. Output streams are defined by equations that transform and combine these inputs to assess system health. Because many cyber-physical systems are safety-critical, the precision of the monitor’s verdicts is essential. Monitoring frameworks often assume that input values perfectly represent the physical system. In practice, sensor measurements include calibration errors and noise. As measurements accumulate in the monitor’s state, their inaccuracies can propagate through computations and affect the final verdict. A simple way to model such inaccuracies is to lift stream values from scalars to intervals, as done in robust semantics for signal-temporal logic [ 30 ] . However, interval arithmetic introduces the aliasing problem: subtracting an interval from itself yields an interval double the size of the error bound (e.g., [2,6]-[2,6]=[-4,4] ), producing overly pessimistic verdicts. An alternative methodology to capture measurement noise explored previously uses symbolic slack variables to model interval-bounded measurement errors [ 14 , 15 ] . There, slack variables symbolically represent the interval of [-1,1] and, using affine arithmetic, can also model the above interval as the affine form x=4+2\epsilon for a slack variable \epsilon . As slack variables are treated symbolically, the computation of x-x indeed leads to the expected result of zero: 4+2\epsilon-(4+2\epsilon)=0 . However, if the measurement errors are independent, such as those induced by per-sample random measurement noise, an independent (fresh) slack variable is required for each measurement. As input measurements can accumulate in stream values indefinitely, the monitor’s memory requirement becomes trace-length dependent, as a new symbolic variable is memorized in each step. Therefore, any trace-length independent runtime monitor must unify slack variables at runtime to keep its internal state from growing beyond any bound. RLola , an extension of Lola [ 13 ] , incorporates slack variables to cover interval-bounded noise [ 15 ] . Prior work identifies a language fragment in which a bounded number of slack variables suffices. This paper addresses the general case, where arbitrary RLola specifications may introduce an unbounded number of slack variables. To ensure bounded memory, we introduce zonotopes as an abstract domain for the monitoring of RLola specifications. The monitor computes a continuous over-approximation of its state using zonotopes, keeping memory usage independent of trace length. Our approach is generic with respect to the chosen approximation strategy, and we compare several state-of-the-art zonotope over-approximation techniques to determine the best-suited for monitoring and to identify further need for research on zonotopic set approximation. 1.1 Motivating Example This section introduces the motivating example shown in Figure 1 , which is based on an industrial robot that can move in two dimensions. For safe operation, the robot must not enter the upper or right region of the factory where the x or y coordinate exceeds four. Endstops trigger when the robot reaches a wall, i.e., when x or y is zero. From each endstop event, the robot estimates its position using its measured velocities and the elapsed time between measurements. Figure 1 : An industrial robot that can move in the two dimensions of a plane. Monitoring whether the robot stays within its working area is a standard runtime-monitoring task. The monitor must track the robot’s position in the same way as the robot and compare it with the specified bounds. Because velocity measurements are noisy, the monitor must incorporate this noise into its computations to produce an accurate and reliable verdict. The following specification shows how such a monitor can be defined in RLola . ⬇ input time : Float input bump_x : Bool input vel_x : Float input bump_y : Bool input vel_y : Float output dt := time - time . prev (0.0) constant delta_x : Variable output epsilon : Variable output vx := vel_x + 0.1 * epsilon + 0.05 * delta_x output vx_filter := 0.8 * vx + 0.2 * vx_filter . prev (0.0) output position_x := if bump_x then 0.0 else position_x . prev (0.0) + vx_filter * dt constant delta_y : Variable output tau : Variable output vy := vel_y + 0.1 * tau + 0.05 * delta_y output vy_filter := 0.8 * vy + 0.2 * vy_filter . prev (0.0) output position_y := if bump_y then 0.0 else position_y . prev (0.0) + vy_filter * dt trigger position_x >_{0.01} 4.0 "Violated Geofence in X-Direction" trigger position_y >_{0.01} 4.0 "Violated Geofence in Y-Direction" Listing 1: A specification for the industrial Robot from Figure 1 . The specification begins with the time input stream, recording the time in seconds since the last measurement. The vel_x and vel_y streams provide independent velocity measurements for the x and y direction, and the boolean bump_x and bump_y streams indicate endstop events. The output streams approximate the robot’s position from the velocity inputs. Each velocity measurement is augmented with two slack variables to capture measurement noise. The constant slack variable delta represents a calibration offset and is declared as a constant stream of type Variable . In contrast to constant variables, the non-constant output streams epsilon and tau of type Variable introduce fresh slack variables at each step, which are also added to vx and vy to model per-measurement errors. To reduce this noise, an exponential filter is applied in vx_filter and vy_filter . Each filter computes a weighted sum of the current noisy measurement and its previous value, accessed via an prev operator that yields the last element of the stream or a default value if none exists. The position coordinates are then reconstructed by adding the distance traveled in the current step (velocity times elapsed time) to the last known coordinate. When an endstop triggers, the corresponding coordinate is reset to zero. Finally, trigger streams compare the reconstructed positions to their thresholds. Because the position streams represent value ranges, direct comparison can result in

Read the complete text