面向网络攻击建模的分布式过程挖掘与图分割方法

刘贞宇，陈羽中，郭 昆，张毓东

(福州大学 数学与计算机科学学院，福州 350116)

(福州大学 福建省网络计算与智能信息处理重点实验室，福州 350116)E-mail：yzchen@fzu.edu.cn

1 引 言

在现今网络安全形势下，政府和企业组织为应对入侵者，通常需要部署防火墙、入侵检测与防御系统等多种网络安全防护设备，以保护信息资产安全.这些网络安全防护设备在运行过程中会产生大量信息等级较低的网络安全警报日志[1]，而网络攻击建模技术旨在通过对网络安全警报日志进行融合及关联关系分析，生成网络攻击图，发现网络攻击的特点和规律，提高应对各种突发网络攻击事件的能力.

现有的网络攻击建模算法，主要基于警报关联或聚类两类方法.警报关联方法的主要思想是将设备的日志记录聚合，形成信息层级高的元警报，再通过相似度计算等方式将元警报互相关联，构建攻击模型.早期基于警报关联的网络攻击建模算法依赖人工输入先验数据，当日志规模增大时，难以生成攻击模型.聚类算法则通过聚类规则，自动关联警报并保存在相应的数据结构中(如树结构或图结构)，无需人工输入先验数据，但存在生成的网络攻击图完备性不足的问题[2].近年的一些研究工作将过程挖掘方法应用到网络攻击建模中.过程挖掘方法依据日志中记录的实例执行信息构建工作流模型，主要用于过程分析.过程挖掘方法能够有效挖掘网络安全警报日志中包含的具有规律性的攻击模式.然而现有的研究工作为了保证攻击模型的完备性，所建立的网络攻击图包含大量结点和边，虽然能够覆盖网络入侵者的攻击行为，但是过于复杂的网络攻击图几乎无法进行人工分析[3，4]，而人工分析是目前抵御网络攻击的关键步骤.虽然有一些研究工作会进行模型简化或分割，但是存在效率低下、丢失攻击图部分信息的问题.此外，在过程挖掘领域，针对海量数据处理的相关研究比较少，现有研究主要对原始数据进行合并重复警报、对警报赋予优先级等方法减少计算压力[5，6]，因此有必要引入分布式架构提高对大规模网络安全日志的处理能力[7，8].针对现有网络攻击建模方法存在的问题，本文提出一种基于启发式过程挖掘与图分割的网络攻击建模方法，主要工作如下：

1)提出了一种基于过程挖掘的攻击图生成方法(HPMA，Heuristic ProcessMining for AttackModeling)，基于过程挖掘方法对网络安全警报日志进行融合，分析网络安全警报日志间的顺序依赖关系和短循环关系，检测每一个网络攻击行为的前驱和后继行为、各个事件中隐含的XOR/AND关系，从而获取各个攻击行为间的逻辑关系，生成网络攻击图.该方法能够有效挖掘网络安全警报日志的关联关系，反映入侵者的攻击行为和攻击策略.

2)提出了一种针对复杂网络攻击图的攻击图分割方法(HGSA，Heuristic GraphSegmentation for AttackModeling).该方法首先寻找网络攻击图的分支结点，从分支结点出发构造网络攻击子图，再根据所分割的网络攻击图的结构，对生成的网络攻击子图进行补全.该方法在保留网络攻击图的结构信息的同时，降低了网络攻击图的复杂度.

3)在上述方法基础上，提出了基于MapReduce的分布式攻击图生成方法(HPMAoMR，HPMAoverMapReduce)以及基于Spark GraphX图计算模型的分布式攻击图分割方法(HGSAoSG，HGSA over Spark GraphX)，能够有效解决大规模网络安全警报日志的融合分析问题.

2 相关工作

2.1 网络攻击图生成

网络攻击建模旨在挖掘网络安全警报日志间的关联关系，并生成网络攻击图.现有的研究工作主要基于警报关联、聚类以及过程挖掘等方法[9].

警报关联是网络攻击建模的核心方法之一，旨在关联构成攻击步骤的低级别网络安全日志警报，融合生成高级别的网络安全警报(又称元警报或超警报).Lee[10]等人提出了一种基于警报特征相似性的警报关联算法.该方法过滤并聚合冗余警报，通过警报相似度确定是否将两个警报关联到元警报.Ning[11]提出了一种基于攻击行为的前因和后果分析的警报关联算法.该算法需要人工定义几种类型攻击的前因和后果，无法适用于大规模的网络场景.上述研究工作仅实现网络安全警报日志的关联，并未对关联结果做进一步分析与抽象.

