Quantitative and Approximate Monitoring

Thomas A. Henzinger, N. Ege Saraç

Abstract

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.

Introduction

Classical runtime verification (RV) typically focuses on boolean verdicts: a monitor observes a system trace and classifies it as "Good," "Bad," or "Unknown." However, modern complex systems often require more nuanced feedback. Instead of a binary "is the system slow?", we often need to know the maximal response time or average energy consumption. Furthermore, computing exact values for these properties in real-time can be computationally prohibitive.

This paper addresses the lack of a formal theory for quantitative properties and the inherent trade-off between monitoring precision and computational resources. We propose a framework where monitors provide numerical estimates that approximate the true value of an infinite trace, and we investigate how increasing memory (registers) enhances this approximation.

Formal Framework and Methods

The proposed framework bridges boolean logic and quantitative analysis by redefining properties and verdicts:

  • Quantitative Properties: Properties are defined as functions mapping infinite traces to values in a specific domain (e.g., real numbers).
  • Verdict Functions: A monitor generates a sequence of numerical verdicts. Precision is evaluated by comparing the limit of these verdicts (e.g., lim sup or lim inf) to the actual property value of the infinite trace.
  • Monitorability Modalities: We define Universal, Existential, and Approximate monitorability to categorize the reliability and precision of monitors.
  • Resource Constraints: To quantify resources, we utilize deterministic register machines. This allows for a formal study of how the number of integer-valued registers impacts the monitor's ability to approximate a property.

Benchmark Properties

To illustrate the framework, we consider properties such as maximal and average response time. These properties demonstrate how a monitor's estimate evolves as it processes a trace of requests (req) and acknowledgments (ack).

Monitoring the maximal response time ($M_{max}$) over a trace.

As shown in Figure 1, the monitor for maximal response time ($M_{max}$) updates its estimate monotonically as it observes longer delays between requests and acknowledgments. In contrast, monitoring average response time ($M_{avg}$) requires more complex tracking of cumulative values.

Monitoring the average response time ($M_{avg}$) over a trace.

Figure 2 illustrates the non-monotonic nature of average response time monitoring, where the estimate can fluctuate as new data points are integrated.

Key Insights

Conservative Generalization

The framework is a "super-set" of existing RV theory. Classical boolean monitorability (safety, co-safety) is reconstructed by selecting specific value domains. For instance, universal monitorability, which is highly restrictive in the boolean setting, becomes more broadly applicable in the quantitative setting because some level of approximation is almost always possible.

The Precision-Resource Ladder

A significant theoretical contribution is the "Every Register Counts" theorem. We prove the existence of quantitative properties where every additional register strictly improves monitoring precision. This establishes a direct mathematical link between hardware resources and the quality of runtime verification.

Results and Discussion

The paper successfully maps the traditional "Safety-Progress Hierarchy" into the quantitative domain. We provide concrete proofs (Theorems 9 and 10) showing that an $(\ell+1)$-counter monitor is strictly more precise than an $\ell$-counter monitor for certain properties. This provides a semantic foundation for evaluating monitors based on their precision-cost trade-offs.

Limitations and Future Directions

While this work establishes a limit-based precision theory, it does not yet account for the speed of convergence—how quickly a monitor reaches a useful estimate. Future research will explore:

  1. Convergence Rates: Measuring how fast estimates improve over time.
  2. Synthesis: Developing algorithms to automatically generate optimal monitors for a given register count.
  3. Statistical Indicators: Extending the framework to more complex statistical properties and unreliable communication channels.
  4. Enforcement: Moving from passive monitoring to active system correction based on quantitative bounds.

Summary updated

Abstract

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.
BibTeX
@inproceedings{henzinger2021quantitative,
  author = {Thomas A. Henzinger and N. Ege Saraç},
  title = {{Quantitative and Approximate Monitoring}},
  booktitle = {LICS},
  year = {2021},
  url = {https://openreview.net/forum?id=9XMQKbl5jq},
}
Figure