论文阅读笔记：一种用于网络异常探测的图分析方法

文章目录

摘要
1. 介绍
2. GRAPHPRINTS的工作流程

2.1 将流量数据表示为图
2.2 Graphlet和轨迹向量
2.3 异常探测框架

3. 实验准备与结果
4. 结论与未来的工作

摘要

调研文章¹。
本文介绍称为GraphPrints的图分析方法，该方法可用于探测网络流量中的异常。

1. 介绍

当前主要依靠两种方法来保护网络资产：其一，基于签名的自动探测系统（automated signature-based detection systems），例如反病毒软件、入侵检测系统、防火墙（但这些方法只在碰见曾经出现过的攻击时才有效）；其二，人工分析网络数据（manual analysis of cyber data）。
为了理解网络活动，安全分析人员转向对网络数据（比如防火墙日志、抓包数据、网络流、系统日志等）的半人工研究（semi-manual investigation）。
GraphPrints方法从IP和整个网络这两个层次来确认网络流量的变化。
关注点：网络流（network flows）–源和目的IP之间的通信的记录。
网络流提供元数据（metadata）：timestamp，IPs，ports，protocol等。元数据描述了在一个小的时间窗口（a small time window）中，IP之间的通信。
网络流（network flows）是监视、诊断、调查网络流量（network traffic）的主要数据源。
一个图 $G=(V,E)$ 定义为顶点 $V$ 和边 $E$ 的集合。其中， $V$ 代表实体，本例中是IPs； $E$ 代表一对顶点之间的关系，本例中指一对IP之间的通信。
GraphPrints方法挖掘graphlet，graphlet是网络拓扑的导出子图，可以认为是构建图的一个个小块（block），它描述了局部拓扑（local topology）。
本文的逻辑是：网络中的异常会给graphlet counts带来变化，而这种变化，可以被我们探测到。

2. GRAPHPRINTS的工作流程

为了进行基于图分析的网络流量异常检测，我们必须要观察网络流数据，并将它们转换成一系列的图。实验使用ARGUS（the Audit Record Generation and Utilization System）来获取网络流数据。

2.1 将流量数据表示为图

首先，建立图 $H$ ，仅有表示IP地址的顶点以及表示每条流的边。每当发现一条流记录，就建立一条从源IP顶点到目的IP顶点的有向边，并按照这条流的total bytes对边赋权。如果两个端口中有一个是常用端口（小于1024），就给这条边着蓝色，反之，着红色。 $H$ 是多重图，因为端口的不同取值，在一对IP之间可能有多条边。要对这些边作聚合，分别计算不同颜色边的总权值，比较后合并。
聚合之后的图 $G$ ，拥有着色的，有向的，无权的边。

2.2 Graphlet和轨迹向量

由于Graphlets反映了网络的局部拓扑，所以它是重要的网络特征。观察网络中的星和路径，可以让我们对网络的整体结构有一个了解。对于给定时间窗口 $i$ 的图 $G_i$ ，我们计算直到大小 $k$ 的，它的graphlets出现的次数，并将这些graphlets计数存放在graphlet degree vector中，用 $g_i$ 标识。论文阅读笔记：一种用于网络异常探测的图分析方法
在本例中，拓扑等价但是有着不同着色的graphlets被认为是不同的。着色可能会让计算复杂，带来内存开销。
为了随时间获取顶点的行为，我们要检查graphlet的自同构轨迹（automorphism orbits）。自同构轨迹是图中对称的顶点的集合。顶点 $v$ 的轨迹向量的入口（entries）是含有 $v$ 的graphlet自同构轨迹的计数。对于给定图 $G_i$ 和顶点 $v$ ，我们将 $G_i$ 中的 $v$ 的轨迹向量记为 $a^i_v$ 。轨迹向量是一个有用的特征，它能标识一个顶点在图中的可扩展的邻居。
网络流数据需要实时观察，并表示为一系列图， $G_1$ ， $G_2$ ，…对于一个给定的图 $G_i$ ，graphlet向量 $g_i$ 标识了这个网络的图层次的特征（比如网络活动的时间窗口上的变化），轨迹向量 $a^i_v$ 标识了网络的顶点层次的特征。作一个形象的比喻，graphlet向量就像手纹（handprints）而轨迹向量就像指纹（fingerprints），所以得到了GraphPrints这个称呼。

2.3 异常探测框架

为了在图层次进行探测，我们需要对先前观测得到的graphlet度向量 $\{g_i\}^n_{i=1}$ 应用多元高斯（a multivariate Gaussian）。由于我们的历史网络数据可能包含（已发现的或尚未发现的）异常，我们使用最小协方差行列式（Minimum Covariance Determinant, MCD）方法，该方法可以在多达 $50\%$ 的异常值确认“最佳匹配”的均值和协方差。具体地说，用户提供一个数值 $h$ 在 $n/2$ 个和 $n$ 个纯数据点之间（pure），该算法找到一个覆盖 $h$ 个点的椭球体的最小体积。这与将高斯分布匹配到 $h$ 个数据点上是等价的，有 $n-h$ 个异常值。因此我们的分布不会倾斜到 $(n-h)/n$ 比率的坏点（bad points）。我们一得到下一个时间窗口的graphlet向量 $g_{n+1}$ 时，就计算它的马氏距离（Mahalanobis distance），马氏距离可以评判这个新向量的异常程度——高分代表极其异常的数据，低分代表相对正常的数据（这个高分、低分是根据高斯分布来评判的）。
为了说明轨迹向量在IP流分析中的作用，我们通过无监督的聚类算法（k-means）来给正常的向量以特征（characterize），并且把向量到簇中心的距离作为异常评分（anomaly score，这里是直接作为评分，还是作为评分的一部分？）。K-means算法是一个无监督学习算法，我们给定一个正数k，通过贪心的方法（a greedy method）将数据分为k个簇。为了建立一个探测器（detector），我们首先要通过在一系列观察的数据点上运行k-means来学习簇中心（the cluster center: centroids）。然后，给定一个新观察得到的轨迹向量，我们要通过考虑它到离它最近的簇中心的距离来决定它的异常评分。本研究中，我们采用间隔统计量（gap statistic）的方法来选择k-means中用到k的值。

