CERIAS - Center for Education and Research in Information Assurance and Security

Skip Navigation
CERIAS Logo
Purdue University
Center for Education and Research in Information Assurance and Security

A Kolmogorov Complexity Approach for Measuring Attack Path Complexity

Research Areas: Network Security

Principal Investigator: Bharat Bhargava

The diculty 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 diculty 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 exibility 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 denes the security of a network in terms of the network assets attainable for attack eort exerted.

Personnel

Other PIs: Nwokedi Idika

Representative Publications

  • N. Idika, B. Bhargava. A
        Kolmogorov Complexity Approach for Measuring Attack Path Complexity, in
        Proceedings of IFIP International Information Security (SEC 2011)
        conference, June 2011, Lucerne, Switzerland

Keywords: metrics of security, science of security, software vulnerability