中文摘要：

攻击图是一种基于模型的安全分析技术,将不同的原子攻击关联起来,用图的形式描述所有可能的攻击路径,在网络和系统的安全性分析中得到广泛的应用.研究了攻击图中的最优原子攻击修复集问题和最优初始条件修复集问题.针对这2个问题,定义了原子攻击拆分加权攻击图和初始条件拆分加权攻击图,将最优原子攻击修复集问题和最优初始条件修复集问题分别归结于原子攻击拆分加权攻击图中的最小S-T割集问题和初始条件拆分加权攻击图中的最小S-T割集问题,并证明其等价性.在此基础上提出了基于网络流的具有多项式复杂度的算法.模拟实验表明,与已有成果相比,该算法具有较高的实际运行效率和很好的可扩展性,能应用于大规模攻击图的分析中.

英文摘要：

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.