基于低秩分解的网络异常检测综述

互联网已经成为社会基础设施，但面临严重的安全挑战[1]，如拒绝服务攻击[2-3]、蠕虫病毒[4]、僵尸网络[5-6]等.例如，2016年Twitter与Spotify的大型数据中心，因遭受了持续的拒绝服务攻击而关闭网站[8]；2017 WannaCry勒索[7]病毒感染了政府、能源、医院、学校、工厂等多个领域.随着新技术的不断应用，互联网变得越来越复杂，攻击手段越来越先进，如何快速精准地检测定位这些异常行为，避免造成更多的损失与危害，变得尤为重要.

1 研究背景

对于网络异常，不少文献有各自的定义：Thottan等人[9]将网络异常描述为一种偏离正常网络行为的事件；Barnett[10]将异常数据集定义为 “与数据集中其余部分出现不一致的观测子集”；Chandola等人[11]认为异常数据的行为模式不符合既定的正常行为；根据Lakhina等人[12]所述，网络异常表现为在网络流量层面上出现不同寻常且明显的变化，这种变化通常可以跨越多个网络链接；Hoque等人[13]将异常定义为“相较于明确定义的正常行为数据，那些更不符合规定的、更令人关注的行为数据”；Hawkins[14]对异常的定义是“异常是远离其他观测数据而疑为不同机制产生的观测数据”.通过上述定义发现，异常检测本质就是检测和发现数据中不符合期望行为的异常数据模式.研究人员在设计异常检测算法前通常需要判断所需检测异常的种类，通常可分为3类[15-16]：

1) 单点异常(point anomalies).单点异常[11,15]即与全局数据的行为模型不同的单点数据.异常数据在数据集中单个出现，不产生聚集.例如某一局域网中，存在某一网络节点发生拥塞，导致其丢包率远远高于其余网络节点，那么该网络节点即为单点异常.单点异常作为最简单的一种异常种类，通常只需要简单的聚类、分类算法即可进行有效检测.网络中U2R，R2L等攻击[17-18]通常可视为单点异常.

2) 集体异常(collective anomalies).集体异常[19-20]通常由多个对象组合构成，即单独观测某一独立个体可能并不存在异常，但是这些个体同时出现则构成一种异常.集体异常通常是由若干个单点组成，例如，拒绝服务攻击通常由攻击者控制大量傀儡机向服务器发送请求来抢占服务器资源，使服务器无法响应正常请求，达到攻击服务器的目的.

3) 上下文异常(contextual anomalies).上下文异常[21]通常被定义为：当数据点的值与同一上下文环境中的其他数据点明显不同时，该数据点被认为是上下文异常值.值得注意的是，同一个值发生在不同的上下文环境中，可能不会被认为是离群值.当我们讨论日志异常检测任务时，“上下文”通常表示为日志文件所示上下文；而当我们讨论时间序列异常检测任务时，“上下文”则表示时间.因此，在网络异常检测中，日志异常、时序数据异常通常可视为上下文异常.

1.1 相关综述工作

异常检测一直以来都是一个备受关注的问题，不少异常检测的综述论文从不同角度对现有的异常检测方法进行了总结与分析.文献[22]将神经网络异常检测方法划分为特征提取方法、正常数据表征方法、异常分值学习方法，并详细介绍了这些方法解决的异常检测问题中存在的挑战.文献[23]对时序数据检测方法进行了综述，并将这些方法根据变量的不同分类为单变量异常检测与多变量检测.文献[24]则将网络异常检测方法划分为基于距离的方法、基于密度的方法、基于软阈值的方法.而文献[25-26]与文献[27]则分别对基于机器学习以及数据挖掘的异常检测方法进行了综述，并将它们根据具体实现算法的不同进行了归类，如聚类分析、支持向量机、决策树、贝叶斯网络等.

尽管文献[22-27]提出一系列的异常检测综述对现有的大部分异常检测方法进行了归类与整理，但它们大多是基于某一具体的异常检测方法进行分类与总结.近期随着稀疏表征技术的快速发展，得益于该技术较强的数据特征提取能力，基于低秩分解技术的异常检测方法也越来越受到重视，因此，本文将对基于低秩分解的异常检测方法进行综述以及分类.

1.2 异常检测方法原理以及分类

异常检测的基本思想是通过算法将异常和正常区分出来，从距离、密度、概率统计这3个不同的角度来区分正常数据和异常数据.异常检测算法可以分为3类，如表1所示：

基于距离的异常检测方法[28-32]是基于数据对象之间的距离计算来定义异常，具有清晰的几何解释.这类方法[31]于1998年被提出，通过计算比较数据与近邻数据集合的距离来检测异常数据，是最常用的异常检测方法之一.其基本思想是正常数据点与其近邻数据相近，而异常数据点则更远[32].这类方法通常不需要数据标签，适用于无监督异常检测场景.其缺点主要包括计算复杂度高、异常距离阈值难以确定等.

基于密度的网络异常检测方法[33-36]，首先需要估算输入空间的密度分布，然后将在低密度空间区域的数据对象定义为异常数据.基于局部离群因子(local outlier factor, LOF)作为一个经典算法[33,36]，通常为每一个数据赋值一个代表其邻域密度的LOF值，当LOF值越大，则表示其邻域密度越低，越有可能是异常数据.这类方法同样不需要数据标签，适用于无监督异常检测场景.其缺点主要包括计算复杂度高、LOF阈值定义困难等.

基于概率统计的异常检测方法[37-41]，最早由Barnett等人[41]提出，首先假设数据集服从某种分布(如正态分布、泊松分布及二项式分布等)或概率模型，然后通过判断各数据点是否符合该分布/模型来实现异常检测.例如，假设数据集服从一元正态分布，当数据点与均值差距大于3倍方差时，则认为该数据点为异常数据.这类方法基于数据分布能够快速有效地找出异常数据，同时又能表示数据所包含的信息特征.其缺点主要包括可解释性差、数据分布/模型难以确定、随着数据特征维度的增加其异常检测精度将降低等.

大量研究基于数据挖掘、机器学习、深度学习等技术实现异常检测过程，由于数据挖掘与机器学习算法存在交叉与重叠，本文将异常检测过程的实现方法分为2类，如表2所示：

尽管经过多年异常检测方法的研究，很多检测方法都实现了不错的异常检测效果.然而，大部分研究都是通过分析独立的时序数据(例如，单链路流量数据[37]、关键性能指标(key performance indicator, KPI)数据[69-70]、日志/记录[71-73]、数据包[74]、简单网络管理协议(simple network management protocol, SNMP)数据[1,75]等)来实现异常检测.这些研究方法却存在一些不可避免的缺陷[76]：

1) 通常需要学习网络攻击的先验知识(prior knowledge)[77]或分析正常用户的行为模式，因此，难以检测新型异常、模仿正常用户行为模式的攻击.

2) 仅利用了网络数据内部的时间相关性，而忽略了空间相关性，而许多异常行为常影响网络中多条链路或路径，并不会在单链路或路径上明显呈现，这就使得检测并不准确.

3) 通常利用阈值判断检测数据是否为异常，却无法定位异常发生的具体位置，这就使得算法在网络管理的应用中存在局限性.

为了解决上述3个缺陷，Lakhina等人[12,78]提出使用流量矩阵作为数据源，并使用一种主成分分析(principal component analysis, PCA)[79]实现了基于低秩分解的全网(network wide)异常检测模型.该模型利用网络数据所蕴含的低秩性特征，通过从网络监测数据分离低秩正常数据和异常数据，实现全网异常检测.

基于低秩分解的全网异常检测模型不仅利用多条链路流量数据中的时间相关性(temporal corre-lation)，而且同时整合了空间相关性(spatial corre-lation)，将高维的网络流量数据矩阵映射到正常子空间与异常子空间，然后在异常子空间中检测凸显的异常行为模式.该模型作为一种无监督异常检测模型，不需要学习任何网络攻击/异常的先验知识以及网络正常行为模式，同时充分利用了网络数据中的时间-空间相关性.另外，通过分离所得异常数据通常能够实现对网络异常的定位.因此，该模型能够很好地解决传统异常检测方法中存在的一系列局限性问题.

尽管，基于低秩分解的全网异常检测模型相较于传统的异常检测方法具有一定的优势性，却依然存在不少挑战.

1) 基于低秩分解的全网异常检测模型关键在于从监测数据中提取正常数据，然而，异常数据通常严重影响正常数据的低秩性，进而影响正常数据的提取.因此，如何准确提取正常数据，并在进行正常数据提取过程中对异常数据进行有效约束，以减少异常数据对正常数据提取的影响，从而保证异常检测精度，这成为一项挑战.

2) 基于低秩分解的全网异常检测模型通常需要使用低秩分解技术(如矩阵/张量分解)，然而，低秩分解过程通常是迭代执行过程，需要高昂的计算代价.这就降低了该模型的可拓展性，同时使其无法满足在线网络异常检测的要求.因此，如何降低该模型的计算代价成为另一项挑战.

为了更清晰地介绍各类基于低秩分解的全网异常检测模型，本文首先在矩阵模型下对各类异常检测方法，根据其对异常数据约束方法的不同进行分类，并介绍各类模型在计算代价以及求解方式上的变种与改进.然后，以同样的方法对张量模型下的异常检测方法进行了分类与总结.

