NMF-NAD：基于NMF的全网络流量异常检测方法

魏祥麟，陈鸣，张国敏，黄建军

(解放军理工大学 指挥自动化学院，江苏 南京210007)

1 引言

因特网已经成为人类生活的重要基础设施，而因网络设备误配置、网络故障、网络安全事件（如分布式拒绝服务攻击、蠕虫传播等）以及不寻常的用户行为等导致的网络异常事件时有发生，严重地干扰了网络的正常运行。然而，在高速且持续变化的链路上准确地检测出网络流量异常，进而维护网络的平稳运行，是因特网服务提供者(ISP)面临的难题，也是网络研究的热点问题之一。

网络流量异常是指网络流量不寻常地和显著地变化，并且可能涵盖多条链路或者路径[1]。检测流量异常面临的主要难点在于：第一，因特网流量的高波动和长相关性会使异常流量淹没于正常的流量之中；第二，流量异常模式非常分散并且经常出现新型异常流量；第三，网络流量巨大，分布式收集和处理很困难；第四，异常检测的实用化要求做到早期检测，对时效性要求较高。

很多异常行为(如 DDoS攻击以及蠕虫传播等等)的全局特性使得传统的单链路方法[2～4]失效，为此，Lakhina等人[1,5]首次采用基于主成分分析(PCA,principal component analysis)的子空间方法进行全网络(network-wide)异常检测，并取得了较好的效果。流量矩阵经过 PCA投影后，得到由一组正交基组成的正常子空间，可以看作是流量的某种固有变化模式，而每条链路或者路径的流量则是这组基向量按照某个系数向量的叠加，这形成了 PCA异常检测的基础。然而，PCA存在以下问题。第一，系数向量中时常出现负值，而网络流量不可能为负，使得这个分解过程的含义难以解释。第二，PCA追求全局误差最小的特性使其容易将连续异常学习为正常流量模式并投影到正常子空间，从而无法有效检测连续突发异常的情况[6,7]。第三，PCA处理复杂度较高。为此，提出了基于非负矩阵分解(NMF, non-negative matrix factorization)的全网络流量异常检测方法 NMF-NAD (NMF based network wide traffic anomalies detection method)。NMF-NAD首先采用非负子空间方法提取流量矩阵中的主要时变模式，并用这些时变模式构成流量正常子空间，并以非负的系数向量对原始流量矩阵进行重构，得到重构矩阵和残余矩阵，然后应用Shewhart控制图基于残余矩阵进行异常点检测。本文首次将NMF应用于全网络流量异常检测领域，并取得了良好的检测效果。

本文的内容安排如下：第2节综述相关工作；第3节研究NMF-NAD算法；第4节通过实验验证了NMF-NAD算法的有效性；第5节是结束语。

2 相关工作

在全网络异常检测方面，主要采用多元统计分析的方法，这类方法可以检测覆盖多条链路的流量异常，成为近年来网络研究的热点。当前基于多元统计分析的方法主要包括基于 PCA的方法和核密度估计的方法。Lakhina等人证实了流量矩阵具有的低维特性以及不同流之间的空间相关性，首次提出了基于PCA的异常检测算法[1,5]，将流量矩阵形成的原始空间分离为正常和异常子空间，并使用Q统计量计算阈值以检测网络异常；而且，实测数据分析表明该方法对于较大的流量异常具有较好的检测性能。

但是，近年来的研究[8,9]，以及实际的实验表明，PCA方法还存在2个主要的问题。第一，PCA方法的检测效果对于其选择的主成分数量以及检测阈值非常敏感。一些基于PCA的方法需要人工设定选择的主成分数量才可以取得较好的检测效果，而不同的主成分选择会导致检测精度差别达到3倍或者更多。检测阈值更是直接决定了检测率的大小，小的阈值可以达到较高的检测率，但同时也会带来较高的误报率；而大的阈值则会在降低误报率的同时降低检测精度。第二，大的或者连续的异常可以毒害PCA的正常子空间。足够大的异常可以显著地污染PCA的正常子空间，使得正常子空间的定义出现偏差，导致增加误报率；连续的异常则可以使得 PCA将其归入正常子空间中，将其当作流量的正常模式，从而降低检测率，这 2个因素也是用来毒害 PCA以降低其检测精度的重要方法[10,11]。

