DP-Auditorium: A flexible library for auditing differential privacy

差分隐私（DP）是一种随机化机制的性质，它能在处理和分析数据时限制任何单个用户信息的影响。DP 为应对日益增长的数据保护关切提供了稳健的解决方案，使跨行业的技术和政府应用（例如美国人口普查）能够在不损害个人用户身份的前提下得以实现。随着其采用率的提高，识别因实现缺陷而开发机制所带来的潜在风险变得十分重要。研究人员最近在隐私机制的数学证明及其实现中发现了错误。例如，研究人员比较了六种稀疏向量技术（SVT）变体，发现六种中只有两种真正满足了所声称的隐私保证。即使数学证明是正确的，实现该机制的代码也容易受到人为错误的影响。

然而，实用且高效的 DP 审计之所以具有挑战性，主要源于机制固有的随机性以及所检验保证的概率性质。此外，保证类型多种多样（例如，纯 DP、近似 DP、Rényi DP 和 集中式 DP），这种多样性加剧了审计问题形式化的复杂性。进一步而言，鉴于所提出的机制数量庞大，调试数学证明和代码库是一项棘手的任务。尽管在特定机制假设下存在临时性测试技术，但为测试 DP 机制开发可扩展工具的努力却寥寥无几。

为此，在“DP-Auditorium: A Large Scale Library for Auditing Differential Privacy”一文中，我们介绍了一个开源库，它仅通过黑盒方式访问机制（即无需了解机制的任何内部属性）来审计 DP 保证。DP-Auditorium 使用 Python 实现，并提供了灵活的接口，使贡献者能够持续改进其测试能力。我们还引入了新的测试算法，针对 Rényi DP、纯 DP 和近似 DP 在函数空间上执行散度优化。我们证明 DP-Auditorium 能够高效地识别 DP 保证违规，并建议哪些测试最适合在各种隐私保证下检测特定缺陷。

DP 保证

DP 机制的输出是从概率分布（M (D)）中抽取的样本，该分布满足确保用户数据隐私的数学性质。因此，DP 保证与成对概率分布之间的性质紧密相关。如果一个机制在数据集 D 和仅相差一条记录的相邻数据集 D' 上确定的概率分布在给定的散度度量下是[不可区分](https://en.wikipedia.org/wiki/Computational_indistinguishability)的，则该机制是差分隐私的。

例如，经典的近似 DP 定义指出，若机制 M(D) 与 M(D’) 之间阶为 eε 的 hockey-stick 散度至多为 δ，则该机制是以 (ε, δ) 为参数的近似 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。与其他方法不同，这些测试器不依赖于被测分布的显式直方图近似。它们依赖于 hockey-stick 散度、Rényi 散度和最大均值差异（MMD）的变分表示，从而能够通过在函数空间上的优化来估计散度。作为基线，我们实现了 HistogramPropertyTester，这是一种常用的近似 DP 测试器。虽然我们的三种测试器采用类似的方法，但为简洁起见，本文重点介绍 HockeyStickPropertyTester。

给定两个相邻数据集 D 和 D'，HockeyStickPropertyTester 会找到 M(D) 与 M(D') 之间 hockey-stick 散度的一个下界 ^δ，该下界以高概率成立。hockey-stick 散度要求两个分布 M(D) 与 M(D') 在近似 DP 保证下彼此接近。因此，如果某项隐私保证声称 hockey-stick 散度至多为 δ，而 ^δ > δ，那么以高概率，D 和 D' 上的散度高于所承诺的值，该机制无法满足给定的近似 DP 保证。下界 ^δ 是作为 hockey-s

…