FRAPpuccino: Fault-detection through Runtime Analysis of Provenance

Xueyuan Han, Thomas F. J.-m. Pasquier, Tanvi Ranjan, Mark Goldstein, Margo I. SeltzerHotcloud 2017

TL;DR

This paper introduces FRAPpuccino (FRAP), a novel system for detecting application faults and intrusions in cloud environments by analyzing runtime provenance data. FRAP models "normal" application behavior using a directed acyclic graph (DAG) of system interactions and flags deviations as anomalies, offering a more comprehensive approach than traditional system-call monitoring.

What Problem Does This Paper Address?

Cloud-based applications, particularly those deployed on Platform as a Service (PaaS) environments, are increasingly popular due to their scalability and efficient resource utilization. However, this growth also makes them prime targets for cyber-attacks and susceptible to runtime faults that can render them unavailable. Existing intrusion and fault detection systems often rely on limited views of application behavior, such as system call sequences, or require extensive manual configuration. This leaves a gap in effectively and automatically identifying anomalous behavior in complex, large-scale cloud applications without significant developer overhead.

Methods

FRAPpuccino tackles this problem through a three-stage process:

  • Learning Stage: FRAP models legitimate application behavior by analyzing its runtime provenance. Provenance data, representing interactions between system entities (files, sockets, processes, etc.), is captured as a directed acyclic graph (DAG). FRAP uses a dynamic sliding window to process this data efficiently, extracting feature vectors that represent the DAG's structure. These feature vectors are then clustered to identify patterns of normal behavior.
  • Detection Stage: New instances of an application are monitored, and their provenance data is converted into feature vectors. These vectors are compared against the learned model. If a feature vector falls outside the established clusters of normal behavior, the instance is flagged as an anomaly.
  • Revision Stage: The system can incorporate feedback to refine the model, particularly by re-clustering instances that were initially flagged as false positives.

A key innovation is FRAP's use of a vertex-centric graph processing framework (GraphChi) and a relabeling algorithm inspired by graph kernels. This allows FRAP to represent complex program interactions and their system-level effects in a compact, numerical format (feature vectors) for anomaly detection. FRAP also employs a dynamic sliding window to manage the potentially massive volume of provenance data, ensuring efficient online detection.

Datasets

Not discussed in the paper. The paper focuses on a simulated cloud environment with a Ruby server exhibiting an out-of-memory vulnerability.

Key Insights and Ideas

  • Provenance as a Richer Signal: FRAP demonstrates that analyzing comprehensive provenance data (interactions between entities) provides a more accurate and nuanced view of application behavior than solely relying on system calls.
  • Graph-Based Anomaly Detection: Representing application behavior as a provenance DAG and using graph relabeling techniques to generate feature vectors is an effective way to capture complex interactions for anomaly detection.
  • Dynamic Sliding Window for Scalability: The use of a dynamic sliding window is crucial for handling the high volume of provenance data generated by cloud applications, enabling real-time detection without excessive storage requirements.
  • Clustering for Normal Behavior Modeling: Clustering feature vectors derived from provenance data effectively distinguishes between normal and anomalous behavior, leveraging the assumption that most instances are legitimate.

Key Results

  • FRAP successfully detected an out-of-memory server crash vulnerability in a simulated cloud environment.
  • The system demonstrated that KLD (Kullback-Leibler Divergence) and Euclidean distance metrics were effective for anomaly detection, while Hellinger distance performed poorly due to its inability to create meaningful clusters.
  • Euclidean distance, while effective, occasionally produced false negatives during the learning stage, highlighting the importance of metric selection and model refinement.

Limitations and Future Work

  • False Positive Identification: The current method for identifying false positives is described as "crude," relying on detecting a large number of abnormal instances. The authors acknowledge that this assumption might not always hold, especially in scenarios where a legitimate but problematic behavior (e.g., a corrupted database) causes many failures.
  • Trustworthiness of Provenance Data: The system assumes provenance data is trustworthy and not tampered with. Securing provenance data against tampering is identified as an area for future work.
  • User Involvement: The authors propose that user involvement could help build better models by identifying false positives, suggesting differential provenance as a potential explanation mechanism.
  • Optimization and Integration: The current prototype requires manual intervention for the end-to-end pipeline and lacks full integration of the revision stage. Future work includes improving the global relabeling map, garbage collection, and exploring more advanced clustering algorithms like Principal Component Analysis.

Summary updated

BibTeX
@inproceedings{han2017frappuccino,
  author = {Xueyuan Han and Thomas F. J.-M. Pasquier and Tanvi Ranjan and Mark Goldstein and Margo I. Seltzer},
  title = {{FRAPpuccino: Fault-detection through Runtime Analysis of Provenance}},
  booktitle = {Hotcloud},
  year = {2017},
}
Figure