Cost-aware network hardening using compact attack graphs

Attack graphs provide analytical support to prevent multistep network attacks by showing all possible sequences of vulnerabilities and their interactions. Since attack graphs generally consist of a very large number of nodes, it is computationally challenging to analyze them for hardening a network against attacks. In this thesis, we propose a greedy heuristic method to find a cost-effective solution to protect a network using compact attack graphs. First, we extract all possible attack paths which reach predetermined critical resources embedded in the network. The exploit or initial condition which contributes the most to attack paths with least cost is selected to be removed. This process continues iteratively and a security analyst can stop it when the total cost exceeds the allocated budget. The experimental results show that our algorithm scales almost linearly with the size of the networks and it can be applied to large-scale graphs with a very large number of nodes. They also show that the algorithm finds nearly minimum cost solution compared to optimal solution. In addition to providing a network-hardening solution, our proposal measures the security level of the network in every step to demonstrate how vulnerable the network is against threats. This accompanying feature is beneficial for network security assessment and situation awareness.