基于状态子集编码的快速DFA构造算法

doi:10.3969/j.issn.0253-2778.2014.01.001

中国科学技术大学学报 ›› 2014, Vol. 44 ›› Issue (1): 1-11.DOI: 10.3969/j.issn.0253-2778.2014.01.001

• 论著 •

基于状态子集编码的快速DFA构造算法

彭坤杨

中国科学技术大学计算机科学与技术学院,安徽合肥 230027

收稿日期:2013-03-26 修回日期:2013-04-23 接受日期:2013-04-23 出版日期:2013-04-23 发布日期:2013-04-23
作者简介:彭坤杨,男,1986年生,博士生. 研究方向：网络与系统安全,高性能计算体系结构. E-mail:pengkuny@mail.ustc.edu.cn
基金资助:
中国科学技术大学博士研究生学术新人项目资助.

A fast DFA construction algorithm by subset encoding

PENG Kunyang

School of Computer Science and Technology, University of Science and Technology of China, Hefei 230027, China

Received:2013-03-26 Revised:2013-04-23 Accepted:2013-04-23 Online:2013-04-23 Published:2013-04-23

摘要/Abstract

摘要： 网络深度包检测等网络应用广泛采用正则表达式匹配技术检测网络中的传输内容，正则表达式用非确定性有限自动机（NFA）或者确定性有限自动机（DFA）实现.网络应用对匹配速度要求很高，相比NFA，DFA具有确定性的匹配速度，但所有基于DFA的方法需要预先从NFA构造一个与之等价的DFA，于是DFA的构造成为系统瓶颈之一.为此通过深入探索自动机内在运行特性——NFA状态间活跃关系和NFA中导致DFA空间膨胀的因素，设计了一种NFA状态子集的编码方法和查询方法，显著减少了DFA构造过程中状态子集的查询代价.基于入侵检测与防护系统Snort中的真实规则集的实验表明，与传统的子集构造算法相比，该方法减少了8833%~9357%的DFA构造时间.

关键词: NFA, DFA, 正则表达式匹配, 深度包检测

Abstract: Regular expression matching is the foundation of many network functions such as deep packet inspection, which is performed using either non-deterministic finite automaton (NFA) or deterministic finite automation (DFA). To meet the requirement of high-speed regular expression matching, DFA has been the prevalent choice for its deterministic nature and matching efficiency. However, all these DFA-based approaches need to construct a DFA from an NFA as an intermediate step, thus the DFA construction process can be one of bottlenecks for the system. By exploring the inherent properties of finite automaton — whether the NFA states simultaneously active and how the self-looping NFA states lead to explosion of DFA state space — a state subset encoding and searching scheme was designed, and a new DFA construction algorithm was proposed. Through experiments based on real life pattern sets from the Snort intrusion detection system, the new DFA construction algorithm was demonstrated to reduce the running time by 8833%~9357% compared with that of the standard subset construction algorithm.

Key words: NFA, DFA, regular expression matching, deep packet inspection

中图分类号:

TP393

彭坤杨. 基于状态子集编码的快速DFA构造算法[J]. 中国科学技术大学学报, 2014, 44(1): 1-11.

PENG Kunyang. A fast DFA construction algorithm by subset encoding[J]. Journal of University of Science and Technology of China, 2014, 44(1): 1-11.

参考文献

