一种智能高效的最优渗透路径生成方法

随着网络应用的广泛普及以及支撑技术的不断发展，云计算、智能设备、区块链、物联网等不断涌现的新技术正在深刻改变人们生活方式，推动社会的飞速发展.然而，与此同时，伴随网络而来的安全问题也愈发严重，不仅给广大用户和企业带来严重的损失，也威胁着国家安全与社会稳定.根据国家计算机网络应急技术处理协调中心的2017年度网络安全工作报告[1]，2017年我国境内感染计算机恶意程序的主机数量约1 256万个，规模在100个主机以上的僵尸网络数量达3 143个，WannaCry蠕虫病毒事件爆发等.然而，在众多网络攻击形式中，渗透攻击威胁更大，特别是以高级可持续攻击(advanced persistent threat, APT)为代表的渗透攻击，给国家、军队和企业带来了巨大的威胁.“震网”病毒[2]开启了APT攻击的先河，随之而来的极光攻击、夜龙攻击、Lurid攻击等均造成了巨大的危害.2017年6月安全厂商ESET公布一款针对电力变电站系统进行恶意攻击的工业控制网络攻击武器Win32 width=5,height=11,dpi=110

Industroyer(ESET命名)，该攻击武器能够直接控制断路器，导致变电站断电.除此之外，BlackTech网络间谍组织以窃取高新技术行业的机密信息为攻击目的，发动多阶段的渗透攻击，给企业带来不可预估的经济损失，同时也严重影响了企业名誉.深入分析近年危害巨大的攻击可知，攻击者通过渗透攻击，不断利用目标网络中的漏洞，持续在内网渗透，最终入侵目标并窃取敏感数据，给国家、军队乃至企业带来巨大的威胁.渗透攻击成为目前网络攻击主要手段之一，严重危害着网络空间安全.

依据网络攻防对抗实践可知，网络中的漏洞是客观存在的，且不能完全被消除.攻击者会利用目标网络中的诸多漏洞，发动一系列有序攻击行为，最终实现攻击目标.随着网络规模的不断扩大，目标网络中的漏洞数量也成倍增加.由于防御资源的有限性，防御方不可能修复所有的漏洞.鉴于此，如何准确高效评估网络中的渗透威胁，从而采取有针对性的防御措施，成为当前网络空间安全防御的重要研究内容.渗透路径描述了攻击者对网络发起的一系列攻击行为，而最优渗透路径描述了攻击者针对某一攻击目标的最大可能渗透路径.依据最优渗透路径，防御方能够最优化防御资源部署，进而实现防御效能的最大化.因此，研究最优渗透路径的生成方法，能够为网络安全防御提供重要决策依据，成为当前应对渗透攻击威胁的重要手段.

攻击图是描述渗透路径的经典模型，攻击图与贝叶斯结合形成的贝叶斯攻击图成为当前求解最优渗透路径的研究热点[3-6].Phillips等人[7]首先提出了攻击图模型，而后攻击图经历了从手工构建到自动构建的过程，具有代表性的成果是TVA[8]和TIAA[9].然而，这些算法的效率较低，无法适用于大规模网络.在攻击图模型中，攻击图的构建过程也就是渗透路径的生成过程.因此，如何提高攻击图构建的效率成为生成渗透路径及最优渗透路径的关键，也是后续网络安全效能评估的基础.当前，从优化思想角度，攻击图构建的优化算法主要可分为2种：

1) 通过预先制定策略来简化攻击图的生成.Ammann等人[10]假设攻击者不会为了获取已有权限而发动攻击，一定程度上解决了属性攻击图含圈的问题.Ou等人[11]通过预先设置攻击目标，然后利用反向搜索的方法生成局部攻击图，提高了攻击图的生成效率，但生成的攻击图不够全面.Dawkins等人[12]通过限制攻击步骤数简化攻击图.同样地，马俊春等人[13]也采用限制攻击步骤数的优化策略，解决了攻击图生成过程中存在的状态爆炸问题.苘大鹏等人[14-15]则采用限制攻击步骤数和攻击路径成功概率的策略来克服攻击图的状态爆炸问题.叶云等人[16]仅是针对某一确定的攻击目标而生成的攻击图，而非全局攻击图.Barrère等人[17]提出核心攻击图的概念，仅关注于给定源节点和目的节点间的渗透路径.

