9.6. Attack Graph Analysis
Attack graphs serve as the basis of further analysis in several areas of network security, including intrusion detection, defense, and forensic analysis. System administrators use attack graphs for the following reasons:
To gather information: Attack graphs can answer questions like “What attacks is my system vulnerable to?” and “From an initial configuration, how many different ways can an intruder reach a final state to achieve his or her goal?”
To make decisions: Attack graphs can answer questions like “Which set of actions should I prevent to ensure the intruder cannot achieve his or her goal?” or “Which set of security measures should I deploy to ensure the intruder cannot achieve his or her goal?”
Since we can produce attack graphs automatically, we make it convenient for system administrators to do “What if?” analysis. Administrators can look at a graph we produce and determine what would happen if they were to change firewall rules, add an IDS, install a software patch, or remove a host from the network. Does making a change to the system make the graph smaller, and in what way?
In this section, we look at two kinds of analyses that we can perform on an attack graph: single action removal and critical action set minimization. The first lets administrators see the effect of removing a single action from the intruder’s arsenal. The second identifies a set of actions that if removed would then prevent an intruder from achieving his or her goal.
To demonstrate the analyses, we expand the example from Section 9.5.1 with an extra host User on the external network and several new actions. An authorized user W of the internal network owns the new host and uses it as a terminal to work remotely on the internal Windows host. The new actions permit an intruder to take over the host User, sniff user W’s log-in credentials, and log in to the internal Windows host using the stolen credentials. We omit the details of the new actions, as they are not essential to understanding the examples. Figure 9.7(a) shows the full graph for the modified example. The graph is significantly larger, reflecting the expanded number of choices available to the intruder.
Figure 9.7. Reducing action arsenal.
9.6.1. Single Action Removal
A simple kind of analysis determines the impact of removing one action from the intruder’s arsenal. Recall from Section 9.4 that each action is a triple <r,hs,ht>, where hs ϵ H is the host from which the attack is launched, ht ϵ H is the host targeted by the attack, and r is an action rule. The user specifies a set Arem of action triples to be removed from the attack graph. Our toolkit deletes the transitions corresponding to each triple in the set Arem from the graph and then removes the nodes that have become unreachable from the initial state.
As demonstrated in Figure 9.7, this procedure can be repeated several times, reducing the size of the attack graph at each step. The full graph in Figure 9.7(a) has 362 states. Removing one of two ways the intruder can sniff user W’s log-in credentials produces the graph in Figure 9.7(b), with 213 states. Removing one of the local buffer overflow actions produces the graph in Figure 9.7(c), with 66 states. At each step, the user is able to visually judge the impact of removing a single action from the intruder’s arsenal.
9.6.2. Critical Action Set Minimization
Let us turn to a more sophisticated analysis, which is a kind of minimization analysis [13]. Suppose the system administrator must decide among several different firewall configurations, several vulnerabilities to patch, or several IDSs to set up. Each choice prevents a different subset of actions. What should the system administrator do?
We cast this question in terms of the Minimum Critical Set of Actions (MCSA) problem: What are the minimum set of actions that must be prevented to guarantee the intruder cannot achieve his or her goal? The sketch of our solution is:
The first reduction can be briefly understood as follows. Each path in the graph is an attack. Label each edge in the path with the action that causes the state transition (note that an action might label more than one edge in the path). Thus, the path defines a set of actions used to “realize” an attack. Thus, an attack graph is a set, R, of “realizable” sets of actions. We need to hit each set in R. If we hit each set in R, then we cut the graph. If we cut the graph, then there is no path from the initial state to any final (success) state in the graph. Finding a minimum critical set of actions then reduces to finding a minimum hitting set for R. That is, a minimum hitting set for R will identify a set of actions that the intruder must have in his or her arsenal in order for him or her to succeed (achieve his or her goal). This set is a critical set of actions.
In short, once an attack graph is generated, we can use an approximation algorithm to find an approximately optimal critical set of actions that will completely disconnect the initial state from states where the intruder has achieved his or her goals [3]. A related algorithm can find an approximately optimal set of security measures that accomplish the same goal. With a single click using our graphical user-interface tool, the user can invoke both of these exposure minimization algorithms.
The effect of the critical action set algorithm on the modified example attack graph is shown in Figure 9.8(a). The algorithm finds a critical action set of size 1, containing the port scan action exploiting the Squid web proxy. The graph nodes and edges corresponding to actions in the critical set computed by the algorithm are highlighted in the toolkit by shading the relevant nodes. The shaded nodes are seen clearly when we zoom in to inspect a part of the graph on a larger scale (Figure 9.8b).
Figure 9.8. Finding critical action sets.
Since the computed action set is always critical, removing every action triple in the set from the intruder’s arsenal is guaranteed to result in an empty attack graph. In the example, we might patch the Linux machine with a new version of the Squid proxy, thereby removing every action triple that uses the Squid port scan rule on the Linux machine from the intruder’s arsenal.