Efficient Algorithm for Detecting Firewall Rule Conflict

摘要

Conflict detection algorithm in the traditional firewall rules, increase when the number of firewall rules to a certain extent, the probability of conflict will increase, which will match the packets cause miscarriage of justice. In order to be able to quickly detect firewall rules in the conflict, this paper presents an improved rule of conflict detection algorithms (DBBV algorithm). The algorithm processes the rules on conflict detection using binary tree data structure, and one-dimensional intersection operation after operation, makes rules simpler to detect. Expression of flexibility in the rules, not due to a redundant operation, resulting in high time complexity. Through the analysis of algorithms, and verified by experiment, the algorithm efficiency significantly higher than traditional ASBV algorithm of conflict detection.