近年来，一些研究工作从关联的网络安全警报日志中提取入侵者的攻击模式，从而构建网络攻击图.Ahmadinejad等[12]提出一种二级混合模型的网络攻击建模算法，首先基于前因和后果的方法关联警报，之后使用相似度聚类将未关联的剩余警报关联起来.Sadoddin等[13]通过FSP-Growth挖掘警报的频繁模式来关联警报.Lagzian等[14，15]则根据IP和攻击方式将警报聚合到图中，然后应用Bit-AssocRule算法挖掘图中的频繁模式，实现警报间的关联.上述方法能够提取入侵者的攻击模式，但是融合层级较低，难以抽象出信息层级更高的网络攻击模型.

聚类是网络攻击建模广泛采用的另一类方法.Spathoulas等[15]利用攻击警报特征的相似性对警报进行聚类，建立攻击模型.Siraj等[16]采用基于PCA和期望最大化聚类算法对警报进行聚类，构建网络攻击图.Alvarenga等[17]采用自顶向下的层次聚类算法对警报进行聚类，得到网络攻击图.上述基于聚类的网络攻击建模算法能够提取入侵者的攻击模式，但难以全面描述网络攻击的全过程，且存在所生成的网络攻击图过于复杂的问题.

过程挖掘方法通过挖掘日志中的实例执行记录以构建工作流模型，能够在没有过程模式先验知识的情况下挖掘工作流.由于入侵者进行网络攻击的流程类似工作流，因此一些研究人员将过程挖掘方法应用于网络攻击建模.Weijters等[18]提出了一种启发式的过程挖掘方法，通过计算各种行为的顺序频次和逻辑规律，分析攻击行为之间的依赖关系和逻辑关系.Alvarenga等[9]则将日志按照日期和攻击目标分组，使用过程挖掘方法从网络安全警报日志中提取网络入侵者的攻击策略信息，建立网络攻击图.上述方法能够全面描绘网络攻击过程，但所生成的网络攻击图仍过于复杂.

2.2 图分割

为了能够完备描述安全日志中蕴含的攻击模式，现有的网络攻击建模方法得到的网络攻击图过于复杂.为了提高网络攻击图的可读性，需要利用图分割方法对网络攻击图进行处理.现有的图分割方法主要分为近似解算法和精确解算法两大类.近似解算法主要基于启发式算法，如线性规划、模拟退火算法、遗传算法、蚁群算法、粒子群算法、谱聚类算法、K-L算法等.现有的图分割算法主要用于复杂网络分析、VLSI电路设计、并行计算等研究领域.但对于基于有向图，前后结点联系紧密的攻击图分割上并不适用.本文则提出一种基于攻击图几何性质的分割算法，对攻击图分割有着良好的效果.

3 预备知识

过程挖掘技术能够在没有过程模式先验知识的情况下挖掘工作流.过程挖掘从依赖关系挖掘开始.设T为一次流程执行案例(Case)，A和B为该案例过程中的两个事件(Event)，又称实例.

定义1.依赖关系.在过程P中，如果每一个从事件Ai到结束事件的有向路径中都包含Aj，且Ai到Aj的路径上不存在其他事件，则Aj依赖于Ai.

定义2.依赖值(Dependency Score).依赖值表示A和B之间存在依赖关系的置信度，记为A⟹wB.设W为案例T上的日志，A,B∈T，事件B的记录在A之后，记为A>wB，则:

(1)

其中|A>wB|表示A>wB在日志W中的出现次数.A⟹wB在-1到1之间取值.若出现负值，则表示可能存在相反关系B⟹wA.A与B之间的依赖关系是否存在可以通过公式(1)计算其置信度.比如，事件A后发生了事件B在日志中出现了55次，A⟹wB=55/56=0.982，则基本能确信其A与B存在着依赖关系.若存在某个噪声数据，使得B>wA出现了一次，则根据公式(1)计算可得A⟹wB=54/57=0.947.几乎不影响置信度的计算结果.

在挖掘过程中，有可能出现同一个实例必须重复执行多次的情况.这种情况在流程图中称为短循环.较长的循环可以作为依赖关系用公式(1)有效挖掘.但是长度为1(如ABBBBBC)则需要通过公式(2)计算挖掘：

设W为事件T上的日志，A,B∈T，则：

