10.3. Attack Graph

Attack graph is the basis of the vulnerability-centric approach we are going to discuss in the rest of this chapter. This section briefly reviews relevant concepts and states our assumptions. Attack graphs represent prior knowledge about network connectivity and the dependency between vulnerabilities. There have been two different representations for an attack graph. First, an attack graph can explicitly enumerate possible sequences of vulnerabilities (i.e., attack paths) that an attacker can follow [2,34]. Second, an attack graph can be represented by the dependency relationships among vulnerabilities, whence attack paths are encoded implicitly [3]. This representation does not lose any information under the monotonicity assumption, which states that an attacker never needs to relinquish any obtained capability. The resulting attack graph has no duplicate vertices, and hence has a polynomial size in the number of vulnerabilities multiplied by the number of connected pairs of hosts. We shall assume this latter notion of attack graphs.

An attack graph of the second notion is usually represented as a directed graph with two types of vertices: exploits and pre- or postconditions. An exploit is a tuple (v,h_S,h_m1,h_m2,...,h_d). This indicates an exploitation of the vulnerability v on the destination host h_d, initiated from the source host h_s and through a series of intermediate hosts h_m1,h_m2, and so on. In particular, for exploits involving two hosts (with no intermediate host) or one host (in local exploits), we use (v,h_s,h_d) and (v,h), respectively. Similarly, a security condition is a triple (c,h_s,h_d) that indicates a security-related condition c involving the source host h_s and the destination host h_d. When a condition involves a single host, we simply write (c,h). Here, conditions typically refer to the existence of vulnerability or the connectivity between two hosts (while there might be abundant security-related conditions in each host, we only include those that are either precondition or postcondition of at least one exploit in the attack graph). Two types of directed edges interconnect exploits and conditions, with no edge going directly between exploits or between conditions. First, an edge pointing from a condition to an exploit denotes the require relation, which means the exploit cannot be executed unless the condition is satisfied. Second, an edge pointing from an exploit to a condition denotes the imply relation, which means executing the exploit will satisfy the condition. For example, an exploit usually requires existence of the vulnerability on the destination host and connectivity between the two hosts. We call the composition of the require and imply relations the prepare-for relation, and denote it as an arrow. Later, when we map alerts to exploits, the prepare-for relation will be abused to relate the alerts, too.

Example 10.1

Figure 10.1 shows an attack graph where exploits are represented as triples (source host, target host, vulnerability) in ovals and security conditions as pairs (host, condition) in plaintext. The attack graph depicts a scenario where an attacker may exploit the sadmind buffer overflow vulnerability (Nessus ID 11841) on any of the two hosts h₁ and h₂ from his or her own machine h₃ since he or she already has the required user privilege on h₃. Once the attacker gains user privilege on h₁ or h₂, he or she can then use it as a stepping stone to further attack other hosts.

In interpreting an attack graph, an important aspect is that the require relation is always conjunctive, whereas the imply relation is always disjunctive. More specifically, an exploit cannot be realized until all of its required conditions have been satisfied, whereas a condition is satisfied if any of the realized exploits implies the condition. During further discussions, we assume attack graphs can be obtained with existing tools, such as the Topological Vulnerability Analysis (TVA) system [35]. We assume the attack graph is updated in a timely fashion upon changes in network topology and configurations. We assume the attack graph can be placed in memory for the given network. It is worth noting that this assumption depends on the size of a network and the complexity of its configurations and, therefore, may not always hold. We do not assume external host addresses to be trustful and hence use wildcards to match them. This may cause false correlations when multiple attackers concurrently launch similar attacks while they do not intend to cooperate with each other. The vulnerability-centric correlation approach needs to match alerts with exploits such that the alerts can be correlated using the knowledge encoded in an attack graph. To match alerts with exploits, the event-type attributes of alerts need to be mapped to the vulnerability attributes of exploits using domain knowledge, such as the correspondence between Snort identifiers and Nessus identifiers [36]. For simplicity, we denote the matching between alerts and exploits as a function Exp() from the set of alerts to the set of exploits. In some cases, an event type matches multiple vulnerabilities, which will be handled by creating a copy of alert for each matched exploit, indicating a simultaneous exploitation of multiple vulnerabilities.

Starting from the knowledge about one’s own network, the vulnerability-centric correlation approach can mitigate the negative impact of disruptive alerts. For example, if an attacker blindly launches some Windows-specific attacks on UNIX machines, then the reported alerts will be ignored by the approach. On the other hand, the limitation lies in that relevant alerts do not always match exploits. For example, an ICMP PING matches no vulnerability, but it may signal the probing preparation for the attacks that follow. Such relevant alerts can be identified based on attack graphs and the knowledge about alert types. The concept of exploits needs to be extended to include alert types in the place of vulnerability attributes. Such special exploits are added to attack graphs and the function Exp will be extended accordingly. Because the vulnerability-centric approach processes incoming alerts in exactly one pass, the correlation method critically depends on temporal characteristics of alerts, such as the order of arrivals and the timestamps. In practice, those characteristics will exhibit much more uncertainty due to various delays in hosts and networks, especially when alerts are collected from multiple sensors placed in different places in a network. We shall address such temporal impreciseness in more details in later sections. However, we assume the clocks of IDS sensors are loosely synchronized with the correlation engine. This can be achieved in many ways depending on specific IDS systems. For example, Snort has built-in support of automatic time synchronization through the network time protocol (NTP) [1].