基于入侵检测系统正则表达式匹配引擎设计

《基于入侵检测系统正则表达式匹配引擎设计》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、杭州电子科技大学硕士学位论文基于入侵检测系统的正则表达式匹配引擎设计研究生：王奇敏指导教师：李训根副教授2012年12月DissertationSubmittedtoHangzhouDianziUniversityfortheDegreeofMasterTheDesignofRegularExpressionsMatchingEngineBasedonIDSCandidate:WangQiminSupervisor:AssociateprofessorLiXungenDecember，2012杭州电子科技大学学位论文原

2、创性声明和使用授权说明原创性声明本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究工作所取得的成果。除文中已经注明引用的内容外，本论文不含任何其他个人或集体已经发表或撰写过的作品或成果。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。申请学位论文与资料若有不实之处，本人承担一切相关责任。论文作者签名：日期：年月日学位论文使用授权说明本人完全了解杭州电子科技大学关于保留和使用学位论文的规定，即：研究生在校攻读学位期间论文工作的知识产权单位属杭州电子科技大学。本人保证毕业离校后，发表论文或使

3、用论文工作成果时署名单位仍然为杭州电子科技大学。学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。（保密论文在解密后遵守此规定）论文作者签名：日期：年月日指导教师签名：日期：年月日杭州电子科技大学硕士学位论文摘要模式匹配是入侵检测系统中的一项关键技术，其算法性能的好坏直接影响到入侵检测系统的性能。早期的模式匹配技术以精确匹配算法为主，如KMP，AC，BM等。随着互联网信息的迅速增长，攻击模式的多样化，这种基于字符串特征的模式规则定义越来越不

4、能满足日益增长的规则库需求，而正则表达式因其丰富和灵活的表达能力在模式匹配中得到了广泛应用。但是，传统的基于软件的正则表达式匹配引擎已经无法满足高速网络的要求，基于硬件的正则表达匹配引擎逐渐成为了国内外学者研究的重点。本文介绍了网络安全防护体系中的入侵检测技术及正则表达匹配算法在入侵检测系统中的应用，详细分析了正则表达式匹配的两种方法DFA和NFA及其硬件实现方法。在此基础上，本文选择了基于DFA的存储器查询的正则表达式匹配架构作为本文的研究内容。针对其存在的不足，从扩展系统一次处理的数据位宽出发，设计了一种基于起始状

5、态猜测的多路正则表达式匹配算法。该算法根据DFA状态转移的流程及RAM的读写速度，把输入字符流缓存成相同长度的多路，猜测除第一路之外的起始状态，先使各路并行匹配，并行匹配完后如果发现起始状态猜测错误，再通过验证匹配纠正其错误。该算法能够在不增加DFA个数的基础上，提高正则表达式的匹配速度。针对正则表达式匹配因FPGA片上存储资源不足需要频繁访问外部存储器的问题，本文2研究了BloomFilter在FPGA上的实现方法；设计一种把DFA和“失效状态”相结合的转移边优化方法。然后，在基于猜测的多路正则表达式匹配算法的基础上

6、，采用了转移边优化后的状态机，结合BloomFilter，设计了一个快速高效的正则表达式匹配引擎。该引擎根据状态深度和其转移边的数目，对状态转移信息进行分类存储和过滤，把匹配过程中经常需要查询和转移边较多的状态信息存放在FPGA内部RAM，把转移边较少的状态信息经过BloomFilter过滤，从而优化了状态信息存储所需的空间，减少了正则表达式匹配过程中访问外部存储器的次数，提高了匹配引擎的整体性能。本文在FPGA上实现了多路正则表达式匹配算法及其匹配引擎，搭建了测试平台，设计了详细的测试方案，对匹配算法及其匹配引擎的性

7、能进行了详细的分析和测试。实验结果表明，本文设计的匹配引擎能够提高匹配速度。关键词：入侵检测系统，正则表达式，多路并行，BloomFilter，FPGAI杭州电子科技大学硕士学位论文ABSTRACTPatternmatchingisakeytechnologyoftheinstrusiondetectionsystemandtheperformanceofitsalgorithmhasadirectinfluenceontheperformanceoftheintrusiondetectionsystem.Earlym

8、ainpatternmatchingtechnologiesareprecisematchingalgorithm,suchasKMP,AC,BM,etc.Withtherapidgrowthofinternetinformationandthediversityoftheattackmode,theruledefinitionb