(2)

其中|A>wA|为T中A>wA出现的次数.

除了依赖关系和短循环关系外，过程挖掘算法还需要挖掘事件中的逻辑关系，如XOR/AND关系.例如，设在日志w中，A之后可能执行B，也可能执行C，则B和C存在AND关系；若B和C不会同时执行，则B和C为XOR关系.挖掘这两种逻辑关系，需要在流程执行的过程中，通过A⟹wB∧C关系对其进行判断:

(3)

若B和C为AND关系，则B和C在案例中往往同时出现，以BC的形式存在，A⟹wB∧C的值会接近1.若其为XOR关系，则B和C几乎不会同时出现在同一个案例中，A⟹wB∧C的值接近0.通常，当A⟹wB∧C<0.1时即判断B和C为XOR关系[19].

4 网络攻击建模

4.1 算法框架

本文提出的网络攻击建模方法主要包括网络安全日志预处理、网络攻击图生成、网络攻击图分割三个步骤.

网络安全日志预处理：对原始网络安全日志进行数据清洗、格式转换等操作，去除噪声与冗余，对日志数据进行分组和聚合，转换为过程挖掘算法所需数据格式.

网络攻击图生成：使用启发式过程挖掘算法，将日志警报数据融合为入侵者的攻击模式数据，建立网络攻击图.

网络攻击图分割：通过图分割算法，在保留原网络攻击图的攻击步骤信息的同时，将复杂度高的网络攻击图分割成复杂度低，可读性强的网络攻击子图.

4.2 网络攻击图生成

使用启发式过程挖掘算法从日志中挖掘初始网络攻击图.启发式过程挖掘算法[19]通过引入频率计算解决了传统过程挖掘算法无法处理噪声数据的问题，在输入日志数量较大时有着优异的挖掘效果.由于网络攻击入侵者的攻击策略与工作流特征十分相似，因此可以将过程挖掘技术应用在攻击图建模方面[9].攻击图生成过程分为如下几个步骤：

首先，对原始IDS报警日志数据聚合.将警报日志按照攻击源IP和时间戳进行分组聚合.然后将其转换为启发式过程挖掘算法所需的XES日志形式作为输入数据.

然后，算法读取输入数据，通过攻击事件出现顺序频次计算依赖值，依赖值是判断攻击事件之间的依赖关系或者逻辑关系是否存在的指标.然后算法会构建一个依赖频率表，通过短循环计算公式计算出短循环关系.

随后，算法通过计算各个事件和依赖间的频率关系，计算挖掘出攻击事件之间的XOR/AND关系，完善攻击策略图中各个行为间的逻辑关系.补充相应的信息.最后输出网络攻击图.

4.3 网络攻击图分割

由网络安全管理人员对网络攻击情况进行人工分析是确保网络系统安全的重要手段[16].然而由于海量网络安全日志中包含了不同入侵者的大量行为记录，网络攻击图中表示入侵者行为的结点数目十分巨大，入侵行为间的先后依赖关系也十分复杂，使得网络攻击图中边的数量也十分庞大，导致网络攻击图过于复杂，不利于网络管理人员直观地分析当前的网络攻击状态.针对上述问题，本文提出了一种针对复杂网络攻击图的攻击图分割算法，将复杂的网络攻击图划分为多个能够直观反映入侵者攻击步骤的网络攻击子图，以方便网络安全管理员进行分析.

4.3.1 问题描述

网络攻击图G=(V,E)表示攻击行为与攻击行为之间关系，V表示结点集，代表着入侵者的攻击行为，E表示攻击图中的边集，代表入侵者攻击行为之间的逻辑关联关系，网络攻击图分割问题定义如下：

定义3.网络攻击图分割.网络攻击图分割.给定网络攻击图G，求G的一个网络攻击图分割P，P={G1,G2,…,Gn},其中Gi表示网络攻击图的某一个子图.

4.3.2 算法概述

攻击图分割的基本思想如下：首先对原始网络攻击图进行遍历，然后以分支为基准，将各个分支遍历到的结点和边保存为新的攻击图.因此对攻击图的分割不会影响原始攻击图结构.算法的主要步骤如下：

步骤1.计算待分割的网络攻击图G的复杂度，若G不是复杂网络攻击图，则输出G后结束；否则将G放入队列Qs中；

步骤2.遍历队列Qs，对队列中的每个待分割的网络攻击图，自顶向下寻找分支点Vs；

