Quantitative and approximate monitoring

Henzinger TA, Sarac NE. 2021. Quantitative and approximate monitoring. Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science. LICS: Symposium on Logic in Computer Science, 1–14.


Conference Paper | Published | English

Scopus indexed
Department
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.
Publishing Year
Date Published
2021-07-07
Proceedings Title
Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science
Acknowledgement
We thank the anonymous reviewers for their helpful comments. This research was supported in part by the Austrian Science Fund (FWF) under grant Z211-N23 (Wittgenstein Award).
Page
1-14
Conference
LICS: Symposium on Logic in Computer Science
Conference Location
Rome, Italy
Conference Date
2021-06-29 – 2021-07-02
ISSN
IST-REx-ID

Cite this

Henzinger TA, Sarac NE. Quantitative and approximate monitoring. In: Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science. Institute of Electrical and Electronics Engineers; 2021:1-14. doi:10.1109/LICS52264.2021.9470547
Henzinger, T. A., & Sarac, N. E. (2021). Quantitative and approximate monitoring. In Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science (pp. 1–14). Rome, Italy: Institute of Electrical and Electronics Engineers. https://doi.org/10.1109/LICS52264.2021.9470547
Henzinger, Thomas A, and Naci E Sarac. “Quantitative and Approximate Monitoring.” In Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science, 1–14. Institute of Electrical and Electronics Engineers, 2021. https://doi.org/10.1109/LICS52264.2021.9470547.
T. A. Henzinger and N. E. Sarac, “Quantitative and approximate monitoring,” in Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science, Rome, Italy, 2021, pp. 1–14.
Henzinger TA, Sarac NE. 2021. Quantitative and approximate monitoring. Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science. LICS: Symposium on Logic in Computer Science, 1–14.
Henzinger, Thomas A., and Naci E. Sarac. “Quantitative and Approximate Monitoring.” Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science, Institute of Electrical and Electronics Engineers, 2021, pp. 1–14, doi:10.1109/LICS52264.2021.9470547.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]

Link(s) to Main File(s)
Access Level
OA Open Access

Export

Marked Publications

Open Data IST Research Explorer

Sources

arXiv 2105.08353

Search this title in

Google Scholar
ISBN Search