(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202111479997.X (22)申请日 2021.12.0 6 (71)申请人 北京大学 地址 100871 北京市海淀区颐和园路5号北 京大学 (72)发明人 杨仝　樊卓宸　吴钰晗　 (74)专利代理 机构 北京君尚知识产权代理有限 公司 11200 专利代理师 邱晓锋 (51)Int.Cl. H04L 9/40(2022.01) G06F 21/71(2013.01) (54)发明名称 一种实时查找持续且低频元素的方法、 APT 攻击检测方法和FRP检测方法 (57)摘要 本发明涉及一种实时查找持续且低频元素 的方法、 APT攻击检测方法和FRP检测方法。 该方 法建立基于Sketch的紧凑数据结构PISket ch， 其 第一部分是布隆过滤器， 第二部分是带有若干个 桶的哈希表； 第一部分查询某个元素是否第一次 出现在当前时间窗口， 第二部分根据第一部分的 查询结果计算每个元素的权重： 当该元素第一次 出现在当前时间窗口中时， 增加该元素在当前窗 口的权重作为奖励； 当该元素在同一个时间 窗口 中超过第二次出现时， 降低该元素的权重作为惩 罚； 提取总权重大于用户设置的阈值的元素作为 持续且低频性元素输出。 本发明实现了准确而高 效地查找持续且低频性元素， 在高处理速度的同 时只需要很小的数据结构内存占用， 能够用于 APT攻击检测和FRP检测等场景。 权利要求书2页 说明书6页 附图2页 CN 115529149 A 2022.12.27 CN 115529149 A 1.一种实时查找持续且低频 元素的方法， 其特 征在于， 包括以下步骤： 建立基于Sketch的紧凑数据结构， 其包括两部分， 第一部分数据结构是布隆过滤器， 第 二部分数据结构是 带有若干个桶的哈希 表； 第一部分数据 结构查询某个元素是否第 一次出现在 当前时间窗口， 第 二部分数据 结构 根据第一部 分数据结构的查询结果计算每个元素的权重： 当该元素第一次出现在当前时间 窗口中时， 增加该元素在当前窗口的权重作为奖励； 当该元素在同一个时间窗口中超过第 二次出现时， 降低该 元素的权重作为惩罚； 提取总权 重大于用户设置的阈值的元 素作为持续且低频性元 素输出。 2.根据权利要求1所述的方法， 其特征在于， 所述布隆过滤器由M个位和k个哈希函数组 成， 每当新的时间窗口开始时， 将布隆过滤器清空， 每次一个元素来时， 查询其是否第一次 到来， 如果是则将其插入到布隆过滤器中， 然后将结果传递给第二部分数据结构进行权重 计算； 所述哈希表是一个带有U个桶的哈希表， 根据第一部分数据结构的查询结果， 这些桶 对每个元素计算总权重， 并尽可能保留权重可能超过用户设置的阈值T的元素； 每个桶有p 个单元格， 每个单元格有三元组： 元素ID、 元素的总权重W和元素出现 的窗口数量N； 与该哈 希表对应的哈希函数h(.)将元 素随机映射到其中的一个桶。 3.根据权利要求2所述的方法， 其特征在于， 所述第 二部分数据 结构根据第 一部分数据 结构的查询结果计算每个元素的权重， 包括： 当一个元素第一次出现在给定的窗口中时， 给 该元素在当前窗口的权重Wi加上一个较大的初始值L作为奖励； 当该元素在同一个窗口中 超过第二次出现时， 对它的权重Wi减1作为惩罚； 所述布隆过滤器检查元素是否出现在当前 窗口中， 如果布隆过滤器报告为假， 说明该元素没有 出现在当前窗口中， 则将该元素插入布 隆过滤器中， 并对该窗口执行两个操作： 初始化在该窗口的权重Wi＝L和增加窗口数N＝N+ 1； 否则， 表 示当前窗口中已经出现了该元素， 将该元素对应的窗口的权重Wi减1， 即， Wi＝Wi‑ 1。 4.根据权利要求3所述的方法， 其特征在于， 采用以下步骤将元素映射到第 二部分数据 结构的哈希 表的桶Bh： 如果存在包含该元素的单元格， 直接 更新该单元格的字 段： 将Wi添加到总权重W中， 即， W ←W+Wi， 并将存储的窗口数量 N更新为当前的N； 如果在Bh中找不到该 元素并且Bh未满， 那么将该 元素存储在任意 一个空单 元格中。 将W设置为 Wi， 即， W←W+Wi。 此时： W＝L， N＝1； 如果Bh中没有一个单元格包含该元素并且Bh没有任何空单元格， 那么从Bh为该元素腾 出空间。 5.根据权利要 求4所述的方法， 其特征在于， 所述从Bh为该元素腾出空间， 是选 择一个元 素m， 其权重在Bh的所有元素中最小， 然后使用替换策略驱逐Bh中权重最小的元素m； 所述替 换策略包括： 每 当发生替换时， 将其权重W ’减1， 如果W ’小于0， 则表 示替换成功， 然后驱逐m， 该元素占据m的位置， W设置为 Wi+1， N设置为1； 如果 替换不成功， 则该 元素离开。 6.根据权利要求5所述的方法， 其特征在于， 所述替换策略为概率形式的替换， 即 以概 率P将最小权 重元素m的权重W’减1， 其中P由用户自定义， 保证其在(0,1)之间。 7.一种APT攻击检测方法， 其特征在于， 将需要筛查的原始数据流作为输入， 采用权利 要求1～6中任一权利要求所述方法查找得到持续性和低频性的元素， 即为疑似的APT攻击权　利　要　求　书 1/2 页 2 CN 115529149 A 2流。 8.一种FRP检测方法， 其特征在于， 将需要筛查的原始数据流作为输入， 采用权利要求1 ～6中任一权利要求所述方法查找得到持续 性和低频性的元 素， 即为疑似的FRP。 9.一种电子装置， 其特征在于， 包括存储器和 处理器， 所述存储器存储计算机程序， 所 述计算机程序被配置为由所述处理器执行， 所述计算机程序包括用于执行权利要求 1～8中 任一权利要求所述方法的指令 。 10.一种计算机可读存储介质， 其特征在于， 所述计算机可读存储介质存储计算机程 序， 所述计算机程序被 计算机执 行时， 实现权利要求1～8中任一权利要求所述的方法。权　利　要　求　书 2/2 页 3 CN 115529149 A 3