步骤3.遍历到分支点Vs，则以Vs作为分割的起始点，去除网络攻击图中的独立子图，然后将网络攻击图剩余部分中以Vs为起始点的有向边加入到队列Qe中；

步骤4.遍历队列Qe，对遍历到的有向边e使用深度优先算法遍历并生成e的后继子图，并将Vs标记为所生成的后继子图的起始点.对每个后继子图，计算其复杂度，如果不是复杂子图，则将后继子图加入队列Qoutput中，Qoutput用于存放分割得到的网络攻击子图；否则将其加入到存放待分割的网络攻击图的队列Qs中；

步骤5.判断队列Qs是否为空，若非空，回到步骤2；

步骤6.遍历Qoutput中的网络攻击子图，对其进行分支信息补全后输出，即为网络攻击图G分割所得的网络攻击子图.

4.3.3 网络攻击图复杂度判定

对网络攻击图进行分割的目的是降低其视觉上的复杂度，增加其可读性，但视觉上的复杂性难以直接衡量，因此需要定义网络攻击图复杂度的评估方法，用于判断一个网络攻击图是否需要进行分割或分割后的子图是否已经具有可读性，可以输出给网络管理员进行分析.本文攻击图分割方法所采用的网络子图复杂度判定规则如下：

(4)

其中|V|为攻击图G结点的个数.若网络攻击图的结点数满足|V|N2, 则网络攻击图G为复杂网络攻击图，需要进行子图分割；若网络攻击图的结点数满足N1<|V|

(5)

参数N1和N2根据文献[9]确定：N1=15，N2=31.

4.3.4 独立子图分割

定义4.后继子图.从网络攻击图G中的某个结点v经以v为起始结点的某条有向边e出发，遍历到的点与边所构成的流程图，为v的一个后继子图，记为Gsucc(v,e).

如图1(a)所示，实线部分为点v的一个后继子图.在网络攻击图G中，结点v表示入侵者的某个攻击行为，其后继子图则代表入侵者执行某个攻击行为后可能进行的后续攻击行为.

定义5.分支点.给定网络攻击图G中的某个结点v，若结点v的出度大于1，则v为网络攻击图G中某个入侵行为的分支点.

攻击流程的分支点代表攻击者在执行攻击计划的过程中，在执行完此攻击步骤后，存在多种不同的可执行攻击方案.图分割算法以分支点为基础分割攻击图，可以将不同的攻击方案分割成独立子图，使得管理员对攻击者的各个攻击方案有较为清晰的把控.算法自顶向下找到网络攻击图的分支点后，首先将易于分割的部分分离出来.

定义6.独立子图.给定v的一个后继子图，若该后继子图内的全部有向边e的端点属于后继子图或为v本身，则该后继子图是以结点v为起始点的独立子图.

如图1(b)所示，实线部分为结点v的一个独立子图，首先从攻击图中获取以v为起始点的有向边，然后从这些有向边开始遍历v的各个后继子图，并且判断遍历到的每一个子图是否为v的独立子图.如果遍历到的图是独立子图，则将该子图从原图中分割出来，作为一次分割结果入队待分割队列中，后续确认是否需要进一步分割.

图1 结点v的后继子图与独立子图

独立子图代表着这个子图内所有的攻击行为都是且仅是分支点代表的攻击行为的后续攻击方案.当网络管理员发现符合独立子图内的攻击顺序被执行，就可以立即确认入侵者之前的攻击行为.同时，由于独立子图只是分支点V的后继子图，因此不需要对分割出的独立子图进行补全，能够提高算法的计算效率.

4.3.5 剩余子图分割

将独立子图分离后，算法需对去除独立子图之后剩余的后继子图作进一步分割.算法选取从以分支点为起始点的有向边出发，依次遍历分支点的各个后继子图，并且生成子图.具体步骤如下：

步骤1.遍历队列Qe，对遍历到的有向边e，以有向边e为起始，使用广度优先遍历算法遍历e的后继结点和对应的有向边，并且标记遍历过的结点和边；

步骤2.对遍历到的每个结点，判断是否存在远距离环，若存在远距离环，则对其进行去除远距离环的操作，最后由遍历到的结点和边生成后继子图Ge.

以图2(a)的网络攻击图为例，结点v为分支点，对网络攻击图的分割过程如图2(b)-图2(d)所示.

图2 以v为起始点将后继图分割成三个子图

