Dynamic Adaptation of Rules for Temporal Event Correlation in Distributed Systems

Rean Griffith, Joseph L. Hellerstein, Yixin Diao, Gail E. KaiserColumbia 2005 · DOI

TL;DR

This paper tackles the challenge of reliably detecting events in distributed systems by correlating temporal patterns, which is often hindered by unpredictable event propagation delays. They introduce an adaptive control architecture that dynamically adjusts correlation rule timers to compensate for these delays, leading to more autonomous management and improved detection accuracy compared to fixed timer settings.

What Problem Does This Paper Address?

In distributed systems, understanding what's happening often requires correlating events that occur across multiple machines over time. Think of detecting a denial-of-service attack by noticing a surge of failed login attempts across several servers within a short window, or monitoring a complex application by tracking the sequence of events across its various components. The core of this detection relies on "temporal event correlation" using rules that specify patterns of events and time constraints.

A major hurdle in this process is the variability of event propagation delays. Events don't travel instantaneously from their source to a central management station. Factors like network congestion, server load, and even administrative tasks can cause these delays to fluctuate significantly. This "propagation skew" means that the time an event actually arrives at the management station might be quite different from when it was generated. If correlation rules use fixed timer values based on ideal, consistent delays, this variability can lead to two undesirable outcomes:

  • False Alarms: The system incorrectly flags an event as a problem because a legitimate event arrived later than expected, triggering a rule.
  • Undetected Alarms: The system misses a real problem because an event arrived too late, falling outside the rule's timer window.

The paper aims to solve this by making the event correlation process more robust and autonomous, reducing the need for manual tuning of timer values by system administrators.

Methods

The paper proposes a novel architecture and an adaptive control algorithm to address propagation skew.

Architecture: The core idea is to introduce "Calibration Probes" and a "Probe Monitor" alongside the existing management station infrastructure.

  1. Calibration Probes: These are special components that generate "Calibration Events." These events are designed to form specific "Calibration Patterns" with known, predetermined generation times.
  2. Probe Monitor: This component, running on the management station, receives these Calibration Events and measures the actual propagation skew for each event in a Calibration Pattern.
  3. Controller: This is the brain of the adaptive system. It receives the measured propagation skews from the Probe Monitor and uses them to dynamically compute "slack times."
  4. Adaptive Rules: The correlation rules themselves are modified to incorporate these computed slack times. Instead of just using a fixed timer value, the effective timer becomes the original timer value plus the dynamically calculated slack time. This slack time is essentially an adjustment to compensate for the estimated propagation skew.

Adaptive Control Algorithm: The algorithm focuses on maximizing the "minimum probability of a correct result" (MAPC). This metric considers both the probability of correctly generating an alarm when one is needed (avoiding undetected alarms) and the probability of correctly not generating an alarm when none is needed (avoiding false alarms). The algorithm uses a non-parametric approach to estimate the median of the propagation skew distribution. It maintains a buffer of recent propagation skew measurements and calculates the median of this buffer. This median skew value is then used to determine the slack time. The intuition is that setting the slack time to the median skew will help balance the trade-off between false and undetected alarms.

Datasets

The paper does not explicitly mention using pre-existing datasets for training or evaluation. Instead, they developed a testbed system to generate their own data. This testbed involved:

  • Event Sources: AMD Athlon XP machines.
  • Management Station: A 3 GHz P4 machine.
  • Event Transport: Siena Publish/Subscribe bus.
  • Configurations: They tested both "unloaded" (separate machines for event distiller and Siena) and "loaded" (event distiller and Siena co-located) configurations.
  • Synthesized Traces: For some experiments, they synthesized propagation skew traces by alternating between data from loaded and unloaded configurations to simulate non-stationary environments.

