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:
- 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).
- Graphlets and Orbits: Instead of simple metrics like packet counts, GraphPrints counts graphlets—small, induced subgraphs such as triangles or stars.
- Graph-level: Total occurrences of these shapes create a "handprint" of the entire network.
- 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.
- 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%.
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