作者：乔治华盛顿大学-Isaiah J. King、H. Howie Huang
引用：King I J, Huang H H. Euler: Detecting Network Lateral Movement via Scalable Temporal Graph Link Prediction [C]. Proceedings 2022 Network and Distributed System Security Symposium, 2022.
原文地址：https://dl.acm.org/doi/pdf/10.1145/3588771
源码地址：https://github.com/iHeartGraph/Euler
数据集：LANL

0. 摘要

提出了 EULER 的框架。它由堆叠在模型不可知序列编码层（例如递归神经网络）上的不可知图神经网络模型组成。根据 EULER 框架构建的模型可以轻松地将其图形卷积层分布在多台机器上，以实现大幅性能提升。EULER 模型可以高效地高精度识别实体之间的异常连接，并且优于其他无监督技术。

1. 引言&动机

检测恶意软件传播的最可靠方法不是详尽列出与其相关的每个已知恶意签名；相反，它是训练一个模型来学习正常活动的样子，并在检测到偏离正常活动的行为时发出警报。存在的挑战：检测模型需要可扩展以适应TB级日志文件、必须具有极低的误报率。

在这项工作中，我们将异常横向移动检测制定为时间图链接预测问题。在网络上以离散时间单位发生的交互可以抽象为一系列称为快照的图 $G_t = \{V, E_t\}$ ，其中 $V$ 是网络中在设定的时间段 $t$ 内具有交互的实体集 $E_t = \{(u, v) ∈ V\}$ 。时间链接预测模型将从以前的快照中学习正常的行为模式，并将可能性分数分配给未来发生的边缘，可能性分数低的边与网络中的异常连接相关。

最近的时间链接预测方法将图神经网络 (GNN) 与序列编码器（例如递归神经网络 (RNN)）相结合，以捕获不断发展的网络的拓扑和时间特征。然而，这些方法要么依赖于嵌入的 GNN 阶段的 RNN 输出，要么仅仅将 GNN 纳入 RNN 架构。如图 1a 所示，这些模型必须是连续的，因而无法扩展到它们去处理大型数据集。

观察到：1）现有架构中内存最密集的部分发生在 GNN 的消息传递阶段；2）节点输入特征的巨大尺寸与相对较小的拓扑节点嵌入之间存在不平衡；这意味着最多的工作和最多的内存使用发生在GNN。如果多个复制的 GNN 独立地对快照进行操作，它们可以并发执行，性能会随之提高，如图 1b 所示。
在这里插入图片描述

(a)先前的方法在嵌入的 GNN 阶段依赖于 RNN 输出，或者仅仅将 GNN 合并到 RNN 架构中，这迫使模型串行工作，一次一个快照。相反，(b) EULER 框架可以利用多个工作机器来保存离散时间图的连续快照。这些工作人员通过每台机器共享的复制 GNN 并行处理快照。这些 GNN 的输出返回到领导机器，领导机器通过递归神经网络运行它们以创建可用于链接预测的时间节点嵌入。

总结贡献如下：

首次将时态图链接预测用于基于异常的入侵检测。其他将图分析应用于异常检测的研究要么没有考虑数据的时间性质，要么没有使用强大的 GNN 模型
对于时间链接预测和检测，我们提出的简单框架与最先进的时间图自动编码器模型一样准确或更精确
提出了一个用于大数据的分布式时间链接预测的可扩展框架

2. 背景

离散时态图： $G = \{G_1, G_2, ...G_T \}$ 被定义为一系列图 $G_t = \{V, E_t, X_t\}$ 的集合，称之为快照。 $V$ 表示出现在网络中的所有节点的集合， $E_t$ 表示时间 $t$ 节点之间的关系，即边集， $X_t$ 表示与 $t$ 时节点相关的特征。所有图都是有向的，有些图具有加权边， $W : E \to R$ 表示每个快照包含的时间段内的边频率。一个图是时间窗口 $δ$ 内的所有主体、对象、时间的三元组 $< src, d s t, t s >$ 。
时间链接预测：定义为在给定先前观察到的网络快照的情况下，找到一个函数来描述时间图中某个时间点存在边的可能性。观察到的可能性得分低于特定阈值的实体之间的交互被称为异常。在网络监控的背景下，这些异常边缘通常表示横向移动。

3. 动机

考虑图 2 中所示的示例。前两个时间片显示网络中的正常活动：首先在 t0，Alice 和 Bob 向他们的计算机 A 和 B 进行身份验证，然后在t1 计算机 A 和 B 向共享驱动器发出请求。在时间 t2 和 t3，如果我们没有看到 Bob 首先向计算机 B 进行身份验证时，它则不与共享驱动器通信。一个简单的概率分布是显而易见的： $\begin{gathered} \mathsf{P}((\mathsf{C1},\mathsf{S D})\in{\mathcal{E}}_{\mathsf{t}+1}\mid(\mathsf{B},\mathsf{C1})\in{\mathcal{E}}_{\mathrm{t}})=1 \\ \mathsf{P}((\mathsf{C1},\mathsf{S D})\in\mathcal{E}_{\mathsf{t}+1}\mid(\mathsf{B},\mathsf{C1})\not\in\mathcal{E}_{\mathsf{t}})= 0 \end{gathered}$ 然而，在 t4 和 t5 中，发生了一些不寻常的事情：计算机 B 从共享驱动器请求数据，而 Bob 没有先通过它进行身份验证，这可能是攻击行为。

