攻击图的两种形式化分析  

Two Formal Analyses of Attack Graphs

作　　者：陈锋[1,2] 张怡[1] 苏金树[1] 韩文报[3] 

机构地区：[1]国防科学技术大学计算机学院,湖南长沙410073 [2]第二军医大学网络信息中心,上海200433 [3]解放军信息工程大学信息工程学院,河南郑州450002

出　　处：《软件学报》2010年第4期838-848,共11页Journal of Software

基　　金：国家自然科学基金No.90604006;国家高技术研究发展计划(863)No.2008AA01A325;国家重点基础研究发展计划(973)No.2009CB320503~~

摘　　要：攻击图是一种基于模型的网络脆弱性分析技术,可以自动分析目标网络内脆弱性之间的关系和由此产生的潜在威胁.攻击图主要有状态攻击图和属性攻击图两类.前者由于存在状态爆炸问题不适应于大规模网络,目前主要的研究大多是基于后者.基于属性攻击图研究了含圈攻击路径问题和最优弥补集问题.针对含圈攻击路径问题,定义了反映真实攻击想定的n-有效攻击路径,提出了一种计算关键属性集所有n-有效攻击路径的迭代算法;针对最优弥补集问题,在定义了所有的风险源为属性攻击图的初始属性的基础上,将该问题转化为带权重的集合覆盖问题,从而归结为NP完全性问题,提出了可应用于大规模攻击图的具有多项式时间复杂度的近似算法.An attack graph is a model-based vulnerability analysis technology, which can automatically analyze the interrelation among vulnerabitities in the network and the potential threats resulting from the vulnerabilities. Since the state-based attack graphs can not be applied to the real large networks for the combinatorial explosion in the number of attack paths, the study is now shifted to attribute-based. Based on attribute-based attack graphs, this paper discusses the loop attack paths and the optimization security measures. For the former, an iterative algorithm is presented to find all the non-loop attack paths to the key attributes with their depth less than the given number n. For the latter, it is proved to be an NP-complete problem, and the greedy algorithm is proposed to solve the problem with polynomial time complexity.

关 键 词：脆弱性 攻击图 有效攻击路径 最优弥补集 贪婪算法 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]