Method to compress DFA transition table for deep packet inspection

doi:10.3778/j.issn.1002-8331.2008.22.022

Computer Engineering and Applications ›› 2008, Vol. 44 ›› Issue (22): 74-76.DOI: 10.3778/j.issn.1002-8331.2008.22.022

• 研发、设计、测试 • Previous Articles Next Articles

Method to compress DFA transition table for deep packet inspection

LIU Jun-chao,ZHAO Guo-hong,CHEN Shu-hui

School of Computer Science，National University of Defense Technology，Changsha 410073，China

Received:2008-01-10 Revised:2008-03-31 Online:2008-07-11 Published:2008-07-11
Contact: LIU Jun-chao

一种用于深度报文检测的DFA状态表压缩方法

刘俊超,赵国鸿,陈曙晖

国防科学技术大学计算机学院，长沙 410073

通讯作者: 刘俊超

Abstract

Abstract: Deep packet inspection based on regular expressions has become extremely important due to its applications in IDS/IPS，application protocol recognition，etc.However，DFA transition table of regular expressions require large amounts of memory，and this limits its practical application.This paper splits the DFA transition table into three tables，compresses the tables using run-length coding，and some optimizations are introduced.The test result using some normal applications in l7-filter indicates that the method has more than 90% compressing rate.

Key words: regular expression, deep packet inspection, DFA, transition table compressing

摘要： 基于正则表达式进行深度报文检测在IDS/IPS、应用层协议识别等网络应用中具有重要作用。然而，采用DFA实现正则表达式需要大量的存储空间，限制了它的实际应用。将DFA状态转换表拆分成3个表，使用run-length编码进行压缩，并对压缩方法进行了优化。采用l7-filter中几个常用应用程序的正则表达式进行测试，结果表明该方法压缩效果一般在90%以上。

关键词: 正则表达式, 深度报文检测, 确定有限自动机, 状态转换表压缩

LIU Jun-chao,ZHAO Guo-hong,CHEN Shu-hui. Method to compress DFA transition table for deep packet inspection[J]. Computer Engineering and Applications, 2008, 44(22): 74-76.

刘俊超,赵国鸿,陈曙晖. 一种用于深度报文检测的DFA状态表压缩方法[J]. 计算机工程与应用, 2008, 44(22): 74-76.

[1]	LIU Mingjie, LIANG Yi, AI Zhongliang, JIA Gaofeng. Research on Chinese Text Proofreading Method for Legal Documents [J]. Computer Engineering and Applications, 2020, 56(24): 274-278.
[2]	SHEN Xiaotong, BI Hui, WANG Suhong, LI Wenjie, ZOU Ling. Study on Selection Algorithm of Channels and Classification of EEG in Patients with Depression [J]. Computer Engineering and Applications, 2020, 56(22): 154-159.
[3]	FU Zhe1，2, LI Jun2. Survey on high performance regular expression matching algorithms [J]. Computer Engineering and Applications, 2018, 54(20): 1-13.
[4]	QIN Jianqiang1, KONG Xiangyu1, HU Shaolin2, MA Hongguang3. Performance comparison of methods for estimating fractal dimension of time series [J]. Computer Engineering and Applications, 2016, 52(22): 33-38.
[5]	CHEN Chu1, REN Pinghong1, YU Jiguo1, MA Bingxian2. Perfect state-judging list based minimization algorithm for DFA [J]. Computer Engineering and Applications, 2013, 49(6): 48-51.
[6]	SU Zhitong, GONG Lingling. MRITIS—remote intelligent test input system [J]. Computer Engineering and Applications, 2013, 49(5): 140-143.
[7]	WU Ping1，2, WU Bin1，2. Optimizing process performance of network traffic management model using regression analysis [J]. Computer Engineering and Applications, 2012, 48(4): 104-106.
[8]	WEI Dezhi, HONG Lianxi, LIN Lina, WU Xu. Improved XFA for deep packet inspection [J]. Computer Engineering and Applications, 2012, 48(34): 245-248.
[9]	FAN Shuyi, MENG Chen, WANG Cheng. New minimized algorithm of DFA states [J]. Computer Engineering and Applications, 2012, 48(1): 47-48.
[10]	WANG Xinmin，ZHANG Tao. Judgemental method of differential fault position in DFA attack against DES [J]. Computer Engineering and Applications, 2011, 47(19): 75-77.
[11]	WANG Jie，SHI Cheng-hui. Dynamic application layer protocol identification program based on regular expressions [J]. Computer Engineering and Applications, 2010, 46(18): 103-106.
[12]	HUANG Jin-jing,ZHAO Lei,YANG Ji-wen. Reconstruction of Web sessions using DFA [J]. Computer Engineering and Applications, 2009, 45(8): 138-140.
[13]	ZHANG Xiao-lin，CUI Min，TAN Yue-sheng. Query optimizational algorithm about XML data stream of lazyDFA on DTD [J]. Computer Engineering and Applications, 2009, 45(28): 131-132.
[14]	HUANG Hua-juan,ZHOU Yong-quan. AFSA-BFGS hybrid algorithm of global optimum for optimization problems [J]. Computer Engineering and Applications, 2009, 45(1): 63-65.
[15]	WANG Jie,LIU Ya-bin,SUN Ke-ke. Research of fast and memory-efficient pattern matching algorithm [J]. Computer Engineering and Applications, 2008, 44(32): 93-95.

Method to compress DFA transition table for deep packet inspection

一种用于深度报文检测的DFA状态表压缩方法

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics