计算机应用研究2017，Vol.34Issue(5)：1525-1530,6.DOI:10.3969/j.issn.1001-3695.2017.05.056
一种面向深度包检测的DFA压缩算法
Algorithm to compress DFA for deep packet inspection
摘要
Abstract
DFA(deterministic finite automata) is very important to achieve deep packet inspection (deep packet inspection,DPI) technology.With the growing number of deep packet inspection rules,the storage space of DFA expands rapidly.Therefore,this paper presented an effective compression algorithm based character replacement.Using the characteristics that the state transition table in each state is often only a few different jumps,it decomposed the state transition table into the remaining table and the character replacement table to make storage space reduce.In addition,many similar states could share the same character replacement table to further compress the storage space.Finally,it presented an O(n2) compression algorithm which n denoted the number of DFA states.The test results show that the proposed algorithm is more stable compression ratio on the L7-filter and Snort rule set,and the compression ratio is below 5 ％.关键词
正则表达式/字符替换/状态转换表压缩/确定性有限自动机/深度包检测Key words
regular expression/character replacement/state transition table compression/deterministic finite automata/deep packet inspection分类
信息技术与安全科学引用本文复制引用
张伟,许海洋..一种面向深度包检测的DFA压缩算法[J].计算机应用研究,2017,34(5):1525-1530,6.基金项目
国家自然科学基金青年科学基金资助项目(61403223) （61403223）
中国劳动关系学院中央高校基本科研业务费专项基金项目(17ZY005) （17ZY005）