2) 通过约简攻击图的表示方式来提高其生成效率.Noel等人[18]采用层次合并和邻接矩阵的方法来减小攻击图显示的节点数量，而状态爆炸问题依然没有解决.苏婷婷等人[19]则提出属性领接矩阵的表示方法，并设计多步邻接矩阵的算法，提高了攻击图的可视性，然而其生成效率依然不高.钟尚勤等人[20]提出主机攻击图生成模型和算法，通过将网络中的主机划分安全组，生成高层次的攻击图，然而该方法对目标网络环境要求较为苛刻，适用性不强.此外，Hong等人[21]提出了分层攻击图表示模型，并证明在网络安全分析中，该模型比攻击图和攻击树更高效，但其并没有深入研究该分层攻击图生成的效率问题.Xie等人[22]提出了一种2层的攻击图，利用邻接矩阵的不断迭代最终生成最优渗透路径，并用灰度图像表示不同主机间的渗透关系，但其方法中生成渗透路径的效率仍不高.Hong等人[23]利用分层的攻击表现模型(attack representation models)来评估移动目标防御(moving target defense, MTD)的有效性，同样，其仅是利用该模型进行分析，并没有给出模型的生成方法.Pokhrel等人[24]提出利用主机访问图结合概率统计模型来分析网络中漏洞节点的重要性，它本质上也是一种分层的攻击图，即主机访问图相当于上层，然而其注重安全评估，并没有深入研究主机访问图的生成效率.此外，Wang等人[25]提出了一种启发式搜索的攻击图构建方法，设计了匹配索引表，提高了原子攻击匹配效率.Kerem等人[26]则建立了一个多代理分布式处理平台，利用虚拟机的并行计算提高攻击图的生成效率，然而该方法仅是一种空间换时间的方式，没有从根本上解决效率问题.

当前以APT攻击为代表的渗透攻击，具有持续时间长的特点，第1种方法通过限制攻击路径长度和状态转移概率等策略往往并不适用于此类攻击的分析，这也给渗透路径的生成提出了新的挑战.在第2种方法中，分层攻击图模型一方面与漏洞数量解耦，提高了攻击图生成效率；另一方面其表现形式灵活，便于最优渗透路径生成及相关的网络安全效能评估.此外，当前的攻击图模型仅注重描述目标网络中已有的漏洞利用关系，不利于描述未知攻击和内部攻击.

鉴于此，在考虑未知攻击和内部攻击条件下，为进一步提高最优渗透路径的生成效率，本文提出一种智能高效的最优渗透路径生成方法.首先提出双层威胁渗透图(two-layer threat penetration graphs, TLTPG)模型，其下层为主机威胁渗透图(host threat penetration graph, HTPG)，描述了目标网络中任意2个主机间的微观渗透场景；上层为网络威胁渗透图(network threat penetration graph, NTPG)，描述了目标网络中各主机之间的宏观渗透关系.借助知识图谱思想构建主机资源知识图谱(host resource knowledge graph, HRKG)，提高了单步渗透攻击构建的灵活性和效率，且可用于描述0day漏洞攻击，克服了传统攻击图仅可描述已知攻击的不足.进一步，利用TLTPG，设计智能化的基于渗透信息交换的最优渗透路径选择算法，大大提高了最优渗透路径的生成效率.

1 TLTPG模型

传统的基于攻击图的渗透路径生成方法主要存在3方面缺陷：1)攻击图生成效率较低，无法适应大规模网络；2)攻击图描述了目标网络中已有的漏洞利用关系，但不利于描述未知攻击和内部攻击.为了解决该问题，本文构建了TLTPG模型，作为一个双层图结构，其下层为HTPG，描述了目标网络中任意2个主机间的微观渗透场景；上层为NTPG，描述了目标网络中各主机之间的宏观渗透关系.

定义1. 主机威胁渗透图表示为GHTPG=(NHTPG,EHTPG).NHTPG为节点，用 width=5,height=11,dpi=110

Host,Privilege width=5,height=11,dpi=110

表示，描述攻击者获得的主机权限，其中Host表示攻击者已渗透的主机，可用该主机的IP地址表示，Privilege表示攻击者获得的主机权限，分为User和Root；EHTPG表示边，用于描述单步渗透攻击，用 width=5,height=11,dpi=110

Service,Vulnerability,Probability width=5,height=11,dpi=110

表示，其中Service表示渗透攻击所利用的主机服务，Vulnerability表示渗透攻击所利用主机服务上的漏洞，一般用公共漏洞和暴露(common vulnerabilities and exposures, CVE)编号表示,Probability表示渗透攻击成功的概率.

定义2. 网络威胁渗透图表示为GNTPG=(NNTPG,ENTPG).NNTPG为节点，描述主机标识，一般用主机的IP地址表示；ENTPG表示边，描述主机间渗透成功概率，用 width=5,height=11,dpi=110

UP，RP

表示，其中UP表示从源主机渗透获得目的主机User权限的概率，RP表示从源主机渗透获得目的主机Root权限的概率，二者均为0-1之间的实数.

图1展示了一个简单的TLTPG实例.相对于传统的攻击图，TLTPG通过分层，宏观与微观相结合，有效减少了由于生成全局攻击图造成的高计算复杂度和空间复杂度，且增强了其可视性，便于网络管理员理解当前网络面临的渗透威胁态势.

2 基于知识图谱的HTPG生成

HTPG从微观层面细致描绘了任意2个主机之间的渗透攻击场景.显然，当从主机HA不能渗透到HB时，则从主机HA到主机HB不存在HTPG.假设目标网络中的主机数为M个，再加上1个外部的攻击者(相当于1个主机)，则最多有(M+1)×M个HTPG.本质上，HTPG相当于将传统的全局攻击图以主机为单位进行分割，使得由原来的1个全局攻击图转换为多个HTPG，使得每一个HTPG的规模更小，生成更加灵活，也更有利于后续的网络安全分析.

