Quantitative and Approximate Monitoring
Authors:
- 29 June 2021
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 1-14
Abstract
In runtime verification, a monitor watches a trace of a system and, if possible, decides after observing each finite prefix whether or not the unknown infinite trace satisfies a given specification. We generalize the theory of runtime verification to monitors that attempt to estimate numerical values of quantitative trace properties (instead of attempting to conclude boolean values of trace specifications), such as maximal or average response time along a trace. Quantitative monitors are approximate: with every finite prefix, they can improve their estimate of the infinite trace's unknown property value. Consequently, quantitative monitors can be compared with regard to a precision-cost trade-off: better approximations of the property value require more monitor resources, such as states (in the case of finite-state monitors) or registers, and additional resources yield better approximations. We introduce a formal framework for quantitative and approximate monitoring, show how it conservatively generalizes the classical boolean setting for monitoring, and give several precision-cost trade-offs for monitors. For example, we prove that there are quantitative properties for which every additional register improves monitoring precision.Keywords
All Related Versions
Funding Information
- Austrian Science Fund
This publication has 35 references indexed in Scilit:
- Quantitative reactive modeling and verificationComputer Science - Research and Development, 2013
- Impartiality and Anticipation for Monitoring of Visibly Context-Free PropertiesLecture Notes in Computer Science, 2013
- Self-adaptive software needs quantitative verification at runtimeCommunications of the ACM, 2012
- 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
- Runtime enforcement monitors: composition, synthesis, and enforcement abilitiesFormal Methods in System Design, 2011
- Quantitative languagesACM Transactions on Computational Logic, 2010
- The Good, the Bad, and the Ugly, But How Ugly Is Ugly?2007
- Computational Analysis of Run-time MonitoringElectronic Notes in Theoretical Computer Science, 2002
- The Safety-Progress Classification1993