原文标题：Graph Mining for Cybersecurity: A Survey
原文作者：Bo Yan, Cheng Yang, Chuan Shi*, Yong Fang, Qi Li, Yanfang Ye, Junping Du
发表期刊：ACM Transactions on Knowledge Discovery from Data
原文链接：dl.acm.org/doi/pdf/10.1145/3610228
主题类型：图数据挖掘
笔记作者：ShuiChang
主编：黄诚@安全学术圈

论文概述

一篇综述论文，讲了图挖掘在网络安全中的应用。探讨了如何使用图挖掘技术检测网络威胁等。论文介绍了图挖掘的基本概念和技术，并比较了传统机器学习方法和图挖掘技术在网络安全中的应用。

图挖掘能解决的问题

• 应用安全

• 网络诈骗 – 包括恶意网页、黑帽SEO、钓鱼网站等
• 评论诈骗（Review Spam） – 网络水军刷评论，存在组间动态复杂、难以检查等问题
• 假新闻
• 假账号 – 虚假账户，用于参加虚假社交，如水军行为
• 金融诈骗 – 对洗钱、套现（cash-out）、贷款违约和保险欺诈做图建模
• 地下市场 – 基于地下论坛的分析：关键参与者检测、账号关联分析、非法产品识别和CTI（Cyber Threat Intelligence， 网络威胁情报）收集
• 交易安全
• 认知域安全（Cognition Security）

• 网络基础设施安全

• 恶意软件
• 系统漏洞
• 区块链安全 – 设计的区块链本身的漏洞（如智能合约漏洞）和区块链中的犯罪活动（区块链洗钱）
• 僵尸网络（BotNet）
• 恶意域名
• 入侵检测
• 网络安全
• 系统安全

图数据挖掘的主要方法

图属性列举（基于结构性的统计特征）

• 节点层次

• 出入度
• 中心度 – 用于衡量节点重要程度，包括度中心度（degree centrality）、介数中心度（between centrality）、接近中心度（closeness centrality）
• PageRank
• 本地集聚系数（Local Clustering Coefficient） – 测量节点与其相邻节点的接近程度：将节点与其邻居之间的实际边的数量除以该节点的邻居之间可能存在的最大边的数量

• 边层次

• 最短路径 – 两个节点间的最短路径

• 图层次

• 直径（Diameter） – 图中两个节点之间最短路径的最大长度
• 度分布（Degree Distribution） – P(k)，即为网络中度数为k的节点的比例，如果总共有n个节点，nk个节点有k个度数，则p(k)=nk/n

网络安全中的同构和异构图

当节点种类或者边种类大于1时，该图被称为异构图，否则该图就为同构图。

同构图

同构图多被用于恶意软件分析。如：API调用、函数调用等。

对于同构图，基本的结构信息可以通过一阶接近度（first-order proximity）和二阶接近度来捕获。一阶接近度的基本思想是高度互连的节点应该紧密嵌入在一起。如：具有调用关系的两个API可以实现类似的功能。然而某些情况下，断开连接的节点也可能有类似的行为。如：两个恶意账户交易走的三方支付平台。二阶接近度就通过比较两个节点的邻居结构来表征两个节点的相似性。即如果两个节点有更常见的邻居，那它们的二阶接近度就更高。

异构图

大多数网络安全的图为异构图。如：Android程序和其签名、使用的API等。

异构图的基本表现形式为网络模式（network schema）。即一个反映节点类型和边关系的元模板。元路径（meta-path）可以捕捉非常有用的内容，从而用于下游任务。

元路径

元路径是在网络模式上定义的路径。其可被表示为关系的结合，通过指定一系列节点类型和边类型的序列描述如何从一个节点到达另一个节点。

如：在作者-论文-引用网络中，存在着“作者-写-论文-被引用-论文-写-作者”这条元路径。

网络安全图挖掘技术分类

依据所利用的特征可分类为：

• 统计特征 – 人为搭建的统计特征，为高维的、且为稀疏的。

• 结构特征 – 即图结构特征
• 属性特征 – 取决于图的属性信息

• 图嵌入 – 特征向量从稀疏转为稠密，且自动保留结构和属性信息。

本文将所利用的图挖掘方法分为了三种类型：

