团树传播算法在贝叶斯网络攻击图中概率计算分析

顾士星

摘 要：攻击图模型中对属性节点的状态评估主要是通过计算该节点置信度进而分析节点的威胁状态。当前运用贝叶斯攻击图评估整体网络安全性，在计算贝叶斯攻击图先验概率以及结合入侵检测系统计算后验概率方面，存在属性节点增加，贝叶斯网的计算复杂度呈指数级增长的问题。针对计算复杂度问题，提出了一种将贝叶斯网络攻击图转化成团树的方法，降低了计算过程中的时间复杂度。实验结果表明，采用该方法使计算节点的置信度、时间复杂度得到一定程度降低。

关键词：贝叶斯网络；攻击图；团树传播；风险评估

DOIDOI：10.11907/rjdk.171323

中图分类号：TP309

文献标识码：A 文章编号：1672-7800（2017）007-0174-04

0 引言

云计算、虚拟化等技术的发展使人们可以便捷地、随需应变地从可配置资源共享池中获取计算、存储、网络等资源，在便利的同时也带来了网络规模越来越大、主机应用数量呈指数级增长等问题。网络攻击牵一发而动全身，网络管理人员需要实时了解网络的运行状态、服务器的安全性等。网络安全的态势预测可以帮助系统管理员更好地理解网络安全态势，为采取防护策略提供参考，有效降低网络安全风险。本文使用基于攻击图（Attack Graph）模型的方法评估网络安全态势，构建贝叶斯网络攻击图（Bayesian Attack Graph），推理方法采用团树（Clique Tree）方法。团树传播算法可应用在局域网中每个机器的威胁指数分析等方面，对相应主机采取升级系统、安装补丁等防护措施。

1 相关工作

攻击图技术研究方向主要包括：目标模型构建、攻击图构建以及攻击图分析。在目标模型构建方面，从目标网络和攻击者建模两个角度来构建目标模型， Sheyne[1]在前人的基础上深入分析后，提出了经典的五元组来描述目标网络。Ou等[1-2]提出一种使用逻辑推理分析网络的脆弱性，并基于该方法提供了生成攻击图的工具（Multi-host， multistage vulnerability analysis， MulVAL），为攻击图分析提供了基础。Xie等[3]使用贝叶斯网络对攻击发生的不确定性进行建模，但是没有引入攻击事件的后验概率。在攻击图分析方面，Homer等[4]提出借助漏洞的指标量化网络整体安全性。张瑜等[5]通过使用危险理论的APT多步攻击实时响应模型，解决了不依据变量实时改变攻击图模型的问题。高妮等[6]结合入侵检测系统检测到的实时攻击事件，运用贝叶斯推理方法对单步攻击行为的后验概率进行动态更新，实现对目标网络整体安全性评估。

上述攻击图分析方法，能够很完整地表示出所有的攻击路径，但是无法定量描述某个节点被攻击者获得的概率以及多个攻击之间的因果关系等。基于贝叶斯网络攻击图的方法在进行概率推理时无法解决大规模网络中后验概率计算的NP问题。本文使用团树传播算法对贝叶斯网络攻击进行精确推断，能够很好地改善后验概率计算存在的问题。

2 贝叶斯网络攻击图

大部分攻击都是利用一系列脆弱性漏洞的组合来攻破系统。攻击图是一种用于建立系统脆弱信息和攻击者用来获得一定目的的所有可能攻击序列的一般化表示方法。使用攻击图可以发现潜在的脆弱性信息进而评估网络的安全性，通过分析脆弱性之间的依赖关系和内部网络配置来分析多个有序原子攻击组合，描述网络系统中可能存在的攻擊路径。贝叶斯网络攻击图[7]可以解决不确定性问题，如攻击之间相互的因果关系以及被攻击利用成功的概率等，而攻击图只能表示存在攻击却无法描述节点的威胁程度。

贝叶斯网络攻击图模型主要描述了资源属性状态、攻击行为及相互因果关系。资源属性、原子攻击和局部条件概率定义如下：

定义1（资源属性）：属性描述一个资源（S）被攻击者获取的状态，其中状态的取值符合伯努利随机二值变量。

