入侵检测系统中基于正则表达式的匹配算法研究

摘要

入侵检测系统(Intrusion Detection System，IDS)是当前最有效的网络安全防御系统，它能够准确高效地识别各种网络入侵行为。IDS依赖于基于正则表达式的特征库，它通过数据收集引擎把收集到的网络数据流和特征库中的特征进行匹配，根据匹配的结果来确定是否存在着网络入侵行为。但在IDS中，匹配的时间通常会占用整个检测时间的90％以上，所以高性能的基于正则表达式匹配算法成为了当前研究的重点。
　　 使用正则表达式来描述各种网络威胁，在匹配时通常需要将表达式转换成确定的有限自动机(Deterministic Finite Automata，DFA)。面对当今高速的网络，传统的基于DFA的正则表达式匹配算法已经很难适用于当前的环境，针对DFA存储空间过大的问题，我们分别从DFA的状态和转移边进行优化。
　　 为了减少DFA的状态，本文提出了一种基于局部查找分组(Local Seeking Grouping，LSG)的正则表达式匹配算法。为了能更好的描述我们的算法，我们对正则表达式的矛盾进行了定义，证明了当表达式之间处于矛盾为正和矛盾独立状态的时候，正则表达式集合的最优k分组问题实际上就是最小边缺失的k分割问题，而最小边缺失的k分割问题也就是最大k分割问题，即NP-hard问题。最后用LSG算法来解决分组问题，并证明了对于最大k分割问题，LSG算法的近似比为k/(k-1)。实验表明，与正则表达式不分组、分为一组相比，正则表达式分若干组在状态总数、匹配时间和存储空间上远远小于另外两种方式;与Becchi、REGADR和Fang Yu分组算法相比，LSG分组算法在分组数、分组时间、状态总数、匹配时间和存储空间上的性能远远优于另外三种算法。
　　 为了减少DFA的转移边，本文提出了一种基于紧密的可扩展的有限自动机（Inseparable Extended Finite Automation，IXFA）的正则表达式匹配算法。IXFA是一种基于XFA的有限自动机，同时也是一种基于DFA的有限自动机，DFA、XFA和IXFA从本质上来说并无区别，只是结构略有不同而已。在IXFA构造过程中，本文提出了基于优先级的转移边压缩算法，即压缩相同后续状态最多的转移边，设置优先级来解析转移边，已达到减少存储空间的目的;在IXFA匹配过程中，本文提出了基于位图的转移边查找算法，即采用位图来并行查找不同优先级的转移边子集，输出优先级最高的匹配转移边，从而确保转移边查找的匹配效率。实验表明，与XFA相比，IXFA在转移边数上、存储空间和匹配时间上的性能远远优于XFA。

目录

声明

摘要

第一章 绪论

1．1 入侵检测系统概述

1．2 入侵检测系统的模型

1．3 入侵检测系统的分类

1．4 典型的入侵检测系统

1．5 基于正则表达式匹配的入侵检测系统

1．6 主要工作和本文结构

第二章 基于正则表达式的匹配算法

2．1 基本概念

2．11 正则表达式

2．12 不确定的有限自动机

2．13 确定的有限自动机

2．14 NFA和DFA的区别

2．2 传统的匹配算法

2．21 传统匹配算法模型

2．22 构造解析树

2．23 构造NFA

2．24 构造DFA

2．25 基于NFA的正则表达式匹配算法

2．26 基于DFA的正则表达式匹配算法

2．3 传统匹配算法的改进思路

2．31 NFA和DFA的选择

2．32 DFA的优化

2．4 本章小结

第三章 DFA状态的优化

3．1 引言

3．2 DFA状态优化的相关研究

3．21 基于状态融合的正则表达式分组算法

3．22 基于膨胀率的正则表达式分组算法

3．23 基于状态增长率的正则表达式分组算法

3．3 基于LSG的正则表达式匹配算法

3．31 正则表达式之间的矛盾

3．32 分组算法的评价指标

3．33 分组算法的两个假设及分析

3．34 最优k分组问题的分析

3．35 LSG算法

3．4 算法实验及性能分析

3．41 匹配引擎

3．42 合成特征规则集

3．43 实际特征规则集

3．5 本章小结

第四章 DFA转移边的优化

4．1 引言

4．2 DFA转移边优化的相关研究

4．21 基于XFA的正则表达式匹配算法

4．22 基于D2FA的正则表达式匹配算法

4．23 基于内容寻址D2FA的正则表达式匹配算法

4．3 基于IXFA的正则表达式匹配算法

4．31 基于XFA的正则表达式匹配算法

4．32 基于优先级的转移边压缩算法

4．33 基于位图的转移边查找算法

4．34 算法分析

4．4 算法实验及性能分析

4．41 匹配引擎

4．42 合成特征规则集

4．43 实际特征规则集

4．5 本章小结

第五章 总结及未来工作展望

5．1 本文总结

5．2 未来工作展望

致谢

参考文献

附录

1．项目研究

2．论文发表