传统的攻击图生成主要依赖构建攻击模式并将其实例化，这种方法较为复杂且不能处理0day漏洞攻击.当前，知识图谱作为一个流行的知识表达和推理模型，在人工智能、语义搜索等领域取得了重大进展，不同于以往的推理模型，知识图谱具有简洁直观、灵活丰富的知识表达能力，使得基于知识图谱的推理也变得更加高效智能[27-28].鉴于此，本文以每个主机为单位建立了HRKG，其主要利用漏洞扫描工具和配置管理器等网络安全工具，收集主机中与渗透攻击有关的信息，并将这此信息进行合理地归并组织.一个典型的HRKG如图2所示：

图2展示了一个典型的HRKG，利用(主语-谓语-宾语)三元组进行描述.例如“HB”-“Running Service”-“IIS Web”表示主机HB上运行了IIS服务，“IIS Web”-“Using Port”-“80”表示IIS Web服务需要使用80端口，“IIS Web”-“Existing Vulnerability”-“CVE-2002-0364”表示IIS Web服务上存在CVE编号为CVE-2002-0364的漏洞，“CVE-2002-0364”-“Getting Privilege of a Successful Attack”-“Root”表示攻击者利用CVE编号为CVE-2002-0364的漏洞发动攻击可获得此主机的Root权限，“CVE-2002-0364”-“Probability of a Successful Attack”-“0.5”表示攻击者利用CVE编号为CVE-2002-0364的漏洞发动攻击成功的概率为0.5，此概率由通用漏洞评分系统(common vulnerability scoring system， CVSS)确定.特别地，服务分为本地服务和远程服务，远程服务则需要使用端口.当一个服务没有包含端口的三元组时，表示此服务为本地服务，则攻击者利用此服务中漏洞的前提条件是攻击者拥有此主机的User权限.考虑到未知攻击在目前网络攻击中所占比重逐渐增大，其对网络安全评估的结果影响也较大，本文利用假设规则来处理未知攻击，进而提高网络漏洞评估的准确性和合理性，具体设计规则如下：若远程服务没有漏洞，则假设其存在一个0day漏洞，攻击者可利用此漏洞获得主机的User权限，其概率为0.05；若本地服务没有漏洞，则假设其存在一个0day漏洞，攻击者可利用此漏洞获得主机的Root权限，其概率为0.05.此概率可依据具体网络的实际状况灵活设定.

依据HRKG，结合由网络拓扑工具获得的主机间连接信息，很容易得到由主机HA到主机HB的HTPG，如图2中所示，当主机HA能够连接到主机HB的80和21端口时，生成的主机HA到主机HB的HTPG如图3所示.显然，利用乘法原则，由HTPG易得从主机HA渗透获得主机HB的User权限的概率为0.7，从主机HA渗透获得主机HB的Root权限的概率为0.56.

相比传统攻击模式方法的复杂性，基于知识图谱的HTPG生成方法更加简洁直观、灵活智能，具备了知识推理的逻辑结构能力，且能够有效表征未知攻击，提高了攻击描述能力.

3 基于渗透信息交换的NTPG生成

定义3. 最优渗透路径.渗透分为直接渗透和间接渗透.直接渗透指从一个主机直接发起攻击渗透到另一个主机；间接渗透指从一个主机通过其他主机作为跳板发起多步攻击渗透到另一个主机.从主机HA发动攻击渗透到主机HB最大可能的攻击路径，称为主机HA到HB的最优渗透路径.显然，最优渗透路径可能为直接渗透或间接渗透.

定义4. 渗透成功概率.主机HA到HB的最优渗透路径的渗透成功概率称为从主机HA到HB的渗透成功概率.渗透成功概率计算依据乘法原则，若主机HA到HB的渗透成功率为0.5，主机HB到主机HC的渗透成功概率为0.7，则从主机HA经过主机HB到主机HC的攻击成功率为0.5×0.7=0.35.特别地，NTPG中的概率便指的是渗透成功概率.

由HTPG易得到任意2个主机之间的直接渗透成功概率，然而由于主机之间渗透路径的多样性，使得2个主机之间的直接渗透并非一定是2个主机之间的最优渗透路径，也就是说由HTPG获得的2个主机之间的直接渗透成功概率并非此2个主机之间的渗透成功概率.例如，当由HTPG得到主机HA到HB的直接渗透成功概率为0，即从主机HA并不能直接渗透到主机HB(可能是从主机HA不能直接访问主机HB)，同时，由HTPG得到主机HA到主机HC的直接渗透成功概率为(0.6,0.4)，主机HC到主机HB的直接渗透成功概率为(0.5,0.4)，显然通过间接的主机HC，从主机HA能够渗透成功到主机HB.因此，如何利用HTPG生成它们的最优渗透路径以及渗透成功概率是生成NTPG的关键.

