30000字硕士毕业论文多形式匹配算法的研究
论文类型：硕士毕业论文
论文字数：30000字
论点：算法,匹配,数据包
论文概述：
研究的背景随着网络的迅猛发展，网络安全问题口益突出，各种不良、反动以及涉及国家安全保密的信息，借助十互联网这种跨地域、跨国界、开放式的通讯方式进行传播。防火墙技术是网络安
论文正文：
第一章绪论 1.1研究的背景随着网络的迅猛发展，网络安全问题口益突出，各种不良、反动以及涉及国家安全保密的信息，借助十互联网这种跨地域、跨国界、开放式的通讯方式进行传播。防火墙技术是网络安全技术中应用最广泛的技术，成为当今网络安全的主流技术之一。数据包过滤系统是防火墙最核心的部分。Ifn模式匹配算法是数据包内容过滤的关键技术之一，其性能优劣关系着整个防火墙和入侵检测系统的效率。因此，寻求一种高效的模式匹配算法具有十分重要的意义。1.1.1基十报头的数据包过滤基十报头的数据包过滤是一个用软件或硬件设备对向网络上传或从网络下载的数据流进行有选择的控制过程。当一个数据包通过数据包过滤器时，检查其报头字段，决定是否允许它通过。 数据包过滤器能够基十如下的标准对数据包进行过滤:.该数据包所属的协议(TCP,UDP等等).源地址.目的地址.目的设备的端口号(请求类型).数据包的传输方向，英特网传给局域网或局域网传给英特网.数据库中既定数据包的签名1.1.2基十内容的数据包过滤基十报头的数据包过滤的简单、高效、实用的特点，使得其在防火墙和入侵检测系统中得到广泛应用。但是，基十报头的数据包过滤只是简单地对数据包的报头进行过滤，Ifn无法深入数据包内部探察，对各种报头合法但内容非法的情况无能为力。基十内容的数据包过滤系统能够对数据包进行关键词过滤和检测，能支持多个关键词逻辑过滤操作，另外，内容过滤系统甚至能对包括图片、音频在内的所有数据进行内容检查。因此，基十内容的数据包过滤能够更好地保障网络安全。由十计算机网络的飞速发展，网络带宽不断拓展，网络内的数据流量不断加大，这就要求防火墙能够在尽量短的时间内处理完大量待检数据流。作为内容过滤防火墙的核心部分，数据包过滤器的效率是提高防火墙速度的关键因素。Ifn模式匹配算法是数据包内容过滤的关键技术之一，其性能优劣关系着整个防火墙和入侵检测系统的效率。这也使得模式匹配逐渐成为网络安全技术的核心和I研究热点之一，在网络安全领域有着举足轻重的地位。 目前，模式匹配算法研究所面临的主要挑战是模式集规模的迅速增大。绝大多数经典的模式匹配算法无法直接有效地运用到大规模模式集条件下。ifub.随着网络带宽的不断增加，模式匹配算法往往会成为系统的瓶颈。所以，研究高性能的适用十大规模模式集的模式匹配算法是当务之急，具有重要的学术意义和广阔的应用前景。1.2模式匹配算法的发展与研究现状BFCBruceForce)算法【‘]是最早提出来的模式匹配算法，也是最简单的一个算法。该算法的最坏时间复杂度为。CM*N)o1970年，S.A.COOK从理论上证明了串匹配问题可以在OCm+n时间内解决，同一年，Morris和Pratt仿照COOK的证明构造了一个算法，随后，Knuth对这个算法进行了一些改进，在1976年，Knuth提出了第一个在线性时间内解决字符串的模式匹配算法，这个算法简称为KMP算法[f2l，它的时间复杂度为O(m+n)。1977年，Boyer和Moore提出了另一个与KMP算法截然不同的却同样拥有线性时间复杂度的算法(BM算法)。BM算法在实际的模式匹配中，跳过了很多无用的字符，这种跳跃式的比较方式，使BM算法获得了极高的效率，特别是在大字符集上进行字符串的模式匹配时。在实际的应用中，BM算法比KMP算法更有效率。多模式匹配是另一个研究热点。 Aho-Corasic算法(AC算法)f}l是第一个在O(N)上解决这个问题的算法。AC算法可以被石‘作是KMP算法的更一般化形式。此后，BM算法跳跃的思想也被应用到了多模式匹配上，1979年Comments-Walter提出了一种新的多模式匹配算法，称为CW算法[，这个算法将AC算法和BM算法的思想结合起来，获得了更好的执行效率。沿着AC算法这条路线，Crochemore等人将AC算法和DAWG结合，获得了一种新的算法，称为DAWG-MATCH}}}。实验结果表明，该算法比Comments-Walte:的算法更有效率。此外，人们还提出了其它一些多模式匹配算法。1994年，SunWu不IIManber提出了第一个基十过滤思想的多模式匹配算法[f}l。这个算法将过滤思想和BM思想结合起来，在实际的应用中获得了极其高的效率。实验表明，在SunSparcl0上，他们的算法可以十10秒内完成在15.8M的文本中搜索10000个模式的工作。在WM算法的基础上，SunWu和Manber实现了一个用十模糊匹配的工具agrep}g}和一个文本检索的工具glimpse}}}，在实际的应用中都获得了良好的效率。 参考文献[1]严蔚敏，吴伟民.数据结构C语言版)UM].北京:清华大学出版社，1997:79-80.Knuth，D.E.，J.H.Morris Jr，V.R.Pratt .Fast pattern matching in strings[J].SIAM J. Comput.1977, 6(1):323一350.[3]Boyer,R.S.，J.S.Moore. A fast string searching algorithm[J].Communication ofACM, 1977,20(10): 762一772.Aho,A.V.,M.J.Corasick.Efficient string matching:an aid to bibliographicsearch[J].Communications of ACM,1975,18(6):333一340.[5]B.Commentz一Walter. A string matching algorithm fast on the average[R].Technical Report 79.09.007, LB.M. Heidelberg Scientific Center, Germany,1979.M.Crochemore, A.Czumaj，L.Gasieniec, T.Lecroq, W.Plandowski, W.Rytter.Fasterpractical multi一pattern matching[J]. Inf. Process. Leu, 1999,71((3一4)):107一113.Wu Sun，Udi Manber. A Fast Algorithm for Multi一pattern Searching[R].Technical Report, The Computer Science Department, The University ofArizona, 1994.Wu Sun，Udi Manber.Agrep一一A Fast Approximate Pattern MatchinTool[C].Usenix Winter Technical Conference, 1992:153一162.Wu Sun，Udi Manber. GLIMPSE: A Tool to Search Through EntireFileSystem[C].Usenix Winter Technical Conference, 1994.Robert Muth，Udi Manber. Approximate multiple string search [J].In Proc.7th Combinatorial Pattern Matching(CPM\' 96), LNCS 1075, 1996: 75一86.Sun Kim, Yanggon Kim. A fast multiple string一pattern matching algorithm[J].Proceedings of the 17 AoM/IAoM International Comference on ComputerScience, May 1999.姚亚锋.基十内容过滤的防火墙的研究[D].安徽理工大学硕士毕业论文，2008.2.谢希一仁.计算机网络教程【M].北京:人民邮电出版社，2002, 3. Cheek Point Express reference[OL].http://www.eheekpoint.com,2003，10.黄智祥，叶震，孙志勇.防火墙技术及其体系结构研究[J].计算机与信息技术，1999，11.郭乐群.基十策略防火墙的设计与实现[[J].通信技术.2001.2(2):53-55.E.AI一Shaer，H. Hamed. Management and translation of filtering security 摘要 5-6 ABSTRACT 6 致谢 7-12 第一章 绪论 12-16 1.1 研究的背景 12-13 1.1.1 基于报头的数据包过滤 12 1.1.2 基于内容的数据包过滤 12-13 1.2 模式匹配算法的发展与研究现状 13-14 1.3 论文的主要内容 14 1.4 论文的章节安排 14-16 第二章 防火墙技术 16-24 2.1 防火墙的定义 16-17 2.2 防火墙的发展历程 17 2.3 防火墙技术分析 17-21 2.3.1 包过滤技术 18-19 2.3.2 应用代理技术 19-20 2.3.3 状态检测技术 20 2.3.4 自适应代理技术 20 2.3.5 内容过滤技术 20-21 2.4 防火墙的功能 21-22 2.5 防火墙的优点与不足 22-23 2.5.1 防火墙技术的优点 22 2.5.2 防火墙技术的不足 22-23 2.6 本章小结 23-24 第三章 模式匹配算法 24-35 3.1 模式匹配定义 24 3.2 单模式匹配算法 24-29 3.2.1 BF（Bruce Force）算法 24-25 3.2.2 KMP（Knuth Morris Pratt）算法 25 3.2.3 BM（Boyer-Moore）算法 25-28 3.2.4 BMH（Boyer-Moore-Horspool）算法 28-29 3.3 多模式匹配算法 29-33 3.3.1 AC（Aho-Corasick）算法 29-31 3.3.2 AC-BM（Aho-Corasick-Boyer-Moore）算法 31-33 3.4 影响模式匹配算法的因素 33-34 3.5 本章小结 34-35 第四章 改进的多模式匹配算法 35-45 4.1 算法设计思想 35 4.2 算法描述 35-38 4.3 算法分析 38-44 4.3.1 最大移动距离 38-42 4.3.2 比较次数 42-44 4.4 本章小结 44-45 第五章 模式匹配算法性能测试 45-50 5.1 测试目的 45 5.2 测试环境 45 5.3 测试数据 45 5.4 测试结果 45-48 5.4.1 时间测试 45-48 5.4.2 空间测试 48 5.5 本章小结 48-50 第六章 总结与展望 50-51 6.1 论文总结 50 6.2 工作展望 50-51 参考文献 51-54 攻读硕士学位期间发表的论文 54-55