基于正则表达式多模式匹配算法的研究

《基于正则表达式多模式匹配算法的研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、抗州电子科技大学硕士学位论文摘要随着计算机和Intemet技术的普及与发展，网络在人们日常生活中发挥越来越重要的作用，但是随之藤来的网络安全问题也隧益突战。入侵检测系统作为保障瓣终安全的重要防护措施得到了广泛应用，模式匹配作为入侵检测系统中的一顼关键技术，其性能优劣关系到整个入侵检测系统的效率，提高模式匹配的效率是提高这类系统检测能力的关键所在。本文简单介绍了入侵检测系统，分析了多模式匹配算法在其中的应用，并对AC、ACBM和WM算法徽了详细说明。但是，随着阚络技术的发爱穰规翼

2、j集复杂性的增加，这些传统翡字符串匹配弓l擎正逐渐被先进的正则表达式引擎所替代

3、。正则表达式匹配引擎一般是基于非确定的有限自动机(NondeterministicFiniteAutomaton,M’A)和确定的有限自动机(DeterministicFiniteAutomaton,D融)的。基予NFA的随配引擎匹配速度慢，但存储空阗相对较小。基于DFA的匹配引擎具有先天的速度优势，但是消耗的存储空间过大，并且随着规则集规模的增大，其对存储空间的需求更大。本文从减少构造的自动机的状态数出发，提出了一种有效的DFA合并算法(称为COMDFA算法)。在自动机构造过程中，将各个正则表达式分开处理，避免合并自动机时状态翻迁移边之闻的交互重叠情况的

4、嫩现，能够大大地减少自动枫的状态数。并且，通过引入空转移合并DFA，构造～个具有最小状态数的自动机，从丽减少存储空间需求。最后，引入压缩率CR(CompressedRate)的概念来描述合并算法对自动机状态数的压缩比率。实验结果表明算法对DFA状态数具有较好的压缩效果。针对NFA和DFA的匹配速度秘内存需求之间的矛盾，提出一种基于DFA制淞结构有限自动机的芷则表达式匹配算法(称为13lN算法)。算法采用DFA-NFA结构实现自动机的构造，分开处理弓

5、起DFA空闽爆炸的状态，以降低存储需求。由于网络中的数据只有很少一部分是恶意数据，而大部分是正常数据，DFA

6、部分在NFA部分之前的设计可以实现数据过滤功能，能够加快算法的匹配速度。同时，在自动机的构造过程中，针对DFA-NFA边秀上的关键状态，对同样的输入字符，设置相应迁移边的优先级。匹配过程采用基于优先级的查找算法，检查优先级来确定当前状态在读入字符下可以跳转到的下一状态，从1愆加快匹配过程。DN算法的测试结果表明其匹配效率和在状态方面的存储需求比传统算法有较大提离。关键诃：模式殛配，入侵检测系统，正则表达式，有限状态自动机杭州电子科技大学硕士学位论文ABSTRACTWiththepopularityanddevelopmentofcomputerandInt

7、eracttechnology,networkplaysa11increasinglyimportantrolein0111"dailylife，butthefollowingproblemsofnetworksecurityareoutstandingdaybydaytoo。Asanimportantprotectionmeasuretoguaranteenetworksecurity,intrusiondetectionsystemhasbeenlargelypopularizedandapplied．Asoneofthekeytechnologies

8、ofintrusiondetectionsystem，theimprovementoftheefficiencyofpatternmatchingalgorithmisessentialtoincreasethetestingabilityofthesystembecausethattheperformanceofpatternmatchingrelatestotheefficiencyofintrusiondetectionsystem．Inthispaper,theintrusiondetectionsystemisintroducedandtheap

9、plicationofpatternmatchingalgorithmsinthesystemisanalyzed．Meanwhile,ACalgorithm，AC—BMalgorithmandWMalgorithmarealsodiscussedindetail．However,alongw{1Illthedevelopmentofnetworktechnologyandtheincrementofcomplexityofrulesets，thetraditionalstringmatchingenginesalegraduallyreplacedbym

10、oreadvancedregularexpressionengin