Adversary Instantiation: Lower Bounds for Differentially Private Machine Learning

In plain words

Differential privacy is a promise that a trained model reveals little about any single training example. The promise is backed by a worst-case proof, and the proof is often loose. This paper asks how much leakage an attacker can actually extract, and it builds the attacker from a game. One part of the attacker prepares two training sets that differ by one example. The model is trained on one of them, chosen at random. A second part looks at the finished model and guesses which set was used. Repeating the game many times shows how often the guess is right, and that rate gives a measured lower bound on the privacy loss.

The attacker can be made stronger or weaker. A weak attacker only sees the final model and cannot change the data. A strong one may insert a crafted example, see every intermediate model, or even control the gradients. The authors use these settings to show which assumptions make the proven bound tight and which make it much too pessimistic. The main lesson is that the worst-case bound can be reached, but only when the attacker has powers that rarely exist in real deployments.

TL;DR

The paper turns the differential-privacy adversary into a concrete attack game and uses it to lower-bound the epsilon of DP-SGD by Monte Carlo testing. With a black-box attacker, the empirical bound stays far below the proven one (CIFAR-10, proven epsilon 4, measured lower bound 0.31). With a malicious dataset and gradient access, the bound comes close to the proven value (proven epsilon 4, lower bound 3.6). The authors conclude that DP-SGD's analysis is tight in the worst case and loose in the average case §4.7, app. B. All numbers are author-reported.

Problem

Training with DP-SGD bounds leakage with an analysis that assumes powerful adversaries: they see all intermediate models and can set gradients directly §1, §2.3. Practitioners often train with large epsilon values in the hope that real leakage is smaller than the proof allows §3.2. Better proofs have improved the bound for the same algorithm over time, and it was unknown whether more improvement was possible §2.3. The paper asks whether the proven bound can be reached by an attacker, and which assumed capabilities matter for that §1.1.

Method

Attack game. The adversary has three roles §3.2:

1. The crafter outputs two datasets D and D' = D plus one extra example (x*, y*). In the simplest variant the extra example is a random draw from the data distribution §4.1.
2. The trainer is not adversarial. It picks one dataset uniformly at random and trains with DP-SGD §3.2, §4.1.
3. The distinguisher sees the trained model, and guesses whether D or D' was used §3.2.

Each run of this game is one instance. The adversary's advantage is measured over many instances §3.3.

DP-SGD update. The trainer uses the standard update with per-example gradients clipped to norm b and Gaussian noise with scale proportional to b §2.3:

# One DP-SGD step on a minibatch B  [eq. 3] [§2.3]
# Gradient step size eta; noise scale sigma; clipping norm b
def dpsgd_step(params, batch, eta, sigma, b):
    # Clip each example's gradient to L2 norm at most b  [§2.3]
    clipped = [clip(grad(params, x, y), b) for (x, y) in batch]
    # Average the clipped gradients over the batch  [eq. 3]
    mean_grad = sum(clipped) / len(batch)
    # Add isotropic Gaussian noise with std sigma  [eq. 3]
    noise = normal(0, sigma**2)
    return params - eta * (mean_grad + noise)

Here clip(v, b) multiplies v by min(1, b / ||v||_2) §2.3. The noise term is drawn per coordinate, as the paper writes Z ~ N(0, sigma^2 I) eq. 3.

Turning error rates into epsilon. For each run the distinguisher's output gives a false-positive rate (guessed D' when the model used D) and a false-negative rate. The paper uses a known inequality between these rates and an (epsilon, delta) guarantee §3.3. The empirical epsilon is:

# Empirical epsilon from error rates  [§3.3] [eq. 4]
# false_positive: guessed D' when the model used D
# false_negative: guessed D when the model used D'
def empirical_epsilon(false_positive, false_negative, delta):
    # Ratio of the two error-rate constraints  [eq. 4]
    ratio_a = (1 - delta - false_positive) / false_negative
    ratio_b = (1 - delta - false_negative) / false_positive
    return max(log(ratio_a), log(ratio_b))

For a statistically valid statement, the paper replaces each rate by its Clopper-Pearson high-confidence bound and uses the same formula eq. 5 §3.3. This gives a lower confidence bound on epsilon.

Attack variants. The paper crosses access (what the distinguisher sees) and modification (what the crafter may change). Table 1 lists six settings tab. 1:

Details of each variant:

• API access (§4.1). The crafter draws (x, y) from the data distribution and adds it to D. The distinguisher computes the model's loss on (x, y) and guesses D' when the loss is at most a threshold tau §4.1.
• Static poison (§4.2). The crafter trains shadow models with DP-SGD on a shadow dataset, then moves a poison input so that its loss on the shadow models changes. The distinguisher is the same as in §4.1 §4.2.
• Intermediate poison (§4.3). The distinguisher is given every intermediate model. It averages or takes the maximum of the loss on the crafted example over the trajectory, and compares it with tau. The paper reports the maximum is better for epsilon at most 2, and the average for larger epsilon §4.3.
• Adaptive poison (§4.4). The crafter produces a fresh poison example during training. It uses a query example, and a double-gradient step (a gradient of a gradient) so that training on the poisoned set raises the query loss §4.4.
• Gradient attack (§4.5). The crafter adds a fixed "watermark" gradient to the training updates by choosing 2n parameters whose gradients are smallest. The distinguisher inspects the weight trajectory and runs a likelihood test for the watermark §4.5 eq. 6.
• Dataset attack (§4.6). The crafter builds a dataset that the model already labels correctly. With the learning rate set to zero, the watermark attack from §4.5 then has almost no noise from other examples §4.6.

