Abstract
Attack graphs represent known attack sequences that attackers can use to penetrate computer networks. Recently, many researchers have proposed techniques for automatically generating attack graphs for a given computer network. These techniques either use model checkers to generate attack graphs and suffer from scalability problems, or they are based on an assumption of monotonicity and are unable to represent real-world situations.
In this paper, we present a vulnerability analysis technique that is more scalable than model-checker-based solutions and more expressive than monotonicity-based solutions. We represent individual attacks as the transition rules of a rule-based system. We define noninterfering rulesets and present efficient, scalable algorithms for those sets. We then consider arbitrary nonmonotonic rulesets and present a series of optimizations which permit us to perform vulnerability assessment efficiently in most practical cases. We motivate the issues and illustrate our techniques using a substantial example.
The work of Pamula and Jajodia was partially supported by the National Science Foundation under grants IIS-0430402 and IIS-0242237, Air Force Research Laboratory, Rome under the grant F30602-00-2-0512, and the Army Research Office under the grant DAAD19-03-1-0257.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Ammann, P., Wijesekera, D., Kaushik, S.: Scalable, Graph-Based Network Vulnerability Analysis. In: Proceedings of the 9th ACM conference on Computer and Communications Security, pp. 217–224. ACM Press, New York (2002)
CERT: CERT Advisory CA-2003-07, Remote Buffer Overflow in Sendmail, http://www.cert.org/advisories/CA-2003-07.html
ADM Crew: BIND NXT Remote Root Exploit, http://adm.freelsd.net/ADM/exploits/t666.c
Dacier, M., Deswarte, Y.: Privilege Graph: An Extension to the Typed Access Matrix Model. In: Gollmann, D. (ed.) ESORICS 1994. LNCS, vol. 875, pp. 317–334. Springer, Heidelberg (1994)
Dacier, M., Deswarte, Y., Kaniche, M.: Models and tools for quantitative assessment of operational security. In: Proceedings IFIP SEC, pp. 177–186 (1996)
Jha, S., Sheyner, O., Wing, J.M.: Minimization and Reliability Analyses of Attack Graphs. Technical Report CMU-CS-02-109, School of Computer Science, Carnegie Mellon University (February 2002)
Jha, S., Sheyner, O., Wing, J.M.: Two Formal Analyses of Attack Graphs. In: Proceedings of the 2002 Computer Security Foundations Workshop, Nova Scotia, Canada, June 2002, pp. 45–59 (2002)
Ortalo, R., Deswarte, Y., Kaaniche, M.: Experimenting with Quantitative Evaluation Tools for Monitoring Operational Security. IEEE Transactions on Software Engineering 25(5), 633–650 (1999)
Phillips, C., Painton Swiler, L.: A Graph-Based System for Network-Vulnerability Analysis. In: Proceedings of the 1998 workshop on New Security Paradigms, pp. 71–79. ACM Press, Charlottesville (1998)
Ramakrishnan, C.R., Sekar, R.: Model-based Vulnerability Analysis of Computer Systems. In: Proceedings of the 2nd International Workshop on Verification, Model Checking and Abstract Interpretation (September 1998)
Ramakrishnan, C.R., Sekar, R.: Model-Based Analysis of Configuration Vulnerabilities. Journal of Computer Security 10(1-2), 189–209 (2002)
Ramsdell, J.: Penetration Analysis Application. The MITRE Corporation (April 2001)
Ritchey, R., O’Berry, B., Noel, S.: Representing TCP/IP Connectivity for Topological Analysis of Network Security. In: 18th Annual Computer Security Applications Conference (December 2002)
Ritchey, R.W., Ammann, P.: Using Model Checking to Analyze Network Vulnerabilities. In: Proceedings of the IEEE Symposium on Security and Privacy, pp. 156–165 (2000)
Sheyner, O., Haines, J., Jha, S., Lippmann, R., Wing, J.M.: Automated Generation and Analysis of Attack Graphs. In: Proceedings of the IEEE Symposium on Security and Privacy, pp. 254–265. IEEE Computer Society, Los Alamitos (2002)
Sheyner, O., Wing, J.: Tools for Generating and Analyzing Attack Graphs. In: de Boer, F.S., Bonsangue, M.M., Graf, S., de Roever, W.-P. (eds.) FMCO 2003. LNCS, vol. 3188, pp. 344–371. Springer, Heidelberg (2004)
Swiler, L.P., Phillips, C., Ellis, D., Chakerian, S.: Computer-Attack Graph Generation Tool. In: Proceedings DISCEX 2001: DARPA Information Survivability Conference and Exposition II, June 2001, pp. 307–321 (2001)
Templeton, S.J., Levitt, K.: A Requires/Provides Model for Computer Attacks. In: Proceedings of the New Security Paradigms Workshop, Ballycotton, County Cork, Ireland, pp. 31–38. ACM Press, New York (2000)
US-CERT: Vulnerability Note Number: 16532—BIND NXT record processing may cause buffer overflow, http://www.kb.cert.org/vuls/id/16532
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Swarup, V., Jajodia, S., Pamula, J. (2005). Rule-Based Topological Vulnerability Analysis. In: Gorodetsky, V., Kotenko, I., Skormin, V. (eds) Computer Network Security. MMM-ACNS 2005. Lecture Notes in Computer Science, vol 3685. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11560326_3
Download citation
DOI: https://doi.org/10.1007/11560326_3
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-29113-8
Online ISBN: 978-3-540-31998-6
eBook Packages: Computer ScienceComputer Science (R0)