2 基于低秩分解的异常检测模型原理

2.1 网络监测数据矩阵

为了研究基于低秩分解的全网异常检测技术，通常可以将同一个网络中所有源节点(origin)和目的节点(destination)对之间的性能数据(例如流量、吞吐量、时延等)建模成一个矩阵.如图1所示，矩阵中的行代表源节点-目的节点对(OD对),而矩阵中的列代表时间(time)，矩阵中元素则代表对应时刻下OD对之间监测的网络性能数据.根据所选择的网络节点类型的不同，可以定义为不同粒度的矩阵，例如链路级、路由级、PoP(point of presence)级流量矩阵[80-81].

2.2 网络数据的低秩性分析

基于低秩分解的网络异常检测算法实现的前提条件是将正常网络性能数据建模为低秩数据，因此，本节将首先给出网络测量数据的低秩性验证.

用户的网络行为通常具有时间稳定性以及空间相关性.文献[82]阐述并证明了网络性能数据的时间相关性、空间相关性、天周期性等特征.如图2所示，图2(a)表示相邻时刻之间的网络性能数据之差的累计概率分布，图2(b)表示不同OD对中的网络性能数据的相关系数，图2(c)表示相邻天之间的网络性能数据之差的累计概率分布.

通过分析图2(a)发现，网络性能数据在相邻时刻之间十分相似.图2(c)则显示相邻天之间的网络数据十分相似.因此，网络性能数据通常具有较强的时间稳定性，这就使得网络性能数据在时间维度(例如图1中的时间)具有低秩性的特点.同样地，通过分析图2(b)发现不同OD对之间的网络数据向量具有较强的相关性，因此，网络数据同样具有较强的空间相关性，从而使得网络数据在空间维度(例如图1中的源节点-目的节点对)具有低秩性的特点.

为了进一步验证网络数据的低秩性，我们将网络性能数据按照图1所示建模为矩阵X，并对X进行奇异值分解(singular value decomposition, SVD)，得到[X]=UΣVT.其中，Σ为对角矩阵，Σ=diag(σ1,σ2,…,σR,0,…,0)，该矩阵的对角线上元素通常为从大到小排列的结果.那么，矩阵X的秩则为矩阵Σ中非零元素的个数.值得注意的是，在实际的应用中，由于网络的监测数据为连续数据存在一定的测量噪音，因此，监测数据通常并不满足严格意义的低秩.根据主成分分析算法的定义，奇异值越大，其所代表的主成分越重要，其前k个奇异值所占比重几乎等于所有奇异值之和时，则可以认为这个矩阵为近似低秩矩阵，并满足低秩性的特点.因此，通常利用指标来判断是否为近似低秩矩阵.

图3表示Abilene和GEANT数据集的低秩性验证结果.通过分析可以发现，少数几个奇异值基本占据了所有奇异值的比重，因此，得以验证网络性能数据具有低秩性特征.

文献[83]同样在开源网络流量数据集Abilene与GEANT上开展了实验，并验证了网络数据的低秩性.另外，大量研究[82-87]利用网络数据的低秩性来填充网络缺失数据.而基于低秩分解的网络异常检测方法则通常利用网络性能数据的低秩性以及低秩分解技术，将高维的网络性能数据映射到正常子空间与异常子空间，其中正常子空间即为低秩子空间.

3 基于矩阵模型的异常检测方法

由于网络性能数据中具有第2节中分析的低秩性特征，因此，基于低秩分解的数据分离模型[88]提出利用网络数据内部的低秩性特征，结合低秩分解技术将监测所得原始数据分离成为正常数据与异常数据.如图4所示，矩阵X为网络监测数据矩阵，利用低秩分解技术可以将其分解为正常数据矩阵M与异常数据矩阵E.根据2.2节分析，正常数据具有低秩性的特点，网络攻击代价高的问题以及网络设备故障的稀疏性问题使得异常数据通常具有稀疏性的特点.因此，异常数据矩阵E通常为稀疏矩阵，通过基于低秩分解的数据分离模型获得稀疏异常数据矩阵E后，即可对网络数据中是否存在异常进行判定，同时根据矩阵中非零元素所处位置可进行异常定位.

为了实现图4所示的数据分离，基于低秩分解的异常检测模型通常将优化目标函数表示为：

其中,X为原始的网络监测数据， M为正常数据矩阵，E为稀疏异常数据矩阵，rank(M)≤R表示正常数据的低秩约束，而ρ(E)表示异常数据约束条件.由于基于低秩分解的异常检测模型关键在于从监测数据中提取正常数据，然而，异常数据通常严重影响正常数据的低秩性，进而影响正常数据的提取，并最终影响异常检测的精度.因此，如何准确地提取正常数据并有效约束异常数据，成为异常检测的关键一环.

本节将分类介绍各类异常检测方法，如表3所示.根据正常数据的提取方法与异常数据约束条件的不同，将基于低秩分解的异常检测方法分为基于PCA的异常检测方法、基于鲁棒的主成分分析方法(robust principal component analysis, RPCA)的异常检测方法、基于直接矩阵分解的异常检测方法，以及其他异常检测方法.然后介绍各类方法在计算代价以及求解方式上的优化与改进.

3.1 基于PCA的异常检测方法

Lakhina等人[12,78]提出将网络流量数据建模为矩阵，并使用PCA算法来实现全网异常检测.该算法利用低秩分解技术，将正常数据M从原始监测数据X中提取出来，如图4所示.

为了实现正常数据的提取，通常对原始监测数据使用PCA[79]求解式(2)来获得网络监测数据的低秩子空间(UR(UR)T)，并将原始数据投影至低秩子空间，得到正常数据：M=UR(UR)TX.

为了求解式(2)，研究[12,78]首先计算数据矩阵X的协方差矩阵Cov(X)，然后通过奇异值分解方法得到协方差矩阵的奇异值{σ1,σ2,…,σn}与特征矩阵U，并选择R个最大的奇异值所对应的特征向量(主成分)构成特征矩阵UR，最后将原始数据矩阵X投影到特征矩阵所构成的空间P=UR(UR)T上，从而得到正常数据M.

通过PCA完成正常数据的提取后，为了实现异常检测，基于PCA的异常检测方法又可以细分为基于子空间残差分析的异常检测方法与基于主成分方向变化的异常检测方法两大类，接下来讲具体介绍这2类方法.

3.1.1 基于子空间残差分析的异常检测方法

基于子空间残差分析的异常检测方法[12,78,89-90]，在获得低秩的正常数据M后，为了能够准确检测并定位异常，直接计算原始数据与正常数据之间的残差子空间(X-M)，并对残差子空间进行阈值判断.当残差大于阈值时，则定义该位置为异常数据，否则为正常数据.

下面将介绍2种阈值设计方案[12,78]，首先定义残差子空间中各位置的平方预测误差(squared prediction error, SPE)为

其中,xij与mij分别表示原始监测矩阵与正常数据阵中第i行、第j列的元素值.

基于Q统计量的方法，定义阈值为

其中,

为第j个特征值，cα是标准正态分布中的1-α分位数，α通常取0.001.当

时，则认为该位置出现了异常，否则为正常.其中

表示置信度为1-α时SPE的异常检测阈值.

EWMA(exponential weighted moving average)方法根据最近的历史数据预测下一个时刻的数据，在第t个时刻预测的残差值可以记作

在第t个时刻真实的残差值可以记作SPEt，则第t+1个时刻预测的残差值

为

其中0≤α≤1是历史数据的相对权重，亦称为平滑指数.

通过式(5)求取实际值和预测值之差的绝对值

称为EWMA统计量，该统计量的极限为

其中,μm表示EWMA统计量的均值，σm表示EMWA统计量的均方差，α表示平滑指数，L为超参数常数，T表示时刻.同样地，当

时，判定该位置为异常，否则为正常数据.

另一方面，由于基于残差分析的异常检测方法需要获得正常子空间的前提是对原始数据进行低秩分解，而这一过程计算代价非常高.文献[91-92]为了让这一类方法更适用于大规模网络的异常检测任务，提出了一种分布式的主成分分析方法，将原本的中心化异常检测转变为分布式异常检测.这种方法为每一个网络监测节点设置一个监测过滤窗口，当且仅当该监测节点中新来临的数据不属于该监测过滤窗口内，才将该数据向中心节点上传于更新.而中心节点则根据各监测节点上传的数据进行参数更新，而不是通过精确的全局数据进行更新，并在更新后将结果下发到各个监测节点.这就使得计算代价大大降低，同时实现了分布式的异常检测.

文献[93]提出了MSPCA的方法.这种方法结合小波变换[94]抽取信号确定性特征的能力以及主成分分析方法抽取多元变量共有模式的能力，更好地实现了正常子空间的获取.该方法首先采用标准正交小波变化W对网络监测数据矩阵X进行多尺度分解，获得各个尺度的小波系数矩阵Z,并利用主成分分析方法对矩阵Z进行重构，然后采用小波逆变换WT还原网络监测数据矩阵

最后利用主成分分析方法将还原得到的矩阵进行重构得到最终的正常子空间矩阵

为了利用该方法实现在线的网络异常检测，文献[93]提出了滑动窗口的模型来降低计算代价.

