针对Shuffle-DP投毒攻击的检测与恢复方法——OceanBase联合成果被数据库顶会录用

混洗差分隐私Shuffle-DP已成为隐私保护去中心化数据分析的领先范式吸引了学术界和工业界的广泛关注。然而现有 Shuffle-DP 协议普遍依赖一个强假设所有用户诚实执行协议。现实场景往往存在恶意用户投毒攻击者他们既可削弱甚至破坏隐私保护如少加或不加噪声也可破坏分析结果的可用性如注入大量虚假消息使聚合结果失去意义。针对 Shuffle-DP 下的投毒攻击防御已有工作或仅能“检测”攻击而无法“恢复”有效结果或局限于频数估计等单一任务缺乏通用性。本论文提出首个适用于所有并集保持查询的通用防御框架在 Shuffle-DP 下既检测投毒攻击又从被污染消息中恢复有意义的分析结果。想了解 OceanBase 在产品技术核心竞争力及不同行业解决方案和最佳实践可下载《OceanBase 一体化分布式数据库》核心理念从“全诚实用户”到“存在投毒攻击者”在 Shuffle-DP 中消息经混洗后匿名分析者无法区分其来自诚实用户还是攻击者。攻击者主要有两类行为破坏隐私少加或不加噪声削弱整体隐私保护、破坏效用发送远超协议预期的消息数量污染聚合结果使误差极大甚至失去意义。本工作的目标是在“不改变仅依赖可信混洗、不依赖用户身份”的前提下设计通用框架实现将任意 Shuffle-DP 协议改造成具备投毒攻击防御能力的版本无攻击时误差与原始协议渐近等价存在攻击者时误差仅增加多对数因子恢复有意义的查询结果通信与计算开销可控。核心技术层次化 Shuffle-DPHSDP一个自然的防御思路是将每个用户隔离各自独立执行一次 Shuffle-DP 协议分析者分别检查每个用户的输出是否合理再将有效结果聚合。这样攻击者最多只能影响自身对应的那一份输出防御效果显著。然而该方案的代价是将 n 个独立加噪结果直接相加误差随 n 线性增长远超原始协议的水平实用性大打折扣。误差过大的根本原因在于完全隔离用户放弃了 Shuffle-DP 通过混洗聚合噪声、摊销误差的核心优势。为此论文提出层次化 Shuffle-DPHSDP在保持防御能力的同时恢复这一优势。HSDP 将 n 个用户组织成深度为 O(log n) 的二叉树最底层每个叶子对应一个用户逐层两两合并直至顶层覆盖全体用户。每个节点对应的用户组在组内联合执行一次 Shuffle-DP 协议从而在组内实现噪声摊销。检测与恢复自底向上进行对每个内部节点分析者将该节点的聚合结果与其两个子节点结果之和进行比较若偏差超过设定阈值则标记为“被污染”并用子节点的有效结果递归替代。由于攻击者至多影响树中从叶子到根的一条路径误差最多跨越 O(lo g n)层传播最终误差相比原始协议仅增加 O(polylog n)因子达到多对数级别的目标。针对“攻击者少加噪声”的隐私破坏攻击框架通过让诚实用户按参与规模对噪声进行缩放补偿确保整体仍满足 (ε,δ)-DP。图 1: HSDP 算法图示HSDP 的通信开销相比原始协议增加了 O(polylog n) 倍每个用户需参与 O(log ⁡n) 层 shuffle-DP 协议隐私预算需要按照 O(log ⁡n) 分割此外在规模较小的底层分组中为保证隐私每用户须贡献更多噪声消息通信代价较高。为此论文提出对层次结构进行优化将底层的分组规模从单用户扩大至 λ减少需要独立执行协议的层数从而显著降低底层的通信开销。通过适当选取 λ可在误差与通信开销之间取得更优的平衡—— λ 越大通信越高效但被攻击者破坏的底层分组规模也相应增大对误差略有影响。论文给出了 λ 的最优选取策略并证明优化后每用户消息数可进一步压缩同时误差保证不变。通用框架一键将任意 Shuffle-DP 协议升级为鲁棒版本在层次化结构之上论文表明给定任意针对并集保持查询的 Shuffle-DP 协议均可通过本框架转化为抗投毒攻击的版本。随机器、混洗器、分析器均可作为黑盒复用框架仅在外层增加“多层级调用 检测与恢复”逻辑。适用查询类型包括比特计数bit counting、求和summation、频数估计frequency estimation、区间计数range counting等所有并集保持查询论文在比特计数、求和与频数估计上给出了具体实例与误差上界并与现有最优协议对比见下表 / 图2。框架可扩展至常数 k 个攻击者误差增加约 k 倍因子并给出进一步通信优化思路。本工作首次在 Shuffle-DP 下为所有并集保持查询提供“检测 恢复”的通用防御方案且不依赖盲签名等额外密码学假设适用范围大于仅支持频数估计且带强约束的已有工作。表 1协议对比表性能与实验成果论文在合成数据与真实数据集上对三种典型并集保持查询比特计数、求和、频数估计进行系统评估将本框架与 GKMPS、BBGN、LWY、CSUZZ、CZ 等现有协议对比。无攻击时本框架与对应原始协议相对误差处于同一量级验证“渐近等价”的理论结论。有攻击时原始协议在投毒攻击下相对误差可飙升至数百甚至失效而本框架能将相对误差稳定在较低水平如 0.1%–1% 量级成功恢复可用结果。在 Uniform、Zipf、Gauss 等分布以及 Adult、SF_Sal、BR_Sal、AOL 等真实数据上本框架在有无攻击两种设定下均表现稳定随用户数 n、隐私预算 ε、攻击者数量 k 等参数的变化与理论分析一致。通信方面每用户消息数与每条消息比特数较原协议呈多对数倍增加与理论分析相符具备实际可部署性。上述结果表明本框架在保持隐私与通信效率的前提下能有效防御 Shuffle-DP 下的投毒攻击并恢复高可用的分析结果。表 2: 各协议在模拟数据集上的实验对比结果表 3: 各协议在现实数据集上的实验对比结果小结与展望本论文针对 Shuffle-DP 模型中恶意用户发起的投毒攻击提出首个面向所有并集保持查询的通用防御框架。通过层次化 Shuffle-DP 设计在实现“检测 恢复”的同时达到无攻击时与原始协议渐近等价的误差、存在常数个攻击者时仅多对数级别的误差增长。实验在合成与真实数据上验证了框架的有效性、通用性与效率。论文同时指出若干开放问题与后续方向能否将防御框架推广到非并集保持查询如何在层次化结构下进一步借鉴现有工作降低通信开销等。这些问题的解决将进一步提升 Shuffle-DP 在开放、不可信用户环境下的可用性与安全性。立即试用 OceanBase 企业版体验国产数据库能力180 天免费试用零门槛开通