(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202211131682.0 (22)申请日 2022.09.15 (71)申请人 浙江大学 地址 310058 浙江省杭州市西湖区余杭塘 路866号 (72)发明人 周政演　罗佳昱　吕靖雯　吴春明　 (74)专利代理 机构 杭州求是专利事务所有限公 司 33200 专利代理师 邱启旺 (51)Int.Cl. G06F 9/50(2006.01) (54)发明名称 一种基于可编程交换机的差分隐私大数据 处理方法 (57)摘要 本发明公开了一种基于可编程交换机的差 分隐私大数据处理方法， 本发明方法(1)利用线 速数据包处理ASIC流水线加速差分隐私的计算， 显著减少CP U周期的消耗； (2)通过聚合网络流量 并除去不必要的操作减少网络流量开销； (3)通 过可编程交换机自动化隐私审计。 本发明在网内 部署差分隐私系统， 加速差分隐私计算， 提高CP U 吞吐量， 减少网络流 量和隐私审计的开销。 权利要求书2页 说明书5页 附图4页 CN 115480917 A 2022.12.16 CN 115480917 A 1.一种基于可编程交换机的差分隐私大 数据处理方法， 其特 征在于， 包括以下步骤： 步骤一： 收集每一数据的键值对信息， 并逐一检查收集的每一数据的键值对信息是否 在预定义范围内； 步骤二： 在可编程交换机控制平面生成一组随机分布的噪声值， 并将其预加载到可编 程交换机的数据平面的有状态内存中； 然后生成一个随机数， 从该随机数索引的有状态内 存中采样噪声； 将采样的噪声加入到步骤一处理获得的尚未添加噪声的数据中， 获得满足 差分隐私的数据并转 发至规约器， 规约器对其中不在预定义范围内的数据用预定义范围的 平均值替换对应数据， 所有数据聚合后输出 结果。 2.根据权利要求1所述的方法， 其特 征在于， 所述 步骤一包括以下子步骤： (1.1)在可编程交换机的数据平面部署CM ‑sketch算法， 收集全部基于映射器提取的每 一数据的键值对信息； (1.2)逐一检查收集的每一数据的键值对信息是否在预定义范围内， 若在预定义范围 内， 继续执行步骤二； 若超出预定义范围， 则基于哈希表或精确表检查该数据是否第一次出 现， 若是第一次出现， 则交换机将该超 出预定义范围的数据的键汇集到哈希表或精确表中， 继续执行步骤二； 否则， 丢弃 该数据。 3.根据权利要求2所述的方法， 其特 征在于， 所述 步骤(1.2)具体为： 在可编程交换机数据平面创建一张 哈希表和一张精确 表， 逐一检查收集的每一数据的 键值对信息是否在预定义范围内， 若在预定义范围内， 继续执行步骤二； 若超出预定义范 围， 则基于哈希表或精确表检查该数据是否第一次出现， 若 是第一次出现， 则哈希表在O(1) 的时间复杂度内记录键， 如果存储时发生哈希冲突， 则将该键上报可编程交换机控制平面， 可编程交换机控制平面将这些冲突的键插 入到精确表中,继续执 行步骤二。 4.根据权利要求1所述的方法， 其特 征在于， 所述 步骤二包括以下子步骤： (2.1)在可编程交换机控制平面中生成一组随机分布的噪声值； (2.2)将生成的一组随机分布的噪声值预加载到可编程交换机的数据平面的有状态内 存中； (2.3)基于数据的键和数据表查询每一数据是否被噪声扰动， 若数据表中存在该键， 即 该数据已被扰动， 则该数据被转发至规约器； 若数据表中不存在该键， 即该数据未被扰动， 则生成一个随机数， 从该随机数索引的有状态内存中采样噪声； 将采样的噪声加入到该数 据的值中， 再将该数据的键汇集到数据表中并转发该数据至规约器； 所述数据表包含全部 被扰动的数据的键 。 5.根据权利 要求4所述的方法， 其特征在于， 所述步骤(2.1)中， 所述一组随机分布的噪 声值为符合拉普拉斯分布的噪声值。 6.根据权利 要求4所述的方法， 其特征在于， 所述步骤(2.2)中， 所述有状态内存采用寄 存器数组的实现方式， 其中， 左移生成的每 个噪声值缩放 为整数再预加载到寄存器中。 7.根据权利要求4所述的方法， 其特征在于， 所述步骤(2.3)中， 在扰动数据 时， 对映射 器输出的数据的键值对移动相同比例， 并添加采样的移动后的噪声值到该移动相同比例的 数据的值中， 将添加噪声后的数据的键汇集到数据 表中之后转发至规约器， 其中， 转 发时将 移动的比例 封装在分组报头中， 报头也被进一步转发到规约器， 规约器将经过缩放且加噪 声的数据右移以恢复缩放比例， 规约器对其中不在预定义范围内的数据用预定义范围的平权　利　要　求　书 1/2 页 2 CN 115480917 A 2均值替换对应数据， 所有数据聚合后输出 结果。 8.根据权利要求1所述的方法， 其特征在于， 还包括运用布隆过滤器记录输出键值和映 射器的依赖关系， 通过查询所有输出键的依赖关系计算隐私预算。 9.根据权利要求8所述的方法， 其特征在于， 运用布隆过滤器记录输出键和映射器的依 赖关系， 通过查询所有输出键的依赖关系计算隐私预算具体为： a、 将布隆过滤器划分为多个分区与每个映射器对应， 记录各映射器输出过的键， 即键 与映射器的依赖关系； b、 运用布隆过 滤器统计各分区相应的映射器输出的键数量； c、 根据获得的各分区相应的映射器输出的键数量的最大值计算隐私预算。权　利　要　求　书 2/2 页 3 CN 115480917 A 3