基于子空间残差分析的异常检测方法通常针对全网所有时刻的性能数据进行设计，并通过将原始数据分为正常子空间与异常子空间进行异常检测.在异常子空间内，我们可以判断是否存在异常数据，同时可以通过异常空间定位异常数据所在具体时刻与位置，如图4所示，稀疏矩阵E中第2行第4列的元素，表示第2个OD对在第4个时刻发生了异常.因此这些方法适合部署于网络数据中心的离线异常检测与定位任务中.

3.1.2 基于主成分方向变化的异常检测方法

基于主成分方向变化分析的异常检测方法[95-96]不同于3.1.1节的残差分析方法，这一类方法并不需要计算原始数据与正常数据之间的残差，而仅需对比前后2时刻下PCA所求主成分的变化来检测异常.

PCA作为一种降维方法，通常以最小化各个数据样本到主成分之间的距离之和为目的，进行优化求解.以图5为例，降维后的主成分方向表示为图5(a)中左侧图的实线箭头所示的新坐标轴，而原始坐标轴则代表原始空间.图5中的小圆圈则表示历史数据样例，当新的数据样例到来时，将在不同程度上影响主成分的方向，尤其是当新来的数据为异常数据(方块)时，由于新数据严重偏离正常数据，通常会使得主成分的方向将发生巨大的偏移(如图5(a)的右侧图所示)；反之，当新来的数据为正常数据(圆圈)时，主成分的方向则并不会发生较大偏移(如图5(b)右侧图所示).正是利用PCA的这一特性，基于主成分方向变化的异常检测方法通常适用于判别新来临的数据是否为异常数据.

由于传统的PCA通常处理向量类型数据，在实际网络的异常检测任务中，网络数据往往建模成为矩阵模型，传统的PCA需要将矩阵模型向量化，以便检查当前时刻是否存在异常.文献[97]提出，蕴含在数据内部的空间相关性将因为向量化过程出现丢失，因此，文献[97]提出使用双向2维PCA来计算网络数据矩阵的主成分，并利用所求主成分来进行异常检测.

首先，将历史的网络数据通过双向2维PCA，计算得到矩阵行列2个空间的历史主成分uhistory，vhistory.如图6所示，通过双向2维主成分分析方法，原始数据从3维降到2维与1维.时刻t下的主成分由u1(t),u2(t)与v1(t)组成，其中u1(t),u2(t)为行空间主成分，v1(t)为列空间主成分；而时刻t+1的主成分由u1(t+1),u2(t+1)与v1(t+1)组成.

为了计算主成分方向的偏移，将行列2个空间的主成分进行拼接，然后通过式(7)计算前后2个时刻的主成分方向之间的夹角来定义其偏移量的大小.

其中,Mt=[Ut,Vt]，Mt+1=[Ut+1,Vt+1]，Vec()为矩阵向量化.最后，通过历史数据的预训练或者专家经验来设定阈值，并与Cosine进行比较，以判断数据是否为异常或是否存在异常.

尽管文献[95-96]所提方法可以准确地检测到一些偏离正常模式较大的异常数据，但随着历史数据的不断积累，新来临的异常数据对主成分方向的影响将越来越小.为了维持新来临数据对主成分方向的影响，文献[95,97]提出一种数据过采样(over-sampling)的方法，将新来临的数据复制α×T遍，并更新主成分unew.其中，α为过采样倍数，一般设置α=0.1，T为历史时刻数.另外，这一方法在计算主成分时需要利用奇异值分解或者特征值分解的方法，通常需要高昂的计算代价.为了实现在线网络异常检测，文献[95,97-100]提出了增量更新的过程，这些更新方法不需要重复地进行主成分计算，不需要保存历史数据，而仅需利用新来临数据直接更新主成分方向.

基于主成分方向变化的异常检测方法通常利用历史时刻的网络性能数据训练主成分，并对新时刻的网络性能数据进行实时分析，通常可以判断数据为异常数据，而无法对异常数据所在位置与时刻进行定位，因此适合部署于网络数据中心或小型网络设备的在线异常检测与告警任务中.

3.2 基于RPCA的异常检测方法

基于PCA的异常检测方法，在异常检测过程并没有对异常数据进行约束，而仅使用Frobenius范数约束所得剩余残差来表征异常数据的分布.Frobenius范数为数据内部各项元素的绝对值平方的总和，即约束数据内部的数值大小，当异常数据符合较小的高斯分布时，异常检测效果可以得到保证.然而，当异常数据中存在较大值(尖锐)时，会在不经意间污染主成分分析的正常子空间(即网络性能数据的低秩性特征)，从而扭曲正常的定义[101]，并最终影响异常检测的精度.

为了解决该问题，并保证异常检测的精度，需要对异常数据进行有效约束.由于网络异常数据具有稀疏性的特点，因此，通常使用L0范数来约束异常数据的分布:

然而，针对L0范数与rank()的约束求解过程比较困难，为此，基于RPCA的异常检测方法[88,102-106]提出对L0范数与rank()问题进行松弛化处理，使用核范数代替rank()约束来提取正常数据，并使用L0范数的最优凸近似(L1范数)来约束异常数据:

其中，L1范数表示数据内部的每个元素绝对值之和，这就使得异常检测方法可以在异常数据中存在较大值时，保证网络异常检测的精度.

大量文献提出求解式(9)的方法.例如，基于标准内点法(standard interior point methods)[107]被率先提出来求解该问题，但是由于该方法需要非常高的计算代价，因此并不适合用于大规模矩阵处理；为了让算法更具可扩展性，文献[108]提出了奇异值阈值算法(singular value thresholding, SVT)来处理核范数约束问题；文献[109]所提的迭代阈值方法(iterative thresholding, IT)能够实现可扩展性更高的优化方案，但其收敛速度相对缓慢；文献[110]提出了包括加速近端梯度方法(accelerated proximal gradient, APG)与梯度上升方法(gradient-ascent)，然而这2种算法在实际应用中依然出现了收敛缓慢的问题；文献[111]提出2种增广拉格朗日方法，其中一种为精确增广拉格朗日(exact augmented Lagrange multipliers)能够实现Q-linear的收敛速度，另一种非精确增广拉格朗日(inexact augmented Lagrange multipliers)方法收敛速度与精确增广拉格朗日方法相似，却在低秩分解问题上实现了计算代价的优化，相较于加速近端梯度方法能够提高近5倍的计算速度，然而这2种方法将低秩约束问题与稀疏异常约束问题合并在一起进行优化，而没有将它们作为可分离的2个子问题进行考虑，依然存在缺陷.

为此，文献[112-114]提出了一种交替方向乘子法(alternating direction method of multipliers, ADMM),通过中间变量将2个子问题进行分离求解，从而获得更好的异常检测效果.通过引入中间变量Z将式(10)转化为

其中中间变量Z为乘子的线性约束，β>0为违反线性约束的惩罚参数，〈·,·〉为标准的内积函数.

最后，各个参数更新为：

其中,

是通过矩阵

进行奇异值分解求得，而

{A∈

m×n|-γ/β≤Aij≤γ/β}.最终，所求矩阵L即为正常数据矩阵，而矩阵E即为稀疏异常矩阵.

经过对式(9)的研究，不少变种方法被应用于数据分离，并取得了不错的效果.例如，文献[115]提出了一种固定秩的方法，将低秩矩阵的秩固定为r，并提出优化目标函数：

而文献[116]提出了一种增量秩的方法来改进式(14)的固定秩的方法，这种方法通过逐步增加秩的大小来进行启发式学习，以学习到最优秩，从而实现更高的异常检测精度.

文献[117]提出了一种归纳方法：

其中矩阵P为低秩投影矩阵，这一优化问题则可通过非精确的增广拉格朗日方法[111]进行求解.

文献[118]提出了使用2维PCA(2D-PCA)来实现异常检测，该方法使用2维PCA替代奇异值分解方法，以实现更多信息的提取从而提高异常检测精度：

另外，由于网络数据是以流数据的形式源源不断到来的，为了能够实现实时的网络异常检测，文献[119-124]提出了增量更新的方法，这些方法仅需利用新来临的数据更新优化方法中的对应参数，而不需要利用整体数据进行重复计算.这些方法一方面降低了优化算法的计算代价，另一方面降低算法对存储空间的需求，可以使得基于鲁棒的主成分分析方法的异常检测算法更适用于简单网络设备以及在线网络异常检测过程.

基于RPCA的异常检测方法通常针对所有时刻的全网性能数据进行设计，并利用数据分离的方法实现异常检测，因此适合部署于网络数据中心的离线异常检测与定位任务中.其中文献[119-124]所提的改进方案，由于在计算复杂度上进行了有效改进，因此同样适合部署于在线异常检测与定位任务中.

3.3 基于直接矩阵分解的异常检测方法

尽管基于RPCA的异常检测方法被证明对于尖锐的异常数据更具鲁棒性，却利用凸松弛技术来实现对原始约束问题的求解，这就使得异常检测精度仍然较低.原始约束问题为：

为了直接求解式(17)的原始问题，文献[125]提出了基于直接矩阵分解的异常检测方法，该方法使用块坐标下降(block coordinate descent)方法来求解，将原始问题的求解过程转化为迭代求解2个子问题.

低秩估计子问题：

异常检测子问题：

异常检测子问题求解过程为：首先计算原始矩阵X与低秩估计子问题的解M之间的残差S；然后将残差矩阵S中的元素进行降序排序，保留前e个元素，其余位置的元素都置为0，最终得到稀疏异常矩阵E.

