基于MapReduce的PCA异常流量检测系统实现

黄志兰，丁圣勇，杨国良，罗颂锋

（中国电信股份有限公司广东研究院 广州 510630）

1 前言

随着计算机网络的飞速发展和互联网应用的日渐丰富，互联网流量呈指数增长，运营商网络面临越来越大的压力。在这些网络流量里，有正常的用户访问流量，也有形形色色的异常流量。网络异常流量是指偏离正常行为的网络流量，引起网络异常流量的原因有很多，如网络设备的不良运行、网络操作异常、突发访问、病毒攻击、网络入侵等。异常流量具有发作突然，先兆特征未知等特点，可以在短时间内给网络设备和网络中的计算机带来极大危害，严重影响网络安全和网络性能[1]。因此，及时检测网络异常行为，判断网络异常的原因，对于保障网络的可靠运行具有重要意义，网络异常流量检测也引起了业界的广泛关注和研究。

有多种途径检测网络异常行为，具体包括SNMP流量分析、网络设备日志分析、Netflow流量分析等。基于Netflow的网络异常流量检测是目前研究和使用最多的方法。Netflow数据描绘了网络的真实流量状况，在网络正常的时候，Netflow数据具有一定的规律性。当网络出现异常时，Netflow数据将呈现不同寻常的变化，这种变化隐藏在高维的流量数据里，需要专门的方法检测。

目前，主流的基于Netflow的网络异常流量检测方法大致可以分为以下几类[2]。

（1）阈值法

根据历史数据建立一个正常的参数基线以及一个容忍范围，一旦网络流量超出基线的容忍范围则认为有网络异常流量出现。

（2）预测法

根据历史数据建立网络流量模型，根据模型预测下一个采样点的数据，如果采样点的实际数据与预测模型数据有较大的误差，则认为有异常流量存在。常用的预测模型有自回归模型（AR）、小波预测[3]、马可夫模型等。

（3）分类法

根据历史数据和已知的特征训练分类器，对新出现的数据进行分类，如SVM方法[4]。这些方法大都针对字节、包、IP流、链路等一维信号的异常变化来检测异常。对于复杂的网络异常流量来说，异常特征隐藏在高维的向量空间中，这些分析方法无法有效应对。

主成分分析（principal component analysis，PCA）[5]方法是发现高维数据模式的通用统计技术，它在数据空间中找一组向量以尽可能地解释原数据的方差，将数据从原来的n维空间降到m维（m<

PCA异常流量检测方法在处理大规模高维数据，尤其是运营商全网流量数据时，面临海量数据处理带来的性能挑战。MapReduce分布式计算方法综合利用计算机集群的处理能力，能高效解决海量数据分析任务。MapReduce应用在PCA异常流量检测上，能显著提高PCA方法的扩展性，使得PCA算法能高效地在运营商全网范围内实时检测异常流量。

本文对PCA异常流量检测方法和MapReduce进行了简单介绍，并介绍了基于MapReduce的PCA异常流量检测系统实现，最后给出了实验结果。

2 PCA异常流量检测

PCA是一种处理高维随机变量的方法，通过对数据进行线性变换，使得变换后的数据能量主要集中在主成分方向，从而使得原本基于高维处理的很多问题能够在低维空间解决[6]。应用在网络异常监测中，PCA的次成分充当了异常显微放大功能。对很多异常，在通常情况下，并不能简单地通过阀值比较来进行判断，如流量矩阵结构的变化等，但这些变化经过PCA变换后，通常会在次成分产生较大波动，从而提供一种有效异常监测功能。

对于一个多维数据集，将其化成矩阵A。Ai表示A的第i列，代表原数据的一维数据序列。PCA的一般步骤描述如下[7]：

·将矩阵A零均值化，即求Ai所有数据的平均值，再用Ai中的每个数据减去这个平均值，得到各列平均值都为0的矩阵B；

·计算矩阵B的协方差，得到协方差矩阵C，C=BTB；

·求解矩阵C的特征值和特征向量，每个特征向量vi就是 C 的主成分或次成分，即：Cvi=λivi，i=1,…,p，其 中 ，λi是vi对应的特征值，对特征向量进行归一化处理；

·把特征值从大到小排列，即 λ1≥λ2≥…≥λp，并把特征向量按照对应的特征值进行重新排序，得到一个特征向量序列（v1，v2，…，vp）；

·选取前r个特征向量作为主成分，剩余的p-r个特征向量作为次成分，r为可调参数；

·每个特征向量的转置与矩阵B的转置的内积就是所求的主成分的值。

将PCA应用在全网异常流量检测时，首先需要将Netflow流量数据转化成PCA可处理的高维矩阵。根据流量聚集程度的不同，可以从路由器、链路、OD（origindestination）流等层面定义PCA输入矩阵[8]。如以链路为单位进行PCA异常流量检测时，把输入矩阵A定义为t×p矩阵，其中p代表网络中的链路数量，t代表采样的点数，这样A的每列i代表第i条链路的时间序列，每行j代表所有链路流在j时刻的采样值。研究表明，流量聚集程度对PCA检测结果的影响很大，过分聚合将隐藏异常流量的特性，聚合不足则会导致PCA被波动过大的小流量干扰而无法正常检测。

