DP-Auditorium：用于审计差分隐私的灵活库

差分隐私（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-Auditorium

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和期望的样本数量n，这些样本由在D上计算的机制输出。此外，我们为测试器和数据集查找器提供了灵活的包装器，允许实践者实现自己的测试和数据集搜索算法。

关键结果

我们在具有不同输出空间的五个私有和九个非私有机制上评估DP-Auditorium的有效性。对于每个属性测试器，我们使用不同的ε值在固定数据集上重复测试十次，并报告每个测试器识别隐私错误的次数。虽然没有测试器 consistently outperform others，但我们识别了先前技术（HistogramPropertyTester）会遗漏的错误。注意，HistogramPropertyTester不适用于SVT机制。

我们还分析了TensorFlow中DP梯度下降算法（DP-GD）的实现，该算法计算私有数据上损失函数的梯度。为了保护隐私，DP-GD采用裁剪机制通过值G限制梯度的l2范数，然后添加高斯噪声。此实现错误地假设添加的噪声尺度为G，而实际上尺度为sG，其中s是正标量。这种差异导致近似DP保证仅对s大于或等于1的值成立。

我们评估属性测试器在检测此错误方面的有效性，并显示HockeyStickPropertyTester和RényiPropertyTester在识别隐私违规方面表现出卓越性能，优于MMDPropertyTester和HistogramPropertyTester。值得注意的是，这些测试器即使在s值高达0.6时也能检测到错误。值得强调的是，s=0.5对应于文献中常见的错误，即在考虑隐私预算ε时遗漏了因子2。DP-Auditorium成功捕获了此错误，如下所示。更多细节参见此处第5.6节。

为了测试数据集查找器，我们计算在发现隐私违规之前探索的数据集数量。平均而言，大多数错误在少于10次调用数据集查找器时被发现。随机化和探索/利用方法在查找数据集方面比网格搜索更高效。更多细节详见论文。

结论

DP是最强大的数据保护框架之一。然而，正确实现DP机制可能具有挑战性，并且容易产生无法通过传统单元测试方法轻易检测到的错误。统一的测试框架可以帮助审计员、监管机构和学者确保私有机制确实是私有的。

DP-Auditorium是一种通过函数空间上的散度优化来测试DP的新方法。我们的结果表明，这种基于函数的估计 consistently outperform previous black-box access testers。最后，我们证明与直方图估计相比，这些基于函数的估计器允许更好的隐私错误发现率。通过开源DP-Auditorium，我们旨在为新的差分隐私算法的端到端测试建立标准。

致谢

此处描述的工作是与Andrés Muñoz Medina、William Kong和Umar Syed共同完成的。我们感谢Chris Dibak和Vadym Doroshenko为我们库提供的有用工程支持和接口建议。