文献[126-128]提出一种轻量级的矩阵分解方法，该方法通过实验分析发现基于L0范数的异常检测方法在实际应用过程中呈现一种“异常位置快速收敛”的性质.这种性质使得稀疏异常矩阵E的非零元素所在位置能够快速确定下来，在迭代过程很少发生改变，甚至不改变，而唯一发生变化的是，稀疏异常矩阵中非零元素的大小.正是利用这一性质，所提轻量级的矩阵分解方法可以通过重用上一轮迭代的低秩估计结果，从而降低算法计算代价，以适应更大规模的数据处理.

基于直接矩阵分解的异常检测方法与基于RPCA的异常检测方法类似，利用数据分离的方法实现异常检测，因此适合部署于网络数据中心的离线异常检测与定位任务中.

3.4 其他异常检测方法

除了3.1～3.3节所述的3种不同约束的异常检测方法，少数研究提出了一些特殊范数约束[125-126,128-130]，这些范数约束在不同角度上加强了对异常数据部分的约束，从而提高异常检测算法的精度.

文献[130]提出了card范数来约束异常数据的稀疏性：

其中，card范数本质上与L0范数一致，该范数通过保留异常矩阵中最大的ε个元素来实现稀疏性约束.

在实际网络中，在数据遭到持续污染的情况下会造成矩阵行中多个元素被污染，如图7所示.当第5个位置的数据遭受持续不断的污染时，第5行中所有元素都为异常数据，为了解决这种结构化异常的问题，文献[125-126,128]提出了一种L2,0范数来约束异常数据.

而为了求解这种约束问题，首先计算原始矩阵X与低秩估计子问题的解M之间的残差S，然后对残差矩阵S的每一行求和，并将每一行的和进行排序，保留最大的ε行，其余行则归0.

如文献[131]所述，文献[88]所提的L1范数与核范数并不是严格的(tight)约束，这就使得所求解并不一定是可信解.为此提出了另外的非凸松弛范数(如式(22)所示)，使用Schatten-p范数来代替核范数约束，使用lq范数来代替L1范数约束，以此加强对正常数据的低秩约束以及异常数据的稀疏约束.

式(22)同样可以被表达为：

其中σi(M)表示矩阵M的第i奇异值.该优化问题则通过近端迭代重加权算法(proximal iteratively reweighted algorithm, PIRA)进行求解.

其他异常检测方法利用数据分离的方法实现异常检测，因此同样适合部署于网络数据中心的离线异常检测与定位任务中.另外，由于对异常数据的不同约束，文献[125-126,128]所提出的使用L2,0范数来约束异常数据的方案，可用于结构化的异常检测与定位任务中.

4 基于张量模型的异常检测方法

尽管第3节所述的异常检测方法取得了不错的效果，最近一些研究[82]却表明网络监测数据建模成为矩阵的表征形式，丢失了蕴含在数据内部的高阶结构化信息，难以表征多模式数据的多维本质.而张量模型作为矩阵模型向多维的扩展，可以表征多模式数据的多维本质，张量模型不再局限于数据内比较简单的2维线性关系，而是将多维放到一起综合考虑，探索多因子、多成分、多线性关系，具有重要的学术价值和应用前景.其已经开始被应用到计量化学、信号处理、机器学习、计算机视觉、认知科学等科学领域[132-135].因此，一部分研究为了充分挖掘网络性能数据内部蕴含的高阶结构化特征，提出将网络监测数据建模成为张量模型.

为了能够更简单、清晰地表达，本文将使用3维张量作为例子进行描述，在实际应用中，张量模型的维度可以大于等于3维.如图8(a)所示，3维张量为长方体的模型，其3个维度分别表示源节点、目的节点、时间，其中元素表示对应时刻下OD对之间监测的网络性能数据；在一些研究中3维张量模型则表现为图8(b)的形式，其3个维度分别表示为节点-目的节点对、天、时间，其中元素则表示为某一OD对在某天的某一时刻下监测的网络性能数据.

正是利用张量模型，大量研究[136-137]通过将基于矩阵模型的算法拓展至张量模型X′，从而实现了更高的异常检测精度.接下来，本节将根据对异常数据的不同约束条件，分类介绍各种异常检测方法并总结分析.

与矩阵模型下的基于PCA的异常检测方法类似，文献[138]将数据建模成为张量模型,实现了基于张量模型的残差分析异常检测方法，该方法通过张量分解算法[139]获得低秩的正常子空间M′.然后计算原始数据X′与正常数据

之间的残差子空间(X′-M′)来进行阈值判断.当残差大于阈值时，则定义该位置为异常数据.

与矩阵模型下的PCA异常检测方法类似，文献[138]的方法更适合部署于网络数据中心的离线异常检测与定位任务中.

同样地，一些研究将基于主成分方向变化的异常检测方法拓展至张量模型.通过各种张量分解的方法，将网络数据构成的张量模型分解成为多个维度的特征矩阵(可视为不同维度的主成分)，并通过分析它们的变化来达到异常检测的目的.例如，文献[140]将网络监测数据建模为如图9所示的模型，其3个维度分别对应源节点、目的节点、对象，对象可以包括不同的监测数据类型或者监测对象.随着时间的推移，每一个时刻都将形成这样一个张量模型.为了检测每一个时刻是否存在异常，提出了使用HOOI的方法将张量分解为3个因子矩阵U1,U2,U3与核心张量G ′的表达模式

如图10所示.

通过分析不同时刻下因子矩阵的变化来判断该时刻是否存在异常，由于不同时刻下的网络接入节点个数不一定相同，使得因子矩阵U1,U2的规模在不同时刻下也不同，也就不能直接使用欧氏距离进行变化的测量，而是使用Grassmann距离[141]来计算：

其中,ζ为各因子矩阵行数的最小值，而θk(Ui(t),Ui(t+1))则表示因子矩阵Ui(t),Ui(t+1)的Grassmann距离.最后，通过判断该距离是否大于阈值μd+2σd来确定是否为异常，当距离大于该阈值时该时刻下存在异常数据，否则为正常数据.其中

由于文献[140]是基于因子矩阵的差异来实现异常检测，而非数据分离，且HOOI方法的计算复杂度较高.因此该方案更适合部署于网络数据中心的离线异常检测与告警任务中.

相似地，文献[140]将网络监测数据建模成如图11所示的2个张量模型，其中一个为网络流数据构成，另一个为网络拓扑数据构成，张量模型的3个维度分别为源节点、目的节点和时间.

同样将图11中的张量模型通过HOOI的方法分解为3个因子矩阵与核心张量，不同的是，该方法仅仅分析时间维度的因子矩阵Utime(t).这一方法通过综合分析网络拓扑与网络流量的变化来检测异常.为了实现这一目的，该方法将2个数据张量经过分解后所得时间维度因子矩阵进行拼接

然后通过式(25)计算该矩阵的Hotelling T2统计量，最后通过该统计量进行异常的判定.

其中,μ为均值，Cov(X)为协方差矩阵.

同样地，与矩阵模型下基于RPCA的异常检测方法类似，文献[102,142]将数据建模成为高阶张量模型X′,并同样使用核范数与L1范数约束正常数据与异常数据，从而得到优化问题：

为了求解式(26)的问题，同样采用了增广拉格朗日的方法引入中间变量进行求解.不同的是为了求解张量模型的核范数约束问题，文献[143]首先将张量模型按照各个维度展开，并针对各个维度展开下的矩阵进行奇异值分解，从而得到各自的低秩估计.而文献[102,144]则同样使用ADMM方法进行求解，不同的是,它们结合T-SVD[145]算法进行式(26)的更新.

文献[140,146]同样提出将数据建模成为张量模型，却分别利用CP分解方法和Tucker分解方法来求解张量模型的核范数约束问题，并使用软阈值方法，在更新异常数据张量E时，将张量中小于阈值的元素归为0，以实现稀疏化约束.

与矩阵模型下基于直接矩阵分解方法的异常检测方法类似，文献[147]将网络流量数据建模为张量X′(如图8(b)所示)，并提出基于L0范数约束的张量恢复算法(式(27)所示)，通过学习网络数据中的高阶结构化信息，从而实现更高精度的异常检测.

其中rank(M′)≤rank(r1,r2,r3)表示该张量在3个不同维度下所形成展开矩阵的秩约束，而E′为L0范数约束的稀疏异常张量.同样地，利用块坐标下降方法将该问题转化为低秩估计子问题与异常检测子问题.不同的是，文献[147]为了快速求解式(27)的多元秩约束的低秩估计子问题以满足大规模网络数据处理的需求，提出了一种连续截断的张量分解方法.

文献[147]所提方法使用数据分离的方法实现异常检测，然而张量分解算法的计算复杂度通常较高.因此，这一类方法更适合部署于网络数据中心的离线异常检测与定位任务中.

尽管文献[147]所提方法能够加速异常检测过程，却仍然无法满足在线的网络异常检测任务.为此，文献[76]提出了一种在线网络异常检测模型，如图12所示.首先将网络流量数据建模成为张量模型，然后定义一个滑动窗口，当新时刻数据来临时，删除窗口内最老的数据，从而保证数据量的同时维持数据的有效性.

