PaperlayerView exact revision on arXiv

Source-linked AI summary

Adversary Instantiation: Lower Bounds for Differentially Private Machine Learning

Milad Nasr, Shuang Song, Abhradeep Thakurta, Nicolas Papernot, Nicholas Carlini

arXiv:2101.04535v1cs.LGcs.CR

TL;DR

The paper asks whether DP-SGD’s theoretical privacy bounds reflect attacks available in realistic settings. It instantiates adversaries with varying capabilities to establish lower bounds on privacy leakage, finding tight worst-case bounds but a gap under practical restrictions.

  • Problem

    It is unclear whether access to intermediate model updates enables stronger attacks on deep neural network training than access to the final model alone.

  • Method

    The paper instantiates the DP adversary with dataset crafters and distinguishers spanning black-box observation, gradient poisoning, and intermediate-update access, then estimates lower bounds using Monte Carlo trials.

  • Results

    For DP-SGD, full-capability attacks match the theoretical upper bound, while realistic restrictions produce substantially lower attack bounds.

  • Takeaways & Limitations

    Tighter privacy guarantees require changing DP-SGD or adding adversary restrictions, and practical deployments may provide stronger privacy than worst-case analysis proves.

Abstract

from arXiv · show

Differentially private (DP) machine learning allows us to train models on private data while limiting data leakage. DP formalizes this data leakage through a cryptographic game, where an adversary must predict if a model was trained on a dataset D, or a dataset D' that differs in just one example.If observing the training algorithm does not meaningfully increase the adversary's odds of successfully guessing which dataset the model was trained on, then the algorithm is said to be differentially private. Hence, the purpose of privacy analysis is to upper bound the probability that any adversary could successfully guess which dataset the model was trained on.In our paper, we instantiate this hypothetical adversary in order to establish lower bounds on the probability that this distinguishing game can be won. We use this adversary to evaluate the importance of the adversary capabilities allowed in the privacy analysis of DP training algorithms.For DP-SGD, the most common method for training neural networks with differential privacy, our lower bounds are tight and match the theoretical upper bound. This implies that in order to prove better upper bounds, it will be necessary to make use of additional assumptions. Fortunately, we find that our attacks are significantly weaker when additional (realistic)restrictions are put in place on the adversary's capabilities.Thus, in the practical setting common to many real-world deployments, there is a gap between our lower bounds and the upper bounds provided by the analysis: differential privacy is conservative and adversaries may not be able to leak as much information as suggested by the theoretical bound.

I. INTRODUCTION

The paper instantiates DP’s hypothetical adversary across attack capabilities to measure privacy leakage in DP-SGD. Full capabilities make the analysis tight, while realistic restrictions reveal a substantial gap and potentially stronger practical privacy.

  • DP-SGD is the most popular method for training neural networks with differential privacy.
  • The paper evaluates adversaries ranging from black-box prediction observers to attackers that poison gradients and observe intermediate updates.This spectrum measures which capabilities are needed to reach the privacy leakage allowed by DP analysis.
  • The findings provide empirical evidence for practitioners and identify adversary restrictions that may help theoreticians obtain stronger privacy guarantees.The practical setting can offer more privacy than the worst-case analysis proves, while new assumptions may improve theoretical bounds.
  • Full adversary capabilities make the DP-SGD lower bound match the provable upper bound, showing the analysis is tight in the worst case.The result implies that stronger bounds require changing DP-SGD or adding assumptions about the adversary.
  • Under realistic restrictions, such as revealing only the final trained model, the empirical lower bound is substantially lower than the theoretical upper bound.This leaves open the possibility of better privacy analysis for practical deployments.
  • Many adversary capabilities do not significantly strengthen the attack; access to only the final model can be almost as effective as access to all intermediate models.

A. Machine Learning

Machine learning models are parameterized functions trained by minimizing loss on finite datasets, commonly with stochastic gradient descent. Overparameterization and repeated training can enable models to memorize training data, motivating differential privacy and its formal guarantees.

  • A machine learning model is a parameterized function fθ mapping inputs from X to outputs in Y.The paper focuses mainly on deep neural networks, while its results are independent of architecture details.
  • Training obtains model parameters by minimizing average loss over a finite dataset D.The training algorithm is denoted by fθ ← T(D).
  • Stochastic gradient descent minimizes training loss by sampling mini-batches, computing their average loss, and updating model parameters with learning rate η.Each update is abbreviated as fθ+1 ← S(fθ, B).
  • Repeated epochs and overparameterization can let neural networks memorize data-specific information unrelated to final accuracy.This memorization enables attacks that extract information from trained models.
  • Differential privacy bounds how much an algorithm’s output distribution can differ between neighboring datasets that differ in one sample.The guarantee is parameterized by ε and δ and remains under arbitrary post-processing.
  • The Gaussian mechanism provides differential privacy for bounded data by adding noise calibrated to ε and δ.If inputs are unbounded, fixed noise may permit reliable distinguishing between neighboring datasets.

