（电路与系统专业论文）快速多模式匹配算法与硬件实现研究.pdf

杭州电子科技大学硕士学位论文杭州电子科技大学硕士学位论文 快速快速多模式多模式匹配匹配算法与硬件实现研究算法与硬件实现研究 研研 究究 生：生：赵海斌 指导教师：指导教师：李训根 副教授 2012 年 12 月 dissertation submitted to hangzhou dianzi university for the degree of master the research of fast multi-pattern matching algorithms and hardware implementation candidate: zhao haibin supervisor: associate professor li xungen december，2012 杭州电子科技大学杭州电子科技大学 学位论文原创性声明和使用授权说明学位论文原创性声明和使用授权说明 原创性声明原创性声明 本人郑重声明： 所呈交的学位论文，是本人在导师的指导下，独立进行研究工作所取 得的成果。除文中已经注明引用的内容外，本论文不含任何其他个人或集体已经发表或撰 写过的作品或成果。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标 明。申请学位论文与资料若有不实之处，本人承担一切相关责任。 论文作者签名： 日期： 年 月 日 学位论文使用授权说明学位论文使用授权说明 本人完全了解杭州电子科技大学关于保留和使用学位论文的规定，即：研究生在校攻 读学位期间论文工作的知识产权单位属杭州电子科技大学。本人保证毕业离校后，发表论 文或使用论文工作成果时署名单位仍然为杭州电子科技大学。学校有权保留送交论文的复 印件，允许查阅和借阅论文；学校可以公布论文的全部或部分内容，可以允许采用影印、 缩印或其它复制手段保存论文。 （保密论文在解密后遵守此规定） 论文作者签名： 日期： 年 月 日 指导教师签名： 日期： 年 月 日 杭州电子科技大学硕士学位论文 i 摘 要 随着网络的高速发展和普及，网络安全问题也日益突出。模式匹配是入侵检测系统的核 心技术，也是解决网络信息安全的核心方法。近年来入侵行为日益复杂和多样，单纯用软件 实现的模式匹配已经无法满足高速网络的要求，而 fpga、asic 和 tcam 等专用器件由于 处理速度快以及可并行等优点，近年来被广泛应用于模式匹配。 本文首先介绍了入侵检测系统的基本知识， 阐述了模式匹配在入侵检测中的作用和地位， 对模式匹配算法及其硬件实现的研究现状和发展趋势进行了分析总结。在此基础上，针对 k 步长自动机中部分状态的失效链过长、失效转移过程中状态跳转次数较多的问题，对 k 步长 自动机进行了改进，消除了各状态的失效函数，对任意的输入仅通过一次状态转移就能跳转 到确定的状态，从而减少了匹配过程中状态跳转的次数，提高了匹配效率。把改进的 k 步长 自动机和 bloom filter 原理相结合，设计了一种基于硬件的快速多模式匹配引擎，对 bloom fiter 及 hash 函数的 fpga 实现进行了重点研究及分析，通过选取最优的 hash 函数个数和映 射空间的大小，优化了 bloom filter 的性能。然后在 fpga 上对匹配引擎的各个模块进行设 计及实现，并采用了流水线技术对其进行优化。 针对基于 bloom filter 的模式匹配引擎存在假阳性误判的问题，本文随后在 fpga 上设 计并实现了一个基于 tcam 的模式匹配引擎。该引擎中的 tcam 模块用 fpga 内部的嵌入 式 ram 和逻辑资源实现，可以根据设计要求对位宽和深度进行灵活的扩展，克服了传统 tcam 芯片功耗大、成本高和配置不灵活的缺点。基于 tcam 的匹配引擎可以并行搜索、精 确匹配，克服了 bloom filter 中的假阳性误判，提高了匹配的效率。 本文最后搭建测试平台， 设计初始化方案和输入激励， 制定测试方案， 分别对基于 bloom filter 和基于 tcam 的两种匹配引擎的性能进行全面测试， 并从匹配速度和嵌入式 ram 利用 率两个方面对测试结果进行对比分析。实验结果表明：这两种匹配引擎都达到了千兆比特的 处理速度，能满足高速网络对匹配速度的要求。 关键词：模式匹配，有限状态自动机，布鲁姆过滤器，tcam，fpga 杭州电子科技大学硕士学位论文 ii abstract with the rapid development and popularization of the network, network security have become increasingly prominent. pattern matching is not only the underlying technology of the the intrusion detection system, but also the core method to solve the network information security. in recent years, the intrusion behaviors are increasingly complex and diverse, the software implementation of pattern matching has been unable to meet the requirements of high-speed network. while fpga, asic, tcam and other special devices has been widely applied in pattern matching because of the fast and parallel processing. in this paper, the basic knowledge of the intrusion detection system is introduced, the role and status of the pattern matching in intrusion detection is elaborated, the research status and development trend of pattern matching algorithms and their hardware implementation are analysed and summarized. on this basis, according to the long failure chain of some state in k-step automaton and too many state transitions during the process of failure transition, the k-step automaton is improved in this paper. after the improvement, all failure transitions are dispensed. for the arbitrary input, the state will be able to jump to a determined state only by one state transition. thus the number of state transitions during the matching process is reduced, which improved the matching efficiency. combined of the improved k-step automaton and the principle of bloom filter, a fast multiple pattern matching engine based on hardware is designed. the fpga implementation of bloom filter and the hash function is researched and analysed. the performance of bloom filter is optimized by selecting the optimal number of hash functions and the optimal size of mapping space. the function, structure and realization method of each module in the engine are detailed. finally pipeline technique is used for optimization. according to the false positive probability existed in bloom filter-based pattern matching engine, a tcam-based pattern matching engine is designed and implemented on fpga in this paper. the tcam module of the engine is implemented with the internal embedded ram and logic resources in fpga. the width and depth of the tcam module can be extended flexibly according to the design requirements, which overcoming the disadvantages of configuration inflexible, higher power consumption and cost of traditional tcam chip. the tcam-based pattern matching engine can perform parallel and exact matching, which overcoming the false positive probability of bloom filter and improving the efficiency of the matching. in this paper, a testing platform is built, the input excitation and initialization scheme are designed, and the test plan is developed. bloom filter-based and tcam-based matching engines 杭州电子科技大学硕士学位论文 iii are tested respectively and comprehensively. the test results of the two engines are compared and analyzed. the experimental results prove: the two matching engines can both achieve multi-gigabit throughput, which can make real-time and wire-speed detection for high-speed network. key words: pattern matching, finite state machine, bloom filter, tcam, fpga 杭州电子科技大学硕士学位论文 iv 目 录 摘 要 . i abstract . ii 第 1 章 绪论 . 1 1.1 研究背景及意义 . 1 1.1.1 研究背景 . 1 1.1.2 研究意义 . 2 1.2 研究现状及发展趋势 . 3 1.3 主要研究内容 . 5 1.4 论文结构安排 . 5 第 2 章 入侵检测与模式匹配算法 . 7 2.1 入侵检测 . 7 2.1.1 入侵检测概述 . 7 2.1.2 入侵检测的结构模型 . 8 2.1.3 入侵检测的分类 . 9 2.1.4 入侵检测的性能评估及影响因素 . 10 2.2 入侵检测中的模式匹配 . 11 2.3 基于软件的模式匹配算法 . 12 2.3.1 单模式匹配算法 . 12 2.3.2 多模式匹配算法 . 15 2.4 基于硬件的模式匹配算法 . 17 2.4.1 基于 bloom filter 的 fpga 实现 . 18 2.4.2 基于 cam/tcam 的实现 . 19 2.5 本章小结 . 20 第 3 章 基于 bloom filter 的多模式匹配算法及 fpga 实现 . 21 3.1 k 步长自动机及其改进 . 21 3.2 布鲁姆过滤器 . 24 3.2.1 布鲁姆过滤器的原理 . 24 3.2.2 布鲁姆过滤器的 fpga 实现 . 27 3.3 基于 bloom filter 的快速多模式匹配引擎 . 30 3.3.1 基于 bloom filter 的匹配引擎设计 . 31 3.3.2 数据拆分模块的设计 . 31 杭州电子科技大学硕士学位论文 v 3.3.3 bloom 过滤引擎的设计 . 32 3.3.4 仲裁模块的设计 . 34 3.3.5 地址映射模块 . 36 3.3.6 sdram 控制接口 . 37 3.3.7 匹配控制模块 . 39 3.4 系统优化 . 40 3.5 本章小结 . 41 第 4 章 基于 tcam 的多模式匹配算法及 fpga 实现 . 42 4.1 tcam 简介 . 42 4.2 tcam 的 fpga 实现 . 44 4.3 基于 tcam 的匹配引擎设计 . 46 4.4 sram 控制接口 . 50 4.5 系统优化 . 51 4.6 本章小结 . 52 第 5 章 测试与分析 . 53 5.1 测试平台 . 53 5.1.1 输入激励 . 53 5.1.2 系统初始化 . 54 5.1.3 性能评估 . 55 5.2 测试方案 . 55 5.3 系统测试与性能分析 . 56 5.3.1 基于 bloom filter 的匹配引擎性能测试 . 56 5.3.2 基于 tcam 的匹配引擎性能测试 . 57 5.3.3 性能分析 . 59 5.4 本章小结 . 60 第 6 章 总结与展望 . 61 6.1 论文总结 . 61 6.2 课题展望 . 61 致 谢 . 62 参考文献 . 63 附 录 . 67 杭州电子科技大学硕士学位论文 1 第 1 章 绪论 1.1 研究背景及意义 1.1.1 研究背景 计算机技术和网络技术的迅猛发展，不仅给国民经济的发展注入了强劲的动力，也深刻 的影响到人们学习、工作、生活的方方面面，现在人们已经离不开网络。但我们也要清醒的 认识到网络是把双刃剑，在我们通过网络获取知识、交流沟通、享受电子商务带来的便利的 同时，各种不良信息也充斥着网络，另外信息泄密、病毒泛滥以及黑客入侵不仅给个人、企 业造成了很大的损失，也对国家安全构成了很大的威胁。如何有效保障网络的安全，使我们 的计算机信息系统不受病毒侵害和黑客的攻击，已经成为网络信息化发展所要解决的关键问 题。同时网络安全已经提升为国家战略，成为了国防安全的重要部分，是影响国家长治久安 和持续发展的重大问题，世界各国都投入了巨大的人力、财力和物力进行网络信息安全方面 的研究。 为了解决网络安全问题，一大批专家学者和企业进行了深入的研究。在 1980 年，网络入 侵检测系统（network intrusion detection system，nids）产生了1，这是一种积极主动的安 全防护技术，能在网络系统遭受危害之前进行拦截和响应。入侵检测系统搜集计算机网络系 统中相关信息源的信息，并分析这些信息中有没有违反安全策略的行为和遭到入侵的迹象。 入侵检测在不影响网络性能的情况下能对网络信息进行检测，从而提供对内部攻击、外部攻 击和误操作的实时保护。 网络信息是以数据包的形式存在的，对数据包的检测有两种方式，一种是基于报头的数 据包过滤，该方式只对数据包的报头进行检测，检测的内容只包括协议类型、源地址、目的 地址、源端口号、目的端口号以及数据包的传输方向，这种检测方式的特点是高效、简单、 实用，但无法深入检测数据包的内部，对报头看似合法但内容非法的数据包就检测不出。另 一种就是深度数据包检测（deep packet inspection, dpi） ，它是 nids 的核心，采用模式匹配 算法，将每个数据包的内容（包括报头和数据载荷）与一组预定义的特征集合进行匹配，从 而发现违背安全策略的行为，该方式对每个出入 nids 的数据包进行深入检测，能更好的保 障网络安全。 网络攻击行为日益复杂和多样，特征库也在不断的更新，变得越来越庞大，因此传统的 基于软件的网络入侵检测系统受到处理器速度和软件串行特性的限制，已经达到理论性能的 瓶颈，难以突破。另外网络通信速度的不断提升，入侵检测系统及核心路由器等网络应用对 匹配速度的要求也越来越高，于是出现了多种基于硬件的高速多模式匹配算法，如 bloom filter 和 cam/tcam。bloom filter 过滤性能好，速度快，因其固有的结构特点可以很容易的 杭州电子科技大学硕士学位论文 2 用硬件实现；cam/tcam 作为一种新型的按内容读取的存储器，其可以在一个时钟周期内 给出查找结果的特性，使得它在各种高速多模式匹配应用中备受关注和追捧。 1.1.2 研究意义 模式匹配算法是计算机领域内的一个研究重点，并取得了一系列的研究成果，对解决计 算机相关领域的许多课题都产生了深远的影响。模式匹配算法的应用领域很广泛，它是文本 处理程序的主要组成部分，可以从文本串中快速的定位和查找所需要的字符串；生物信息学 领域的研究也要用到模式匹配，从基因序列中查找和定位功能基因组其实就是串的匹配。此 外模式匹配还应用于数据压缩、病毒库特征码的匹配、搜索引擎、语言翻译和拼写检查等。 当然，模式匹配算法最重要的应用还是在信息安全领域。模式匹配算法是深度数据包检 测中的关键技术，其性能好坏直接影响到入侵检测系统的匹配效率。近年来新一代的网络技 术迅速发展，网络的数据传输速率不断的加快；另一方面随着网络知识的普及和网络的进一 步开放，使得攻击行为和手法越来越高明和隐蔽。这就对模式匹配算法提出了更高的要求， 模式匹配算法不但要准确的检测出隐藏在数据包中的攻击行为和不良信息，还要尽可能的满 足网络传输的实时性和快速性。在高速网络环境下，如果模式匹配算法无法及时的处理大量 的实时网络数据包，则必然会造成网络的拥堵，严重者会造成整个网络的瘫痪，然后不得不 丢弃部分数据包，这就破坏了信息的完整性。解决这些问题的关键，是模式匹配算法，只有 高效快速的模式匹配算法才能在保证网络安全的前提下，提供尽可能大的网络吞吐率。所以 必须对模式匹配算法进行深入广泛的研究，不断改进算法的时间和空间效率，研究适用于网 络入侵检测的实时、高效、快速的模式匹配算法对计算机的信息安全和网络安全都有着重要 的意义。 高性能的模式匹配算法是网络入侵检测系统的核心，而且深度包检测也严重的依赖于模 式匹配算法的效率和性能。随着网络应用的复杂化，用于入侵检测的特征库的规模也越来越 大，snort 作为一种轻量级的入侵检测系统，其 2.2 版本的规则库中就包含了 2300 多条规则， 这就需要快速、高效的、能同时匹配多条规则的多模式匹配算法。理想情况下，我们希望多 模式匹配算法能达到线速的要求， 但基于软件的入侵检测系统受到 cpu 运算速度和软件串行 特点的限制，不可能达到每秒几百兆比特的处理速度，况且一个系统中的 cpu 不能只用来处 理模式匹配，还要进行其他的应用和操作。这迫使很多网络研究机构开始探索基于硬件的 模式匹配技术，一些用于网络入侵检测的基于硬件的模式匹配技术被开发出来，他们中的大 多数都是用 fpga 实现的。这些技术使用 fpga 内部的可重构和高度并行的逻辑资源，设计 了一个高速的搜索引擎，并取得的令人意想不到的效果。 硬件的可并行性和快速性越来越多的被开发和利用，并应用于多模式匹配，并取得了一 系列的成果，这也更激发了对这一领域的研究热情，越来越多的研究机构和个人开始重点研 究适合硬件实现的多模式匹配算法。用硬件实现模式匹配，其实质就是用空间换时间，即用 大量的硬件逻辑资源换取匹配速度的提高， 并在时间复杂度和占用的逻辑资源方面寻求平衡。 杭州电子科技大学硕士学位论文 3 但随着模式串的增多，基于硬件的多模式匹配算法受限于昂贵的硬件逻辑资源，不过随着微 电子技术的发展，硬件资源的集成度越来越高，单个芯片的可用逻辑资源也越来越多，相信 硬件资源的限制将很快被打破，基于硬件的多模式匹配算法会获得更大的发展空间。 不难想象，基于硬件的多模式匹配算法将会大大的提升网络入侵检测系统的性能，在网 络安全领域扮演越来越重要的角色，成为学界研究的重点。 本文研究的重点就是快速多模式匹配算法及 fpga 实现。 1.2 研究现状及发展趋势 虽然入侵检测系统在 1980 年就产生了， 但真正把模式匹配算法应用到入侵检测系统中却 是在 1995 年， 当时 sandeep kumar 在他的论文2中提出了用模式匹配算法来检测入侵的想法， 从此入侵检测系统中的模式匹配算法得到了快速的发展。模式匹配算法根据划分依据的不同 有很多分类方法，根据匹配的模式数目的不同，可以把模式匹配算法分为单模式匹配算法和 多模式匹配算法两种；根据匹配成功的定义方式可以划分为精确匹配和模糊匹配等。本文研 究的重点是多模式精确匹配。 多模式匹配算法是计算机领域中被广泛研究的经典算法之一，主要包括 aho-corasick 和 commentz-walter 算法，这两种算法可以分别看做是 kmp 和 boyer-moore 单模式匹配算法的 扩展。这两种算法仅仅适合用软件实现，并且算法的吞吐量有限。在通用 cpu 上，用软件实 现的多模式匹配算法的吞吐率只有 100kbps，已无法满足 gigabit 的网络速度。所以人们开始 研究速度更快的、基于硬件的多模式匹配算法。 在过去的十几年里，一些令人关注的算法和技术被开发出来，并应用于网络入侵检测中 的多模式匹配。采用的硬件技术包括 asic 和可编程逻辑 fpga，而 fpga 与 asic 相比，设 计更灵活，可重构，设计周期更短，成本更低，应用更广泛。目前模式匹配的硬件实现方法 主要有如下几种：(1)纯 fpga 实现，即把规则集中的每条规则都用 fpga 内部的逻辑资源来 实现；(2)利用 fpga 内部的嵌入式存储器；(3)fpga 和外部存储器相结合；(4) bloom filter； (5) cam/tcam。 一些基于 fpga 的技术利用片内的逻辑资源把模式串编译成并行的状态机或者组合逻 辑，这种方法虽然速度很快，但非常占用逻辑资源，现在很多规则库动辄都是几千条规则， 需要大容量的 fpga 芯片，但这种芯片的成本很高，所以纯粹基于 fpga 的解决方案受限于 规则库的规模，没有实用价值。 cho yh 介绍的方法3是用 fpga 中的嵌入式存储器来实现并行的模式检测模块(pdm)。 该方法把长的模式串分割成短的子串，并按顺序匹配这些子串，使得 pdm 能匹配任意长度 的模式串。 y.sugamara 介绍的方法4是想通过一次匹配处理多个字符的方法来加快 ahocorasick 有 限自动机的匹配速度，该方法使用后缀匹配，用 fpga 内部的 lookup table 实现，所以对模 式集的规模比较敏感。 杭州电子科技大学硕士学位论文 4 sarang dharmapurikar在2006年提出了在fpga上用bloom filter实现高速串匹配的硬件 结构5, 6。该结构基于 k 步长状态机，利用了 bloom filter 的快速过滤性能和较低的逻辑资源 占用率，在 fpga 内部实现了 bloom filter，作为一级过滤，滤掉了网络数据流中绝大部分的 不匹配信息，减少了访问外部存储器(存放的是状态转移信息)的次数，大大提高了系统的性 能，达到了 multi-gigabit 的处理速度。但这种结构也存在不足：由于 bloom filter 中的 hash 函数的碰撞，导致 bloom filter 存在假阳性误判；另外当查找到某条规则时，bloom filter 先 命中，然后还要从外部存储器中将状态机信息读进来，再进行精确匹配，而状态机信息往往 是多个字节的，所以完成一次精确匹配需要消耗好多个时钟周期，影响了该结构的匹配速度。 lockwood 和 song 采用了 extended bloom filter (ebf) 对此结构做了改进7，使 bloom filter 的数目减少，提高了匹配的效率。与 nfa/daf 相比8，基于 bloom filter 的硬件实现结构具 有 multi-gigabit 的处理速度，特征串的扩展也更加方便。但改进之后的结构仍然存在以下几 点不足：(1)需要许多的存储器资源；(2)模式串数目的增加使得性能降低；(3)对长串需要进行 处理， 划分成长度合适的短串； (4)模式串的长度分布不均匀， 导致对应不同长度的 bloom filter 分配到的模式串数目不均衡。 目前，高速模式匹配硬件实现的一个研究热点是 cam(content addressable memory)。 cam 是一种能够并行搜索的专用存储器件，每时钟周期完成一次搜索，可作为高效的模式匹 配单元。cam 包括普通 cam(binary cam)和 tcam(ternary cam)。普通 cam 中能存储两 种状态： 1或0，进行的是精确的匹配。而 tcam 的每个存储单元可以存储三种状态： 1、0或x(无关项)，可以对不同长度的模式串并行搜索。gokhale 描述了一种基 于 cam 的可编程的模式匹配系统9， 引入了串结尾标记， 该系统可以匹配不同长度的模式串。 但这类方法只适合处理少量的、长度较短的模式串。基于 tcam 的匹配引擎 ftse 虽然有较 好的输出性能10, 11，但在特征库的规模较大时，滑过的窗口会变小，处理性能也有明显的下 降。其它的一些基于 cam 的匹配方法，如 pre-decoded cam12等，都有各自的优缺点。虽然 cam/tcam 存在着功耗较大的问题，但作为一种每个时钟周期完成一次并行搜索的专用器 件，cam/tcam 是非常理想的快速模式匹配工具。 基于 cam 的可编程模式匹配系统的实现主要有两种方法：一种是利用商业化的、分立 的 cam 存储器，但分立的 cam 芯片存在以下缺点：(1)配置不够灵活；(2)做为一种片外存 储器，对他的频繁访问势必会造成系统整体性能的下降；(3)需要设计辅助的控制电路来实现 fsm 算法。另一种实现方法是采用可编程逻辑器件 fpga 来实现 cam 和 fsm，可以在一个 fpga 芯片上同时设计 cam 和 fsm 的控制逻辑，这样的话就能实现 cam 的灵活配置，而 且把 cam 做在 fpga 内部，可以大大提高访问速度，提高系统整体性能。不足之处是 cam 的容量受 fpga 芯片的资源限制，很难实现大规模的 cam。不过目前 fpga 技术发展很快， 片内