针对此问题，本文从经典的路由信息协议(routinn information protocol， RIP)获得启发，提出了基于渗透信息交换的NTPG生成(NTPG generation， NG)算法，该算法是一个分布式算法.将每一个主机都看作一个智能体，一边维护从它自己到其他每一个主机的渗透信息，另一边不断和其他主机交换渗透信息.每个智能体的动作如下：

1) 仅和相邻主机交换渗透信息.如果从主机HA能够直接渗透到主机HB，则称主机HB为主机HA的相邻主机.NG算法规定，不相邻的主机不交换渗透信息.

2) 主机交换的渗透信息是当前主机所知道的全部信息，即自己的渗透信息表.也就是说，交换的信息是“我到目标网络中所有主机的渗透成功概率，以及渗透到每个主机应利用的下一个跳板主机”.

3) 按固定的时间间隔交换渗透信息.例如每隔1 min.然后主机根据自己收到的渗透信息更新渗透信息表.当主机连接、漏洞更新等网络安全要素变化时，相应主机也及时向相邻主机通告网络安全要素变化后的渗透信息，以保证目标网络中所有主机的渗透信息的准确性.

显然，NG算法在刚刚开始时，每个主机仅知道到其相邻主机的渗透成功概率(由HTPG可知).接着，每一个主机也仅和数量非常有限的相邻主机交换并更新渗透信息.但经过若干次的交换更新后，所有的主机最终都会知道到达目标网络中任何一个主机的渗透成功概率和渗透到每一个主机应利用的下一个跳板主机.

渗透信息表中最主要的信息是：到某个主机的渗透成功概率(即最大可能攻击路径的概率)，以及应经过的下一个跳板主机.渗透信息更新的原则是找出到每个主机的渗透成功概率.

下面以一个简单的例子介绍该算法.假定一个目标网络中有6台主机，分别记为HA,HB,HC,HD,HE和HF，已知主机HA的渗透信息表，如表1所示.现在收到相邻主机HB发来的渗透更新信息，如表2所示.

其中“NO”表示无下一个跳板主机，即可通过直接渗透到目标主机.更新后的主机HA的渗透信息表如表3所示.

NG算法让目标网络中的所有主机都和自己的相邻主机定期交换渗透信息，并不断更新其渗透信息表，确定从每一个主机到目标网络中的其他主机的最优渗透路径(即最大可能的渗透成功概率).特别地，虽然所有的主机最终都拥有了到目标网络中的其他所有主机的渗透信息，但由于每一个主机的位置不同，它们的渗透信息表也是不同的.NG算法核心如下.

算法1. NG算法核心.

输入:初始的渗透信息表

表示主机Hx的初始渗透信息表，N为目标网络中主机的数量，

表示主机Hx当前渗透信息表，x.neighbor_host表示主机Hx的相邻主机* width=7,height=11,dpi=110

输出:最终的渗透信息表

① PITcurrent=PITinitial;

③ for each host Hy∈x.neighbor_host

⑦ PITfinal=PITcurrent.

PIT_CHANGE为任意2个主机进行渗透信息交换的函数，其定义如下：

*主机HA 的初始渗透信息表为PITA，主机HA获得主机HB的渗透信息表PITB后利用渗透信息交换更新为PITA′，i∈PITB表示属于渗透信息表PITB中的一个表项,i.target_host表示渗透信息表中表项i的目标主机，渗透成功概率(penetration success probability)简写为psp，i.next_jump_host表示渗透信息表中表项i的下一跳板主机* width=7,height=11,dpi=110

② if isempty(PITB)

⑤ for each item i∈PITB

⑥ if

∃j∈PITA′ and j.target_host=

⑦ i.psp=i.psp×(psp of HA to HB);

⑧ i.next_jump_host=HB;

⑨ add i to PITA′;

if ∃j∈PITA′ and j.target_host=

if i.psp×(psp of HA to HB)>j.psp

j.psp=i.psp×(psp of HA to HB);

j.next_jump_host=HB;

else if i.psp×(psp of HA to HB)≤j.psp

基于渗透信息交换的NTPG生成算法的最终目标是使目标网络中所有主机都得到正确的渗透成功概率，即达到收敛.它是一种迭代算法，而算法1仅相当于一次迭代，即一次主机渗透信息交换，显然，经过算法1的若干次迭代，可实现最终目标.事实证明，基于渗透信息交换的NTPG生成算法是可收敛的，且收敛速度很快.

定理1. NG算法达到收敛所需的迭代次数=目标网络中最长渗透路径的步数-1.

证明. 用数学归纳法进行证明.

1) 当目标网络中最长渗透路径的步数为1时，目标网络中从一个主机到另一个主机的渗透均为直接渗透，显然，由HTPG得到的2个主机的直接渗透成功概率便是该2个主机间的渗透成功概率，即不需要迭代，也就是说NG算法达到收敛所需的迭代次数为0，定理1成立；

2) 假设目标网络中最长渗透路径的步数为m(m代表任意自然数)时，定理1成立，即NG算法达到收敛所需的迭代次数为m-1；

