Quantitative and Approximate Monitoring
Quantitative and Approximate Monitoring
复制标题
定量和近似监测
DOI：
--
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
N. Saraç
中科院分区：
文献类型：
--
作者：
T. Henzinger;N. Saraç
在运行时验证中，一个监视器观察系统的一个轨迹，并且如果可能的话，在观察每个有限前缀之后判定未知的无限轨迹是否满足一个给定的规范。我们将运行时验证理论推广到那些试图估计定量轨迹属性数值（而非试图得出轨迹规范的布尔值）的监视器，比如沿着一个轨迹的最大或平均响应时间。定量监视器是近似的：对于每个有限前缀，它们能够改进对无限轨迹未知属性值的估计。因此，可以根据精度 - 成本权衡来比较定量监视器：对属性值更好的近似需要更多的监视器资源，比如状态（在有限状态监视器的情况下）或寄存器，并且额外的资源会产生更好的近似。我们引入一个用于定量和近似监视的正式框架，展示它如何保守地推广用于监视的经典布尔设置，并给出监视器的几个精度 - 成本权衡。例如，我们证明存在一些定量属性，对于这些属性，每增加一个寄存器都会提高监视精度。
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.
护盾合成
影响因子：
0.8
作者：
Alshiekh, Mohammed;Bloem, Roderick;Humphrey, Laura;Topcu, Ufuk;Wang, Chao
通讯作者：
Wang, Chao
影响因子：
1.8
作者：
Aceto, Luca;Achilleos, Antonis;Lehtinen, Karoliina
通讯作者：
Lehtinen, Karoliina
影响因子：
1.8
作者：
Alur, Rajeev;Mamouras, Konstantinos;Stanford, Caleb
通讯作者：
Stanford, Caleb