Key Insights and Ideas

  • Propagation Skew is a Major Problem: The paper convincingly demonstrates that propagation skew can be substantial (up to 50% of pattern generation time in their testbed) and significantly impacts the reliability of temporal event correlation.
  • The Trade-off is Fundamental: There's an inherent tension between avoiding false alarms and avoiding undetected alarms. Aggressively trying to catch every event can lead to too many false positives, while being too conservative can lead to missed critical events.
  • Median Skew is Key for Balance: The adaptive algorithm's core insight is that setting the slack time to the median of the propagation skew distribution offers a good balance between the two types of errors. This is because it aims to make the system equally sensitive to events arriving slightly early or slightly late relative to the ideal.
  • Autonomy is Achievable: The proposed architecture and algorithm enable a "self-managing" system by automatically adjusting timers, reducing the need for manual intervention by administrators.
  • Adaptation Works Even with Imperfect Data: The adaptive algorithm performs well even when propagation skews are not perfectly independent (i.e., have autocorrelations), which is a common scenario in real-world systems.

Key Results

  • Improved Accuracy: The adaptive control algorithm consistently achieved results as good as, and often better than, the best possible fixed slack time setting across various scenarios (unloaded, loaded, and non-stationary propagation skews).
  • MAPC Metric: The Minimum Average Probability of a Correct Result (MAPC) metric effectively quantifies the performance of the adaptive system, showing significant improvements, especially in loaded configurations. For instance, in a loaded scenario, MAPC improved from 0.44 with a fixed slack time of 0 to 0.75 with an adjusted fixed slack time, and the adaptive algorithm consistently matched or exceeded this.
  • Buffer Size Impact: The adaptive algorithm's performance is sensitive to the buffer size (N) used for estimating the median skew. For stationary skews, a larger N is better, but for non-stationary skews (where distributions change), smaller buffer sizes (around 5-7) adapt faster and perform better.
  • Substantial Skew Measurement: Their testbed experiments revealed propagation skews that were substantial, often around 50% of the pattern generation time.

Limitations and Future Work

Limitations: * Independence Assumption: The adaptive control algorithm relies on the assumption that propagation skews are independent and identically distributed. While the algorithm performs well even with some autocorrelation, significant deviations from this assumption could impact performance. * Buffer Size Tuning: While the paper suggests optimal buffer sizes (N) for different scenarios, there's still a parameter to consider. * Testbed Specificity: The results are based on a specific testbed configuration. Generalizing these findings to vastly different network environments or system architectures might require further validation.

Future Work: * More Extensive Measurements: The authors plan to conduct more extensive measurements of propagation skews in diverse environments. * More Complex Temporal Patterns: The current work focuses on relatively simple temporal patterns. Future work will extend the approach to handle more complex patterns. * Cost-Sensitive Alarms: The current algorithm aims for a balanced probability of correct results. Future work could incorporate different costs for false alarms versus undetected alarms to tailor the system's behavior.

Summary updated

Abstract

Event correlation is essential to realizing self-managing distributed systems. For example, distributed systems often require that events be correlated from multiple systems using temporal patterns to detect denial of service attacks and to warn of problems with business critical applications that run on multiple servers. This paper addresses how to specify timer values for temporal patterns so as to manage the trade-off between false alarms and undetected alarms. A central concern is addressing the variability of event propagation delays due to factors such as contention for network and server resources. To this end, we develop an architecture and an adaptive control algorithm that dynamically compensate for variations in propagation delays. Our approach makes Management Stations more autonomic by avoiding the need for manual adjustments of timer values in temporal rules. Further, studies we conducted of a testbed system suggest that our approach produces results that are at least as good as an optimal fixed setting of timer values.
BibTeX
@inproceedings{griffith2005dynamic,
  author = {Rean Griffith and Joseph L. Hellerstein and Yixin Diao and Gail E. Kaiser},
  title = {{Dynamic Adaptation of Rules for Temporal Event Correlation in Distributed Systems}},
  booktitle = {Columbia},
  year = {2005},
  doi = {10.7916/d8fb59tw},
}
Figure