C. Differentially-Private Stochastic Gradient Descent

DP-SGD clips individual gradients and adds Gaussian noise before composing private updates across training. Its analysis uses conservative adversary capabilities, including access to intermediate updates and direct gradient control, motivating questions about tighter, more realistic privacy bounds.

  • DP-SGD mechanism: DP-SGD clips gradients to bound each individual update by b, then adds Gaussian noise with scale proportional to b.The minibatch update uses Gaussian noise Zi ∼ N(0, σ2I) and the clipping function projects vectors onto an ℓ2 ball of radius b.
  • DP-SGD mechanism: Per-iteration private updates compose into a differential privacy guarantee for the entire model-training pipeline.The analysis applies post-processing to model parameters and uses composition across iterations.
  • DP-SGD analysis: Naive composition yields ε ≫ 10^4 for accurate neural networks, whereas the Moments Accountant proves ε < 10 for the same algorithm.Later work further improved DP-SGD analyses, but the passage frames these as analyses under the same algorithmic setting.
  • Research question: The paper instantiates adversaries to analyze DP-SGD tightness under varying assumptions and identify practical conditions for exploiting the upper-bound leakage.The analysis treats DP-SGD as an over-approximation of adversaries that occur in practice.
  • Adversary capabilities: DP-SGD analysis assumes adversaries may receive intermediate model updates, although practical deployments often reveal only the final trained model.This assumption supports composition over minibatch iterations, while direct final-model analysis is known for convex models but not general deep neural networks.
  • Adversary capabilities: The analysis also assumes direct adversarial control of gradient updates, even though training pipelines typically receive examples and derive gradients from the model and inputs.The passage identifies gradients as a simpler trust boundary for proof purposes.

B. Instantiating the DP Adversary

The paper instantiates the differential privacy adversary as a crafter, a model-training process, and a distinguisher, then estimates privacy leakage from repeated attack trials. This framework varies adversary capabilities to compare empirical lower bounds with DP-SGD’s analytical guarantees.

  • Attack protocol: The attack begins by constructing neighboring datasets D and D′ that differ in exactly one example.The crafter produces the pair, and the trainer randomly selects one dataset for training.
  • Attack protocol: The model trainer independently trains on one randomly selected dataset, while the adversary does not control this training step.Depending on the setup, the trainer may perform one step or a full training run and may reveal final or intermediate weights.
  • Attack protocol: The distinguisher receives the crafter’s datasets and training output, then predicts whether training used D or D′.Its output is 0 for D and 1 for D′.
  • Lower-bound estimation: Repeated trials produce success or failure bits used to estimate false positive and false negative rates for empirical (ε, δ)-DP.The analysis accommodates both pure DP with δ = 0 and the (ε, δ) variant.
  • Lower-bound estimation: The Clopper-Pearson method supplies confidence bounds on attack performance and a lower confidence bound on empirical ε.With 1000 trials, even complete adversary success implies an ε lower bound of only 5.60.

IV. EXPERIMENTS

The experiments instantiate six adversary models with progressively varying capabilities and evaluate their ability to distinguish models trained on neighboring datasets. Results span realistic API access through stronger attacks, showing that attack strength depends on both dataset diversity and adversary capabilities.

  • Six attack configurations vary adversary capabilities across access, dataset manipulation, and dataset control.The configurations correspond to relevant ML deployments and key assumptions in privacy analysis.
  • A. API Access Adversary: The baseline membership inference adversary uses API access to compare the trained model’s loss on the single differing example against a threshold.It constructs D and D′ by adding one randomly sampled example, then predicts D′ when the loss is sufficiently small.
  • A. API Access Adversary: The baseline membership inference attack is explicitly used to lower-bound privacy leakage rather than to determine whether a user belongs to the training set.The experiments use MNIST, CIFAR10, and Purchase under ε values of 1, 2, 4, and 10.
  • A. API Access Adversary: On CIFAR-10 with ε = 4, the attack achieved a true positive rate of 0.017 and false positive rate of 0.002.Across 1,000 trials, the empirical lower bound converted to (ε, δ)-DP with (0.31, 10^-5), versus the provable upper bound of (4, 10^-5).
  • A. API Access Adversary: MNIST showed no significant advantage over random chance, whereas CIFAR-10 and Purchase were easier to distinguish.The paper hypothesizes that MNIST’s high image similarity makes single-example changes less influential.
  • The paper frames weak-attack results as potentially reflecting either pessimistic DP bounds or an insufficiently strong adversary, with the latter interpretation ultimately supported.The strongest-capability experiments address whether DP-SGD bounds remain accurate when adversaries use more of the permitted capabilities.

