赵 超，王慧强+，林俊宇，吕宏武，韩冀中

1.哈尔滨工程大学 计算机科学与技术学院，哈尔滨 150001

2.中国科学院 信息工程研究所，北京 100000

1 引言

计算机网络已成为当今社会不可或缺的组成部分，然而随着网络技术快速发展，大量的安全漏洞暴露出来。安全漏洞是各类网络安全事件层出不穷的主要原因[1]。理论上，为确保网络安全，应该扫描并修复网络中的全部漏洞，但由于网络的实际情况、安全与业务架构之间的矛盾、加固代价、漏洞修复的滞后性等问题，修复全部漏洞实际上通常无法做到。因此，如何针对网络的整体安全状况，选择合适的安全加固措施，既保障网络的安全，同时尽可能减小对业务的影响，降低所选加固措施的总代价，成为网络安全管理员面临的一大难题。

针对这一问题，研究人员提出了一系列网络安全分析模型，如故障树（fault tree）、攻击树（attack tree）、攻击图（attack graph）等。故障树最早用于装备工程领域，用来分析设备故障原因，提高维修效率，后由Helmer等人[2]引入网络安全领域，但故障树的规模会随逻辑门和基本事件数目的增加呈指数级增长，因此不适合大规模网络的攻击建模。攻击树模型由Schneier[3]提出，以叶子节点表示攻击方法，根节点表示最终目标，能够清晰地表示可能的攻击方式，但随着问题规模的扩大，树形结构的建模会导致模型中存在大量冗余，使得模型结构非常庞大。在此基础上，Phillips和Swiler[4]提出攻击图模型。随着学者对攻击图模型的不断研究，提出了属性攻击图，较好地解决了状态攻击图存在的空间爆炸问题。文献[5]首次提出了攻击者能力的“单调性假设”，将攻击图生成算法的复杂度由指数级降为多项式级，随后又提出了很多方法用以生成攻击图[6-8]，开发了一系列的攻击图自动生成软件[9-10]，进一步降低攻击图生成的时间复杂度。

要利用攻击图获得网络安全加固策略，需要对其做进一步的分析，相比于攻击图的生成，对攻击图分析方法的研究还存在很多问题。文献[11]首先提出最小原子攻击修复集问题，认为可以通过修复原子攻击阻断攻击路径，并用贪婪算法求解，但该方法没有考虑修复代价。文献[12-13]研究了最优初始条件修复集问题，通过修复某些初始属性以阻断攻击路径，同时以最少的修复措施保障关键节点的安全，但精确的攻击路径搜索算法具有指数级时间复杂度，无法应用于大规模网络中。文献[14]提出了n-有效攻击路径生成算法，通过限制迭代次数降低算法时间复杂度，但仅以路径长度作为攻击风险的评判标准，没有考虑不同漏洞在攻击难度和造成后果等方面的差异，并且算法同样没有解决局部最优问题。文献[15]提出用基于网络流的攻击图分析方法，解决最优原子攻击修复集和最优初始属性修复集问题，算法效率较高，但是忽略了属性攻击图节点间的逻辑关系，因此生成的修复策略修复代价过高。文献[16]基于依赖攻击图，同时考虑攻击威胁和修复成本，直接计算关键状态，但在实际应用中，修复成本对于攻击者的攻击行为并无影响，不宜作为风险评估的依据。

针对目前研究的不足，基于属性攻击图，以现有的攻击图构建方法为研究基础，对攻击图的分析方法展开研究，提出了一种适用于大规模网络安全加固的攻击图分析方法。首先，提出攻击路径的风险评估方法，并采用启发式算法搜索攻击图中风险系数最高的攻击路径；然后，以此为度量基础，根据网络的实际情况，设置危险阈值，搜索出全部危险系数大于阈值的潜在攻击；最后，选择能够阻断这些高危险潜在攻击的属性，生成低代价的网络安全加固策略。

2 攻击路径危险系数度量方法

网络中普遍存在着安全漏洞，并且每天都有大量的新漏洞被发现，但对全部漏洞进行修复往往是不切实际的。攻击图能够很好地展现漏洞之间的关联，通过对攻击图的分析，选择危险性较高、修复难度较低的漏洞进行修复，尽可能地使网络具有相对较高的安全程度是一个更加实际的办法。要判断不同攻击方式的威胁程度，需要有具体的评判方法，在阐述具体方法之前，首先给出一些基本定义。

