Skip to main content

模式匹配

(Pattern Matching)#

课题介绍#

随着互联网应用不断增加以及应用层协议趋于复杂，传统的基于网包包头（packet header）的状态检测（stateful inspection）技术已经不能满足当前网络安全处理的需求，基于网包载荷（packet payload）的深度检测（DI, Deep Inspection）技术由此兴起，并且已经成为业务感知路由器、深度检测防火墙（Deep Inspection Firewall）、网络入侵检测系统（NIDS，Network Intrusion Detection System）、网络入侵防御系统（NIPS，Network Intrusion Prevention System）以及统一威胁管理（UTM, Unified Threat Management）等设备的关键组成部分和核心技术所在。本课题深入研究深度检测技术中的模式匹配（pattern matching）问题，即如何在网流的载荷中快速高效地匹配字符串（string）或正则表达式（regular expression）特征。随着软件定义网络（SDN, Software Defined Networking）等概念的提出以及云计算的日益普及，模式匹配在可编程网络传输节点和服务节点上面临着规则特征复杂、规则数目庞大、规则更新快速、高吞吐率、低延时、低功耗等需求。因此，结合当前最新的软硬件平台进展，研究新型高效能的模式匹配算法，对于开发和推广高性能网络安全检测及内容感知等设备具有十分重要的意义。

研究方法与研究目标#

1）算法分析#

  1. 算法理论分析
  • 数据结构层面：挖掘算法数据结构中存在的多维度的冗余，追溯冗余存在的理论依据，通过压缩冗余项来优化算法。
  • 自动机层面：基于自动机理论，分析算法状态空间爆炸的特征，通过空间转换思想来设计大规模有效的算法。
  • 规则层面：从正则语言的语义出发，研究规则表述问题的根源，通过规则自身的变换来设计高效可扩展的算法。
  1. 复杂度分析
  • 研究模式匹配算法在时域和空域的统计特性和理论复杂度；通过引入平滑分析（smoothed analysis）研究和对比算法的真实性能。
  1. 系统实现分析
  • 研究算法与系统架构设计的结合，将算法高效地映射和部署在通用硬件、专有硬件、分布式系统等平台和系统上。

2) 算法设计：#

  1. 字符串匹配
  • 跳跃优化：通过启发式算法来优化WM算法的跳跃搜索。代表算法：RSI，MDH。
  • 多级哈希：通过两级哈希构造和自动机的双数组结构存储实现大规模的高速匹配。代表算法：TFD。
  • 双重表述：通过AC自动机表述外加后缀树表述实现跨序列数据包的无缓冲匹配。代表算法：AC-Suffix-Tree。
  1. 正则表达式匹配
  • 二维转移压缩：通过状态内维度和状态间维度上的压缩来去除冗余的相同转移。代表算法：FEACAN，RCDFA。
  • 状态简化表示：通过自动机结构到树结构的转换来简化状态节点的表示。代表算法：SC_FA。
  • 规则拆分表述：通过先去除规则本身的歧义后重构原规则语义来实现非膨胀的规则匹配。代表算法：FREME。
  • 规则拆分匹配：通过拆分出正则表达式匹配中的字符串匹配，重构正则匹配流程。代表算法：HES，E-HES。
  • 规则优化分组：通过对大规模正则表达式规则集合进行优化分组，减少因正则表达式之间语义交叠造成的自动机状态爆炸。代表算法：GARegex。
  • 并行规则匹配：通过设计中间状态单元，减少多核平台上并行化正则表达式匹配带来的额外计算开销。代表算法：ParaRegex。
  • 匹配过程编码：通过比特编码，将自动机中的状态转移转化为布尔矩阵乘法运算。代表算法：BFA。

3) 算法实现：#

  • 网络处理器平台：在Cavium OCTEON 5860网络处理器平台上实现了20 Gbps深度检测原型系统。
  • 通用处理器平台：在Intel Xeon E5504处理器平台上实现了100Mbps的千万条字符串规则规模级别的TFD算法原型，以及300Mbps的压缩率在80%以上的SC_FA算法仿真；在Intel Pentium E5300处理器平台上实现了节省1~2个数量级内存消耗的AC-Suffix-Tree算法。在Intel i7-3770处理器平台上实现了匹配速度、存储开销及预处理时间上均提升1~2个数量级的FREME算法。在Intel i7-6700HQ处理器平台上实现了10k patterns下吞吐达到1.7Gbps的HES算法。
  • 众核平台：在Tilera TILEPRO64众核平台上实现了3Gbps的千条正则表达式规则规模级别的CSR算法原型。
  • FPGA平台：在Xilinx Virtex-5 FPGA平台上实现了10 Gbps的压缩率在90%以上的FEACAN和RCDFA算法仿真。

项目合作：#

  • 2015.05 - 2017.03 北京云杉世纪网络科技有限公司委托开发合作
  • 2011.07 - 2012.06 清华大学信息科学与技术国家实验室（筹）学科交叉基金资助（合作者USC Prof. Viktor Prasanna）
  • 2011.01 - 2012.12 北京市支持中央在京高校共建项目资助
  • 2010.07 - 2011.06 清华大学信息科学与技术国家实验室（筹）学科交叉基金资助（合作者USC Prof. Shanghua Teng）
  • 2007.06 - 2009.12 国家高新技术研究发展计划（863计划）信息技术领域重点项目资助
  • 2007.08 - 2008.07 华为基金资助
  • 2007.06 - 2008.12 清华大学信息科学技术学院基础研究基金资助