钱叶魁等从时空特性出发，提出了基于多尺度PCA(MSPCA, multiscale PCA)[12]的方法。该方法在进行PCA方法之前加入了小波去噪的过程，意在去除数据中的噪声（由于测量数据的错误或不准确导致）并使得数据平滑，然后使用PCA方法分离正常和异常子空间，最后使用Q统计量计算阈值或者指数滑动平均控制图来检测网络异常。可以看出MSPCA方法与PCA方法的最主要区别在于其加入了小波去噪过程，而这会减轻大的异常对于正常子空间的影响，从而有可能提高检测精度；第二，MSPCA方法考虑了采用指数滑动平均控制图来设定检测阈值。

文献[13]提出了基于统计用户行为距离的异常检测方法。为了减小 PCA算法检测的复杂性，文献[14]提出了分布式实现 PCA检测的方法。Tarem等人在文献[7]指出 PCA方法在检测连续异常时性能较差，并提出了基于核密度估计的检测方法，但这种方法的参数较多，实际检测时需要大量的人工干预。本文方法与已有方法的最大不同在于：在检测连续突发异常时拥有更好的性能，并且分解过程具有更好的可解释性。

3 流量矩阵建模及NMF-NAD算法

本节首先定义了流量矩阵模型；然后介绍了NMF的基本思想，并分析了其与PCA的主要区别；最后提出了基于 NMF的全网络异常检测算法NMF-NAD，并分析了该算法的复杂度。

3.1 流量矩阵和非负矩阵分解

全网络异常检测是基于在多个网络位置经多个测量周期统计得到的流量特征数据进行的[8]。这里的网络位置可以是链路、路由器以及汇聚点等等。流量特征则可以是分组数、流数、字节数以及源IP地址熵等各种流量统计信息。为了便于研究，定义流量矩阵X为一个dp×的矩阵，其中，d是测量周期的数量，而p是网络位置的数量[8]。Xij表示在第i个测量周期时第j个网络位置流量特征数据的测量值。

对于流量矩阵X=[X1,X2,…,Xp]，其中，Xi是第i个网络位置的测量值列向量，Xi∈Rd，d是测量周期的数量。NMF的目标是将X分解为2个矩阵U∈Rd×r和V∈Rr×p，X≈UV，并满足如下目标函数：

定义了代价函数之后，那么式(2)可以重写为如下带有约束的非线性最优化问题：

式(3)是一个带约束的非线性规划问题，而约束条件就是V非负，可以使用Lagrange multiplier方法求解。令U=[uij]，V=[vij]。令αij，βij分别是对应限制条件uij≥0 和vij≥0 的 Lagrange乘子，并令矩阵α=[αij],β=[βij]。那么拉格朗日函数L就如式(4)所示：

求L对于U和V的偏导如式(5)所示：

利用 Kuhn-Tucker条件αijuij=0，βijvij=0，得到式(6)：

从而得到式(7)所示的更新方程：

3.2 基于NMF的全网络流量异常检测

基于 NMF的全网络流量异常检测主要分为 3步：构建正常子空间、获取残余矩阵以及异常凸显与检测。

3.2.1 构建正常子空间

对于原始流量矩阵X，第i个网络位置的测量值向量可以看作位于d维实空间的一个点。由于具有低维特性，因此流量矩阵可以用一个r（r＜＜d）维子空间表示，而这个r维子空间则可以通过NMF构建。更具体地说，对X进行NMF之后，得到的U=[U1,U2,…,Ur]的每一列都构成了r维子空间的一个基向量，其中每一维基向量都捕获了流量随时间变化的一种时变模式。而V=[V1,V2,…,Vp]则是矩阵X中每一列在这个r维子空间的系数向量。类似于文献[15]中的概念，称该r维子空间为正常子空间。