本文对中国电信全网异常流量进行检测，流量聚集在Region-to-Region级别的OD流层面。我们把中国电信城域网按地理位置划分成十大区域，每个区域称为一个Region，每个Netflow数据流根据源IP和目的IP归属到某个Region-to-Region OD流，Region的区间由 IP地址段决定。系统采用基于IP特征的信息熵时间序列构建PCA输入矩阵，信息熵提供了一个可计算的高效机制，用于评估分布的离散和聚合程度，而各种异常都将影响一个或多个IP特征的分布，因此基于IP特征的信息熵时间序列可以有效地捕获网络流量的异常变化[8]。

PCA输入矩阵或称流量矩阵A由一系列时间序列向量构成，每个时间序列向量有m个特征，这m个特征为OD流与 IP流量特征（源IP、目的 IP、源端口、目的端口、包数量、字节数）的组合。即：A为n×m矩阵，n代表采样点数，m代表特征数目，A的每列i代表第i个特征的时间序列，每行j代表所有特征在j时刻采样的信息熵。特征名为ODk_IP_Feature，如ODk_SRCIP表示第k个OD流的源IP统计值的信息熵。

对于PCA异常流量检测而言，PCA过程相对简单，只对输入矩阵进行简单的数学变换，然后计算特征值和特征向量即可，对机器性能和运算效率要求不高。对全网流量进行分析统计，得出一个可供PCA有效运算的输入数据矩阵，却是一个相当艰巨的任务。为此，需要引入高性能的分布式计算方法，借用计算机集群的大规模处理能力解决海量数据分析问题。通过分析，我们发现MapReduce分布式计算模型天然适应对流量数据的统计分析，可在大规模流量数据中快速生成PCA算法所需的输入矩阵。我们也通过真实数据验证了基于MapReduce的PCA异常流量检测的可行性。

3 MapReduce分布式计算方法

MapReduce[9]是一种有效的分布式编程模型，它提供了泛函编程的一个简化版本，与传统编程模型中函数参数只能代表明确的一个数或数的集合不同，泛函编程模型中函数参数能够代表一个函数，这使得泛函编程模型的表达能力和抽象能力更高。Google云计算系统以及开源的Hadoop分布式软件架构都提供了对MapReduce编程模型的实现，这些系统隐藏了并行化、容错、数据分布、负载均衡等复杂的分布式处理细节，提供了简单有力的接口来实现自动的并行化和大规模分布式计算，从而能在大量普通PC机上实现高性能计算。

在MapReduce模型中，输入数据和输出结果都被视作由一系列key/value对组成的集合。用户指定map函数对输入key/value集进行处理，形成中间形式的key/value集；MapReduce库按照key值把中间形式的value集中起来，传给用户指定的reduce函数；reduce函数把具有相同key的value合并在一起，最终输出一系列key/value对。

MapReduce过程主要包括以下几个步骤：

·将输入的海量数据切成小片分给不同的机器处理；

·Map任务将输入数据解析成key/value对，执行用户定义的map函数，把输入的key/value对转成中间形式的key/value对；

·按照key值对中间形式的key/value进行排序、聚集；

·把不同的key和相应的value集分配给不同的机器，完成reduce运算；

·输出reduce结果。

在Hadoop分布式软件架构中，数据的分片、任务的分配及调度、中间结果的排序汇总、运算结果的输出都是由框架实现的，用户只需编写自己的Map函数和Reduce函数。Hadoop MapReduce模型具有很强的容错性，已被许多系统成功运用。本文提出的基于MapReduce的PCA异常流量检测系统，也架构在Hadoop平台之上。

4 基于MapReduce的PCA异常流量检测系统

为验证MapReduc的可行性，我们基于Hadoop分布式软件架构，实现了PCA网络异常流量检测系统，系统部署在与电信骨干网互通的Hadoop服务器集群上。系统由数据采集模块、统计分析模块、PCA异常流量检测模块、监控模块4部分组成，系统架构如图1所示。

流量采集模块基于Cisco开源的Netflow流量采集器NFC组件实现，收集来自中国电信骨干网全网路由器的Netflow流量。为应对海量Netflow数据的存储需求，我们对NFC模块进行了修改，使其将收集到的Netflow数据以二进制文件的形式存储在Hadoop分布式文件系统HDFS中。流量采集模块每Δt时间内生成一个HDFS文件，每个HDFS文件产生一个熵时间序列。

MapReduce统计分析模块是系统的核心，它基于Hadoop MapReduce编程模型对Netflow流量数据文件进行统计分析，最终输出供PCA异常流量检测模块处理的熵矩阵。统计分析模块的数据处理过程如下。

·根据IP地址段定义Region-to-Region的OD流，并将OD流与源IP、目的IP、源端口、目的端口、包数、字节数六个IP特征进行组合，形成形如ODk_SRC_IP、ODk_DST_IP、ODk_SRC_PORT、ODk_DST_PORT、ODk_Packet、ODk_Bytes（k=1,…,100）的特征。按照特征的取值范围定义不同的区间，构建特征分布直方图。