在这里插入图片描述
现有的基于图的方法不考虑时间，而许多基于事件的方法孤立地查看每个事件，他们缺乏捕捉网络中其他实体之间发生的交互的重要性以及它们如何与单独事件相关的能力，将看不出 (C1,SD) 在时间 t1 和时间 t5之间的区别。为了检测示例中的攻击，模型需要参考之前发生的事件以及网络中的其他交互来考虑事件。在一个时间点发生的两个实体之间的事件不能被认为与未来在不同的全局背景下发生的同一事件相同。

这里原文举的例子是t1和t4，但是我理解的是：传统方法会因为发生过t0，导致认为t5是正常的，其实并不是，所以必须考虑时间信息，不能忽略相同信息的时间影响，比如验证过期需要重新验证。所以改成了t1和t5。

4. EULER

该框架旨在学习以时间图的先前状态为条件的概率函数，以确定边缘出现在稍后状态的可能性。

A. 编码与解码器

它由堆叠在模型不可知递归神经网络 (RNN) 上的模型不可知图神经网络 (GNN) 组成。这些模型共同旨在找到编码函数 $f (\cdot)$ 和解码函数 $g (\cdot)$ 。编码函数将具有 $T$ 个快照的时间图中的节点映射到 $T$ 个低维嵌入向量。解码功能确保在编码过程中丢失的信息最少，旨在从潜在 $Z$ 向量重建输入快照。 $\begin{aligned} & Z=f(\{\mathcal{G}_0,\ldots,\mathcal{G}_T\}) \\&=\operatorname{RNN}(\left[\operatorname{GNN}(\mathbf{X}_0,\mathbf{A}_0),\ldots,\operatorname{GNN}(\mathbf{X}_T,\mathbf{A}_T)\right]) \end{aligned}$ 其中 $A_t$ 是时间 $t$ 快照的 $∣ V ∣ \times ∣ V ∣$ 邻接矩阵表示。这个 $T \times ∣ V ∣ \times d$ 维张量 $Z$ 被优化为包含关于图形结构的信息，以及它如何随时间变化的动态。

解码函数 $\mathbf{g}(\mathbf{Z}_\mathbf{t})=\mathbf{Pr}(\mathbf{A}_{\mathbf{t}+\mathbf{n}}=\mathbf{1}\mid\mathbf{Z}_\mathbf{t})\\=σ(\mathbf{Z}_{\mathrm{t}}\mathbf{Z}_{\mathrm{t}}^{\mathsf{T}})={\mathbf{\tilde{A}}}_{\mathrm{t+n}}$ 其中 $σ (\cdot)$ 表示 logistic sigmoid 函数, 且 ${\mathbf{\tilde{A}}}_{\mathrm{t+n}}$ 表示在时间 $t + n$ 处重建的邻接矩阵。

B. 工作流程

EULER 框架的核心是将与模型无关的 GNN 的副本（我们称之为拓扑编码器）堆叠在具有一些简单约束的与模型无关的循环层上。当适应以一个循环层作为领导者、多个拓扑编码器作为工作者的领导者/工作者范式时，它具有大规模并行的潜力。整体工作流程如图 3 所示，分为5个阶段：

领导者生成工作人员并指示他们加载哪些快照
领导者启动训练循环，工人生成拓扑嵌入
接收到拓扑嵌入后，领导者通过 RNN 处理它们
将RNN的输出发回工人计算损失或打分
在训练模式下，损失返回给领导者进行反向传播。

C. 训练

两种训练模式：链接检测器和链接预测器。区别在于第 4 步将 $Z_t$ 嵌入发送给工作人员以计算损失。链路检测器是感应的；他们使用部分观察到的快照生成 $Z_t$ 并尝试用 $g(Z_t)$ 重建完整的邻接矩阵 $A_t$ 。然后人工执行审计以识别已经发生的异常连接。链接预测器是转导的；他们使用快照生成 $Z_t$ ，以预测未来状态 $A_{t+n}$ ，然后对观察到的边进行评分。

D. 分类

尽管对于我们的大部分评估，我们依赖于与分配给边的分数的适应性相关的回归指标，但自动化确定异常阈值的过程以获得分类分数是很有用的。为此，在训练模型时，我们拿出一个或多个完整快照作为额外的验证集。使用来自训练快照的 RNN 的最终隐藏状态 h 作为验证快照的输入，找到边缘似然分数的最佳截止阈值。给定验证快照中存在的一组边缘分数，最佳截止阈值 τ 满足 $\text{argmin}\quad\|(1-\lambda)\text{TPR}(\tau)-\lambda\text{FPR}(\tau)\|$ 其中 $TPR (τ)$ 和 $FPR (τ)$ 指的是给定截止阈值 $τ$ 的分类的真阳性率和假阳性率，λ = 0.6。