Abstract: With the increase in number of components that makes up a computer network, and increase in attack types, large amounts of low level alerts are being generated by an Intrusion detection systems (IDS). It is difficult to make sense of these alerts by themselves, the manual task of finding the relationship among them would take huge time. Hence, came the need of Alert Correlation systems.
Keywords: Intrusion Detection System, Alert Correlation, Alert
An intrusion detection system (IDS) is an automated software that is capable of scanning all the activities that occur in the network. There are 3 main methodologies used by these systems; signature based, anomaly based, and stateful protocol analysis. When an event occurs in a network, the IDS analyse the event using one of the above mentioned methodology, to determine if that event is malicious or not. If it is found to be malicious, an alert is generated that is passed to the system administrators.
Due to increase in the number of automated systems, that tries to infiltrate a network (such as nmap, Nessus), a huge amount alerts may be generated by an IDS. The number alerts increases, when multiple IDS sensors are used at different points in the network. In addition to this, IDS lack the capabilities to identify the relationships among different alerts. As a result, it is time consuming and challenging to analyse all the generated alerts.
To fulfil this gap, alert correlation systems were introduced. Paper (1) define alert correlation as a conceptual interpretation of multiple alerts such that new meanings are assigned to these alerts. The alert correlation system tries to identify the relationships among the alerts, to give a high level picture of what is happening.
This paper is written to give an introduction to what alert correlation is, to identify the basic building blocks of these systems and to identify the categories of alert correlation algorithms. In this regard, section 2, looks at the fundamental operations of these systems. While the section 3, looks at different algorithms that have been designed to correlate alerts.
2. Fundamental Correlation Operations
The different types of alert correlation can be identified based on the correlation operation that is executed on alerts. According to the paper (2), these operations could be divided into 7 types. They are compression, filtering, selective suppression, thresholding, modification, generalization, enrichment and specialization.
Compression operation consists of detecting the number of same alerts, which occurred in a given time frame and generating a new alert, which includes the count of each alert type. This method loses some data, such as the time at which the alerts occurred. If it is lossless, then the operation is referred as aggregation (2). For example, if alert a, b, c occurred 2,3,1 times respectively within a time frame, the compression process will generate a new alert d, which will include the number of time each alert occurred.
2.2 Filtering operation
Filtering is the process of filtering out alerts based on certain parameters. This operation may lead to many losses as well. Eg. If a filter is in place to filter out alerts with the attribute ‘c’, if any alerts with attribute ‘a’ and ‘c’, or ‘c’ and ‘d’ may be filtered out. Only alerts that contain attribute ‘c’ will pass through.
2.3 Selective Suppression
Selective suppression operation consists of discarding of alerts based on a predefined criteria. The criteria may involve discarding of an alert if another type of alert is present, or due to a priority setting. For example, alert type 1 may be discarded if alert type 3 is present.
This operation generates an alert if a particular type of alerts is generated beyond a certain threshold value within a certain time period. This method may result in huge loss of information, as many alerts may not be reported to the analyst, if they do not meet the threshold value.
Modification correlation operation works by which, depending on a context, an alert may be replaced by another one. This approach may result in loss of information as well, if the modification is irreversible. An example of this process, may include the alert priority could be modified due to the presence of a certain condition.
Generalization is the operation by which a certain group of alerts are replaced by another alert, if they meet certain characteristics. For example, many alerts may be generated during nmap scanning, a new alert may be created by correlation process, which says ‘nmap scanning took place.’
This is the opposite operation of generalization, by which multiple alerts are generated based on an alert using a deductive type reasoning (2). These alerts may be specialised based on data from the database and configurations. For example, if alert type 5 occurs, system knows that for that type of alert to occur alert type 6, and alert type 7 should have been present, hence the system generates new alerts for alert type 6 and 7.
Enrichment operation consists of generating an alert which contains additional information based on previous data. For example, if an alert type 7 occurs, system adds additional information such as a list of possible attack types.
3. Alert Correlation Algorithms
Alert correlation algorithms can be categorised into 3 main types, based on the characteristics. They are similarity based, knowledge based and statistical based correlation algorithms.
Similarity based algorithms, works by detecting the similarities between alerts. These similarities are determined by a rule set which is defined by the analyst. The second category, knowledge based correlation, requires a database of knowledge consisting of fixed patterns and alert histories in the correlating process. The statistical-based approach requires the least amount of knowledge. These algorithms can detect alert that occurs outside the norm of the normal alerts. They are also referred as an anomaly based alert correlation.
The following sub-section explains each of the category separately and highlight some of the works done by researchers in each category.
3.1 Similarity based correlation
These algorithms works on the basis that there has to be a factor that would define a particular set of alerts. If this defining factor is found in an alert or a cluster of alerts (meta-alert), in a given period of time, these alerts are merged to form a new alert or a new meta-alert is formed.
This group of correlation algorithms can be subdivided in to three types. They are simple rules, hierarchal rules and machine learning. (3) Simple rules category works on the basis that rules need to be designed expressing relationships among the attributes of alerts. The second sub category, find alerts, that identifies the drawbacks of network architecture. This type of algorithms are needed as network issues are persistent, and require special handling or should be discarded. Finally, the machine learning algorithm works by automatically building models with special parameters, which could be used to identify an attack type from a group alerts.
In the paper (4) simple rule based Emerald product is discussed. These algorithms work by defining a rule set which tries to match the relationships among the attributes of alerts. These rules are evaluated among alerts to identify the relationships among them. Hence, these systems does not require a large database of knowledge.
This type algorithms forms hierarchical abstraction levels, and these levels are used to make decisions about security events. This type of algorithms work on the premise that an alert occurs due to some reason also referred as “root cause”. The paper (5) argues that 90% of alerts generated by an Intrusion detection system are due to a root-cause. And these alerts are persistent and should be removed as it floods the IDS, hiding more imminent threats on the network.
The last sub category of similarity based correlation is machine learning. These algorithms generate comparison factors automatically during training process. Machine learning algorithms could be of supervised or unsupervised. For a supervised machine learning algorithm, a set of clustered alerts should be given during the training process, using which the algorithms builds models based on a set of parameters specified by the supervisor. On the other hand, for an unsupervised algorithm, the perimeters are decided by the system, during the training process.
3.2 Knowledge based correlation
This type of algorithms requires a knowledge base in order to work. These can be further divided based into two categories based on the knowledge it requires. They are scenario based and pre/post condition based.
Scenario based algorithms are based on the idea that the attacker must follow specific actions for a success of an attack. The second type of correlation, works by defining a set of pre-requisites and the expected result for a particular attacks. This type of algorithm lacks alert correlation against unknown attack types.
These types of algorithms are used to identify multi-step attacks. Scenario based algorithm assume that for a particular attack type to occur, the attacker will follow a known sequence of steps.
Paper (6) introduce an approach which automatically analyse multiple alerts generated by an IDS, and group them based on the likelihood of them belonging to a particular attack scenario. They achieved this by using self-organizing maps and unsupervised clustering algorithms.
Pre/post condition based
This category of algorithms are implemented by defining a knowledge base, which include a prerequisite for an alert to occur, such as network configurations and structure, and post conditions that follows it. With the help of this knowledge base, the systems are capable of identifying the alerts which belongs to groups, hence reducing the number of alerts shown to the security analyst.
3.3 Statistical based correlation
These algorithms works on the idea that some attacks will have similar statistical attributes and can be categorized based on these attributes. These types of algorithms store causal relationships between different incidents and analyses there occurred frequencies in the system education period using previous data statistical analysis and then attack steps are generated (3).
Purely statistical based approach does not require a knowledge base of attack types. But according to paper (3) these algorithms yield good result only in a specific domain, otherwise results in a high error rate.
Below summarizes the comparison of algorithms done on paper (3). According to the results obtained by them, a complete alert correlation system needs a hybrid approach, which include algorithms addressing all concerns.
|Combining alerts from various sensors||Yes||Yes||No|
|Detect false alert||Yes||Yes||Guessing|
|Detecting multi-staged attacks||Hardly||Yes||Guessing|
The state of art intrusion detection systems are capable of identifying almost all possible attack types. Due to increase in the number of attacks, these systems generates a huge amount of alerts, which are over whelming and time consuming for an analyst to analyse. In order to address these issues, alert correlation systems are needed. This paper summarized fundamental correlation approaches used by these systems. Moreover, different categories of alert correlation algorithm was introduced and discussed.
This paper looked at several techniques that have already been developed in this area, each addressing different concerns in alert correlation systems. I hope this paper gives a better understanding of alert correlation systems and would be useful in furthering the knowledge of this topic.
- A Survey on IDS Alerts Processing Techniques. SAFAA O. AL-MAMORY, HONG LI ZHANG. s.l. : 6th WSEAS International Conference on Information Security and Privacy, 2007.
- Fabien Pouget, Marc Dacier. Alert Correlation: Review of the state of the art. 2003.
- Seyed Ali Mirheidari, Sajjad Arshad, Rasool Jalili. Alert Correlation Algorithms: A Survey and Taxonomy. 2013.
- Skinner, Alfonso Valdes and Keith. Probabilistic Alert Correlation. 2001.
- Julisch, Klaus. Clustering Intrusion Detection Alarms to Support. s.l. : ACM Journal, 2002.
- Multistep Attack Detection and Alert Correlation in Intrusion Detection Systems. Fabio Manganiello, Mirco Marchetti, and Michele Colajanni. 2011. Vol. 200.