2.1 基本定义

属性攻击图能够展示出攻击者利用网络中的各种安全漏洞进行攻击的所有可能方式，它的形式化定义如下。

定义1（属性攻击图）属性攻击图AG定义为一个三元组D=＜V,A,E＞。其中，V表示属性节点集合，V0表示初始属性节点集合，Vd表示非初始属性节点集合，则V0与Vd共同构成属性节点集合V，即V=V0⋃Vd；A表示原子攻击集合；E表示有向边集合，是有序积集((V0⋃Vd)×A)⋃(A×Vd)的一个子集。

同时，属性攻击图需满足以下规则：

（1）当原子攻击a的所有前提属性均得到满足的情况下，原子攻击a才能被执行。

（2）属性v的任意一个前提原子攻击被执行，都可以使攻击者获得属性v。

在属性攻击图中，通常用文字表示属性节点，用圆或椭圆表示原子攻击节点，用箭头表示有向边，如图1所示。

Fig.1 An example of attack graph图1 攻击图实例

定义2（可达）在一个攻击图中，对于属性集Va∈V，若攻击者从Va出发，经过一系列攻击行为，可以获得属性v，则称Va可达v，记作Va⇒v；反之，若攻击者从Va出发，不足以获得属性v，则称Va不可达v，记作Vav。

定义3（初始可达集）若Va⇒v，且Va⊆V0，则称Va是v的初始可达集。

定义4（最小初始可达集）若Va是v的初始可达集，且对 ∀v′∈Va，Va-v′v，则称Va是v的最小可达初始属性集，简称最小初始集。

也就是说，对于攻击者的一次攻击行为，若要获得关键属性，对应的最小初始集中的所有属性都是必要的。

定义5（攻击路径）攻击者利用一个最小初始集，经过一步或多步攻击，最后获得目标属性的过程，称为一次攻击过程，将这个过程中发生的所有原子攻击按先后顺序构成一个序列，称为一个攻击路径，表示形式为ai→aj→…→ak。

对于一个关键属性v，可能存在多个最小初始集，并且不同的最小初始集中可能存在相同的初始属性。例如，在图1所示的攻击图中，攻击者可以通过初始属性v0、v3，经由攻击路径a1→a3获得属性v5；也可以通过属性v1、v2、v3，经由攻击路径a2→a3获得属性v5。因此，属性v5存在两个最小初始集，分别为{v0,v3}和{v1,v2,v3}。

2.2 攻击路径危险系数

为了得到网络安全加固策略，首先需要知道攻击者有哪些可能的攻击路径。在攻击图中，搜索全部攻击路径的算法具有无法避免的指数级时间复杂度，无法适用于大规模网络。一个更具实际意义的方法是：通过评估攻击路径的风险，搜索被攻击可能性较高的攻击路径，并提前阻断，保障网络的相对安全。

为了度量不同攻击路径被攻击者利用可能性的高低，需要对攻击路径上全部漏洞的严重程度进行评估。给出一种基于CVSS（common vulnerability scoring system）的攻击路径危险系数的计算方法。CVSS是NVD（national vulnerability database）提出的一套公开标准，被用于评价安全漏洞的严重程度。对于每一个已知漏洞，CVSS会给出一个基础分数（base score），该分数通过AccessVecto（r接入方式）、Access-Complexity（攻击复杂度）、Authentication（身份验证）、ConfImpact（机密性影响）、IntegImpac（t完整性影响）、AvailImpac（t有效性影响）等指标计算得出，漏洞的危险程度越高，分数就越高，取值范围是[0,10]。可以看出，作为一种通用的漏洞评分标准，CVSS基础分数综合考虑了攻击难度和造成后果的严重程度，能较好地反映出攻击者对于不同漏洞实施攻击的意愿的高低。因此，本文采用CVSS基础评分作为参考，并以此说明攻击路径危险系数的计算方法。

