（计算机科学与技术专业论文）基于bloom+filter的报文分类算法研究.pdf

国防科学技术大学研究生院学位论文 摘要 在互联网飞速发展的同时，网络安全问题日趋严重。特别是各种新型的网络 攻击不断出现，对网络的正常稳定运行带来巨大的威胁。入侵防护是一种主动的 深度防御技术，通过采取主动防护和在线防御，可以有效抵御各种网络攻击。 然而随着网络链路速率的不断提高和网络流量的不断增加，入侵防护系统 ( i n t r u s i o np r e v e n t i o ns y s t e m ，i p s ) 的实现面临严重的性能挑战。报文分类是i p s 处理流程中的重要环节，其实现效率是影响i p s 性能的重要因素。本文对i p s 中报 文分类技术进行研究，提出将b l o o mf i l t e r 应用于报文分类的新方法，并对这种方 法进行了深入分析。论文的主要工作和贡献包括： 提出了基于b l o o mf i l t e r 的报文分类算法b f p c 。该算法基本思想是采 用计数型b l o o mf i l t e r 与动态链表相结合的方式，实现报文分类的功能。 与其他算法相比，b f p c 算法在时间、空间复杂度等方面具有一定优势。 对b f p c 算法的功耗开销进行了深入的分析。以降低算法实现功耗为目 标，提出了将h a s h 函数分段计算与最短链表精确匹配相结合的优化方法。 通过推导表明，优化有效降低了算法实现的功耗。 对i p s 硬件实现模型进行了分析，提出了i p s 中基于b f p c 算法的流信息 预处理引擎实现框架，并对b f p c 算法的具体实现，包括参数选择、数据 结构设计、模块划分和处理流程等，进行了深入分析。 b l o o mf i l t e r 是支持快速数据检索的重要方法。本文提出的b f p c 算法为将 b l o o mf i l t e r 应用到网络安全设备的设计中提出了新的思路，具有一定的研究价值 和应用价值。 关键词：入侵防护系统，b l o o mf i l t e r ，报文分类，h a s h 函数 第i 页 国防科学技术大学研究生院学位论文 a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to fi n t e r n e t ，t h ep r o b l e m so fn e t w o r ks e c u r i t yb e c o m e e v e nm o r es e v e r e e s p e c i a l l yt h ec o n s t a n ta p p e a r a n c e so fn e wn e t w o r ka t t a c k sb r i n gt h e g r e a tt h r e a t st ot h es t a b i l i t yo fn e t w o r k i n t r u s i o np r e v e n t i o ni sat e c h n i q u et op r e v e n ta l l k i n d so fn e t w o r ka t t a c k se f f e c t i v e l yb yt h em e a n so fa c t i v ep r o t e c t i o na n dd e f e n c e o n l i n e h o w e v e r ，谢t ht h ec o n s t a n ti n c r e a s eo ft h el i n ks p e e da n dn e t w o r kt r a f f i c ，t h e i m p l e m e n t a t i o no fi n t r u s i o np r e v e n t i o ns y s t e m ( i p s ) w i l lm e e tas e r i o u sc h a l l e n g eo n p e r f o r m a n c e t h et e c h n i q u eo fp a c k e tc l a s s i f i c a t i o n i sa ni m p o r t a n tp r o c e s si nt h e i m p l e m e n t a t i o no fl p s ，a n dt h ee f f i c i e n c yo fa l g o r i t h m sf o rp a c k e tc l a s s i f i c a t i o np l a y sa p a r t i c u l a rr o l ei nt h ep e r f o r m a n c eo fi p s t h ep u r p o s eo ft h i sp a p e ri st op r e s e n tan e w a l g o r i t h mf o rp a c k e tc l a s s i f i c a t i o nb a s e do nb l o o mf i l t e ra n ds t u d yt h en e wa l g o r i t h m d e e p l y t h em a i nc o n t r i b u t i o n so f t h i sp a p e ra r ea sf o l l o w s ： p r e s e n tan e w a l g o r i t h mf o rp a c k e tc l a s s i f i c a t i o nb a s e do nb l o o mf i l t e rw h i c h i sn a m e db f p c t h ec o r ei d e ao ft h i sa l g o r i t h mi st om a k et h ef u n c t i o no f p a c k e tc l a s s i f i c a t i o nb yc o m b i n i n gt h ec o u n t i n gb l o o m f i l t e rw i t ht h ed y n a m i c c h a i nl i s t s t h ea l g o r i t h mo fb f p ch a st h ea d v a n t a g eo v e ro t h e ra l g o r i t h m si n t h ea s p e c t so ft i m ec o m p l e x i t y ，s p a c ec o m p l e x i t ya n ds oo n m a k er e s e a r c hi n d e p t ho nt h ep o w e rc o n s u m p t i o no fb f p c w i t ht h ep u r p o s e o fr e d u c i n gt h ep o w e rc o n s u m p t i o n ，a no p t i m i z e da p p r o a c ho fc o m b i n i n gt h e o p e r a t i o no ft w op h a s e sf o rh a s hf u n c t i o nw i t ht h ea c c u r a t em a t c ho ft h e s h o r t e s tc h a i nl i s ti sp r e s e n t e d i ti sc a l c u l a t e dt h a tt h eo p t i m i z a t i o nc a nr e d u c e t h ep o w e rc o n s u m p t i o no fb f p ce f f e c t i v e l y m a k ea na p p r o a c ht ot h em o d e lo fi p sd e s i g n e db yh a r d w a r e a n dt h e f r a m e w o r kt oi m p l e m e n tt h ep r e t r e a t m e n te n g i n ef o rd a t af l o ww h i c hi sb a s e d o nt h eb f p ci ni p si sw e l li n t r o d u c e d t h ep a p e ra l s o a n a l y z e s t h e i m p l e m e n t a t i o no fb f p c ，i n c l u d i n gt h es e t t i n go fp a r a m e t e r s ，d a t as t r u c t u r e s ， m o d u l ep a r t i t i o n s ，m a n i p u l a t i o np r o c e s sa n ds oo n b l o o mf i l t e rp l a y sa ni m p o r t a n tr o l et os u p p o r tq u i c kq u e r yo fd a t ae l e m e n t s t h e a l g o r i t h mo fb f p cp r o p o s e di nt h i sp a p e rg i v e san e ww a y t oa p p l yt h eb l o o mf i l t e rt o t h ed e s i g no fe q u i p m e n t sf o rn e t w o r ks e c u r i t y ，a n dh a st h es i g n i f i c a n c eo fr e s e a r c ha n d a p p l i c a t i o n k e yw o r d s ：i n t r u s i o np r e v e n t i o ns y s t e m ，b l o o mf i l t e r ，p a c k e tc l a s s i f i c a t i o n ，h a s h f u n c t i o n 第i i 页 国防科学技术大学研究生院学位论文 表目录 表2 1 假阳性概率在不同的m n 和k 的组合下的分布1 4 表3 1 多种报文分类算法比较2 6 表5 1 流信息预处理引擎实现参数设置4 5 表5 2 主要数据结构具体情况表4 7 表5 3h c t 表项节点存储信息4 7 第1 i i 页 国防科学技术大学研究生院学位论文 图 目录 图1 1i p s 网络分布图2 图1 2i p s 工作原理图。3 图1 3r f c 算法数据流图6 图2 1b l o o mf i l t e r 基本结构图9 图2 2 假阳性概率f 与k 关系图1 5 图2 3 假阳性概率f 与m 、n 关系图1 6 图2 4 计数型b l o o mf i l t e r 结构图17 图3 1b f p c 算法原理结构图1 9 图3 2 特征向量及动态链表构造图2 0 图3 3 规则查询算法流程图2 1 图3 4 规则添加算法流程图2 2 图3 5 规则删除算法流程图2 3 图3 6b f p c 算法详细结构图2 4 图4 1 分阶段h a s h 运算结构图3 0 图4 2 不同m n 取值下功耗p 与r 关系图3 4 图4 3 第一阶段匹配成功概率p 与r 关系图3 4 图4 4 功耗p 与r 关系图3 5 图4 5 功耗降低比率与r 关系图3 6 图5 1i p s 硬件模型结构图3 7 图5 2i p s 硬件模型处理流程图3 9 图5 3 五元组提取模块功能划分图4 0 图5 4 五元组提取流程图4 0 图5 5 流信息预处理引擎结构图4 1 图5 6 流信息预处理流程图4 2 图5 7 负载分配引擎模块结构图4 3 图5 8 主要模块划分图4 4 图5 9 假阳性概率f 与变量t 关系图4 5 图5 10 主要数据结构关联图4 6 图5 1 1 特征向量存储空间分配图4 7 图5 1 2 流i d 存储空间分配图4 7 图5 1 3 定时器及流状态存储空间分配图4 8 图5 1 4 流查询请求处理流程图4 9 第1 v 页一 国防科学技术大学研究生院学位论文 图5 15 流创建请求处理流程图5 0 图5 1 6 流删除请求处理流程图5 l 图5 1 7 动态链表修改情况分析图5 l 图5 1 8 流超时管理处理流程图5 2 第v 页 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已 经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它教育机构的学 位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文 中作了明确的说明并表示谢意。 学位论文题目：基王堡! q q 堕i ! ! 壁! 鲍拯塞佥耋簋垂堡窒 学位论文作者签名： 鱼趔二日期：矽哆年2 月妇 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留、使用学位论文的规定。本人授权国 防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子文档，允 许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据库进行检索， 可以采用影印、缩印或扫描等复制手段保存、汇编学位论文 ( 保密学位论文在解密后适用本授权书。) 学位论文作者签名：妇壶宣= 衔拊教燃：搀珥一 日期：砷年，工月多日 日期：2 7 年，z 月z 日 国防科学技术大学研究生院学位论文 第一章绪论弟一早三百y 匕 随着计算机和通信技术的不断发展，计算机得到了广泛和深入的应用。网络 连接的计算机用户数量日益增多，网络的开放性和共享性也在不断的扩大。现在 计算机已经成为人们生活和工作中不可缺少的重要的组成部分。但是，在人们充 分享受计算机网络带来的方便和快捷的同时，计算机网络的安全问题也越来越变 得重要，成为有关研究人员关注的热点问题。 1 1 课题研究背景 在过去的几年中，随着网络技术，尤其是光纤技术的快速发展，光纤通信网 络正迅速成为主要的网络传输手段，使网络带宽一直呈指数级的增长趋势。网络 应用的性能需求表现为高吞吐量、低延迟、高带宽、低主机开销和低存储开销等 特点。面对目前网络运行的现状，网络攻击呈现出新的趋势： 首先，攻击过程的自动化与攻击工具的快速更新，攻击工具的自动化程度继 续不断增强，自动化攻击涉及的内容也都发生了变化。 其次，攻击工具的不断复杂化。攻击工具的编写者采用了比以前更加先进的 技术，攻击工具的特征码越来越难以通过分析来发现，并且越来越难以通过基于 特征码的监测系统发现，例如防病毒软件和入侵监测系统，当今攻击工具的三个 重要特点是反监测功能、动态行为以及攻击工具的模块化。 再次，漏洞的数量在成倍的增长。对于每天新发现的漏洞，软件厂商及时进 行修补存在一定的难度，而且入侵者往往能够在修补漏洞之前首先发现这些漏洞， 随着发现漏洞的工具的自动化趋势，留给用户打补丁的时间越来越短，尤其是缓 存区溢出类型的漏洞，是计算机安全的最大威胁。 最后，随着网络上计算机的数量的不断增长，所有计算机之间存在很强的依 存性，如果某些计算机遭到入侵，它就有可能成为入侵者进一步攻击的跳板。对 于网络基础架构如d n s 系统、路由器的攻击也成为一个严重的安全问题 j 】。 基于上面所描述的网络攻击的新趋势，计算机网络的安全问题，已经成为计 算机应用和信息化建设的关键问题。传统的计算机网络安全技术包括防火墙技术， 入侵检测技术等。 防火墙技术的核心思想是在不安全的网络环境中构造一种相对安全的内部网 络环境。它比较适合于内部网络相对独立，且与外部网络的互联途径有限、网络 服务种类相对集中的网络。虽然防火墙可以提高内部网络的安全性，但是也存在 一些缺陷和不足，具体表现有：防火墙不能阻止来自内部的攻击，防火墙不能提 第1 页 国防科学技术大学研究生院学位论文 供实时检测以及不能跟踪入侵者等【2 j 。 入侵检测是指发现非授权用户企图使用计算机或者合法用户滥用特权的行 为。为完成入侵检测任务而设计的计算机系统为入侵检测系统，即i d s 。i d s 作为 防火墙有益的补充，能够帮助网络系统快速地发现攻击的发生，它扩展了系统管 理员的安全管理能力，提高了信息安全基础结构的完整性，但是i d s 还是存在一 些问题和缺陷：缺乏主动的防御能力，缺乏准确定位和处理机制以及性能普遍不 足等【3 1 。 针对防火墙和i d s 存在的上述不足，以及网络入侵所表现出来的新的特点和 趋势，有关研究人员经过长期的研究发现，采用主动防御的措施来应对新阶段的 网络攻击具有很好的效果。所以一种新型的网络安全技术一一入侵防护系统 ( i n t r u s i o np r e v e n t i o ns y s t e m ，i p s ) 越来越受到人们的关注。研究i p s 具有极其重要 的理论和实际意义。 目前大多数的网络安全技术是有局限性的，因为它们使用特征码辨别是否存 在攻击行为，这意味着只能检测已经编入识别程序的特定的攻击。因为最新出现 的攻击尚未被广泛认识，新的特征码尚未被开发出来。因此最有效的防御技术是 直接瞄准潜在的、新的攻击，找出延迟其破坏的方法。这就提出了主动防御的入 侵防护系统的需求【1 删。 图1 1i p s 网络分布图 上副4 】为i p s 在网络中的分布图。i p s 实现实时检查和阻止入侵的原理在于i p s 拥有数目众多的过滤器，能够防止各种攻击，当新的攻击手段被发现后，i p s 就会 创建一个新的过滤器。i p s 报文处理引擎是专业化定制的集成电路，可以深层检查 数据包的内容，如果有攻击者利用介质访问控制层到应用层的漏洞发起攻击，i p s 能够从数据流中检查出这些攻击并加以阻止。传统的防火墙技术不能对应用层的 内容进行检测，它的包过滤技术也不会针对每个字节进行检查，因而也就无法发 第2 页 国防科学技术大学研究生院学位论文 现攻击活动。i p s 可以做到对每个字节进行检查。 i p s 对报文的处理流程可以简单的概括为：所有经过i p s 的报文都将被分类， 分类的依据是报头信息，例如源i p 地址和目的i p 地址，源端口号和目的端口号以 及协议号等内容。每种过滤器负责分析对应的报文内容。通过过滤检查被标记为 安全的报文可以继续在主干网络中传送，包含恶意内容的报文将会被丢弃，被怀 疑的报文需要接受进一步的检查。具体的流程图如下图所示： 图1 2l p s 工作原理图 过滤器引擎集合了流水和大规模并行处理硬件，能够并行执行数据包的过滤 检查。并行过滤处理可以确保数据包能够不问断的快速通过系统，不会对速度造 成影响。硬件加速技术对于i p s 而言具有重要的意义，因为传统的软件解决方案 必须串行的进行过滤检查，会导致数据包的处理速度与同益增长的网络带宽不相 匹配【5 】【6 】。 经过应用以及验证，可以发现i p s 拥有以下几个方面的特尉6 】： ( 1 ) 嵌入式运行。只有以嵌入模式运行的i p s 设备才能够实现实时的安全防护， 实时拦截所有可疑的数据包，并对该数据流的剩余部分进行拦截。 ( 2 ) 深入分析和控制。i p s 必须具有深入分析能力，以确定哪些恶意的流量已 经被拦截，根据攻击类型、策略等来确定哪些流量应该被拦截。 ( 3 ) 高质量的入侵特征库是i p s 高效运行的必要条件，i p s 还应该定期的升级 特征库，并快速的应用到所有的传感器。 ( 4 ) i p s 必须具有高效处理数据包的能力，对整个网络性能的影响保持在最低 水平。 上面的内容对i p s 的工作原理以及特点进行了说明，通过介绍以及目前网络 攻击的现状可以看到采取主动防护的措施是重要的，同时也是必然的。i p s 作为一 种新型的网络安全技术，必将拥有广阔的应用前景。 1 2 i p s 面临的挑战 第3 页 国防科学技术大学研究生院学位论文 尽管i p s 具有广泛的应用前景，但是设计并实现高效的i p s 也面临了众多的挑 战，包括性能瓶颈、单点故障和误报漏报等。其中最主要的问题是性能瓶颈，主 要表现在i p s 必须与数千兆或者更大容量的网络流量保持同步，尤其是当加载了 数量庞大的检测特征库时，设计不够完善的i p s 将无法支持这种响应速度。由于 嵌入式的工作模式，性能的好坏直接影响到整个网络的正常运转，所以面对网络 主干流量的飞速增长，i p s 性能的好坏直接决定了单点故障和误报漏报的情况。如 果i d s 出现故障，最坏的情况就是造成某些攻击无法被检测到，而如果嵌入式的 i p s 遇到故障关闭，用户就会面对一个由i p s 造成的拒绝服务问题，所有客户将无 法访问网络提供的应用。 从图1 2 所示的i p s 原理图可以看到到达i p s 的报文首先需要经过报文分类的 处理，然后根据负载情况送交过滤器处理，最后确定是否丢弃报文，从整个流程 可以看到过滤操作可以并行处理，然而报文的分类只能串行处理，所以报文分类 算法的性能是造成i p s 性能瓶颈的主要因素。设计一种高性能低功耗的报文分类 算法是解决i p s 性能瓶颈的关键所在，绝大多数的i p s 产品都在寻求使用硬件，比 如f p g a 7 | ，来对报文分类算法进行设计，降低功耗，提高运行效率。 报文分类算法的性能直接决定于算法的功耗开销的大小，原因在于算法的性 能主要通过最坏情况下的复杂度等参数得到体现。通过研究高性能算法的时间和 空间复杂度等参数可以发现与算法的功耗存在必然的联系。 报文分类算法的功耗主要体现在算法实现时所占用的资源和时间。算法所占 用的资源主要体现为所使用的内存，内存数量决定了算法的空间复杂度。频繁的 内存访问是分类算法速度慢的主要原因，也是功耗增加的主要因素，尤其是并行 的内存访问。比如t c a m 使用的是并行匹配比较方式，所以t c a m 芯片的功耗较 大。因此减少内存访问的次数，对于分类算法而言至关重要，这也是分类算法满 足一定的功耗要求的原因所在。此外算法实现时对于内存的维护和管理同样属于 算法的功耗范畴，如果内存的数量居多，势必造成维护和管理变得复杂，算法的 功耗增大，同样空间复杂度也超出了高性能低功耗算法的限度。 算法处理报文所占用的时间主要分为两部分，分别是报文处理的必需时间和 滞后时间。必需时间表示报文处理占用的必不可少的时间，滞后时间表示的是由 于访存速度不同等原因所产生的额外等待时间。所以算法功耗的大小还体现在算 法处理报文时所产生的必需时间和滞后时间的长短。对于所有算法而言必需时间 是相对固定的，而滞后时间由于内存访问技术的不同表现出长短区别，因此从某 种意义上算法功耗的大小与滞后时间的长短存在必然的联系。功耗低的算法所产 生的滞后时间短，提高了网络带宽的利用效率，相应的提升了报文分类的吞吐量， 更为重要的是算法的时间复杂度也会相应的减小，符合高性能低功耗算法的要求。 第4 页 国防科学技术大学研究生院学位论文 上述内容从时间和空问两个角度对报文分类算法的性能和功耗分别作了讨 论，从中可以看到性能与功耗存在必然的联系，所以实现高性能的算法可以从降 低功耗的方向进行研究。 基于报文分类算法的重要性，对其设计应当遵循以下四个原则：线速转发原 则、折衷原则、满足实时需要原则和简单性原则。其中简单性原则是针对算法的 功耗问题提出的，其思想是在满足实时需要的前提下，设计简单的算法，过分复 杂的算法不仅导致实现过程复杂，而且算法本身的运行要消耗一定的资源和时间 【8 】 o 一个实用的快速分类算法需要进行多方面的权衡，往往需要结合多种算法的 设计思想。可以看到，分类算法要满足高速网络设备所需要的高速率，最终还要 利用硬件来实现。每一种快速的报文分类算法都是在定应用特定的前提下针对 特定的应用场合而提出的。由于前提和应用场合的差异，没有统一的标准来衡量 各种算法的优劣，在实际应用中也很难找到现成的算法能直接用于特定的应用系 统，需要通过研究和综合各种思想，才能设计和实现适用于自身应用需求的算法【9 1 。 实用化的快速报文分类技术的研究是近年来的一个热点。其目的是在有限的 空问条件下，根据报文分类的特点来设计算法，使其能用较大分类规则集对分组 进行快速分类处理，且在最坏情况下也具有较高的性能。目前已经提出了若干算 法，下面将对已有的算法进行简单的介绍【9 j 。 算法从实现的角度可分为两种：一种是全部用硬件实现的算法，另一种是软 件实现的算法。软件算法一般提供特定维数的分类能力，特别是一维和二维的分 类算法。对于支持高维分类的算法在空间和时间复杂度上不能很好的满足要求。 全部用硬件实现的算法对报文分类而言，分类速度快，时间和空问复杂度能够很 好的满足要求，但是从价格而言比较昂贵。 传统的报文分类算法主要分为四类，分别为基于数据结构的算法、几何算法、 启发式算法和基于硬件的算法。基于数据结构的算法主要从表和树两种数据结构 进行报文的分类实现。几何算法对基于树的分类算法有所改进，降低了时间和空 间复杂度。启发式算法和硬件实现的算法目前运用的比较广泛，以下将对几种已 有的算法进行简要的介绍【8 】【1 0 】【l l 】。 ( 1 ) 线性查找 线性查找( l i n e a rs e a r c h ) 是一种基于数据结构的算法，它是最简单的一种数 据结构，按照优先级升降顺序把分类规则存储在一个数组或者链表中。对于一个 到达报文的报头，逐条查找规则，直到匹配为止。很明显，线性查找的空间和时 间复杂度都是o 州) ，这种方案不适用于有大量规则的报文分类情况【1 0 1 。 ( 2 ) c r o s s p r o d u c t i n g 第5 页 国防科学技术大学研究生院学位论文 c r o s s p r o d u c t i n g 为一种基于计算几何的报文分类算法，是一种适合于任意维 数和任意形式域的流分类方案。主要思路是将多维的报文分类问题建立在多个一 维的报文分类基础上，利用多个一维的报文分类的结果查找c r o s s p r o d u c t i n g 表获 得最终的分类结果。该方法的主要优点是便于实现，缺点是对规则维数和数量的 可扩展性较差。 ( 3 ) 递归流分类算法 递归流分类( i 强c ) 算法采用的是递归方式来分步骤解决任意规则的流分类问 题。属于启发式的算法。r f c 算法把多字段分类问题看作为数据包头控制字段取 值空间( s ) 到类标识空间( t ) 的映射问题( t = l o g n ，n 为规则数，且t ) 和左移( ) 操作。 第1 0 页 国防科学技术大学研究生院学位论文 ( 1 ) 异或移位【1 9 】 在此以循环位移3 b i t 为例介绍异或移位函数的计算过程： h a s h l = a s i p ( 1 6 3 ) ；h a s h l = h a s h loa d i p ；h a s h = h a s h l ： h a s h l = b s i p ( 1 6 3 ) ；h a s h l = h a s h los p o r t ；h a s ho = h a s h l ； h a s h l = b d i p ( 16 3 ) ；h a s h l = h a s h lod p o r t ；h a s ho = h a s h l 。 其中h a s h l 、h a s h 为1 6 b i t 无符号整型。h a s h 是异或、位移算法返回的哈希序 列。 ( 2 ) i p s x 1 9 1 f l = i p 源地址，f 2 = i p 目的地址，f 3 = t c p 或u d p 报文的源端口和目的端口。 中间变量h 1 、v l 、v 2 均是3 2 比特串。算法的输出是h 1 的后1 6 b i t 串。 v l = f l0t 2 ；v 2 = f 3 ；h l = v l 4 ；h lo = v 1 1 2 ： h lo - - - v l 1 6 ；h l0 = v 2 6 ：h lo - - - v 2 1 0 ；h l0 - - - v 2 7 。 ( 3 ) 随机数法【1 7 】【2 0 】【2 1 1 1 2 2 j 随机数法根据采用的不同的随机数可以生成一系列的h a s h 函数，该方法的具 体定义如下：假设给定源i p 前1 6 b i t ，记为b s l p 2 i x l ，x 2 ，x 1 6 ) ，则第i 个h a s h 函 数的表示如下： 魄( x ) = 谚l 五o z 2 x 2o 0 2 1 6 6 j 其中“口表示的是第i 组随机数序列中的第j 个随机系数，它的取值满足从1 到 特征向量深度m 之间的均匀分布的条件，表示为输入数据的第i 个比特位，表 示与运算，o 表示x o r 运算。此类h a s h 函数硬件实现方便，如上面的例子，该 函数的实现只需要1 6 个两输入的与门和一个1 6 输入的异或门就可以产生出h a s h k e y 。 异或移位、i p s x 和随机数法这3 种算法本质上都是位移和异或操作的组合， 都具有时间复杂度为o ( 1 ) 的运算。而异或和移位操作都可以方便的采用硬件加以 实现，所以针对硬件实现的b l o o mf i l t e r 而言，上述h a s h 函数为理想的选择。 根据h a s h 冲突解决的方法可以分为两种：直链式和散列式。 ( 1 ) 直链式1 2 3 】 直链式的方法是将产生相同索引值的数据元素通过链表进行存储。链表的头 指针存放在h a s h 索引值对应的特征向量中。以下是对该方式的插入、查询和删除 迸行描述。 c h a i n e d h a s h i n s e r