计算机工程与应用 ›› 2008, Vol. 44 ›› Issue (22): 74-76.DOI: 10.3778/j.issn.1002-8331.2008.22.022

• 研发、设计、测试 • 上一篇    下一篇

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

刘俊超,赵国鸿,陈曙晖   

  1. 国防科学技术大学 计算机学院,长沙 410073
  • 收稿日期:2008-01-10 修回日期:2008-03-31 出版日期:2008-07-11 发布日期:2008-07-11
  • 通讯作者: 刘俊超

Method to compress DFA transition table for deep packet inspection

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

  1. 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

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

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

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