Temporal hyperproperties are system properties that relate multiple execution traces. For (finite-state) hardware, temporal hyperproperties are supported by model checking algorithms, and tools for general temporal logics like HyperLTL exist. For (infinite-state) software, the analysis of temporal hyperproperties has, so far, been limited to $k$-safety properties, i.e., properties that stipulate the absence of a bad interaction between any $k$ traces. In this paper, we present an automated method for the verification of $\forall^k\exists^l$-safety properties in infinite-state systems. A $\forall^k\exists^l$-safety property stipulates that for any $k$ traces, there exist $l$ traces such that the resulting $k+l$ traces do not interact badly. This combination of universal and existential quantification enables us to express many properties beyond $k$-safety, including, for example, generalized non-interference or program refinement. Our method is based on a strategy-based instantiation of existential trace quantification combined with a program reduction, both in the context of a fixed predicate abstraction. Notably, our framework allows for mutual dependence of strategy and reduction.
翻译:超高时性能是涉及多个执行痕迹的系统属性。 对于( fite- state) 硬件, 时间超强性能得到模型检查算法的支持, 以及超LTL 等一般时间逻辑工具的支持。 对于( intite- state) 软件, 超高性能分析到目前为止仅限于 $k$- 安全特性, 即, 表明任何美元痕迹之间没有不良互动的特性。 在本文中, 我们提出了一个自动的核查方法, 用于核查 $\forall- k\ exmissions- sl- safety tyal typeal tyal typeal。 $llall- k- slates- setective typecial typeal typeal tylation typeace by a strictlegyme of common supal impressionalal redustrical of express.