Analytical framework for measuring network security using exploit dependency graph

Attack graph is a popular tool for modelling multi-staged, correlated attacks on computer networks. Attack graphs have been widely used for measuring network security risks. Majority of the works on attack graph use host-based or state-based approaches. These attack graph models are either too restrictive or too resource consuming. Also, a significant portion of these works have used `probability of successfully exploiting a network` as the metric. This approach requires that the `probability of successfully exploiting individual vulnerabilities` be known a priori. Finding such probabilities is inherently difficult. This present study uses exploit dependency graph, which is a space efficient and expressive attack graph model. It also associates an additive cost with executing individual exploits, and defines a security metric in terms of the `minimum cost required to successfully exploit the network`. The problem of calculating the said metric is proved to be NP-complete. A modified depth first branch and bound algorithm has been described for calculating it. This study also formulates, a linear-time computable, security metric in terms of the `expected cost required to successfully exploit the network` assuming a random attacker model and an uncorrelated attack graph.