10.2. Review of Alert Correlation and Related Techniques

Although most alert correlation techniques share the same objective of discovering relationships among isolated alerts, these techniques have evolved with respect to the different relationships they discover. Early work on alert correlation usually focused on the syntax similarity between alerts. That is, they group alerts with similar attributes into natural clusters to simplify the further examination of alerts [8–11]. These techniques are especially useful as preprocessing steps prior to other analyses. Some of the techniques correlate similar alerts based on their statistical or temporal similarity [12, 13]. Such methods can provide supplementary results about unknown attacks or unknown relationships among attacks.

Rather than relying on the syntax similarity, such as between similar attributes, other techniques aim to discover semantic similarity between attacks, such as the case that one attack is used by attackers to prepare for another. Some techniques use knowledge about known attack strategies or scenarios to find correlated attacks that match these strategies or scenarios [14–18]. These methods are analogous to misuse detection in that the strategies or scenarios play the role of signatures. Treating a complete strategy or scenario as a signature also leads to the limitation that variations from the signature will usually be ignored. This limitation was soon addressed by splitting the strategy or scenario into pairs of alert types that can be correlated with common pre- and postconditions [18–20].

The correlation between alerts discovered in Templeton and Levitt [18], Cuppens and Miege [19], and Ning et al. [20] is sometimes called a causal relationship. This reflects a key difference from the afore-mentioned work that defines a complete strategy or scenario as a signature in matching alerts. With respect to the causal relationship, two alerts are correlated if the former satisfies at least one security-related condition required by the latter. The role of the former attack can be regarded as contributory since it makes the second attack easier but not necessarily possible. On the other hand, previous approaches correlate a set of alerts to another alert, only if the former collectively satisfies all the conditions required by the latter.

Using the causal relationship between alerts reduces the complexity of alert correlation, because the relationship exists between a pair of alerts instead of between two sets of alerts. The causal relationship also makes it possible to tolerate attacks missed by IDSs because an alert will be correlated with others even if some of its required preconditions are not satisfied. On the other hand, correlation based on the causal relationship may introduce false positives, and the results also lack high-level attack strategies used by the attacker. A later work aims to extract such strategies from correlated alerts based on knowledge about different types of attacks that may play the same role in a multistep intrusion [21]. This work also attempts to reduce noises in the correlation result through verification against raw audit logs.

Combining domain knowledge with other information, such as the statistical or temporal similarity between alerts and common resources shared by alerts, leads to hybrid approaches that can discover unknown relationships among alerts [22, 23]. A recent work attempts to increase the validity of correlation by borrowing a technique for tracking operating system (OS) level events [24]. The assumption there is that each network attack will also trigger a series of interdependent OS events, such as the reads or writes of the same file. Thus, the correlation between two alerts is more convincing if the OS events they trigger are correlated. The interdependency between OS events is considered as hard evidence since it is inherent to the operating system and not prune to potential human errors in domain knowledge. Alert correlation is also shown to be helpful in dealing with insider threats [25, 26].

Closely related to the vulnerability-centric alert correlation method we describe below, topological vulnerability analysis techniques address the lack of relationships among vulnerabilities reported by security scanners. The interdependency between vulnerabilities and security conditions has long been investigated [27–31]. By regarding each exploitation of vulnerability as a state transition between the set of preconditions and that of postconditions, model checking was first used to analyze whether the given goal condition is reachable from the initially satisfied conditions [32, 33]. Later, a modified version of the model checker was used to enumerate all possible sequences of exploits between the two [2, 34]. The result of such an analysis was called an attack graph.

The above notion of attack graph explicitly includes all sequences of attacks that lead to compromises of given critical resources. However, attack graphs also face a scalability issue due to an exponential explosion in the number of potential attack sequences. A more compact representation of attack graphs was thus proposed to address this issue [3]. Underlying the new representation of attack graphs is the monotonicity assumption that says an attacker never needs to relinquish any obtained capability. Under the assumption, each exploit appears at most once in any sequence of attacks. In another word, each exploit (or condition) corresponds to no more than one vertex in the attack graph. This fact guarantees that an attack graph always has a polynomial size in the total number of vulnerabilities and security conditions. In this chapter, we shall assume such a compact representation of the attack graph.