Abstract Monitors for Quantitative Specifications
Open Access
- 23 September 2022
- book chapter
- Published by Springer Nature
- p. 200-220
Abstract
Quantitative monitoring can be universal and approximate: For every finite sequence of observations, the specification provides a value and the monitor outputs a best-effort approximation of it. The quality of the approximation may depend on the resources that are available to the monitor. By taking to the limit the sequences of specification values and monitor outputs, we obtain precision-resource trade-offs also for limit monitoring. This paper provides a formal framework for studying such trade-offs using an abstract interpretation for monitors: For each natural number n, the aggregate semantics of a monitor at time n is an equivalence relation over all sequences of at most n observations so that two equivalent sequences are indistinguishable to the monitor and thus mapped to the same output. This abstract interpretation of quantitative monitors allows us to measure the number of equivalence classes (or “resource use”) that is necessary for a certain precision up to a certain time, or at any time. Our framework offers several insights. For example, we identify a family of specifications for which any resource-optimal exact limit monitor is independent of any error permitted over finite traces. Moreover, we present a specification for which any resource-optimal approximate limit monitor does not minimize its resource use at any time.Keywords
This publication has 48 references indexed in Scilit:
- Rigorous approximated determinization of weighted automataTheoretical Computer Science, 2013
- Impartiality and Anticipation for Monitoring of Visibly Context-Free PropertiesLecture Notes in Computer Science, 2013
- Runtime Verification for LTL and TLTLACM Transactions on Software Engineering and Methodology, 2011
- What can you verify and enforce at runtime?International Journal on Software Tools for Technology Transfer, 2011
- Quantitative languagesACM Transactions on Computational Logic, 2010
- Comparing LTL Semantics for Runtime VerificationJournal of Logic and Computation, 2009
- The Good, the Bad, and the Ugly, But How Ugly Is Ugly?2007
- Monitoring Temporal Properties of Continuous Signals2004
- Automating software feature verificationBell Labs Technical Journal, 2002
- Abstract interpretationACM Computing Surveys, 1996