10.1. Introduction

With 20 years of research on vulnerability analysis and intrusion detection, most critical computer networks are now under the protection of various security measures, such as access control, firewalls, intrusion detection systems (IDSs), and vulnerability scanners. With proper implementations, such measures can effectively thwart intrusion attempts made by amateur attackers and so-called script kiddies. However, real nightmares to a security administrator are usually caused by more experienced attackers who can easily circumvent basic security controls and detections through multistep intrusions. In such an intrusion, an attacker launches multiple attack steps that prepare for each other such that privileges can be gradually obtained and escalated on a series of intermediate hosts before he or she reaches the final goal.

Security administrators usually find it challenging to defend against multistep intrusions because most existing security tools have been designed to cope with individual incidents of attacks rather than correlated attacks. IDSs, such as Snort [1], can report intrusion alerts on isolated attack steps, but these systems are typically unaware of the relationships among attacks. It is generally difficult to identify correlated attacks corresponding to a multistep intrusion by manually inspecting the large amount of intrusion alerts reported by IDSs. Attackers can hide their intentions by deliberately triggering false attack attempts and by spreading an intrusion over a longer time period, both of which will make it more difficult for administrators to identify the intrusion. Similarly, vulnerability scanners can identify individual weaknesses in a host or network, but each identified vulnerability by itself usually does not seem to be a serious threat until it is combined with others in a cleverly-crafted multistep intrusion.

Penetration testing can sometimes reveal a potential multistep intrusion thanks to the heavy human intervention used in such a testing. However, due to the same reason, the effectiveness of such testing critically depends on the capabilities of the red team (representing attackers) and is prone to human errors. Topological vulnerability analysis can be regarded as an automated version of penetration testing [2, 3]. The result of such an analysis, the attack graph, can be used to harden a network such that critical resources can be protected at a minimal cost [2, 4, 5]. This approach provides an ideal solution to defending against multistep intrusions. However, the solution is not always feasible due to its incurred administrative costs and its potential impact on the availability of network services. In practice, we may have to live with some vulnerability, and to take actions only when an actual intrusion has been detected. This, though at a different level, is analogous to the fact that we need IDSs even though we already have vulnerability scanners. Finally, to ignore the correlation between attack steps and respond to each individual attack will cause large volumes of false-positive intrusions and effectively render a network useless.

In this chapter, we discuss real-time detection and prediction methods for less-than-ideal situations where vulnerabilities have to be tolerated. The methods will help administrators to monitor and predict the progress of actual multistep intrusions, and hence to take appropriate countermeasures in a timely manner. We first review the literature on alert correlation. Adding the missing relationships among attack steps, alert correlation techniques reassemble isolated IDS alerts into more meaningful attack scenarios. Previous alert correlation techniques typically either rely on domain knowledge about alert types or rely on statistical methods to identify the relationships among alerts. A more recent approach uses the knowledge obtained through topological vulnerability analysis to correlate alerts [6, 7]. Inspired by an ancient Chinese saying, “Know your enemy, know yourself, fight a hundred battles, win a hundred battles,” this vulnerability-centric approach starts from the knowledge about one’s own weaknesses (vulnerabilities) and incorporates information about one’s enemies (intrusion alerts). The approach shows a promising direction toward defeating multistep intrusions, because it inherits advantages from both alert correlation and topological vulnerability analysis. In particular, the knowledge about a network helps to filter out irrelevant alerts that do not correspond to vulnerabilities in the network.

In addition to filtering out irrelevant alerts, the vulnerability-centric approach also makes alert correlation immune to the so-called slow attack. Most previous alert correlation methods have been designed for offline applications, such as computer forensics. Thus, those methods typically have a computational complexity and memory requirement that are both proportional to (or worse than) the number of received alerts. This fact implies that only a limited number of alerts can be processed for correlation with a fixed amount of resources, such as memory. Such a limitation does not cause apparent problems in an offline application, because the number of alerts is already known and resources can be accordingly allocated. However, alert correlation in the real-time defense against ongoing intrusions brings a new challenge that renders many existing methods ineffective. A live attacker may be aware of the above-mentioned limitation. Thus, the attacker can exploit the limitation by following slow attacks. To prevent any two attack steps from being correlated, the attacker may either passively delay the second step or actively trigger false alerts between the two attack steps. In either case, correlation methods would be defeated.

To remove the above limitation, the vulnerability-centric alert correlation method first makes the key observation that not all alerts need to be explicitly correlated due to the transitive property of correlation relation. That is, if two attacks exploit the same vulnerability on the same host, and they both occur before a third attack that exploits a different vulnerability, then either both of the first two attacks prepare for the third attack (if the two vulnerabilities are related) or neither of them do (if the vulnerabilities are not related). To take advantage of this observation, the method materializes attack graphs as a special queue graph data structure. The queue graph only keeps in memory the last alert of each type, and only records explicit correlation relationship between two alerts if they are both in memory. As a result, both the time complexity and the memory requirement of alert correlation are now independent of the number of received alerts. Correlation can thus be established between any two alerts that may be separated by arbitrarily many others. Therefore, the correlation method is immune to the slow attack.

The method is also extended for the hypothesis of attacks missed by IDSs, for the prediction of possible future attacks and for the aggregation of repetitive alerts. Roughly speaking, we compare the knowledge encoded in the attack graph with the fact reflected in correlated alerts. An inconsistency between the knowledge and the facts implies potential attacks missed by IDSs, whereas extending the facts in a way that is consistent with the knowledge can indicate future attacks. To represent the analysis result in a compact way, an alert aggregation mechanism is also incorporated in the method, which ensures that no transitive edges will be introduced in the result graph and indistinguishable alerts will be aggregated. This capability is important because repetitive brute-force attempts may trigger a large number of similar alerts in a short time, and these alerts will render the result graph incomprehensible if not aggregated. Previously, alerts need to be aggregated prior to correlation, which adds extra overhead. Instead, the method described here interleaves alert aggregation with alert correlation, and the aggregation may actually make alert correlation faster. The described method can thus correlate, hypothesize, predict, and aggregate alerts all at the same time. Empirical results show that these tasks can be fulfilled faster than IDSs can report alerts. The method thus provides security administrators a practical tool in monitoring and predicting ongoing multistep intrusions.

The rest of this chapter is organized as follows. The next section reviews previous alert correlation and topological vulnerability analysis techniques. Section 10.3 introduces relevant concepts on attack graphs that will be needed in later sections. Section 10.4 then focuses on the vulnerability-centric method for alert correlation, hypothesis, prediction, and aggregation. Section 10.5 concludes the chapter.