基于FM Sketch的超点检测算法的研究

发布时间：2017-07-27 02:09

  本文关键词：基于FM Sketch的超点检测算法的研究

  更多相关文章： 网络测量 主机基数 超点 FM Sketch IP地址捣碎

【摘要】：随着计算机互联网的蓬勃发展,网络攻击频繁发生,如蠕虫病毒、分布式拒绝服务攻击(DDoS)、端口扫描等。这些攻击事件在短时间内产生大量的网络链接,导致网络堵塞甚至瘫痪。如扫描式蠕虫在进行传播时,其被感染主机通常在短时间内向大量的其它主机发送报文。DDoS则是在短时间内大量不同的主机向同一被攻击主机发送报文。超点是在一段测量时间内链接了大量不同目的主机的源主机。因此,实时识别超点对于网络安全和管理有重要的意义。本文将Flajolet-Martin(FM) Sketch和IP地址捣碎技术应用于超点检测。FM Sketch是一随机化计数结构,而IP地址捣碎使用一个哈希函数将32位的IP地址映射到长度为32位的比特位串中,并且该哈希函数是可逆的。以此为基础提出了两种超点检测算法。第一种检测算法使用5个二维位数组和6个哈希函数,前四个哈希函数选取源IP字符串的部分比特位作为哈希值,根据哈希函数的映射特性,利用选择的哈希短串的重叠比特位还原出源IP字符串,不需要单独的空间存储源IP,减少了读取内存的次数。该算法分为在线报文处理模块和离线统计模块。在线报文处理模块使用哈希函数处理报文并更新位数组,离线统计模块重建源IP字符串,使用FM Sketch估计超点基数并输出超点信息。第二种超点检测算法在第一种算法的基础上加入IP地址捣碎技术,该算法的在线报文处理模块首先捣碎报文的源IP地址,离线统计模块使用捣碎技术将重建的源IP进行可逆变换。在实验中,使用从不同网络中收集到的报文Trace进行实验,使用错误否定率、错误肯定率作为评估标准,将本文的算法和相关的超点检测算法进行对比。实验结果表明,本文提出的算法能够更准确有效地检测出超点。
【关键词】：网络测量 主机基数 超点 FM Sketch IP地址捣碎
【学位授予单位】：大连海事大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：TP393.08
【目录】：

• 摘要5-6
• ABSTRACT6-10
• 第1章 绪论10-16
• 1.1 研究背景10-11
• 1.2 研究意义11-12
• 1.3 国内外研究现状12-14
• 1.4 论文的研究内容和组织结构14-16
• 第2章 网络测量相关技术16-19
• 2.1 FM Sketch16-17
• 2.2 IP地址捣碎17-18
• 2.3 本章小结18-19
• 第3章 超点检测算法的研究19-30
• 3.1 基于流抽样的超点检测算法19-21
• 3.1.1 流抽样19
• 3.1.2 基于哈希流抽样的超连接主机检测算法19-21
• 3.2 基于Bitmap的超点检测算法21-27
• 3.2.1 Bitmap21
• 3.2.2 基于随机老化过滤器的隐超点检测算法21-22
• 3.2.3 基于虚拟向量的超点检测算法22-25
• 3.2.4 基于可逆结构的超点检测算法25-27
• 3.3 基于Bloom Filter的超点检测算法27-29
• 3.3.1 Bloom Filter27-28
• 3.3.2 基于CBF的超点检测算法28-29
• 3.4 本章小结29-30
• 第4章 基于FM Sketch的超点检测算法30-44
• 4.1 FMBF算法30-38
• 4.1.1 总体设计30-31
• 4.1.2 数据结构31-33
• 4.1.3 在线报文处理模块33-35
• 4.1.4 离线统计模块35-38
• 4.2 IM-FMBF算法38-42
• 4.2.1 总体设计38
• 4.2.2 具体描述38-42
• 4.3 算法的性能分析42-43
• 4.3.1 算法的空间复杂度42
• 4.3.2 算法的时间复杂度42-43
• 4.4 本章小结43-44
• 第5章 实验44-59
• 5.1 实验数据44
• 5.2 测量测度44
• 5.3 实验数据分析44-49
• 5.3.1 实验参数47
• 5.3.2 IP地址捣碎前后均匀性对比47-49
• 5.4 FMBF和IM-FMBF算法实验对比49-51
• 5.4.1 参数设置49
• 5.4.2 实验结果分析49-51
• 5.5 IM-FMBF和RCDS算法实验对比51-58
• 5.5.1 参数设置51-52
• 5.5.2 实验环境52
• 5.5.3 实验结果52-58
• 5.6 本章小结58-59
• 第6章 总结与展望59-60
• 6.1 总结59
• 6.2 工作展望59-60
• 参考文献60-64
• 攻读学位期间公开发表论文64-65
• 致谢65

【相似文献】

中国期刊全文数据库 前10条

1 刘波;;“算法设计与分析”教学探讨[J];高等理科教育;2007年04期

