基于布隆过滤器的精确匹配算法设计与实现

计算机科学 ›› 2015, Vol. 42 ›› Issue (Z6): 429-434.

基于布隆过滤器的精确匹配算法设计与实现

王鹏超,杜慧敏,曹广界,杜琴琴,丁家隆

西安邮电大学电子工程学院西安710061,西安邮电大学电子工程学院西安710061,西安邮电大学电子工程学院西安710061,西安邮电大学电子工程学院西安710061,西安邮电大学电子工程学院西安710061

出版日期:2018-11-14 发布日期:2018-11-14
基金资助:
本文受国家自然科学基金(90607008,60976020),陕西省政府基金(2011k06-47)资助

Design and Implement of Exact Matching Algorithm Based on Bloom Filter

WANG Peng-chao, DU Hui-min, CAO Guang-jie, DU Qin-qin and DING Jia-long

Online:2018-11-14 Published:2018-11-14

摘要/Abstract

摘要： 针对布隆过滤器技术存在将不属于该集合的某元素误判为属于该数据集合(假阳性)和元素删除困难的问题,提出了CAM(内容可寻址存储器)来进行二级匹配。与直接将字符串存储在CAM的单级匹配模式不同,提出将布隆过滤器的k个哈希值存入CAM,从而判断某元素是否真正属于这个集合,从而达到精确匹配,且易于删除元素。对算法在Snort2.9规则库下的分析结果表明,相较于单级CAM查找,所设计的两级匹配模式在假阳率为0.01时,系统的资源占用减少5倍以上；本算法功耗降低10倍以上,能够减轻系统的负载,提高系统性能,适用于高速网络中字符串的检测。

Abstract: Because the technology of Bloom filter makes the element which does not belong to a set misjudge the element belonging to the set and element removal is difficult,this paper introduced CAM(Content Addressable Memory) for two exact matches.We proposed that the k hash values of the Bloom filter store in CAM,in order to determine whether an element belongs to this collection,and it is easy to remove elements.The results of the algorithm based on Snort2.9 rule database show that,compared with single-stage CAM seeking,in false positive rate of 0.01,the BF-CAM system reduces by more than 5-fold reduction in resource consumption,10 times in power consumption,and it can reduce the load of system,improve system performance,and adapt to detect strings in the high-speed networks.

Key words: Bloom filter,CAM,String matching,Hash function,Network security

王鹏超,杜慧敏,曹广界,杜琴琴,丁家隆. 基于布隆过滤器的精确匹配算法设计与实现[J]. 计算机科学, 2015, 42(Z6): 429-434. https://doi.org/

WANG Peng-chao, DU Hui-min, CAO Guang-jie, DU Qin-qin and DING Jia-long. Design and Implement of Exact Matching Algorithm Based on Bloom Filter[J]. Computer Science, 2015, 42(Z6): 429-434. https://doi.org/

参考文献

[1] Ruijie Network.DPI Technical Papers.http://wenku.baidu.com/ iew/aa73eac66137ee06ef f91879.html.2010.3
[2] Tuck N,Sherwood T,Calder B,et al.Deterministic memory- efficient string matching algorithms for intrusion detection[C]∥ Twenty-third AnnualJoint Conference of the IEEE Computer and Communications Societies(INFOCOM 2004).IEEE,2004,4:2628-2639
[3] Introduction to Snort.http://www.snort.org/docs/
[4] Song H,Dharmapurikar S,Turner J,et al.Fast hash table lookup using extended bloom filter:an aid to network processing[J].ACM SIGCOMM Computer Communication Review,ACM,2005,35(4):181-192
[5] Mitzenmacher.Compressed bloom filters[J].IEEE/ACM Trans-actions on Networking(TON),2002,10(5):604-612
[6] Peir J K,Lai S C,Lu S L,et al.Bloom filtering cache misses for accurate data speculation and prefetching[C]∥Proceedings of the 16th International Conference on Supercomputing.ACM,2002:189-198
[7] Bloom B H.Space/time trade-offs in hash coding with allowable errors[J].Communications of the ACM,1970,13(7):422-426
[8] Mitzenmacher M.Compressed bloom filters[J].IEEE/ACMTransactions on Networking,2002,10(5):604-612
[9] 谢鲲.布鲁姆过滤器查询算法及其应用研究 [D].长沙:湖南大学,2007
[10] Tan J S,Kuang Z,Yang G.Bloom filter based frequent patterns mining over data streams [C]∥2012 International Conference on Graphic and Image Processing.International Society for Optics and Photonics,2013:87685V-87685V-7
[11] 徐欣,李宗华,卢启中,等.基于FPGA的内容可寻址存储器研究设计与应用[J].国防科技大学学报,2001,23(5):69-73
[12] Guo R,Delgado-Frias J G.IP Routing table compaction andsampling schemes to enhance TCAM cache performance[J].Journal of Systems Architecture,2009,55(1):61-69
[13] Kim Y D,Ahn H S,Kim S,et al.A high-speed range- matching TCAM for storage-efficient packet classification[J].IEEE Transactions on Circuits and Systems I:Regular Papers,2009,56(6):1221-1230
[14] Chen Y,Oguntoyinbo O.Power efficient packet classification using cascaded bloom filter and off-the-shelf ternary CAM for WDM networks[J].Computer Communications,2009,32(2):349-356
[15] Kanizo Y,Hay D,Keslassy I.Access-efficient balanced Bloom filters[J].Computer Communications,2013,36(4):373-385
[16] AbuHmed T,Mohaisen A,Nyang D H.A survey on deep packet inspection for intrusion detection systems[J].Magazine of korea Telecommunication Society,2007,24(11):25-36
[17] McLaughlin K,O’Connor N,Sezer S.Exploring CAM design for network processing using FPGA technology [C]∥International Conference on Internet and Web Applications and Services/ Advanced International Conference on Telecommunications,2006(AICT-ICIW’06).IEEE,2006:84-84
[18] 田耘,徐文波.Xilinx FPGA 开发实用教程[M].北京:清华大学出版社,2008

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed