Beyond Membership: Limitations of Add/Remove Adjacency in Differential Privacy

这篇论文《BEYOND MEMBERSHIP: LIMITATIONS OF ADD / REMOVE ADJACENCY IN DIFFERENTIAL PRIVACY》（超越成员资格：差分隐私中“添加/删除”邻接关系的局限性）深入探讨了在机器学习模型训练中使用差分隐私（DP）时，当前主流的“添加/删除”（Add/Remove）邻接关系定义在保护数据属性（如标签）方面的不足。

以下是该论文的详细技术总结：

1. 研究背景与问题 (Problem)

• 核心矛盾：差分隐私（DP）旨在限制攻击者区分两个相邻数据集的能力。目前大多数 DP 实现（如 Opacus 库）默认使用添加/删除邻接关系（Add/Remove Adjacency, $\sim_{AR}$）。在这种定义下，两个数据集如果相差一条记录的添加或删除，则视为相邻。这种机制主要设计用于保护成员资格隐私（即某人是否在训练集中）。
• 实际痛点：在许多机器学习应用场景（如监督微调）中，用户更关心的是保护单条记录的属性隐私（例如，特定用户的标签是什么），而不仅仅是该用户是否在训练集中。
• 理论缺陷：当攻击目标是推断已知在训练集中的个体的属性时，"添加/删除"邻接关系提供的隐私保证被高估了。攻击者可以通过替换邻接关系（Substitute Adjacency, $\sim_{S}$）（即用一个样本替换另一个样本）来构建更有效的攻击。虽然"添加/删除"隐私界隐含了"替换"隐私界，但其隐私参数（$\epsilon$）会显著变弱（通常 $\epsilon_S \approx 2\epsilon_{AR}$ 或更差），导致实际保护力度远低于报告值。
• 现有差距：现有的隐私会计（Privacy Accounting）工具通常基于"添加/删除"假设，导致从业者误以为模型对属性推断攻击具有足够的抵抗力，而实际上并非如此。

2. 方法论 (Methodology)

为了验证上述差距，作者开发了一套针对替换邻接关系的审计（Auditing）框架，旨在量化实际隐私泄露。

2.1 审计威胁模型

作者设计了多种审计场景，模拟不同能力的攻击者（在隐藏状态 Hidden-State 威胁模型下，即攻击者只能访问最终模型）：

