论文部分内容阅读
随着计算机和Internet技术的普及与发展，网络在人们日常生活中发挥越来越重要的作用，但是随之而来的网络安全问题也日益突出。入侵检测系统作为保障网络安全的重要防护措施得到了广泛应用，模式匹配作为入侵检测系统中的一项关键技术，其性能优劣关系到整个入侵检测系统的效率，提高模式匹配的效率是提高这类系统检测能力的关键所在。本文简单介绍了入侵检测系统，分析了多模式匹配算法在其中的应用，并对AC、AC_BM和WM算法做了详细说明。但是，随着网络技术的发展和规则集复杂性的增加，这些传统的字符串匹配引擎正逐渐被先进的正则表达式引擎所替代。正则表达式匹配引擎一般是基于非确定的有限自动机（Nondeterministic FiniteAutomaton,NFA）和确定的有限自动机（Deterministic Finite Automaton, DFA）的。基于NFA的匹配引擎匹配速度慢，但存储空间相对较小。基于DFA的匹配引擎具有先天的速度优势，但是消耗的存储空间过大，并且随着规则集规模的增大，其对存储空间的需求更大。本文从减少构造的自动机的状态数出发，提出了一种有效的DFA合并算法（称为COM_DFA算法）。在自动机构造过程中，将各个正则表达式分开处理，避免合并自动机时状态和迁移边之间的交互重叠情况的出现，能够大大地减少自动机的状态数。并且，通过引入空转移合并DFA，构造一个具有最小状态数的自动机，从而减少存储空间需求。最后，引入压缩率CR(Compressed Rate)的概念来描述合并算法对自动机状态数的压缩比率。实验结果表明算法对DFA状态数具有较好的压缩效果。针对NFA和DFA的匹配速度和内存需求之间的矛盾，提出一种基于DFA-NFA结构有限自动机的正则表达式匹配算法（称为D_N算法）。算法采用DFA-NFA结构实现自动机的构造，分开处理引起DFA空间爆炸的状态，以降低存储需求。由于网络中的数据只有很少一部分是恶意数据，而大部分是正常数据，DFA部分在NFA部分之前的设计可以实现数据过滤功能，能够加快算法的匹配速度。同时，在自动机的构造过程中，针对DFA-NFA边界上的关键状态，对同样的输入字符，设置相应迁移边的优先级。匹配过程采用基于优先级的查找算法，检查优先级来确定当前状态在读入字符下可以跳转到的下一状态，从而加快匹配过程。D_N算法的测试结果表明其匹配效率和在状态方面的存储需求比传统算法有较大提高。