TL;DR
This paper introduces MetricForensics, a novel framework for analyzing "volatile graphs" – dynamic networks that change rapidly over time, like internet traffic. It tackles the challenge of extracting meaningful insights from massive, constantly evolving datasets by employing a multi-level "drill-down" approach that balances computational efficiency with in-depth analysis.
What Problem Does This Paper Address?
The explosion of data collection capabilities has led to the availability of highly dynamic network data, often referred to as "volatile graphs." These graphs, characterized by constantly appearing, disappearing, and changing edges and nodes, are common in areas like cybersecurity (internet communication traces) and social networks. Traditional graph analysis techniques, designed for static or slowly evolving graphs, struggle to keep up with the sheer volume and speed of changes in volatile graphs, especially when near real-time detection of events or anomalies is required. The core problem is how to efficiently and effectively mine these dynamic datasets to uncover interesting behaviors, events, and anomalies without being overwhelmed by the data's volatility.
Methods
MetricForensics proposes a three-pronged approach:
- Multi-Level "Drill-Down" Architecture: This is the cornerstone of the framework. It starts with coarse-grained analysis at a global level, using computationally inexpensive metrics. If an anomaly or interesting event is detected at this coarse level, the system "drills down" to finer temporal and topological resolutions. This means analyzing smaller time windows and focusing on specific communities or individual nodes, allowing for more detailed, but computationally intensive, analysis only where it's needed.
- Suite of Graph Metrics: MetricForensics utilizes a collection of graph metrics categorized into three levels:
- Global Metrics: These measure high-level properties of the entire graph (e.g., number of active vertices, eigenvalues). They are designed to be fast to compute, often scaling linearly with the number of active vertices or edges.
- Community Metrics: These focus on the structure of communities within the graph, typically more computationally expensive than global metrics.
- Local Metrics: These examine individual vertices and their immediate neighborhoods (e.g., centrality, ego-net analysis). These are the most computationally intensive and are applied only at the finest levels of refinement.
- Collection of Analysis Techniques: The framework supports various analysis techniques that can be applied to the computed metrics:
- Single Metric Analysis: Treating metric values over time as time series and applying techniques like ARMA models, Fourier analysis, or wavelet analysis to detect patterns and anomalies.
- Coupled Metric Analysis: Examining the relationships between two or more metrics, such as correlation analysis, to identify interesting events where expected correlations break down.
- Non-Metric Analysis: This includes visualization tools and attribute data inspection, used for deeper understanding once an event has been flagged by metric-based analysis.
The data model for volatile graphs involves representing the data as a sequence of "snapshot graphs" (the graph at a specific time) and "summary graphs" (aggregations of snapshots over a period), which helps manage the data's volatility.
Datasets
The authors evaluated MetricForensics on three real-world volatile graphs:
- ENTP: An enterprise IP traffic trace collected over 4.5 days in 2007.
- RMBT: MIT Reality Mining's Bluetooth proximity sensor data collected over 12 months.
- LBNL: IP traffic collected on an internal enterprise network on a specific date, which included scanning activities.
The largest of these datasets had approximately 3 million vertices and 32 million edges, spanning 4.5 days, demonstrating the framework's ability to handle large-scale volatile data.
Key Insights and Ideas
- "Elbow" Patterns: The paper identifies "elbow" patterns in the relationship between the largest eigenvalues (λ₁ and λ₂) of weighted graphs. These patterns indicate a shift in the dominant phenomenon driving the graph's structure, such as a heavy edge changing weight.
- "Broken Correlations": A significant finding is the observation of "broken correlations" between graph metrics. When metrics that are typically highly correlated suddenly diverge, it signals an interesting event or anomaly that warrants further investigation.
- "Prolonged Spikes": The analysis revealed "prolonged spikes" in activity, characterized by low-volume but sustained bursts of events. These are detected through fractal dimension analysis, which measures the "burstiness" of data.
- "Strange Stars": In local-level analysis of egonets (a vertex's immediate neighborhood), the authors discovered "strange stars" – nodes with many connections but unexpectedly low total edge weights, suggesting unusual interaction patterns.
- Multi-level approach is crucial for scalability: The core idea that analyzing coarse-grained metrics first to identify regions of interest before applying computationally expensive methods is key to handling massive, volatile datasets efficiently.
Key Results
The experiments demonstrated that MetricForensics can effectively:
- Detect interesting events and anomalies: The framework successfully identified the novel phenomena mentioned above ("elbows," "broken correlations," "prolonged spikes," and "strange stars") across different datasets.
- Scale to large datasets: The system was tested on graphs with millions of vertices and edges, showcasing its scalability and ability to provide near real-time analysis.
- Provide insights into network behavior: The discovered phenomena offer new ways to understand the dynamics of volatile graphs, particularly in cybersecurity contexts. For instance, "broken correlations" can highlight unusual network behavior that might indicate an attack.
Limitations and Future Work
- User Interaction: While the framework automates many analyses, some techniques like visualization and attribute inspection require user interaction, which can be a bottleneck for fully automated real-time systems.
- Flexibility of Metrics: The paper emphasizes that the framework is extensible to include more metrics and analysis techniques. Future work could involve exploring a wider range of metrics and their combinations.
- Real-time Performance: While the paper demonstrates scalability, achieving true real-time performance for all levels of analysis on extremely high-velocity streams might require further optimization.
- Attribution: The paper mentions attribution as a goal, and the multi-level approach is designed to facilitate it, but further research could focus on more direct attribution mechanisms.
Summary updated