Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

We describe a framework for managing network attack graph complexity through interactive visualization, which includes hierarchical aggregation of graph elements. Aggregation collapses non-overlapping subgraphs of the attack graph to single graph vertices, providing compression of attack graph complexity. Our aggregation is recursive (nested), according to a predefined aggregation hierarchy. This hierarchy establishes rules at each level of aggregation, with the rules being based on either common attribute values of attack graph elements or attack graph connectedness. The higher levels of the aggregation hierarchy correspond to higher levels of abstraction, providing progressively summarized visual overviews of the attack graph. We describe rich visual representations that capture relationships among our semantically-relevant attack graph abstractions, and our views support mixtures of elements at all levels of the aggregation hierarchy. While it would be possible to allow arbitrary nested aggregation of graph elements, it is better to constrain aggregation according to the semantics of the network attack problem, i.e., according to our aggregation hierarchy. The aggregation hierarchy also makes efficient automatic aggregation possible. We introduce the novel abstraction of protection domain as a level of the aggregation hierarchy, which corresponds to a fully-connected subgraph (clique) of the attack graph. We avoid expensive detection of attack graph cliques through knowledge of the network configuration, i.e. protection domains are predefined. While significant work has been done in automatically generating attack graphs, this is the first treatment of the management of attack graph complexity for interactive visualization. Overall, computation in our framework has worst-case quadratic complexity, but in practice complexity is greatly reduced because users generally interact with (often negligible) subsets of the attack graph. We apply our framework to a real network, using a software system we have developed for generating and visualizing network attack graphs.

REFERENCES

• 1: C. Ramakrishnan, R. Sekar, "Model-Based Analysis of Configuration Vulnerabilities," in Proceedings of the 7th ACM Conference on Computer and Communication Security, November 2000.
• 2: Ronald W. Ritchey , Paul Ammann, Using Model Checking to Analyze Network Vulnerabilities, Proceedings of the 2000 IEEE Symposium on Security and Privacy, p.156, May 14-17, 2000
• 3: Oleg Sheyner , Joshua Haines , Somesh Jha , Richard Lippmann , Jeannette M. Wing, Automated Generation and Analysis of Attack Graphs, Proceedings of the 2002 IEEE Symposium on Security and Privacy, p.273, May 12-15, 2002
• 4: S. Jha , O. Sheyner , J. Wing, Two Formal Analys s of Attack Graphs, Proceedings of the 15th IEEE Computer Security Foundations Workshop (CSFW'02), p.49, June 24-26, 2002
• 5: R. Baldwin, Kuang: Rule Based Security Checking, Technical Report, MIT Lab for Computer Science, May 1994.
• 6: D. Zerkle, K. Levitt, "Netkuang - A Multi-Host Configuration Vulnerability Checker," in Proceedings of the 6th USENIX Unix Security Symposium, San Jose, CA, 1996.
• 7: Cynthia Phillips , Laura Painton Swiler, A graph-based system for network-vulnerability analysis, Proceedings of the 1998 workshop on New security paradigms, p.71-79, September 22-26, 1998, Charlottesville, Virginia, United States [doi>10.1145/310889.310919]
• 8: L. Swiler, C. Phillips, D. Ellis, S. Chakerian, "Computer-Attack Graph Generation Tool," in Proceedings of the DARPA Information Survivability Conference & Exposition II, June 2001.
• 9: J. Dawkins, C. Campbell, J. Hale, "Modeling Network Attacks: Extending the Attack Tree Paradigm," in Proceedings of the Workshop on Statistical and Machine Learning Techniques in Computer Intrusion Detection, Johns Hopkins University, June 2002.
• 10: Paul Ammann , Duminda Wijesekera , Saket Kaushik, Scalable, graph-based network vulnerability analysis, Proceedings of the 9th ACM conference on Computer and communications security, November 18-22, 2002, Washington, DC, USA [doi>10.1145/586110.586140]
• 11: S. Jajodia, S. Noel, B. O'Berry, "Topological Analysis of Network Attack Vulnerability," in Managing Cyber Threats: Issues, Approaches and Challenges, V. Kumar, J. Srivastava, A. Lazarevic (eds.), Kluwer Academic Publisher, 2003.
• 12: Frédéric Cuppens , Rodolphe Ortalo, LAMBDA: A Language to Model a Database for Detection of Attacks, Proceedings of the Third International Workshop on Recent Advances in Intrusion Detection, p.197-216, October 02-04, 2000
• 13: Steven J. Templeton , Karl Levitt, A requires/provides model for computer attacks, Proceedings of the 2000 workshop on New security paradigms, p.31-38, September 18-21, 2000, Ballycotton, County Cork, Ireland [doi>10.1145/366173.366187]
• 14: Ronald Ritchey , Brian O'Berry , Steven Noel, Representing TCP/IP Connectivity For Topological Analysis of Network Security, Proceedings of the 18th Annual Computer Security Applications Conference, p.25, December 09-13, 2002
• 15: Frédéric Cuppens , Alexandre Miège, Alert Correlation in a Cooperative Intrusion Detection Framework, Proceedings of the 2002 IEEE Symposium on Security and Privacy, p.202, May 12-15, 2002
• 16: Peng Ning , Yun Cui , Douglas S. Reeves, Constructing attack scenarios through correlation of intrusion alerts, Proceedings of the 9th ACM conference on Computer and communications security, November 18-22, 2002, Washington, DC, USA [doi>10.1145/586110.586144]
• 17: P. Ning, D. Xu, C. Healey, R. St. Amant, "Building Attack Scenarios through Integration of Complementary Alert Correlation Methods," in Proceedings of the 11th Annual Network and Distributed System Security Symposium, February, 2004.
• 18: S. Noel, S. Jajodia, "Correlating Intrusion Events and Building Attack Scenarios through Attack Graph Distances," submitted.
• 19: Peter Eades , Qing-Wen Feng, Multilevel Visualization of Clustered Graphs, Proceedings of the Symposium on Graph Drawing, p.101-112, September 18-20, 1996
• 20: Adam L. Buchsbaum , Jefferey R. Westbrook, Maintaining hierarchical graph views, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.566-575, January 09-11, 2000, San Francisco, California, United States
• 21: Marcus Raitner, HGV: A Library for Hierarchies, Graphs, and Views, Revised Papers from the 10th International Symposium on Graph Drawing, p.236-243, August 26-28, 2002
• 22: M. Raitner, Maintaining Hierarchical Graph Views for Dynamic Graphs, Technical Report, MIP-0403, University of Passau, January, 2004.
• 23: Steven Noel , Sushil Jajodia , Brian O'Berry , Michael Jacobs, Efficient Minimum-Cost Network Hardening Via Exploit Dependency Graphs, Proceedings of the 19th Annual Computer Security Applications Conference, p.86, December 08-12, 2003
• 24: Nessus vulnerability scanner, <http://www.nessus.org/>.

INDEX TERMS

Primary Classification:
  K. Computing Milieux
  K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS
      K.6.5 Security and Protection (D.4.6, K.4.2)
          Subjects: Unauthorized access (e.g., hacking, phreaking)

General Terms:
Human Factors, Management, Security

Keywords:
clustered graphs, network attack graphs, network attack modeling, vulnerability analysis