B. Static Input Poisoning Adversary

The static input poisoning adversary strengthens membership inference by crafting a malicious training example rather than sampling one randomly. This worst-case input achieves higher empirical privacy-leakage lower bounds consistently across datasets.

  • The adversary crafts a poisoned input so that including it changes the model output and makes membership inference easier.The attack constructs neighboring datasets D and D′ that differ by this malicious example.
  • Shadow models approximate the trainer’s behavior and guide adversarial-example construction using the trainer’s hyperparameters.The crafter iteratively updates the input to create a worst-case poisoning example.
  • The malicious-input attack achieves a higher empirical lower bound than random-sample membership inference across all datasets.The improvement is attributed to replacing average-case inputs from the training distribution with worst-case inputs for membership inference.

C. Intermediate Poison Attack

The intermediate poison attack gives the distinguisher the full sequence of model updates in addition to the malicious input. This extra access only slightly improves performance over using the final model alone.

  • The DP-SGD analysis grants the adversary access to intermediate model parameters throughout training, not only the final model.The attack evaluates the privacy relevance of this additional white-box capability for deep neural networks.
  • The distinguisher analyzes intermediate losses using either their average or maximum over the training sequence.It applies the same poisoned-input crafter while changing the information available to the distinguisher.
  • Access to all intermediate models only slightly outperforms access to the final model parameters.The result suggests that the final model output leaks almost as much information as the gradients applied during training.

D. Adaptive Poisoning Attack

The adaptive poisoning attack changes the malicious training dataset at every iteration, exploiting intermediate model updates to obtain tighter privacy lower bounds.

  • Adaptive attack: The adversary generates a fresh poison input on each gradient-descent iteration to make models trained on D and D′ behave differently on a query.Double backpropagation updates the malicious input to reduce the query loss after a temporary model update.
  • Adaptive attack: The adversary game lets the attacker choose D and D′ from the current weights before each minibatch training step.The trainer then trains on one selected dataset, and the adversary predicts which dataset was used.
  • Adaptive attack: The trainer updates the malicious dataset before each iteration when training on D′, while the distinguisher uses the query input rather than inserted poison examples.The attack assumes strong adversarial control over the dataset to establish a lower bound on privacy leakage.
  • Results: On Purchase with ε = 2, the adaptive poisoning attack achieves εlower = 0.37, compared with 0.25 for the prior attack.Changing the dataset at each iteration enables more effective exploitation of intermediate model updates.

E. Gradient attack

The gradient attack gives the adversary direct control over malicious gradient updates and direct access to intermediate model weights, strengthening the distinguisher.

  • Attack model: DP-SGD analysis permits the adversary to control gradient updates because clipping and noising operate on updates regardless of how they were obtained.This attack therefore supplies malicious gradients directly rather than deriving them from ordinary examples.
  • Attack model: The Crafter inserts a watermark into parameters with the smallest observed gradient changes, while the distinguisher detects it from intermediate model weights.The trainer may add the malicious gradient with probability q and reveals intermediate parameters to the attacker.
  • Attack model: The gradient-poisoning game alternates between adversarially chosen gradient collections and minibatch updates using clipped and noised gradients.The adversary predicts which dataset was used after the training rounds.
  • Results: For ε = 1, the attack achieves an empirical lower bound ε = 0.3 and is almost tight, although the gap increases at larger ε.Direct access to model gradients improves the adversary’s lower bound.

F. Malicious Datasets

