基于fpga的可配置正则表达式匹配引擎的设计

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

1、万方数据分类号UDC学位论文基于FPGA的可配置正则表达式匹配引擎的设计作者姓名：江彬指导教师：白秋果教授东北大学信息科学与工程学院申请学位级别：硕士学科类别：工学学科专业名称：检测技术与自动化装置论文提交日期：2014年6月论文答辩日期：2014年6月学位授予日期：2014年7月答辩委员会主席：金伟教授评阅人：齐世清副教授王书涛教授东北大学2014年6月万方数据AThesisfortheDegreeofMasterinDetectionTechnologyandAutomationEquipmentsDesignofConfigurableMatchingEngineforReg

2、ularExpressionwithFPGAByJiangBinSupervisor：ProfessorBaiQiuguoNortheasternUniversityJune2014万方数据独创性声明本人声明，所呈交的学位论文是在导师的指导下完成的。论文中取得的研究成果除加以标注和致谢的地方外，不包含其他人己经发表或撰写过的研究成果，也不包括本人为获得其他学位而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均己在论文中作了明确的说明并表示谢=亡二思。学位论文作者签名：多于移日期：易／勿．9莎．坳学位论文版权使用授权书本学位论文作者和指导教师完全了解东北大学有关保留、使用学位

3、论文的规定：即学校有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人同意东北大学可以将学位论文的全部或部分内容编入有关数据库进行检索、交流。作者和导师同意网上交流的时间为作者获得学位后：半年口一年弋／一年半口两年口学位论文作者签名：户甲移签字日期：≯／纱咿莎．2纱导师签名：签字日期：少／纱矿石．却√，’¨T·’y‘71万方数据东北大学硕士学位论文摘要基于FPGA的可配置正则表达式匹配引擎的设计摘要正则表达式具有较强的灵活性、逻辑性及功能性，是一种字符串匹配模式，可以迅速地用较简单的方式来表述复杂的字符串。正则表达式多用于入侵检测系统及文本处理等。一般地

4、，都是采用软件方式来实现正则表达式的匹配。然而，随着网络带宽的大幅度提高、网络数据流量的剧增以及云计算技术等的快速发展，软件实现的方式成了正则表达式高速匹配的瓶颈。而硬件由于其并行化工作的特点，可以用于快速处理模式的匹配，因此成为研究人员设计、构造匹配引擎的新载体。FPGA由于其特殊结构及具有可重复配置等特性，现多用于高速多数据处理的场合。本文介绍了采用FPGA来实现正则表达式匹配的方法。论文首先对正则表达式构造自动机的几种经典算法进行了简述。在分析对比各自优缺点之后提出了一种新的NFA构造算法，该算法的空间复杂度理论上为D(月)，时间复杂度为D(刀：)。且构造生成的NFA的规模数

5、相对很小，其中状态数比正则表达式中含有的普通字符数玎要少，转换数约等于刀。有且只有一个终止状态。其次对在FPGA中实现匹配的过程进行了研究，提出了构建匹配子模块的设计，生成匹配子模块库。该设计可以大大节约后续设计过程中的时间成本，加快入侵检测系统中的特征模式的更新速度。对于一些特殊结构的正则表达式，论文给出了设计中的一些优化方案以节约实现中的硬件资源。最后利用论文中构建的子模块库，分别采用新算法S-NFA和经典的Thompson算法对正则表达式进行处理，生成对应的NFA。论文的第四章给出了将NFA进行逻辑化处理的方法，以适用于硬件化的处理。搭建Testbench测试平台，对各实例进

6、行测试并给出了仿真结果，从得到的NFA规模以及实际匹配延时两个方面对新的算法进行了评价。综上所述，本文在对正则表达式匹配技术的研究基础之上，提出了一种新的NFA构造算法及NFA的逻辑化处理方法，构建了匹配子模块库，通过仿真实验对该子模块库进行了验证，并比较了S-NFA算法和Thompson算法的性能。结果表明S-NFA算法在构造过程、生成的NFA的规模以及应用后的实际延时等方面要优于传统的Thompson算法，且适合于用FPGA来实现。关键词：正则表达式；匹配；自动机；S-NFA；FPGA万方数据东北大学硕士学位论文AbstractDesignofConfigtwableMatch

7、ingEngineforRegularAbstractRegularexpressionisakindofmodelforstringmatching，andcanquicklydescripecomplexstringsbyasimplepatternbecauseofitsflexity，logicalityandfunctionality．RegularexpressionusuallyisusedtoNetworkIntrusionDetectionSyste