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

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.