（计算机系统结构专业论文）一种基于可重构计算的汉字模糊匹配算法与硬件实现.pdf

摘要 随着网络技术的发展和网络应用的普及，互联网已经成为人们获取信息、相互联系 的主要途径之一，它与人们的日常生活和工作也日益密切的联系起来，然而随之而来的 安全性也日趋突出。目前，互联网中垃圾邮件、非法、有害信息的泛滥，不仅侵蚀了网 络资源，而且扰乱了人们正常的生活和工作，给社会和企业都带来了不小的危害和损失， 因此研究发展安全有效的信息过滤技术，以满足对日益增长的网络信息流量的检测过滤 需求，具有非常重要的现实意义。 目前，依赖于匹配算法的改进和计算机性能的提高，通过软件系统对网络信息数据 进行匹配过滤已经可以满足一定的监控需求，但随着网络数据量的迅猛增长，这种方法 仍旧难以满足高流量的核心网络中对实时信息监控的需要。与之相比，一些a s i c 产品 和基于f p g a 结构的解决方案尽管能够提供更高的数据处理能力，但成本相对较高，系 统灵活性也相对欠缺。 针对这一需求，特别是网络信息中，中文信息过滤的需要，我们设计并实现了一个 基于可重构计算的硬件汉字模糊匹配系统。系统通过并行结构提高数据处理能力，利用 f p g a 的可重构特性保证了系统灵活性和可扩展性。在检测技术方面，我们采用基于动 态规划的s m i t h - w a t e r m a n 算法，并以此为基础针对网络信息中汉字匹配需求的特点进行 了改进，在f p g a 芯片中实现了多模式的模糊匹配，实现了对各种模式变体的识别，从 而缩减了模式库的规模，有效提高了系统匹配能力，可以得到g b p s 量级的数据处理能 力。 关键词：可重构计算；模糊匹配：多模式匹配；f p g a a ni m p l e m e n t a t i o no f c h i n e s ec h a r a c t e r a p p r o x i m a t em a t c h i n g b a s e do ur e - c o n f i g u r a b l ec o m p u t i n g z h a n gn a n ( c o m p u t e r a r c h i t e c t u r e ) d i r e c t e db yz h a n gp e i h e n g w i t ht h ed e v e l o p m e n ta n da d o p t i o no fn e t w o r kt e c h n o l o g y , i n t e r n e th a sb e c o m eo n eo f t h em o s ti m p o r t a n tw a y sp e o p l eg e ta c c e s st oi n f o r m a t i o n , a sw e l la sc o m m u n i c a t i o n i n t e m e t i sm o r ea n dm o r ec l o s e l yr e l a t e dt oo u rd a i l yl i f ea n dw o r k , b u ta tt h es a m et i m e ，t h e r ea l s o a r i s em a n yp r o b l e m so fs e c u r i t y s p r e a d i n go v e rt h en e t w o r k , j u n km a i l sa n di l l e g a l i n f o r m a t i o nn o to n l yo c c u p yn e t w o r kr e s o u r c e s ，b u ta l s od i s t u r bp e o p l e sn o r m a ll i f ea n dd o d a m a g et ot h es o c i e t y t h e r e f o r e ，i th a sg r e a ts i g n i f i c a n c et or e s e a r c ha n dd e v e l o pi n f o r m a t i o n f i l t e r i n gt e c h n o l o g i e st h a t a r eb o t hs e c u r ea n de f f e c t i v e ，s oa st o s a t i s f yt h em o n i t o r i n g r e q u i r e m e n t so nt h ei n c r e a s i n gn e t w o r ki n f o r m a t i o nf l o w d u et ot h ei m p r o v e m e n to fm a t c h i n ga l g o r i t h ma n dc o m p u t e rp e r f o r m a n c e ，i ti sp r e s e n t l y p o s s i b l et om o n i t o rt h en e t w o r kd a t av i as o f t w a r es y s t e m sa tas i g n i f i c a n ts p e e d b u tw i t i lt h e c u r r e n ts h a r pi n c r e a s eo fn e t w o r kd a t a , t h a ts o l u t i o ns t i l ln e e d st ot a k ee f f o r t st os a t i s f yt h e n e e d so fs i m u l t a n e o u sm o n i t o r i n gi nac e n t r a ln e t w o r kw i t h 1 1 i g hd a t af l o w a l t h o u g ht h e a s i cp r o d u c t sa n ds o l u t i o n sb a s e do nf p g as t r u c t u r e ss h o wc o m p a r a t i v e l yb e t t e rd a t a p r o c e s s i n ga b i l i t y , m e ya l s oh a v ed e f e c t ss u c ha st h eh i 曲c o s ta n dt h ei n f l e x i b i l i t y t os o l v et h ep r o b l e m , w eh a v es p e c i a l l yd e s i g n e da n dr e a l i z e dah a r d w a r em o d e lb a s e do n r e c o n f i g u r a b l ec o m p u t i n g ，w h i c hi m p r o v e sd a t ap r o c e s s i n ga b i l i t yt h r o u g ht h ep a r a l l e l h a r d w a r ea n da tt h es a m et i m eg u a r a n t e e st h ef l e x i b i l i t ya n ds c a l a b i l i t yo f t h es y s t e mt h r o u g h t h er e c o n f i g u r a b i l i t yo ff p g a o ft h ed e t e c t i n gt e c h n o l o g y , w eh a v ea d o p t e dt h ed y n a m i c p r o g r a m m i n ga l g o r i t h mi nc i r c u i t st or e a l i z et h ea p p r o x i m a t em a t c h i n go fp a r e m s ，s ot h a tt h e p a t t e mv a r i a b l e sc o u l db ed e t e c t e da n di d e n t i f i e d ，t h ep a a e ms t o r a g er e d u c e d ，a n dt h ed e t e c t i n g a b i l i t ye f f e c t i v e l yi n c r e a s e d k e y w o r d s ：r e c o n f i g u r a b l ec o m p u t i n g ，a p p r o x i m a t em a t c h i n g ， m u l t i p a a e mm a t c h i n g ，f p g a i i i 图目录 图2 1 从前向后匹配模式前缀的精确匹配算法 图2 2 从后向前匹配模式前缀的精确匹配算法 图2 3a c - b m 算法建立模式树 图2 4 基于自动机的模糊匹配算法 9 1 0 图2 5 基于过滤思想的模糊匹配 图2 6 基于过滤思想的模糊匹配1 l 图2 7 f p g a 构造成c a m 形式 图2 8c a m 单元内部使用b r u t ef o r c e 方式 图2 9 b r u t e f o r c e 流水复用 图2 1 0b r u t ef o r c e 编码复用 图2 ，1l 前缀后缀分开匹配。 图2 1 2 基于k m p 算法的多模式精确匹配。 图2 1 3d f a 逻辑实现。 图2 1 4d f a r o m 实现 图2 1 6b l o o mf i l t e r 基本结构 图3 1 单个计算节点的f c i - x 加速卡结构 图3 2 系统整体框图 图3 3 匹配单元的组织结构 图3 4p e 阵列结构框图 图3 5 矩阵计算结果比较 1 3 1 3 1 3 1 3 l ! ； 11 ； 。2 0 2 0 图3 6 矩阵计算部分的流水结构。 图3 7 矩阵计算每一级的内部逻辑结构。 图3 8 模式匹配单元结构框图 图3 9 规则匹配单元结构框图 图4 1 输入控制模块结构框图 图4 2 输入控制模块的f i f o 结构 图4 3 序列调整模块框图 图4 4 序列调整状态机的时序图 2 7 2 7 图4 5 查找表内部结构2 9 图4 6 模式匹配部分的流水线结构 图4 7 单个处理单元内部结构 图4 8 结果回收流水线结构 3 0 3 0 3 l 一种基于可重构计算的汉字模糊匹配算法与硬件实现：图目录 图4 9 规则匹配部分的流水线结构 图4 1 1 0 规则匹配单元内部结构 3 2 图4 11 编码区问划分3 4 图5 1 样本库规则库示意图 图5 2 在不同敏感度下正确识别出的文章数。 图5 3 在不同敏感度下错误识别出的文章数 图5 4 各规则在不同敏感度下被误判次数 图5 6 模糊匹配的扩展 x 3 9 4 l 表2 1 动态规划矩阵 表目录 表2 2 基于f p g a 多模式精确匹配的主流方法性能表 表31 一最小距离矩阵计算 表3 2 一基于r a m 的精确匹配状态机 表3 3 一资源消耗 表4 1 一查找表第一级 。1 6 2 2 2 4 2 6 表4 2 一查找表第二级 表4 3 一替换对矩阵的影响 表4 4 一删除对矩阵的影响 表4 5 一插入对矩阵的影响 表4 6 一同音字编码 2 9 3 3 表4 7 一查找表中编码区间的处理 表5 1 一规则库 。3 3 3 4 3 4 3 7 表5 2 一不同敏感度下不同长度模式串的阈值设置3 7 表5 3 一测试结果 表5 4 一精确匹配条件下两种算法对比攫8 试结果。 表5 5 一s m i t h - w 征r m n 算法的系统执行时f 司对比 表5 6 一识别率测试结果 表5 7 一误判率测试结果 x i 4 3 4 5 声明 我声明本论文是我本人在导师指导下进行的研究工作及取得的研究成 果。尽我所知，除了文中特别加以标注和致谢的地方外，本论文中不包含 其他人已经发表或撰写过的研究成果。与我一同工作的同志对本研究所做 的任何贡献均已在论文中作了明确的说明并表示了谢意。 作者签名：易妖豫豹 日期：加罗多 论文版权使用授权书 本人授权中国科学院计算技术研究所可以保留并向国家有关部门或机 构送交本论文的复印件和电子文档，允许本论文被查阅和借阅，可以将本 论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编本论文。 ( 保密论文在解密后适用本授权书。) 作者签名：孤刁钢导师签名： 擞甲五雪吼洲“ 1 1 应用背景 第一章引言 在当今信息时代，我们的生活中充斥着各种各样的信息，特别是互联网技术的高速 发展，为信息的发布与传递提供了一个高效的平台。资料查询、资源共享、协同计算、 网上办公、远程医疗、网上购物、电子商务、电子邮件、虚拟社区等等，已经渗透到人 们日常生活工作的方方面面。而与此同时网络技术的发展也为垃圾信息的传播创造了有 利条件。各种色情、暴力、赌博、邪教、迷信、诽谤、欺诈信息和内容充斥网络，给家 庭、社会和企业造成了经济和财产损失，并引发了诸多的社会问题。据统计，2 0 0 3 年国 内网民每天接收的垃圾邮件达到数千万封，已经超过了正常电子邮件的数量；全球垃圾 邮件占电子邮件总数的比例已由2 0 0 1 年的7 猛升至目前的5 1 ，并且仍在以每5 个月 翻一番的速度高速增长：欧盟的一项调查表明，垃圾邮件每年为欧洲造成超过6 0 亿欧元 的经济损失；在网络上流动的非教育信息中7 0 涉及到暴力与此同时垃圾信息还 危害到了互联网本身的发展，垃圾信息占用了大量的传输、存储和运算资源，特别是对 核心骨干网络，不但造成网络资源的浪费，而且引发了巨大的存储需求，这对信息安全 是一个重大挑战。为此，人们开始研究采用技术手段来解决这一问题。 过滤技术是目前网络信息检测中应用的主要手段。信息过滤技术是通过用户提供的 一个过滤需求，利用计算机从动态变化的信息流中自动检索出满足用户个性化需求的信 息，它既可以用于屏蔽有害信息，也可以用于收集有益信息，可以帮助人们更可靠、更 有效的获取对自己有价值的信息。传统的信息匹配与检索主要包括：文本扫描、签名文 件、倒排文件、向量模型和聚类等等。针对互联网动态实时、数据量大、变化频繁的特 点，对网络信息的过滤通常利用模式匹配技术进行文本扫描，这样做不需要在维护索引 表上花费大量的时空开销，也更适用于频繁产生和更新的动态数据环境，在原文的基础 上就可以完成搜索任务。 1 2 系统瓶颈与解决方案 信息过滤是一个庞大复杂的系统，涉及到协议还原、数据分析、建立模型，模式匹 配、学习更新和决策等多个部分。其中建立模型、学习更新等部分都可以采用离线方式 进行而在在线处理部分中，又以模式匹配部分的计算量最大，耗时最长，占用系统资 源最多，因而在很大程度上限制了系统检测速度的提升。 为了适应数据流量的迅猛增长、数据信息实时变化的需求，人们通过改进匹配算法、 提高并行度等方式提高匹配性能，以期实现线性匹配，从而提高整个系统的检测性能。 中国科学院硕士学位论文一种基于可重构计算的汉字模糊匹配算法与硬件实现 目前，针对网络信息的过滤大多通过文本扫描，采用基于关键字精确匹配的方式。依赖 于匹配算法的改进和计算机性能的提升，通过软件对网络信息的监控已经可以达到 1 0 0 m b p s 量级的匹配速度，但随着网络数据量的迅猛增长，这种方法仍旧难以满足高流 量的核心网络中实时信息监控的需要。为了适应这一需求，目前也已经提出了一些基于 a s i c 和f p g a 的解决方案，与软件系统相比，硬件系统可以提供更高的并行性，更好 的分担系统负担，得到更高的数据处理能力，通常可以在g b p s 量级。然而基于硬件实 现的系统，开发周期长、成本高，更重要的是灵活性差，这大大限制了硬件系统的应用。 为此我们采用了基于可重构计算技术的硬件解决方案。目前我们已经完成了p c i 硬件加 速卡的设计【4 3 1 1 4 4 1 ，采用“通用系统+ 标准接口+ 专用部件”的结构，核心部件是现场可 编程门阵列( f i e l dp r o g r a m m a b l eg a t e a r r a y ，f p g a ) 芯片，通过重构内部逻辑可以实现 不同的加速算法，适应不同的应用需求。本文中我们将利用现有的硬件加速卡，将模式 匹配算法重构到硬件逻辑中，从而在信息过滤系统中，实现对最主要的模式匹配算法的 加速，提高处理能力。 同时在实际应用中，各种有害信息为了绕过检测系统的监控，通常会利用各种变体 进行伪装。而为了适应这种变化，需要在模式库中添加各种变体的信息，这使得精确匹 配算法中的模式库急剧膨胀，无形中增加了系统负担，而传统的信息过滤系统对此通常 无能为力。因此在信息过滤系统中对模糊匹配的需求也越来越多，但算法复杂，性能较 差。对于模糊匹配算法我们已经具有一定的研究基础，在d n a 和蛋白质序列检测中， 利用硬件加速卡实现了对模糊匹配算法的加速。因此针对网络信息过滤的应用，我们同 样考虑使用模糊匹配算法。与生物信息处理不同，网络信息过滤中的待测序列是实时变 化更新的，而目标序列( 即模式串) 则相对较短，因此可以采用并行方式同时匹配多个 模式，从而实现多模式的线性匹配。 1 3 本文的贡献 本文的研究旨在尝试一种基于可重构计算技术的硬件实现方法，并特别针对汉字信 息的特点，寻求一种可实现模糊匹配的解决方案，满足高速骨干网络中不断增长的信息 过滤需求。主要包括以下几个方面： 1 基于可重构计算技术的硬件解决方案。我们利用专用硬件对模式匹配算法进行 加速，以空间换时间，采用“通用系统+ 标准接口+ 专用部件”的结构以促进 整个系统性的提升。我们设计了p c i 加速卡，通过p c i - x 接口与系统总线相连 接，以1 0 0 m 频率计算，可以得到g b p s 量级的数据带宽；卡上集成f p g a 实现 算法加速，通过专用处理单元和并行结构来提高多模式匹配的速度；同时利用 f p g a 的可重构特性，保证模式库的及时更新和系统的灵活性，可以根据不同的 应用环境和需要，实现不同的加速算法。 2 满足网络信息过滤中规则库实时更新的需要。网络数据动态变化，检测系统的 2 第一章引言 模式库也需要随时进行更新，以适应这种需求。受限于现有的编译技术和器件 资源，f p g a 的重构过程往往比较复杂，而布局布线的改变还可能会导致系统工 作频率的变化，进而影响系统性能。为了能够避免重构过程对硬件结构产生太 大的影响，降低重构过程的复杂度，我们对匹配电路进行了改进，将算法的实 现与模式信息的存储分隔开，以保证重构过程中硬件结构的相对稳定，从而在 保持灵活性的同时保证系统性能不受影响。 3 满足对各种模式变体的模糊匹配需求。随着检测技术的发展，各种反检测的手 段也应运而生，为了能够检测出有害信息的各种变体，现有的检测系统更多的 是采用扩展模式库的方法，将各种变体囊括进来，这在一定程度上增加了系统 负担。为了避免模式库的无限扩张，更重要的是节约硬件资源，我们在系统中 尝试采用模糊匹配算法进行匹配。由于模糊匹配算法需要大量的数据计算，特 别是多模式匹配的情况，因而在以往用软件实现的信息检测系统中出现得比较 少，而对于硬件系统来说，引入了专用的计算单元，同时并行匹配多个模式， 可以使匹配性能大幅提升。 4 针对中文信息过滤需求。现有基于硬件的信息过滤系统大多是应用于入侵检测， 所处理的数据也以a s a i 字符为主，字符集相对较小。而对中文信息的检测则 要复杂得多。首先中文属大字符集，每一个汉字对应1 6 - , - 3 2 位编码，需要消耗 更多的比较逻辑或r a m 资源来实现；其次英文单词有明显的分词标记，单词往 往可以通过切分前缀和后缀的方式将多模式合并。而中文词组通常比较短，每 一个字都包含独特的信息，很难再进一步的切分。同时汉字比字母具有更高的 信息密度，绝大多数汉字可以独立构成语素，因此汉字的删除、插入、替代、 交换等错误，可能引入或丢失部分信息，对语义产生比较大的影响。而英文字 母插入或删除的影响则会小得多。为此我们在匹配过程中设计了符合汉字特点 的匹配电路。模式匹配部分采用1 6 位数据总线宽度，并在匹配过程中通过重编 码来降低位宽。在我们的系统中，模糊性主要考虑符号插入、汉字拆分和同音 字、各种变体字、拼音替换的情况。 除此之外，本文还设计了一个规则库，用于对系统性能进行测试，同时收集了超过 1 5 g b 的网页作为测试样本，比较了精确匹配算法和模糊匹配算法对文本信息的检测效 果。测试结果表明，模糊匹配算法能够有效地收敛模式库的规模，能够得到满意的检测 效果，与软件实现的系统相比，能够得到更高处理能力。 1 4 论文的组织 本论文针对网络信息过滤的需求，在第一章中介绍了课题背景与现有系统的主要技 术瓶颈，以及本文研究的重点和方向；并在第二章中，介绍了模式匹配技术的发展和现 状，阐述了模式匹配的主要算法，列举了一些基于f p g a 的模式匹配系统，和硬件实现 中国科学院硕士学位论文一种基了：可重构计算的汉字模糊匹配算法与硬件实现 的主要方法，并以此为基础展开我们的设计思路和方案。 在第三章介绍我们的算法设计；第四章详细介绍系统的硬件实现，以及我们对模糊 匹配的考虑，和针对模糊匹配所做的扩展。 在第五章，我们对系统进行了性能测试，其中包括对检测结果正确性的分析和系统 匹配速度的分析。 最后，对整个论文进行了总结，并提出了下一步的研究方向。 第二章模式匹配算法及硬件实现 信息过滤系统中最核心部分是模式匹配，针对网络信息的过滤大多采用基于关键词 的精确匹配方式，对数据包中的有效文本部分进行实时扫描。随着计算机技术的发展， 目前基于软件实现的精确匹配系统可以达到1 0 0 m b p s 的匹配能力，但仍旧难以满足高流 量的核心网络中实时信息监控的需要。针对这一需求，一些a s i c 产品和基于f p g a 结 构的硬件解决方案也相继被提出，其中比较成熟的商业产品，如n e t s c r e e n 、s o u r c e f k e 和c i s c o 的防火墙都可以完成多模式匹配，满足网络数据实时监测的需要。与软件实现 相比，硬件处理方法可以更好的分担c p u 的负担，得到更高的并行性，和更高的数据吞 吐量，从而大大提高匹配性能。在这一章中我们将介绍主流的精确匹配和模糊匹配算法， 以及一些硬件实现的主要思想和各种方法的特点，为我们的系统设计提供有价值的参考。 2 1 精确匹配算法 模式匹配是最早出现的计算机应用领域之一，随着技术的发展，很多加速算法也被 相继提出。目前，模式匹配技术被广泛应用于生物计算、信号处理、信息检索、病毒和 入侵监测、模式识别、以及数据压缩等领域。针对网络信息过滤，精确匹配是最常使用 的一种方式，为此我们将在本节中将重点介绍现有的主要精确匹配方法。 2 1 1 单模式精确匹配算法 单模式匹配是指通过文本扫描的方式，在字符集芝上，给定一个长度为n 的文本字 符串t 1 n 】，以及一个长度为m 的模式字符串p 1 m 】。如果对于l $ 如，存在t s 一1 s + 叫 = p 1 m 1 ，则模式p 在文本t 的位置s 处出现，即模式串与文本串匹配。 b r u t e - f o r c e 是最早、最简单的实现模式匹配的算法，需要将待测文本a - i t n 1 与模式 串p 1 m 1 中的字符逐个进行比较，得出匹配结果。这种方式对于小文本集来说是可以接 受的，但对于大规模的文本库和比较长的模式，匹配效率很低，待测文本每移动一位， 整个模式串都需要重新匹配一次，其最坏情况的时间复杂度为o ( m n ) 。为了得到更低 的时间复杂度，取得更快的匹配效果，人们在此基础上对算法进行了改进，试图使每一 次比较中所获取的信息，能够更有效地发挥出来，从而减少比较次数，加快文本扫描的 速度。基于这种考虑，后来的单模式精确匹配算法大体可以分为以下几大类【4 l 】： 首先是采用从前向后匹配模式前缀的方式。最典型的是k m p 算法，时间复杂度为 o ( m + n ) 。这也是第一个在线性时间内解决字符串模式匹配的算法。算法将待测文本 顺序通过检测窗口，并在窗口内从前向后逐个匹配每一个字符，通过这样的匹配可 以使我们对模式串的特征有进一步的了解。当匹配失败时，我们可以利用这些积累 中国科学院硕士学位论文一种基于可重构计算的汉字模糊匹配算法与硬件实现 的信息，知道当前字符不可能出现的位置。如图2 1 中，当a 和d 匹配失败时，我们 可以通过前面的匹配信息知道a 只能出现在模式串的第一个位置，因此将整个检测 窗口后移3 个位置。算法通过状态机记录已匹配的前缀内容，并根据状态机的跳转 确定匹配结果。类似的思想还有s h i f to r 算法 2 1 等。这类算法的最差时间复杂度都达 到了理论最优结果o ( n ) ，但是由于只能逐个字符进行扫描，它们的平均时间复杂度 往往都较差。 l2345678 t e s ts t r i n g abcadefg p a t t e r ns t r i n g abcd b r u t e - f o r c e abcd k m p + abcd 图2 1 从前向后匹配模式前缀的精确匹配算法 其次是采用从后往前匹配模式后缀的方式。最典型的是b m 算法p l ，其基本思想也 是挖掘每次比较的内在信息，只是在检测窗口内从后往前扫描文本，并根据匹配模 式的后缀内容来决定窗口的移动。与k m p 算法相同，图1 2 中b m 算法的移动也是 3 个位置，但这种方法更好的利用了人们从左到右的输入习惯，由于所匹配的后缀 在当前窗口后部，使得算法实际上对正文中的很多字符都不必进行扫描，因此能在 很大程度上减少比较次数，在实际应用中可以得到比k m p 算法更快的扫描速度。这 类算法的最差时问复杂度为o ( m n ) ，但平均时间复杂度达到亚线性。基于b m 算法 的思想后来又提出了多种改进的版本和变体，其应用也最为广泛，如b m h 算法【4 j 适用单模式匹配；s b m h 算法嘲适用于小规模的多模式匹配；a c b m 算法 6 1 用于多 模式精确匹配等口】。 l2345678 0 一旦c a d ef g abcd - abcd - abcd 图2 2 从后向前匹配模式后缀的精确匹配算法 另外，为了将当前扫描窗口中更多的有用信息挖掘出来，还有一些算法将上述两种 思想相结合，采用从后向前匹配模式前缀的方式。在从后向前进行模式扫描时，反 向使用模式逆串的后缀自动机( d a w g ) 1 7 】来匹配模式的前缀，增大窗口移动的距离， 从而获得更好的平均时间复杂度。如b d m 8 1 ，r f 算法【9 l 等。 2 1 2 多模式精确匹配算法 多模式匹配是指有k 个模式p 【l 】p k 】和一个文本t ，寻找k 个模式中的任何个 6 兰枞 第二章模式匹配算法及硬件实现 模式在t 中是否出现以及出现的位置。采用精确匹配算法需要在其基本的时间复杂度上 在乘以k ，这样的时间开销对于一个大模式集的扫描来说，显然是巨大的。因此，为了 能够满足实际应用中多模式匹配的需要，人们又开发出很多多模式匹配算法，力图减少 比较次数。这些算法的基本思想大多基于单模式匹配，更多的则是对模式库进行改建， 通过h a s h 表或者模式树的方式构造模式库( 如图2 3 【1 0 】) ，并利用自动机对其进行深度 扫描，从而简化匹配过程，减少比较次数。这样处理在空间上更加节省资源，时间上也 不需要对所有的模式子串进行独立的扫描，因此可以得到更高的效率。目前主要的算法 有基于a c 算法思想的a c b m 算法 6 1 、以及基于w m 算法【1 2 1 思想的m w m 算法【1 3 】 等。 c f d o c s c f m l s y n t a x c h e c k c f c f d o c s e x a m p l e a p l 3 c f d o c s e x a m p l e a p p e m a i l a p p l l c a b o n c f m c f d o c s e x a m p l e a p p e m a t l g e t f f i e c f m ，c f d o c s ，e x a m p i e a p p ，p u b l i s h ，a d m i n ，a p p e v a l u a t e c f m ，c f d o c s e x a m p l e s c v b e a n s b e a n l n f o c f m e x 慨d e a 刚c a t 叭f m snippe,谚figettemjpedmfreacltory刚cfmcfdocsexamplesmamframeset c f m d “”。 ，c t c f 批d o c 。s e x a m p i e ，“m 鲥烈8 “。佣蒯。，挪l 8 忙淼嚣n t c f m ，c f d o c s ，e x p e v a ， ，c f d o c s ra m p l ，1 n h h c h ，d m m f j ，a a m e n t ，c f d 。s ，e x p e v a s p i a y o p e n e 删e c f m e ： s f 。p p h c a t l o n c f m 7 c f d o c s e x p e v a e x p r c a b c 佃 k v a i c y b e a n s b e a n l n c f d o c s s n l p p e t s m a l n f r a m e s e tc f m 缸咖 i 、 1 ，c t a o c s ，s n - 。e t s ，e v 剖u a t e c t m 生，。黜碧黧赫2 加 7 d d o c 8 7 8 r p p e t s ，f l b e x 峙t s 。c 佣 e x p r a 晶l c c f m 图2 3a c - b m 算法建立模式树 目前，依赖于计算机性能的不断提升和算法的改进，软件实现的多模式匹配系统通 常在l o o m b p s 量级。在不同的应用中，模式库和待测文本具有不同的特点，匹配性能也 有很大差异。由于软件实现无法并行扫描整个规则树，匹配时间取决于规则库的扫描深 度。对深层次的扫描越多，整体性能下降越多，数据带宽也受到很大限制。因此软件实 现的多模式匹配系统通常存在最坏情况，在高速网络中这一点也常被有害信息所利用， 导致检测系统瘫痪。 s n o r t 是一个开放源码的入侵检测系统，它定位于实现轻量级的入侵检测，可以完 成实时流龟分析和对网络上的i p 包登录进行测试等功能，能完成协议分析，内容查找 匹配，能用来探测多种攻击和嗅探，对数据包p a y l o a d 进行匹配分析，其核心思想就是 多模式的精确匹配。在s n o r t 系统的历代版本中，汇集了各种主流的多模式匹配算法， 实现了字符串的多模式匹配，但主要是针对英文信息的检测。 中国科学院硕士学位论文一种基于可重构计算的汉字模糊匹配算法与硬件实现 2 2 模糊匹配算法 伴随着检测技术的发展，各种有害信息也采用诸如添加、删除、替换、拆分等手段 试图绕过检测系统的监控。而随着应用领域的发展和数据规模的扩大，可以容忍一定错 误的近似模式匹配得到更多的关注。例如，接收到的信弓在传输中受到噪声的影响，生 物计算中d n a 序列的突变，文本扫描中有意或无意的拼写错误。此外在模式识别、图 像压缩、文本压缩、病毒和入侵检测等应用中，都有一些模糊匹配算法被提出。 模糊匹配算法土要包括：动态规划算法、自动机算法、过滤算法、位并行算法等【1 ”。 2 2 1 基于距离计算的模糊匹配 计算序列间的距离是模糊匹配技术中一种最常用的方法，这种思路主要是针对不同 的应用领域建立不同的错误模型，针对插入、删除、替代、交换等不同的错误类型建立 不同的罚分机制，计算文本串( t ) 和模式串( p ) 之间的“距离”。当距离小于某个阈 值时，即可认定两个串近似匹配。 这里的“距离”通常是指能够使两串相同的最少的插入、删除、替代、交换等修改 次数，它衡量了两个串中最相似部分的近似程度；而“阈值”则标志了可以认定两序列 匹配的最小近似程度，只具有统计意义。 考察两个串的近似度( 距离) 通常有以下几个标准： 编辑距离( l e v e n s h t e i no r e d i t d i s t a n c e ) ，允许“插入”、“删除”和“替代”错误； 0 d ( x ，y ) m a x ( 1 工i , i y l ) 海明距离( h a m m i n gd i s t a n c e ) ，允许“替代”错误； 0 d ( x ，y ) l 工j i 工l 刊y i e p i s o d e 距离( e p i s o d ed i s t a n c e ) ，允许“插入”错误。 d ( x ，y ) = ( 1y 卜l 工i ) o r 2 2 2 动态规划算法 动态规划是广泛使用的一种计算距离的方法通过计算距离矩阵c o 制川，l 得到两个 序列x 和y 的距离，其中c 表示将x o 。转换成y o j 所需要的最少操作个数，而最后一 点c ，i 的值即为两序列的最小距离 c i o = i c o ，j = j 第二章模式匹配算法及硬件实现 c i ，】= 1 + m i n ( c c t - ，l c , j - | 一，c i - l 。一) x x 。l2 y y j j c i 。川5 e d ( x ，y ) 表2 1 一动态规划矩阵 0surgery do l23 4567 slol23456 u2 lol23 45 r32lol234 v4 32ll234 e54322l23 y65433222 使用动态规划算法进行模糊匹配的最坏和平均时间复杂度为o ( 1 x l l y l ) ，空间复杂度为 o ( m i n ( 1 x l ，l y l ) ) ，只需要保留一行或一列的数据即可但在有些应用中需要确切的找到近 似字串的具体位置，这是就需要保留整个矩阵的数据以便回溯。 2 2 3 自动机算法 模糊匹配的另一种主要方式是利用非确定性状态机建立一个查找模型，通过状态跳 转记录匹配的和出现错误的字符。 图2 4 基于自动机的模糊匹配算法 在图2 4 所示的状态机中，每一列表示模式中的一个字符或子串，每一行分别对应 出现错误的个数。匹配过程中状态按箭头所指的方向移动，其中水平方向箭头表示匹配， 垂直方向箭头表示插入，斜向箭头表示替换，虚线箭头表示册4 除。状态机从左上角的起 始点开始，当到达最右边的状态时匹配完成。对于不同的距离类型和不同的罚分机制， 可以通过采用不同的箭头组合来实现。例如海明距离只考虑替代错误，因此需要使用水 平箭头和斜向箭头，e p i s o d e 距离只考虑插入错误，因此需要使用水平箭头和垂直箭头。 此外对于不同的罚分情况，也只需要修改跳转的行数。 9 中国丰 学院硕士学位论文一种基于可重构计算的汉字模糊匹配算法与硬件实现 使用状态机方式可以很容易得到o ( n ) 的最坏时问复杂度，但是需要建立复杂的状态 机，特别是对于模式比较长，以及罚分方式有较大差异的时候，状态机的复杂度将显著 上升。对于硬件实现来说，将大大增加资源消耗和逻辑复杂度。 2 2 4 基于搜索树的模糊匹配 模糊匹配要求能够在文本t 中检测到允许k 个错误存在的长度为m 的模式p ，可以 看出这个被检测出近似匹配的子序列长度应该在m - k 和m + k 之问，过长或过短都无法满 足上述要求。因此可以得到一个模式p 的近似匹配模式集u t ( p ) ，利用传统的精确匹配 方法在文本t 中检测这一近似模式集，即可得到近似匹配结果。 以例= x e a ( x , 彤” 例如模式p - 摆貊o 对应允许1 个错误的近似模式集u 1 ( ：t 盈e l l o ? ： u 。( p ) = e l l o ih l l o | h e l o fh e l l u u x e l l o lh x l l o 。h e x l o th e l x o | h e l i x u u x h e l l o ih x e l l o 。h e x l l o lh e l x l o fh e l l x o | h e l l o x z 由于每个模式对应的近似模式集都会随着k 的变化呈指数增加，因而这种方式将原 有模式集大大扩充。对于大规模的多模式匹配，如果逐一检测每个模式显然是非常困难 的。为此需要将模式集构造成树，这样可以缩减模式集的大小，也为匹配过程提供便利。 2 2 5 基于过滤思想的模糊匹配 在模式匹配过程中检测“不匹配”的情况比检测“匹配”的更容易。过滤算法正是 基于这种思想对文本进行粗筛，将不匹配的部分先筛除掉。 如果a 、b 为两个近似匹配的序列，即e d ( a ，b ) 热，其中a 可以表示为子串a i 和x 。 的集合a = a l 。i a 2 x 2 x k ，i a ( 窀1 ) ，此时序列a 中至少有s 个子串a 1 1 在序列b 中出现。 爿 墨! 二l j 三一一乌 蔓!壁 生! !基! b 一筮： 图2 5 基于过滤思想的模糊匹配 如果a 、b 为两个近似匹配的序列，即e d ( a ，b 玛( ，其中序列a 可以表示为子串a 和x 。的集合a = a l x l a 2 x 2 x j i a j 伫1 ) ，此时序列a 中至少有一个子串a l 出现在序列b 中 并且包含l k j j 个错误。 第二章模式匹配算法及硬件实现 a 2 x 2a 3 _ 一- r 一 a 2 j 、，、，、 、 、，、 图2 6 基f 过滤思想的模糊匹配 每一个近似匹配的序列都会包含一些没有错误的子序列，因此通过精确检测模式中 的一系列片断，可以实现近似匹配整条序列的要求。这种方法实际上将模式再进一步划 分成一系列模式片断，使用精确匹配算法逐一对这些片断进行精确匹配，再根据这些片 断构造出完整的模式，实现模糊匹配。由于在主要计算部分使用了精确匹配算法，过滤 算法比通常的模糊匹配算法速度更快。但它只适用于模式串比较长的情况，对于那些相 对较短的模式( 如中文模式的模糊匹配) ，切分后仅剩下单个的字符就失去了它的意义。 此外这种切分方式也不能涵盖所有的近似情况。 2 2 6 基于位并行算法的模糊匹配 位并行算法充分利用了计算机指令自身位操作的并行性，将非确定性状态机映射到 计算机的字节中，每一个状态对应一位，使用“位”来标志状态信息，从而减少了指令 数量，大大缩短了执行的时间。此外在位并行思想的基础上，还可以应用动态规划算法， 这使得软件实现模糊匹配上可以得到很好的效果。但这种方法不适合硬件实现，这里不 做过多的介绍。 2 3 精确匹配算法的硬件实现 在诸多硬件解决方案中，a s i c 器件凭借其自身提供的专用加速部件，可以支持很高 的数据流量和数据处理能力，但成本高、灵活性差，因而应用相当有限，更多的系统则 是采用多处理器的方式，如利用网络处理器实现模式的并行处理。近年来随着可重构技 术的发展，f p g a 以其灵活性和低成本备受关注，针对网络信息的检测，基于f p g a 的 多模式精确匹配系统，其带宽通常可以达到g b p s 量级，远超过软件系统的处理能力。 在这一节中我们将介绍几种主要的硬件实现方法和解决方案。 2 3 1 精确匹配算法的硬件方法 硬件解决方案采用以空间换时间的方式，充分利用并行性提高系统性能，特别是针 对计算量大的应用，可以通过专用的算法加速部件分担系统的运算负担。而在诸多实现 方法中，对于算法的选择除了需要考虑逻辑电路的复杂度之外，更重要的是在有限的硬 件资源内，平衡时间与空间的开销，兼顾在实际应用中的灵活性