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

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.

Introduction

Modern network security is a "big data" challenge. 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 often blind. GraphPrints addresses 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 identify exactly which device is acting up.

The GraphPrints Framework

GraphPrints treats network traffic as a dynamic graph where IP addresses are nodes and communications (flows) are edges. The framework operates in three primary stages:

  1. Graph Representation: Traffic is divided into discrete time slices (e.g., 31-second windows). Edges are categorized 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 simple metrics like packet counts, GraphPrints counts graphlets—small, induced subgraphs such as triangles or stars.
  3. Graph-level: Total occurrences of these shapes create a "handprint" of the entire network.
  4. Node-level: The system uses automorphism orbits, which describe the specific "role" a node plays within a graphlet (e.g., whether a node is the center of a star or a leaf). This creates a unique "fingerprint" for every IP.
Graphlet and orbit counting for network fingerprinting.
  1. Detection Framework: For the whole network, the Minimum Covariance Determinant (MCD) fits a robust Gaussian distribution to the graphlet counts, allowing the model to learn "normal" behavior even from messy training data. For individual IPs, k-means clustering is applied to orbit vectors; if an IP's behavior deviates significantly from its usual cluster, it is flagged.

Experimental Evaluation and Results

The authors evaluated GraphPrints using real-world traffic from a small office building, encompassing over 10,500 unique IP addresses. To test detection capabilities, they injected a recorded session of BitTorrent traffic. BitTorrent was chosen because its peer-to-peer structure creates a distinct topological signature compared to standard web browsing.

The system demonstrated exceptional accuracy in the BitTorrent test case, achieving a 100% True Positive Rate at both the network and IP levels. At the graph (time-interval) level, the false positive rate was 2.84%. Interestingly, some of these "false" positives were actually previously unknown IP scans discovered during the evaluation. At the node (IP) level, the false positive rate was a remarkably low 0.05%.

Network-level anomaly detection using Mahalanobis distance.

As shown in the detection results, the "anomaly scores" (Mahalanobis distance) for the BitTorrent traffic were significantly higher than the background noise, suggesting the method is highly sensitive to structural shifts.

Conclusion and Future Work

The core insight of GraphPrints is that how nodes connect is more telling than how much they communicate. Structural patterns like stars or cliques are strong indicators of specific behaviors, such as scanning or Command and Control (C2) activity. While highly effective, counting graphlets is computationally expensive. Future work will focus on scaling to larger graphlets and adding more "node colors"—such as labeling IPs by department—to identify even more 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},
}
Figure