Realizability modulo theories

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 abil- ity 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 tol- erate uncertainties. As perfect anticipation is in general not computable, we use techniques from abstract interpretation, especially widening, to approximateanticipatorymonitoringverdicts.Finally,wereportonthree empirical cases studies using a prototype implementation of a symbolic instantiation of our approach.