The malicious-dataset attack constructs a dataset with minimal unintended influence on model parameters, bringing the empirical privacy lower bound close to the DP-SGD upper bound.

  • Dataset construction: The adversary constructs a worst-case dataset designed to minimize unintended influence from other training examples.This setting is considered unlikely in practice and is studied to test the DP-SGD analysis under its worst-case assumptions.
  • Dataset construction: The constructed dataset is labeled by the initial model, so training on minibatches excluding the malicious examples becomes an effective no-op apart from Gaussian noise.The initial model already labels the sampled data perfectly.
  • Dataset construction: Setting the learning rate to zero prevents Gaussian noise from corrupting the model weights and keeps θi ≡ θ0.The paper treats this as allowable under DP-SGD’s guarantee for arbitrary hyperparameter assignments.
  • Results: With the worst-case dataset, the lower bound is nearly tight: when the theoretical DP-SGD bound is ε = 4, the attack achieves 3.6.Removing intrinsic noise from other examples significantly tightens the lower bound.
  • Results: The authors conclude that exploiting all assumptions in DP-SGD analysis can produce privacy leakage close to maximal.They identify better modeling of intrinsic dataset noise as a possible route to tighter guarantees, while noting that formalizing it is nontrivial.

G. Theoretical Justifications

Theoretical tightness follows from tight Gaussian-mechanism, subsampling, composition, and RDP-to-DP arguments, extending from one-dimensional to higher-dimensional settings.

  • Tightness analysis: For one iteration in one dimension, observing the private update makes the Gaussian-noise lower bound expected to be tight.The Gaussian mechanism is analytically tight, and the paper states that empirical lower bounds should consequently be tight for one iteration.
  • Tightness analysis: In higher dimensions, changing one sample can affect one gradient coordinate, reducing the analysis to independent one-dimensional problems with equal-scale noise.The paper uses this coordinate-wise reduction to justify tightness beyond the one-dimensional case.
  • Tightness analysis: Tight RDP guarantees for minibatch subsampling and tight composition over iterations support the tightness of the resulting privacy bounds.The conversion from RDP to differential privacy is also tight within a constant factor.

V. RELATED WORK

The paper introduces adversarial instantiation as a way to compare empirical privacy leakage with DP-SGD’s analytical upper bounds. It finds tightness under full capabilities but a substantial gap under practical restrictions, with implications for theoretical assumptions and deployment.

  • Contribution: The proposed adversarial-game methodology evaluates the gap between privacy leakage lower bounds and DP-SGD’s analytical upper bounds.It instantiates games between hypothetical adversaries and model trainers.
  • Theoretical implications: Full-capability adversaries make the current DP-SGD analysis tight, leaving no gap between lower and upper bounds.The paper verifies that the Moments Accountant is tight as currently implemented.
  • Practical implications: Under realistic adversary restrictions, empirical privacy can be stronger than the worst-case bound.In centralized settings, adversaries limited to realistic capabilities currently do not succeed as often as the upper bound suggests.
  • Theoretical implications: Better privacy guarantees therefore require changing DP-SGD or imposing additional restrictions on the adversary.Assumptions about dataset naturalness alone are unlikely to help substantially because pathological and CIFAR10 attacks have similar effectiveness.
  • Practical implications: The results challenge the practice of choosing very large ε values while assuming measured exposure will remain negligible.The paper states that it refutes such claims in general.
  • Scope: Stronger adversaries could nevertheless succeed more often than the evaluated attacks.This leaves the practical gap dependent on the adversary capabilities considered.

APPENDIX A: EXPERIMENTAL SETUP

The appendix describes the experimental datasets, models, training settings, repetition strategy, and privacy accounting used to evaluate increasingly powerful adversaries. Results show tight worst-case bounds but lower empirical privacy leakage under realistic restrictions.

  • Datasets and models: Experiments use MNIST, CIFAR10, and Purchase with convolutional or fully connected neural networks trained using DP-SGD.MNIST and CIFAR10 use four-layer convolutional networks; Purchase uses a three-layer fully connected network.
  • Results: Dataset and gradient attacks approach theoretical privacy bounds, while restricting access from gradients to inputs produces a noticeable drop in empirical privacy parameters.Access to intermediate models, as in federated learning, can still produce values close to theoretical bounds.
  • Results: When adversaries cannot modify the dataset, gradients, or input, practical ε is much lower than the theoretical bound.Figure 9 summarizes this trend across increasingly powerful adversaries and compares empirical ε with the certifiable upper bound.
  • Results: Overall, DP-SGD is tight in the worst case but loose in the average case.The appendix frames this distinction as the central summary of the experiments.
Loading 2101.04535v1…