Monitoring Event Frequencies

Thomas Ferrère, Thomas A. Henzinger, Bernhard Kragl

Abstract

The monitoring of event frequencies can be used to recognize behavioral anomalies, to identify trends, and to deduce or discard hypotheses about the underlying system. For example, the performance of a web server may be monitored based on the ratio of the total count of requests from the least and most active clients. Exact frequency monitoring, however, can be prohibitively expensive; in the above example it would require as many counters as there are clients. In this paper, we propose the efficient probabilistic monitoring of common frequency properties, including the mode (i.e., the most common event) and the median of an event sequence. We define a logic to express composite frequency properties as a combination of atomic frequency properties. Our main contribution is an algorithm that, under suitable probabilistic assumptions, can be used to monitor these important frequency properties with four counters, independent of the number of different events. Our algorithm samples longer and longer subwords of an infinite event sequence. We prove the almost-sure convergence of our algorithm by generalizing ergodic theory from increasing-length prefixes to increasing-length subwords of an infinite sequence. A similar algorithm could be used to learn a connected Markov chain of a given structure from observing its outputs, to arbitrary precision, for a given confidence.

Introduction

In runtime verification, monitoring system statistics—such as identifying the most frequent request type (the mode) or typical latency (the median)—is essential for identifying behavioral anomalies and trends. However, standard real-time monitoring approaches are often resource-intensive. For a system with a large alphabet, such as a million unique IP addresses, an exact real-time monitor would require a million counters to track the mode accurately at every time step. This creates a significant memory bottleneck for embedded systems or high-speed network hardware.

This paper addresses this challenge by shifting the paradigm from exact real-time tracking to limit monitoring. The authors propose that if a system's behavior eventually stabilizes (e.g., as a connected Markov chain), it is possible to build a monitor that converges to the correct answer using significantly less memory by relaxing the requirement for instantaneous accuracy.

Methods

The proposed limit monitoring framework avoids tracking the entire alphabet simultaneously. Instead, it focuses on small subsets of data over "chunks" of increasing length.

The Tournament Algorithm

To identify the mode, the monitor employs a "Tournament Algorithm." It maintains a single "current champion" ($x$) and selects a "random challenger" ($y$). During a specific data chunk, the monitor only counts occurrences of $x$ and $y$. If the challenger $y$ appears more frequently than the champion $x$ within that chunk, $y$ becomes the new champion for the subsequent round.

Generalized Ergodic Theory

A key innovation is the extension of Ergodic theory. While standard Ergodic theory relates long-term averages to probabilities using prefixes of a sequence, this work generalizes the theory to arbitrary subwords (infixes) of increasing length. This mathematical foundation proves that sampling random chunks is statistically sufficient to identify the true underlying frequencies of a Markov chain.

A synthetic Markov chain model and a table demonstrating the convergence of event frequencies using prefixes versus infixes.

Key Results

The paper establishes several critical theoretical bounds and guarantees through mathematical proofs and synthetic Markov chain models:

  • The "Real-Time" Tax: The authors prove a lower bound showing that any exact real-time monitor for $\Sigma$-counting statistics (like mode and median) requires $\Omega(|\Sigma|)$ counters. This justifies the necessity of the limit monitoring approach.
  • Constant Memory Complexity: By relaxing the requirement for instantaneous accuracy, the memory requirement drops from $O(|\Sigma|)$ to $O(1)$. Specifically, the algorithm for the mode requires only four counters: two for the champion and challenger, one for the chunk length, and one for the current position.
  • Almost-Sure Convergence: For systems modeled as connected Markov chains, the monitor is proven to converge to the correct verdict with probability 1.
  • Convergence Rate: In simple i.i.d. cases, the probability of error decreases exponentially with the number of samples.

Discussion and Future Work

While the algorithm is highly memory-efficient, its time-efficiency—the speed of convergence—remains an open question, particularly for very large alphabets where the true mode might not be sampled as a challenger for a long time. Furthermore, the current proofs rely on the system behaving as a connected Markov chain. Future research could explore how these monitors perform in non-stationary or adversarial settings where an attacker might attempt to hide anomalies during periods when the monitor is not observing specific events.

Summary updated

Abstract

The monitoring of event frequencies can be used to recognize behavioral anomalies, to identify trends, and to deduce or discard hypotheses about the underlying system. For example, the performance of a web server may be monitored based on the ratio of the total count of requests from the least and most active clients. Exact frequency monitoring, however, can be prohibitively expensive; in the above example it would require as many counters as there are clients. In this paper, we propose the efficient probabilistic monitoring of common frequency properties, including the mode (i.e., the most common event) and the median of an event sequence. We define a logic to express composite frequency properties as a combination of atomic frequency properties. Our main contribution is an algorithm that, under suitable probabilistic assumptions, can be used to monitor these important frequency properties with four counters, independent of the number of different events. Our algorithm samples longer and longer subwords of an infinite event sequence. We prove the almost-sure convergence of our algorithm by generalizing ergodic theory from increasing-length prefixes to increasing-length subwords of an infinite sequence. A similar algorithm could be used to learn a connected Markov chain of a given structure from observing its outputs, to arbitrary precision, for a given confidence.
BibTeX
@inproceedings{ferrere2020monitoring,
  author = {Thomas Ferrère and Thomas A. Henzinger and Bernhard Kragl},
  title = {{Monitoring Event Frequencies}},
  booktitle = {CSL},
  year = {2020},
  url = {https://openreview.net/forum?id=SLbF36JNZq},
}
Figure