基于NMF的正常子空间构建过程与基于PCA的基向量提取过程[15,16]有 2点不同。第一，由于NMF是带约束条件的最优化问题且目标函数是非凸函数，因此采用梯度下降的优化方法只能得到局部最优解，与 PCA追求的全局误差最小化相比，局部最优的结果使得连续突发异常现象能够较好地凸显出来；第二，NMF抽取的基向量和系数具有非负的特点，这使得各个基向量之间的内积均大于零，因此基向量之间不完全正交，这与“网络流量的变化是多种流量变化模式的加性组合”这一事实相吻合。而 PCA的系数向量中存在负值，这使得网络流量可能是多个时变模式的负的叠加，可解释性较差。

3.2.2 获取残余矩阵

构建了r维子空间以后，就可以利用这r个基向量对流量矩阵进行重构，得到矩阵，并且将看作是流量矩阵中的噪声和异常部分，称为残余矩阵。每个测量周期在残余矩阵中对应的行是异常时刻凸显的基础，称为这个测量周期对应的残余流量。

3.2.3 凸显与检测异常

对于第i个测量周期的测量值经过NMF之后，可以记作其中，分别表示矩阵的第i行，并且分别是Xi中的正常和异常(残余)流量的成分。如果在第i个测量周期发生了网络异常，则Xi将有更多的流量落入中，使得其在中的值大于那些未发生网络异常的测量周期的值，使发生网络异常的测量周期和正常测量周期在中对应的向量的值存在较大的差别。

如果在每个测量周期采取均值、标准差或者极差作为统计信息，则发生网络异常的测量周期与正常的测量周期在中对应的向量的值之间的差别就表现为二者统计信息之间的差别。该差别可用Shewhart控制图[17]很好地捕捉到。为了描述清晰，将每个测量周期称为一个采样点，将发生异常的测量周期称作异常采样点，而将未发生异常的测量周期称为正常采样点。

Shewhart控制图的理论依据是中心极限定理[17]，它假定研究对象服从正态分布，利用样本数据检验总体的均值μ和标准差σ是否发生显著变化来设定控制限，并以控制限为标准来判断某个采样点是否发生异常或超出控制。本文选择的是均值-极差控制图(

假定d个样本独立服从正态分布N(μ,σ2)，并且每个采样点有p个采样值。在第i个采样点，其极差为Ri，而R是d个采样点极差的均值，

当μ和σ都已知时，以概率 1-α落在区间中。在实际应用中，μ1-α/2通常取为3，也就是生产中的3σ控制线。根据中心极限定理，即使样本偏离正态假设，Shewhart控制图的结果仍然近似可用。对于均值和方差，采用样本进行估计，则控制图的控制界限可以写作式(8)～式(10)：

3.3 NMF-NAD算法描述

3.3.1 NMF-NAD算法

基于上述讨论，提出一种基于 NMF的全网络异常检测算法 NMF-NAD。该算法包含以下基本步骤：1) 对原始流量矩阵X进行非负矩阵分解，得到重构矩阵，如算法1中的第1到第2步所示；2) 计算得到误差矩阵，如算法 1中的第 3步所示；3) 使用 Shewhart控制图检测发生异常的测量周期，如算法1中的第4到第9步所示。

算法1 NMF-NAD

输入：X//原始流量矩阵

输出：ATS(anomalies time period set) //发生异常的测量周期的集合

3.3.2 复杂性分析

NMF-NAD算法的时间复杂性主要包括2个部分：NMF分解和根据阈值进行的异常检测。NMF分解的复杂性为O(pdkr)，其中，k是迭代的轮数，r是子空间的维数，d是测量周期的数量，p是网络位置的数量。而基于阈值的判断部分复杂度为O(d)，因此 NMF-NAD算法的时间复杂性为O(pdkr)。相比之下，PCA方法的复杂度为O(dp2)[15]。k与r在实际计算中取值均较小，因此一般地，NMF-NAD的实际处理复杂度低于 PCA方法的处理复杂度。

4 算法评价与分析