攻击者对网络进行多步攻击的过程中，每一步攻击对应着一个安全漏洞，对于任意的原子攻击a，令r(a)为原子攻击a的危险系数，则：

对于任意攻击路径l，r(l)为攻击路径l的危险系数，定义为l上全部利用的漏洞危险系数的乘积，则：

攻击路径的危险系数反映了路径被攻击者选择的意愿大小的相对程度，为攻击路径的威胁程度评判提供了依据。

3 最小初始集生成方法

上文提到，搜索全部攻击路径的算法具有无法避免的指数级时间复杂度，无法适用于大规模网络。在实际应用中，由于网络性质的不同，不同的组织、机构对于自身网络安全程度的要求并不相同。例如，大型商业公司和一些政府部门对网络安全性的要求通常较高，在网络安全方面的投入也较大；而对于一般的办公网络，只要保证网络的正常使用即可，安全要求相对较低，通常也无法承受过高的安全加固代价。针对这种情况，设计方法采用以下步骤：（1）搜索网络中危险系数最高的攻击路径，作为初步判断网络安全状况的基础；（2）根据步骤（1）的结果，结合网络的安全需求情况和专业人员的经验，设定一个危险阈值；（3）搜索出全部危险系数大于阈值（潜在风险较高）的攻击路径对应的最小初始集，所得的最小初始集将作为本文第4部分的输入，为最终生成网络安全加固策略提供基础。

3.1 最大危险系数计算

最大危险系数攻击路径的精确搜索算法同样具有指数级的时间复杂度，因此可采用启发式算法求解攻击图中的最大危险系数。在一个攻击图中，对攻击路径的搜索通常采用自底向上的方式，由关键属性出发，逆向构造攻击路径，这个过程与蚂蚁选路的过程非常相似，因此选用蚁群算法求解攻击图中最大危险系数问题。对蚁群优化算法中的ASrank模型进行适当的修改，提出攻击图最大危险系数计算方法。

定义6（攻击路径运算符“+”）设l1、l2为两个攻击路径，将l2连接在l1后面，构成一个新的攻击路径，称为l1、l2的“+”运算，记作l1+l2。

给定攻击图AG和目标属性vk，所有蚂蚁从vk出发，采用深度优先的迭代搜索方式构建危险系数最高的路径lmax。由于属性攻击图中节点间存在逻辑关系，针对属性攻击图中的两种节点，算法遵循以下规则：

（1）当蚂蚁位于属性节点v∈Vd时，蚂蚁在v的前提原子攻击节点中选择一个加入lmax中并移动到该节点上。

（2）当蚂蚁位于原子攻击节点a∈A时，依次对a的每一个前提属性节点构建攻击路径，将结果与该蚂蚁已生成的路径进行“+”运算。

规则（1）中，蚂蚁选择原子攻击节点并不是盲目的，而是倾向于选择信息素浓度和收益更高的节点，这里的收益更高指的是原子攻击节点的危险系数r(a)更大。因此，蚂蚁位于属性节点v时，选择原子攻击节点i的概率可以表示为：

其中，参数α，β＞0；τi是节点i的信息素浓度；ηi是节点i的启发式信息，ηi=r(i)。

构造的路径危险系数r(l)初始值设为1，当K只蚂蚁完成构建后，按照构建的解路径危险系数的大小排序，只有排列在最前的ω-1只蚂蚁和生成了至今最优解的蚂蚁才允许释放信息素。构建的解路径危险系数r(l)越大的蚂蚁，留下的信息素就越多。信息素更新准则为：蚂蚁在它选择的原子攻击节点上留下的信息素量为Q×Rk，这里Q是一个常数，Rk是蚂蚁k构造解路径的危险系数。同时，信息素会随着时间的流逝而挥发，信息素更新公式如下：

其中，t是迭代次数；ρ∈[0,1]是控制信息素τi挥发的参数；Δτi是节点i上信息素的总增量；是蚂蚁k在节点i上留下的信息素量。在信息素更新之后，进行第t+1次迭代。算法经过T次迭代后，得到最终结果。

