Steven Noel
George Mason University
USA

Sushil Jajodia
George Mason University
USA

Significant progress has been made in the efficient generation of network attack graphs. But previous approaches have relied on graph drawing algorithms for displaying the often large and complex graphs that are generated, making it difficult to understand patterns of attack. In this paper, we show how an adjacency matrix representation for attack graphs, combined with information-theoretic clustering, makes attack patterns clear and provides a framework for attack correlation, prediction, and hypothesizing. Our approach applies to general attack graphs, including those based on network vulnerabilities, detected intrusions, or combinations thereof. It also can be applied to attack graphs with aggregated vertices, e.g., aggregated by machine, as well as non-aggregated graphs. We raise the attack graph adjacency matrix to higher powers to show attacker reachability across the network for a given number of attack steps, with the union of per-step reachability providing attack prediction over all possible number of steps (transitive closure). We show how this reachability analysis provides a concise summary of attack graph changes resulting from (actual or hypothetical) network configuration changes. Using clustered attack graph adjacency matrices, we place intrusion alarms in the context of vulnerability-based attack graphs. In this way, false alarms become apparent within regions of non-reachability based on the network configuration. Also, missed detections are inferred from alarms occurring between machines that are only reachable via multiple attack steps. We introduce a graphical technique that shows multiple-step attacks by matching rows and columns of the attack graph adjacency matrix. This also allows attack responses to be identified and prioritized according to the number of steps required to reach victim machines. The techniques we describe all have low-order polynomial complexity for scalability to larger networks.

Keywords: Network attack modeling, attack graphs, attack prediction, attack response

Read Paper (in PDF)