深度包检测中的模式匹配算法研究

深度包检测中的模式匹配算法研究

作者：赵睿杜慧敏张丽果王亚刚

来源：《现代电子技术》2012年第03期

摘要：计算机网络技术飞速发展给人们生活带来便利的同时，也带来了严重的网络安全问题，由于各种网络攻击行为的不断出现-深度包检测逐渐成为网络安全的必然要求，作为影响深度包检测技术性能的模式匹配算法，成为研究的关键技术。对深度包检测中常见的一些模式匹配算法进行了分析和总结，并提出了进一步的研究方向。

关键词：网络安全；内容过滤；深度包检测；模式匹配算法

中图分类号：TN711-34；TP302.7文献标识码：A文章编号：1004-373X(2012)03-0100-04

随着计算机网络的高速发展，网络中的安全问题也日趋严重，包括非法访问、信息窃取、拒绝服务攻击、蠕虫或木马等病毒在内的各种网络攻击行为已经给网络安全造成了极大的威胁。内容安全作为网络安全的重要分支，内容过滤技术一直是网络安全中的研究重点，深度包检测技术(Deep Packet Inspection，EPI)是内容过滤技术的核心，对内容安全和内容过滤技术的深入研究具有重要意义。

深度包检测技术是一种具有代表性的数据流特征字节识别方法，通过深入读取IP数据包载荷的内容来对OSI七层协议中的应用层信息进行分析，从而得到整个应用程序的内容。由于深度包检测技术是根据预先定义好的特征规则，对读取的数据包内容进行匹配，所以深度包检测的关键技术是模式匹配，随着特征规则的不断增多和网络带宽的迅猛增长，对模式匹配算法的性能要求也越来越高。本文对一些深度包检测中常见的模式匹配算法进行了综述。

1模式匹配算法的分类

模式匹配算法按照其功能可以分为三类：精确匹配算法、近似匹配算法和正则表达式匹配算法。模式匹配算法的分类如图1所示。

精确匹配算法的功能是从输人的字符串序列中找出一个或一组与待匹配的目标模式串完全相同的子串。精确匹配算法主要应用在文本数据检索、资源定位和网络安全的入侵检测等领域。

根据目标模式串的数目多少，可以将模式串的精确匹配算法分为单模式匹配算法和多模式匹配算法。单模式匹配算法一次只能搜索一个目标字符串，而多模式匹配算法一次可以搜索多个目标字符串。

根据目前精确匹配算法检索数据序列的方式，将精确匹配算法主要分为三类模式：前缀模式、后缀模式和子串模式。前缀匹配模式主要是在到来的数据流中寻找与目标模式串相同的最长前缀，在匹配不成功的情况下通过某种策略计算窗口滑动的安全距离，以减少不必要的匹配工作量。后缀模式是从待匹配数据中寻找与目标模式串后缀相同的最长子串，它同样需要在匹配不成功的情况下根据某种策略计算匹配窗口的滑动距离，它与前缀匹配的不同还在于它的匹配过程是从右向左反向进行的。子串模式可以看作是前缀模式和后缀模式的结合，在匹配窗口内，它同后缀模式的匹配过程一样，从右向左反向进行，然而它又是在窗口中寻找同目标模式串前缀相同的最长子串并计算窗口的安全滑动距离。

近似匹配算法的功能是按照预先定义好的相似度量标准，在数据序列中找出一个或一组同特定的目标模式串不完全相同，但差异度在一定范围内的子串。近似匹配算法主要应用在图像、信息处理和计算生物学等领域。

正则表达式算法的功能是根据正则表达式的描述，在数据序列中找出所有的满足正则表达式描述的子串。正则表达式算法主要应用于简单的序列匹配无法描述的情形。

2模式匹配算法

根据网络内容过滤的要求，本文主要讨论精确匹配算法，字符串的精确匹配从实现方式上可以分为软件和硬件两个方面。在软件实现上，主要的算法包括Naive算法，Knuth，Morris 和Pratt三人设计的属于前缀模式的KMP(Knuth-Morris-Pratt)算法，Rebort S.Bo—yer和

J.Strother Moore设计的一种基于后缀的BM(Boyer-Moore)算法基于有限状态机FSM的

AC(Aho-Corasiek)算法，由Sun Wu和Udi Manber提出的WM算法和基于AC算法的基础上提出来的FS算法，以及基于压缩编码的思想的CE算法。这些基于软件的算法虽然易于实现并且灵活多变，但是由于其处理速度和吞吐量已经很难适应当前网络带宽的增长速度，所以现在一般都是采用硬件的形式实现快速匹配。在硬件实现方面，主要包括基于比较器CAM的模式匹配，基于有限状态机的模式匹配，基于TCAM的模式匹配，基于Bloom Filter的模式匹配和基于多核处理器思想的模式匹配技术。

2.1基于比较器CAM的模式匹配