为避免蚂蚁生成无效的含圈攻击路径或重复计入属性节点导致的危险系数计算错误，引入了两个属性节点集Vselected和Vvisited，分别存放当前节点的祖先节点和兄弟节点。在深度优先迭代之前，若节点已在Vselected中，说明产生无效的含圈攻击路径，若节点已在Vvisited中，说明该节点之前已经搜索过，不必再次搜索。下面给出每只蚂蚁构造高危险系数攻击路径时的算法ant_path_search的伪代码。

算法1 ant_path_search算法

算法第4行若构造的攻击路径含圈，属无效攻击路径，蚂蚁重新搜索；第7行属性v是已搜索过的分支，无需重新搜索；第11行蚂蚁根据式（3）中的概率选择下一步原子攻击节点；第16行对所有下一步属性节点的攻击路径做“+”运算，迭代构造完整的攻击路径。

依照此方法，蚂蚁可以构造一条攻击路径并计算出危险系数，循环运行算法K次，可以得到K条攻击路径，然后根据式（4）更新各个节点的信息素，更新搜索到的最大危险系数，重复此过程T次，得到最后结果。

假设攻击图AG中含有N个节点，每只蚂蚁最多对N个节点遍历一次，共有K只蚂蚁，迭代T轮，则该蚁群算法的时间复杂度为O(T×K×N)。

3.2 最小初始集生成

通过蚁群算法可以得到攻击路径中最高的危险系数，在此基础上，可以根据网络对安全的要求程度、网络规模和可承受代价多少的不同，设定一个容忍系数μ，危险阈值rth=rmax×μ，认为危险系数r＞rth的攻击路径具有较高危险性，应该予以阻断。同时，研究发现真实的攻击路径长度往往较短[10]，并且过长的攻击路径会降低攻击者的攻击意愿，因此设定一个攻击者攻击意愿的衰减系数γ，当攻击路径l长度大于lmax时，危险系数随攻击路径步数的增长而衰减。此外，考虑到一个网络中可能包括多个关键节点，不同的节点重要程度不同，因此为每个目标属性v设置一个参数λv反映目标节点的重要程度。当修复资源有限的情况下，该参数可以帮助管理员将更多的资源投入到更重要的节点上。因此攻击路径的危险系数公式更新为：

其中，m为路径l的步数；m′为lmax的步数。

容忍系数μ需要根据网络对安全的要求、网络规模和可承受代价的情况综合设置。对网络安全的要求越高，网络规模越小，可承受代价越大，μ应越小，危险阈值rth越小，满足危险系数r＞rth的攻击路径就越多，反之亦然。衰减系数γ则通过降低超长攻击路径的危险系数限制被选择的攻击路径数量，γ越小，超长路径的危险系数r越小，满足条件r＞rth的路径数量就越少，γ越大，则满足条件的路径数量就越多。参数λ需要根据目标节点的重要程度设置，越重要的节点λ应越大，对应该属性的攻击路径危险系数就越高，满足条件r＞rth的路径数量就越多。容忍系数μ、衰减系数γ和参数λ需要专业人员依据经验，并结合上述情况综合设置。

在后续分析中需要使用攻击路径对应的最小初始集，因此提出最小初始集生成算法（minimum initial reachable attribute sets，MIRAS），搜索全部危险系数r＞rth的攻击路径对应的最小初始集。首先给出一个新的集合运算符。

定义7（集合运算符“×”）设A、B为两个元素为集合的集合，从A中任取一个元素A′，B中任取一个元素B′，把它们的并集作为一个元素，所有这样的元素构成一个集合，称为集合A与B的“×”运算，记作A×B，即A×B={A′⋃B′|A′∈A,B′∈B}。

MIRAS算法从给定的关键属性节点v出发，采用深度优先搜索，并用危险阈值rth限制搜索过程，迭代地搜索出节点v的全部高危险系数最小初始集M(v)。在向前搜索过程中，若v是可达属性节点，则v的全部最小初始集M(v)就是v的父节点的最小初始集的并集；若v是原子攻击节点，则M(v)就是v的父节点的最小初始集的“×”运算。在搜索的同时计算当前攻击路径的危险系数，当一条攻击路径含圈，或危险系数小于阈值rth时，返回空集∅。这样就可以迭代地搜索出全部危险系数大于阈值rth的攻击路径对应的最小初始集。由于篇幅的原因，这里不再详述MIRAS算法的伪代码。

