(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202111563899.4 (22)申请日 2021.12.20 (71)申请人 中盈优创资 讯科技有限公司 地址 200000 上海市嘉定区安亭镇杭桂 路 1112号10层10 04室-4 (72)发明人 王磊　 (74)专利代理 机构 上海嘉蓝专利代理事务所 (普通合伙) 31407 专利代理师 金波 (51)Int.Cl. H04L 9/40(2022.01) G06F 16/2453(2019.01) G06F 16/22(2019.01) (54)发明名称 一种基于Trie树实现DDOS用户匹配的方法 及装置 (57)摘要 本发明公开一种基于Trie树实现DDOS用户 匹配的方法及装置， 其中， 该方法包括： 管理系统 通过web界面手动录入用户信息和用户相对应的 IP地址信息； 管理系统同步将信息下 发到下游检 测设备中,检测系统收到信息后， 将IP地址转变 成二进制数据,通过Trie树算 法， 生成IP节点， 同 时生成id信息对应的二叉Trie树； 路由器发送 Netflow报 文到DDOS检测系统， 解码数据报文， 获 取目的IP地址信息； DDOS检测系统根据生成的 Trie树进行匹配， 匹配到地址后， 获取当前报文 IP归属CIDR 网段的用户信息； 检测系统通过Trie 数据算法获取的用户信息向下游匹配发送， 丢弃 掉没有匹配的报文数据。 该方法及装置基于Trie 树技术对大数据量的报文进行用户IP匹配， 实现 高性能用户数据匹配,提升数据处 理性能。 权利要求书1页 说明书6页 附图3页 CN 114465757 A 2022.05.10 CN 114465757 A 1.一种基于Trie树实现D DOS用户匹配的方法， 其特 征在于， 该 方法包括： S01、 管理系统通过web界面手动录入用户信息和用户相对应的IP地址信息； S02、 管理系统同步将IP地址信息下发到下游检测设备中,检测系统收到信息后， 将IP 地址转变成二进制数据,通过Trie树算法， 生成IP节点， 同时生成id信息对应的二叉Trie 树； S03、 路由器发送Netflow报文到DDOS检测系统后， 解码数据报文， 得到解析后的报文后 获取目的IP地址信息； S04、 DDOS检测系统根据生成的Trie树进行匹配， 匹配到地址后， 获取报文IP归属CIDR 网段用户信息； S05、 检测系统通过Trie数据算法获取的用户信息向下游匹配发送， 丢弃掉没有匹配的 报文数据。 2.根据权利要求1所述的基于Trie树实现DD OS用户匹配的方法， 其特征在于， 所述IP地 址信息包括 IP对应的CIDR地址 。 3.根据权利要求1所述的基于Trie树实现DDOS用户匹配的方法， 其特征在于， 所述S04 中DDOS检测系统根据生成的Trie树进行最长匹配。 4.一种基于Trie树实现D DOS用户匹配的装置， 其特 征在于， 该装置包括： 信息录入模块101、 管理系统通过web界面手动 录入用户信息和用户相对应的IP地址信 息。 IP地址转换模块、 管理系统同步将IP地址信息下发到下游检测设备中,检测系 统收到 信息后， 将IP地址转变成二进制数据,通过Trie树算法， 生成IP节点， 同时生成id信息对应 的二叉Trie树。 解码模块、 路由器发送Netflow报文到DDOS检测系统后， 解码数据报文， 得到解析后的 报文后获取目的IP地址信息 。 Trie树匹配模块、 DD OS检测系统根据 生成的Trie树进行匹配， 当匹配到某个地址后， 获 取当前报文IP归属CIDR网段 所属目的用户信息 。 下游匹配模块、 检测系 统通过Trie数据算法获取的用户信息继续向下游匹配发送， 并 丢弃掉没有匹配的报文数据。 5.根据权利要求4所述的基于Trie树实现DD OS用户匹配的装置， 其特征在于， 所述IP地 址信息包括 IP对应的CIDR地址 。 6.根据权利 要求4所述的基于Trie树实现DDOS用户匹配的装置， 其特征在于， 所述Trie 树匹配模块中D DOS检测系统根据生成的Trie树进行最长匹配。 7.一种计算机设备， 包括存储器、 处理器及存储在存储器上并可在处理器上运行的计 算机程序， 其特 征在于， 所述处 理器执行所述计算机程序时实现权利要求1 ‑3所述方法。 8.一种计算机可读存储介质， 其特征在于， 所述计算机可读存储介质存储有执行权利 要求1‑3所述方法的计算机程序。权　利　要　求　书 1/1 页 2 CN 114465757 A 2一种基于 Trie树实现D DOS用户匹配的方 法及装置 技术领域 [0001]本发明涉及网络安全领域， 尤其是一种基于Trie树实现DDOS用户匹配的方法及装 置。 背景技术 [0002]目前对于ddos攻击目的用户的匹配都是基于目的IP的匹配， 如果用户包含众多的 IP是基于CIDR形式的， 现阶段匹配都是基于IP拆 分后将IP拆 分后存储与数据库中的数据进 行比较， 匹配效率随着数据增 加而而逐渐下降， 服 务性能严重降低。 [0003]现有的ddos攻击检测中， 都是需要预制用户所属CIDR格式的IP同步到检测系统 中， 用户归属IP大部分都是基于掩码形式的， 检测系统接收到用户IP后， 将解析用户IP段， 将拆分后的IP存储到数据库中， 当系统收到用户netflow流量报文后解析目的IP， 将解析后 的目的IP在数据库中匹配归属用户， 如果用户量大量增加或者用户流量都大幅增加后， 该 方法匹配用户的效率明显降低， 系统响应会受到 很大的影响。 [0004]CIDR： 用于给用户分配IP 地址以及在互联网上有效地路由IP数据包的对IP 地址进 行归类的方法。 [0005]trie树， 又称前缀树或字典树， 是一种有序树， 用于保存关联数组， 其中的键通常 是字符串。 与二叉查找树不同， 键不是直接保存在节点中， 而是由节点在树中的位置决定。 一个节点的所有子孙都有相同的前缀， 也就是这个节点对应的字符串， 而根节点对应空字 符串。 一般情况下， 不是所有的节点 都有对应的值， 只有叶子节点和部 分内部节点所对应的 键才有相关的值。 [0006]trie树中的键通常是字符串， 但也可以是其它的结构。 trie树的算法可以很容易 地修改为处理其它结构的有序序列， 比如一串数字或者形状的排列。 比如， bitwise  trie中 的键是一串位元， 可以用于表示整数或者内存地址 。 [0007]trie树的基本性质： [0008]1、 根节点 不包含字符， 除根节点以外每 个节点只包 含一个字符。 [0009]2、 从根节点到某一个节点， 路径上 经过的字符连接起 来， 为该节点对应的字符串。 [0010]3、 每个节点的所有子节点包 含的字符串不相同。 [0011]trie树的优点： 可以最大限度地减少无谓的字符串比较， 故可以用于词频统计和 大量字符串排序。 [0012]trie树跟哈希 表比较： [0013]1、 最坏情况时间 复杂度比hash表好 [0014]2、 没有冲突， 除非一个key对应多个值(除key外的其 他信息) [0015]3、 自带排序功能(类似Radix  Sort)， 中序遍历t rie可以得到排序。 发明内容 [0016]为解决人工进行网络故障定位存在的上述问题， 本发明提供一种基于Trie树实现说　明　书 1/6 页 3 CN 114465757 A 3