TL;DR
This paper introduces a novel relational clustering approach for analyzing enterprise network traffic. By leveraging Markov Logic Networks (MLNs) and a new "set evidence" formulation, it effectively groups network ports into services, offering administrators a clearer understanding of network behavior and potential security risks without relying on traditional, often brittle, port-based or payload inspection methods.
What Problem Does This Paper Address?
Network administrators are overwhelmed by the sheer volume of network traffic data. Analyzing this data to understand user behavior, detect anomalies, and identify services is a critical but challenging task. Traditional methods often involve manual inspection of filtered data, which is time-consuming and requires deep domain expertise. Existing automated approaches, like clustering, often rely on extracting features from connection data, where the quality of feature selection significantly impacts performance. Furthermore, many methods struggle to naturally incorporate relational information between network entities (like users, applications, and servers) and the concept of "set evidence" – where multiple entities are known to belong to the same group. This paper aims to bridge this gap by developing a relational clustering method that directly models these relationships and handles set evidence more effectively, leading to more interpretable and actionable insights for network management and security.
Methods
The core of this paper's contribution lies in its novel application and extension of Statistical Relational Learning (SRL), specifically Markov Logic Networks (MLNs), for network service clustering.
- Markov Logic Networks (MLNs): MLNs are a powerful framework that combines first-order logic with probabilistic graphical models. They allow for the representation of complex relationships between entities and their associated probabilities using weighted logical formulas. This is a significant departure from traditional vector-space models, as MLNs can directly model relations without requiring explicit feature extraction.
- Set Evidence Formulation: A key innovation is the introduction of "set evidence" to MLNs. Instead of relying solely on pairwise relationships, this method incorporates evidence that a group of ports (entities) likely belong to the same service. This is crucial because network services often involve multiple ports that are functionally related, but not necessarily in a direct pairwise manner. The paper proposes three variations of a "SetE" function (SetE₁, SetE₂, SetE₃) to integrate this set evidence into the MLN framework, each with slightly different ways of penalizing inconsistencies.
- Greedy Clustering Algorithm: To address the NP-hard nature of MLN inference, the authors propose a greedy clustering algorithm. This algorithm iteratively merges clusters (services) that yield the maximum gain in total weight, aiming to find a good partition of ports into services.
Datasets
The authors evaluated their approach using two types of datasets:
- Synthetic Dataset: A synthetic dataset was generated to simulate network traffic and service behaviors. This dataset allowed for controlled experiments, including the introduction of "noise" (incorrect set evidences) to test the robustness of the algorithms. The size and characteristics of this dataset are detailed in Table 2.
- Nexthink Dataset: A real-world enterprise network traffic dataset was collected from July 2008 to September 2008 by Nexthink. This dataset contains TCP/UDP connection records along with associated user and application information. Due to the lack of ground truth labels for network services in this real-world data, evaluation primarily relied on unsupervised measures like modularity.
Key Insights and Ideas
- Relational Modeling is Key: The paper strongly advocates for relational modeling over traditional feature-based approaches for network traffic analysis. MLNs' ability to directly incorporate relationships between entities (ports, applications, destinations) provides a more natural and powerful way to understand network behavior.
- Set Evidence for Services: The concept of "set evidence" is a critical insight for accurately clustering network services. Many services are defined by a collection of ports that work together, and modeling this group behavior is more effective than just looking at individual port connections or pairwise relationships.
- Interpretability Matters: The goal is not just to cluster, but to provide interpretable clusters. The identified services offer administrators a high-level overview of network functions, helping them understand server roles and potential security risks (e.g., identifying file sharing ports or groups of malware).
- Robustness to Noise: The proposed relational methods, particularly SetE₁, showed robustness to noisy data, maintaining performance where traditional methods might falter.
Key Results
- Synthetic Data Performance: On synthetic datasets, the proposed relational clustering methods (especially SetE₁) consistently outperformed k-means and other relational methods in terms of PWF score, indicating better clustering accuracy.
- Real-World Data Insights: For the Nexthink dataset, the relational clustering approach successfully identified meaningful groups of services, including "ports range" and "ports function." Notably, it was able to identify malware groups that were not easily distinguishable by k-means.
- Modularity as an Indicator: The study found a correlation between PWF scores and modularity measures (Q1 and Q2) on synthetic data, suggesting that modularity can serve as a useful unsupervised evaluation metric when ground truth is unavailable.
- Algorithm Behavior: Different SetE functions exhibited distinct intermediate clustering behaviors on the Nexthink dataset, with SetE₂ showing the highest modularity at the end of the algorithm, suggesting its strength in capturing community structure.
Limitations and Future Work
- Computational Complexity: Relational clustering, especially with MLNs, is computationally intensive (NP-hard). The paper uses greedy algorithms and Monte Carlo methods to mitigate this, but exact inference remains a challenge.
- Online Clustering: The current approach is not designed for real-time, online analysis. Future work aims to develop an online version of the clustering algorithm, which is challenging because relational clustering results can be sensitive to the order of incoming data.
- Incorporating More Relations: The current model primarily uses connectivity information. Future work could incorporate additional relational data, such as interactions between applications and users, to further refine service discovery and potentially eliminate the influence of "universal" applications that span many services.
Summary updated