在新数据来临时，为了能够及时检测并报告异常的位置，文献[76]提出了一种基于CP分解重用的技术，仅需存储少数小规模中间变量，便能够利用新来临数据更新低秩估计子问题中所求解.根据文献[76]所述，该方法能够实现与文献[147]相似的检测精度，却能够满足在线网络异常检测的计算速度要求.

尽管文献[76]所提方案使用数据分离的方法实现异常检测，但是得益于其模型的设计与计算复杂度的大幅度降低，该方法适合部署于网络数据中心的在线异常检测与定位任务中.

根据文献[148]所述，尽管张量模型能够充分网络数据中的高阶结构化信息，却仅考虑了数据内部的线性特征(低秩)，而忽略了可能出现的非线性特征.对于网络数据，源节点域、目的节点域和时间域之间除了线性相关性外，还存在一些非线性邻近信息[84-85,148].例如，同一网络拓扑在某个特定时间(即办公时间、休息时间)应具有相似的流量数据，因此网络性能数据应包含时间邻近信息.而根据节点扮演的角色，网络中的节点可以分为多种不同的类别，例如正常的终端用户和功能强大的服务器.相同类别的节点可能具有相似的网络访问模式，并产生相似的流量负载，从而导致流量数据具有源节点邻近性和目的节点邻近性.因此，文献[148]提出了一种基于流形学习的方法来将这种非线性特征融入异常检测问题中，并提出优化目标函数：

其中Otime,Oori,Odes分别表示与时间邻近度、源节点邻近度和目的节点邻近度相对应的约束.这3个邻近度分别表示为

其中A,B,C为CP分解中因子矩阵，而La,Lb,Lc分别是时间邻居图、源节点邻居图、目的节点邻居图的拉普拉斯矩阵.

5 方法比较

网络空间安全已经成为国家安全的重要组成部分，异常检测成为网络管理的重要部分之一.而数据挖掘、机器学习、深度学习等领域的快速发展为网络异常检测提供了坚实的理论依据.基于低秩分解的网络异常检测作为一种无监督的异常检测方法，吸引了越来越多的学者们进行深入研究.然而，不同的方法由于约束条件的不同和优化求解方式的不同，达到异常检测精度与计算速度也不同.本节将对基于低秩分解的网络异常检测方法进行了总结以及优缺点的分析，如表4所示：

6 挑战与展望

近年来，尽管基于低秩分解的网络异常检测受到了越来越多学者的关注，各种新的研究方法与成果不断涌现，但当前的异常检测研究还处于学术研究的阶段，基于低秩分解的网络异常检测仍然面临着诸多挑战.例如，异常检测方法对于网络特性与领域知识的融合问题，异常检测算法与模型的适应性问题，以及异常检测的后续任务研究问题.这些挑战将推动这一研究方向往更深入的方向不断发展.总的来说，未来的研究方向将主要包括3个方面：

1) 网络特性与领域知识的融合问题.现有基于低秩分解的异常检测模型通常仅约束了正常网络数据的低秩性与异常数据的稀疏性等特点，缺乏对实际网络环境中存在的特征约束，例如网络连通性约束、网络带宽约束、网络流量约束.而这些网络特有的约束通常能够帮助网络管理中心判断数据的正常与否，以及协助网络数据轮廓、特征、模型的构造.另外，网络异常检测模型可以分析与利用的计算机网络领域知识越来越丰富，例如网络拓扑信息、网络设备信息等.

然而，网络特性与领域知识通常并不能表示为欧氏空间数据，难以融入现有的方法.因此，如何设计算法模型，将计算机网络特性与领域知识融入基于低秩分解的异常检测模型中，并提出对应的求解方法，以提高异常检测精度是未来的研究方向之一.

2) 异常检测算法与模型的适应性问题.现有的算法与模型在数据与设备上存在一系列适应性问题.例如，基于低秩分解的异常检测方法通常建立在数据的完整性上，当数据存在大量缺失时，其异常检测的精度会遭到较大的影响.一方面，完整的网络数据采集代价较大，另一方面，数据在传输过程中往往会存在不可避免的丢失，所以网络数据通常会存在缺失的问题.而对存在缺失的网络数据环境进行异常检测充满了挑战.因此，如何设计算法在数据缺失的情况下准确分离正常数据与异常数据，从而保证异常检测精度，将会是未来的研究方向之一.

另外，在实际网络中，网络设备的存储代价与计算代价有限，现有的基于低秩分解的异常检测算法大多针对网络监控中心设计，需要较高的计算以及存储能力.因此，如何将现有算法模型进行压缩，而不损失其异常检测精度，以保证简单网络设备能够进行分布式的异常检测，减少对网络监控中心的依赖，将会是未来的研究方向之一.

3) 基于异常检测的预测分析与根因分析问题.现有的网络异常检测方法通过分析测量到的网络数据来实现，却无法对网络异常进行有效预测.在网络管理中，如何对网络异常进行预测，并根据预测结果进行事先诊断与预防十分重要.因此，如何通过对历史异常数据的分析，来预测未来发生异常的位置以及时间，是未来的研究方向之一.

另外，在实际的网络管理场景中，通过基于低秩分解的网络异常检测方法可以分离得到稀疏异常数据.尽管可以通过稀疏异常数据进行异常定位与检测，却无法进行进一步的异常根因溯源以及有效进行恢复与管理.因此，如何通过分析发生异常的种类、分布以及时间来确定发生异常的根因，是未来的研究方向之一.

作者贡献声明：李晓灿负责论文的撰写与修改；谢鲲负责论文结构设计与指导，以及论文部分章节的修改；张大方负责各方法的整理与校对，以及论文修订；谢高岗负责部分章节内容的撰写与修改.

[1]Thottan M, Ji Chuanyi. Anomaly detection in IP networks[J]. IEEE Transactions on Signal Pocessing, 2003, 51(8): 2191-2204

[2]Kolias C, Kambourakis G, Stavrou A, et al, DDoS in the IoT: Mirai and other botnets[J]. Computer, 2017, 50(7): 80-84

[3]Yan Qiao, Yu F R, Gong Qingxiang, et al, Software-defined networking (SDN) and distributed denial of service (DDoS) attacks in cloud computing environments: A survey, some research issues, and challenges[J]. IEEE Communications Surveys, 2015, 18(1): 602-622

[4]Deshpande S, Thottan M, Sikdar B. Early detection of BGP instabilities resulting from Internet worm attacks[C] //Proc of the 4th IEEE Global Telecommunications Conf. Piscataway, NJ: IEEE, 2004: 2266-2270

[5]Silva Sérgio S C, Silva Rodrigo M P, Raquel C G, et al. Botnets: A survey[J]. Computer Networks, 2013, 57(2): 378-403

[6]Li Chao, Wei Jiang, Xin Zou, Botnet: Survey and case study[C] //Proc of the 4th Int Conf on Innovative Computing, Information and Control. Piscataway, NJ: IEEE, 2009: 1184-1187

[7]Fordoński R, Kasprzak W. WannaCry ransomware cyberattack as violation of international law[J]. Studia Prawnoustrojowe, 2019, 44(1): 47-73

[8]Baek S, Kwon D, Suh S C, et al. Clustering-based label estimation for network anomaly detection[J]. Digital Communications and Networks, 2021, 7(1): 37-44.

[9]Thottan M, Liu Guanglei, Ji Chuanyi. Anomaly Detection Approaches for Communication Networks[M]. Berlin: Springer, 2010: 239-261

[10]Barnett V. The study of outliers: Purpose and model[J]. Journal of the Royal Statistical Society: Series C (Applied Statistics), 1978, 27(3): 242-250

[11]Chandola V, Banerjee A, Kumar V. Anomaly detection: A survey[J]. ACM Computing Surveys, 2009, 41(1): 1-15

[12]Lakhina A, Crovella M, Diot C. Diagnosing network-wide traffic anomalies[J]. ACM SIGCOMM Computer Communi-cation Review, 2004, 34(4): 219-230

[13]Hoque N, Bhuyan M H, Baishya R C, et al. Network attacks: Taxonomy, tools and systems[J]. Journal of Network and Computer Applications, 2014, 40(1): 307-324

[14]Hawkins D M. Identification of Outliers[M]. London: Chapman and Hall, 1980: 1-200

[15]Ahmed M, Mahmood A N, Hu Jiankun. A survey of network anomaly detection techniques[J]. Journal of Network and Computer Applications, 2016, 60(1): 19-31

[16]Ahmed M, Mahmood A N. Novel approach for network traffic pattern analysis using clustering-based collective anomaly detection[J]. Annals of Data Science, 2015, 2(1): 111-130

[17]Jeya P G, Ravichandran M, Ravichandran C S. Efficient classifier for R2L and U2R attacks[J]. International Journal of Computer Applications, 2012, 45(21): 28-32

[18]Sornsuwit P, Jaiyen S. Intrusion detection model based on ensemble learning for U2R and R2L attacks[C] //Proc of the 7th Int Conf on Information Technology and Electrical Engineering (ICITEE). Piscataway, NJ: IEEE, 2015: 354-359

[19]Bontemps L, Cao V L, McDermott J, et al. Collective anomaly detection based on long short-term memory recurrent neural networks[C] //Proc of the 6th Int Conf on Future Data and Security Engineering. Berlin: Springer, 2016: 141-152

