网络防护墙中多模式匹配算法的研究

发布时间：2021-06-19 17:44

模式匹配算法在计算机科学领域中是一个经典的研究方向。但在IPv4协议渐渐向IPv6协议转换的过程中,IPv6协议令地址空间得以扩大,从而可以将更多的设备并入到物联网环境当中,但与此同时也使得在互联网上产生更多的数据信息。在网络防护墙中,模式集合的任意组合、网络流量的不断加大,这些更为苛刻的要求使得模式匹配算法的性能亟需进一步提升。本文首首先让相关研究背景进行了介绍,介绍了部分较为经典的模式匹配算法的原理及搜索树的经典思路与算法。通过分析经典AC算法的基本思路与基础结构,本文提出了一种基于经典AC算法的改良思路。第二章的分析可以发现,在经典AC算法中goto表本质上是一个有限状态机。存放goto表的方法可以有许多不同的形式。为平衡存储空间和运行效率,在经典的AC算法中是采用Trie树的形式进行存储。本文的研究重点就是改良或者更换这个Trie树的研究方向上,希望能够将经典AC算法的效率进行改善或者提升。接下来本文根据上面的思路提出了使用B树以及B树的多种变形形式来改善经典AC算法。在前面的介绍中一般可以发现Trie树常用来操作字符串。Trie树将不同字符串的相同前缀只保存一份,相对其它直接保存字符串一定程度上节约了空间。但是Trie树在保存较大字符串时资源消耗会很大,这样一来在新的IPv6环境中AC算法的效率必然不能满足新的需求。B树可以有效的减少磁盘读写次避免频繁的查找,往往应用在数据库中作为索引。所以理论上可以提高AC算法的效率。最后,本文对经典AC算法、AC-BM算法以及提出的改良算法进行了性能测试与对比。实验过程中因IPv6进攻数据采用的实验室模拟环境进行,使得其与真实环境有些许变换,但在实验数据中依旧可以发现,改良算法在模式数量大量增加的情况下,成功地保持了较为理想的性能。但是也不难发现新的改良算法在模式数量相对较小或者识别模式长度在一定范围的情况下并不如经典AC算法,这也必然成为下一个研究的重点部分。
【学位授予单位】：湖北工业大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：TP393.08

文章目录

摘要

Abstract

第1章引言

1.1 研究背景

1.2 国内外现状

1.3 本文研究的内容

1.4 论文结构

第2章相关技术研究

2.1 单模式匹配算法

2.1.1 BM算法(Boyer—Moore)

2.1.2 KMP算法

2.2 多模式匹配算法（AC算法）

2.3 搜索树（SEARCH TREE）

2.3.1 平衡二叉树（Binary Search Tree）

2.3.2 字典树（TrieTree）

2.3.3 B树(BTree)

2.4 本章小结

第3章 AC算法的改良研究与实现

3.1 实现机制

3.2 实现方法

3.2.1 预处理阶段

3.2.2 匹配阶段

3.2.3 算法分析

3.3 实验测试

3.3.1 时间性能测试

3.3.2 空间性能测试

3.4 本章小结

第4章模拟进攻环境测试

4.1 测试用网络防护墙介绍

4.1.1 帧捕获模块研究设计

4.1.2 协议解析模块的完成

4.1.3 监测模块研究设计

4.2 模拟进攻测试结果与分析

4.3 本章小结

第5章总结与展望

5.1 工作总结

5.2 进一步工作展望

参考文献

致谢

附录

【相似文献】