多时间尺度同步的网络异常检测方法.doc

第12期王风宇等：多时间尺度同步的网络异常检测方法65多时间尺度同步的网络异常检测方法王风宇1,2,3，云晓春1，曹震中4(1. 中国科学院 计算技术研究所, 北京 100080; 2. 山东大学 计算机科学与技术学院, 山东 济南 250101;3. 中国科学院 研究生院, 北京 100039; 4. 曲阜师范大学 计算机科学学院, 山东 曲阜 273165)摘 要：为了改善高速网络环境下异常检测的准确性和及时性，提出了一种多时间尺度同步的异常检测算法DA-MTS。该算法通过无抽取Haar小波变换对网络流量时间序列进行预处理，获得的细节信号逼近高斯白噪声，根据正态分布的“3”法则可以判断细节信号中存在的异常变化。分析和实验表明，该算法能够同时在多个时间尺度上以递推方式进行无延迟的异常检测，不但提高了异常检测的准确性，而且保证了异常发现的及时性。关键词：网络流量；异常检测；时间序列； trous小波变换中图分类号：TP393 文献标识码：A 文章编号：1000-436X(2007)12-0060-06Method of detecting network anomaly on multi-time-scaleWANG Feng-yu1,2,3, YUN Xiao-chun1, CAO Zhen-zhong4(1. Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100080, China;2. School of Computer Science and Technology, Shandong University, Jinan 250101, China;3. Graduate School of Chinese Academy of Sciences, Beijing 100039, China;4. Computer Science College, Qufu Normal University, Qufu 273165, China)Abstract: To detect anomaly timely and precisely in high-speed network, an algorithm, named DA-MTS(detecting anomaly on multi-time-scale synchronously),was proposed. Firstly, pre-process the time series of traffic with non-decimated Haar wavelet transform to produce detail signals, which approximately follow Gaussian white noise. Then detect anomaly based on “3” principal of normal distribution. Analysis and experiments reveal that this algorithm can detect anomaly on several time-scales recursively without delay, so it can detect anomaly precisely and timely.Key words: network traffic; anomaly detection; time series; trous wavelet transform1 引言收稿日期：2007-09-23；修回日期：2007-12-03基金项目：国家自然科学基金资助项目（60573134）；新世纪优秀人才支持计划Foundation Items: The National Natural Science Foundation of China (60573134); The Program for New Century Excellent Talents in University随着Internet规模的不断扩大，网络异常事件的发生也越来越频繁。一方面，蠕虫爆发、DDoS攻击等大规模网络安全事件占用大量的网络和计算资源；另一方面突发访问(flash crowd)及网络故障等非恶意行为也会使流量发生突变，影响正常网络服务。网络的异常通常表现为网络流量的异常，因此实时监测网络流量是保证网络运行的重要手段。网络流量异常检测是指建立网络流量的正常行为模式轮廓，若实时获得的网络流量信息的轮廓值与正常值的差异超出指定的范围，就进行入侵报警1。针对网络流量异常检测已经进行了大量研究，但准确性一直难以令人满意。尽管如此，异常检测在发现未知网络入侵及网络故障检测等方面有着不可替代的作用。随着网络带宽的不断提高，网络流量异常检测面临新的问题：一方面，网络传输速率大幅度提高，相同的网络攻击，在局域网表现非常明显，而在高速线路可能并不容易发现，需要高准确性的网络流量异常检测模型；另一方面，网络带宽提高的同时也加快了网络攻击的速度，以网络蠕虫爆发为例，它能够在10min甚至更短的时间内感染互联网内大部分脆弱主机。基于以上状况，本文提出了一种多时间尺度同步的高速网络异常检测方法DA-MTS。首先采用递推式无抽取Haar小波变换方法分解流量时间序列获得不同时间尺度下的细节信号，然后根据消除冗余后的细节信号分布特征及正态分布的“3”法则判断异常事件的发生，并用前向归并法消除多余的报警。实验证明该算法不但能够准确检测到流量异常，而且报警及时。本文第2节介绍了相关的研究状况；第3节描述了多时间尺度同步的网络异常检测算法；第4节用模拟异常流量对算法进行了测试；最后是全文的结束语。2 相关工作针对网络异常检测开展了大量的研究，目前异常检测方法大致可以归为以下几类：统计方法、机器学习方法、数据挖掘方法等。高速主干网络具有传输速度快、数据量大的特点，传统的机器学习、数据挖掘等异常检测方法的计算效率难以保证在线检测的及时性。基于统计的异常检测方法具有适应能力强、计算效率高的特点，在高速网络流量监测中被较多采用。从流量轮廓获取的角度可以把基于统计的异常检测方法进一步分为两类。第一类是分析特定的细节特征。因为特定的网络入侵方法通常会使某些协议字段或其它特征量的取值或比例发生非常显著的变化。例如文献2通过分析SYN和FIN数据包数量的差异来发现拒绝服务攻击中的SYN-Flooding攻击。然而这类方法有其局限性，入侵方式具有多样性，穷尽搜索理想度量子集的开销是无法容忍的1。第二类是把网络总体流量(packet或flow的数量)作为分析对象。如文献3通过检测滑动窗口中的AR模型残差序列的GLR(generalized likelihood ratio)来发现异常，但GLR方法发现异常的延迟比较大；文献4在AR模型预测的基础上用残差比检测突变点，能够及时报告异常；文献5则通过AAR模型参数的变化检测网络流密度的突变。这类方法所需流量信息易于获取，且不局限于某种流量异常，但由于网络流量的动态性和复杂性，模型的准确性较难保证。研究表明，网络流量在一定的时间尺度范围具有自相似特征6，基于小波变换的流量模型通过伸缩和平移运算对信号进行多尺度分析，能够同时描述时间序列的长相关和短相关特征，从而更加准确地刻画网络流量特征7。文献8,9通过小波变换对网络流量时间序列进行分解，并同时在不同的时间尺度进行检测，使流量异常检测的准确性得到较大提高。但研究中采用的是二次样条小波8或伪样条小波9，会在不同的时间尺度上产生不同程度的异常发现延迟，而且采用的滑动窗口式检测也导致异常发现的延后。3 多时间尺度同步的异常检测算法基于高速网络异常检测的需求以及已有检测方法存在的不足，提出了多时间尺度同步的网络流量异常检测方法DA-MTS。图1是多时间尺度同步的网络流量异常检测算法流程及结构图，作为示例，图中给出了三层小波分解。该算法分为以下步骤：图1 DA-MTS异常检测算法结构及流程1) 采集线路单位时间IP包的数量，构成网络流量时间序列。随着网络带宽快速提高，主机系统中DRAM的访问速度已经落后于高速网络的传输速度，而且这个差距还在不断拉大。在线根据flow或特定协议字段进行统计越来越困难。IP网络传输是以包作为交换单位的，要对网络传输和处理速度产生影响甚至冲击，就会在包的数量上有较大变化10。2) 用无抽取Haar小波变换把流量时间序列分解为不同时间尺度上的信号。把无抽取Haar小波分解预处理用于流量异常检测具有4方面的优势：网络流量具有周期性和趋势性变化，小波分解把流量时间序列分解为不同时间尺度的细节信号和近似信号，使异常流量表现的更加明显；网络业务量具有自相似特征，小波变换对具有长程依赖性的信号能够起到去相关的作用；同时在不同的时间尺度上检测，可以在一定程度上发现逐步提高发包速度的网络入侵；无抽取Haar小波变换具有时移不变性，在任何时间点t都不用t以后的数据来计算尺度系数和小波系数，为后续检测的及时性提供了保证。3) 利用正态分布序列的统计特性判断异常并报警。分析和实验表明，消除冗余后的无抽取Haar小波变换细节信号是均值为零的平稳随机序列，且逼近高斯白噪声。利用正态分布的“3”法则可以判断流量突变的发生，然后用前向归并措施消除多尺度检测带来的重复报警。该异常判断方法可以有效避免异常发现的延后。3.1 小波分解预处理小波分解和重构通常使用基于多分辨率分析的塔式算法。该算法对原始信号的分解过程中，每分解一次，新的信号序列的点数就要比上一级减少一半，所以塔式算法不能对某一时间点在各尺度层上建立直观的关系。更重要的是该算法不具有时移不变性，如果删除时间序列最初的一些值，所得小波变换的系数与原来的不同，需要重新计算。因此本文采用无抽取的 trous 离散小波变换算法11。 trous小波变换为一冗余变换，长度为N的时间序列，在每一个时间尺度上的分解序列长度仍然是N，这样在每一个时间尺度的同一时间点就可以建立直接联系，而且具有时移不变性。设网络流量时间序列为x(t),则可以用离散低通滤波器h得到尺度系数：， (1)根据 trous小波变换的性质，各时间尺度下的细节系数可通过尺度系数来表示，即： (2)则集合为原时间序列直到分辨率J的小波变换,其中(j=1,2,J)为各尺度下的细节信号, cj为近似信号。原时间序列可以由细节信号和近似信号重构(3)无抽取Haar小波变换是在 trous小波变换算法的基础上以h=(1/2,1/2)作为低通滤波器，根据式(1)、式(2),尺度系数和小波系数的计算方法为 (4) (5)(6)无抽取Haar小波变换计算复杂度为O(J)，J为小波分解的层数。图2中用矩形框标示了在最新数据到达时与小波分解相关的历史数据，其中给出了前3层小波分解，可以看出在任何时间点t都不用t以后的数据来计算小波系数。小波变换的层数与检测渐增式异常直接相关，发包速度变化越慢就需要越多的层数才能检测到，现实中渐增式异常一般为自然增速，不需要过多的分解层数就能检测到，同时考虑到计算量，通常分解36层即可。图2 无抽取Haar小波分解3.2 小波细节信号特征分析通过小波变换，原网络流量时间序列分解为多个时间尺度下的细节信号dj (j=1,2,p)和近似信号。网络流量时间序列具有自相似特征9，而自相似过程在二进栅格下的小波变换系数是平稳随机序列，而且当采用的小波函数是整数位移正交归一的小波基时，小波变换对自相似过程有很强的去相关作用，小波细节信号可以近似看作白噪声序列12。由于采用的无抽取Haar小波变换是冗余小波变换，要具有上述小波系数特征，首先要消除冗余，因此把第j层细节信号分为2j个序列，其中第p(0p2j)个序列为(7)当新的数据到达时，分解得到的小波系数只属于其中一个序列，对算法的计算复杂度不产生任何影响。图2中以第一层细节信号序列为例，用黑色填充的圆和未填充的圆表示了去除冗余后形成的2个小波系数序列。下面以3.1节小波分解的第二层细节信号为例分析无冗余的小波细节信号的独立性和正态性。图3是无冗余小波细节信号的自相关分析图，自相关分析图中给出了95%置信区间，自相关系数落入此区间表示与0无显著差异，可以看出该序列相关性很弱，可以近似为独立分布。图4是用正态概率图(normal probability plot)检验无冗余细节信号的正态性，图4中曲线可以较好地用直线拟合，因此该序列基本符合正态分布。同时用Jarque-Bera检验法14对该细节信号作了分布拟合检验，在显著性水平0.05下服从正态分布。综合以上分析，消除冗余后的小波系数序列近似为高斯白噪声。 图3 无冗余细节信号自相关分析图4 无冗余细节信号正态概率3.3 异常判断方法综合前面对细节信号分布特征的分析，正常网络流量状态下，无冗余细节信号是均值为0的平稳序列，可以近似为高斯白噪声，其概率密度函数服从正态分布。当时间序列发生突变时，相应时间尺度的细节信号必然大幅偏离正常分布规律。假设无冗余细节信号序列d(t)均值为(=0)，方差为2，则根据正态分布规律有 (8)其中，(x)为标准正态分布的分布函数，据此可计算出序列的分布特征：P-3d (t) 3=99.74% (9)这就是正态分布的“3”法则，也就是说当小波系数取值偏离均值(=0)超过l=3倍均方差时，可以判断异常事件的发生，阈值l的取值可以根据需求进行调整,一般取34。每一个高斯白噪声序列设置一个滑动窗口，用于保存最近一段时间的历史数据，作为判断异常的依据。窗口滑动的步长为1个时间点，考虑到数据的时效性和计算空间的节约，取窗口长度为80，过长的历史数据对检测准确性影响不大。当异常发生时，异常数据必然对后续一个阶段的异常检测造成影响，我们用异常值消除的方法，即异常小波系数不参加序列的均方差计算，以保证用正常数据作为判断异常的标准。DA-MTS在每个时间点上的处理主要分为两步。第一步小波分解的时间复杂度是O(m),m是小波分解的层数；第二步是计算滑动窗口中历史数据的均值和标准差，时间复杂度仍然为O(m)。所以该算法时间复杂度为O(m)。DA-MTS算法中，占用空间的主要是历史窗口中的数据，假设我们做了m层分解，则共需要2m+12个滑动窗口，每个窗口中保存的历史数据的数量是常数，因此算法的空间复杂度为O(2m+1)。由于m的值很小，实际占用空间也很小。4 网络流量异常检测实验用真实流量数据与模拟异常数据相结合的方法构造了模拟流量数据。以NLANR测量的Auckland大学校园网出口OC-3线路一天的IP分组流量数据作为背景流量，统计时间间隔1min。文献10对DDoS攻击的时间和流量分布做了详细的统计分析，据此模拟构造了几次网络攻击流量，其中包括恒定速率的攻击和逐步提高发包速度的攻击，然后叠加在背景流量的不同时段。另外通过在一段高速流量减去相同时间长度的低速流量，构造了一次网络故障异常。表1是几次模拟异常的情况，其中最高速率是每分钟发送包的最大数量。表1模拟流量异常列表异常 ID异常类型起止时间最高速率/(packetmin-1)A1SIA546 - 562+30000A2SIA672 - 680+10000A3AIA865 - 876+20000A4AIA950 - 951+20000A5网络故障1155 - 118510000(SIA - slowly increased attack, AIAabrupt increased attack)把表1中的网络流量异常加入背景流量后构造出待检测流量时间序列，如图5所示，其中用灰色矩形框标出了异常所在时间区域。用本文介绍的DA-MTS异常检测算法和GLR检测算法6对该流量序列进行异常检测，GLR检测算法通过比较2个滑动窗口中时间序列的残差的广义似然比(GLR, generalized likelihood ratio)来检测异常。实验中多尺度检测算法小波分解层数为4，阈值l=4；GLR检测算法的历史窗口和检测窗口的大小均为L=20，AR模型的阶数p=2，GLR的阈值h=5。图5 包含流量异常的网络流量时间序列(万包/min)表2是2种检测算法的检测结果。可以看出，本文提出的异常检测算法不但准确检测到了异常，而且报警时间也非常及时，只对渐增式异常有轻微的延迟；而GLR算法报警时间会延迟近一个甚至2个滑动窗口的长度，而且由于历史窗口和前一次检测窗口的重叠，会产生二次报警，对于变化幅度较小的渐增异常A2，GLR检测算法没有检测到。表2中同时给出了本文检测算法发现异常所在的层，2个渐变式异常都是在小波分解的高层发现的，而其他异常是首先在第一层检测到的，这证明了小波分解在检测渐变式异常方面所起到的作用。表2异常检测准确性比较时间类别A1A2A3A4A5实际时间546-562672-680865-876950-9511155-1185DA-MTS(时间 / 信号层)553/4678/3865/1950/11155/1-1186/2GLR 算法时间580-600No880-900960-9801160-12205 结束语高速网络流量大吞吐量的特征，对异常检测方法的计算效率提出了新的挑战，以往大部分异常检测方法的准确性或及时性难以适应这种需求。无抽取Haar小波变换算法分解具有自相似特征的网络流量时间序列后产生不同时间尺度下的细节信号，该细节信号在去除冗余后近似为高斯白噪声，而正态分布的“3”法则可以用来检测存在的异常，在此基础上提出了多时间尺度同步的异常检测算法DA-MTS。实验数据表明，该算法不但能够在多个层次上剥离正常数据变化，从而使流量突变能够更容易被检测到，而且发现异常及时。无论从计算效率上还是从准确性上，DA-MTS算法能够较好满足高速网络流量异常检测的需求。参考文献：1卿斯汉, 蒋建春, 马恒太等. 入侵检测技术研究综述J. 通信学报, 2004, 25(7): 19-29.QING S H, JIANG J C, MA H T, et al. Research on intrusion detection techniques: a survey J. Journal on Communications, 2004,25(7): 19-29.2WANG H, ZHANG D, SHIN K G. Detecting SYN flooding attacks A. Proc 21st Joint Conf IEEE Computer and Comm Societies (IEEE INFOCOM), IEEE Press C. 2002.1530-1539.3THROTTAN M, JI C. Adaptive thresholding for proactive network problem detectionA. IEEE International Workshop on Systems ManagementC. Newport , Rhode Island , 1998. 108-116.4邹柏贤. 一种网络异常实时检测方法J. 计算机学报, 2003, 26(8): 940-947.ZOU B X. A real time detection method for network traffic anomaliesJ. Chinese Journal of Computer, 2003, 26(8): 940-947.5孙钦东,张德运,高鹏. 基于时间序列分析的分布式拒绝服务攻击检测J,计算机学报, 2005, 28(5):767-773.SUN Q D, ZHANG D Y, GAO P. Detecting distributed denial of service attacks based on time series analysisJ. Chinese Journal of Computer, 2005,28(5):767-773.6PAXSON V, FLOYD S. Wide area traffic: the failure of Poisson modelingJ. IEEE/ACM Transactions on Networking, 1995, 3(3): 226-244.7WORNELL G. Wavelet-based representations for the 1/f family of fractal processA. Proceeding of IEEEC. 1993.1428-1450.8ALARCON V, BARRIA J A. Anomaly detection in communication networks using wavelets J. IEE Proceedings Communications, 2