ISSN 1000-1239 CN 11-1777/TP

• 信息安全 •

### 基于并行字符索引的多步长正则表达式匹配算法

1. 1(湖南大学信息科学与工程学院 长沙 410082); 2(中国科学院计算技术研究所 北京 100190) (lxding@hnu.edu.cn)
• 出版日期: 2015-03-01
• 基金资助:
基金项目：国家“九七三”重点基础研究发展计划基金项目(2012CB315805)；国家自然科学基金项目(61173167，61100171)

### Multi-Stride Regular Expression Matching Using Parallel Character Index

Ding Linxuan1, Huang Kun2, Zhang Dafang1

1. 1(College of Computer Science and Electronics Engineering, Hunan University, Changsha 410082); 2(Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100190)
• Online: 2015-03-01

Abstract: Deep packet inspection (DPI) is a key function of network intrusion detection and prevention systems (NIDPS). TCAM-based regular expression matching algorithms have been proposed as a promising approach to improve processing speed, which is an important research direction of DPI. Ternary content addressable memory (TCAM) has the characters of high searching speed and small storage space, as well as the TCAM power consumption is proportionate to its storage space. Deterministic finite automaton (DFA) requires large storage space and the storage space of multi-stride DFA grows exponentially with the stride of DFA, which leads to high TCAM power consumption of DFA, especially for multi-stride DFA. This paper presents a parallel character-indexed multi-stride regular expression matching algorithm to address such limitation. This algorithm uses the idea of building parallel character indexes according to the stride of DFA, and reduces the number of activated TCAM blocks by using bitmap intersection, which in turn translates low TCAM power. Experimental results show that our algorithm reduces the TCAM power by more than 99.8% as well as the TCAM space usage by 48.5%~65.3%, and improves the matching throughput by 1.9~2.6 times compared with previous solutions based on multi-stride DFA.