差异隐私(DP) 是随机机制的一种属性，可在处理和分析数据时限制任何个人用户信息的影响。DP 提供了一种强大的解决方案来解决人们对数据保护日益增长的担忧，使跨行业和政府应用（例如美国人口普查）的技术能够在不 损害个人用户身份的情况下实现。随着其采用率的提高，识别开发具有错误实现的机制的潜在风险非常重要。研究人员最近发现私有机制及其实现中的数学证明存在错误。例如，研究人员比较了六种稀疏向量技术 (SVT) 变体，发现其中只有两种真正满足了所声称的隐私保证。即使数学证明正确，实现该机制的代码也容易受到人为错误的影响。
然而，实用且高效的 DP 审计具有挑战性，这主要是由于机制固有的随机性和所测试保证的概率性质。此外，存在多种保证类型（例如纯 DP、近似 DP、Rényi DP和集中 DP），这种多样性增加了制定审计问题的复杂性。此外，考虑到所提出的机制的数量，调试数学证明和代码库是一项艰巨的任务。虽然在特定的机制假设下存在临时测试技术，但很少有人努力开发用于测试 DP 机制的可扩展工具。
为此，我们在“ DP-Auditorium：用于审计差异隐私的大型库”中引入了一个开源库，用于仅通过黑盒访问机制（即不了解机制的内部属性）来审计 DP 保证。DP-Auditorium 用 Python 实现，提供了一个灵活的接口，允许贡献者不断改进其测试能力。我们还引入了新的测试算法，该算法对 Rényi DP、纯 DP 和近似 DP 的函数空间执行散度优化。我们证明 DP-Auditorium 可以有效识别 DP 保证违规行为，并建议哪些测试最适合在各种隐私保证下检测特定错误。
DP 担保
DP 机制的输出是从满足确保用户数据隐私的数学属性的概率分布 ( M ( D )) 中抽取的样本。因此，DP 保证与概率分布对之间的属性紧密相关。如果在给定的发散度量下，由M在数据集D和相邻数据集D'上确定的概率分布（仅相差一个记录）无法区分，则该机制是差分隐私的。
例如，经典的近似 DP定义指出，如果M ( D)和M ( D' )之间e阶ε的曲棍球棒散度最多为δ ，则该机制为参数为 ( ε , δ ) 的近似 DP 。纯 DP 是近似 DP 的一个特例，其中δ = 0。最后，如果𝛼阶的Rényi 散度最多为ε（其中ε是一个较小的正值），则该机制被视为参数为 ( 𝛼 , ε)的Rényi DP 。在这三个定义中， ε不能互换，但直观上传达了相同的概念；ε值越大意味着两个分布之间的差异越大或隐私性越差，因为这两个分布更容易区分。
DP-礼堂
DP-Auditorium 由两个主要组件组成：属性测试器和数据集查找器。属性测试器从针对特定数据集评估的机制中抽取样本作为输入，旨在识别所提供数据集中的隐私保证违规行为。数据集查找器建议隐私保证可能失败的数据集。通过结合这两个组件，DP-Auditorium 可以 (1) 自动测试各种机制和隐私定义，以及 (2) 检测隐私保护机制中的错误。我们实现了各种私有和非私有机制，包括计算记录平均值的简单机制和更复杂的机制，例如不同的 SVT 和 梯度下降机制变体。
属性测试器确定是否存在证据来拒绝以下假设：两个概率分布P和Q之间的给定散度受正在测试的 DP 保证确定的预定预算的限制。它们从P和Q的样本中计算下限，如果下限值超过预期散度，则拒绝该属性。如果结果确实有界，则不提供任何保证。为了测试一系列隐私保证，DP-Auditorium 引入了三种新颖的测试器：(1) HockeyStickPropertyTester、(2) RényiPropertyTester 和 (3) MMDPropertyTester。与其他方法不同，这些测试器不依赖于被测试分布的显式直方图近似。它们依赖于曲棍球棒散度、Rényi 散度和最大均值差异(MMD) 的变分表示，这些表示能够通过对函数空间进行优化来估计散度。作为基准，我们实现了HistogramPropertyTester，这是一种常用的近似 DP 测试器。虽然我们的三个测试器采用类似的方法，但为简洁起见，我们在本文中重点介绍 HockeyStickPropertyTester。
给定两个相邻数据集D和D'， HockeyStickPropertyTester 会找到M ( D)和M ( D' ) 之间曲棍球棒散度的下限^ δ，该下限以高概率成立。曲棍球棒散度强制两个分布M ( D)和M ( D' ) 在近似 DP 保证下接近。因此，如果隐私保证声称曲棍球棒散度最多为δ，且^ δ > δ，则很有可能散度高于对D和D'的承诺，并且该机制无法满足给定的近似 DP 保证。下限^ δ 是作为曲棍球棒散度变分公式的经验和易处理的对应物计算得出的（有关更多详细信息，请参阅论文）。 ^ δ的准确度 随着从机制中抽取的样本数量的增加而增加，但随着变分公式的简化而降低。我们平衡这些因素以确保^ δ 既准确又易于计算。
数据集查找器使用黑盒优化来查找最大化^ δ （散度值δ的下限）的数据集D和D'。请注意，黑盒优化技术专门设计用于无法为目标函数推导梯度的设置。这些优化技术在探索和利用阶段之间振荡，以估计目标函数的形状并预测目标可以具有最优值的区域。相比之下，完整的探索算法（例如网格搜索方法）会在相邻数据集D和D'的整个空间中进行搜索。DP-Auditorium 通过开源黑盒优化库Vizier实现了不同的数据集查找器。
在新的机制上运行现有组件只需要将机制定义为 Python 函数，该函数接受数据数组D和由基于D计算的机制输出的所需样本数n。此外，我们为测试人员和数据集查找人员提供了灵活的包装器，使从业者能够实现自己的测试和数据集搜索算法。
主要结果
我们评估了 DP-Auditorium 在具有不同输出空间的五种隐私机制和九种非隐私机制上的有效性。对于每个属性测试器，我们使用不同的ε值在固定数据集上重复测试十次，并报告每个测试器识别隐私漏洞的次数。虽然没有一个测试器始终优于其他测试器，但我们会识别出以前的技术（HistogramPropertyTester）会遗漏的漏洞。请注意，HistogramPropertyTester 不适用于 SVT 机制。
每个属性测试人员发现所测试的非私有机制存在隐私侵犯的次数。NonDPLaplaceMean 和 NonDPGaussianMean 机制是用于计算平均值的拉普拉斯和高斯机制的错误实现。
我们还分析了TensorFlow 中DP 梯度下降算法(DP-GD) 的实现，该算法计算私有数据上的损失函数的梯度。为了保护隐私，DP-GD 采用一种裁剪机制，将梯度的l2 范数限制为一个值G，然后添加高斯噪声。此实现错误地假设添加的噪声的比例为G，而实际上，比例为sG，其中s是正标量。这种差异导致近似 DP 保证仅对大于或等于 1 的 s值成立。
我们评估了属性测试器在检测此漏洞方面的有效性，并表明 HockeyStickPropertyTester 和 RényiPropertyTester 在识别隐私侵犯方面表现出色，优于 MMDPropertyTester 和 HistogramPropertyTester。值得注意的是，即使s值高达 0.6，这些测试器也能检测到漏洞。值得强调的是，s = 0.5 对应于文献中常见的错误，即在考虑隐私预算ε时遗漏了两个因子。DP-Auditorium 成功捕获了此漏洞，如下所示。有关更多详细信息，请参阅此处的第 5.6 节。
使用 HistogramPropertyTester（左）和 HockeyStickPropertyTester（右）测试 DP-GD 时，估计不同s值的散度和测试阈值。
使用 RényiPropertyTester（左）和 MMDPropertyTester（右）测试 DP-GD 时，估计不同s值的散度和测试阈值
为了测试数据集查找器，我们计算了在发现隐私违规之前探索的数据集数量。平均而言，大多数错误都是在不到 10 次调用数据集查找器时发现的。随机化和探索/利用方法在查找数据集方面比网格搜索更有效。有关更多详细信息，请参阅论文。
结论
DP 是最强大的数据保护框架之一。然而，正确实施 DP 机制可能具有挑战性，并且容易出现使用传统单元测试方法无法轻易检测到的错误。统一的测试框架可以帮助审计人员、监管机构和学者确保私有机制确实是私有的。
DP-Auditorium 是一种通过函数空间上的散度优化来测试 DP 的新方法。我们的结果表明，这种基于函数的估计始终优于以前的黑盒访问测试器。最后，我们证明这些基于函数的估计器与直方图估计相比，可以更好地发现隐私漏洞。通过开源DP-Auditorium，我们旨在为新的差分隐私算法的端到端测试建立标准。
致谢
本文所述工作由 Andrés Muñoz Medina、William Kong 和 Umar Syed 共同完成。我们感谢 Chris Dibak 和 Vadym Doroshenko 为我们的库提供的有益工程支持和界面建议。
评论