Algorithms Improving the Storage Efficiency of Deep Packet Inspection
Author:
Affiliation:

  • Article
  • | |
  • Metrics
  • |
  • Reference [17]
  • | |
  • Cited by [2]
  • | |
  • Comments
    Abstract:

    With the rapid increase in the number of deep packet inspection rules, it is necessary to store deterministic finite automata (DFA) representations of regular expressions efficiently in order to meet the practical requirements of network processing. First, a new hybrid FSM construction method is proposed for compressing the states of DFA. DFAs are built in different ways for the regular expressions. By analyzing the states of the converted DFAs, the distinguished complexities of DFAs become noticeable. This leads to a change in state of the DFA from a quadratic/exponential expression to a linear expression. Next, an efficient compressing algorithm, called Weighted Delayed Input DFA (WD2FA), is proposed for state transitions of the DFAs. This algorithm can reach a reduction rate of about 95% for the regular expressions with any complexity. The analysis shows that the performance of the WD2FA is better than the delayed input DFA (D2FA), and D2FA is a special case of WD2FA with weight 0. The experimental results show that the number of states for the FSM can be controlled at the level of linearity, and transitions are reduced to 7% based on the compression states.

    Reference
    [1] Aho AV, Corasick MJ. Efficient string matching: An aid to bibliographic search. Communications of the ACM, 1975,18(6): 333-340 . [doi: 10.1145/360825.360855]
    [2] Li WN, E YP, Ge JG, Qian HL. Multi-Pattern matching algorithms and hardware based implementation. Journal of Software, 2006, 17(12):2403-2415 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/17/2403.htm [doi: 10.1360/jos172403]
    [3] Hopcroft JE, Motwani R, Ullman JD. Introduction to Automata Theory, Languages, and Computation. 3rd ed., Reading: Addison Wesley, 2006.
    [4] Hopcroft J. An O(n log n) algorithm for minimizing states in a finite automaton. Technical Report, STAN-CS-TR-71-190, Stanford: Stanford University, 1971.
    [5] Yu F, Chen ZF, Diao YL, Lakshman TV, Katz RH. Fast and memory-efficient regular expression matching for deep packet inspection. In: Bhuyan LN, Dubois M, Eatherton W, eds. Proc. of the 2006 ACM/IEEE Symp. on Architecture for Networking and Communications Systems. New York: ACM, 2006. 93-102 . [doi: 10.1145/1185347.1185360]
    [6] AbuHmed T, Mohaisen A, Nyang D. A survey on deep packet inspection for intrusion detection systems. Magazine of Korea Telecommunication Society, 2007,24(11):25-36 .
    [7] BrodieBC, Cytron RK,Taylor DE. A scalable architecture for high-throughput regular-expression pattern matching. In: Kaeli D, ed. Proc. of the 33rd Int’l Symp. on Computer Architecture. New York: ACM, 2006. 191-202 . [doi: 10.1109/ISCA.2006.7]
    [8] Becchi M, Crowley P. An improved algorithm to accelerate regular expression evaluation. In: Yavatkar R, Grunwald D, Ramakrishnan KK, eds. Proc. of the 2007 ACM/IEEE Symp. on Architecture for Networking and Communications Systems. New York: Association for Computing Machinery, 2007. 145-154 . [doi: 10.1145/1323548.1323573]
    [9] Kumar S, Dharmapurikar S, Yu F, Crowley P, Turner J. Algorithms to accelerate multiple regular expressions matching for deep packet inspection. In: Rizzo L, Anderson T, McKeown N, eds. Proc. of the 2006 Conf. on Applications, Technologies, Architectures, and Protocols for Computer Communications. New York: Association for Computing Machinery, 2006. 339-350 . [doi: 10.1145/1159913.1159952]
    [10] Tuck N, Sherwood T, Calder B, Varghese G. Deterministic memory-efficient string matching algorithms for intrusion detection. In: Li VOK, Krunz M, Li B, eds. Proc. of the 23rd Annual Joint Conf. of the IEEE Computer and Communications Societies (IEEE INFOCOM), Vol. 4. Washington: IEEE Computer Society, 2004. 2628-2639 . [doi: 10.1109/INFCOM.2004.1354682]
    [11] Floyd RW, Ullman JD. The compilation of regular expressions into integrated circuits. Journal of ACM, 1982,29(3):603-622 . [doi: 10.1145/322326.322327]
    [12] Lin CH, Huang CT, Jiang CP, Chang SC. Optimization of pattern matching circuits for regular expression on FPGA. IEEE Trans. on Very Large Scale Integration (VLSI) Systems, 2007,15(12):1303-1310 . [doi: 10.1109/TVLSI.2007.909801]
    [13] Aldwairi M. Hardware-Efficient pattern matching algorithm and architectures for fast intrusion detection [Ph.D. Thesis]. North Carolina State University, 2006.
    [14] Heering J, Klint P, Rekers J. Incremental generation of lexical scanners. ACM Trans. on Programming Languages and Systems (TOPLAS), 1992,14(4):490-520 . [doi: 10.1145/133233.133240]
    [15] Sommer R, Paxson V. Enhancing byte-level network intrusion detection signatures with context. In: Jajodia S, Atluri V, Jaeger T, eds. Proc. of the 10th ACM Conf. on Computer and Communications Security. New York: Association for Computing Machinery, 2003. 262-271 . [doi: 10.1109/FPGA.2003.1227239]
    [16] Green TJ, Gupta A, Miklau G, Onizuka M, Suciu D. Processing XML streams with deterministic automata and stream indexes. ACM Trans. on Database Systems, 2004,29(4):752-788 . [doi: 10.1145/1042046.1042051]
    [17] Chen D, Wong RK. Optimizing the lazy DFA approach for XML stream processing. In: Schewe KD, Williams H, eds. Proc. of the 15th Australasian Database Conf. Darlinghurst: Australian Computer Society, Inc., 2004. 131-140 .
    Related
    Comments
    Comments
    分享到微博
    Submit
Get Citation

于强,霍红卫.一组提高存储效率的深度包检测算法.软件学报,2011,22(1):149-163

Copy
Share
Article Metrics
  • Abstract:6152
  • PDF: 8617
  • HTML: 0
  • Cited by: 0
History
  • Received:October 17,2008
  • Revised:August 19,2009
You are the first2044705Visitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address:4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code:100190
Phone:010-62562563 Fax:010-62562533 Email:jos@iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063