Quantitative Safety and Liveness
Open Access
- 21 April 2023
- book chapter
- Published by Springer Nature
- p. 349-370
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:
- Simulation distancesTheoretical Computer Science, 2012
- Runtime Verification for LTL and TLTLACM Transactions on Software Engineering and Methodology, 2011
- Quantitative analysis of real-time systems using priced timed automataCommunications of the ACM, 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
- Computational Analysis of Run-time MonitoringElectronic Notes in Theoretical Computer Science, 2002
- Safety, liveness and fairness in temporal logicFormal Aspects of Computing, 1994
- Recognizing safety and livenessDistributed Computing, 1987
- Adequate proof principles for invariance and liveness properties of concurrent programsScience of Computer Programming, 1984