• S1 (最坏情况数据集)：攻击者构建两个最坏情况的相邻数据集 $D$ 和 $D'$，其中 $D'$ 是将 $D$ 中的目标样本 $z$ 替换为 $z'$。
• S2 (梯度空间)：攻击者直接操纵梯度，构造一对梯度 $g_z$ 和 $g_{z'}$，使其范数达到裁剪上限 $C$ 且方向相反。
• S3-S5 (输入空间)：攻击者仅能修改输入数据。
  • S3：构造对抗性输入样本 $z'$，使其梯度与 $z$ 的梯度余弦相似度最小。
  • S4：构造错误标签样本（Mislabeled Canary）。
  • S5：从辅助数据集中选择自然样本作为 $z'$。

2.2 审计算法 (Algorithm 1)

• 挑战者：训练两个模型，一个在数据集 $D$ 上训练（包含 $z$），另一个在 $D'$ 上训练（包含 $z'$，即替换了 $z$）。
• 攻击者：观察最终模型参数 $\theta_T$ 或输出 Logits，计算区分度分数（如 $\text{logit}(z) - \text{logit}(z')$ 或参数变化量 $\theta_T - \theta_0$）。
• 评估指标：通过大量重复实验（Repeats），计算假阳性率（FPR）和假阴性率（FNR），利用高斯差分隐私（$\mu$-GDP）理论将观测结果转换为经验隐私下界 $\hat{\epsilon}$。

2.3 理论对比

• 作者对比了三种隐私预算：
  1. $\epsilon_{AR}$ (Accounting)：基于"添加/删除"邻接关系的理论上限。
  2. $\epsilon_{S}$ (Accounting)：基于"替换"邻接关系的理论上限（使用数值会计方法，如 PRV）。
  3. $\epsilon_{S}$ (Group Privacy)：通过群隐私（Group Privacy）定理从 $\epsilon_{AR}$ 推导出的"替换"上限（通常较宽松）。
• 实验旨在验证：经验泄露 $\hat{\epsilon}$ 是否超过了 $\epsilon_{AR}$，以及是否紧密跟随 $\epsilon_{S}$。

3. 主要贡献 (Key Contributions)

1. 提出了针对替换邻接关系的审计算法：开发了多种构造"金丝雀"（Canary）样本的方法（包括梯度空间构造和输入空间构造），用于在隐藏状态威胁模型下审计 DP 模型。
2. 揭示了"添加/删除"会计的误导性：通过实证证明，基于"添加/删除"邻接关系报告的隐私保证（$\epsilon_{AR}$）严重高估了对属性推断攻击（Attribute Inference）的保护能力。
3. 验证了经验泄露与替换会计的一致性：实验结果显示，审计得到的隐私泄露 $\hat{\epsilon}$ 往往超过 $\epsilon_{AR}$，但与基于"替换"邻接关系的理论会计 $\epsilon_{S}$ 高度吻合。
4. 提供了具体的构造策略：详细描述了如何在梯度空间和输入空间构造最坏情况的攻击样本，特别是针对自然数据集（Natural Datasets）的构造方法。

4. 实验结果 (Results)

作者在 CIFAR-10（图像分类）、SST-2（文本分类）和 Purchase100（从 scratch 训练）等数据集上进行了广泛实验：

• 最坏情况数据集审计 (S1)：

  • 当使用最坏情况构造的数据集时，经验隐私泄露 $\hat{\epsilon}$ 明显超过了 $\epsilon_{AR}$（添加/删除会计值）。
  • $\hat{\epsilon}$ 紧密跟随 $\epsilon_{S}$（替换会计值），证明了替换邻接关系是更准确的评估标准。
  • 使用群隐私定理（Theorem 4.1）从 $\epsilon_{AR}$ 推导出的 $\epsilon_{S}$ 上限比直接数值会计得到的 $\epsilon_{S}$ 要宽松（即数值会计更紧）。

• 自然数据集审计 (S2-S5)：

  • 梯度空间金丝雀 (S2)：在微调（Fine-tuning）场景下，构造的梯度金丝雀能产生最紧的审计结果，且明显违反 $\epsilon_{AR}$ 保证。
  • 输入空间金丝雀 (S3-S5)：
    • 在微调模型上，输入空间金丝雀（如对抗样本、错误标签）也能检测到超出 $\epsilon_{AR}$ 的泄露。
    • 在从 scratch 训练的模型上，输入空间金丝雀的效果较弱（受非凸优化和初始化影响），但在梯度空间金丝雀下依然能观察到符合 $\epsilon_{S}$ 的泄露。
  • 采样率影响：随着子采样率 $q$ 的降低，输入空间金丝雀的审计效力显著下降，但梯度空间金丝雀依然稳健。

• 文本分类：在 SST-2 上的微调实验同样显示，基于梯度金丝雀的审计结果紧密跟随 $\epsilon_{S}$，且超过了 $\epsilon_{AR}$。

5. 意义与结论 (Significance & Conclusion)

• 对实践者的警示：如果应用场景关注的是属性隐私（如标签隐私、特征隐私），仅依赖标准的"添加/删除"DP 会计工具（如 Opacus 默认设置）是危险的，因为它会给出虚假的安全感。
• 重新定义邻接关系：在报告 DP 保证时，必须明确说明使用的邻接关系。对于属性保护，应使用**替换邻接关系（Substitute Adjacency）**进行隐私预算计算和报告。
• 未来方向：
  • 现有的输入空间金丝雀对超参数敏感且收敛较慢，未来需要设计更鲁棒的输入空间攻击样本。
  • 该审计方法主要适用于基于梯度的 DP 算法（如 DP-SGD, DP-Adam），对于其他 DP 机制（如标签 DP 的特殊实现）可能需要调整。
  • 计算成本较高（需要大量重复训练），未来可探索单轮审计优化。

总结：这篇论文有力地证明了在保护单条记录属性时，"添加/删除"邻接关系是不充分的。通过构建针对"替换"邻接关系的审计工具，作者揭示了当前 DP 实现中普遍存在的隐私高估问题，呼吁在属性隐私保护场景下采用更严格的邻接定义和会计方法。