[20]Ahmed M, Mahmood A N. Network traffic analysis based on collective anomaly detection[C] //Proc of the 9th IEEE Conf on Industrial Electronics and Applications. Piscataway, NJ: IEEE, 2014: 1141-1146

[21]Song Xiuyao, Wu Mingxi, Jermaine C, et al. Conditional anomaly detection[J]. IEEE Transactions on Knowledge and Data Engineering, 2007, 19(5): 631-645

[22]Pang Guansong, Shen Chunhua, Cao Longbing, et al. Deep learning for anomaly detection: A review[J]. ACM Computing Surveys, 2021, 54(2): 1-38

[23]Blázquez-García A, Conde A, Mori U, et al. A review on outlier/anomaly detection in time series data[J]. arXiv preprint, arXiv: 2002.04236, 2020

[24]Baddar S, Merlo A, Migliardi M. Anomaly detection in computer networks: A state-of-the-art review[J]. Journal of Wireless Mobile Networks Ubiquitous Computer Dependable Appllication, 2014, 5(4): 29-64

[25]Haji H, Ameen Y. Attack and anomaly detection in IoT networks using machine learning techniques: A review[J]. Asian Journal of Research in Computer Science, 2021, 21(5): 30-46

[26]Nassif A B, Talib M A, Nasir Q, et al. Machine learning for anomaly detection: A systematic review[J]. IEEE Access, 2021, 9: 256-271

[27]Agrawal S, Agrawal J. Survey on anomaly detection using data mining techniques[J]. Procedia Computer Science, 2015, 60(2): 708-713

[28]Knorr E M, Ng R T. Algorithms for mining distance-based outliers in large datasets[C] //Proc of the 24th Very Large Data Bases Conf. New York: ACM, 1998: 392-403

[29]Knorr E M, Ng R T. Finding intensional knowledge of distance-based outliers[C] //Proc of the 25th Very Large Data Bases Conf. New York: ACM, 1999: 211-222

[30]Angiulli F, Basta S, Pizzuti C. Distance-based detection and prediction of outliers[J]. IEEE Transactions on Knowledge and Data Engineering, 2005, 18(2): 145-160

[31]Orair G H, Teixeira C H C, Meira Jr W, et al. Distance-based outlier detection: Consolidation and renewed bearing[J]. Proceedings of the VLDB Endowment, 2010, 3(1-2): 1469-1480

[32]Petrovskiy M I. Outlier detection algorithms in data mining systems[J]. Programming and Computer Software, 2003, 29(4): 228-237

[33]Breunig M M, Kriegel H P, Ng R T, et al. LOF: Identifying density-based local outliers[C] //Proc of the 11th ACM SIGMOD Int Conf on Management of data. New York: ACM, 2000: 93-104

[34]Koufakou A, Georgiopoulos M. A fast outlier detection strategy for distributed high-dimensional data sets with mixed attributes[J]. Data Mining and Knowledge Discovery, 2010, 20(2): 259-289

[35]Bigdeli E, Mohammadi M, Raahemi B, et al. Incremental anomaly detection using two-layer cluster-based structure[J]. Information Sciences, 2018, 429(5): 315-331

[36]Breunig M M, Kriegel H P, Ng R T, et al. Optics-of: Identifying local outliers[C] //Proc of the 5th European Conf on Principles of Data Mining and Knowledge Discovery. Berlin: Springer, 1999: 262-270

[37]Barford P, Kline J, Plonka D, et al. A signal analysis of network traffic anomalies[C] //Proc of the 2nd ACM SIGCOMM Workshop on Internet Measurment. New York: ACM, 2002: 71-82

[38]Kim S S, Reddy A L N. Statistical techniques for detecting traffic anomalies through packet header data[J]. IEEE/ACM Transactions on Networking, 2008, 16(3): 562-575

[39]Soule A, Salamatian K, Taft N. Combining filtering and statistical methods for anomaly detection[C] //Proc of the 5th ACM SIGCOMM Conf on Internet Measurement. New York: ACM, 2005: 331-344

[40]Ye Nong, Emran S M, Chen Qiang, et al. Multivariate statistical analysis of audit trails for host-based intrusion detection[J]. IEEE Transactions on Computers, 2002, 51(7): 810-820

[41]Barnett V, Lewis T. Outliers in statistical data[J]. Journal of Wiley Series in Probability and Mathematical Statistics, 1984, 2(5): 21-36

[42]Hand D J. Principles of data mining[J]. Drug Safety, 2007, 30(7): 621-622

[43]Wu Xindong, Zhu Xingquan, Wu Gongqing, et al. Data mining with big data[J]. IEEE Transactions on Knowledge and Data Engineering, 2013, 26(1): 97-107

[44]Jordan M I, Mitchell T M. Machine learning: Trends, perspectives, and prospects[J]. Science, 2015, 349(6245): 255-260

[45]Hanguang L, Yu Ni. Intrusion detection technology research based on apriori algorithm[J]. Physics Procedia, 2012, 24(2): 1615-1620

[46]Dong Yuhong, Hsu S, Rajput S, et al. Experimental analysis of application-level intrusion detection algorithms[J]. International Journal of Security and Networks, 2010, 5(2/3): 198-205

[47]Kumar V, Chauhan H, Panwar D. K-means clustering approach to analyze NSL-KDD intrusion detection dataset[J]. International Journal of Soft Computing and Engineering, 2013, 3(6): 2231-2307

[48]Gu Guofei, Perdisci R, Zhang Junjie, et al. Botminer: Clustering analysis of network traffic for protocol-and structure-independent botnet detection[J]. USENIX Security Symposium, 2008, 7(2): 253-275

[49]Komviriyavut T, Sangkatsanee P, Wattanapongsakorn N, et al. Network intrusion detection and classification with decision tree and rule based approaches[C] //Proc of the 9th Int Symp on Communications and Information Technology. Piscataway, NJ: IEEE, 2009: 1046-1050

[50]Sahu S, Mehtre B M. Network intrusion detection system using J48 Decision Tree[C] //Proc of the 12th Int Conf on Advances in Computing, Communications and Informatics (ICACCI). Piscataway, NJ: IEEE, 2015: 2023-2026

[51]Kline J, Nam S, Barford P, et al. Traffic anomaly detection at fine time scales with Bayes nets[C] //Proc of the 3rd Int Conf on Internet Monitoring and Protection. Piscataway, NJ: IEEE, 2008: 37-46

[52]Hoque M S, Mukit M, Bikas M, et al. An implementation of intrusion detection system using genetic algorithm[J]. arXiv preprint, arXiv: 1204.1336, 2012

[53]Li Wei. Using genetic algorithm for network intrusion detection[J]. Journal of the United States Department of Energy Cyber Security Group, 2004, 1(1): 1-8

[54]Xia Tao, Qu Guangzhi, Hariri S, et al. An efficient network intrusion detection method based on information theory and genetic algorithm[C] //Proc of the 24th IEEE Int Performance, Computing, and Communications Conf. Piscataway, NJ: IEEE, 2005: 11-17

[55]Senthilnayaki B, Venkatalakshmi K, Kannan A. Intrusion detection using optimal genetic feature selection and SVM based classifier[C] //Proc of the 3rd Int Conf on Signal Processing, Communication and Networking (ICSCN). Piscataway, NJ: IEEE, 2015: 1-4

[56]Sanchez F, Duan Zhenhai, Dong Yingfei. Blocking spam by separating end-user machines from legitimate mail server machines[J]. Security and Communication Networks, 2016, 9(4): 316-326

[57]Yang Chun, Deng Feiqi, Yang Haidong. An unsupervised anomaly detection approach using subtractive clustering and hidden Markov model[C] //Proc of the 2nd Int Conf on Communications and Networking in China. Piscataway, NJ: IEEE, 2007: 313-316

[58]Goodfellow I, Bengio Y, Courville A. Deep Learning[M]. Cambridge, MA: MIT Press, 2016

[59]Li Zhipeng, Qin Zheng, Huang Kai, et al. Intrusion detection using convolutional neural networks for representation learning[C] //Proc of the 15th Int Conf on Neural Information Processing. Berlin: Springer, 2017: 858-866

[60]Kim T, Suh S C, Kim H, et al. An encoding technique for CNN-based network anomaly detection[C] //Proc of the 26th IEEE Int Conf on Big Data. Piscataway, NJ: IEEE, 2018: 2960-2965

[61]Kwon D, Natarajan K, Suh S C, et al. An empirical study on network anomaly detection using convolutional neural networks[C] //Proc of the 38th Int Conf on Distributed Computing Systems (ICDCS). Piscataway, NJ: IEEE, 2018: 1595-1598

[62]Su Ya, Zhao Youjian, Niu Chenhao, et al. Robust anomaly detection for multivariate time series through stochastic recurrent neural network[C] //Proc of the 25th Int Conf on Knowledge Discovery & Data Mining. New York: ACM, 2019: 2828-2837

[63]Yin Chuanlong, Zhu Yuefei, Fei Jinlong, et al. A deep learning approach for intrusion detection using recurrent neural networks[J]. IEEE Access, 2017, 5: 21954-21961

[64]An J, Cho S. Variational autoencoder based anomaly detection using reconstruction probability[J]. Special Lecture on IE, 2015, 2(1): 1-18

