Analysis of Attack Graphs Based on Network Flow Method

An intruder often breaks into a network through a chain of exploits. Each exploit in the chain lays the groundwork for subsequent exploits. Such a chain is called attack path. Attack graph, one kind of succinct representation of attack paths, is an important tool for analyzing security vulnerabilities in networks. Security analysts use attack graphs for detection and defense. However, attack graphs do not directly provide a solution to protect key resources from invasion. And finding a solution by hand is error-prone and tedious. Existing automated methods for finding such solutions are less efficient and scale poorly. In this paper, we propose solutions based on network flow method to automate the task of hardening a network against multi-step intrusions. We discuss the optimization critical attack sets problem and the optimization critical initial condition sets problem. Then we define the atomic-attacks split weighted attack graph (ASWAG) and the initial-condition split weighted attack graph (ISWAG), and convert the former two problems into the minimum S-T cut problems in ASWAG and ISWAG. The conversions are proved to be equivalent. Two algorithms with polynomial time complexity are proposed. Simulation results show that the algorithms are more efficient and scale better than the existing methods. We can use them to analyze large-scale attack graphs.