入侵检测系统中模式匹配算法的研究

论文摘要

本文介绍了课题的研究背景和意义、入侵检测的发展与现状、模式匹配算法的发展与现状和入侵检测系统概述,重点研究了几种常见的模式匹配算法。包括:BF算法、KMP算法、BM算法、BMH算法、BMHS算法。对各种算法的性能进行了详细分析。然后针对BMHS算法的不足,和结合BMH算法和BMHS算法的优点提出了两种改进的模式匹配算法—BMHS2算法和BMHS3算法。给出了算法执行代码,并对新算法的效率进行了分析,最后通过实验验证了改进算法的优越性。本文的主要工作和贡献包括:（1）对入侵检测中的模式匹配算法进行了详细的分析,并指出了BMHS算法的不足。（2）结合BMH算法和BMHS算法的优点,提出了新的模式匹配算法—BMHS2算法,BMHS2算法在BMH算法和BMHS算法的基础上,增加了模式P中出现字符到模式P最右位置的距离d的计算,能够跳过很多无效字符,实现了最大移动距离2m,最好情况下的时间复杂度为O（n/2m）。实验仿真结果表明,改进算法与BMH算法和BMHS算法相比,在匹配次数和执行时间上都更优,能改善入侵检测系统的检测效率。（3）针对BMHS算法的不足,提出了新的模式匹配算法—BMHS3算法,BMHS3算法在BMHS算法的基础上增加了最末位字符和在匹配串中出现字符的前一位置字符是否出现的考虑,能够跳过很多无效字符,多数情况下能实现最大移动距离m+1。最大移动距离的概率比BMHS算法更高。实验仿真结果表明,改进算法与BMHS算法相比,在匹配次数和执行时间上都优于BMHS算法,能改善入侵检测系统的检测效率。

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 研究背景
• 1.1.1 课题来源
• 1.1.2 网络安全技术的重要性
• 1.2 研究意义
• 1.3 入侵检测的发展与现状
• 1.3.1 主机审计—入侵检测的起点
• 1.3.2 入侵检测技术发展的历程
• 1.3.3 现有入侵检测系统存在的主要问题
• 1.4 模式匹配算法的发展与现状
• 1.5 本文的研究内容及内容安排
• 第二章 入侵检测系统概述
• 2.1 入侵检测的相关概念
• 2.1.1 入侵
• 2.1.2 入侵检测
• 2.1.3 入侵检测系统
• 2.2 入侵检测系统的原理
• 2.3 入侵检测系统的模型和结构
• 2.3.1 入侵检测系统的基本模型
• 2.3.2 入侵检测系统的结构
• 2.4 入侵检测系统的产品分类
• 2.4.1 根据采集数据源的不同分类
• 2.4.2 根据检测方法分类
• 2.5 入侵检测的算法
• 2.6 小结
• 第三章 模式匹配算法的研究
• 3.1 基于模式匹配的检测方法
• 3.1.1 模式匹配算法的背景及原理
• 3.1.2 基于模式匹配系统的特点
• 3.1.3 模式匹配系统的实现
• 3.1.4 模式匹配的网络数据包的主要特征
• 3.2 单模式字符串匹配算法
• 3.2.1 BF（Brute Force）算法
• 3.2.2 KMP（Knuth-Morris-Pratt）算法
• 3.2.3 BM 算法
• 3.2.4 BMH 算法
• 3.2.5 BMHS 算法
• 3.3 小结
• 第四章 模式匹配算法的改进
• 4.1 改进算法一—BMHS2 算法
• 4.2 改进算法二—BMHS3 算法
• 4.3 仿真实验状况与结果分析
• 4.4 小结
• 第五章 总结与展望
• 5.1 总结
• 5.2 入侵检测系统的发展趋势
• 参考文献
• 致谢
• 附录Ａ个人简历、在学期间发表的学术论文与研究成果
• 附录Ｂ实验中四种算法测试代码