资源描述：
《网络入侵检测中多模式匹配的状态编码方法.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、ISSN1000-0054清华大学学报(自然科学版)2009年第49卷第4期w39CN11-2223/NJTsinghuaUniv(Sci&Tech),2009,Vol.49,No.4http://qhxbw.chinajournal.net.cn网络入侵检测中多模式匹配的状态编码方法吴碧海,赵有健(清华大学计算机科学与技术系,北京100084)摘要:为了减少网络入侵检测系统的硬件实现方案中自域的研究热点之一。动机占用的存储容量,提出了一种自动机状态的编码方法。NIDS通常由特征串集合和匹配引擎两部分组该方法通过对自动机状态重新进行编号,使得多个状态能够成。匹
2、配引擎从报文的应用层数据中搜索特征串集用一个通配编号来表示,这样自动机中具有相同输入和下一合中所有的特征串,并报告所有的匹配位置。高效的状态的多条变迁就能被聚合为一条,大大减小了需要存储的[1]多模式匹配算法如Aho-Corasick、Commentz-变迁数目。可以证明状态编码方法能够将变迁数目减小到理[2][3]Walter、Wu-Manber是匹配引擎的核心技术。论上最小值同时保证自动机恒定的处理速率。实验表明,对于常见特征串集,该方法可以将变迁数目减小98.9%以上。为了按照目前网络Gbit的速率实时检测报文,研究者提出了很多NIDS的硬件实现方案。关
3、键词:网络入侵检测系统;多模式匹配;状态编码;自动[1]机基于自动机的多模式算法如Aho-Corasick由于能够按照恒定速率处理目标串并且实现简单,被中图分类号:TP393.08文献标识码:A广泛应用在硬件方案中。针对硬件实现方案的研究文章编号:1000-0054(2009)04-0612-04主要集中在如何减小自动机占用的存储容量和提高自动机的处理能力。文[4]提出了bit-split方法将一Stateencodingformulti-patternmatching个大自动机划分成多个小自动机以减小存储消耗。fornetworkintrusiondetec
4、tion文[5]采用编码压缩算法来提高存储效率。上面两种WUBihai,ZHAOYoujian方案都采用查询表结构存储每个状态接受一个输入(DepartmentofComputerScience&Technology,字节后所有可能的256个下一状态,而实际的DFATsinghuaUniversity,Beijing100084,China)中每个状态包含的变迁数目要远小于256,因此查Abstract:Astateencodingschemewasdevelopedtoreducethe询表结构增加了不必要的存储消耗。文[6]和[7]采storagefort
5、heDeterministicFiniteAutomaton(DFA)inhardware-basedNetworkIntrusionDetectionSystem(NIDS).The用变迁表结构只存储自动机中每个状态实际包含的schemegreatlyreducesthenumberoftransitionsbyre-encodingthe变迁,并分别提出了B-FSM和DelayedInputDFADFAstatessothatmultiplestatescanberepresentedbyonenumber2andtransitionswiththesam
6、einputtothenextstatecanbe(DFA)方法来减小表示一个自动机所需要的变迁combinedintoonetransfer.Theoreticalanalysesprovethatthis数目。但是,B-FSM方法减小变迁数目较少,而stateencodingschememinimizesthenumberoftransitionswhile2DFA虽然能大量减小变迁数目,却降低了NIDS的maintainingthebestworstcaseDFAperformance.ExperimentsonamainstreamNIDSrulese
7、tshowthatthestateencodingscheme处理速率。reducesthetransitionsbymorethan98.9%.本文基于变迁表结构提出了一种自动机状态的Keywords:NIDS;multi-patternmatching;stateencoding;DFA编码方法,能够将Aho-Corasick算法生成的自动机的变迁数目减到理论上最小值,同时不影响NIDS随着Internet的普及,网络安全成为越来越重要的课题。传统的网络安全工具如防火墙只检测网收稿日期:2008-03-27基金项目:国家自然科学基金资助项目(9060402
8、9,60773150);络层和传输层的
