Abstract
The difficulty associated with breaching an enterprise network is commensurate with the security of that network. A security breach, or a security policy violation, occurs as a result of an attacker successfully executing some attack path. The difficulty associated with this attack path, then, is critical to understanding how secure a given network is. Currently, however, there are no consistent methods for measuring attack path complexity that make the assumptions of a modeler explicit while providing flexibility in how the modeler models the attack path. To provide these desirable attributes, we propose a regular-expressions-inspired language whose rationale for attack path complexity measurement is based on Kolmogorov Complexity. After detailing our Kolmogorov Complexity-based method, we demonstrate how it can be applied to a novel security metric: the K-step Capability Accumulation metric–a metric that defines the security of a network in terms of the network assets attainable for attack effort exerted.
Chapter PDF
Similar content being viewed by others
References
Mell, P., Scarfone, K., Romanosky, S.: Common Vulnerability Scoring System. IEEE Security and Privacy 4, 85–89 (2006)
Computer Emergency Response Team (CERT), http://www.cert.org
Wang, L., Singhal, A., Jajodia, S.: Measuring Overall Security of Network Configurations Using Attack Graphs. In: Barker, S., Ahn, G.-J. (eds.) Data and Applications Security 2007. LNCS, vol. 4602, pp. 98–112. Springer, Heidelberg (2007)
Phillips, C.A., Swiler, L.P.: A Graph-based System for Network-vulnerability Analysis. In: Proceedings of the 1998 Workshop on New Security Paradigms, pp. 71–79. ACM, New York (1998)
Ming, L., Vitanyi, P.: An Introduction to Kolmogorov Complexity and Its Applications. Springer, Heidelberg (1997)
Evans, S., Bush, S., Hershy, J.: Information Assurance Through Kolmogorov Complexity. In: DARPA Information Survivability Conference and Exposition (2001)
Lippmann, R., Ingols, K., Scott, C., Piwowarski, K., Kratkiewicz, K., Artz, M., Cunningham, R.: Validating and Restoring Defense in Depth Using Attack Graphs. In: Military Communications Conference (2006)
Noel, S., Jajodia, S.: Managing Attack Graph Complexity Through Visual Hierarchical Aggregation. In: Proceedings of the 2004 ACM Workshop on Visualization and Data Mining for Computer Security, pp. 109–118. ACM, New York (2004)
Li, W., Vaughn, R.: Cluster Security Research Involving the Modeling of Network Exploitations Using Exploitation Graphs. In: Proceedings of the Sixth IEEE International Symposium on Cluster Computing and Grid Workshops (2006)
Dantu, R., Kolan, P.: Risk Management Using Behavior Based Bayesian Networks. In: Kantor, P., Muresan, G., Roberts, F., Zeng, D.D., Wang, F.-Y., Chen, H., Merkle, R.C. (eds.) ISI 2005. LNCS, vol. 3495, pp. 115–126. Springer, Heidelberg (2005)
Dacier, M., Deswarte, Y., Kaâniche, M.: Models and Toos for quantitative assessment of operational security. In: Proceedings of the 12th International Information Security Conference, pp.177–186 (1996)
Ortalo, R., Deswarte, M., Kaâniche, M.: Experimenting with Quantitative Evaluation Tools for Monitoring Operational Security. IEEE Transactions on Software Engieering 25, 633–650 (1999)
Spracklin, L.M., Saxton, L.V.: Filtering spam using kolmogorov complexity estimates. In: Advanced Information Networking and Applications Workshops, pp. 321–328 (2007)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 IFIP International Federation for Information Processing
About this paper
Cite this paper
Idika, N., Bhargava, B. (2011). A Kolmogorov Complexity Approach for Measuring Attack Path Complexity. In: Camenisch, J., Fischer-Hübner, S., Murayama, Y., Portmann, A., Rieder, C. (eds) Future Challenges in Security and Privacy for Academia and Industry. SEC 2011. IFIP Advances in Information and Communication Technology, vol 354. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-21424-0_23
Download citation
DOI: https://doi.org/10.1007/978-3-642-21424-0_23
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-21423-3
Online ISBN: 978-3-642-21424-0
eBook Packages: Computer ScienceComputer Science (R0)