如图2(b)，首先从v为起始点的有向边e1出发以深度优先遍历后继子图.将遍历到的结点和边连同分支点Vs一起保存为一个新的子图G1.同理，分别从e2、e3出发遍历v的后继子图，并将结果保存为新的子图G2和G3，如图2(c)、图2(d)所示.

子图表示着入侵者某个攻击阶段的攻击策略.当网络管理员聚焦在某个攻击行为时，子图中的结点表示着在该攻击行为前后有可能出现的攻击行为.不属于相同子图的结点，其对应的攻击行为不会相互在前后出现，因此网络管理员可以集中在这个子图中研究当前攻击行为的依赖关系和逻辑关系.

4.3.6 去除远距离环

定义7.远距离环.自结点v出发，经过一个或多个结点可返回结点v.则称所经过结点构成的路径为v的一个远距离环.

远距离环是过程挖掘算法中由于存在远距离依赖因而产生的环.图3(a)显示了图2(b)中网络攻击子图G1的部分子图，从图中可以看出，算法执行到以v为分支点进一步分割图模型时，遍历算法通过图中实线路径可回到v，即实线部分组成了一个远距离环.

图3 远距离环

远距离环会导致许多不必要的重复计算，增加图分割算法的复杂度，因此在分割网络攻击图的过程中需要对远距离环进行处理.按照构成远距离环的结点的不同，对远距离环的处理可分为以下两种情况.

Case1：如图3，算法从结点v对向下遍历到的结点v1，若v1∉G1，且v1≠v，则认为结点v1为图外结点(如图3(a)).遍历退回前一个结点t，并且v1和遍历到的指向v1的边不加入后继子图G1中，得到的子图G1，如图3(b)中实线部分所示；

Case2：若遍历到一条指向分支点v的边e(如图3(c))，退回前一次访问的结点t，将以v为终点的有向边加入后继子图G1，则得到的子图即为图3(c)所示.

4.3.7 生成子图补全

当分割队列的图全部分割完成后，为了让网络安全管理员便于对分割后的网络攻击图进行分析，需要对分割结果进行信息补全.需要补全的是图内结点的前驱结点的信息，这些前驱结点代表攻击模型图中入侵者行为的前驱步骤，但是在遍历生成子图的过程中，遍历算法沿着有向边的方向前进，部分结点的前驱结点无法遍历到，未纳入到子图中.为了让管理员能够更方便地了解入侵者行为的前后关系，需要将这些结点纳入到子图中.

此外，这些前驱结点同时存在于其他子图中，补全这些结点的信息可以实现不同的子图相互关联.生成子图补全步骤如下：

步骤1.遍历待补全的子图，对遍历到的结点v，从攻击图G中寻找指向v的边的集合Ev.

步骤2.遍历Ev，判断Ev中的有向边e是否属于待补全图.若e不属于待补全图，则将e保存到待补全图中.

如图4所示，对图2(b)所示的分割子图G1进行信息补全，新加入的点和边在图4中加粗标出.

图4 信息补全样例

4.3.8 算法描述

算法主要流程的伪代码如下所示：

算法1.Complex Graph Segmentation Algorithm

1.function AttackGraphGenerater(AttackGraphG)

2.ifComplexDegree(G)then

3.Qs.push(G)

4.while(Qs)do

5.G←Qs.pop(G)

6. /* Looking for branch points */

7. VS← SearchSplitVertex(G)

8. /* Judge independent subgraph */

9.ifIsDependentGraph(VS)then

10. /* Independent subgraph segmentation */

11. DependGraphGenerater(VS)

12.endif

13. /* saves the edge to be traversed */

14. Qe.push(getSuccEdge(VS))

15.while(Qe)do

16. /* Looking for successor subgraphs */

17. Ge=getSuccGraph(Qe.pop())

18.ifComplexDegree(Ge)then

19.Qs.push(Ge)

20. /* saves the output graph */

21.else

22.QOutput.push(Ge))

23.endif

24. end while

25. end while

26.while(QOutput)do

27. /* subgraph Completion */

28. G=InfoComplete(QOutput.pop())

29.Output(G)

30. end while

31.else

32.Output(G)

33.endif

4.4 算法复杂度分析

过程挖掘算法的时间复杂度和待挖掘的攻击步骤数量k相关，时间复杂度为O(k2)[19].

图分割算法的时间复杂度如下：

步骤1.判断攻击图的复杂度需计算攻击图包含的点和边的数量，因此所需时间为O(m).其中m为攻击图结点的数量.

