Extending logical attack graphs for efficient vulnerability analysis

ABSTRACT

Attack graph illustrates all possible multi-stage, multi-host attacks in an enterprise network and is essential for vulnerability analysis tools. Recently, researchers have addressed the problem of scalable generation of attack graph by logical formulation of vulnerability analysis in an existing framework called MulVAL. In this paper, we take a step further to make attack graph-based vulnerability analysis useful and practical for real networks. Firstly, we extend the MulVAL framework to include more complex security policies existing in advanced operating systems. Secondly, we present an expressive view of the attack graph by including negation in the logical characterization, and we present an algorithm to generate it. Finally, we present an incremental algorithm which efficiently recomputes the attack graph in response to the changes in the inputs of the vulnerability analysis framework. This is particularly useful for mutation or "what-if" analysis, where network administrators want to view the effect of network or host parameter changes to the attack graph before pushing the changes on the network. Preliminary experiments demonstrate the effectiveness of our algorithms.

REFERENCES

• 1: www.physorg.com/news124982803.html.
• 2: www.skyboxsecurity.com.
• 3: Umut A. Acar , Guy E. Blelloch , Robert Harper, Adaptive functional programming, Proceedings of the 29th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.247-259, January 16-18, 2002, Portland, Oregon
• 4: The National Security Agency. Security Enhanced Linux™.
• 5: 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]
• 6: G. Cohen et. al. System and method for risk detection and analysis in a computer network united states patent 6,952,779, october 2005.
• 7: Sudhakar Govindavajhala and Andrew Appel. A Windows access control demystified. Tech. rep., Princeton University, 2006.
• 8: Ashish Gupta , Inderpal Singh Mumick , V. S. Subrahmanian, Maintaining views incrementally, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.157-166, May 25-28, 1993, Washington, D.C., United States
• 9: Kyle Ingols , Richard Lippmann , Keith Piwowarski, Practical Attack Graph Generation for Network Defense, Proceedings of the 22nd Annual Computer Security Applications Conference on Annual Computer Security Applications Conference, p.121-130, December 11-15, 2006 [doi>10.1109/ACSAC.2006.39]
• 10: R. Lippmann and K. Ingols. An annotated review of past papers on attack graphs. Technical report, MIT Lincoln Laboratory, USA, March 2005.
• 11: J. W. Lloyd, Foundations of logic programming, Springer-Verlag New York, Inc., New York, NY, 1984
• 12: Prasad Naldurg , Stefan Schwoon , Sriram Rajamani , John Lambert, NETRA:: seeing through access control, Proceedings of the fourth ACM workshop on Formal methods in security, p.55-66, November 03-03, 2006, Alexandria, Virginia, USA [doi>10.1145/1180337.1180343]
• 13: Steven Noel , Michael Jacobs , Pramod Kalapa , Sushil Jajodia, Multiple Coordinated Views for Network Attack Graphs, Proceedings of the IEEE Workshops on Visualization for Computer Security, p.12, October 26-26, 2005 [doi>10.1109/VIZSEC.2005.14]
• 14: Steven Noel , Sushil Jajodia, Managing attack graph complexity through visual hierarchical aggregation, Proceedings of the 2004 ACM workshop on Visualization and data mining for computer security, October 29-29, 2004, Washington DC, USA [doi>10.1145/1029208.1029225]
• 15: Steven Noel , Sushil Jajodia, Understanding Complex Network Attack Graphs through Clustered Adjacency Matrices, Proceedings of the 21st Annual Computer Security Applications Conference, p.160-169, December 05-09, 2005 [doi>10.1109/CSAC.2005.58]
• 16: Xinming Ou , Sudhakar Govindavajhala , Andrew W. Appel, MulVAL: a logic-based network security analyzer, Proceedings of the 14th conference on USENIX Security Symposium, p.8-8, July 31-August 05, 2005, Baltimore, MD
• 17: Xinming Ou , Andrew W. Appel, A logic-programming approach to network security analysis, Princeton University, Princeton, NJ, 2005
• 18: Xinming Ou , Wayne F. Boyer , Miles A. McQueen, A scalable approach to attack graph generation, Proceedings of the 13th ACM conference on Computer and communications security, October 30-November 03, 2006, Alexandria, Virginia, USA [doi>10.1145/1180405.1180446]
• 19: Xinming Ou , Sudhakar Govindavajhala , Andrew W. Appel, MulVAL: a logic-based network security analyzer, Proceedings of the 14th conference on USENIX Security Symposium, p.8-8, July 31-August 05, 2005, Baltimore, MD
• 20: Robert Paige , Shaye Koenig, Finite Differencing of Computable Expressions, ACM Transactions on Programming Languages and Systems (TOPLAS), v.4 n.3, p.402-454, July 1982 [doi>10.1145/357172.357177]
• 21: Lippmann R., Ingols K., Scott C., Piwowarski K., Kratkiewicz K., and Cunningham R. Validating and restoring defense in depth using attack graphs. In MILCOM, 2006.
• 22: C. R. Ramakrishnan , R. Sekar, Model-based analysis of configuration vulnerabilities, Journal of Computer Security, v.10 n.1-2, p.189-209, 2002
• 23: Thomas Reps , Tim Teitelbaum , Alan Demers, Incremental Context-Dependent Analysis for Language-Based Editors, ACM Transactions on Programming Languages and Systems (TOPLAS), v.5 n.3, p.449-477, July 1983 [doi>10.1145/2166.357218]
• 24: Konstantinos Sagonas , Terrance Swift , David S. Warren, XSB as an efficient deductive database engine, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.442-453, May 24-27, 1994, Minneapolis, Minnesota, United States
• 25: D. Saha and C.R. Ramakrishnan. Incremental evaluation of tabled logic programs. In International Conference on Logic Programming, volume 2916 of LNCS, pages 389--406, 2003.
• 26: Diptikalyan Saha , C. R. Ramakrishnan, Incremental and demand-driven points-to analysis using logic programming, Proceedings of the 7th ACM SIGPLAN international conference on Principles and practice of declarative programming, p.117-128, July 11-13, 2005, Lisbon, Portugal [doi>10.1145/1069774.1069785]
• 27: D. Saha and C.R. Ramakrishnan. Incremental evaluation of tabled prolog: Beyond pure logic programs. In Practical Aspects of Declarative Languages, volume 3819 of LNCS, pages 215--229, Charleston, South Carolina, Jan 2006.
• 28: Beata Sarna-Starosta and Scott D. Stoller. Policy analysis for security-enhanced linux. In Proceedings of the 2004 Workshop on Issues in the Theory of Security (WITS), pages 1--12, April 2004. Available at http://www.cs.sunysb.edu/~stoller/WITS2004.html.
• 29: 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
• 30: Anu Singh , C. R. Ramakrishnan , I. V. Ramakrishnan , Scott D. Stoller , David S. Warren, Security policy analysis using deductive spreadsheets, Proceedings of the 2007 ACM workshop on Formal methods in security engineering, p.42-50, November 02-02, 2007, Fairfax, Virginia, USA [doi>10.1145/1314436.1314443]
• 31: Oleg Sokolsky , Scott A. Smolka, Incremental Model Checking in the Modal Mu-Calculus, Proceedings of the 6th International Conference on Computer Aided Verification, p.351-363, June 21-23, 1994
• 32: Vipin Swarup, Sushil Jajodia, and Joseph Pamula. Rule-based topological vulnerability analysis. In MMM-ACNS, pages 23--37, 2005.
• 33: Hisao Tamaki , Taisuke Sato, OLD Resolution with Tabulation, Proceedings of the Third International Conference on Logic Programming, p.84-98, July 14-18, 1986
• 34: uDraw(Graph). Available at http://www.informatik.uni-bremen.de/uDrawGraph/en/uDrawGraph/uDrawGraph%.html.
• 35: Jeffrey D. Ullman, Principles of Database and Knowledge-Base Systems: Volume II: The New Technologies, W. H. Freeman & Co., New York, NY, 1990
• 36: Lingyu Wang, Anyi Liu, and Sushil Jajodia. Using attack graphs for correlating, hypothesizing, and predicting intrusion alerts. Computer Communications, 29(15):2917--2933, 2006.
• 37: Lingyu Wang , Steven Noel , Sushil Jajodia, Minimum-cost network hardening using attack graphs, Computer Communications, v.29 n.18, p.3812-3824, November, 2006 [doi>10.1016/j.comcom.2006.06.018]
• 38: Lingyu Wang, Chao Yao, Anoop Singhal, and Sushil Jajodia. Interactive analysis of attack graphs using relational queries. In DBSec, pages 119--132, 2006.
• 39: XSB. The XSB logic programming system. Available at http://xsb.sourceforge.net.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.0 General
          Subjects: Security and protection (e.g., firewalls)

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.6 Logic Programming

General Terms:
Management, Security

Keywords:
attack graphs, incremental analysis, logic programming