(19)中华 人民共和国 国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202111421577.6 (22)申请日 2021.11.26 (71)申请人 哈尔滨工程大 学 地址 150001 黑龙江省哈尔滨市南岗区南 通大街145号哈尔滨工程大学科技处 知识产权办公室 (72)发明人 刘凌灼　王武辉　王祥　王宝宝　 吴昊　丁一　刘苹　陈森　董露　 (51)Int.Cl. G06F 16/901(2019.01) H04L 9/40(2022.01) (54)发明名称 一种基于B+树和位图索引融合树的冲突检 测方法 (57)摘要 本发明属于索引查找和冲突检测技术领域， 具体涉及一种基于B+树和位图索引融合树的冲 突检测方法。 本发明将网络安全设备的七元组策 略建立成一棵融合， 若不存在重叠属性， 则可 以 通过只比较一个属性就能快速确定是否有存在 与待插入策略冲突的策略， 解决了在策略冲突中 的一致性检测无法快速提高时效性和准确性的 问题。 采用B+树和位图索引的融合模型， 可以快 速比较新插入 策略与现有策略的七 元组属性， 避 免了将所有的属性都比较一遍。 本发明通过B+树 和位图索引的融合模型把策略的七元组进行划 分， 使得模型能更加快速地确定当前策略的位 置， 从而达到更准确更快捷的策略冲突检测效 果。 权利要求书1页 说明书4页 附图1页 CN 114168800 A 2022.03.11 CN 114168800 A 1.一种基于B+树和位图索引融合 树的冲突检测方法， 其特 征在于， 包括以下步骤： 步骤1： 在多种安全设备中提取大量的由协议、 源IP、 目的IP、 源端口、 目的端口、 时间、 动作构成的七元组， 将这些七元组整理为后续冲突检测训练所需的策略树； 步骤2： 当新增一条策略时， 定义待插入策略为x， B+树当前的根结点为root， 确定插入 的位置； 步骤2.1： 先判断root结点是否已满， 每个结点最多只能包含2*M –1个策略； 如果根节点 已经满了则生 成一个新结点node， 作为树新的根结点， 将r oot作为一个结点加入到node中； 其中， M是B+树的阶； 步骤2.2： 若root结点中已经无法在放下更多的策略， 则使用划 分子树的方法， 将root 结点中的策略分成两部分， 将前半部分的策略放入到一个新的结点中， 然后将这个结点也 加入到新的根节点中； 步骤2.3： 将策略x插入到不满的根节点中， 首先判断当前结点是否是叶子结点； 如果不 是叶子结点， 就将待插入策略x与当前结点中的所有 策略从最后一个开始比较， 一旦找到一 个比当前策略小的结点， 就先判断这个结点是否已经满了， 如果满了则直接划分子孩子， 然 后再比较当前策略应该插入到哪个子孩子中； 如果当前策略比前一半策略要大， 则递归比 较后一个子树是否是叶子结点； 如果已经是叶子结点， 并且当前结点不满， 因为如果满了， 则就会在判断父节点时就会将当前 结点分成两个子树， 对此确定插 入的位置； 步骤3： 划分后， 按照顺序自底向上做索引， 自顶向下进行插入操作； 通过融合树的算法 模型， 对新插 入的策略进行冲突检测； 步骤3.1： 将当前插入的策略与当前结点中的策略进行比较； 先对协议这个属性进行位 图索引， 相当于把B+树做纵向划分， 确定当前 策略所在的融合 树范围； 步骤3.2： 再比较源IP的大小， 如果两个源IP相同则比较目的IP的大小， 如果目的IP也 相同则比较源端口 的大小以此类 推； 步骤4： 通过比较七元组的各个属性之间的关系， 确定是否存在冲突， 若存在则是什么 样的冲突类型； 最后比较到最后一个属性动作则说明当前策略和比较策略至少有一部 分相 同的信息， 如果动作相同则是冗余冲突； 如果动作不同， 则又分成三种冲突： 泛化冲突， 覆盖 冲突和关联冲突。权　利　要　求　书 1/1 页 2 CN 114168800 A 2一种基于B+树和位图索引融合树的冲突检测方 法 技术领域 [0001]本发明属于索引查找和 冲突检测技术领域， 具体涉及一种基于B+树和位图索引融 合树的冲突检测方法。 背景技术 [0002]由于在工控网络下， 安全设备数量、 种类众多， 各类安全策略描述方法各不相同， 当对全网安全策略进行统一调整时， 造成安全管理员对安全策略配置所需专业知识要求 高， 工作量大， 易出错。 同时， 安全策 略可能涉及多种安全设备、 主机、 服务器、 网络设备等， 对网络连通性、 应用可用性等可能存在复杂的影响。 由于通信数据量的庞大， 安全策略的数 量也会急剧增长， 为了保障安全策略的一致性， 需要对安全策略的冲突进行有效和快速地 检测， 以便对检测出来的冲突进行消 解， 从而不论是在新增安全策略或是处理安全策略执 行的反馈结果， 都能有利于对安全策略进 行智能优化有效防止冲突， 能快速、 准确地检测出 类型策略冲突， 保证网络的安全。 发明内容 [0003]本发明的目的在于提供一种基于B+树和位图索引融合 树的冲突检测方法。 [0004]一种基于B+树和位图索引融合 树的冲突检测方法， 包括以下步骤： [0005]步骤1： 在多种安全 设备中提取大量的由协议、 源IP、 目的IP、 源端口、 目的端口、 时 间、 动作构成的七元组， 将这些七元组整理为后续冲突检测训练所需的策略树； [0006]步骤2： 当新增一条策略时， 定义待插入策略为x， B+树当前的根结点为root， 确定 插入的位置； [0007]步骤2.1： 先判断root结点是否已满， 每个结点最多只能包含2*M –1个策略； 如果根 节点已经满了则生成一个新结点node， 作为树新的根结点， 将root作为一个结点加入到 node中； 其中， M是B+树的阶； [0008]步骤2.2： 若root结点中已经无法在放下更多的策略， 则使用划分子树的方法， 将 root结点中的策 略分成两部分， 将前半部分的策略放入到一个新的结点中， 然后将这个结 点也加入到新的根节点中； [0009]步骤2.3： 将策略x插入到不满的根节点中， 首先判断当前结点是否是叶子结点； 如 果不是叶子结点， 就将待插入策略x与当前结点中的所有策略从最后一个开始比较， 一旦找 到一个比当前策略小的结点， 就先判断这个结点是否已经满了， 如果满了则直接划分子孩 子， 然后再比较当前策略应该插入到哪个子孩子中； 如果当前策略比前一半策略要 大， 则递 归比较后一个子树是否是叶子结点； 如果已经是叶子结点， 并且当前结点不满， 因为如果满 了， 则就会在判断父节点时就会将当前 结点分成两个子树， 对此确定插 入的位置； [0010]步骤3： 划分后， 按照顺序自底向上做索引， 自顶向下进行插入操作； 通过融合树的 算法模型， 对新插 入的策略进行冲突检测； [0011]步骤3.1： 将当前插入的策略与当前结点中的策略进行比较； 先对协议这个属性进说　明　书 1/4 页 3 CN 114168800 A 3