网络流量异常检测利器:MV-Sketch介绍与实战

作者简介:朱龙隆,福州大学数计学院2018级计算机科学与技术(实验班)本科生,目前研究方向为网络测量,邮箱1614864145@qq.com

一、 背景

网络测量是SDN发展的基础,是优化网络结构、改善网络服务质量、实现网络故障诊断和恢复的重要手段。在SDN网络中, 网络管理员通过网络测量及时了解、监控、掌握网络状态,调整网络的性能参数,及时发现可能存在的DDOS攻击、网络入侵等状况。

基于Sketch的网络测量与SDN结合具有天然特性[1]。大量部署的SDN云数据中心拥有每秒成千上万的并发流,需要sketch提供海量流量下的高速网络测量;SDN控制器的全局视野有助于全网调度、策略制定,实时提供网络信息,有利于Sketch的应用实施;Sketch在较小内存下对重流(heavy flow)(如heavy hitter(大流)和heavy changer(突变流))的快速检测有助于SDN云数据中心的大量部署。

二、 Sketch介绍

什么是Sketch?Sketch是一种紧凑的用于流量数据统计亚线性数据结构。其使用哈希将数据映射到Sketch中,将大量网络流压缩至小部分的内存空间中,无需存储所有网络流,以达到节约内存的目的,并通过查询操作获得流量统计数据。

为什么要使用Sketch?网络流主要依据五元组分类,每流检测为每个网络流都分配一个计数器,保证了测量的零误差,但空间复杂度极高。抽样技术选取部分报文来推断网络流量总体的性能参数,减少了测量的数据量,但其数据的不完整性对测量结果的准确性造成了很大影响。数据流技术通过哈希的方法把庞大的数据映射到小的存储空间内,其中以基于Sketch的方法应用最广泛。Sketch将具有相同哈希值的流存入相同的桶内,可以在保证准确度的同时大大减少存储空间。

本文所介绍的MV-SKetch[2]可以在小内存下实现对重流的快速检测。通过对重流的检测,网络管理员可以实时掌握网络的状态、及时发现并应对可能出现的网络入侵等状况,此举大大提高了运营网络的鲁棒性。

三、 MV-Sketch概述

MV-Sketch是一种高效、紧凑、可逆的Sketch,使用较小静态内存空间即可实现重流检测。MV-Sketch主要利用MJTRY算法(主票选算法)[10],在Sketch中保留重流候选,只需较小的空间即可支持更新和查询操作,从而实现了小内存下的重流检测。同时,相较于动态分配流存储空间的方式,静态分配方式有助于降低内存管理开销,且可以利用SIMD加速MV-Sketch。

四、 现有问题与解决

1.现有问题1:传统的Sketch虽然高效但不可逆
传统的Sketch举例:
Count-Min_Sketch[4]:使用多个哈希函数,选取计数器的最小值来保证高准确率。

存在问题:传统的Sketch高效却不可逆,他们无法从本身中恢复所有重流,只能通过遍历所有流的方式查询是否存在重流,这样的方法将带来大量查询开销。

MV-Sketch的解决:MV-Sketch将重流候选保存于Sketch数据结构本身,从而保证了可逆性。

2.现有问题2:现有Sketch保证可逆但更新开销高
现有的可逆Sketch举例:

①带有额外数据结构的Sketch
Count-Min-Heap[3]:Count-Min-Heap通过在Count-Min上增加一个堆以记录重流。

LD-Sketch[5]:通过动态变化长度的数组记录重流的候选者,驱逐其他流,以达到节约存储空间的目的。

存在问题:由于依靠额外的数据结构来存储重流,更新时易导致高内存访问开销,且随着候选重流数目的增加而增加。此外,LD-Sketch动态分配流存储空间,增加了开销,且难以利用硬件实现。

②基于分组检测的Sketch
Deltoid [6]:将流关键字(一般是五元组或源目的IP)映射到计数器组的一个子集中,使用多个计数器来记录流。
Fast Sketch[7]:与Deltoid 相似,而它将流关键字的商映射到Sketch中。
存在问题:由于计数器的数量随着流关键字长度的增加而增加,Deltoid 和Fast Sketch都有很高的更新开销。

③结合枚举的Sketch
Reversible Sketch[8]:通过削减流关键字的枚举空间来查找重流。
SeqHash[9]:与Reversible Sketch设计类似,但它将不同长度的关键字前缀哈希到诸多较小的Sketch中。

存在问题:Reversible Sketch和SeqHash的更新成本随着流关键字的长度的增加而增加,也很容易导致过高内存占用。

现有可逆Sketch存在问题总结:现有的可逆Sketch:LD-Sketch、Fast Sketch、Reversible Sketch……,虽然通过各种方式来保存重流(如依靠额外的数据结构),但在实施更新操作时,易导致高内存访问开销,从而使性能大打折扣。

