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.
翻译:安全性和活性是计算的基本概念,也是许多核查范式的基础。布林属性的安全性-生命性分类通过观察无限计算痕迹的有限前缀(为了安全,从不为了生命)来描述某个属性是否可以伪造。在数量规格和核查中,属性没有指定真实值,而是将量化值指定为无限痕迹(例如成本或与布林属性的距离)。我们引入了定量安全和活性部分,并且我们证明我们的定义导致对(1) 布林属性的安全性-进展等级和(2) 布尔属性的安全性-生命性分解的保守性定量概括。特别是,我们表明每一种定量属性都可以作为量化安全性属性和定量性活性属性的最起码的点。因此,像布林属性一样,量化性属性也可以在安全和活性部分中分解为$-min-droundo,或者说, $\maxx-decomm-commation,此外,量化性属性可以自然地测量每个量化性能的安全性能的精确度。我们只能通过对每个量化性能进行精确的精确度监测。