步骤2.寻找出所有分支点的过程相当于遍历一遍攻击图的过程，因此所需时间仍为O(m).

步骤3.在去除独立子图和分割图模型的过程中会多次对分支结点进行遍历，遍历的次数取决于分支点的个数x和分支的边数n.因此一阶段所需时间为O(xn).

步骤4.分割剩余子图的所需的时间仍为O(xn).

步骤5.此步骤每个子图信息补全所需的时间和所需要补全的结点个数有关.因此所需总时间为O(nm).

综上此算法所需时间为O(n(m+x)).运行时间和分割图的结构有很大关系.

考虑算法的空间复杂度，在计算的过程中，需要额外的内存用于保存分割出的子图，所需的空间大小取决于图的结点数量m和边的数量n.故算法的空间复杂度为S(m+n).

5 分布式网络攻击建模

5.1 分布式攻击图生成

启发式过程挖掘算法用于网络攻击图挖掘时，主要步骤是计算安全日志中攻击事件之间的关联关系，然后将各个节点的计算结果进行聚合和拼接，得到网络攻击图.分布式攻击图生成算法包括SecurityCaseRelationCreation、AttackRelationComputation、EventClassification以及EventClassification四个模块.

SecurityCaseRelationCreation：该模块的主要目标是创建事件之间的关系.从HDFS读取原始安全警报后，SecurityXesLogCaseMapper识别出日志记录的字段信息，如SourseIP流量特征签名等信息.然后根据SourseIP字段将原始日志分片为多个子集，将分片后的子集作为挖掘算法中的案例.将SourseIP设置为分片关键字，将流量特征Signature设置为挖掘算法中的实例，即攻击图中的攻击行为.同时，设置Timestamp为关键字进行二次排序.然后将结果输入到AttackCaseReducer中，算法循环遍历每个案例，依次计算案例中的顺序关系、循环关系和逻辑关系，然后创建并输出案例中攻击步骤之间的关系数据.例如，XES日志会根据SourceIP字段分成多个SubLog.设A和B是同一案例下的两个攻击事件实例，之后在reduce任务中，AttackCaseReducer会通过B在A后出现的频率，计算两个事件之间的顺序关系频数，输出|A>wB|，即攻击事件B在攻击事件A后发生的次数.

AttackRelationComputation：该模块仅执行Reduce任务RelationReducer.RelationReducer的输入是上一阶段中AttackCaseReducer的输出.RelationReducer将攻击行为之间的关联关系聚合，同时，通过各种关系数据计算事件之间的依赖值和短循环关系，并计算事件之间的逻辑关系.同时在运算过程中，算法会将案例中存在的每一种关系(包括顺序关系、分支关系、短循环关系等)都聚合起来，然后将聚合后的关系数据输出提供下一个模块进行计算.假设输入的关系数据中存在a与b，a与c的顺序关系(a⟹b、a⟹c)，这些关系会按照关系数据中的左值(即关系中的前驱结点)进行聚合，然后将结果输出.

AttackClassification：在该模块中，ScoredEventMapper会根据攻击行为关系对中的左值(例如顺序关系中的前驱)将数据进行进一步分片.然后通过ScoredEventReducer构建前后结点，输出事件结点作为key，结点的前驱，后继和以及他们之间的边(即关系)三种数据作为value输出.

CausalMatrixGeneration：该模块主要是拼接汇总挖掘出的关系.在前一模块输出的事件结点作为key输入至CausalMatrixMapper中，Mapper会通过key对应的结点找到关系数据中相应的前驱结点和后继结点，构建对应关系矩阵.最后在CausalMatrixReducer将各个计算节点的输出结果汇总到一个实例中，输出一个完整的攻击图.

5.2 分布式攻击图分割

使用启发式过程挖掘算法挖掘出的攻击图，结点和边的数量往往很大，所生成的攻击图结构十分复杂，需要对攻击图进行分割，以便于分析攻击行为.本文提出的攻击流程模型使用有向图来表示入侵者的攻击策略，而Apache Spark的GraphX组件十分适合处理图数据处理.因此，可将Spark与前一阶段的MapReduce攻击图发现相结合，利用Spark GraphX组件进行分布式攻击图分割.由于Spark使用RDD作为数据抽象，因此需要从HDFS中读取攻击图并且保存在RDD中.读取出图的数据后，将图的信息保存在如下三个RDD上：VertexTable、EdgeTable和RoutingTable，其中VertexTable存储结点信息，EdgeTable存储边的信息，RoutingTable存储结点在集群中的位置.