3) 当目标网络中最长渗透路径的步数为m+1时，对于目标网络中的任一对HA和HB，设从HA到HB的最长渗透路径的步数为p，显然p≤m+1.当p≤m时，由2)可知，经过m-1次迭代可获得从主机HA到HB的渗透成功概率；当p=m+1时，不妨设从HA到HB的最长渗透路径分割为2段，一段从HA到HB′共m步，一段从HB′到HB共1步，则由2)易知，经过m-1次迭代可获得从HA到HB′的渗透成功概率，由于从HB′到HB仅为1步，则再经过1次迭代，便可获得从HA到HB的渗透成功概率.至此可知，当目标网络中最长攻击路径的步数为m+1时，对于目标网络中的任一对主机HA和HB，经过m次迭代，便可获得从HA到HB的渗透成功概率，即NG算法达到收敛所需的迭代次数为m.

NG算法解决了由目标网络中所有的直接渗透概率求得任意2个主机的渗透成功概率(最优渗透路径的概率)，算法依赖的原理是目标网络中的任意主机都可能作为渗透的跳板.然而实际上，攻击者从主机HA渗透到主机HB，仅需要获取主机HA的User权限而非Root权限.因此，NG算法仅适用于求解关于User权限的渗透成功概率.为了进一步求解关于Root权限的渗透成功概率，引入一个函数F.

定义5. 函数F.C=F(A,B)，函数的输入为2个大小相等的矩阵A和B，函数的输出为矩阵C，其大小也与A和B相等.满足：

不妨设依据HTPG得到的关于Root权限的直接渗透矩阵为R0，而最终得到的NTPG中的关于User权限的间接渗透矩阵为U，Root权限的间接渗透矩阵为R.显然可得：

综上可知，利用NG算法能够获得U，进一步利用式(2)可获得R.

4 任意2个主机间的最优渗透路径生成

由第3节生成NTPG可知，每个主机都保持并记录自己的渗透信息表，渗透信息表的形式为 width=5,height=11,dpi=110

目标主机、渗透成功概率、下一个跳板主机 width=5,height=11,dpi=110

.若要确定从主机Hx到主机Hy的最优渗透路径，其算法如下：

算法2. 任意2主机间最优渗透路径生成算法.

输入:最终的渗透信息表

输出:OPPx y—主机Hx到主机Hy的最优渗透路径.

③ OPPx y={Hx} width=7,height=11,dpi=110

*初始化*

④ Ht=Hx;

*初始化,构造一个辅助主机Ht* width=7,height=11,dpi=110

⑤ while (j.next_jump_host～=∅)

*j为

中的一个表项，且j.target_host==Hy* width=7,height=11,dpi=110

⑥ add j.next_jump_host to OPPx y;

⑦ Ht=j.next_jump_host;

⑨ add Hyto OPPx y;

算法2借助目标网络中渗透信息表，利用链式索引方式，从主机Hx开始，不断索引渗透到目标主机Hy的下一个跳板主机，其算法复杂度为O(N).图4展示了主机Hx到Hy的最优渗透路径生成示例,其具体过程为：若要确定从主机Hx到Hy的最优渗透路径，首先索引主机Hx的渗透信息表，找到下一个跳板主机Ho，接着索引主机Ho的渗透信息表，找到下一跳板主机Hp，再接着索引主机Hp的渗透信息表，找到下一跳板主机Hq，继续索引主机Hq的渗透信息表，发现下一个跳板主机为空，则说明从主机Hq到目标主机Hy的最优渗透路径为直接渗透，故索引停止，最终生成的从主机Hx到Hy的最优渗透路径为Hx→Ho→Hp→Hq→Hy.进一步分析可得如下定理.

定理2. NG算法生成的最优渗透路径不含圈。

证明. 用反证法.假设NG算法生成的最优渗透路径含圈，如图5所示的含圈渗透路径实例，从主机Hx到Hy的最优渗透路径为Hx→Hm→Hn→Hm→Hy，其渗透成功概率为p1×p2×p3×p4，又p5和p4均为从主机Hm到Hn的渗透成功概率，故p5=p4，又因p2，p3必小于1，进而可知p1×p2×p3×p4<p1×p4=p1×p5，即可知从主机Hx到Hy的渗透路径Hx→Hm→Hy相比Hx→Hm→Hn→Hm→Hy渗透成功的概率更大，由最优渗透路径定义知，Hx→Hm→Hn→Hm→Hy并不为从主机Hx到Hy的最优渗透路径，固假设不成立.

5 实验与分析

为了验证本文方法的有效性，搭建了一个实际网络环境来进行测试.实验网络拓扑如图6所示.