资源属性状态取值为S=0或者S=1。其中1表示资源被攻击者占据，Pr（S）表示资源状态为1的概率，相反的0表示资源未被占据，Pr（S）表示资源状态为0的概率。

定义2（原子攻击a）：定义原子攻击a：Spre⊕Spost→[0，1]，其中，Spre，Spost∈S且满足以下条件：①Spre≠Spost；②给定Spre = 1且Spost=1，状态从Spre成功加入Spost的概率P（Spre，Spost）>0；

③不存在S1，S2，…，Sj∈S-{Spre，Spost}，满足P（Spre，S1）>0，P（S1，S2）>0，…，P（Sj-1，Sj）>0且P（Sj，Spost）>0。

定义3（贝叶斯网络攻击图）：贝叶斯网络攻击图定义为一个有向无环图BAG=（S，τ，A，ε，Lc），其中：①S=Ninternl∪Nexternal∪Nterminal，Ninternal为攻击图的内部节点，Nexternal表示攻击图的外部节点（远程攻击者），Nterminal表示攻击图的目标节点；②τS×S，其中，（Spre，Spost）∈τ且Spre⊕Spost∈A表示两个资源间可达，即存在攻击路径。定义状态节点Si的父节点为Pa[Si]={Sj∈S|（Sj，Si）∈τ}；③A={ai|i=1，…，n}表示攻击图中存在原子攻击，ai=0或1分别表示原子攻击未发生或已发生；④ε表示状态节点与其父节点之间的关系，分解为一个二元组，dj∈{AND，OR}。dj=AND表示一次原子攻击达到状态Sj需满足其所有父节点状态全部为1，即Sj=1→Si∈Pa[Sj]，Si=1。dj=OR表示一次原子攻击到达状态Sj满足其父节点中存在一个节点的状态为1，即Sj=1→Si∈Pa[Sj]，Si=1；⑤Lc表示一组条件独立的率分布函数，每一个资源属性Sj∈Ninternal∪Nterminal都有一个局部条件概率分布（Local Conditional Probability Distribution，LCPD）。

定义4 （LCPD函数）：假设BAG=（S，τ，A，ε，Lc）是一个攻击图，同时Sj∈Ninternal∪Nterminal，即资源属性Sj属于攻击图内节点或者攻击者占据的节点。假设vi是与原子攻击Si⊕Sj相关的漏洞被成功利用的概率。资源Sj的局部条件概率取决于该节点与所有父节点之间的ε关系。

当dj=AND时：Pr（Sj|Pa[Sj]）=0，Pr（∩Si=1vi）， Si∈Pa[Sj]|Si=0其它（1）

当dj=OR时：

2.1 漏洞利用成功率计算

每一个节点的LCPD需要安全管理员根据攻击过程中每个漏洞的利用成功率确定。漏洞的利用成功率与每个漏洞被利用的难易程度有关。本文采用美国通用标准与技术研究院提供的通用CVSS[8] （ Common Vulnerability Scoring System）评估漏洞利用成功率。

CVSS评分如表1所示，由0～10范围的数字来度量，其中每个漏洞由base、temporal和environmental属性组成，base属性跟漏洞利用成功概率有关。

漏洞利用成功概率可从CVSS的子项exploitability计算获得，计算公式为Pr（vi）=2×AV×AC×Au。

2.2 构建贝叶斯网络攻击图

本文研究关注点主要集中在贝叶斯网络攻击图分析，贝叶斯网络攻击图构建主要借助于Ou等提出的MulVAL工具生成攻击图方法，具体步骤如下：

（1）基础信息采集。局域网中资产信息、网络配置以及防火墙配置等信息；基于OVAL扫描器对网络中主机的漏洞扫描，利用CVSS评估系统对漏洞利用成功率进行评估，并生成漏洞利用成功率P。

（2）攻击图模型建立。利用MulVAL工具根据采集的信息生成攻击图。

（3）贝叶斯网络攻击图模型构建。贝叶斯网络攻击图构建主要依赖MulVAL生成的攻击图以及漏洞利用成功概率来生成网络结构模型以及LCPD函数的计算，生成贝叶斯模型算法如算法1所示：

算法1 BAG_gengeration（AG，Pstart，P）输入：攻击图AG=（S，τ，a，ε）；Pstart表示远程攻击者初始攻击能力，即S0的取值；P表示漏洞利用成功率。