NMF-NAD作为一种新的子空间方法，为了考察其性能，将其与 2种典型的子空间方法 PCA[16]以及MSPCA[12]进行了对比。为了对这3种方法进行综合的对比并分析NMF-NAD方法的敏感性，首先进行了模拟实验，在人工生成的数据注入具有不同参数的异常，然后对3种方法的检测结果进行了对比。为了进一步地验证NMF-NAD方法在实际流量数据中的检测效果，又采用最新提出的实验方法基于因特网实测数据进行了实验。为了评价异常检测算法的检测性能，采用了2个测度：检测率和误报率。检测率定义为所有异常测量周期中被检测出来的比例；误报率定义为正常流量周期中被判定为异常的比例。

4.1 模拟实验及其分析

4.1.1 模拟实验方法

网络流量通常由3种成分构成[18]：近似周期性的正常成分、高斯噪声成分和异常成分。产生这 3种成分并按适当比例人工合成流量矩阵中每条网络流(即X的一列)。具体步骤如下：利用多种不同周期的流量(比如周期为7天、5天、3天、24h、12h、6h、3h和1.5h的周期流)叠加来模拟周期性的网络流量[16]，并构造基准流量矩阵，如图1(a)所示；在基准流量矩阵上叠加上零均值的高斯噪声，获得不含异常的流量矩阵，如图1(b)所示；再以一定的规则加入各种典型异常，如图1(c)所示，其中，虚线圈中是异常注入的采样点。用这种方法生成121条网络流并组成流量矩阵X，其中，每条流包含2 010个测量周期。

图1 合成一条异常流的步骤

在此考虑了 4种典型的流量异常[19]：阿尔法(alpha)异常、（分布式）拒绝服务攻击(DoS, DDoS)、闪拥(flash crowd)和入口/出口移动(ingress/egress shift)异常。阿尔法异常是指点到点之间不寻常的高速字节传输；（分布式）拒绝服务攻击是指单源或多源对单个目的地的洪泛攻击；闪拥是指大量客户同时访问某一站点，比如某个Web服务器或视频网站等；入口/出口移动则是BGP策略变化引起流量出口点的变化。

一般可以使用4个参数来描述这4种网络流量异常[19]：持续时间、流量变化大小、源-目的数以及形状函数。各种异常通常具有不同的持续时间，例如拒绝服务攻击通常持续5～30min，阿尔法和闪拥异常可能持续任意时间，而入口/出口移动异常通常持续很多天，直到发生下次 BGP策略变化。当网络异常出现时，可以用2种方式模拟流量大小的变化：一是通过为基准流量矩阵中部分网络流乘上一个乘法因子，二是通过为基准流量矩阵中部分网络流加上一个常数项。源-目的数是指异常所涉及的网络流的数目，拒绝服务攻击或阿尔法事件一般涉及到单个源和单个目的地；入口/出口移动异常则通常涉及到2个源点和2个目的地；而闪拥则会涉及到多个源和单个目的。形状参数是用来模拟各种异常的变化行为，如阿尔法异常通常表现为流量大小的急剧上升，拒绝服务攻击通常表现为流量大小的逐渐上升，闪拥事件通常表现为流量大小的迅速上升，然后又逐渐减少，而入口/出口移动表现为流量大小的阶跃变化，这些行为可以用不同的形状函数(比如斜坡、指数和台阶函数等)及其组合来表征。

在实验中，采样点之间间隔为5min，异常注入过程如下：从第300个采样点到第800个采样点期间，每隔50个采样点注入一次阿尔法攻击，并且阿尔法攻击持续30min(持续6个采样点)；从第1 000个到第1 500个采样点里，每隔50个采样点注入一次分布式拒绝服务攻击或者闪拥攻击，攻击持续时间为30min(持续6个采样点)；从第1 700到第1 800个采样点期间，持续注入入口/出口移动的异常(持续100个采样点)，将某条网络流的一定比例的流量迁移到另外一个网络流对上。

4.1.2 检测结果

3种算法异常时刻凸显的结果如图2所示，其中，竖轴为各种检测方法得到的每个测量周期对应的残余流量向量中所有元素的平方和 (SSE, square sum of the elements of the residual traffic)。

对于PCA方法，采用的是Q统计量的方法进行检测。

