关键词: 正则表达式匹配, 有穷自动机, 算法, 评测

Abstract: Deep inspection is playing an important role in providing secure network environment and guaranteeing network service quality. As a key technology for high-performance deep inspection, regular expression matching algorithms attract a great deal of attention in both academic research and industrial practice. With the rapid development of network technology, the volume of network traffic keeps increasing, the rulesets used for deep inspection are becoming larger while more complex, and the network topology is more flexible and dynamic than ever. Existing matching methods are facing many challenges, including those in matching speed, memory consumption, update ability, and so on. This survey first introduces the background of regular expression matching problem, then categorizes existing algorithms in the aspects of memory compression, speed acceleration, new automata design, and rule partition and grouping, and evaluates them in matching speed, memory consumption, as well as preprocessing with real life network traffic and rulesets. A guideline for efficient regular expression matching under different scenarios, and an outline of future work on high performance regular expression matching algorithms are also provided.

Key words: regular expression matching, finite automata, algorithm, evaluation