基于节点共享计数型Bloom filter高效动态数据包过滤方案

Efficient dynamic packet filtering program based on shared-node counting Bloom filter

入侵防御系统（intrusion prevention system，IPS）中常用的包过滤方案大量消耗时间和空间，丢包率高，不能实现多过滤器并行处理。针对此问题，设计了一种新的过滤器方案，该方案在网络设备驱动层采用节点共享计数型bloom filter技术，通过改进哈希函数的集合，减少了位数组元素的碰撞率，实现了过滤规则的动态添加和删除。由元组空间法把过滤规则划分多个集合，在每个集合中创建不同的节点共享计数型Bloom filter位数组，并且优化搜索算法，进一步降低了位数组元素的碰撞率。通过在多核处理器中建立多个并行处理线程，实现了过滤的并行处理。实验结果表明，新的方案能够减少28％～31％的碰撞率和12％～19％的hash表的访问次数。

The ordinary packet filtering program used in an intrusion prevention system （IPS） consumes a tremendous amount of time and space that results in a larger packet loss rate and can not he achieved in parallel processing. This paper designs a new filtering program by adopting the shared-node counting bloom filter technology on the network device driver layer. The collision rate of the elements in bits group can be evidently decreased, and the free addition and deletion of dynamic filtering rules can be easily realized by improving the sets of hash functions. In each of the multi-rules sets, which is divided by tuple space, different shared-node counting Bloom filter bits groups are created. The search algorithm in tuple space is optimized and the collision rate of elements in bits group is further reduced. In the multi-core processors, filter processing can be executed in parallel through the establishment of a number of parallel processing threads. Experiment results show that the presented filtering program can reduce 28 %-31% of the collision rate and 12 %--19 % of the hash table visits.