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

基于位分割的K步长多模式匹配算法的研究

作　者: 朱芳芳
导　师: 李训根
学　校: 杭州电子科技大学
专　业: 电路与系统
关键词: 模式匹配入侵检测 Bloom Filter 位分割状态机
分类号: TP393.08
类　型: 硕士论文
年　份: 2014年
下　载: 1次
引　用: 0次
阅　读: 论文下载

内容摘要

随着网络技术的高速发展和互联网的日益开放，网络应用日趋普及。与此同时，网络带来的攻击行为也引发了人们对网络安全问题的关注。作为维护网络安全的重要手段，入侵检测系统得到了广泛的应用。而模式匹配是入侵检测系统中最重要的一种检测技术，其创新性和有效性将成为提高入侵检测系统性能和效率的关键。论文对入侵检测系统进行了一个简单的概述，介绍了入侵检测的一般过程和分类，并阐述了模式匹配在入侵检测中的应用。此外，论文还对几种经典的模式匹配算法作了详细的介绍，其中包括BF、KMP、BM等单模式匹配算法和AC、AC_BM等多模式匹配算法。论文介绍了Bloom Filter的原理及应用。Bloom Filter是一种基于多个哈希函数映射压缩空间的数据结构，通过寻找一种优化的哈希查找算法可以提高Bloom Filter的性能。针对现有哈希算法中链地址法处理冲突时存在查找效率低的问题，论文设计了一种改进的哈希表查询算法。经分析和实际测试表明，该算法在不增加消耗的同时降低了冲突时执行查询的查找长度，从而缩短了查询响应时间。针对经典AC算法构建的状态机内存利用率低且需要频繁访问外存的问题，论文设计了一种改进的K步长状态机。设计算法主要由以下四个模块组成：改进的AC算法、文本转换、映射机制和匹配查询。其中，改进的AC算法对原AC状态机中各个状态的输出进行了重新定义，映射机制则负责将改进的AC状态机中相应的状态信息映射到K步长状态机中。通过这种映射机制，最终生成的K步长状态机中只包含跳转和输出信息，没有失效函数。而且在状态存储时，改进的K步长状态机在原有链式存储的基础上，只保留出现过的子串输入，对于链表中未出现的子串，则借助查询算法进行处理。因此，和原来的K步长状态机相比，改进的K步长状态机占据更高的内存优势。尽管改进的K步长状态机解决了一些问题，但并没有达到最优的内存资源利用率。为此，在它的基础上，论文提出了一种基于位分割的K步长多模式匹配方法，即从位的角度出发，将原先的一个状态机分割成八个小状态机，每个状态机可以同时读取K个输入字符的K个比特位，当所有子状态机都输出匹配信号时才确定匹配。该算法有两个优点：首先，子状态机的每个状态最多只有2K种输入选择，这使得内存更加紧凑；其次，几个子状态机可以独立并行工作，加快了模式查询的速度。同时，为了避免一些不必要的查询，待匹配的字符可以先进入Bloom Filter引擎过滤出可疑字符，由于Bloom Filter存在假阳性误判，过滤后的字符要进行精确匹配。在文中，精确匹配由位分割状态机来完成。二者的结合从整体上提高了匹配查询的效率。

全文目录

摘要  5-6
ABSTRACT  6-10
第1章绪论  10-15
  1.1 研究背景和意义  10-12
    1.1.1 研究背景  10-11
    1.1.2 研究意义  11-12
  1.2 研究现状和发展趋势  12-13
  1.3 主要研究内容  13-14
  1.4 论文结构安排  14-15
第2章模式匹配算法研究  15-29
  2.1 入侵检测系统概述  15-19
    2.1.1 入侵检测的一般过程  15-16
    2.1.2 入侵检测系统的一般模型  16-17
    2.1.3 入侵检测系统的分类  17-19
  2.2 模式匹配算法在入侵检测中的应用  19-20
  2.3 单模式匹配算法  20-25
    2.3.1 BF(Brute-Force)算法  20-21
    2.3.2 KMP(Knuth-Morris-Pratt)算法  21-23
    2.3.3 BM(Boyer-Moore-Horspool)算法  23-25
  2.4 多模式匹配算法  25-28
    2.4.1 AC(Aho-Corasick)算法  25-28
    2.4.2 AC_BM(Aho-Corasick-Boyer-Moore)算法  28
  2.5 本章小结  28-29
第3章 Bloom Filter查询算法  29-37
  3.1 哈希查询算法  29
  3.2 改进的哈希表查询算法  29-33
    3.2.1 算法思想  30-31
    3.2.2 算法分析  31-32
    3.2.3 实例测试  32-33
  3.3 标准 Bloom Filter 查询算法  33-35
    3.3.1 标准 Bloom Filter 查询算法的基本操作  33-34
    3.3.2 标准 Bloom Filter 查询算法理论分析  34-35
  3.4 Bloom Filter 过滤引擎设计  35-36
  3.5 本章小结  36-37
第4章基于字符的K步长多模式匹配算法  37-45
  4.1 K 步长多模式匹配算法  37
  4.2 K 步长状态机的改进  37-42
    4.2.1 改进的 AC 状态机的设计  38
    4.2.2 文本转换模块的设计  38-39
    4.2.3 改进的 K 步长状态机的建立  39-42
  4.3 匹配查询  42-44
  4.4 本章小结  44-45
第5章基于位分割的K步长多模式匹配算法  45-58
  5.1 基于单字节的位分割状态机  45-51
    5.1.1 构造过程分析  45-50
    5.1.2 搜索匹配过程  50-51
  5.2 基于多字节的位分割状态机  51-56
    5.2.1 构造过程分析  51-55
    5.2.2 搜索匹配过程  55-56
  5.3 算法分析  56-57
  5.4 本章小结  57-58
第6章总结与展望  58-60
  6.1 论文总结  58-59
  6.2 课题展望  59-60
致谢  60-61
参考文献  61-66
附录  66

基于位分割的K步长多模式匹配算法的研究

内容摘要

全文目录

相似论文