输出：贝叶斯网络攻击图BAG=（S，τ，A，ε，Lc）。初始化攻击图BAG；复制攻击图AG的资源属性节点、边、原子攻击每条关系至BAG的S，τ，A，ε；for （each node Sj in BAG）； if（ j = 1 ）； Lc1（ S1 = True ） = Pstart； Lc1（ S1 = False ） = 1-Pstart； else； for（each edge τj in BAG）； if（ d in εi = AND ）；使用公式（1）计算LCPD； else； 使用公式（2）计算LCPD； endfor（08）；endfor（03）

3 团树传播算法

在给定一个贝叶斯网络模型的情况下，根据已知条件，利用条件概率计算出感兴趣节点发生的概率。使用贝叶斯网络，实现根据网络中节点已存在的值推断其它节点的概率值。

贝叶斯网络推理[9]有3种方式：①因果推理（Causal Inference）：从原因出发，根据一定的原因，求出在该原因下某个或多个节点结果发生的概率；②诊断推理（Diagnostic Inference）：由結果推出原因，根据产生的结果，计算条件概率的后验概率即为导致该结果发生的原因；③混合推理（Mixed Inference）：既包括因果推理又包括诊断推理。

贝叶斯网络推理算法分为精确推理算法和近似推理算法。团树传播算法首先将贝叶斯图转换成一个团树[10]，然后通过信息传递将信息依次传遍团树的每个节点，最终使团树满足全局一致性。

3.1 团树构造

团树构造包括构造端正图、三角化以及构造团树的过程。端正图的构造主要涉及对贝叶斯网络模型中具有相同孩子的父节点用无向边连接起来，并将有向边转化为无向边。贝叶斯网络攻击图构造端正图见图1。

三角化过程本质上就是对顶点按照以下顺序进行：①预消除顶点的邻居顶点节点联接起来；②删除该顶点，并添加边；③删除的顶点满足添加的边最少的原则。端正图的消元顺序如表2所示。

结果形成的团树结构如图2所示。

3.2 团树传播推理算法

团树传播推理算法先将贝叶斯网络转换为一种二次结构，通过对二次结构的推理得到贝叶斯网络推理的精确结果。SS=（CT，PP），其中：CT=（C，S）为团树，C为贝叶斯网络中的团集，S为CT中的边集；PP为与团和边相关的概率势（Probability Potentials），可从每个团中的变量概率分布经计算得到。在SS上计算联合概率是通过计算CT上团和边的PP实现的。团树传播推理算法的目的是计算每一个非证据变量的后验概率分布。团树传播算法流程如下：算法2 团树传播算法Clique（G，Gc，An）输入：G贝叶斯攻击图；Gc表示一个覆盖G的团树；An表示原子攻击是否发生的取值。输出：每一个非攻击变量S的后验概率P{S/A1=a1，A2=a2，…，An=an}

利用G将Gc初始化

在Gc的函数中，将证据变量集合中的An设置为其取值

在Gc中任选一个团节点Cp作为枢纽

for（每一个与Cp相邻的节点C）

调用CollectMessage（Cp，C）

for（每一个与Cp相邻的节点C）

调用DistributeMessage（Cp，C）

for（G中每一个非证据变量X） a：选择一个包含X的团Cx； b：把初始化时和信息传递过程与储存在Cx处的函数相乘，得到一个C'x的函数h（C'x），这里C'x=CxE； c：计算∑C'x＼＼{X}h（C'x）∑C'xh（C'x）即为证据变量X的后验概率。endprint

上述算法中，CollectMessage（Cp，C）表示信息的分发，即将Cp节点所含有的信息向团树中所有的节点依次传播过去。DistributeMessage（Cp，C）表示信息的收集，即将团树除Cp之外的团节点信息收集到Cp的团节点。其中，相邻节点的信息传递算法sendMessage（C，C'）描述如下：输入：团树中的两个相邻节点C，C'。作用：计算并存储从C到C'的信息。设C'1，C'2，…，C'k为除C以外的其它邻居节点；