[65]Chen Zhaomin, Yeo C K, Lee B S, et al. Autoencoder-based network anomaly detection[C] //Proc of the 12th Wireless Telecommunications Symp (WTS). Piscataway, NJ: IEEE, 2018: 1-5

[66]Fiore U, Palmieri F, Castiglione A, et al. Network anomaly detection with the restricted Boltzmann machine[J]. Neurocomputing, 2013, 122: 13-23

[67]Nguyen K K, Hoang D T, Niyato D, et al. Cyberattack detection in mobile cloud computing: A deep learning approach[C] //Proc of the 12th IEEE Wireless Communications and Networking Conf (WCNC). Piscataway, NJ: IEEE, 2018: 1-6

[68]Salama M A, Eid H F, Ramadan R A, et al. Hybrid intelligent intrusion detection scheme[M] //Soft Computing in Industrial Applications. Berlin: Springer, 2011: 293-303

[69]Zhao Nengwen, Zhu Jing, Wang Yao, et al. Automatic and generic periodicity adaptation for KPI anomaly detection[J]. IEEE Transactions on Network and Service Management, 2019, 16(3): 1170-1183

[70]Su Ya, Zhao Youjian, Xia Wentao, et al. CoFlux: Robustly correlating KPIs by fluctuations for service troubleshooting[C] //Proc of the 20th Int Symp on Quality of Service. New York: ACM, 2019: 1-10

[71]Xie Yi, Yu Shunzheng. Anomaly detection based on Web users’ browsing behaviors[J]. Journal of Software, 2007, 18(4): 967-977 (in Chinese)(谢逸, 余顺争. 基于Web用户浏览行为的异常检测[J]. 软件学报, 2007, 18(4): 967-977)

[72]Li Yang, Fang Binxing, Guo Li, et al. A network anomaly detection method based on transduction scheme[J]. Journal of Software, 2007, 18(10): 2595-2604 (in Chinese)(李洋, 方滨兴, 郭莉, 等. 基于直推式方法的网络异常检测方法[J]. 软件学报, 2007, 18(10): 2595-2604)

[73]Meng Weibin, Liu Ying, Zhu Yichen, et al. LogAnomaly: Unsupervised detection of sequential and quantitative anomalies in unstructured logs[C] //Proc of the 30th Int Joint Conf on Artificial Intelligence. Piscataway, NJ: IEEE, 2019: 4739-4745

[74]Feng Cheng, Li Tingting, Chana D. Multi-level anomaly detection in industrial control systems via package signatures and LSTM networks[C] //Proc of the 47th Annual IEEE/IFIP Int Conf on Dependable Systems and Networks (DSN). Piscataway, NJ: IEEE, 2017: 261-272

[75]Stallings W. SNMP and SNMPv2: The infrastructure for network management[J]. IEEE Communications Magazine, 1998, 36(3): 37-43

[76]Li Xiaocan, Xie Kun, Wang Xin, et al. Online Internet anomaly detection with high accuracy: A fast tensor factorization solution[C] //Proc of the 23rd Conf on Computer Communications. Piscataway, NJ: IEEE, 2019: 1900-1908

[77]Liu Hancong, Shah S, Jiang Wei. On-line outlier detection and data cleaning[J]. Computers & Chemical Engineering, 2004, 28(9): 1635-1647

[78]Lakhina A, Crovella M, Diot C. Characterization of network-wide anomalies in traffic flows[C] //Proc of the 4th ACM SIGCOMM Conf on Internet Measurement. New York: ACM, 2004: 201-206

[79]Wold S, Esbensen K, Geladi P. Principal component analysis[J]. Chemometrics and Intelligent Laboratory Systems, 1987, 2(1/2/3): 37-52

[80]Medina A, Taft N, Salamatian K, et al. Traffic matrix estimation: Existing techniques and new directions[J]. ACM SIGCOMM Computer Communication Review, 2002, 32(4): 161-174

[81]Zhou Jingjing, Yang Jiahai, Yang Yang, et al. Research development on traffic matrix estimation[J]. Journal of Software, 2007, 18(11): 2669-2682 (in Chinese)(周静静, 杨家海, 杨扬, 等. 流量矩阵估算的研究[J]. 软件学报, 2007, 18(11): 2669-2682)

[82]Xie Kun, Wang Lele, Wang Xin, et al. Accurate recovery of Internet traffic data: A sequential tensor completion approach[J]. IEEE/ACM Transactions on Networking, 2018, 26(2): 793-806

[83]Xie Kun, Peng Can, Wang Xin, et al. Accurate recovery of Internet traffic data under variable rate measurements[J]. IEEE/ACM Transactions on Networking, 2018, 26(3): 1137-1150

[84]Zhang Yin, Roughan M, Willinger W, et al. Spatio-temporal compressive sensing and Internet traffic matrices[C] //Proc of the 18th ACM SIGCOMM Conf on Data Communication. New York: ACM, 2009: 267-278

[85]Roughan M, Zhang Yin, Willinger W, et al. Spatio-temporal compressive sensing and Internet traffic matrices (extended version)[J]. IEEE/ACM Transactions on Networking, 2011, 20(3): 662-676

[86]Gürsun G, Crovella M. On traffic matrix completion in the Internet[C] //Proc of the 22nd Internet Measurement Conf. New York: ACM, 2012: 399-412

[87]Xie Kun, Wang Lele, Wang Xin, et al. Sequential and adaptive sampling for matrix completion in network monitoring systems[C] //Proc of the 25th IEEE Conf on Computer Communications (INFOCOM). Piscataway, NJ: IEEE, 2015: 2443-2451

[88]De la Torre F, Black M J. Robust principal component analysis for computer vision[C] //Proc of the 8th IEEE Int Conf on Computer Vision. Piscataway, NJ: IEEE, 2001: 362-369

[89]Hoang D H, Nguyen H D. A PCA-based method for IoT network traffic anomaly detection[C] //Proc of the 20th Int Conf on Advanced Communication Technology. Piscataway, NJ: IEEE, 2018: 381-386

[90]Camacho J, Pérez-Villegas A, García-Teodoro P, et al. PCA-based multivariate statistical network monitoring for anomaly detection[J]. Computers & Security, 2016, 59(8): 118-137

[91]Huang Ling, Nguyen X, Garofalakis M, et al. Distributed PCA and network anomaly detection[C] //Proc of the 16th NIPS. New York: ACM, 2006: 252-272

[92]Livani M A, Abadi M. Distributed PCA-based anomaly detection in wireless sensor networks[C] //Proc of the 19th Int Conf for Internet Technology and Secured Transactions. Piscataway, NJ: IEEE, 2010: 1-8

[93]Qian Yekui, Chen Ming, Ye Lixin, et al. Network-wide anomaly detection method based on multiscale principal component analysis[J]. Journal of Software, 2012, 23(2): 361-377 (in Chinese)(钱叶魁, 陈鸣, 叶立新, 等. 基于多尺度主成分分析的全网络异常检测方法[J]. 软件学报, 2012, 23(2): 361-377)

[94]Donoho D L, Johnstone I M, Kerkyacharian G, et al. Wavelet shrinkage: Asymptopia?[J]. Journal of the Royal Statistical Society: Series B (Methodological), 1995, 57(2): 301-337

[95]Lee Y J, Yeh Y R, Wang Y C F. Anomaly detection via online oversampling principal component analysis[J]. IEEE Transactions on Knowledge and Data Engineering, 2012, 25(7): 1460-1470

[96]Ding Meimei, Tian Hui. PCA-based network traffic anomaly detection[J]. Tsinghua Science and Technology, 2016, 21(5): 500-509

[97]Xie Kun, Li Xiaocan, Wang Xin, et al. On-line anomaly detection with high accuracy[J]. IEEE/ACM Transactions on Networking, 2018, 26(3): 1222-1235

[98]Artac M, Jogan M, Leonardis A. Incremental PCA for on-line visual learning and recognition[C] //Proc of the 15th Object Recognition Supported by User Interaction for Service Robots. Piscataway, NJ: IEEE, 2002: 781-784

[99]Li Yongmin. On incremental and robust subspace learning[J]. Pattern Recognition, 2004, 37(7): 1509-151

[100]Huang Dong, Yi Zhang, Pu Xiaorong. A new incremental PCA algorithm with application to visual learning and recognition[J]. Neural Processing Letters, 2009, 30(3): 171-182

[101]Ringberg H, Soule A, Rexford J, et al. Sensitivity of PCA for traffic anomaly detection[C] //Proc of the 17th ACM SIGMETRICS Int Conf on Measurement and Modeling of Computer Systems. New York: ACM, 2007: 109-120

[102]Wright J, Ganesh A, Rao S R, et al. Robust principal component analysis with complex noise [C] //Proc of the 25th Int Conf on Machine Learning. New York: ACM, 2014: 55-63

[103]De la Torre F, Black M J. Robust principal component analysis for computer vision[C] //Proc of the 8th IEEE Int Conf on Computer Vision. Piscataway, NJ: IEEE, 2001: 362-369

[104]Zhao Qian, Meng Deyu, Xu Zongben, et al. Robust principal component analysis with complex noise[C] //Proc of the 22nd Int Conf on Machine Learning. New York: ACM, 2014: 55-63

[105]Candès E J, Li Xiaodong, Ma Y, et al. Robust principal component analysis?[J]. Journal of the ACM, 2011, 58(3): 1-37

