基于元组空间搜索的规则集冲突检测算法

当添加防火墙规则时，新规则可能会与已有规则发生冲突，造成潜在的安全漏洞。要避免此漏洞产生，管理员必须正确地确定新规则插入的位置，找出与新规则相冲突的所有规则。目前冲突检测算法时间复杂度为O(dN)，效率低下，为此提出了一种基于元组空间搜索的规则集冲突检测算法。该算法不仅能找出与新规则相冲突的所有规则，且时间复杂度降为O(㏒N+N/w)，可有效帮助管理员正确确定新规则插入位置，避免了漏洞的产生。

A Detection Algorithm for Rule Set Conflicts Based on Tuple Space Search

Adding a new firewall rule often conflicts with the existed ones,which leads to security vulnerabilities.In order to avoid such vulnerabilities,firewall administrators have to determine an appropriate position in the firewall rule set to be inserted,and identify all the rules conflicting with the new rule in advance.The time complexity of the current conflicts detection algorithm for firewall rule set is O(dN),which makes its performance very poor.A new algorithm for detecting firewall rule set conflicts based on tuple space search is presented not only to find all the rules conflicting with the new rule,but also reduce the time complexity as O(lgN+N/w).So it can efficiently help administrators determine an appropriate insertion position of the new rule to avoid vulnerabilities.