# A Hierarchical Security Event Correlation Model for Real-Time Threat Detection and Response
## 1 Introduction
### Related Works
#### 1.2.4 Correlation and Clustering Algorithms  
Clustering algorithms can be categorized in several ways. One way is whether the algorithm is optimized for numerical or categorical data. Depending on the features selected, network events can be clustered using either category. For example, [PERSON]. [21, 22] used a numerical-based approach, by calculating the entropy of the different IP header fields to cluster the data. By analyzing the entropy values, certain attack types could be reasoned. As an example, during the scan phase of an attack, few attacking IP addresses attack many ports on a few targets. The entropy value of the destination port addresses would be low for a port-scan attack.  
In terms of the categorical features of a network event, researchers have often turned to clustering using the CLIQUE [23] algorithm and its variants. According to the recent comprehensive survey on clustering algorithms performed by [PERSON] and [PERSON] [24], CLIQUE can handle high-dimensional data, with a computational complexity that is quadratic with the data dimensions and linear with the number of objects. This means that algorithm performance suffers with high data volumes. The feature set of a network event defined in our paper is five-dimensional; therefore, the algorithm should perform well in a deterministic way. The volume, however, is huge, as network traces from packet snifferscan grow very huge in a small amount of time. Additionally, the first step of CLIQUE is Apriori-like, in which it builds singleton clusters, i.e., clusters of one frequent itemset. It then gradually combines the clusters into bigger partitions of increasing combinations of the feature space before deciding which of those partitions forms a cluster. While this algorithm has successfully been used to identify clusters, the computational complexity of mining frequent itemsets is often cited as its biggest weakness [25].  
In terms of mining patterns from event logs, [PERSON] [26] proposed an algorithm that performed data summaries in the first run in the same manner as CLIQUE. In the second step, candidate clusters were created in the cluster table, and the final round of data points were allocated to a matching cluster candidate if it existed; otherwise, a new entry was created. This algorithm was suitable for event logs of textual data, where the feature space could not be figured out beforehand. For real-time clustering, [PERSON] et al. [16] initiated a memory queue Q, into which they deposited an incoming stream of alerts. All alerts that matched a set of mined features were fused into a hyperalert which had features that were a combination of the features of the constituent elementary alerts. They used the temporal similarity to purge a hyperalert from the queue if the incoming alert exceeded a given temporal threshold. The hyperalerts were further stored into a database for further offline analytics. Their approach was tailored to the real-time clustering of alerts and extracted features that were present in typical alert messages but not in the raw events, as is the case with this research.  
Our paper concurs with the conclusion by [PERSON] and [PERSON] [24] that no clustering algorithm is universally suitable for all problems. With that in mind, we present our own developed correlation and clustering algorithm that considers the uniqueness of the problem at hand. The clustering algorithm takes into consideration the characteristics of network event data to be clustered. Some of the characteristics are summarized below.  
* The data space dimensionality is small and fixed. More precisely, the event log entry as defined is a five-tuple record.
* Each event can belong to candidate clusters that can be defined by the set of predefined mining rules.
* The data of the mined features are categorical.