Anomaly Detection Using Program Control Flow Graph Mining From Execution Logs

Animesh Nandi, Atri Mandal, Shubham Atreja, Gargi Banerjee Dasgupta, Subhrajit BhattacharyaKDD 2016 · DOI

TL;DR

This paper introduces OASIS, a novel system for detecting anomalous behavior in distributed applications by mining their execution logs. It achieves this by constructing a "healthy state" control flow graph (CFG) from logs, overcoming limitations of prior work by not requiring application-specific knowledge or transaction IDs, and demonstrating high accuracy and scalability.

What Problem Does This Paper Address?

Troubleshooting distributed applications in cloud environments is a significant challenge due to the sheer volume and complexity of machine-generated data, particularly execution logs. While logs contain rich information, simply analyzing error messages is insufficient, leading to missed problems (low recall) or false alarms (low precision). Existing log mining techniques often rely on application-specific knowledge, assumptions about parameter formats, or the presence of explicit transaction identifiers, which are not always available in modern, heterogeneous microservice architectures. This paper aims to bridge this gap by developing a robust and scalable method to mine control flow graphs (CFGs) from interleaved execution logs without these restrictive assumptions, enabling accurate anomaly detection.

Methods

OASIS employs a multi-stage pipeline for CFG mining and anomaly detection:

  • Template Mining (Multi-modal): This is a core innovation. Instead of relying solely on text similarity, OASIS uses a "multi-modal" approach that combines textual content with temporal vicinity (i.e., the typical sequence of templates that appear before and after a given template). This helps overcome confusion caused by long or varied parameters in log messages. It first creates "approximate templates" by identifying invariant keywords and then refines these using temporal context.
  • CFG Edge Mining (Two-stage Sequence Mining): To mine the transitions (edges) between templates (nodes) in the CFG from interleaved logs, OASIS uses a novel two-stage approach. The first stage computes "Nearest-Neighbor-Groups" (NNS) for each template, identifying statistically co-occurring templates. The second stage then uses this NNS information to prune noise from interleaving and accurately identify immediate predecessors and successors, thus constructing the CFG edges.
  • Anomaly Detection: The mined CFG represents the "healthy state" of the system. OASIS detects two types of anomalies:
  • Sequence Anomalies: Raised when a parent node in the CFG is not followed by any of its expected children within a defined time lag.
  • Distribution Anomalies: Raised when the observed branching probabilities between a parent node and its children deviate significantly from the learned healthy state.

Datasets

The paper evaluates its methods using a combination of synthetic and real-world datasets:

  • Synthetic Datasets: Generated by a custom log generator to control parameters like CFG structure, template complexity, and levels of intra- and inter-parallelism. This allows for controlled evaluation against known ground truth.
  • Real-world Datasets:
    • linux: Linux system logs.
  • distMW: A proprietary distributed middleware application.
  • OpenStack: Logs from a popular cloud VM provisioning system, used for a case study of the end-to-end anomaly detection system.

Key Insights and Ideas

  • Temporal Vicinity is Crucial for Template Mining: Relying solely on text similarity for log template extraction is insufficient, especially with complex parameters. Incorporating the temporal context of log messages significantly improves accuracy.
  • Two-Stage Sequence Mining for Robust CFG Edge Extraction: Directly mining sequences from interleaved logs is challenging. A two-stage approach using NNS groups effectively filters out noise and identifies true transitions, overcoming limitations of traditional sequence mining.
  • CFG as a "Healthy State" Model: The control flow graph derived from logs provides a powerful, data-driven model of normal system behavior, against which deviations can be effectively detected.
  • Scalability is Achieved through Parallelization: The pipeline is designed for distributed execution, leveraging frameworks like Spark and Hadoop to process massive log volumes efficiently.

Key Results

  • Template Mining: OASIS's multi-modal approach consistently outperforms competitive methods (logcluster, loghound, edit-distance) in both precision and recall across various synthetic and real-world datasets, especially when dealing with long parameters and complex templates. For instance, on the distMW dataset, OASIS showed better precision and recall compared to other methods.
  • CFG Edge Mining: OASIS significantly outperforms alternative approaches (SM-vanilla, SM-tred, SM-wtred, PM, PM-noCID) in mining CFG edges, achieving high precision and recall even under high levels of intra- and inter-parallelism. For example, in a synthetic setting with 10 CFGs and 10 threads each, OASIS achieved precision > 90% and recall > 82%.
  • Scalability: The pipeline demonstrates excellent scalability, processing over 500 GB of log data per day on a 10-node low-end VM cluster. The processing time for each stage decreases significantly with an increasing number of worker nodes.
  • Anomaly Detection: The system achieves high precision for sequence anomalies and satisfactory precision and recall for distribution anomalies across various configurations. A case study with OpenStack successfully identified a sequence anomaly when a critical process was killed.

Limitations and Future Work

  • Template Mining Dependence on CFG Accuracy: While the multi-modal approach is robust, errors in the mined CFG can negatively impact template mining accuracy in real-world scenarios, potentially leading to merged incorrect templates or fragmented correct ones.
  • Sequence Anomaly Misses at Merge Points: Sequence anomalies can be missed when injected at parent nodes of popular merge points, as the anomaly detection algorithm might not differentiate between multiple paths leading to the merge.
  • Distribution Anomaly Fluctuations: Occasional misses and false alerts in distribution anomalies are attributed to not capturing the full spectrum of workload fluctuations due to the time-windows used for measuring branching probabilities.
  • Future Work: The authors call for more research in accurately classifying log lines to ground truth templates without application-specific knowledge. They also suggest improving distribution anomaly detection by using smaller time-windows and larger training datasets to better capture benign fluctuations.

Summary updated

BibTeX
@inproceedings{nandi2016anomaly,
  author = {Animesh Nandi and Atri Mandal and Shubham Atreja and Gargi Banerjee Dasgupta and Subhrajit Bhattacharya},
  title = {{Anomaly Detection Using Program Control Flow Graph Mining From Execution Logs}},
  booktitle = {ACM SIGKDD Conference on Knowledge Discovery and Data Mining},
  year = {2016},
  doi = {10.1145/2939672.2939712},
}
Figure