下面分析MIRAS算法的时间复杂度。设最高危险系数攻击路径的步数为m′，对于容忍系数μ、衰减系数γ和参数λ，存在正整数m使得λγm+1＜μ＜λγm，因此算法搜索的攻击路径长度不大于m′+m。设攻击图中节点个数为N，节点的最大入度为d，则当v为属性节点时，最多调用MIRAS(ai,r,m)算法d次，当v为原子攻击节点时，最多调用MIRAS(vi,r,m+1)算法d次，因为搜索的路径长度不大于m′+m，算法最多迭代2(m′+m)次，所以MIRAS算法的时间复杂度为O(d2(m′+m)×N)。由于m′+m为正整数，算法具有多项式级时间复杂度。

MIRAS算法给出了对于单一关键属性v的全部最小初始集的计算方法。若攻击图中存在多个关键属性，只需为每一个关键属性vi′增加一个虚拟的下一步原子攻击ai′，将这些原子攻击的危险系数分别设为λi′，再为这些原子攻击增加一个共同的虚拟结果属性vk′，即可把求关键属性集Vk的全部高危险系数最小初始集问题转化为求关键属性vk′的高危险系数最小初始集问题。

4 最优修复集生成方法

通过上文的方法可以获得攻击图中全部危险系数大于阈值的攻击路径对应的最小初始集，需要对这些最小初始集进行进一步的分析、计算，最终得到最优修复集，即网络安全加固策略。

4.1 最优修复集问题

关键属性vk的每一个最小初始集代表着一条可能的攻击路径，因此可以采取消除其中某些初始属性的方法来阻断该路径，这些措施包括为系统漏洞打补丁，修改系统设置，禁用服务，加装防火墙或修改防火墙设置，改变网络拓扑等。

定义8（待修复集）在一个最小初始集中，所有可以被相应的安全弥补措施消除的属性构成的集合，称为待修复集。

5.动词不定式复合结构做后置定语，它和动词不定式短语一样，均只能放在被修饰成分的后面，做后置定语。例如：

定理1消除待修复集中的任意一个属性，均可阻断对应的攻击路径。

证明对于关键属性vk，Va是vk的一个最小初始集，Vr是Va对应的待修复集，显然Vr⊆Va，∀v′∈Vr有v′∈Va，根据最小初始集定义可知，Va-v′⇒vk。 □

为了保障关键属性的安全，需对其全部高危险系数攻击路径对应的待修复集进行修复。根据定理1，在对单个待修复集进行修复时，只需选择其中的一个属性，并采取相应措施将其消除即可。同时，通过图1的例子可以发现，不同的最小初始集中可能含有共同的初始属性，因此消除一个属性可能同时修复多个待修复集。而每种阻断措施都需要付出一定的代价，例如修改系统设置或防火墙设置可能以降低系统易用性甚至牺牲某些业务功能为代价，系统升级可能以服务断开时间为代价等。因此，如何选取属性进行消除，使总代价最低就成为网络安全加固策略生成研究的关键问题。本文称该问题为最优修复集问题，该问题的数学描述如下。

在攻击图AG中，设vk为关键属性，为vk的全部待修复集，，设变量yj，若vj被选中，则yj=1，否则yj=0，cj为vj的代价。要使最优修复集总代价最小，就是要求：

该问题等价于带权重的集合覆盖问题，是NP完全问题，精确求解算法时间复杂度为指数级，对于大规模网络，显然不具有实际应用价值。贪婪算法[14]是解决该问题的一个方法，效率很高，但极易陷入局部最优，因此得到的加固策略代价较高。生成网络安全加固策略的目的是为网络安全管理员提供参考，在资源有限的情况下如何保障网络具有更高的安全性。因此，对于大规模网络的安全加固来说，相比于快速给出一个代价较高的加固策略，在可接受的时间范围内计算出代价更低的加固策略显然更具实用价值。基于此出发点，提出基于蚁群算法的网络安全加固策略生成算法AS-NSH，求解最优修复集。

4.2 网络安全加固策略生成

首先对问题进行预处理，步骤如下：

AS-NSH算法描述如下：

