董博1,王雪2
(1. 辽宁大学 计算中心,辽宁 沈阳 110036;2. 辽宁大学 信息化中心,辽宁 沈阳 110036)
摘要:针对网络安全威胁问题,将人工智能理论和相关技术与网络安全态势评估相融合,提出一种以细化变量进行分组的贝叶斯网络作为基础研究的网络安全态势评估方法。该算法可以有效减少变量数量,缩短产生贝叶斯网络的程序运行时间,并通过相关实验验证了有效地减少变量数量对最终的结果并没有产生过多影响。用本算法对大量网络实际运行数据进行测试,结果表明该方法能够很好地区分不同的网络安全威胁,从而能够有效评估网络安全态势。
关键词:贝叶斯网络;网络安全;态势评估;结构学习
0引言
网络安全态势感知就是把所收集的与网络安全相关的要素进行融合,然后按照一定的方法对这些要素进行分析和理解,进而判断当前网络的安全态势并预测未来的安全态势。
1网络安全态势评估方法
网络安全态势评估是网络安全态势感知的重要环节,国内外学者从不同的角度出发,对网络安全态势评估做了大量科学研究工作。
在国内,韦勇等[1]证明了基于多源融合网络安全态势评估比基于单源网络安全态势评估更加准确有效。刘念等[2]提出一种基于免疫的网络安全态势感知方法。
在国外,Mohsen Naderpour等[3]提出基于SA支持系统的GDTA方法,这种方法能帮助管理人员找出异常情况。Jason shifnet 等开发了Spinning Cube of Potential Doom 系统, 极大地提高了网络安全态势评估能力[4]。
2贝叶斯网络
贝叶斯网络是描述数据变量之间依赖关系的图形模型 ,其描述如下:网络结构S=(G,Θ)是一个有向图 ,其中,每一个节点代表一个数据变量,G=(X,E) 是没有环路没有顶点的图,X={X1,...,Xn}。Θ={P(Xi|Pa(Xi))}为其中Xi节点在其父节点的条件概率集合。
用P(Xi)代表节点Xi的条件概率密度,Pa(Xi)表示其父节点集合,由贝叶斯推理公式有:
P(Xi)=P(Xi|Pa(Xi))(1)
根据概率链规则,由n个变量决定的联合贝叶斯概率为:
P(x1,x2,...,xn)=∏ni=1p(xi|Pa(xi))(2)
在S中不存在任何有向环, 称为有向无环图(Directed Acyclic graph , DAG) 。参考文献[5]中描述了有向无环图的递推公式:
r(n)=∑ni=1(-1)i+1n
i2i(n-1)r(n-i)=n2O(π)(3)
其中,r(1)=1, r(2)=3, r(3)=25, r(5)=29 281, r(10)=4.2×1018,这意味着,一旦节点数大于7,对所有节点在有效时间内执行一次完全遍历是不可能的。
3聚类算法理论框架和研究方法
由于在构建贝叶斯网络的过程中,网络的结构复杂性使得变量的数目过多,造成表达式超指数的增长。为了解决这个问题,本文采用一种新的聚类算法,采用细分变量作为子集(或群组),通过单独地学习每一个子集的结构,由这些子集的结构最终组装成最终的结构。
3.1理论背景
以下用到的Robinson 公式[5]表明有向无环图中变量数量。其中,n表示变量的数量,r(1)=1。
r(n)=∑ni=1(-1)i+12i(n-i)n
ir(n-i)(4)
r(n)>∑kl=1r(Jl+1)(5)
其中,J1+J2+…+Jk=n-1,Jl+1 定理1 对于n≥2,有: r(n)≥2n-2nr(n-1) r(n)≥2(n-1-J)(n+J-2)2n(n-1)...(J+2)×r(J+1)(6) 其中,0≦J≦n-1。 当n=2时,r(2)=3≧2。当n>2时,参考文献[2]中已经证明定理成立。 定理2 r(n)∑kl=1r(Jl+1)≥p(n,Jk-Jk+,k)1(7) 证明: 由定理1中公式(6): r(n)≥2(n-1-Jl)(n+Jl-2)2n(n-1)...(Jl+2)×r(Jl+1) l=1,...,k 所以: ∑kl=1r(n)≥2(n-1-Jl)(n+Jl-2)2n(n-1)...(Jl+2)r(Jl+1)(8) k×r(n)≥∑kl=12(n-1-(Jk+))(n+(Jk-)-2)2n(n-1)...(Jk++2)r(Jl+1)(9) 由于上式中,2(n-1-(Jk+))(n+(Jk--2)2n(n-1)...(Jk++2)是常数,与l无关,即: k×r(n)≥2(n-1-(Jk+))(n+(Jk-)-2)2n(n-1)...(Jk++2)∑kl=1r(Jl+1)(10) 因此: r(n)∑kl=1r(Jl+1)≥2(n-1-(Jk+))(n+(Jk-)-2)2n(n-1)...(Jk++2)k(11) 即: r(n)∑kl=1r(Jl+1)≥p(n,Jk-Jk+,k)1(12) 所以: r(n)>∑kl=1r(Jl+1)(13) 例如,存在20个变量分成四个子集,子集1中包含5个变量,子集2中包含3个变量,子集3中包含6个变量,子集4中包含6个变量。则有: r(n)=658.114×∑kl=1r(Jl+1)∑kl=1r(Jl+1)(14) 表明r(n)远大于∑kl=1r(Jl+1)。 3.2结构学习过程 贝叶斯网络学习过程的主要目的是在相应变量间进行推理,得出有效的因果关系,从而形成一个有向无环图。对所有的变量(包括兴趣变量)进行结构学习。最终的结构学习过程如算法1。 算法1贝叶斯分组学习优化算法 定义:n:分组数量 λi:分组的索引 Vij:在λi分组下的变量j索引 P(Vij): Vij的父集 N: 类的变量节点 STi:分组i的变量结构 Oi:分组变量排序 Nλi:属于λi分组内的变量数量 Vλi: i分组的变量集 算法过程如下: 1:Begin 2:For each i<=n Do Oi←MWST(N, Vλi:) 3:End for 5:For each i<=n Do STi←K2(Oi, Vλi:) 6:End For 7:For each 2<=i<=n do Vλi←VλiUVλi\\{N} 8:For each 1<= j<= Nλi do 9:从STi中开始,添加到ST1中并保留从 10:Vij和P(Vij)之间的弧 11:End For 12: End For 很多学者提出了多种关于贝叶斯网络的结构学习算法,比如MWST算法、TPDA(Three Phase Dependency Analysis)算法、K2算法、ACOB (Ant Colony OptimizationB algorithm)等。本文选用K2算法进行对比分析的主要原因是K2算法的计算时间短,算法复杂度低,稳定度高。为了解决初始变量有序化问题,采用了MWST算法。MWST算法对数据集大小的变化不太敏感,并能产生初始化序列,而且其产生的图与之前的图差别不大。因此,采用MWST算法既能满足初始化序列的要求又能非常准确地接近原始数据,可以成为K2算法的有效输入。 4实验过程与结果 选用了BNT toolbox工具包和Matlab2014b实验平台,实现MWST算法和K2算法的结构学习过程。 运行环境为:Inter Core2 2.8GHz处理器,4 GB内存,Win7 64位操作系统,系统平均CPU利用率为38%,内存的平均使用率为17%。 数据来源采用美国林肯实验室的数据KDDCUP,其包含连续属性及离散属性等不同属性值(如攻击持续时间、网络协议类型等),并标有其所属的类型(如正常或具体的攻击类型) 。所有攻击主要分为以下4大类: (1)DoS(Denial of Service Attacks ):拒绝服务。 (2)UToR(User to Root Attacks):试图获取根用户权限。 (3)RToL(Remote to Local User Attacks):入侵者试图利用系统的缺陷绕过防火墙。 (4)Probe(Probe in network):端口扫描。 4.1Kmeans算法数据预处理 设定聚类范围为 2~10,采用层次聚类算法和自举技术优化的K2算法进行聚类,得到每个因素的聚类准则值,如图1所示。找到最佳聚类数和聚类中心可以使每个属性更好地反映数据特性,避免由专家指定而造图1各属性聚类准则值 成的主观影响。同理适用于其他影响因素,得到其最佳聚类数和聚类中心如表1所示。 4.2实验具体过程 (1)选取10%的数据集(共 494 019 条连接记录)作为样本训练数据集。之后获取来自于本校的防火墙日志,使用20150104 00:00:00 到20150107 23:59:59之间,合计四天共96 h的数据,共875个报警事件作为测试集。 (2)对训练集中连续性属性进行离散化处理,确保其中属性数据值在 100 个左右,并在此基础上进行分组贝叶斯算法的分类试验。 (3)分别用本文提出的算法和经典的K2算法分别获取100个变量和1 024个变量。 (4)对数据进行归类,按照相关试验类型的不同预归类成2 类或5个主要类。 (5)分两种情况对算法进行比较: ①数据记录只分类成正常(Normal)或异常(Unnormal)两类,即将所有具体类型的攻击都作为异常类。 ②数据记录分类成 5大类 (Normal、DoS、UToR、RToL、Probe),各具体攻击类型分别归类到这5类中。 4.3实验结果和分析 在第一阶段实验过程中,分别用K2算法和本文设计的算法对不同的数据集进行运算。可以看出,与经典的K2算法相比,本文算法运行时间得到了有效的缩短。在第二阶段实验中,验证了分组变量对实验结果的影响微乎其微,如表2所示。其中训练集数据分别含有100个变量和1 024个变量。 对于算法有效性的评价标准采用分类准确率来衡量。采取两种情形进行试验,第一种情形将数据的类型分成两种如表3所示,可以看出本文算法分类准确度明显优于K2算法。第二种情形将数据分成5类,结果如图2和图3表3分类准确率(%)类型训练集测试集本文。 从图2和图3可以看出,本文所提算法在准确率方面也优于K2算法。但无论是本文方法还是传统的K2算法,在UToR与RToL训练样本的分类准确度上,还都达不到较好的效果,主要原因是这两种训练样本占整体样本比例相对较少。当训练样本的数量较多时,分类的准确率会得到较大提升。 5结束语 首先,本文在数学上证明了通过对相关变量进行分组并形成相关的聚类可以有效地减少贝叶斯网络的规模。其次,选取了Kmeans方法优化了聚类过程。最后,通过实验证明本文方法可以大量减少网络态势分析中的变量数量,并且丢失的数据在实际评估过程中不影响推理过程所产生的贝叶斯网络,同时节省了大量的程序执行时间。 参考文献 [1] 韦勇,连一峰,冯登国. 基于信息融合的网络安全态势评估模型[J].计算机研究与发展, 2009, 46(3):353362. [2] 刘念,刘孙俊,刘勇,等.一种基于免疫的网络安全态势感知方法[J]. 计算机科学, 2010,37(1):126129.[3] NADERPOUR M, LU J, ZHANG G. An intelligent situation awareness support system for safetycritical environments[J]. Decision Support Systems, 2014,59(1):325340. [4] STEPHEN L.The spinning cube of potential doom[J]. Communications ACM,2004, 47(6): 2526. [5] ROBINSON R W. Counting unlabeled acyclic digraphs[C].In: Lecture Notes in Mathematics, Combinatorial Mathematics, 1977:2843.