学位论文 > 优秀研究生学位论文题录展示

基于Bloom Filter的超点检测算法的研究

作　者: 贺小娜
导　师: 刘卫江
学　校: 大连海事大学
专　业: 计算机科学与技术
关键词: IP流超点可逆Bloom Filter 流抽样
分类号: TP393.06
类　型: 硕士论文
年　份: 2010年
下　载: 51次
引　用: 0次
阅　读: 论文下载

内容摘要

超点检测对于设计高效的流量工程方案有着重要的意义。随着互联网的蓬勃发展,网络入侵事件频繁发生,如蠕虫传播、分布式DDOS攻击、端口扫描等。这些攻击事件在短时间内产生大量的流量链接,导致网络堵塞甚至瘫痪。如扫描式蠕虫在进行传播时,被感染主机通常在短时间内向大量的其他主机发送分组,我们称这一主机为超点。实时识别超点并获得超点的信息对于网络操作和管理有重要的作用。本文对超点检测算法展开研究,以算法的内存消耗情况和测量的精确度为出发点,将可逆Bloom Filter技术应用于超点检测,提出了两种超点检测方案。第一种检测方案是利用Bloom Filter和可逆Bloom Filter检测超点。可逆Bloom Filter包含4个哈希函数,它们选取源IP字符串的部分比特位作为哈希函数的哈希值,根据哈希函数的映射特性,利用选择的哈希短串的重叠比特位还原出IP的信息。给每个哈希函数独立的存储空间,在很大程度上减少了哈希过程所带来的内部冲突。算法分析表明：此算法具有较小的空间复杂度且能扩展到40Gbps高速网络环境中。第二种检测方案是基于“抽样后过滤”技术。首先对链路上的流进行流抽样,然后用Bloom Filter过滤,减少测量中处理的流数,从而提高算法的可扩展性。我们采用基于哈希的流抽样算法,即利用哈希函数来完成流抽样。本文对算法采用来自不同的数据源的Trace进行测试。采用加权相对差作为测量测度,对实验所得的数据进行分析。实验结果表明,本文提出的两种方案可以准确、高效地检测出超点的信息。

全文目录

摘要  5-6
ABSTRACT  6-10
第1章绪论  10-18
  1.1 网络流量测量的必要性  10-12
  1.2 超点的相关定义  12-14
    1.2.1 互联网流的定义  12-13
    1.2.2 超点的定义  13-14
  1.3 超点的研究背景及意义  14-16
  1.4 研究内容与论文结构  16-18
第2章网络测量相关技术  18-28
  2.1 网络测量方法  18-19
  2.2 哈希算法  19-20
  2.3 Bloom Filter的介绍  20-25
    2.3.1 Bloom Filter算法简介  20-23
    2.3.2 Bloom Filter的误差分析及最优哈希函数个数  23-24
    2.3.3 Bloom Filter的扩展  24-25
  2.4 抽样技术  25-27
    2.4.1 基于报文的抽样  25-27
    2.4.2 基于流的抽样  27
  2.5 本章小结  27-28
第3章超点检测算法的相关研究  28-42
  3.1 基于流抽样的超点检测技术  28-31
    3.1.1 基于哈希流抽样算法  28-30
    3.1.2 基于Bloom Filter数据结构的流抽样算法  30-31
  3.2 抽样和数据流相结合的超点检测算法  31-35
    3.2.1 流抽样和Bitmap结构相结合的算法  31-33
    3.2.2 比特矩阵结构和报文抽样方式相结合的算法  33-35
  3.3 双过滤器检测端口扫描算法  35-37
  3.4 自适应抽样算法  37-41
    3.4.1 基于Bloom Filter的参数化的流抽样算法  37-41
    3.4.2 自适应地调整抽样参数的超点检测算法  41
  3.5 本章小结  41-42
第4章利用Bloom Filter检测超点  42-58
  4.1 算法介绍  42-48
    4.1.1 算法整体设计  42-43
    4.1.2 可逆Bloom Filter的构造  43-45
    4.1.3 算法的实施  45-48
  4.2 算法分析  48-50
    4.2.1 算法的内存空间消耗  48-49
    4.2.2 算法适应的链路速度  49
    4.2.3 准确性评价  49-50
  4.3 实验说明  50-54
    4.3.1 实验数据  50-51
    4.3.2 测量测度  51-52
    4.3.3 实验结果  52-54
  4.4 算法的改进加入抽样技术  54-57
    4.4.1 改进算法的整体设计  54
    4.4.2 抽样分析  54-55
    4.4.3 实验结果  55-57
  4.5 本章总结  57-58
第5章总结与展望  58-60
  5.1 论文的创新点  58
  5.2 论文完成的主要工作  58-59
  5.3 工作的展望  59-60
参考文献  60-64
攻读学位期间公开发表论文  64-65
致谢  65-66

基于Bloom Filter的超点检测算法的研究

内容摘要

全文目录

相似论文