·定义Map-Reduce过程，对输入的Netflow数据文件进行统计分析，形成每个特征分布的直方图。Map-Reduce过程对每一条Netflow数据流进行处理，根据src_ip、dst_ip字段确定数据流归属于哪一个OD，然后对IP特征分布进行累加统计。

·根据特征分布直方图，计算每个特征ODk_IP_Feature的信息熵 Entropy（pi）=-Σpilog pi，其中pi为落入第i个取值区间的概率。

·所有特征的熵值组成一个熵时间序列，将该序列存储在MySql数据库中，供PCA异常流量检测模块处理。

PCA异常流量检测模块对MySql数据库中的熵时间序列进行处理，每次选取k条记录，形成600×k矩阵，其中k为可调参数。PCA异常流量检测模块依次对熵矩阵进行零均值化、协方差矩阵计算、特征值和特征向量计算等步骤后形成主成分和次成分。新的熵时间序列在主成分、次成分方向通过内积投影，即可形成相应的主成分/次成分值，供异常流量监控模块使用。

异常流量监控模块通过曲线图显示Δt×k时间段内各采样点的主成分和次成分值。当次成分曲线变化图出现明显的尖峰时，说明网络中有异常流量出现，系统发出告警。

5 实验结果

我们对基于MapReduce的PCA异常流量检测系统进行了验证测试。系统部署在Hadoop分布式处理平台上，平台由14台IBM刀片服务组成，与中国电信ChinaNet骨干网互通。服务器的硬件配置为：2路8核2.5 GHz CPU，8 GB内存，280 GB硬盘。配置的操作系统为Ubuntu 8.10 Server，Hadoop版本为0.19.1,网络结构如图2所示。

实验使用的数据来源于中国电信骨干网，路由器Netflow流量的采样比为1∶5 000，每天可生成10 TB流量数据。图3、图4显示了对网络真实数据进行PCA异常流量检测的结果，为了便于查看，我们截取了20 min内的监测效果图。图3显示的是前5个PCA主成分取值随时间变化的曲线，可以看出，PCA主成分反映了正常流量的稳定规律，随时间波动较小。图4显示了最后5个次成分取值随时间变化的曲线，可以看出，次成分对网络异常敏感，随时间波动较大，在03:40这个时间点5个次成分均出现不同程度的尖峰，该时刻网络出现异常流量的可能性极大。由此可见，PCA方法能有效发现网络中的异常流量。

MapReduce具有良好的可扩展性，能够有效应对大规模PCA异常流量检测对计算能力的需求。当需要处理的数据量增大时，通过在Hadoop集群中添加更多的计算机可以有效提高PCA异常流量检测方法的处理效率。图5反映了基于MapReduce的PCA异常流量检测系统的扩展能力，可以看出，对于单机系统而言，随着数据量增大，运行时间呈线性增长。在多机情况下，如5台机、10台机时，随着流量数据增加，PCA运行时间增长缓慢。随着集群机器增多，基于MapReduce的PCA异常流量检测方法运行效率得到提升。

实验结果表明，PCA方法能有效检测网络中的异常流量，将MapReduce应用在PCA异常流量检测上，能有效提高系统的运行效率和扩展性，使得PCA方法能够有效应对运营商超大规模的网络数据。

6 结束语

实验表明，MapReduce分布式编程模型天然适应Netflow网络流量数据分析。利用MapReduce方法对Netflow流量数据进行处理，生成熵时间序列矩阵供PCA算法检测分析，可有效提高PCA异常流量检测系统的处理能力和性能。未来，我们将尝试把MapReduce分布式编程思想应用到其他流量分析方法，以提高现有流量分析工具的工作性能和处理能力，从而应对全网大规模流量数据的分析处理需求。

1 杨丹，胡光岷，李宗林，姚兴苗.全局的多流量相关异常检测算法.电子科技大学学报，2008,37(6)

2 贾冠昕，杨波，陈贞翔，彭立志.基于NetFlow时间序列的网络异常检测.计算机工程与应用，2008,44(24)

3 肖志新，杨岳湘，杨霖.基于小波技术的网络异常流量检测与实现.计算机科学，2006,33(10)

4 柴志成.一种基于SVM的网络异常流量检测新方法.贵阳学院学报，2008,3(1)

5 王敏，李纯喜，陈常嘉.浅谈基于PC A的网络流量分析.微计算机信息，2006，22(6)

6 Lakhina A,Crovella M,Diot C.Diagnosing network-wide traffic anomalies.ACM SIGCOMM,Portland,August 2004

7 王海龙，杨岳湘，李强.基于子空间方法的大规模网络流量异常检测.计算机工程与应用,2007，43(11)

8 Haakon Ringberg,Augustin Soule,Jennifer Rexford,Christophe Diot.Sensitivity of PCA for traffic anomaly detection.In:Proc of SIGMETRICS'07,2007

9 Dean Jeffrey,Sanjay Ghemawat.MapReduce:simplified data processing on large clusters.In:Proc of Symposium on Operating System Design and Implementation,2004