基于Spark平台的恶意软件最大频繁子图挖掘方法

周显春，肖 衡，焦萍萍，邹琴琴

（三亚学院信息与智能工程学院，三亚 572022）

0 引言

子图挖掘（subgraph mining）是图数据挖掘的一个重要分支，它已经成为数据挖掘中的一个研究热点［1］，旨在从大规模复杂图数据中发现有意义的子图模式。随着社交网络、互联网、生物信息学等领域的快速发展，大量的图数据已经成为现代科学研究的重要来源，在社交网络中可以发现社交网络中的社区结构、关系网络等信息，在推进系统中可以发现用户间的相关关系、用户兴趣等信息，从而提高推荐系统的准确性，在网络安全中可以发现网络攻击行为、恶意软件等信息。但是，这些数据通常是非常复杂和庞大的，很难从中提取有意义的信息。

1 图数据挖掘算法相关研究

目前，图数据挖掘算法可以分为三类：针对图集合、针对单个大图［2］及分布式频繁子图挖掘。

在针对图集合的频繁子图挖掘中，可以使用邻接矩阵表示图数据，并使用基于Apriori 算法的改进算法，如AGM［3］、FSG［4］和MARGIN［5］，或者基于DFS 的改进算法gSpan［6］来挖掘频繁子图。其中，gSpan 算法能够支持对边缘属性和标签等更丰富的信息进行挖掘，但在大规模数据集上性能可能受到影响。为此，UBW-gSpan 算法［7］通过引入最小支持度阈值和最大标签数目阈值两个参数进行优化。

在针对单个大图的频繁子图挖掘中，SUBDUE［8］、SIGRAM［9］算法和GRAMI［10］算法是常用的算法。SUBDUE 算法利用图匹配和图压缩进行子图挖掘，能够有效挖掘大规模图中的频繁子图，并且不需要事先指定子图的大小，但存在不能处理具有变化的图数据集以及可能生成重复子图的缺点。SIGRAM 算法采用基于图同构的方法进行子图匹配，将每个图转换为一个特征向量来捕获其结构信息，并使用随机映射来降低计算复杂度。GRAMI［10］算法将图形模式挖掘问题转化为限制约束问题，从而实现高效的挖掘，但需要注意参数选择、候选生成复杂度和内存占用等缺点。

分布式频繁子图挖掘算法旨在Hadoop［11］/Spark［12-13］框架大规模分布式系统中挖掘频繁子图。该算法将数据集划分为多个分区，在每个分区上运行子图挖掘算法，最后将每个分区的结果进行合并，得到全局频繁子图。FSMBUS算法［14-15］通过分布式计算和分治策略来解决这些问题，减少了搜索空间，提高了挖掘效率，缺点是在处理大规模图数据库时会面临计算复杂度高的问题。

为了解决传统子图挖掘算法时效性差的问题，提出了一种基于Spark 分布式平台的恶意软件最大频繁子图挖掘方法，利用改进FSMBUS算法的优点，能够利用子结构之间的相似性进行最大频繁子图挖掘，从而减少搜索空间并提高挖掘效率。该算法应用于恶意软件同源性判定，发现恶意软件中存在的共同子结构，以改善恶意软件检测的效果。通过实验验证了改进算法的效果。

2 最大频繁子图提取方法

2.1 提取方法的架构

最大频繁子图提取方法分为两个阶段：数据预处理和数据挖掘，流程如图1所示。数据预处理负责从恶意代码中提取程序依赖图；数据挖掘是核心部分，包括任务并行化、子图挖掘、子图剪枝、CSP 模型判断［16］、是否存在超图等阶段。Master结点通过并行化把任务分解并分配给Worker 结点。子图在每个Worker 节点上对子图扩展进行迭代计算，通过频繁度比较完成边的扩展和剪枝。最后，在主结点通过判定频繁子图是否存在超图得到最大频繁子图（图2）。

图1 最大频繁子图提取流程

图2 基于Spark集群最大频繁子图提取架构

2.2 函数调用图提取

利用调试工具运行被混淆的代码，并在运行过程中监视其行为和状态，通过分析运行时数据和代码执行流程，提取函数调用图。

2.3 基于Spark的改进FSMB算法

2.3.1 FSMBUS算法［13］

它是一种基于状态机的流式数据挖掘算法，在候选频繁子串的每个位置中，查找所有长度为k-1的子串是否出现在之前已经确定为频繁子串的位置中，如果未出现的次数小于最小支持度阈值，则需要剪枝。剪枝可以有效地减少计算量，提高算法的效率。其伪代码如下：

输入:L：一个列表，包含所有长度为k-1 的频繁子串；S：一个字符串列表，表示序列集合；P：一个候选频繁子串，用于判断是否需要剪枝；threshold：频繁子图的最小支持度阈值。

输出:prune：一个布尔值，表示是否需要对该候选频繁子串进行剪枝。

（1）初始化一个计数器count为0

（2）对于每个字符串s∈S，执行以下步骤：

1）在s中使用后缀数组和后缀LCP 数组找到所有长度大于等于|P|的子串，记为Si；

2）在Si中使用位向量和比特位并行操作找到所有与P匹配的子串，记为Mi；

3）将Mi中所有与P相等的子串对应的位置记录在一个集合中，记为Pi；

4）对于Pi中的每个位置p，执行以下步骤：

（a）将p转化为Pi的编号，记为pid