外网用户可通过Internet访问本网络.实验网络分为4个区域，分别是DMZ区、子网1、子网2和子网3.DMZ区有1台Web服务器.子网1有2台设备，1台Pad和1台主机，可连接Internet.子网2有2台主机，不能连接Internet.子网3包括3台服务器，分别是打印服务器、文件服务器和数据服务器.网络中的服务访问规则如表4所示.其中，攻击者为Internet中的1台主机.通过Nessus漏洞扫描器对网络各网络段进行扫描，得到各主机中漏洞信息，结合CVSS得到表5所示的各主机信息及其所含漏洞信息.特别地，Pad和H1并不能通过网络访问内网的H2和H3，但由于人为操作不当的因素，可通过USB等传输设备连接到H2和H3.

5.1 TLTPG生成

依据每一个主机的漏洞信息，可建立了每个主机的HRKG，进而利用表4所示的访问规则可得到任意2个主机间的HTPG.下面以攻击者为源主机，Web服务器为目的主机为例，介绍HTPG的生成方法.首先依据表5中的Web服务器的漏洞信息建立其HRKG，如图7所示.

依据陈小军等人的文献[29]，设攻击复杂度为高、中、低的漏洞的利用成功率分别为0.2,0.6,0.8.由于Web服务器上运行着Apache Http Server和Tomcat两个服务，虽然利用漏洞扫描工具未发现Tomcat中有漏洞，但其中依然可能存在0day漏洞，故可利用假设规则，即假设Tomcat中存在一个0day漏洞.

由表4所示，攻击者可利用http通过80端口访问Apache Http Server，则可知从攻击者到Web服务器的HTPG如图8所示.进而可知从攻击者渗透获得Web服务器的User权限的概率为0.8，从攻击者渗透获得Web服务器的Root权限的概率为0.6(0.8×0.05=0.04<0.6).

由上述方法可生成目标网络中任意2个主机间的HTPG.不妨假设通过人为操作不当因素使得本来物理隔离的子网1和子网2连接的概率为0.4，进而可得到网络中主机间的直接渗透概率，如图9所示.

进一步，依据第3节的算法1和式(2)，能够得到关于User权限的间接渗透矩阵为U和关于Root权限的间接渗透矩阵为R.

5.2 任意2个主机间的最优渗透路径

不妨设外部攻击者要发动针对Database Server的攻击，则依据算法2可得出攻击者的最优渗透路径为attacker→Pad→H2→Database Server，即攻击者只需要3步就可获得Database Server的Root权限，其渗透成功概率为0.115 2.通过算法2可获得任意2个主机间的最优渗透路径，进而为针对目标网络中关键资产的防御提供重要决策依据，如目标网络中主机防御优先级选择(假设主机HA到目标网络中关键资产的渗透成功概率较大，则在防御资源有限的情况下应优先加强对主机HA的异常检测及脆弱性修复)、攻击场景构建及预测(依据TLTPG模型提供的概率知识推测漏警误警状况)等.

5.3 算法效率分析

通过分析整个最优渗透路径生成的全过程可知，NG算法是核心，其算法复杂性决定了最优渗透路径生成的效率.与本文算法最为相似的是文献[22].文献[22]中定义了F函数，进而利用F函数的N(N为目标网络中主机数量)次迭代获得了目标网络中各主机间的渗透成功概率，经分析，F函数的算法复杂度为O(N3)，则再经过N次迭代，其算法整体复杂度为O(N4).在本文提出的NG算法中，PIT_CHANGE函数的算法复杂度为O(N)，则算法1的复杂度为O(N3)，又由定理1可知，设目标网络中最长渗透路径的步数为m，算法1经过m-1次迭代可收敛，故NG算法的算法复杂度为O((m-1)×N3)，由目标网络特点及渗透攻击的一般性可知，m-1≪N.此外，文献[22]中提出在实际的目标网络中，由于矩阵的稀疏性，实际的算法开销必定小于O(N4)，同样，在本文算法中，PIT_CHANGE函数仅与一个主机的相邻主机的每项渗透信息相比较，其开销与其相邻主机的渗透信息表中项目数量成线性关系，远小于O(N).再者，算法1第2行的for循环，表示一个主机与所有相邻主机交换渗透信息，其开销与其相邻主机的数量成线性关系，也远小于O(N).由此可见，NG算法的开销也远小于O((m-1)×N3).又者，NG算法可拓展为一种分布式算法，其各个主机可并行进行渗透信息表的交换，也提高了算法的效率.综上分析可知，本文算法1在开销上优于文献[22]中的算法，具有一定的性能优势.

为了进一步分析本文算法的实际效率，我们对算法进行了仿真测试.仿真测试的实验平台为Hp Z240 Tower Workstations，处理器为Inter® Xeon® CPU E3-1234 v6，频率为3.7 GHz，内存为32 GB.仿真测试软件为Matlab 2010.我们测试了网络节点数目N为10,20,30,50和100时不同算法的运行时间.对于每组实验，我们重复10次，取其平均值.针对文献[22]中Xie利用F函数来计算渗透成功概率，他仅是直接利用F函数迭代N-1次来得到收敛结果，这种方式往往会消耗很多时间.实际上，理论分析可知，F函数往往仅需要迭代小于N-1次便能得到收敛结果.鉴于此，我们进一步改进了Xie的算法，通过控制F函数的迭代次数，使其一达到收敛便停止无效的迭代运算.进而，将我们的算法、Xie的算法和改进Xie的算法进行了对比，不同主机数目条件下3种算法花费的时间如图10所示：