3. 实验准备与结果

作为演示数据集，网络流数据是在某个工作日，从校园中的一个小办公楼的主网络交换机上获取（main network switch）的。流量既包含了有线子网，也包含了无线子网，还有一个在单独的NAT网络上的配有很多虚拟机的小数据中心。由于在办公室网络中是不允许有bit torrent流量的，我们专门设置了bit torrent流量，bit torrent流量与其它流量有着相似的拓扑。
数据集包含10507个IP，其中2795个IP属于办公室的子网，419个IP是无线网络上的，2153个IP是数据中心上的。
将数据表示为一些列图 $G_i$ ，时间窗口为31s，其中有1s是重叠的（overlap）。我们总共观察了350个图，每个图平均有1265个节点和4901条边，其中 $76\%$ 的边是红色的。此外，在每个时间段（time interval）中，平均有4929条非空流，因此，大多数的着色边表示的是单一的流（single flow，也就是说没有多少条边是原本的重边经过合并之后得到的，前面说过多重边的合并）。在bit torrent的流量中，我们找到40个时间段（Figure 2 中的no. 278-317），这些时间段中，至少有一个流是属于bit torrent的。其中，前24个时间段包含大约 $15\%$ bit torrent流，后16个时间段仅包含 $2\%$ 的bit torrent流。为了测试，我们在图的层面（at the graph level）考虑这24个时间间隔的TP（true positives），在节点的层面（at the node level）考虑这些时间间隔中涉及bit torrent活动的顶点的TP。异常探测器的目标是探测（pinpoint）出异常事件，我们认为网络活动的大量变化是一个TP，尽管可能这个变化并不大。此外，我们没有意识到哪些可能是离奇的活动在剩余的数据中。
计算了大小为3的graphlets和对应的自同构轨迹来创建 $g_i$ 序列并为每个顶点 $v$ 创建了一系列轨迹计数向量 $a^i_n$ 。使用MCD算法，我们将初始的高斯分布匹配到前150个graphlet向量，对后面的向量，我们使用马氏距离来给异常程度评分，并对高斯分布进行re-fit，让它包含新的数据点。在本研究中， $h=0.85n$ 。在Figure 2中为每个时间窗口给出了异常评分。用红线表示阈值，我们选择这个阈值来标识最大化的已知TP，最小化在阈值之上的点的数目。由于已知的异常在流量中很容易地能分辨出来，这个阈值可得到完美的TP率，0FN（zero false negatives），此外我们看到176个未知异常中的5个被探测到了。论文阅读笔记：一种用于网络异常探测的图分析方法
在节点层面的探测（node-level detection），我们任意地按照和数据中顶点出现的概率比率选取40个IP，并从前150个时间间隔中聚集它们的轨迹向量。使用间隔统计量的方法，选择 $K=5$ 为k-means方法的 $K$ 值。在剩下的200个时间间隔中，这40个IP的轨迹向量离靠它们最近的簇中心的距离列在Figure 3的上面这条线中了。
论文阅读笔记：一种用于网络异常探测的图分析方法

4. 结论与未来的工作

我们的实验得出GraphPrints方法在图层次和节点层次分别有 $2.84\%$ 和 $0.05\%$ 的FP率，两者都有 $100\%$ 的TP率。这证实了，在网络流量中的值得注意的变化，通过3-graphlets/orbits的计数，是可以识别出来的。此外，对意料之外的异常的发现是GraphPrints的未来研究的重要领域——如何跟踪一个已探测到的事件到（1）某个特定的graphlet/orbit计数和（2）具体的那个不正常的网络流。由于GraphPrints方法允许节点着色，重要的上下文信息——比如，某个IP在已知子网中的身份，ASN，国家代号等，可以通过节点着色来编码，我们希望以后在图中囊括这些信息以得到更多的有用的结果。最后，我们认为，对节点层次的簇的研究可以得到对不同类型的用户行为的特征；举个例子，某个簇包括与email使用相关的轨迹向量，也有和web浏览相关的轨迹向量。
总结一下，本工作提出一个图分析方法，以期得到对网络流量数据的分析、探测、标识的初步结果，在各层以比较低的FP率分别出网络行为的值得关注的变化。

Conference Paper Submitted: C.R. Harshaw, R.A. Bridges, M.D. Iannacone, J.R. Goodall, “GraphPrints: Towards a Graph Analytic Method for Network Anomaly Detection” to CISRC 2016, Jan 28, 2016 ↩︎