（b）在L中查找长度为k-1 的子串是否出现在pid中，如果出现，则将count加1

（3）如果count小于threshold，则将prune设为True，否则设为False

（4）返回prune的值

2.3.2 创建给定子图的所有不同超图的伪代码

输入：一个子图g（V′,E′），原图G（V,E）

输出：子图g的所有不同超图的列表

（1）初始化超图列表H为包含V′的初始超图

（2）对于原图G中V′-|V′|+1个节点的子集S：

1）如果S中至少包含g的所有节点，则创建一个新的超图G′

2）将S中的所有节点添加到G′的节点集合中

3）对于g的每条边（e1,e2），如果S中同时包含e1和e2中的所有节点，则将它们添加到G′的超边集合中

4）如果G′不是H中的任何超图的子集，则将G′添加到H中

（3）返回超图列表H

2.4 基于GraphFrames的大规模单图上的子图匹配算法

GraphFrames是一种基于DataFrame和GraphX的图处理库，提供了方便的API来实现图分析任务。包括加载大规模单图和查询子图、子图查询、子图匹配、结果输出。其伪代码如下：

（1）读取原始图G和查询图Q

（2）对G和Q进行顶点和边的特征提取

（3）在G中寻找与Q相同的顶点集合V

（4）对每个V中的顶点，寻找与Q相同的邻居结构，生成候选子图

（5）将候选子图转换为GraphFrames 格式，构建候选子图集合CG

（6）使用GraphFrames 中的find（）对CG进行子图同构匹配，得到匹配的子图集合M

（7）对M进行筛选和排序，输出最优的匹配子图

3 实验结果及分析

实验使用虚拟集群，虚拟机PC 机31 台,其中1 台master主节点，30台为slave从节点。每台PC机的配置相同：操作系统为Centos7.9，CPU为Intel Core i7 3.8 GHz，16 GB 内存，使用Scala 2.12.17 开发，集群环境建立在Hadoop3.3.4、Spark3.3.1、jdk 1.8上。

3.1 数据集

http://malware.lu确实是一个公认的恶意代码样本库，一共有4964137 个恶意软件样本，其中包含各种类型的恶意代码家族，例如病毒、蠕虫、木马、后门、根包和间谍软件等，大部分经过了加壳处理。每个实验样本，Mytob、Netsky、Allaple、Bagle、Mydoom、Agobot/Gaobot，均有3000个。

3.2 评价指标

采用最大频繁子图挖掘时间、恶意软件检测的准确率（PR）、误报率（FPR）、漏报率（FNR）四个指标对模型的检测效果进行评价。

3.3 实验结果及分析

3.3.1 支持度对运行时间的影响

由图3 可知，MapReduce 方法挖掘最大频繁子图的运行时间较多，与改进FSMBUS、传统FSMBUS 算法相比，时间要多2～4 倍。在支持度的值为8.0 之后，三种分布式算法的运行时间基本稳定。改进FSMBUS 算法运行时间稳定在3.7 ms 左右,传统FSMBUS 算法运行时间稳定在2.7 ms 左右，说明了两种算法比较稳定。改进FSMBUS 算法比传统FSMBUS 算法多了1 ms 左右，主要原因是传统FSMBUS 算法是进行频繁子图挖掘，而改进FSMBUS 算法是应用于挖掘最大频繁子图，与传统FSMBUS 算法多了一个超图运算操作。

图3 支持度与系统运行时间的关系

3.3.2 运行时间的分析

如表1所示，三种方法的最大频繁子图挖掘时间的对比，可以发现基于Hadoopk的方法频繁子图挖掘时间是基于Spark的方法的3～4倍；基于Spark 的改进FSMBUS 方法进行最大频繁子图挖掘时间要比Top-Down算法快20～60 ms，平均减少时间32 ms，说明了本文的方法对大图挖掘最大频繁子图的效果较好。

表1 最大频繁子图挖掘时间

3.3.3 恶意软件识别效果的分析

由表2 可知，改进FSMBUS 相较于传统FSMBUS 方法，其平均准确率提高了1.3 个百分点、平均误报率降低了3.6%个百分点；相对于MapReduce 方法，改进FSMBUS 的平均准确率提高了1.7 个百分点、平均误报率降低了1.8 个百分点。并且改进FSMBUS 方法对大部分恶意软件的检测效果比较稳定，不仅说明最大频繁子图可以作为恶意软件的检测特征，而且对恶意软件的检测效果很好，平均准确率和平均误报率分别为95.6%和4.4%。

表2 传统FSMBUS、改进FSMBUS和MapReduce检测效果/%

4 结语

为了解决传统子图挖掘算法时效性低的问题，本文提出了一种基于Spark 架构的恶意软件最大频繁子图挖掘方法。该方法采用次优树数据结构进行并行化处理，利用GRAMI 算法计算支持度，并采用次优树连接和扩展边的方式获取最大频繁子图，从而提高挖掘效率。利用改进的FSMBUS 方法在Spark 分布式平台上进行实现，用于挖掘恶意软件中的最大频繁子图。实验结果表明，该方法相对于Top-Down 算法平均挖掘时间减少了32 ms，与基于频繁子图的恶意软件检测相比，平均准确率提高了1.3 个百分点、平均误报率降低了了3.6 个百分点。子图相似匹配是最大频繁子图挖掘的关键，因此是下一步研究的重点和方向。