Skip to Main content Skip to Navigation
Conference papers

A Kolmogorov Complexity Approach for Measuring Attack Path Complexity

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.
Document type :
Conference papers
Complete list of metadata

Cited literature [12 references]  Display  Hide  Download
Contributor : Hal Ifip Connect in order to contact the contributor
Submitted on : Monday, July 24, 2017 - 10:40:20 AM
Last modification on : Thursday, August 1, 2019 - 2:26:01 PM


Files produced by the author(s)


Distributed under a Creative Commons Attribution 4.0 International License



Nwokedi Idika, Bharat Bhargava. A Kolmogorov Complexity Approach for Measuring Attack Path Complexity. 26th International Information Security Conference (SEC), Jun 2011, Lucerne, Switzerland. pp.281-292, ⟨10.1007/978-3-642-21424-0_23⟩. ⟨hal-01567600⟩



Record views


Files downloads