Theory. For one dimension, the authors argue that the gradient-level attacks should be tight for one iteration, because the Gaussian mechanism is tight under Rényi DP. They say the multi-dimensional case reduces to this, and that subsampling and composition are tight §4.7. This is an argument, not a formal proof.

DP-SGD formulas used in the attacks. The Gaussian-mechanism setting that motivates DP-SGD is eq. 2. The likelihood of the watermark statistic in §4.5 is eq. 6. Both are stated only as far as the paper writes them.

Hyperparameters

Results

Author-reported. All experiments use the three datasets above unless the table says otherwise. The paper gives most lower bounds in figures. Only the values stated in the text are listed here.

Summary across settings: fig. 1 (MNIST, epsilon 2) and fig. 9 (appendix) show the empirical bound growing from the black-box setting to the dataset attack, which the authors say is close to the proven value app. B.

Paper vs code

No official code.

The paper states that the implementation is in Objax with a link that is "blinded for review" app. A. The arXiv metadata has no project page or comment with a link. GitHub searches with the WebFetch tool for "adversary instantiation", "adversary instantiation privacy", "privacy auditing DP-SGD" in google-research, "dpsgd lower bound attack" for the carlini user, and "objax differential privacy" in the google org all returned no items. No repository could be verified as the authors', so none is recorded.

Pitfalls

• Ceiling of the test. With 1,000 trials, even a perfect attacker cannot show an empirical epsilon above 5.60 at 95% confidence §3.3. Values near this cap are limited by sample size, not by privacy.
• Empirical bound is not a proof of privacy. The result is a lower bound on leakage for the specific attack tested. A weak attack gives a weak bound. The authors say the same §4.1.
• Threshold tau is not specified. The paper never states how the distinguisher's threshold is chosen §4.1, §4.3, §4.5. If it is tuned on the same trials used for the error rates, the Clopper-Pearson bounds no longer hold as stated. This is this card's inference from standard statistics, not the paper's claim.
• Selection of max or mean. For intermediate poisoning the better of the two rules is chosen per epsilon after the experiment §4.3. This is another choice made on the outcome; report both if you replicate.
• Noise multiplier chosen by result. The authors try four noise multipliers and keep the one with the best practical epsilon app. A. Choosing the setting from the measured epsilon makes the reported bounds optimistic.
• Figure-only numbers. Most empirical bounds appear only in figures fig. 3 to fig. 8. Exact values for these settings are not in the text.
• Adaptive poisoning: timing conflicts. The protocol replaces the poison each iteration §4.4 protocol, but the text says "at each iteration ... after each epoch" §4.4. The algorithm also writes the inner step as f'(x) = f(x) - lr * grad, mixing a function of x with a function of the parameters. An implementer has to pick a reading. The code is not available to check it.
• Poison input update sign. The static crafter writes x <- x + s * grad of the shadow loss, which increases the loss alg. Crafter 2, §4.2. Yet the text calls the procedure an adversarial-example method (DeepFool) §4.2. Which direction matches the intended attack is not stated.
• Gradient attack depends on weight deltas. The crafter sums absolute differences of consecutive weights over the first t_o steps, and the text says it observes gradients §4.5. Whether the learning rate is included in this sum is not stated.
• Watermark likelihood is simplified. The paper treats the gradient coordinates at the chosen positions as zero, and multiplies the per-step likelihoods as if independent §4.5 eq. 6. These are assumptions, not checked results.
• Malicious dataset uses learning rate zero. The attack sets the learning rate to zero so the model stays at its initial weights, and labels the data with the initial model's outputs §4.6. The paper says DP-SGD still holds for such hyperparameters. How outputs become labels (argmax, soft labels) is not stated.
• Division by zero. The point estimate in eq. 4 is undefined when a false-positive or false-negative count is zero. The paper uses the upper confidence bounds in eq. 5, which avoids this. An implementer using point estimates must handle the case.
• Trial counts disagree. Section 4.1 says 1,000 trials, appendix A says 1,000 for most experiments and 1,000,000 for the malicious dataset §4.1 app. A.
• Unclear claim. The conclusion says the lower bound "is bounded below by a factor of 10x" for static poisoning §4.2. The factor is not defined in the text, so this card does not restate it.

Lineage

• Builds on: Jagielski et al. 2020, poisoning attacks to audit DP-SGD, extended here to more adversary settings and to delta > 0 §1.1 §3.3.
• Builds on: Ding et al. 2018, Monte Carlo auditing of DP mechanisms §3.3.
• Builds on: Shokri et al. 2017, membership inference attack used as the black-box baseline §4.1.
• Builds on: Kairouz et al. 2015, the error-rate inequality behind eq. 4 §3.3.
• Builds on: Abadi et al. 2016, the DP-SGD algorithm and moments accountant §2.3.
• Compared against: Carlini et al. 2019, arguing that large epsilon can still be safe in practice §3.2 §5.
• Compared against: Jayaraman et al. 2019, relating upper and lower bounds with weaker lower bounds §5.
• Superseded by: not known from content in this wiki.