对i=1，2，…，k，gi为在节点C中存储的C'i到C的信息；设f1，f1，…，fl为初始化时存储在C处的函数，且设Z=CC'∪E ；计算如下函数：ψ←∑Z∏li=1fi∏kj=1gj；ψ即为C到C'的信息，将此信息存储在节点C中，以备以后信息传递时使用。

4 实验分析

给出一个网络拓扑结构如图3所示，防火墙规则设置远程攻击者通过端口能够访问主机的方式，如图3所示，防火墙后主要包括Web服务器、文件服务器以及数据库服务器等。

漏洞信息获取采用Oval漏洞扫描器扫描实验环境中的主机，结合网络拓扑等信息作为Mulval工具的输入信息，生成通用的攻击图模型。

使用算法1来生成该节中定义的部分贝叶斯网络攻击图模型如图4所示。节点S1、S2的概率表示攻击者初始的攻击能力，定义为P（S1）=0.6、P（S2）= 0.8，此处略去每个节点的LCPD表，贝叶斯网络先验概率计算结果如表3所示。

结合入侵检测系统的入侵报警数据以及漏洞利用成功率等，检测到发生A3攻击事件，根据算法2使用团树传播算法计算贝叶斯网络算法后验概率，计算结果如表3所示。

通过在防火墙后不同主机中安装多个不同应用来模拟资源节点变化，多次使用Oval漏洞扫描器对系统扫描，利用文中所述方法构建贝叶斯攻击图以及团树攻击图。通过多次试验计算分析得到使用贝叶斯算法以及团树传播算法的时间对比如图5所示，可以看出使用团树的方法来计算贝叶斯的后验概率，在算法时间复杂度上得到了一定程度的降低。

5 结语

使用基于团树传播推理分析的方法对贝叶斯网络攻击图进行推理分析，能够在一定程度上降低贝叶斯攻击图推理的时间复杂度，实验结果验证了这个方法的可行性。能够形式化描述一个资源节点被攻击者攻击成功的概率，以及获得该资源节点后下一个最具威胁性的资源节点，有利于网络管理人员采取相应措施，如修复官方给出的补丁、关闭不需开启的网络服务等，进一步提高信息系统的安全性。本文提出的推理方法在一定程度上可以减少计算贝叶斯攻击图后验概率的时间。消元顺序的选择对概率计算的时间复杂度有一定影响，本文采取随机选择方式进行消元顺序选择。未来将研究最优化的消元顺序以进一步降低概率计算时间。利用攻击图来寻找整个信息系统的脆弱点对保护系统安全、维护个人信息隐私等有着非常重要的意义。

参考文献：

[1]SHEYNER O， WING J. Tools for generating and analyzing attack graphs[J]. Lecture Notes in Computer Science， 2003.

[2]OU X. A logic-programming approach to network security analysis[EB/OL]. http：//www.cs.princeton.edu/research/techreps/TR-735-05.

[3]XIE P， LI J H， OU X， et al. Using Bayesian networks for cyber security analysis[C]. IEEE/IFIP International Conference on Dependable Systems & Networks， Chicago， 2010.

[4]HOMER J， ZHANG S， OU X， et al. Aggregating vulnerability metrics in enterprise networks using attack graphs[J]. Journal of Computer Security， 2013，21（4）：561-597.

[5]张瑜， QINGZHONG LIU， 李涛， 等. 基于危险理论的APT攻击实时响应模型[J]. 四川大学学报：工程科学版， 2015，47（4）：83-90.

[6]高妮， 高岭， 贺毅岳， 等. 基于贝叶斯攻击图的动态安全风险评估模型[J]. 四川大学学报：工程科学版， 2016，48（1）：111-118.

[7]POOLSAPPASIT N，DEWRI R， RAY I. Dynamic security risk management using bayesian attack graphs[J]. IEEE Transactions on Dependable & Secure Computing， 2011，9（1）：61-74.

[8]SCHIFFMAN M.Common vulnerability scoring system（CVSS）[EB/OL].[2016-09-07].http：//www.first.org/cvss/user-guide.

[9]TARONI F. Bayesian networks for probabilistic inference and decision analysis in forensic science[M]. Wiley， 2014.

[10]李志瑤， 宗芳， 张屹山. 贝叶斯网络推理分析的团树传播算法——以停车行为分析为例[J]. 长春大学学报， 2012（5）：505-509.endprint