布隆过滤器、计数布隆过滤器与其应用课件.pptx

1、信息安全课程报告Bloom filter - The course report of Information security布隆过滤器组长： 汇报人：目录CONTENTS1背景介绍2算法描述3误判概率证明和计算4优劣详解6布隆过滤器设计和应用5布隆过滤器改进方案布隆过滤器 背景介绍The background of Bloom filter01比如在字处理软件中，需要检查一个英语单词是否拼写正确（也就是要判断 它是否在已知的字典中）；在 FBI，一个嫌疑人的名字是否已经在嫌疑名单上；在网络爬虫里，一个网址是否被访问过等等。背景介绍 一般来讲，计算机中的集合是用哈希表（hash table）

2、来存储的。 Hash函数作用就是把要存的数据映射成hash表中的一个位置，这个位置就是你要存放该数据的地方。一般把hash表的每个位置都叫做“槽（slot）”。 它的好处是快速准确，缺点是浪费存储空间。当集合比较小时，这个问题不显著，但是当集合巨大时，哈希表存储效率低的问题就显现出来 了。Hash函数假设hash表的大小为9（即有9个槽），hash(k) = k mod 9，现在要把一串数据存到表里：5,28,19,15,20,33,12,17,10 hash(5)=5, hash(28)=1，hash(19)=1， 0 1 2 3 4 5 6 7 8 n个关键字映射到k个槽中，n只要大于k，

3、一定至少有一个槽放了多于1个元素，所以不能完全避免碰撞（冲突） 。 Hash函数285位图法就是Bitmap的缩写。就是用每一位来存放某种状态，适用于大规模数据，但数据状态又不是很多的情况。通常是用来判断某个数据存不存在的。 位图法可以理解为通过一个bit数组来存储特定数据的一种数据结构；由于bit是数据的最小单位，所以这种数据结构往往是非常节省存储空间。位图法比如一个公司有8个员工，现在需要记录公司的考勤记录，传统的方案是记录下每天正常考勤的员工的ID列表，比如2012-01-01:1,2,3,4,5,6,7,8。 假如员工ID采用byte数据类型，则保存每天的考勤记录需要N个byte，其中

4、N是当天考勤的总人数。 1 2 3 4 5 6 7 8 这样可以每天采用恒定的1个byte即可保存当天的考勤记录。位图法01110011布隆过滤器（Bloom Filter），它结合了位图和Hash表两者的优点. 位图的优点是节省空间，但是只能处理整型值一类的问题，无法处理字符串一类的问题. 而Hash表却恰巧解决了位图无法解决的问题，然而Hash太浪费空间。布隆过滤器布隆过滤器计数计数布隆过滤器布隆过滤器 计数布隆过滤器是对基本布隆过滤器的改进，使布隆过滤器可以支持删除成员。 因为布隆过滤器的基本单位是1个bit，只能表达2种状态，即存在、不存在。 如果把基本单位1bit拓展成多个bit，这

5、样就能增加更多信息，表达出多种状态。布隆过滤器 算法描述The description of its core algorithm 02Bloom Filter 布隆过滤器（Bloom Filter）是一种概率空间高效的数据结构。用于检索一个元素是否在一个集合中用于检索一个元素是否在一个集合中。 存在“在集合内（可能错误）在集合内（可能错误）”和“不在集合内（绝对不在集不在集合内（绝对不在集合内）合内）”两种情况。 温故知新 核心思想核心思想就是利用多个不同的多个不同的Hash函数函数来解决“冲突”。 如何判断某元素x是否在一个集合中？X1,X2,X3.XnRX核心思想算法原理 Bloom F