首先构建一个完全图，节点集合由Vr中的全部属性和一个哑元节点构成，每个节点都具有信息素，每轮投放K只蚂蚁。开始时，所有蚂蚁都从哑元节点开始构解，每只蚂蚁根据式（11）给出的概率选择下一步节点，蚂蚁每访问一个节点，就将该节点加入已选节点集，同时，已覆盖的集合也可能发生变化，因此，在蚂蚁每一步行动之后，都需要重新计算剩余节点的选择概率。

其中，Vallowed是没有被选择的节点集合；参数α,β＞0；τi是节点i的信息素浓度；是蚂蚁k选择节点i的收益代价比，可以表示为：

其中，Seti表示节点i能够覆盖的待修复集的集合；表示蚂蚁k当前已经覆盖的待修复集的集合；wi是节点i对应的代价。

其中，Q是一个常数；Wk是蚂蚁k构造解的代价；t是迭代次数；ρ∈[1,0]是控制信息素τi挥发的参数；Δτi是节点i上信息素的总增量；是蚂蚁k在节点i上留下的信息素量。在信息素更新之后，进行第t+1次迭代。算法经过T轮迭代后，得到最终结果。

下面分析AS-NSH算法的时间复杂度。设待修复集个数为m，节点数即属性个数为n，一只蚂蚁每次选择下一步节点前都要计算所有剩余节点的选择概率，蚂蚁最多选择n个节点，每轮有K只蚂蚁，迭代T轮，因此AS-NSH算法的时间复杂度为O(T×K×n2)。

通过AS-NSH算法能够计算出目标网络的最优修复集，即获得了该网络的安全加固策略，即对最优修复集中的每个属性，采取相应的网络安全加固措施进行消除，保障目标网络安全。

5 仿真实验与评价

设计两组仿真实验分别验证本文提出的最小初始集生成方法和最优修复集生成方法的性能。仿真实验的主机环境为Intel CoreTM2 Quad CPU 2.67 GHz，4.0 GB RAM，Windows 7操作系统，采用Java编程实现。

5.1 最小初始集生成方法性能分析

实验模拟生成5个不同规模的攻击图，属性节点的最大入度和出度均为4，原子攻击节点的最大入度为3，出度为1，原子攻击的危险系数为0到1之间的随机值。攻击图的规模特征如表1所示，对提出的ant_path_search+MIRAS（APSM）算法、Obtain-Path（OP）算法[14]和精确求解的Network-Hardening（NH）算法[13]的时间性能进行对比。APSM算法中，MIRAS算法的λ均设为1，蚁群算法的迭代计算次数T=100，蚂蚁数量，其他参数设置如表2所示。

Table 1 Scale characteristics of simulated attack graphs表1 模拟攻击图的规模特征

图2给出了NH算法、不同参数的OP算法和不同参数的APSM算法在5组攻击图上的时间性能情况，纵坐标以指数形式表示。其中，OP1的有效路径长度n=10；OP2的有效路径长度n=15；APSM1的容忍系数μ=0.2，衰减系数γ=0.6；APSM2的容忍系数μ=0.1，衰减系数γ=0.8。其中，在后两个实验攻击图上，NH算法在104s内没有给出结果。可以看出，NH算法的运行时间随攻击图规模扩大而急剧增长，可扩展性较差，难以实际应用。APSM算法和OP算法的运行时间增长较慢，均具有良好的可扩展性，计算时间复杂度方面均优于NH算法。

Table 2 Parameters of ant_path_search algorithm表2 蚁群算法的参数设置

Fig.2 CPU time of algorithms in different scales of attack graphs图2 不同规模攻击图下各算法的CPU运行时间

同时可以看出，OP算法和APSM算法的运行时间受参数设置的影响明显。对比OP1与OP2可知，OP算法的运行时间随有效路径长度n的增大而增长。对比APSM1与APSM2可知，容忍系数μ越小，哀减系数γ越大，则算法运行时间越长，反之则运行时间越短。