在对单个复杂图进行分割时，若图的复杂度并不是非常高(例如只有数十结点)，通常将分割任务分配在一个节点上进行.使得多个节点可以同时进行多个图分割任务.若图的结点数量巨大，则需要调用Graph.partitionBy对图重新分片，将复杂图分片到多个节点上，再进行分割任务.

6 实验与分析

6.1 实验环境与数据集

6.1.1 实验环境

本节通过实验对本文提出的攻击图生成算法与攻击图分割算法进行分析.算法实现语言为Java，基于Hadoop和Spark分布式框架，实验环境设置如表1所示.

表1 实验环境配置

实验数据集为欧洲某国的ISP提供商在2016年3月到8月之间，产生自IDS/IPS设备的网络攻击数据.实验数据集中的每条日志数据只记录行为信息，不描述攻击者使用的攻击策略，所包含的主要字段如表2所示.此外，为便于研究者们进行算法模型验证，6月与7月的网络攻击数据，按照常见的攻击模式对攻击进行了详细的分类，作为验证集提供.

表2 字段说明

由于实验数据的大小超过11 GB，因此实验选择7月某一周的数据作为输入数据，在对数据进行预处理后，将数据按天分组，以SourseIP字段作为聚类关键字段分为若干组作为输入案例(Case)，并将公式(4)中的γ设为0.3.在单节点实验中，过程挖掘工具选用了ProM框架.ProM框架是目前最流行的过程挖掘工具之一.ProM框架提供了可扩展日志流输入支持，因此对原始数据做预处理后，将日志转换成ProM支持的XES(eXtensible Event Stream)日志格式，以天为单位划分，分别导入到ProM框架中进行过程挖掘.

6.1.2 对比算法与评估指标

本文采用文献[20]的Alpha算法与文献[9]的攻击模型发现算法(MDA，Model Discovery Algorithm)作为HPMA的对比算法，并采用Precision、Recall与F1-score作为性能评价指标.

6.2 实验分析

6.2.1 过程挖掘结果分析

将7月26日-7月30日的攻击日志分成5组分别进行实验，计算每日的Precision、Recall以及F1-score，并求出平均值，结果如图5所示.

图5 Recall、Precision和F1-score比较

由图5可知，基于启发式过程挖掘算法的召回率、准确率、F1-score分别达到91.3%、85.7%以及88.8%，均优于对比算法.所生成的网络攻击图基本涵盖了发生的攻击序列，说明启发式过程挖掘算法能够有效地从安全日志中挖掘出入侵者的攻击策略以及可能使用的攻击步骤.这是由于过程挖掘算法在挖掘过程中能够更好地消除噪声数据的影响.

6.2.2 网络攻击图分割结果分析

由于原始数据记录的规模十分庞大，因此尽管将数据按照天数分开，挖掘结果仍然十分复杂.以2016年7月31日的结果为例.当天日志一共323120条记录，以SourseIP作为关键字分为了4367个案例，平均实例数量大约为79个.以当天的日志输入后，输出的结果为一个由34个结点，109条边组成的复杂攻击图.本节对网络攻击图分割结果进行分析.以根据7月第4周的数据生成的网络攻击图为例，攻击图分割方法将该初始网络攻击图分割为14个网络攻击子图.网络攻击子图构成的结点和边数如表3所示.

表3 分割后的网络攻击子图

从表3可以看出，经过分割算法分割，原网络攻击图被分成了13个非复杂网络攻击图和一个序号为11的复杂网络攻击图，对序号为11的复杂网络攻击子图进行回溯可知，该子图是由于图分割算法在进行信息补全操作后，从非复杂图转换为复杂图.接下来对实验结果样例进行分析，验证分割结果图的有效性.

图6是序号6的网络攻击子图，从图6可以看出，进行了sshScan扫描攻击的入侵者，往后一般会选择四种攻击行为：Impossible Flags(利用无效tcp头部字段的标志位滥用，一种DOS攻击)，Nmap扫描，恶意SMB探针，恶意PHP程序.其中，前三种攻击行为有可能互为后续攻击.使用SMB探针后，利用windows系统漏洞进行MS SQL Hello Buffer Overflow攻击(利用MS SQL漏洞的一种攻击)或者引发windows即插即用异常请求.另一方面，若入侵者在sshScan扫描后，使用了PHP恶意程序，入侵者会使用PHP代码注入就行进一步攻击.从上述例子可以看出，所提出的算法输出的攻击子图显然可以清楚地反映入侵者的攻击模式.

