论文部分内容阅读
随着互联网的快速发展，深度包检测系统成为了网络中越来越重要的组件。当前，由于深度包检测系统的核心算法的设计缺陷，实际的深度包检测系统往往无法提供线速处理的能力，同时，网络环境的不断复杂化也使深度包检测系统面临着前所未有的挑战。现代深度包检测系统大多数都采用正则表达式来定义模式，但传统上利用有穷状态自动机(FA)实现正则表达式可能导致匹配算法的时间复杂度很高或者需要大规模的存储空间。这些因素导致基于正则表达式的深度包检测系统效率低下。本文基于正则表达式的深度包检测系统，设计和实现了基于正则表达式多模式匹配算法来解决上面的问题，包含的主要内容有：
在正则表达式的存储优化方面：
●分析了造成DFA状态数膨胀的正则表达式的类型，提出一种量化DFA状态数膨胀的参数一正则表达式的膨胀率DR(Distent Rate)，并将这个参数应用到之后的算法中。
●提出了一种正则表达式分片的算法(RECCADR)，将正则表达式分成了头部、中部、尾部三个部分，其中头部和尾部是造成正则表达式的DFA状态数膨胀较轻的部分，中部是膨胀严重的部分。通过正则表达式合理分片，可以显著降低DFA的状态数，从而降低DFA的存储空间。
●提出了一种正则表达式集合的分群算法(REGADR)，基于正则表达式的膨胀率DR(Distent Rate)将正则表达式集合有选择的分成DFA状态数相近的群，降低了正则表达式匹配算法的空间复杂性。
基于上面对正则表达式存储优化方面取得的进展，设计了在高速网络条件下在深度包检测系统的一种新型的多模式匹配算法-TSREMA，具体包括：
●设计了TSREMA算法的存储结构：平行根两级结构的存储模型，通过合理分布模式集合，可以在保持匹配算法性能下降不大的情况下，有效地降低了模式集合的存储消耗。
●设计了TSREMA算法的匹配策略：在存储结构的基础上，设计了包含快速处理通道和慢速处理通道的区分服务匹配策略，保证了正常数据包的快速通过和恶意数据包的全面检测，适合深度包检测系统在网络环境下提供线速处理服务。