• 结构的-属性的（structural/attributed）：根据是否使用了属性信息
• 表层的-深度的（shallow/deep）：根据是否使用了深度学习
• 同构的-异构的（homogeneous/heterogeneous）：根据是否为异构图

对于不同的网络安全问题来说，侧重于不同的图挖掘方法能够起到不同的效果。

统计特征

结构特征：多用于早期的安全解决方案，泛用性欠佳。如，出入度可以分辨僵尸网络

属性特征：属性特征（Attributed Feature）包含节点属性和边权重等。

图嵌入

图嵌入（graph embedding）目的为给非关系数据降维和获取图里结构和属性的特征。

结构的-属性的

结构嵌入的目的是获取图结构方面的嵌入。如果两个节点在某一方面的结构含有相似性，则其结构嵌入会存在较为相近的距离。故，很多研究采用随机漫步（random walk）来对节点结构特征进行采样。这样的技术包括：DeepWalk、LINE、Node2vec、Struct2vec等。

属性嵌入可以同时表示结构和节点的信息。这样的技术包括：GraphSAGE、GAT。

表层的-深度的

早期研究都为表层的，可训练的参数只有节点嵌入。这样的方式基本为矩阵分解（matrix factorization）和随机漫步。

深度学习所带来的图神经网络（Graph Neural Networks，GNNs）提供了一种获取图嵌入的更方便的、可扩展的方式。这样的方式可分为两种：

• 基于谱方法的（spectral method）：图卷积网络GCN
• 基于空间方法的（spacial method）：消息传递网络MPNN

还存在GAT、GraphSAGE、STGNN等网络。

同构的-异构的

为同构网络所设计的方法存在如下几类：随机漫步的Node2vec、DeepWalk、LINE，以及GNN的GCN、GAT、GraphSAGE。

网络空间安全的图数据挖掘常常遵循这条假设：相似的节点会更有可能相互连接，存在相似的嵌入。

异构图的嵌入往往更重视语义（Semantic）。如，两个主机经常通过同一个协议发包，那么它们就更有可能存在相同的嵌入。大多以预定义的元路径引导的随机漫步算法来进行这种语义嵌入的发现。

一些高级异构嵌入方法依赖于获取并组合异质邻居节点的信息。这便提出了几种解决方法：

• 将不同的嵌入通过映射函数转换到相同的空间；
• 将目标节点嵌入通过指定邻居节点进行聚合后，使用多聚合方式来获取最终节点嵌入；
• 通过元路径获取聚合后的节点后，进行聚合，如下图。

网络安全图挖掘主要过程

• 任务定义
• 确定任务能否使用图进行建模
• 将任务抽象为图任务（如节点预测、节点分类）
• 数据收集
• 收集任务相关数据，确定节点集、属性集和关系集等。
• 图构建
• 对数据进行建模，构建具体的图实例
• 模型设计
• 通过深入分析任务属性和构建的图来设计和优化模型
• 通过图嵌入或通过传统的统计分析
• 模型评估
• 分类模型可使用ACC、Micro-F1、FPR（对于IDS）等。
• 聚类模型可使用AMI等。
• 代码相似度、推荐系统等可以用Rank-n、MRR等。

图挖掘技术解决问题时的典型工作流

交易安全

例：利用黑客论坛分析地下市场

收集信息-建立AHIN-定义元路径-进行随机漫步和多视图融合-获取嵌入进行进一步的下游任务

认知域安全

例：使用重定向链接识别网络垃圾邮件

收集信息-建立HIN-提取特征、基于图建立重定向模板-训练模型预测

例：评论诈骗-水军刷评

收集信息-建立HIN-提取新的基于共同评论的图-设计模型，应用类似社区发现算法的图挖掘方法-解决问题

网络安全

例：挖掘恶意域名

数据收集-搭建HIN-图表示和元路径+邻居节点嵌入融合-检测（节点分类问题）

例：IDS

数据收集-搭建HIN-应用图挖掘技术

系统安全

例：文件级别的恶意软件检测

数据收集-数据处理（反汇编获取Dalvic字节码）-搭建函数调用图-采用基于模板（难以检测0day）或基于学习（有检测0day能力）的恶意软件分析方法-进行特征提取-二分类或多分类任务

数据集与工具

数据集

数据收集工具