整体上APSM算法的运行时间稍长于OP算法，这是因为APSM算法为了更准确地对攻击图进行风险评估，首先需要对攻击图中的最高危险系数进行计算，需要消耗少量时间，APSM算法在搜索时还需要不断计算已生成路径的危险系数，同样需要消耗时间。虽然OP算法在时间性能上略优于APSM算法，但OP算法生成的攻击路径还需要进一步计算生成最小初始集，并且OP算法仅以路径长度作为风险评判的依据，需要在算法运行前对网络状况缺乏一定了解的情况下确定有效路径长度n。而APSM算法综合了攻击实施难度、后果严重程度、攻击路径长度和目标节点的重要程度来判断攻击路径的危险程度，并且可以在对网络的安全状况有一定了解的情况下设置参数，结果更符合真实情况。因此，APSM算法在运算结果的合理性上优于OP算法。

5.2 最优修复集生成方法性能分析

实验使用10组数据对比AS-NSH算法和Weighted-Greedy（WG）算法[14]的性能，该数据集由布鲁内尔大学的Beasley教授在文献[17]中提出，是一组求解集合覆盖问题的实例数据，提供公开下载。每组数据包括集合数m、元素数n、每个元素的代价Wi、每个集合包含的元素和每组问题的最优解，最优解即能够覆盖全部集合的最低总代价。对10组数据分别用WG算法和AS-NSH算法进行求解，AS-NSH算法参数设置如下：迭代次数T设为100次，α为1，β为2，ρ为0.5，Q为1，K设为20，τ0设为K/Wg。实验结果如表3所示。

Table 3 Experimental results of two algorithms on different data sets表3 两种算法在各实验数据集上的运行结果

表3展示了各组数据的规模特征和两种算法的运行结果。算法下面的两列数据分别为所生成的解C和生成解与最优解相差的百分比S，其中AS-NSH算法的结果为20次运算的平均值。对比实验结果可知，AS-NSH算法生成的解均明显小于WG算法。AS-NSH算法的平均结果比最优解高3.36%，而WG算法平均比最优解高11.69%。相比于WG算法，ASNSH算法将生成策略与最优策略的差距降低了71.3%。图3展示了WG算法、AS-NSH算法在10组数据上运行结果与最优解的对比，其中横坐标为数据集编号，纵坐标为各算法的解。

Fig.3 Results of two algorithms and optimum图3 两种算法的结果与最优解的对比

Fig.4 CPU time of two algorithms图4 两种算法的CPU时间

图4展示了两种算法在各组数据上运行的平均时间。WG算法所需时间均小于1 s，明显少于ASNSH算法。AS-NSH算法的运行时间虽然较多，但依然在合理的范围内，而结合之前的实验结果，WG算法计算出的结果并不理想。在实际应用中，WG算法给出的加固策略会给用户造成更大的修复代价，而AS-NSH算法的结果更接近最优解，能够有效地降低所需的安全加固代价，在资源有限的情况下获得更优的加固策略和更好的安全保障。对于一个实际的网络，生成安全加固策略需要的时间只要在合理的范围内即可，能够计算出更好的解，尽可能地为用户节约修复代价显然更具实际意义。因此对于大规模网络的安全加固，AS-NSH算法具有更大的实际应用价值。

6 结束语

本文提出了一种面向大规模网络安全加固的攻击图分析方法。首先提出了综合考虑攻击难度、攻击后果严重程度、路径长度和目标节点重要程度的风险评估方法，并通过启发式算法计算最大风险系数的攻击路径，避免了精确搜索攻击路径的指数级时间复杂度问题；然后结合最大风险系数、网络规模、网络性质和实际需求设置危险阈值，搜索高风险的最小初始集；最后提出启发式算法求解最优修复集问题，计算低代价的网络安全加固策略，避免精确求解的指数级时间复杂度问题。实验结果表明，本文方法具有良好的可扩展性，可应用于大规模网络中，与现有方法相比，能够在可接受的时间内，有效地获得更符合真实威胁情况的攻击路径。在本次选取的实验数据集上，相比于贪婪算法，本文方法将生成策略与最优策略的差距减小了71.3%。综上所述，本文方法具有更强的实际应用价值。在后续的研究工作中，将进一步完善攻击路径的风险评估方法，使之更加符合真实情况，同时对提出的各算法进行优化，进一步降低网络安全加固策略的代价。