6、ilter需要一个位数组位数组(和位图类似)和K个映射函数个映射函数(和Hash表类似)。包含两种操作：插入和查询插入和查询1.初始化：将所有位置置02. 集合R=r1,r2.rn,通过k个相互独立的映射函数h1,h2,.hk，将集合R中的每个元素rj(1=j 忽略碰撞并且只存储元素是否在其中的二进制信息时k=1的布隆过滤器 使用k1的布隆过滤器，即k个哈希函数将每个元素改为对应于k个bits，因为误判度会降低很多，并且如果参数k和m选取得好，一半的m可被置为1，这充分说明了布隆过滤器的空间效率性。优点 布隆过滤器可以表示全集，其它任何数据结构都不能。 k和m相同，使用同一组散列函数的两个布隆

7、过滤器的交并差运算可以使用位操作进行。优点 在增加了错误率这个因素之后，布隆过滤器通过允许少量的错误来节省大量的存储空间。优点 有误判的概率，即存在假阳性（False Position），无法获取集合中的元素数据。 随着存入的元素数量增加，误算率随之增加。但是如果元素数量太少，则使用散列表足矣。（误判补救方法是：再建立一个小的白名单，存储那些可能被误判的信息。）缺点 一般情况下不能从布隆过滤器中删除元素。 另外计数器回绕也会造成问题。缺点布隆过滤器 改进方案The design and application in Bloom filter0500000000001亿邮箱随机数生成器随机数生成

8、器F1-8f1 = F1 f2 = F2f3 = F3f4 = F4 f5 = F5f6 = F6f7 = F7f8 = F8信息信息指纹指纹随机数生成器随机数生成器G10111111102111111110f1 = F1 = f1 f2 = F2 f3 = F3 = m2f4 = F4 = m3 f5 = F5 = m4f6 = F6 = m5f7 = F7 = m6f8 = F8 = m7CounterCounting Bloom FilterCounting Bloom Filter的出现解的出现解决了这个问题，它将标准决了这个问题，它将标准Bloom Bloom FilterFilte

9、r位数组的每一位扩展为一个位数组的每一位扩展为一个小的计数器小的计数器(Counter)(Counter)，在插入元素，在插入元素时给对应的时给对应的k(kk(k为哈希函数个数为哈希函数个数) )个个CounterCounter的值分别加的值分别加1 1，删除元素时，删除元素时给对应的给对应的k k个个CounterCounter的值分别减的值分别减1 1，Counting Bloom FilterCounting Bloom Filter通过多占用通过多占用的存储空间的代价，给的存储空间的代价，给Bloom Bloom FilterFilter增加了删除操作。增加了删除操作。10110102

10、10BFCBFn n：集合元素个数，集合元素个数，k k：HashHash函数个数，函数个数，k = 0.7 * m / n M M：位数组的大小位数组的大小从从nknk次哈希中选择次哈希中选择j j次次j j次哈希都选中了第次哈希都选中了第i i个个CounterCounter其它其它nkjnkj次哈希没有次哈希没有选中第选中第i i个个CounterCounter基本思想：基本思想：1.1.元素元素x x对应的对应的k k个个countercounter中的最小值中的最小值m mx x=出现频率出现频率f fx x2.2.f fx x m mx x的概率和标准的概率和标准bloom fil

11、terbloom filter的误判概率相同的误判概率相同5016111210k k个位置全个位置全部发生碰撞部发生碰撞索引结构索引结构co1co2co3co4o1o2o3o4子串长度子串长度log3N位位Coarse VectorCoarse Vectorco1co2o1o2子串长度子串长度(loglogN)3位位LOOK UP TABLEOffset VectorOffset Vector子串长度子串长度=(loglogN)3位位loglog2 2N N个个countercounterlogN/loglogNlogN/loglogN025701026527Counter0000010001

12、00010OverFlow VectorCounting Bloom Filter Vectorx=log(M/n)y = floor(log(max(OFj) + 1查询一个查询一个countercounter时，时，DCFDCF要要求两次内存访问。假设想查求两次内存访问。假设想查询位置为询位置为j j的的countercounter的值，的值，我们先读出我们先读出CBFVCBFV和和OFVOFV的值，的值，分别为分别为CjCj和和OFjOFj，那么，那么countercounter的值就可以表示为的值就可以表示为Vj = (2xVj = (2xOFj OFj Cj)Cj)。最大值增加至最大

13、值增加至2x+12x+1时，每次时，每次OFVOFV大小改变的时候都需要重大小改变的时候都需要重建。重建是一件开销很大的工建。重建是一件开销很大的工作，必须重新创建一个作，必须重新创建一个OFVOFV数数组，然后把旧组，然后把旧OFVOFV数组的值拷数组的值拷贝到新建的贝到新建的OFVOFV数组中，最后数组中，最后把旧把旧OFVOFV数组的空间释放掉。数组的空间释放掉。1000001000100010当当OFVOFV的最大值减少到的最大值减少到2x 2x 1 1时，我们可以选择马上重建时，我们可以选择马上重建OFVOFV，也可以采用一些策略延，也可以采用一些策略延迟迟OFVOFV的重建，以避免

14、一些临的重建，以避免一些临时性的减少导致时性的减少导致OFVOFV反复重建。反复重建。000001000000010布隆过滤器 设计和应用The design and application in Bloom filter06布隆过滤器应用假设有一条URL，那么就先建立32个二进制常量(取不同值，误报率会不同)。即4字节的向量，然后将这32个二进制位全部设置为0，对于这条URL，用8个不同的随机数产生8个信息指纹，再用一个随机数产生器把这8个信息指纹映射到1到32的8个自然数，并把这些位置置为1。如果要检测某条URL是否在这个Bloom Filter中，我们仍然用上述8个随机数产生8个信息指纹

15、，并将这8个指纹对应到布隆过滤器的8个二进制位，如果8位都为1，则说明这条URL在这个Bloom Filter中，否则只要有一位不为1，就说明不在。Bloom Filter绝不会漏掉任何一个重复的URL，但可能会有误报情况，虽然这种可能性很小，上述说的误报概率只有千万分之一，可以通过建立一个小的名单，存储可能误判的URL，并进行比较。已爬URL的过滤代码实现class BloomFilter private static final int BIT_SIZE = 2 28 ;/二进制向量的位数 private static final int seeds = new int3, 5, 7, 1

16、1, 13, 31, 37, 61;/用于生成信息指纹的8个随机数，最好选取质数 private BitSet bits = new BitSet(BIT_SIZE); private Hash func = new Hashseeds.length;/用于存储8个随机哈希值对象 public BloomFilter() for(int i = 0; i seeds.length; i+) funci = new Hash(BIT_SIZE, seedsi); 已爬URL的过滤代码实现public void addValue(String value) /将字符串value哈希为8个或多个整数

17、，然后在这些整数的bit上变为1 if(value != null) for(Hash f : func) bits.set(f.hash(value), true); public boolean contains(String value) if(value = null) return false; boolean ret = true; /将要比较的字符串重新以上述方法计算hash值，再与布隆过滤器比对 for(Hash f : func) ret = ret & bits.get(f.hash(value); return ret; 已爬URL的过滤代码实现/*随机哈希值对象*/pu

18、blic static class Hash private int size;/二进制向量数组大小 private int seed;/随机数种子 public Hash(int cap, int seed) this.size = cap; this.seed = seed; /* 计算哈希值(也可以选用别的恰当的哈希函数) */ public int hash(String value) int result = 0; int len = value.length(); for(int i = 0; i len; i+) result = seed * result + value.ch

19、arAt(i); return (size - 1) & result; public class Test public static void main(String args) BloomFilter b = new BloomFilter(); b.addValue(); b.addValue(); System.out.println(b.contains(); System.out.println(b.contains(); 计数布隆过滤器负载均衡（load balance）：将任务平摊到多个操作单元上执行，共同完成工作。半流 ：由相同的数据包组成的集合。全流：标识的半流和标识的半

20、流的并集 。大部分的多媒体协议信令和数据传输采用的是不同的端口。传统的负载均衡算法不能保证将多媒体会话映射到一个处理核上。因此应该根据流的信息动态调整映射位置。通过增加DP、SP的端口信息生成信息摘要，通过布隆过滤器直接映射到同一个处理器上面。计数布隆过滤器将需要调整的全流标识生成对应的摘要信息Digest，将其保存到精确流匹配布隆过滤器中，对于每一个到来的 IP数据包，提取标识并生成 Digest然后根据和 Digest查询 ESBF结构 ，如果在其中，则转发到指定的处理核 否则 ，对 Digest取模得到对应的处理核 ID。通过保存全流的标识到哈希表中 ，可以动态指定某个全流到相应的处理核

21、计数布隆过滤器ESBF算法基于 CBF,利用 CBF的多个哈希函数保证算法具有更低的冲突概率,CBF可以高效的根据(DA, SA, DP, SP)和k个哈希函数对IP包映射到不同的CPU上面进行处理。同时也可以对索引记录高效的插入和删除。动态更改处理IP包的CPU。 计数布隆过滤器插入算法代码如下：Insertelem(x，id)Digest DIGEST HASH(x)；创建链表结点并将 digest、id域赋值 ；for(i=l to k)ifLinkheadbi(x)counter=0)将结点添加到链表尾部；elseif(链表长度为 counter)将结点添加 到链表尾部；else将结点

22、添加到链表头部；)Linkhead(h。(x)counter+；)插入算法将由生成的 Digest依次插入到 k个链表之中。为了节省空间，如果结点都添加到链表尾部 ，则 k个链表可以共享一个链表结点 。计数布隆过滤器删除算法代码如下 ：Deletelem(x)Digest DIGEST HASH(x)；for(i=1 to k)j=O；while(jLinkheadh(x)counter)if(结点 中的 digest域与 Digest相等)将结点从链表中删除 ，跳出循环；j+；Linkhead(h。(x)Counter一； 删除算法将 k个链表 中结点 digest的值与生成的 Digest

23、相 等的结点从链表 中依次删除。计数布隆过滤器查询算法代 码如 下：Lookup(x)Digest DIGEST HASH(x)；for(i=l to k)if(Linkhead(h，(x)counter=0)return false；J-k个 counter中最小值对应 的 hi(x)for(i：1 to LinkheadDcounter)i结点 中的 digest域与 Digest相等)return 结点的 id域；return false；)查询算法取 k个计数器 中值最小的计数器所对应 的链表进行比较，最坏情况下比较的次数为该最小计数器的值。感谢聆听，批评指导THANK YOU TO LISTEN TO CRITICISM GUIDANCE布隆过滤器组长： 汇报人：