Abstract

Attack graph has emerged as a useful tool for defending against multi-step network attacks involving correlated vulnerabilities. However, most current representations of attack graphs are not scalable [35]. Even the attack graph of a reasonably large network is usually incomprehensible to the human eyes. For realistic networks with tens of thousands of hosts and hundreds of vulnerabilities, even computing the attack graph may become infeasible. On the other hand, an attack graph of a real-world network usually has much redundancy due to the presence of hosts with similar configurations, such as those in an office or computer lab. To out best knowledge, existing work can at best hide such scalability issues through visualization techniques but cannot remove the redundant information, which does not comprise real solutions. This thesis presents a scalable representation of attack graphs for removing such redundancy. The representation is based on a well known compression technique, namely, reference encoding. More precisely, we use one host as the reference to other hosts with similar vulnerabilities and connectivity; details of the latter can then be omitted in the resultant attack graph. We introduce our compression model step by step. We start with a simple case where hosts have identical connectivity and vulnerabilities. We show that a one-host model can be used in some cases but it has limitations in representing remote exploits across different machines. We then introduce a two-node model to address the limitation and show that the one-host model is actually a special case of the two-node model. Next, we study the more realistic case where hosts may have different connectivity and vulnerabilities. We show that in some cases small differences are better hidden in textual rules while in other cases the differences are better handled by leaving the involved hosts outside the compression model. To evaluate the proposed compression model, we will describe a case study on a small network. We will also show experimental results based on random network topologies generated by existing tools. Both results confirm that our model can significantly reduce the complexity of attack graphs.