Quantitative Safety and Liveness
Preprint
Abstract
Safety and liveness are elementary concepts of computation, and the foundation of many verification paradigms. The safety-liveness classification of boolean properties characterizes whether a given property can be falsified by observing a finite prefix of an infinite computation trace (always for safety, never for liveness). In quantitative specification and verification, properties assign not truth values, but quantitative values to infinite traces (e.g., a cost, or the distance to a boolean property). We introduce quantitative safety and liveness, and we prove that our definitions induce conservative quantitative generalizations of both (1)~the safety-progress hierarchy of boolean properties and (2)~the safety-liveness decomposition of boolean properties. In particular, we show that every quantitative property can be written as the pointwise minimum of a quantitative safety property and a quantitative liveness property. Consequently, like boolean properties, also quantitative properties can be $\min$-decomposed into safety and liveness parts, or alternatively, $\max$-decomposed into co-safety and co-liveness parts. Moreover, quantitative properties can be approximated naturally. We prove that every quantitative property that has both safe and co-safe approximations can be monitored arbitrarily precisely by a monitor that uses only a finite number of states.Keywords
All Related Versions
This publication has 47 references indexed in Scilit:
- Abstract Monitors for Quantitative Specifications2022
- Monitorability of Expressive Verdicts2022
- Monitorability Under Assumptions2020
- Refining the Safety–Liveness Classification of Temporal Properties According to Monitorability2019
- Generalized Quantitative Analysis of Metric Transition Systems2013
- Weighted Safety2013
- PSL Model Checking and Run-Time Verification Via Testers2006
- Discounting the Future in Systems Theory2003
- Efficient Model Checking of Safety Properties2003
- Synthesizing Monitors for Safety Properties2002