实验结果表明：无论目标网络中的节点数为多少，我们的算法均保持最优，改进的Xie算法其次，而Xie算法效率最差.当目标网络中的节点数大于30时，Xie的算法消耗时间急剧上升;当目标网络中的节点数大于50时，改进的Xie的算法也开始急剧上升.当目标网络中的节点数为100时，我们算法需要34.5 min，改进Xie的算法则需要将近4.4 h，Xie的算法则需要31.2 h.此外，我们算法所需时间随目标网络节点数增长速率保持在可接受范围内.综上实验分析可知，相比较于Xie的算法，我们算法具有明显优势，能够提高了最优渗透路径的生成效率.

6 结束语

当前，以APT攻击为代表的渗透攻击给网络安全带来了巨大的威胁.最优渗透路径生成能够描述攻击者入侵目标网络的最大可能攻击过程，为攻击行为分析及防御策略部署提供了重要依据.然而，当前的研究一方面忽略了对未知攻击和内部攻击的描述，另一方面最优渗透路径生成效率较低.针对此问题，本文提出一种智能高效的最优渗透路径生成方法.利用分层结构的TLTPG，高效灵活描述了渗透路径.借助于知识图谱思想，构建主机资源知识图谱，通过智能推理高效得到下层HTPG，进而设计智能化的NG算法，得到上层NTPG.最后依据TLTPG模型，设计任意2个主机间的最优渗透路径生成算法.实验结果表明：该方法能够描述未知攻击和内部攻击，且可提高最优渗透路径生成效率.未来的工作包括算法的并行实现及利用TLTPG进行网络防御策略部署.

[1]National Internet Emergency Center. 2017 Annual Report of Chinese Internet Security[M]. Beijing: Post & Telecom Press, 2018: 39-144 (in Chinese)(国家计算机网络应急技术处理协调中心. 2017年中国互联网网络安全报告[M]. 北京: 人民邮电出版社, 2018: 39-144)

[2]Nourian A, Madnick S. A systems theoretic approach to the security threats in cyber physical systems applied to STUXNET[J]. IEEE Transactions on Dependable and Secure Computing, 2018, 15(1): 2-13

[3]Mu

oz-González L, Sgandurra D, Paudice A, et al. Efficient attack graph analysis through approximate inference [J] ACM Transactions on Privacy and Security, 2017, 20(3): 10:1-10:30

[4]Wang Shuo, Tang Guangming, Kou Guang, et al. Attack path prediction method based on causal knowledge net[J]. Journal on Communications, 2016, 37(10): 188-198 (in Chinese)(王硕, 汤光明, 寇广, 等. 基于因果知识网络的攻击路径预测方法[J]. 通信学报, 2016, 37(10): 188-198)

[5]Wang Shuo, Tang Guangming, Wang Jianhua, et al. Attack scenario construction method based on causal knowledge net[J]. Journal of Computer Research and Development, 2018, 55(12): 2620-2636 (in Chinese)(王硕, 汤光明, 王建华, 等. 基于因果知识网络的攻击场景构建方法[J]. 计算机研究与发展, 2018, 55(12): 2620-2636)

[6]Zangeneh V, Shajari M. A cost-sensitive move selection strategy for moving target defense[J]. Computers & Security, 2018, 75(4): 72-91

[7]Phillips C, Swiler L P. A graph-based system for network vulnerability analysis[C] //Proc of Workshop on New Security Paradigms. New York: ACM, 1998: 71-79

[8]Jajodia S, Noel S. Topological vulnerability analysis: A powerful new approach for network attack prevention, detection, and response[G] //Algorithms, Architectures and Information Systems Security. Singapore: World Scientific, 2008: 285-305

[9]Ning Peng, Cui Yun, Douglas S R, et al. Techniques and tools for analyzing intrusion alerts[J]. ACM Transcations on Information and System Security, 2004, 7(2): 274-318

[10]Ammann P, Wijesekera D, Kaushik S. Scalable graph-based network vulnerability analysis[C] //Proc of the 9th ACM Conf on Computer and Communications Security. New York: ACM, 2002: 217-224

[11]Ou X, Rajagopalan S R, Sakthivelmurugan S. An empirical approach to modeling uncertainty in intrusion analysis[C] //Proc of Computer Security Applications Conf. Piscataway, NJ: IEEE, 2009: 494-503

[12]Dawkins J, Hale J. A systematic approach to multi-stage network attack analysis[C] //Proc of the 2nd IEEE Int Information Assurance Workshop. Piscataway, NJ: IEEE, 2004: 48-54

[13]Ma Junchun, Sun Jiyin, Wang Yongjun, et al. Study of attack graph construction based on distributed parallel processing[J]. Acta Armamentarii, 2012, 33(1): 109-115 (in Chinese)(马俊春, 孙继银, 王勇军, 等. 基于分布并行处理的攻击图构建方法研究[J]. 兵工学报, 2012, 33(1): 109-115)