[1]Zang Yuqing,Li Xiaoyu,Zheng Chen,et al.2010 security vulnerability analysis and prospect[J].Netinfo Security,2011(2):69-72.

[2]Helmer G,Wong J,Slagell M,et al.Asoftware fault tree approach to requirements analysis of an intrusion detection system[J].Requirements Engineering,2002,7(4):207-220.

[3]Schneier B.Attack trees[J].Dr Dobb's Journal,1999,24(12):21-29.

[4]Phillips C,Swiler L P.A graph-based system for networkvulnerability analysis[C]//Proceedings of the 1998 Workshop on New Security Paradigms,Charlottsville,Sep 22-25,1998.New York:ACM,1998:71-79.

[5]Ammann P,Wijesekera D,Kaushik S.Scalable,graph-based network vulnerability analysis[C]//Proceedings of the 9th ACM Conference on Computer and Communications Security,Washington,Nov 18-22,2002.New York:ACM,2002:217-224.

[6]Ingols K,Lippmann R,Piwowarski K.Practical attack graph generation for network defense[C]//Proceedings of the 22nd Annual Computer Security Applications Conference,Dec 11-15,2006.Washington:IEEE Computer Society,2006:121-130.

[7]Ou Xinming,Boyer W F,McQueen M A.A scalable approach to attack graph generation[C]//Proceedings of the 13th ACM Conference on Computer and Communications Security,Alexandria,Oct 30-Nov 3,2006.NewYork:ACM,2006:336-345.

[8]Ye Yun,Xu Xishan,Qi Zhichang,et al.Attack graph generation algorithm for large-scale network system[J].Journal of Computer Research and Development,2013,50(10):2133-2139.

[9]Ou Xinming,Govindavajhala S,AppelAW.MulVAL:a logicbased network security analyzer[C]//Proceedings of the 14th USENIX Security Symposium,Baltimore,Jul 31-Aug 5,2005.Berkeley:USENIXAssociation,2005,14:8.

[10]Jajodia S,Noel S.Topological vulnerability analysis:a powerful new approach for network attack prevention,detection,and response[J].Algorithms,Architectures,and Information Systems Security,2007,3:285-305.

[11]Jha S,Sheyner O,Wing J.Two formal analyses of attack graphs[C]//Proceedings of the 15th IEEE Computer Security Foundations Workshop,Cape Breton,Jun 24-26,2002.Washington:IEEE Computer Society,2002:49-63.

[12]Noel S,Jajodia S,O'Berry B,et al.Efficient minimum-cost network hardening via exploit dependency graphs[C]//Proceedings of the 19th Annual Computer Security Applications Conference,Las Vegas,Dec 8-12,2003.Washington:IEEE Computer Society,2003:86-95.

[13]Wang Lingyu,Noel S,Jajodia S.Minimum-cost network hardening using attack graphs[J].Computer Communications,2006,29(18):3812-3824.

[14]Chen Feng,Zhang Yi,Su Jinshu,et al.Two formal analyses of attack graphs[J].Journal of Software,2010,21(4):838-848.

[15]Wu Jinyu,Jin Shuyuan,Yang Zhi.Analysis of attack graphs based on network flow method[J].Journal of Computer Research and Development,2011,48(8):1497-1505.

[16]Wang Shuzhen,Zhang Zonghua,Kadobayash Y.Exploring attack graph for cost-benefit security hardening:a probabilistic approach[J].Computers&Security,2013,32(1):158-169.

[17]Beasley J E.An algorithm for set covering problem[J].European Journal of Operational Research,1987,31(1):85-93.

附中文参考文献：

[1]张玉清,李潇宇,郑晨,等.2010年安全漏洞态势分析与展望[J].信息网络安全,2011(1):69-72.

[8]叶云,徐锡山,齐治昌,等.大规模网络中攻击图自动构建算法研究[J].计算机研究与发展,2013,50(10):2133-2139.

[14]陈锋,张怡,苏金树,等.攻击图的两种形式化分析[J].软件学报,2010,21(4):838-848.

[15]吴金宇,金舒原,杨智.基于网络流的攻击图分析方法[J].计算机研究与发展,2011,48(8):1497-1505.