微信服务号

微信订阅号

2025年4月13日 10:13 星期日
首页 > 过刊浏览>2011年第22卷第8期 >1838-1854. DOI:10.3724/SP.J.1001.2011.04034
PDF HTML阅读 XML下载 导出引用 引用提醒
面向网络安全的正则表达式匹配技术
作者:
基金项目:

国家自然科学基金(60903209); 国家重点基础研究发展计划(973)(2007CB311100); 国家高技术研究发展计划(863)(2009AA01Z437, 2007AA01Z406, 2007AA01Z467, 2007AA01Z442, 2007AA01Z474, 2011AA012504)


Regular Expressions Matching for Network Security
Author:
  • 摘要
    • | |
  • 访问统计
    • |
  • 参考文献 [41]
    • |
  • 相似文献 [20]
    • |
  • 引证文献
    • | |
  • 文章评论
    摘要:

    分析了基于有穷状态自动机的正则表达式匹配方法的时间复杂度、空间复杂度以及二者之间的制约关系,深入讨论了在网络安全应用中遇到的特有问题与挑战.围绕这两个问题,对当前出现的多种优化技术和策略进行了全面的综述和评价,最后对未来的研究方向进行了总结和展望.

    Abstract:

    This paper analyzes the regular expression matching methods’ time complexity, space complexity and the tradeoff between them. The experiences, problems, and challenges encountered by the regular expression matching in network security field are well-classified and discussed in depth. Focusing on the two issues, a comprehensive overview of the current optimizing techniques and strategies adopted by academic and business communities is presented. Finally, a conclusion and some suggestions for future research are put forward.

    参考文献
    [1] Snort 2.8.x. 2009. http://www.snort.org
    [2] 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]
    [3] Wu S, Manber U. A fast algorithm for multi-pattern searching. Technical Report, TR-94-17, Tucson: Department of Computer Science, University of Arizona, 1994. 1?11.
    [4] Allauzen C, Raffinot M. Factor oracle of a set of words. Technical Report, 99-110, Institute Gaspard-Monge, University deMarne-la-vallee, 1999. 1?28.
    [5] Application layer packet classifier for linux. 2009. http://l7-filter.sourceforge.net/
    [6] Bro intrusion detection system. 2009. http://bro-ids.org/Overview.html
    [7] TippingPoint X505. 2008. http://www.tippingpoint.com/products_ips.html
    [8] Cisco IOS IPS deployment guide. http://www.cisco.com
    [9] Yu F, Chen ZF, Diao YL, Lakshman TV, Katz RH. Fast and memory-efficient regular expression matching for deep packet inspection. In: Proc. of the IEEE/ACM Symp. on Architectures for Networking and Communications Systems. San Jose, 2006. 93?102. [doi: 10.1145/1185347.1185360]
    [10] Kumar S, Dharmapurikar S, Yu F, Crowley P, Turner J. Algorithms to accelerate multiple regular expressions matching for deep packet inspection. In: Proc. of the ACM SIGCOMM. Pisa, 2006. 339?350. [doi: 10.1145/1159913.1159952]
    [11] Becchi M, Cadambi S. Memory-Efficient regular expression search using state merging. In: Proc. of the IEEE Infocom. Anchorage, 2007. 1064?1072. [doi: 10.1109/INFCOM.2007.128]
    [12] Kumar S, Chandrasekaran B, Turner JS, Varghese G. Curing regular expressions matching from insomnia, amnesia, and acalculia In: Proc. of the 3rd ACM IEEE Symp. on Architecture for Networking and Communications Systems. Washington: IEEE, 2007. 155?164.
    [13] Becchi M, Crowley P. A hybrid finite automaton for practical deep packet inspection. In: Proc. of the ACM CoNEXT 2007. 2007. [doi: 10.1145/1364654.1364656]
    [14] Smith R, Estan C, Jha S, Siahaan I. Fast signature matching using extended finite automaton (XFA). In: Proc. of the ICISS 2008. 2008. 158?172. [doi: 10.1007/978-3-540-89862-7_15]
    [15] Hopcroft JE, Motwani R, Ullman JD. An Introduction Automata Theory, Languages and Computation. 2nd ed., Boston: Addison Wesley, 2000. 1?50.
    [16] Chen SH, Su JS, Fan HP, Hou J. An FSM state table compressing method based on deep packet inspection. Journal of Computer Research and Development, 2008,42(8):1299?1306 (in Chinese with English abstract).
    [17] Kong SJ, Smith R, Estan C. Efficient signature matching with multiple alphabet compression tables. In: Proc. of the 4th Int’l Conf. on Security and Privacy in Communication Networks. Istanbul, 2008. 1?10. [doi: 10.1145/1460877.1460879]
    [18] Ficara D, Giordano S, Procissi G, Vitucci F, Antichi G, Pietro AD. An improved DFA for fast regular expression matching. ACM SIGCOMM Computer Communication Review, 2008,38(5):29?40. [doi: 10.1145/1452335.1452339]
    [19] Kumar S, Turner J, Williams J. Advanced algorithms for fast and scalable deep packet inspection. In: Proc. of the IEEE/ACM Symp. on Architectures for Networking and Communications Systems. 2006. 81?92. [doi: 10.1145/1185347.1185359]
    [20] Becchi M, Crowley P. An improved algorithm to accelerate regular expression evaluation. In: Proc. of the IEEE/ACM Symp. on Architectures for Networking and Communications Systems. 2007. 145?154. [doi: 10.1145/1323548.1323573]
    [21] Zhang SZ, Luo H, Fang BX, Yun XC. Fast and memory-efficient regular expression matching using transition sharing. IEICE Trans. on Information and Systems, 2009,E92-D(10):1953?1960. [doi: 10.1587/transinf.E92.D.1953]
    [22] Xu Q, E YP, Ge JG, Qian HL. Efficient regular expression compression algorithm for deep packet inspection. Journal of Software, 2009,20(8):2214?2226 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/3311.htm [doi: 10.3724/SP.J.1001. 2009.03311]
    [23] Myers G. A four russians algorithm for regular expression pattern matching. Journal of the ACM, 1992,39(2):432?448. [doi: 10.1145/128749.128755]
    [24] Green T, 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]
    [25] Smith R, Estan C, Jha S, Kong SJ. Deflating the big bang: Fast and scalable deep packet inspection with extended finite automata. In: Proc. of the ACM SIGCOMM. 2008. 207?218. [doi: 10.1145/1402958.1402983]
    [26] Clark CR, Schimmel DE. Efficient reconfignrable logic circuit for matching complex network intrusion detection patterns. In: Proc. of the 3rd Int’l Conf. on Field Programmable Logic and Application (FIL 2003). New York: Springer-Verlag, 2003. 956?959.
    [27] Moscola J, Lockwood J, Loui RP, Pachos M. Implementation of a content-scanning module for an Internet firewall. In: Proc. of the 11th Annual IEEE Symp. on Field-Programmable Custom Computing Machines. Washington, 2003. 31?38. [doi: 10.1109/FPGA. 2003.1227239]
    [28] Hutchings BL, Franklin R, Carver D. Assisting network intrusion detection with reconfigurable hardware. In: Proc. of the 10th Annual IEEE Symp. on Field-Programmable Custom Computing Machines. Washington, 2002. 111?120. [doi: 10.1109/FPGA. 2002.1106666]
    [29] Sourdis I, Pnevmatikatos D. Pre-Decoded CAMs for efficient and high-speed NIDS pattern matching. In: Proc. of the 12th Annual IEEE Symp. on Field-Programmable Custom Computing Machines. Napa, 2004. 258?267. [doi: 10.1109/FCCM.2004.46]
    [30] Becchi M, Crowley P. Efficient regular expression evaluation: Theory to practice. In: Proc. of the 4th ACM/IEEE Symp. on Architectures for Networking and Communications Systems. New York: ACM Press, 2008. 50?59. [doi: 10.1145/1477942. 1477950]
    [31] Lee J, Hwang SH, Park NS, Lee SW, Jun S, Kim YS. A high performance NIDS using FPGA-based regular expression matching. In: Proc. of the 2007 ACM Symp. on Applied Computing Archive. New York, 2007. 1187?1191. [doi: 10.1145/1244002.1244259]
    [32] Lin CH, Huang CT, Jiang CP, Chang SC. Optimization of regular expression pattern matching circuits on FPGA. In: Proc. of the Conf. on Design, Automation and Test in Europe: Designers’ Forum (DATE 2006). Leuven: European Design and Automation Association, 2006. 12?17. http://portal.acm.org/citation.cfm?id=1131355.1131359
    [33] Faezipour M, Nourani M. Constraint repetition inspection for regular expression on FPGA. In: Proc. of the 2008 16th IEEE Symp. on High Performance Interconnects. Washington, 2008. 111?118. [doi: 10.1109/HOTI.2008.14]
    [34] Sidhu R, Prasanna VK. Fast regular expression matching using FPGAs. In: Proc. of the 10th Annual IEEE Symp. on Field- Programmable Custom Computing Machines. Washington, 2001. 237?238. [doi: 10.1109/FCCM.2001.22]
    [35] Yang YHE, Prasanna VK. Automatic construction of large-scale regular expression matching engines on FPGA. In: Proc. of the 2008 Int’l Conf. on Reconfigurable Computing and FPGAs. Cancun, 2008. 73?79. [doi: 10.1109/ReConFig.2008.47]
    [36] Virtex-4 FPGA, Xilinx. 2006. http://www.xilinx.com
    [37] Becchi M, Crowley P. Extending finite automata to efficiently match Perl-compatible regular expressions. In: Proc. of the Int’l Conf. on Emerging Networking Experiments and Technologies (CoNEXT). Madrid, 2008. [doi: 10.1145/1544012.1544037]
    [38] Becchi M, Wiseman C, Crowley P. Evaluating regular expression matching engines on network and general purpose processors. In: Proc. of the 2009 ACM/IEEE Symp. on Architectures for Networking and Communications Systems. Princeton, 2009. [doi: 10.1145/1882486.1882495]
    [39] Hayeng M, Shaw M. Extended finite automata on stream-oriented architectures using rapid mind. Technical Report, CS 758, Madison: University of Wisconsin-Madison, 2008. 1?11.
    [40] Cao J, Tan JL, Liu P, Guo L. Research of Boolean expression matching. Application Research of Computers, 2007,24(9):70?72 (in Chinese with English abstract).
    [41] Cao J, Liu YB, Liu P, Tan JL, Guo L. Research on ordered Boolean expression matching with window. Journal on Communications, 2007,28(12):125?130 (in Chinese with English abstract).
引用本文

张树壮,罗浩,方滨兴.面向网络安全的正则表达式匹配技术.软件学报,2011,22(8):1838-1854

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2010-03-22
  • 最后修改日期:2010-10-11
文章二维码
友情链接:中国科学院软件研究所中国计算机学会中国科学院国家自然科学基金委员会CCF数字图书馆Int'l J of Softw Info计算机系统应用
您是第19820051位访问者
版权所有：中国科学院软件研究所 京ICP备05046678号-3
地址：北京市海淀区中关村南四街4号,邮政编码：100190
电话：010-62562563 传真：010-62562533 Email：jos@iscas.ac.cn
技术支持：北京勤云科技发展有限公司

京公网安备 11040202500063号