一种基于位向量交集运算的规则冲突检测算法

An Algorithm for Detecting Filters Conflicts Based on the Intersection of Bit Vectors

无论从报文分类算法自身还是从安全角度,规则冲突检测都是一个重要的研究课题.而目前常用的冲突检测算法效率较低.针对这一情况,在ASBV算法基础之上,提出了一种高效的冲突检测算法DBBV.同ASBV算法类似,DBBV算法也采用了分治思想和位向量技术.但与ASBV算法不同,在每一维规则分量处理过程中,DBBV算法只需要进行一次位向量交集运算,而ASBV算法需要进行多次位向量并集运算;DBBV算法支持以范围形式表示的规则集,而ASBV算法只支持以前缀形式表示的规则集.对DBBV算法的正确性进行了证明,测试表明其检测速度快于ASBV算法.

Detection of conflicts among filters is an important issue for packet classification and network security. On the one hand, to reduce the time spent on packet classification, a certain algorithm for detecting filters conflicts should be applied to find out all conflicting filters during the preprocessing phase and the update phase. On the other hand, because of the complexity of firewall filters, when firewall administrators add a filter, the newly added filter may conflict with the existing ones. This may lead to security vulnerabilities. Thus a certain algorithm for detecting filters conflicts should also be applied to find out all the existing filters conflicting with the new filter. Several algorithms for detecting conflicts have already been proposed but most of them are of poor performance or set restrictions on filters. Presented in this paper is an algorithm named DBBV for detecting filters conflicts, which is based on ASBV. Similar to ASBV, DBBV employs a divide-and-conquer method and bit vectors. Different from ASBV, DBBV needs only to calculate the intersection of bit vectors once in the course of every dimensional processing, while ASBV needs to compute the union of bit vectors many times. Also, DBBV does not set any restrictions on filters, while ASBV limits every field of filters to be a prefix. Experiments show that the performance of DBBV is better than that of ASBV.