［1］ Hopcroft J E, Motwani R, Ullman J D. Introduction to Automata Theory, Languages and Computation ［M］. 3ed, Addison-Wesley, 2006.
［2］ Aha A V, Corasick M J. Efficient String matching: An aid to bibliographic search［J］. Communications of the ACM, 1975, 18(6): 333-340.
［3］ Boyer R S, Moore J S. A fast string searching algorithm［J］. Communications of the ACM, 1977, 20(10): 762-772.
［4］ Alicherry M, Muthuprasanna M, Kumar V. High speed pattern matching for network IDS/IPS ［C］// Proceedings of the 14th International Conference on Network Protocols. Santa Barbara, USA: IEEE Press, 2006: 187-196.
［5］ Yu F, Katz R H, Lakshman T V. Gigabit rate packet pattern-matching using TCAM［C］// Proceedings of the 12th International Conference on Network Protocols. Berlin, Germany: IEEE Press, 2004: 174-183.
［6］ Sung J S, Kang S M, Lee Y, et al. A multi-gigabit rate deep packet inspection algorithm using TCAM ［C］// Proceeding of IEEE Gliobal Telicommunications Conference. St. Louis, USA: IEEE Press, 2005: 1-5.
［7］ Zu Y, Yang M, Xu Z H, et al. GPU-based NFA implementation for memory efficient high speed regular expression matching ［C］// Proceedings of 17th ACM SIGPLAN on Principles and Practice of Parallel Programming. New Orleans, USA: ACM Press, 2012: 129-140.
［8］ Peng K Y, Dong Q F. TCAM-based NFA implementation ［C］// Proceedings of the 12th ACM SIGMETRICS/Performance joint International Conference on Measurement and Modeling of Computer Systems. London, UK: ACM Press, 2012: 379-380.
［9］ Yu F, Chen Z F, Diao Y L, et al. Fast and memory efficient regular expression matching for deep packet inspection ［C］// Proceedings of the ACM/IEEE Symposium on Architecture for Networking and Communications Systems. San Jose, USA: ACM Press, 2006: 93-102.
［10］ Kumar S, Dharmapurikar D, Yu F, et al. Algorithms to accelerate multiple regular expressions matching for deep packet inspection［C］// Proceedings of the Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications. Pisa, Italy: ACM Press, 2006: 339-350.
［11］ Becchi M, Crowley P. An improved algorithm to accelerate regular expression evaluation ［C］// Proceedings of the 3rd ACM/IEEE Symposium on Architecture for Networking and Communications Systems. Orlando, USA: ACM Press, 2007: 145-154.
［12］ Chen M. TCAM-based high speed regular expression matching［D］. University of Science and Technology of China, Hefei, China, 2010.
［13］ Meiners C R, Patel J, Norige E, et al. Fast regular expression matching using small TCAMs for network intrusion detection and prevention systems［C］// Proceedings of the 19th USENIX conference on Security. Washington, USA: USENIX Association, 2010: 8.
［14］ Peng K Y, Dong Q F, Chen M. TCAM-based DFA deflation: A novel approach to fast and scalable regular expression matching ［C］// Proceedings of IEEE International Workshop on Quality of Service. San Jose, USA: IEEE Press, 2011: 1-3.
［15］ Peng K Y, Tang S, Chen M, etal. Chain-based DFA deflation for fast and scalable regular expression matching using TCAM［C］// Proceedings of the 7th ACM/IEEE Symposium on Architectures for Networking and Communications Systems. Brooklyn, USA: ACM Press, 2011: 24-35.
［16］ Leslie T. Efficient approaches to subset construction ［D］. University of Waterloo, Ontario, Canada, 1995.
［17］ Becchi M. Regular expression processor［EB/OL］. http://regex.wustl.edu/.
［18］ Becchi M and Crowley P. Efficient regular expression evaluation: Theory to practice［C］// Proceedings of the ACM/IEEE Symposium on Architecture for Networking and Communications Systems. San Jose, USA: ACM Press, 2008: 50-59.
［19］ Becchi M, Franklin M A, Crowley P. A workload for evaluating deep packet inspection architectures ［C］// Proceedings of International Symposium on Workload Characterization. Seattle, USA: IEEE Press, 2008: 79-89.
［20］ Smith R, Estan C, Jha S. XFA: Faster signature matching with extended automata ［C］// Proceedings of the IEEE Symposium on Security and Privacy. Oakland, USA: IEEE Press, 2008:187-201.
［21］ Smith R, Estan C, Jha S, et al. Deflating the big bang: Fast and scalable deep packet inspection with extended finite automata ［C］// Proceedings of the ACM SIGCOMM Conference on Data Communications. Seattle, USA: ACM Press, 2008: 207-218.
［22］ Snort: A free and open source network intrusion detection system (NIDS) and network intrusion prevention system (NIPS) ［EB/OL］. http://www.snort.org/.

[1]	刘胜久，李天瑞，刘佳，谢鹏. 带权超网络的多重分形研究[J]. 中国科学技术大学学报, 2020, 50(3): 369-381.
[2]	邵曦煜，李京，周志强. 一种Ceph块设备跨集群迁移算法[J]. 中国科学技术大学学报, 2018, 48(9): 748-754.
[3]	徐华，李京. 面向带宽保障的云中虚拟集群调度算法[J]. 中国科学技术大学学报, 2018, 48(6): 495-503.
[4]	程国林，常红，柯导明，张平. 高速接口中多指针弹性缓冲器设计[J]. 中国科学技术大学学报, 2017, 47(10): 854-861.
[5]	李华康，刘盼，杨一涛，孙国梓. 一种基于节点映射关系的云数据安全代理访问机制[J]. 中国科学技术大学学报, 2017, 47(4): 304-310.
[6]	陈振国，田立勤，林闯. 基于感知源信任评价的物联网数据可靠保障模型[J]. 中国科学技术大学学报, 2017, 47(4): 297-303.

基于状态子集编码的快速DFA构造算法

A fast DFA construction algorithm by subset encoding

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 6

编辑推荐

Metrics

本文评价