Login | Register

Attack graph compression


Attack graph compression

Long, Tao (2009) Attack graph compression. Masters thesis, Concordia University.

[thumbnail of MR63328.pdf]
Text (application/pdf)
MR63328.pdf - Accepted Version


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.

Divisions:Concordia University > Gina Cody School of Engineering and Computer Science > Concordia Institute for Information Systems Engineering
Item Type:Thesis (Masters)
Authors:Long, Tao
Pagination:x, 72 leaves : ill. ; 29 cm.
Institution:Concordia University
Degree Name:M.A. Sc.
Program:Institute for Information Systems Engineering
Thesis Supervisor(s):Wang, L
Identification Number:LE 3 C66I54M 2009 L66
ID Code:976208
Deposited By: Concordia University Library
Deposited On:22 Jan 2013 16:21
Last Modified:13 Jul 2020 20:09
Related URLs:
All items in Spectrum are protected by copyright, with all rights reserved. The use of items is governed by Spectrum's terms of access.

Repository Staff Only: item control page

Downloads per month over past year

Research related to the current document (at the CORE website)
- Research related to the current document (at the CORE website)
Back to top Back to top