Runtime verification (RV) examines whether a system’s run satisfies its specification. This typically requires full knowledge of the run, but many applications face imprecise or missing inputs, e.g., from noisy sensors. We aim to develop a symbolic RV procedure that can handle noisy inputs and is able to exploit assumptions that encode background knowledge about the system in order to produce reliable monitoring verdicts. As the symbolic setting in general induces increasingly large monitoring states, we aim to identify fragments of specifications where monitoring requires constant memory. After providing a formalization of the problem at hand, we propose an RV procedure and give formal correctness statements and proofs. We empirically validate our approach in two realistic case studies. The developed RV procedure is the first to effectively handle both uncertainties and assumptions in the expressive setting of Lola, and we identify relevant and expressive fragments where our procedure requires constant memory. Our evaluation witnesses the practical applicability of the approach. RV with uncertainties and assumptions is feasible in the Lola setting, and needs only constant memory in some relevant fragments. Future work will explore further theories and adapt the approach to specific applications.

Abstract Runtime verification is a technique for monitoring a system’s behavior against a formal specification. Monitors must produce verdicts that are sound with respect to the specification. Anticipation is the ability to immediately produce verdicts when the monitor can confidently predict the inevitability of the verdict. Stream runtime verification is a specialized form of runtime verification tailored to the monitoring and verification of data streams. In this paper we study anticipatory monitoring for stream runtime verification. More specifically, we present an algorithm with anticipation for monitoring of Lola specifications, which we then extend to exploit assumptions and tolerate uncertainties. As perfect anticipation is in general not computable, we use techniques from abstract interpretation, especially widening, to approximate anticipatory monitoring verdicts. Finally, we report on three empirical cases studies using a prototype implementation of a symbolic instantiation of our approach.