基于数据流方法的大规模网络异常发现

2006年2月JournalonCommunicationsFebruary2006第27卷第2期通信学报Vol.27No.2基于数据流方法的大规模网络异常发现郑军,胡铭曾,云晓春,郑仲（哈尔滨工业大学计算机网络与信息安全技术研究中心，黑龙江哈尔滨150001）摘要：随着网络规模和速度的增加，大规模网络异常发现要求检测算法能够在无保留状态或者少保留状态下对G比特级的海量网络业务量数据进行实时在线分析。针对在高速骨干网上进行大规模网络异常发现的特点和要求，提出了一种基于数据流的大规模网络异常发现的方法，第一次将数据流模型用于大规模网络的异常发现。主要包括以下创新点：设计了一种面向异常发现的网络流量概要数据结构和突发高频事件检测算法；提出了一种基于安全监测策略定制的预查询方法来进行多数据流的关联监测并且对数据流查询进行了优化；在真实数据分析的基础上，对网络业务量进行了数据约减，使得监测部分特殊类型的数据流能最大程度地获得整体网络业务量的变化特征以提高异常发现的效率。通过真实网络环境下的实验和性能评价验证了数据流方法的有效性。关键词：异常发现；数据流；大规模网络；突发高频事件；概要数据结构中图分类号：TP393.08文献标识码：A文章编号：1000-436X(2006)02-0001-08AnomalydetectionoflargescalenetworkbasedondatastreamsZHENGJun,HUMing-zeng,YUNXiao-chun,ZHENGZhong(ResearchCenterofComputerNetworkandInformationSecurityTechnology,HarbinInstituteofTechnology,Harbin150001,China)Abstract:Theanomalydetectionalgorithmsofthelargescalenetwork(LSN)wererequiredtoanalysisthevastnetworktrafficofGbitlevelinreal-timeandon-the-fly.AnovelmonitoringmechanismofLSNanomalydetectionbasedonthedatastreamapproachwasproposed.Themaincontributionsincluded:thesketchdatastructureandthefrequentsketchalgorithmofdatastreamsweredesignedforanomalydetectionofLSN.Optimizedquerymethodsweredesignedforcustomizingthesecuritymonitoringanddetectionpolicywiththecorrelationsofmultidatastreams.Thedatareductionwasproposedtomakeitpossiblethatthewholenetworktrafficcharactercouldbegotusingafewofspecialdatastreams.TheexperimentsoftherealnetworkingenvironmentsvalidatetheeffectivityofLSNanomalydetectionmethods.Keywords:anomalydetection;datastreams;largescalenetwork;burstyfrequentevent;sketchdatastructure1引言随着Internet的高速发展，网络的规模与流量迅速增加。传统入侵检测系统（IDS）[1]并不能简单的推广用于面向大规模网络的网络业务量监测（networktrafficmonitoring）与异常发现（anomalydetection）。因为传统的IDS一般面向局域网或者企业网[1]，检测能力依靠于对单个数据包进行关键字匹配的误用检测能力，而传统的异常检测算法的效率难以满足高速骨干网监测的需要。对于大规模网络的异常发现来说，监控点通常布置在逻辑位置相对较高的高速骨干网节点上。在这样的高位监测点收稿日期：2005-11-15；修回日期：2005-12-20基金项目：国家高技术研究发展计划（“863”计划）基金资助项目（2002AA104410）；国家自然科学基金资助项目（60403033）FoundationItems:TheNationalHighTechnologyResearchandDevolopmentProgramofChina(863Program)(2002AA104410);TheNationalNaturalScienceFoundationofChina(60403033)·2·通信学报第27卷上数据呈现以下特点：由于网络的随机性，各网络业务量数据到达相互独立；网络业务量数据高速无穷到达，且不间断，呈现海量数据特点，无法进行本地存储。所以依靠于报文捕获→数据包还原→关键字匹配的传统入侵检测系统效率无法满足要求，即便采用硬件分流措施，数据分析速度无法跟上流量速度。大规模网络的异常发现实际上是一种高速网的客观规律发现技术。对于蠕虫爆发以及DoS/DDoS攻击这些大规模网络安全事件来说，在一定时间和空间范围内，某些特定类型网络业务量会呈现出特定的高频特性。我们面临的问题是：对于持续海量出现的网络数据报文，什么样的信息出现的突发（bursty）频率最大；这样的信息与大规模安全事件是否关联。由于上面提到的高位监测点的数据特性，这种网络异常发现必须是在无保留状态或者少保留状态下在线实时完成，也就是对高速经过的海量数据在不进行本地拷贝的情况下，在较小时间内完成数据挖掘（datamining）工作，以便提供更快的网络安全应急响应。这就完全不同于传统入侵检测中的异常检测方法，需要对数据处理和分析算法进行全新的设计。针对高速网络环境下大规模网络异常发现的特点和难点，本文首次提出并实现了一种基于数据流模型的大规模网络异常发现方法。基于数据流方法设计了一种面向大规模网络异常发现的概要数据结构（sketch）和突发高频数据项检测算法。实现了基于高速骨干网的面向安全事件检测和预警的大规模网络异常发现。2相关工作比较目前已有的大规模网络异常发现的研究多集中于入侵检测领域内。而传统的异常入侵检测的机器学习方法[1]并不适用于大规模网络的流量分析与异常发现。我们把已有的工作概括为两个方法。2.1基于时间序列分析的方法异常检测系统通过对特定统计对象进行均匀采样，形成时间序列，通过AR、ARMA、ARMIA以及EWMA等经典的时间序列模型，或者其他的时间序列分析方法进行分析。一般分为两个方向：一个是分析特定的细化安全事件的统计对象[2]。文献[3]通过时间序列模型分析SYN和SYN-ACK数据包差异的统计来发现拒绝服务攻击中的SYN-Flooding攻击。第二个方向是把经典时间序列模型用于网络流量分析。文献[4]通过经典时间序列模型对网络流量进行预测，并在预测基础上对网络异常状态进行分析和预警。但是时间序列分析用于异常检测存在两个问题：第一，由于网络流量特别是高速网络流量本身的动态性和复杂性，通过某个时间序列模型进行流量拟和并预测准确性较难保证，而在预测基础上进行更进一步的异常发现准确更难保证。所以单纯通过时间序列分析的异常检测方法仍然需要其他辅助方法进一步的完善；第二，由于经典的时间序列模型，如ARMA模型，差分方程系数计算复杂性使其用在异常检测上仍然存在困难，检测的实时性和灵活性难以保障。2.2基于信号的小波分析方法最近十年来，实验证明网络业务量具有自相似及长相关特征[5,6]，且随着网络速度的增加这种特性越来越明显,这就打破了先前泊松过程的假设。而小波本身具有多时间尺度的特性，因此可以很好地刻画描述网络业务量模型。文献[7,8]将小波分析用于网络异常分析，通过小波对网络流量信号进行时域－频域分解，能够划分不同时域—频域特征的网络流量异常。小波分析办法虽然初见成效但仍不够准确，而且这样的检测需要对本地网络业务量行为模式进行长期统计观察并建模；此外，信号的小波分析方法只能检测网络流量异常而不能区分造成网络流量异常的不同原因，比如这种方法在一定范围内无法区分是DoS/DDoS异常还是正常用户对某些网站的突发访问（flashcrowd）异常。3突发高频数据项的检测算法3.1大规模网络的突发高频事件定义1突发高频事件（burstyfrequentevent）就是在高位网络监测点上能够观察到的，一段时间内反复持续出现，但是在宏观时间尺度上又是小概率的异常事件。高速网络流量环境下的大规模网络异常发现与传统的网络入侵检测有所不同，其目的主要是监测高速网络业务量，监测并发现那些突发性出现的高频同类信息或者与常规分布不同的信息。也就是在高速经过的海量数据中，能够及时发现这些突发高频事件并能够通过其他相关方法把这些突发高频事件与网络安全事件相关联，便于及时掌握大规模网络的状态并对网络异常做出应急响应措施。第2期郑军等：基于数据流方法的大规模网络异常发现·3·3.2数据流模型在位于高速骨干网的高位监测点上对所到达的每个网络数据项进行拷贝，然后再进行本地分析是不现实的，只能对其进行在线状态的无保留监测（monitoringon-the-fly），这就要求突发高频检测算法具有低时间复杂度。在此，引入数据流模型（datastreams）。它是最近几年才出现的一种新的数据处理应用模型[9]。数据流模型的最大优势就是能够在不保留或者少保留数据的前提下对在线数据进行实时的一次性单遍处理（one-pass）。下面给出数据流的定义。定义2数据流α(α1,α2,
αi
)是一系列逐条先后到达的数据项。数据项αi=(ai,ui)，αi∈S，S称为类域表示所有不同种类数据项的集合。其中ai为标志数据项αi的属性值。这里存在一个随时间变化的信号变量A[ai]。在数据流中，当新的数据项到达时A[ai]＝A[ai－1]+ui。本文中面向高速骨干网异常发现的数据流算法包含两个方面内容：(1)摘要数据结构（sketchdatastructure）：在使用极小内存和时间的前提下对海量数据流特征进行小空间逼近表达，以支持在线分析和检测；(2)一次性单遍处理算法：在摘要数据结构基础上完成对高速网络数据的一次性单遍处理，发现突发高频数据项。3.3高频概要算法3.3.1算法描述对于高速网环境中无穷到达的海量网络数据流，数据流算法必须满足两个条件：在线实时处理和有限存储空间。数据流模型研究的基础是概要数据结构的选择和设计，即在也就是丢弃多数的原始网络数据，在计算机内存内生成网络数据流的概要大纲（sketch）为进一步突发高频事件挖掘做准备。关于概要数据结构的设计目前仍然是数据流研究的热点问题，很多方法被用来生成数据流的概要数据结构[9]，包括小波方法、散列方法、直方图方法、计数方法以及抽样的方法[9,10]。为了进行网络突发高频事件检测，本文设计了一种高频概要算法（FSA,frequentsketchalgorithm）。FSA在多级散列的基础上进行计数（count）操作。FSA的计数器更新（update）算法如下：FrequentSketchUpdate算法Update(S,a,u)计数器值加1IF(a计数器值大于a之前元素计数器值)DOWHILE(a计数器值大于a之前元素计数器值)DO交换两者位置ENDWHILE设置位置变动标志位ENDIFEND算法在高频项处理时需要进行大量的节点信息交换，这是影响算法执行效率的主要瓶颈。我们用一个带有模拟指针的散列表来实现以优化。程序在启动时首先初始化一个由Item构成的线性表，线性表大小由FSA中存储的数据项个数决定。每个表项的键值为其在线性表中的位置。初始化算法伪代码如下：FrequentSk