图2 3种方法的异常凸显对比

对于 MSPCA以及 NMF-NAD方法，采用了Shewhart控制图进行异常检测。检测的具体过程如3.2.3节所述，是基于误差矩阵进行的。结果分别如图3和图4所示。

图3 MSPCA方法的检测结果

图4 NMF-NAD方法的检测结果

由图3和图4可以看出，MSPCA和NMF-NAD不同程度地检测出了PCA无法检测的连续异常点。与NMF-NAD方法相比，MSPCA方法具有更高的误报率，如在它第200个采样点周围的异常点都是由于误报形成的。

具体的检测结果如表1所示。可见NMF-NAD方法在三者中间检测率最高，同时误判率也较低。

表1 异常检测结果

4.1.3 参数影响的讨论

在NMF-NAD方法中，选取的r的数量和迭代周期k不仅会影响NMF-NAD方法的复杂性，也会影响方法的检测效果。表2给出了在r取不同值时的检测结果。由表2可以看出，r取值为2时检测效果最佳。r的取值与数据集的特性有关，在不同的数据集上取值会有所不同。

表2r取值不同时的检测结果

另外，考察了子空间的维数r=2时，迭代轮数k对于检测效果的影响。实验结果如图5所示。可见，当k取值为50时就可以达到稳定的检测效果。

图5k取值不同时的NMF-NAD检测效果对比

4.2 对因特网实测数据的分析

4.2.1 数据集、实验方法以及测度

为了评价NMF-NAD算法在真实流量数据集上的检测性能，采用了从Abilene实测得到的流量矩阵数据集[1,2,6,18]，数据集的具体描述如表 3所示。Dataset1与Dataset2采自不同的时期且有不同粒度，可以用来考量检测方法的适用性。

表3 Abilene流量矩阵

为了保证对比的公平，采用文献[20]最新提出的实验方法。对于每一种检测方法和每一个的数据集，具体过程如下。

第1步：对数据集应用检测方法得到初始异常集合(BAS, base anomaies set)，其数量为|BAS|=NBAS，其中，| |表示集合的势。

第2步：向数据集注入4种异常，并记为注入异常集合(IAS, injected anomalies set)，其数量为|IAS|=NIAS。

第3步：对注入异常后的数据集再次应用检测方法，得到检测异常集合(DAS, detected anomalies set)，并且异常的数量为|DAS|=NDAS，其中，属于BAS的异常的数量为N1，属于IAS的数量为N2。

第4步：根据BAS、IAS和DAS计算检测率和保持率。

其中，检测率(TPR, true positive ratio)以及保持率(KPR, keep positive ratio)定义如式(12)所示：

另外，在异常注入过程中，需要避免与现有异常的重合。

4.2.2 实验结果

取子空间维数r=2，并且迭代轮数为50轮，3种方法的异常凸显结果如图6和图7所示。图6和图7分别给出了针对Dataset1和Dataset2的异常时刻凸显结果，其中，y轴是各种方法的残余矩阵的2范数值。可以看出，NMF-NAD方法更好地凸显出了发生异常的那些采样点，MSPCA方法次之，而PCA方法无法较好地凸显出异常的采样点。

图6 Dataset1数据集异常凸显结果

图7 Dataset2数据集异常凸显结果

运行 50次后取均值，最终的检测结果分别如表4和表5所示。可见NMF-NAD方法在实测数据环境下，取得了高于PCA和MSPCA方法的检测率，并且较好地检测出了原有的异常点。

表4 3种检测方法对Dataset1的检测结果

表5 3种检测方法Dataset 2的检测结果

5 结束语

本文提出了一种基于非负子空间的全网络异常检测方法 NMF-NAD，理论分析表明该算法与PCA类方法相比，在检测连续突发的情况下具有更好的性能。模拟实验数据以及因特网实测数据的分析表明，NMF-NAD算法具有更好的检测性能，优于PCA以及MSPCA方法。目前提出的NMF-NAD方法属于批处理的检测方法，下一步要对其进行改进，提出在线的、存储开销更低的检测方法，并考虑对发生异常的网络流进行定位。

