Distilling critical attack graph surface iteratively through minimum-cost SAT solving
Distilling critical attack graph surface iteratively through minimum-cost SAT solving
复制标题
DOI：
10.1145/2076732.2076738
复制
发表时间：
2011-12
影响因子：
3.9
通讯作者：
Heqing Huang;Su Zhang;Xinming Ou;A. Prakash;K. Sakallah
中科院分区：
文献类型：
--
作者：
Heqing Huang;Su Zhang;Xinming Ou;A. Prakash;K. Sakallah
人们早就认识到，系统管理员找出存在于完整攻击图中的关键安全问题可能是乏味的，甚至是不可行的，即使对于小型企业网络也是如此。因此，需要在分析的准确性和效率之间进行权衡，以实现攻击图的完整性和有用性之间的合理平衡。在本文中，我们提供了一种攻击图提炼的方法，以便用户可以通过筛选出完整攻击图中最关键的部分来控制所呈现的信息量。用户可以根据指定的严重性度量选择仅查看k个最关键的攻击路径，例如攻击者在特定计算机上执行特定攻击的可能性和成功的机会。我们将依赖攻击图转换为布尔公式，并根据严重性度量为公式中的攻击变量分配代价度量。然后，我们应用最小成本SAT求解(MCSS)来寻找最关键的路径，就攻击者部署导致网络中某些关键资产的多步骤攻击所产生的最小成本而言。在反例指导的抽象和求精(CEGAR)的启发下，设计了一种迭代过程，以有效地指导MCSS呈现包含可控数量的真实攻击路径的解决方案，形成关键攻击图面。该方法可以在几分钟内从中型企业网络生成的全部攻击图中提取关键攻击图面。在不同规模的网络场景上的实验表明，即使对于小尺寸的关键攻击图面(大约是原始完整攻击图大小的15%)，计算的风险度量也很好地近似于使用完整攻击图计算的值，这意味着提取的关键攻击图面能够捕获企业网络中的关键安全问题，以便进一步深入分析。
It has long been recognized that it can be tedious and even infeasible for system administrators to figure out critical security problems residing in full attack graphs, even for small-sized enterprise networks. Therefore a trade-off between analysis accuracy and efficiency needs to be made to achieve a reasonable balance between completeness of the attack graph and its usefulness. In this paper, we provide an approach to attack graph distillation, so that the user can control the amount of information presented by sifting out the most critical portion of the full attack graph. The user can choose to see only the k most critical attack paths, based on specified severity metrics, e.g. the likelihood for an attacker to carry out certain exploit on certain machine and the chance of success. We transform an dependency attack graph into a Boolean formula and assign cost metrics to attack variables in the formula, based on the severity metrics. We then apply Minimum-Cost SAT Solving (MCSS) to find the most critical path in terms of the least cost incurred for the attacker to deploy multi-step attacks leading to certain crucial assets in the network. An iterative process inspired by Counter Example Guided Abstraction and Refinement (CEGAR) is designed to efficiently guide the MCSS to render solutions that contain a controlled number of realistic attack paths, forming a critical attack graph surface. Our method can distill critical attack graph surfaces from the full attack graphs generated for moderate-sized enterprise networks in only several minutes. Experiments on various sized network scenarios show that even for a small-sized critical attack graph surface (around 15% the size of the original full attack graph), the calculated risk metrics are good approximation of the values computed with the full attack graph, meaning the distilled critical attack graph surface is able to capture the crucial security problems in an enterprise network for further in-depth analysis.