MV-Sketch的解决:MV-Sketch使用较小静态内存空间进行构建,限制了每个数据包更新的内存访问开销,避免更新时过高内存占用的风险,且与使用动态内存相比,减轻内存管理开销且可利用SIMD实现硬件加速。

五、 MV-Sketch 具体介绍

设计思路

如图1[2],MV-Sketch的数据结构和Count-Min-Sketch类似,由 r 行 构成,每一行有 w 个桶,每个桶中记录三个元素Vi,j 、 Ki,j 、 Ci,j 。Vi,j 表示哈希到这个桶内所有流的总和, Ki,j表示当前桶内的重流候选, Ci,j 记录当前桶内重流候选的计数值,用于判断是否继续保留此重流候选。

当数据包到来时,MV-Sketch利用 r 个独立的哈希函数,将数据包分别映射到1 - r 行,所映射列序j由哈希值hi(x)决定。哈希到某个桶之后,根据MJRTY算法来更新重流候选。查询时,根据新流和桶内重流候选是否一致来决定估计值,最后返回所有行中估计值最小值。在一个周期结束时,MV-Sketch以是否大于设定的阈值为标准来判断重流。

图 1: MV-Sketch 的数据结构

如何利用MJRTY算法

MJRTY算法用于确定任意数量的候选人中,哪一个获得了多数选票,所拥有票数高于总票数一半者,一定是主要候选人。以一个例子介绍其大体思路:

假设有三位候选人A、B和C,并假设按以下顺序对代表进行了投票:A A A C C B B C C C B C C

记录完第三张选票后,A以3票领先。在处理接下来的三张选票时,将三张A票与三张其他票(两张C票,一张B票)配对(抵消)。记录所有选票之后,C成为主要候选人。

算法 1:MV-Sketch更新算法

MV-Sketch借鉴MJRTY算法,在执行更新操作时(算法1[2]),先累加Vi,j = Vi,j + vx (Vi,j增加新流字节数),再将新流x与当前桶内重流候选Ki,j进行比较,若相同,那么计数器Ci,j增加新流的字节数,否则相应地减少;若减少至零下(即Ci,j <0),则x取代Ki,j,且Ci,j取绝对值。在实际中,由于少数重流所带流量在桶内所有流量中占主导地位,因而在一个周期结束时,MV-Sketch可以在桶内保持准确的重流候选。

改进及优势

使用较小静态内存:相比于LD-Sketch等使用动态内存分配的Sketch-based方法,MV-Sketch避免高内存访问的风险,且可利用SIMD加速。

在Sketch数据结构本身存储重流:不必依靠额外的数据结构来保证Sketch的可逆性,省去了额外的内存管理开销,也避免发生附加空间占用大量内存的风险。

引进MJRTY算法:在MJRTY算法的基础上加以改进(计数器加减1变为加减新流的字节数),从而在存储空间中保留准确的重流候选。

六、效果

在实际实验中,MV-Sketch相对于其他最先进的Sketch-based方法,总体来说表现出了更高的准确度、召回率、吞吐量(高达3.38倍[2]),以及更小的相对误差。

实验一:heavy hitter检测精度

图 2:heavy hitter检测精度比较[2]

实验一[2]比较了在检测heavy hitter时MV-Sketch和其他Sketch-based算法的精度。如图2,当内存在512KB及以下时,Deltoid和Fast Sketch的精度和召回率都接近于零。Count-Min-heap和LD-Sketch的精度都很高,但当内存仅64KB时,它们不再保持高精度。总体而言,MV-Sketch的精度较高。例如,MV-Sketch的相对错误比LD-Sketch和Count-Min-Heap分别低55.8%[2]和87.2%[2]。

实验二:heavy changer检测精度

图 3:heavy changer检测精度比较[2]

实验2[2]比较了在heavy changer检测中,MV-Sketch和其他Sketch-based算法的精度。如图3,当内存为512KB及以下时,Deltoid和Fast Sketch的精度和召回率都接近于零。Count-Min-Heap在几乎所有内存条件下,召回率都达不到1,而MV-Sketch在内存为64KB以上时,保持了100%的召回率。在内存为256KB及以下时,MV-Sketch精度较低,但当内存在128KB及以上时,MV-Sketch精度高于LD-Sketch。

七、 MV-Sketch试运行实验

环境:Ubuntu16.4,g++5.4,make4.1

1.前期准备
源码下载(Github):

文件说明:

  • mvsketch.hpp, mvsketch.cpp: MV-Sketch的实现
  • mvsketch_simd.hpp, mvsketch_simd.cpp: MV-Sketch的SIMD版本
  • main_hitter.cpp: heavy hitter检测示例
  • main_changer.cpp: heavy changer检测示例
  • main_simd.cpp: SIMD优化heavy hitter检测示例

2.数据准备
作者提供的数据(十万流):https://drive.google.com/file/d/1WLEjB-w4ZlNshl1vUMb98rrowFuMBWuJ/view?usp=sharing

本文的数据准备(百万流):