[14]Man Daping, Zhang Bing, Zhou Yuan, et al. Depth-first method for attack graph generation[J]. Journal of Jilin University: Engineering and Technology Edition, 2009, 39(2): 446-452 (in Chinese)(苘大鹏, 张冰, 周渊, 等. 一种深度优先的攻击图生成方法[J]. 吉林大学学报: 工学版, 2009, 39(2): 446-452)

[15]Man Dapeng, Zhou Yuan, Yang Wu, et al. Method to generate attack graphs for assessing the overall security of networks[J]. Journal on Communications, 2009, 30(3): 1-5 (in Chinese)(苘大鹏, 周渊, 杨武等. 用于评估网络整体安全性的攻击图生成方法[J]. 通信学报, 2009, 30(3): 1-5)

[16]Ye Yun, Xu Xishan, Qi Zhichang, et al. Attack graph generation algorithm for large-scale network system[J]. Journal of Computer Research and Deelopment, 2013, 50(10): 2133-2139 (in Chinese)(叶云, 徐锡山, 齐治昌, 等. 大规模网络中攻击图自动构建算法研究[J]. 计算机研究与发展, 2013, 50(10): 2133-2139)

[17]Barrère M, Steiner R V, Mohsen, R, et al. Tracking the bad guys: An efficient forensic methodology to trace multi-step attacks using core attack graphs[C] //Proc of the 13th Int Conf on Network and Service Management. Piscataway, NJ: IEEE, 2017: 1-7

[18]Noel S, Jacobs M, Kalapa P. Multiple coordinated views for network attack graphs[C] //Proc of the 2nd Workshop on Visualization for Computer Security. Piscataway, NJ: IEEE, 2005: 99-106

[19]Su Tingting, Pan Xiaozhong, Xiao Haiyan. Research on attack graph based on attributes adjacncy matrix[J]. Journal of Electronics & Information Technology, 2012, 34(7): 1744-1747 (in Chinese)(苏婷婷, 潘晓中, 肖海燕, 等. 基于属性邻接矩阵的攻击图表示方法研究[J]. 电子与信息学报, 2012, 34(7): 1744-1747)

[20]Zhong Shangqin, Xu Guosheng, Yao Wenbin, et al. Network security analysis based on host-security-group[J]. Journal of Beijing University of Posts and Telecommunications, 2012, 35(1): 19-23 (in Chinese)(钟尚勤, 徐国胜, 姚文斌, 等. 基于主机安全组划分的网络安全性分析[J]. 北京邮电大学学报, 2012, 35(1): 19-23)

[21]Hong J, Kim D S. Harms: Hierarchical attack representa-tion models for network security analysis[C] //Proc of the 10th Australian Information Security Management Conf. Western, Australia: Research Online, 2012: 74-81

[22]Xie Anming, Cai Zhuhua, Tang Cong, et al. Evaluating network security with two-layer attack graphs[C] //Proc of Computer Security Applications Conf. Piscataway, NJ: IEEE, 2009

[23]Hong J B, Kim D S. Assessing the effectiveness of moving target defenses using security models[J]. IEEE Transactions on Dependable and Secure Computing, 2016, 13(2): 163-177

[24]Pokhrel N R, Tsokos C P. Cybersecurity: A stochastic predictive model to determine overall network security risk using Markovian process[J]. Journal of Information Security, 2017, 8(2): 91-105

[25]Wang Shuo, Tang Guangming, Kou Guang, et al. An attack graph generation method based on heuristic searching strategy[C] //Proc of the 2nd IEEE Int Conf on Computer and Communications. Piscataway, NJ: IEEE, 2016: 1180-1185

[26]Kerem K, Sivrikaya F. Distributed attack graph generation[J]. IEEE Transactions on Dependable & Secure Computing, 2016, 13(5): 519-532

[27]Liu Qiao, Li Yang, Duan Hong, et al. Knowledge graph construction techniques[J]. Journal of Computer Research and Development, 2016, 53(3): 582-600 (in Chinese)(刘峤, 李杨, 段宏, 等. 知识图谱构建技术综述[J]. 计算机研究与发展, 2016, 53(3): 582-600)

[28]Yang Yuji, Xu Bin, Hu Jiawei, et al. Accurate and efficient method for constructing domain knowledge graph[J]. Journal of Software, 2018, 29(10): 1-16 (in Chinese)(杨玉基, 许斌, 胡家威, 等. 一种准确高效的知识图谱构建方法[J]. 软件学报, 2018, 29(10): 1-16)

[29]Chen Xiaojun, Fang Binxing, Tan Qingfeng, et al. Inferring attack intent of malicious insider based on probabilistic attack graph model[J]. Chinese Journal of Computers, 2014, 37(1): 62-72 (in Chinese)(陈小军, 方滨兴, 谭庆丰, 等. 基于概率攻击图的内部攻击意图推断算法研究[J]. 计算机学报, 2014, 37(1): 62-72)