图6 序号6的攻击子图的攻击步骤

6.2.3 时间性能分析

A.攻击图生成算法时间性能分析

本节对比Alpha算法、基于Alpha算法的分布式过程挖掘算法(AlphaoMR)、HPMA算法、分布式HPMA算法(HPMAoMR)的时间性能.实验取7月份两周的日志数据，分别选择11.4G、8G、4G以及1G的日志数据作为输入，并同时对比单机运行和集群运行的结果.每次实验重复运行三次，取平均值进行对比.实验结果如图7所示.

图7 数据规模对攻击图生成算法运行时间的影响

从图7可以看出，当日志数据规模仅为1GB时，分布式挖掘算法的运行时间并没有很明显的优势，然而随着日志数据的增大，分布式挖掘算法的优势逐渐明显，其中分布式Alpha算法的运行时间最短，分布式挖掘算法HPMAoMR的运行时间略长于分布式Alpha算法(AlphaoMR)，但是两者均明显优于单机版本的HPMA算法和Alpha算法.分布式Alpha算法的运行时间优于本文提出的HPMAoMR算法的原因在于，Alpha算法基于W-net进行过程挖掘，由于其缺少对重复任务的挖掘，因此计算量小了许多，较基于启发式算法的HPMA的核心步骤更为简单快速，因此Alpha算法的算法复杂度较低，在运行时间上有一定优势，但是HPMA能够获得优于ALPHA算法的网路攻击图挖掘效果.

接下来固定日志数据规模为11G，通过增减集群节点数，对比分析不同节点数量对网络攻击图挖掘运行时间的影响.实验结果如图8所示，HPMAoMR的运行时间单位为min.当集群节点数为2个时，HPMAoMR的运行时间相比单机版本算法减少了39%.当集群节点数增加为4个时，运行时间减少了62%.但是当节点数增加为8个时，运行时间仅减少了67%.算法从单机到2节点能够明显减少运行时间，是因为两个节点同时处理原始数据，能够有效缓解IO压力.在集群数量从4个增加到8个时，效果并不十分明显，这主要是因为在4个节点数时已经能够有效地解决IO瓶颈问题，同时在Map过程中，由于节点数量变多，数据分片数量变多，节点相互通讯的时间增加，对算法运行时间也有一定的影响，因此性能提升已经不大.

图8 节点数对攻击图生成算法与分割算法运行时间的影响

将网络攻击图挖掘算法生成的网络攻击图作为Spark GraphX的输入，Spark GraphX从HDFS读取到的攻击图的结点数为276，边的数量为1053.同时对比单机环境与Spark集群下网络攻击图分割算法(HGSA)的运行时间，每次实验重复运行三次，取平均值进行对比.实验结果如图8所示，HGSAoSG的运行时间单位为s.从图8中可以看出，基于Spark的图分割算法的运行时间显著优于单机状态下的图分割算法，而Spark集群中节点数量的挑战对结果影响不大，并且对数百个结点的图进行分割时，Spark可以接近实时地输出结果，处理效率较高.

7 总 结

本文提出了一种攻击图生成方法，将启发式过程挖掘技术用于从网络攻击策略模型挖掘.这种方法的主要思想是利用网络攻击者攻击行为和工作流特征的相似性，使用过程挖掘对网络安全日志进行挖掘.为了验证生成方法的有效性，本文使用一个攻击数据集进行实验，实验结果表明过程挖掘算法能够有效挖掘出入侵者的攻击策略.同时，为了解决过程挖掘的输出攻击图的结构复杂的问题，本文提出了一种针对复杂攻击图的分割方法.该方法在有效地保存攻击图的基础结构前提下，成功将复杂的攻击图分割成多个复杂度低的攻击子图，大大增加图的可读性.

在上述攻击图生成方法的基础上，提出基于Hadoop和Spark的分布式攻击图生成方法，该方法使用Spark GraphX对生成的攻击图进行分割，提高分割效率.并通过YARN将MapReduce和Spark整合.解决了过程挖掘算法在单机运行状态下数据处理能力不足的问题，使得攻击图的挖掘效率得到极大提高，减少算法运行时长.并且搭建了一个Hadoop集群对提出的方法进行了实验，验证了算法的有效性.此算法能够使网络管理员能够监控网络安全，并使网络安全管理员能够获取更详细的网络攻击信息，从而做出适当的决策.