3. 修改iptraces.txt文件:
十万流:

百万流:

4. 修改代码(以main_hitter.cpp为例):
十万流:
配置阈值、行数、桶数:

百万流:
配置阈值、行数、桶数:

更改数据路径:

强制类型转换(用源目的IP标识流):将数据中用五元组所标识流的源目的IP、length剥离出来,并以“源IP-目的IP 长度”形式标识流

5. 环境要求
安装 g 和 make ,建议ubuntu14.04及以上,make 3.81及以上,g 至少4.8以上。

确保已经安装好了必要的库libpcap(可以通过apt-get install libpcap-dev在Ubuntu中安装libpcap)

6. 编译
使用make编译,命令如下

编译过程展示:
$ make main_hitter

$ make main_changer

$ make main_simd

注意,要编译SIMD示例,需要确保CPU和编译器能够支持AVX和AVX2。
可用命令cat/proc/cpuinfo检查CPU,确保标记包含“avx”和“avx2”(倒二行):

7. 运行
-运行示例,程序将输出一些关于检测精度的统计信息。

8. 输出结果展示:
main_hitter输出结果展示
十万流:

百万流:

main_changer输出结果展示
十万流:

百万流:

9. 试运行实验小结:

MV-Sketch在十万流,百万流的数据规模下,其结果都表现出了高准确度、低相对错误、100%召回率。本文将所准备的流数据用源目的IP标识,不同于作者所提供数据以五元组形式,因而需要进行强制类型转换等对代码的修改及函数调用。

八、总结

快速增长的网络规模对当今的网络流量检测技术提出了更高的要求,现有Sketch保证可逆性时,易导致过高内存访问。MV-Sketch引进了MJRTY算法,在Sketch本身保持异常流量,保证可逆性的同时避免了对内存的过度依赖。

在MV-Sketch效果验证实验[2]中,其召回率一直都保持在高水平,但MV-Sketch在极小内存下的检测能力还有待加强,尤其是对于heavy changer的检测能力。或许我们可以根据不同应用场景、限制条件,选择性使用Sketch,或采取多种Sketch方法组合嵌套的方式,来进行异常流量检测。

参考文献:
[1]https://www.sdnlab.com/22685.html
[2]Lu Tang,Qun Huang,Patrick P. C. Lee,"MV-Sketch: A Fast and Compact Invertible Sketch for Heavy Flow Detection in Network Data Streams", Proc. of IEEE INFOCOM 2019 .
[3]G. Cormode, S. Muthukrishnan, "An Improved Data Stream Summary: The Count-min Sketch and its Applications", Journal of Algorithms, vol. 55, no. 1, pp . 58-75, 2005.
[4]G. Cormode and S. Muthukrishnan. An Improved Data Stream Summary: The Count-min Sketch and its Applications. Journal of Algorithms,
55(1):58–75, 2005.
[5]Q. Huang, P. P. C. Lee, "A Hybrid Local and Distributed Sketching Design for Accurate and Scalable Heavy Key Detection in Network Data Streams", Computer Networks, vol. 91, pp. 298-315, Nov 2015.
[6]G. Cormode and S. Muthukrishnan. What’s New: Finding Significant Differences in Network Data Streams. IEEE/ACM Trans. on Networking, 13(6):1219–1232, 2005.
[7]Y. Liu, W. Chen, and Y. Guan. A Fast Sketch for Aggregate Queries over High-Speed Network Traffific. In Proc. of IEEE INFOCOM, 2012.
[8]R. Schweller, Z. Li, Y. Chen, Y. Gao, A. Gupta, Y. Zhang, P. Dinda, M. Y. Kao, G. Memik, "Reversible Sketches: Enabling Monitoring and Analysis over High-Speed Data Streams", IEEE/ACM Trans. on Networking, vol. 15, no. 5, pp. 1059-1072, 2007.
[9]T. Bu, J. Cao, A. Chen, P. P. C. Lee, "Sequential Hashing: A Flexible Approach for Unveiling Significant Patterns in High Speed Networks", Computer Networks, vol. 54, no. 18, pp. 3309-3326, 2010.
[10]R. S. Boyer, J. S. Moore, "MJRTY -A Fast Majority Vote Algorithm", Automated Reasoning, pp. 105-117, 1991.


  • 本站原创文章仅代表作者观点,不代表SDNLAB立场。所有原创内容版权均属SDNLAB,欢迎大家转发分享。但未经授权,严禁任何媒体(平面媒体、网络媒体、自媒体等)以及微信公众号复制、转载、摘编或以其他方式进行使用,转载须注明来自 SDNLAB并附上本文链接。 本站中所有编译类文章仅用于学习和交流目的,编译工作遵照 CC 协议,如果有侵犯到您权益的地方,请及时联系我们。
  • 本文链接https://www.sdnlab.com/23514.html
分享到:
相关文章
条评论

登录后才可以评论

朱龙隆 发表于19-09-04
2