[1] LAKHINA A, CROVELLA M, DIOT C. Characterization of network-wide anomalies in traffic flows[A]. IMC[C]. 2004. 201-206.

[2] LOGG C, COTTRELL L, NAVRATIL J. Experiences in traceroute and available bandwidth change analysis[A]. SIGCOMM Workshop[C]. 2004. 247-252.

[3] BRUTLAG J D. Aberrant behavior detection in time series for network monitoring[A]. USENIX[C]. New Orleans, Louisiana, USA,2000. 139-146.

[4] MA J, PERKINS S. Online novelty detection on temporal sequences[A]. SIGKDD[C]. Washington, DC, USA, 2003.613-618.

[5] LAKHINA A, CROVELLA M, DIOT C. Mining anomalies using traffic feature distributions[A]. SIGCOMM[C]. Philadelphia, Pennsylvania, USA, 2005. 217-228.

[6] AHMED T, COATES M, LAKHINA A. Multivariate online anomaly detection using kernel recursive least squares[A]. INFOCOM[C]. Anchorage, Alaska, USA, 2007. 625-633.

[7] AHMED T. Online anomaly detection using KDE[A]. GlobeCom[C].Honolulu, Hawaii, USA, 2009. 1-8.

[8] REINGBERG H, SOULE A, REXFORD J,et al. Sensitivity of PCA for traffic anomaly detection[A]. ACM Sigmetrics[C]. 2007. 109-120.

[9] BRAUKHOFF D, SALAMATIAN K, MAY M. Applying PCA for traffic anomaly detection: problems and solutions[A]. IEEE INFOCOMM[C]. 2009. 2866-2870.

[10] RUBINSTEIN B I P, NELSON B, HUANG L,et al. ANTIDOTE:understanding and defending against poisoning of anomaly detectors[A]. ACM IMC[C]. 2009.1-14.

[11] 钱叶魁, 陈鸣. 面向 PCA 异常检测器的攻击和防御机制[J]. 电子学报, 2011, 39(3):543-548.QIAN Y K, CHEN M. Poison attack and defense strategies on PCA-based anomaly detector[J]. Acta Electronica Sinica, 2011, 39(3):543-548.

[12] BAKSHI B. Multiscale PCA with application to multivariate statistical process monitoring[J]. AIChE Journal,1998,44(7): 1596-1610.

[13] SENGAR H, WANG X, WANG H,et al. Online detecting of network traffic anomalies using behavioral distance[A]. IWQoS[C]. Charleston,South Carolina, 2009. 1-9.

[14] LIU Y, ZHANG L, GUAN Y. Sketch-based streaming PCA algorithm for network-wide traffic anomaly detection[A]. ICDCS[C]. Genoa, Italy, 2010. 807-816.

[15] XU W, LIU X, GONG Y. Document clustering based on non-negative matrix factorization[A]. ACM SIGIR[C]. Toronto, Canada, 2003.267-273.

[16] LAKHINA A, CROVELLA M, DIOT C. Diagnosing network-wide traffic anomalies[A]. SIGCOMM[C]. Portland, OR, USA, 2004. 219-230.

[17] 王兆军, 邹长亮, 李忠华. 统计质量控制图理论与方法[EB/OL].http://www.202.113.29.3/～zjwang/publications/books/spc.pdf.WANG Z J, ZOU C L, LI Z H. The theory and methods of statistical quality control charts[EB/OL]. http://www.202.113.29.3/～zjwang/publications/ books/ spc.pdf.

[18] LAKHINA A, PAPAGIANNAKI K, CROVELLA M,et al. Structural analysis of network traffic flows[A]. SIGMETRICS[C]. New York,NY, USA, 2004.61-72.

[19] SOULE A, SALAMATIAN K E, TAFT N. Combining filtering and statistical methods for anomaly detection[A]. IMC[C]. Berkeley, CA,USA, 2005. 1-14.

[20] NYALKALKAR K, SINHA S, BAILEY M,et al. A comparative study of two network-based anomaly detection methods[A]. INFOCOM[C]. Shanghai, China, 2011. 176-180.