双向AC 算法及其在入侵检测系统中应用
作者:

Two-Way AC Algorithm and its Application to Intrusion Detection System
Author:
  • 摘要
  • | |
  • 访问统计
  • |
  • 参考文献 [7]
  • |
  • 相似文献
  • |
  • 引证文献
  • | |
  • 文章评论
    摘要:

    在经典的多模式字符串匹配算法-AC 算法的基础上,提出了双向AC 算法。该算法在预处理阶段构造正向和反向两个有限状态自动机,匹配时使用正向有限自动机从文本串中间位置向右扫描,同时依据反向有限状态自动机从中间位置向左扫描。将该算法应用于开放源码的入侵检测系统Snort 中,实验结果表明较BM 算法、WM 算法和AC 算法本算法有更好的时间性能。如使用发现攻击即停止匹配方式检测,则该算法的效率约为AC 算法的1.5 倍。

    Abstract:

    Based on AC algorithm for performing multiple string matching algorithms, two-way AC algorithm was proposed. The algorithm constructs a forward finite automaton and a reversed finite automaton in the preprocessing stage. In the Matching stage it scans the text string from middle to right with a forward finite automaton and concurrently from middle to left with a reversed finite automaton. The algorithm has been implemented by modifying the source code of Snort. The experimental result shows that the time performance of two-way AC algorithm is superior to BM algorithm, WM algorithm and AC algorithm. Efficiency of the algorithm is about 1.5 times AC algorithm if the mode of detection is to discover and stop.

    参考文献
    1 Boyer RS, Moore JS. A fast string searching algorithm. Communications of the ACM, 1997,20(10):762-772.
    2 Wu S, Manber U. Fast algorithm for multi-pattern searching. Tucson: Department of computer science university of arizona, 1994.
    3 Aho A, Corasick M. Efficient string matching: An aid to bibliographic search. Communications of the ACM, 1975,18(6): 333-343.
    4 张庆平. 一种基于Snort 的入侵检测系统的实现和应用[硕士学位论文].长春:吉林大学,2008.
    5 高平利,任金昌.基于Snort 入侵检测系统的分析与实现.计算机应用与软件,2006,23(8):134-138.
    6 Roesch M, Green C. Snort users manual. [2009-9-5].https://www.Snort.org/assets/125/Snort_manual-2_8_5_1.pdf
    7 The Shmoo Group. Capture the capture the flag data use statement.[2007-6-15].http://cctf.shmoo.com/data/cctf-defcon10/
    相似文献
    网友评论
    网友评论
    分享到微博
    发 布
引用本文

杨超.双向AC 算法及其在入侵检测系统中应用.计算机系统应用,2011,20(3):222-225

复制
分享
文章指标
  • 点击次数:2118
  • 下载次数: 4288
  • HTML阅读次数: 0
  • 引用次数: 0
历史
  • 收稿日期:2010-07-12
  • 最后修改日期:2010-09-16
文章二维码
您是第11245625位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京海淀区中关村南四街4号 中科院软件园区 7号楼305房间,邮政编码:100190
电话:010-62661041 传真: Email:csa (a) iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号