论文部分内容阅读
随着正则表达式在网络安全系统和各种服务中的应用越来越广泛,这些系统采用正则表达式匹配算法作为他们的核心,检测数据包有效载荷中的攻击特征。最近几年的研究大多集中在大规模的正则表达式规则集下,如何有效地减少DFA存储空间的开销。在现代网络入侵检测系统中,如何从海量数据中甄别出有害信息,对阻止和遏制潜在的危险行为,对维护网络中数据的传输安全与稳定,对促进互联网产业健康发展,都具有十分重要的现实意义。为了检测数据包有效载荷中的危险模式,需要在线速度内完成正则表达式匹配。虽然确定性有限状态机(DFAs)允许此操作在线性时间内完成,但他们在内存中的存储可能会需要过高的需求。在内存存储空间中,DFA的开销主要用于存储其状态转移表,表的行宽对应DFA的状态数目,而表的列宽对应着每个状态的转移边数目|Σ|(Σ是输入字符的字母表)。对正则表达式规则集进行分组是一种用于解决DFA状态膨胀问题的重要方法。目前为止,对于DFA在内存中存储开销过大问题的解决思路,可以分为两种,即减少DFA的状态数目和压缩DFA的转移边,通过正则表达式规则集分组算法来压缩DFA的存储空间属于上述中的第一种解决思路。本文在对目前状态机优化技术深入分析和研究的基础上,改进了正则表达式分组算法,其可以在处理规模较大的规则集时,提高状态机的匹配性能。由实验数据可知,改进后的算法不仅在分组性能上比一般的分组算法要好,其所需的更新时间也较小。在本文中,还分析和研究了大量的状态机优化技术。其中一种DFA压缩技术能使得在处理N长字符串时,最多产生2N个状态遍历。而且,该算法具有更低的时间复杂性且很适合某些动态场景。与此同时,随着那些以线速度实现正则表达式匹配的技术不断被人们发现。不同的解决方案:如自动机的类型(确定型vs非确定型)和实现具体参数的配置。虽然每种解决方案在某些特定的规则集和流通模式集中运行的很好,但是并没有对大量的方案、规则集和流通模式集的设定进行系统的比较。因此,对于一个实现者,在大量现有的算法和架构方案中做出一个合适的决定,这将是一个极大的挑战。为了解决这个问题,本文对大量的正则模式匹配技术做出一个综合性的评估,考虑到了算法和架构两个方面。还提供了详细的性能报告和通过基于对规则集的简单评估,决定最佳配置的明确指导。这些指导能在实现实际的正则匹配系统中提供显著的帮助。