2 肖小克;陈莉;;《算法设计与分析》实践教学探讨[J];福建电脑;2009年10期

3 穆瑞辉;;计算机算法设计研究与思考[J];数字技术与应用;2012年12期

4 潘博;;构建“算法设计与分析”趣味课堂[J];科教文汇(下旬刊);2013年06期

5 王希常,杨志强;一类考场编排算法的设计[J];山东师范大学学报(自然科学版);2002年04期

6 龙腾芳,高金文;“分而治之”方法在算法设计中的应用[J];渤海大学学报(自然科学版);2004年01期

7 吕国英;;《算法设计与分析》教材建设的实施[J];计算机教育;2007年19期

8 徐子珊;;“算法设计与分析”教学中理论与技术的平衡[J];计算机教育;2008年10期

9 郑红;邵志清;符海波;;“算法设计与分析”课程教学改革初探[J];计算机教育;2008年14期

10 高尚;;“算法设计与分析”课程改革初探[J];计算机教育;2008年14期

中国重要会议论文全文数据库 前10条

1 雷咏梅;;椭圆曲线密码体制的算法设计与实现[A];西部大开发 科教先行与可持续发展——中国科协2000年学术年会文集[C];2000年

2 杨盘洪;朱军祥;赵建安;杨静;;机动目标跟踪的模糊变结构交互多模算法[A];2007'中国仪器仪表与测控技术交流大会论文集（二）[C];2007年

3 徐子珊;;《算法设计与分析》课程中的工程教育[A];2005年全国理论计算机科学学术年会论文集[C];2005年

4 王辉;刘治昌;;用一种新算法设计的安全系统[A];2007年中国智能自动化会议论文集[C];2007年

5 舒辉;柳清峰;杜祝平;周蓓;;实践教学模式在本科专业课程教学中的应用[A];中国电子教育学会高教分会2010年论文集[C];2010年

6 彭小宏;阳东升;刘忠;;基于聚类算法的组织协作网设计[A];2006中国控制与决策学术年会论文集[C];2006年

7 李皓;罗熊;;云存储部署优化的进化算法设计[A];2013年中国智能自动化学术会议论文集（第三分册）[C];2013年

8 罗长政;李熙莹;王镇波;罗东华;;一种大流量交叉路口的背景提取与更新算法[A];第十五届全国图象图形学学术会议论文集[C];2010年

9 杨利;李霖;昌月楼;阳国贵;;对称位向量及启发式并行散列连接算法[A];数据库研究与进展95——第十三届全国数据库学术会议论文集[C];1995年

10 张晋;;嵌入式电脑鼠运行算法的研究[A];全国第20届计算机技术与应用学术会议（CACIS·2009）暨全国第1届安全关键技术与应用学术会议论文集（上册）[C];2009年

中国重要报纸全文数据库 前1条

1 ;算法设计的策略[N];电脑报;2003年

中国博士学位论文全文数据库 前10条

1 谷伟哲;齐次光滑算法及其应用[D];天津大学;2010年

2 龙海侠;进化算法及其在生物信息中的应用[D];江南大学;2010年

3 谭跃;具有混沌局部搜索策略的粒子群优化算法研究[D];中南大学;2013年

4 尤海峰;求解隐式目标优化问题的交互式进化算法研究[D];中国科学技术大学;2011年

5 张常淳;基于MapReduce的大数据连接算法的设计与优化[D];中国科学技术大学;2014年

6 郭崇慧;地区中长期发展规划若干定量模型、算法及应用研究[D];大连理工大学;2002年

7 蒋蔚;粒子滤波改进算法研究与应用[D];哈尔滨工业大学;2010年

8 孙贺;算法设计中的若干前沿问题[D];复旦大学;2009年

9 陈宁涛;基于二分技术的高效算法设计及其应用[D];华中科技大学;2006年

10 娄晓文;无符号基因组切割再粘贴重组问题的算法研究[D];山东大学;2010年

中国硕士学位论文全文数据库 前10条

1 李欣园;基于选择偏好的组合聚类算法研究与实现[D];内蒙古大学;2015年

2 杨潇;界约束非线性最小二乘问题的无导数算法[D];上海交通大学;2015年

3 王晓璐;基于Zynq的LS-SVM算法加速器设计[D];哈尔滨工业大学;2015年

4 楼磊磊;医疗保险数据异常行为检测算法和系统[D];浙江大学;2015年

5 齐海龙;基于改进人工蜂群算法的非线性系统辨识方法研究[D];北京化工大学;2015年

6 蔡平梅;结构化稀疏信号的恢复算法研究[D];上海大学;2015年

7 赵晨阳;基于蚁群算法的高阶图匹配方法研究[D];西安电子科技大学;2014年

8 苟清松;多目标粒子滤波检测前跟踪算法研究[D];电子科技大学;2015年

9 李枝勇;蝙蝠算法及其在函数优化中的应用研究[D];上海理工大学;2013年

10 李莲;基于蜂群和粗糙集的聚类算法研究[D];长沙理工大学;2014年

，

本文编号：579339