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

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

作　　者：李林[1] 卢显良[1] 

机构地区：[1]电子科技大学计算机学院,成都610054

出　　处：《北京邮电大学学报》2006年第5期111-114,124,共5页Journal of Beijing University of Posts and Telecommunications

基　　金：国家信息产业部电子发展基金项目

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

关 键 词：规则冲突 元组空间搜索 安全漏洞 

分 类 号：TP393.08[自动化与计算机技术—计算机应用技术]