[106]Paffenroth R, Kay K, Servi L. Robust pca for anomaly detection in cyber networks[J]. arXiv preprint, arXiv: 1801.01571, 2018

[107]Chandrasekaran V, Sanghavi S, Parrilo P A, et al. Rank-sparsity incoherence for matrix decomposition[J]. SIAM Journal on Optimization, 2011, 21(2): 572-596

[108]Cai Jianfeng, Candès E J, Shen Zuowei. A singular value thresholding algorithm for matrix completion[J]. SIAM Journal on Optimization, 2010, 20(4): 1956-1982

[109]Wright J, Ganesh A, Rao S R, et al. Robust principal component analysis: Exact recovery of corrupted low-rank matrices via convex optimization[C] //Proc of the 22nd NIPS. New York: ACM, 2009: 289-298

[110]Lin Zhouchen, Ganesh A, Wright J, et al. Fast convex optimization algorithms for exact recovery of a corrupted low-rank matrix[J]. Coordinated Science Laboratory Report, 2009, 5(2): 11-25

[111]Lin Zhouchen, Chen Minming, Ma Yi. The augmented lagrange multiplier method for exact recovery of corrupted low-rank matrices[J]. arXiv preprint, arXiv: 1009.5055, 2010

[112]Lin Tianyi, Ma Shiqian, Zhang Shuzhong. Global convergence of unmodified 3-block ADMM for a class of convex minimization problems[J]. Journal of Scientific Computing, 2018, 76(1): 69-88

[113]Lin Tianyi, Ma Shiqian, Zhang Shuzhong. On the global linear convergence of the ADMM with multiblock variables[J]. SIAM Journal on Optimization, 2015, 25(3): 1478-1497

[114]Lin Tianyi, Ma Shiqian, Zhang Shuzhong. On the sublinear convergence rate of multi-block ADMM[J]. Journal of the Operations Research Society of China, 2015, 3(3): 251-274

[115]Leow W K, Cheng Yuan, Zhang Li, et al. Background recovery by fixed-rank robust principal component analysis[C] //Proc of the 23rd Conf on Computer Analysis of Images and Patterns. Berlin: Springer, 2013: 54-61

[116]Lai Jian, Leow W K, Sim T. Incremental fixed-rank robust PCA for video background recovery[C] //Proc of the 26th Int Conf on Computer Analysis of Images and Patterns. Berlin: Springer, 2015: 652-663

[117]Bao Bingkun, Liu Guangcan, Xu Changsheng, et al. Inductive robust principal component analysis[J]. IEEE Transactions on Image Processing, 2012, 21(8): 3794-3800

[118]Sun Yipeng, Tao Xiaoming, Li Yang, et al. Robust two-dimensional principal component analysis via alternating optimization[C] //Proc of the 15th IEEE Int Conf on Image Processing. Piscataway, NJ: IEEE, 2013: 340-344

[119]Zhang Zemin, Liu Dehong, Aeron S, et al. An online tensor robust PCA algorithm for sequential 2D data[C] //Proc of the 23rd IEEE Int Conf on Acoustics, Speech and Signal Processing. Piscataway, NJ: IEEE, 2016: 2434-2438

[120]Wang Huahua, Banerjee A. Online alternating direction method (longer version)[J]. arXiv preprint, arXiv: 1306.3721, 2013

[121]Qiu Chenlu, Vaswani N. Real-time robust principal components’ pursuit[C] //Pro of the 48th Annual Allerton Conf on Communication, Control, and Computing (Allerton). Piscataway, NJ: IEEE, 2010: 591-598

[122]Qiu Chenlu, Vaswani N. ReProCS: A missing link between recursive robust PCA and recursive sparse recovery in large but correlated noise[J]. arXiv preprint, arXiv: 1106.3286, 2011

[123]Qiu Chenlu, Vaswani N. Recursive sparse recovery in large but structured noise—Part 2[C] //Prof of the 32nd IEEE Int Symp on Information Theory. Piscataway, NJ: IEEE, 2013: 864-868

[124]Qiu Chenlu, Vaswani N, Lois B, et al. Recursive robust pca or recursive sparse recovery in large but structured noise[J]. IEEE Transactions on Information Theory, 2014, 60(8): 5007-5039

[125]Xiong Liang, Chen Xi, Schneider J. Direct robust matrix factorizatoin for anomaly detection[C] //Proc of the 11th Int Conf on Data Mining, Piscataway, NJ: IEEE, 2011: 844-853

[126]Li Xiaocan, Xie Kun, Wang Xin, et al. Quick and accurate false data detection in mobile crowd sensing[J]. IEEE/ACM Transactions on Networking, 2020, 28(3): 1339-1352

[127]Xie Gaogang, Xie Kun, Huang Jun, et al. Fast low-rank matrix approximation with locality sensitive hashing for quick anomaly detection[C] //Prof of the 23rd Conf on Computer Communications, Piscataway, NJ: IEEE, 2017: 1-9

[128]Li Xiaocan, Xie Kun, Wang Xin, et al. Quick and accurate false data detection in mobile crowd sensing[J]. IEEE/ACM Transactions on Networking, 2020, 28(3): 1339-1352

[129]Xue Zhichao, Dong Jing, Zhao Yuxin, et al. Low-rank and sparse matrix decomposition via the truncated nuclear norm and a sparse regularizer[J]. The Journal of Visual Computer, 2019, 35(11): 1549-1566

[130]Zhou Tianyi, Tao Dacheng. Godec: Randomized low-rank & sparse matrix decomposition in noisy case[C] //Proc of the 28th Int Conf on Machine Learning. New York: ACM, 2011: 22-31

[131]Wang Jing, Wan Meng, Hu Xuegang, et al. Image denoising with a unified schatten-p norm and lq norm regularization[J]. Journal of Optimization Theory and Applications, 2014,21(3): 1562-1572

[132]Han Yufei, Moutarde F. Analysis of large-scale traffic dynamics in an urban transportation network using non-negative tensor factorization[J]. International Journal of Intelligent Transportation Systems Research, 2016, 14(1): 36-49

[133]Cichocki A, Mandic D, De Lathauwer L, et al. Tensor decompositions for signal processing applications: From two-way to multiway component analysis[J]. IEEE Signal Processing Magazine, 2015, 32(2): 145-163

[134]Skibbe H, Reisert M. Spherical tensor algebra: A toolkit for 3D image processing[J]. Journal of Mathematical Imaging and Vision, 2017, 58(3): 349-381

[135]Hazan T, Polak S, Shashua A. Sparse image coding using a 3D non-negative tensor factorization[C] //Proc of the 10th Int Conf on Computer Vision. New York: ACM, 2005: 50-57

[136]Kasai H, Kellerer W, Kleinsteuber M. Network volume anomaly detection and identification in large-scale networks based on online time-structured traffic tensor tracking[J]. IEEE Transactions on Network and Service Management, 2016, 13(3): 636-650

[137]Silva E S, Streit A. Network anomaly detection based on tensor decomposition[C] //Proc of the 18th Mediterranean Communication and Computer Networking Conf. New York: ACM, 2020:12-20

[138]Kim H, Lee S, Ma Xiaoli, et al. Higher-order PCA for anomaly detection in large-scale networks[C] //Proc of the 3rd Int Workshop on Computational Advances in Multi-Sensor Adaptive Processing. Piscataway, NJ: IEEE, 2009: 85-88

[139]Kolda T G, Bader B W. Tensor decompositions and applications[J]. Journal of SIAM, 2009, 51(3): 455-500

[140]Mahyari A G, Zoltowski D M, Bernat E M, et al. A tensor decomposition-based approach for detecting dynamic network states from EEG[J]. IEEE Transactions on Biomedical Engineering, 2016, 64(1): 225-237

[141]Ye Ke, Lim L H. Distance between subspaces of different dimensions[J]. arXiv preprint, arXiv: 1407.0900, 2014

[142]Lu Canyi, Feng Jiashi, Chen Yudong, et al. Tensor robust principal component analysis with a new tensor nuclear norm[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2019, 42(4): 925-938

[143]Goldfarb D, Qin Zhiwei. Robust low-rank tensor recovery: Models and algorithms[J]. Journal on Matrix Analysis and Applications, 2014, 35(1): 225-253

[144]Zhang Zemin, Aeron S. Exact tensor completion using t-SVD[J]. IEEE Transactions on Signal Processing, 2016, 65(6): 1511-1526

[145]Martin C D, Shafer R, LaRue B. An order-p tensor factorization with applications in imaging[J]. SIAM Journal on Scientific Computing, 2013, 35(1): A474-A490

[146]Anandkumar A, Jain P, Shi Yang, et al. Tensor vs matrix methods: Robust tensor decomposition under block sparse perturbations[C] //Proc of the 25th Artificial Intelligence and Statistics. New York: ACM, 2016: 268-276

[147]Xie Kun, Li Xiaocan, Wang Xin, et al. Fast tensor factorization for accurate Internet anomaly detection[J]. IEEE/ACM Transactions on Networking, 2017, 25(6): 3794-3807

[148]Xie Kun, Li Xiaocan, Wang Xin, et al. Graph based tensor recovery for accurate Internet anomaly detection[C] //Proc of the 25th Conf on Computer Communications. Piscataway, NJ: IEEE, 2018: 1502-1510