GraphPrints: Towards a Graph Analytic Method for Network Anomaly Detection

Christopher R. Harshaw, Robert A. Bridges, Michael D. Iannacone, Joel W. Reed, John R. Goodall

TL;DR

GraphPrints is a novel anomaly detection framework that fingerprints network traffic by analyzing its underlying graph structure. By counting "graphlets"—tiny, recurring sub-structures—it can identify both global shifts in network behavior and the specific IP addresses responsible for the anomaly with high precision and low false-positive rates.

What Problem Does This Paper Address?

Modern network security is a "big data" nightmare. Analysts are often buried under millions of flow records daily, making manual investigation impossible. Meanwhile, traditional signature-based tools (like firewalls or antivirus) only catch known threats. If an attacker uses a new technique or a "zero-day" exploit, these systems are blind.

The authors address the need for unsupervised anomaly detection: finding "never-before-seen" attacks by identifying qualitative changes in how devices communicate. The challenge is doing this at scale while providing enough granularity to tell an analyst exactly which device is acting up, rather than just sounding a general alarm.

Methods

GraphPrints treats network traffic as a dynamic graph where IP addresses are nodes and communications (flows) are edges.

  1. Graph Representation: They divide traffic into time slices (e.g., 31-second windows). Edges are colored based on port numbers: "blue" for well-known ports (standard services) and "red" for high-numbered ports (often used by peer-to-peer apps or custom malware).
  2. Graphlets and Orbits: Instead of looking at simple metrics like packet counts, they count graphlets—small, induced subgraphs (like triangles or stars).
  3. Graph-level: They count the total occurrences of these shapes to create a "handprint" of the whole network.
  4. Node-level: They use automorphism orbits, which describe the specific "role" a node plays within a graphlet (e.g., is the node the center of a star or just a leaf?). This creates a "fingerprint" for every IP.
  5. Detection Framework:
    • For the whole network, they use the Minimum Covariance Determinant (MCD) to fit a robust Gaussian distribution to the graphlet counts. This allows the model to learn "normal" even if the training data contains some existing anomalies.
  6. For individual IPs, they use $k$-means clustering on the orbit vectors. If an IP's behavior falls too far from its usual cluster, it’s flagged.

Datasets

The authors evaluated GraphPrints using real-world traffic collected from a small office building (including wired, wireless, and a small datacenter).

  • Ambient Traffic: 350 time windows of real office activity.
  • Implanted Anomaly: They "injected" a recorded session of BitTorrent traffic from a single host. BitTorrent was chosen because its peer-to-peer structure creates a distinct topological signature compared to standard web browsing.
  • Scale: The dataset included over 10,500 unique IP addresses.

Key Insights and Ideas

  • Structure as Behavior: The core "aha" moment is that how nodes connect is more telling than how much they talk. A botnet or a peer-to-peer file share creates structural patterns (stars, cliques, long paths) that look fundamentally different from a client-server relationship.
  • The Power of Orbits: By tracking orbits, the system doesn't just see that a node is busy; it sees that the node has suddenly become the "hub" of a star-shaped communication pattern, which is a strong indicator of scanning or C2 (Command and Control) activity.
  • Robustness to "Dirty" Data: By using MCD for the graph-level detection, the system can be trained on real, messy network data without the "normal" baseline being skewed by outliers or existing low-level attacks.

Key Results

The system demonstrated exceptional accuracy in the BitTorrent test case:

  • Detection Rate: 100% True Positive Rate at both the network and IP levels.
  • False Positives:
    • 2.84% at the graph (time-interval) level. Interestingly, some of these "false" positives were actually previously unknown IP scans discovered during the evaluation.
  • 0.05% at the node (IP) level, meaning it very rarely blamed the wrong device.
  • Clarity: The "anomaly scores" for the BitTorrent traffic were significantly higher than the background noise, suggesting the method is highly sensitive to structural shifts.

Limitations and Future Work

  • Anomaly Variety: The current study only tested one type of anomaly (BitTorrent). Future work needs to verify if this works for more subtle threats like slow data exfiltration or lateral movement.
  • Computational Complexity: Counting graphlets is computationally expensive. While the authors used 3-node graphlets effectively, scaling to larger graphlets (4 or 5 nodes) or more edge colors could lead to a "combinatorial explosion" in processing time.
  • Contextual Enrichment: The authors suggest that adding more "node colors"—such as labeling IPs by their country of origin or department—could make the fingerprints even more powerful for identifying sophisticated, targeted attacks.

Summary updated

Abstract

This paper introduces a novel graph-analytic approach for detecting anomalies in network flow data called GraphPrints. Building on foundational network-mining techniques, our method represents time slices of traffic as a graph, then counts graphlets---small induced subgraphs that describe local topology. By performing outlier detection on the sequence of graphlet counts, anomalous intervals of traffic are identified, and furthermore, individual IPs experiencing abnormal behavior are singled-out. Initial testing of GraphPrints is performed on real network data with an implanted anomaly. Evaluation shows false positive rates bounded by 2.84% at the time-interval level, and 0.05% at the IP-level with 100% true positive rates at both.
BibTeX
@inproceedings{harshaw2016graphprints,
  author = {Christopher R. Harshaw and Robert A. Bridges and Michael D. Iannacone and Joel W. Reed and John R. Goodall},
  title = {{GraphPrints: Towards a Graph Analytic Method for Network Anomaly Detection}},
  booktitle = {CISRC},
  year = {2016},
  url = {https://openreview.net/forum?id=ERUEfKR9omx},
}

Loading related content...

Figure