PaperlayerView exact revision on arXiv

Source-linked AI summary

Certified Robustness to Adversarial Examples with Differential Privacy

Mathias Lecuyer, Vaggelis Atlidakis, Roxana Geambasu, Daniel Hsu, Suman Jana

arXiv:1802.03471v4stat.MLcs.AIcs.CRcs.LG

TL;DR

Adversarial examples threaten deep neural networks, while prior defenses were either breakable or limited in scale and model support. PixelDP connects differential privacy to certified robustness by adding calibrated noise and using expected prediction scores. The paper reports a certified defense that scales to Inception on ImageNet and applies broadly across architectures, while noting weaker bounds for l∞ attacks and prediction-time sampling overhead.

  • Problem

    Prior adversarial-example defenses were often vulnerable to sophisticated attacks, while certified defenses were limited in scalability or model applicability.

  • Method

    PixelDP adds calibrated differential-privacy noise to a model’s scoring function and uses expected noisy scores to certify robustness against norm-bounded attacks.

  • Results

    PixelDP scales to Inception on ImageNet and is reported as broadly applicable across architectures, with 68.3% accuracy at L = 0.1 versus 77.5% for the unprotected ImageNet network.

  • Takeaways & Limitations

    The DP-robustness connection provides a generic and scalable foundation for certified adversarial-example defense, including large-network evaluation on ImageNet.

  • Takeaways & Limitations

    For l∞ attacks, the required sensitivity bounds are suboptimal and produce weaker results than for l1 or l2 attacks.

Abstract

from arXiv · show

Adversarial examples that fool machine learning models, particularly deep neural networks, have been a topic of intense research interest, with attacks and defenses being developed in a tight back-and-forth. Most past defenses are best effort and have been shown to be vulnerable to sophisticated attacks. Recently a set of certified defenses have been introduced, which provide guarantees of robustness to norm-bounded attacks, but they either do not scale to large datasets or are limited in the types of models they can support. This paper presents the first certified defense that both scales to large networks and datasets (such as Google's Inception network for ImageNet) and applies broadly to arbitrary model types. Our defense, called PixelDP, is based on a novel connection between robustness against adversarial examples and differential privacy, a cryptographically-inspired formalism, that provides a rigorous, generic, and flexible foundation for defense.

I. Introduction

Adversarial examples expose serious security risks, while earlier defenses were often broken or limited in scale and model applicability. PixelDP connects differential privacy with certified robustness to provide a generic, scalable defense across architectures and datasets.

  • Motivation: Adversarial examples use small input perturbations to cause erroneous predictions, threatening safety- and security-critical applications.Examples include imperceptible stickers that alter a self-driving car’s stop-sign classification.
  • Motivation: Best-effort defenses have repeatedly been broken, motivating rigorous, theory-backed approaches to adversarial robustness.Certified defenses provide guarantees but have generally been tied to network details and evaluated only on small networks and datasets.
  • Contribution: PixelDP connects differential privacy with norm-bounded adversarial robustness and uses this connection as a generic certified-defense foundation.The connection maps input features such as pixels to database records and extends to l1, l2, and l∞ attack norms.
  • Contribution: PixelDP adds differential-privacy noise to a DNN computation, distinguishing adversarial-defense use from differential privacy for protecting training data.The defense can be incorporated broadly, including through a separate auto-encoder without structural changes to the target network.
  • Evaluation: The evaluation includes Inception on ImageNet and multiple architectures across CIFAR-10, CIFAR-100, SVHN, and MNIST.The authors present this as the first certified adversarial-examples evaluation for Inception trained on ImageNet.

B. DP Background

Differential privacy limits how much a randomized computation’s output distribution changes when its input database changes. Its post-processing and expected-output stability properties provide the formal ingredients later used for robustness certification.

  • Definition: Differential privacy introduces randomness into computations to limit information leakage about individual database records.The guarantee concerns how output distributions change when databases differ slightly.
  • Definition: An (ϵ, δ)-DP algorithm bounds output-distribution changes for databases within distance one under a chosen metric.The parameters ϵ and δ quantify the strength of the privacy guarantee.
  • Metrics: DP applies beyond Hamming distance to general metrics, including p-norms relevant to norm-bounded adversarial attacks.For small ϵ and δ, changing one database entry cannot change the output distribution very much.
  • Properties: Post-processing preserves the same DP guarantee, while bounded-output DP algorithms have expected outputs that are stable under small input changes.The expected-output stability property is established in Lemma 1.
  • Properties: The expected value of a bounded randomized output can be represented through the probabilities that the output exceeds thresholds.The expectation is taken over the algorithm’s randomness.

C. DP-Robustness Connection

The DP-robustness connection turns privacy-style output stability into a certificate for adversarial robustness. PixelDP randomizes a scoring function, estimates expected scores, and certifies a label when its lower bound exceeds all competing upper bounds.

  • Connection: A DP scoring function over input features yields stability bounds on expected label scores, which combine with score separation to certify robustness.The approach treats features such as pixels as database records and applies DP to the prediction function.
  • Connection: PixelDP transforms a model’s scoring function into a randomized (ϵ, δ)-PixelDP function and predicts using its expected scores.The winning label is selected by arg max_k E(A_k(x)).
  • Implementation: Because expected scores are generally not analytically tractable after post-noise computation, PixelDP estimates them with Monte Carlo prediction-time sampling.Figure 1 depicts repeated noisy evaluations and combines measurement-error bounds with stability bounds for certification.
  • Certification: A label is certified robust when its lower-bounded expected score exceeds the upper-bounded expected score of every other label.This condition establishes robustness for attacks within the certified p-norm radius.
  • Certification: For attacks of p-norm size 1, the certification is exact with no failure probability, and group privacy generalizes the result to size L.The stated certification applies regardless of the differential privacy parameter δ.

III. PixelDP Certified Defense

PixelDP inserts differential-privacy noise into a neural network to obtain certified robustness against norm-bounded adversarial examples. Its post-processing foundation supports flexible noise placement, broad architectures, and certification procedures that can scale to large models and datasets.

  • Defense architecture: PixelDP adds a differentially private noise layer to a DNN, making its prediction distribution insensitive to bounded input changes.The network can use Laplace or Gaussian noise mechanisms calibrated to sensitivity, attack size, and privacy parameters.
  • Defense architecture: The post-processing property carries the (ϵ, δ)-PixelDP guarantee through subsequent network layers when no skip connection bypasses the noise.This permits the noise layer to be placed at different points in the architecture while preserving the guarantee.
  • Certification use: PixelDP can certify individual predictions or provide a lower bound on test accuracy under attacks, independent of how future attacks are implemented.The latter quantity is called certified accuracy.
  • Robustness guarantee: For a fixed noise standard deviation, doubling the construction attack bound L doubles ϵ, so the guarantee degrades gracefully for larger attacks.This scaling follows the paper’s use of group privacy.
  • Sensitivity and placement: Sensitivity can be computed for inputs, linear layers, convolutions, and deeper placements, but successive bounds may become loose and batch normalization is difficult to handle.The authors generally recommend adding noise early, where sensitivity is easier to bound.
  • Sensitivity and placement: A separately trained auto-encoder can supply the noise layer before a predictive DNN, enabling certified modeling with a smaller training component and a pre-trained Inception-v3 network.The stacked auto-encoder and DNN remain (ϵ, δ)-PixelDP by post-processing.

C. Training Procedure

PixelDP training preserves the original loss and optimizer while constraining pre-noise sensitivity. Noise is retained during training because removing it produces near-zero certified accuracy in the authors’ experience.

  • Training Procedure: PixelDP retains noise during training because removing the noise layer produces near-zero certified accuracy in the authors’ experience.The certification’s soundness requires noise at prediction time, but training without noise performs poorly empirically.
  • Training Procedure: Training constrains pre-noise sensitivity, using layer normalization for some norms and projection after each SGD step for the 2-norm sensitivity.The chosen technique depends on the input and output norm pair being bounded.
  • Training Procedure: Training optimizes predictions from one noise draw, whereas prediction estimates expected scores using multiple independent noise draws.This training objective pushes the network toward a larger expected-score margin for the true label.

D. Certified Prediction Procedure

PixelDP predicts from Monte Carlo estimates of randomized scores and attaches a robustness certificate when confidence bounds establish a sufficient label margin. It can return either an input-specific attack radius or dataset-level certified accuracy.

  • Certified Prediction Procedure: PixelDP selects the label with the largest Monte Carlo estimate of the randomized network’s expected score rather than using one deterministic score vector.The estimate averages independent invocations of the randomized network.
  • Certified Prediction Procedure: Confidence bounds and a union bound account for Monte Carlo estimation error when constructing lower and upper score estimates.Hoeffding’s inequality or empirical Bernstein bounds can provide the estimation guarantees.
  • Certified Prediction Procedure: A prediction is certified robust to p-norm attacks of size L when the estimated score bounds satisfy the generalized robustness condition.Under that condition, the classification model is robust with probability at least η.
  • Certified Prediction Procedure: The DP bounds themselves are nonprobabilistic; the failure probability 1 − η arises from Monte Carlo estimation and can be reduced with more network invocations.This separates privacy-based robustness guarantees from sampling error.
  • Certified Prediction Procedure: PixelDP can compute the maximum certified attack size Lmax for each input, rather than only testing robustness at one fixed attack bound.The prediction receives a robustness size certificate equal to the largest attack size satisfying the certification condition.
  • Certified Prediction Procedure: At the dataset level, PixelDP certifies a lower bound on accuracy under attacks up to an inference-time threshold T.This certification need not be computed for every prediction, and a few hundred draws can retain a large fraction of certified predictions in practice.

IV. Evaluation

PixelDP is evaluated across five image-classification datasets, multiple architectures, and comparisons with prior certified and best-effort defenses. The evaluation measures accuracy, certified robustness, attack performance, computational overhead, and dataset/model scalability.

  • Evaluation setup: The evaluation compares PixelDP with one prior certified defense and one best-effort defense using conventional and certified accuracy metrics.Certified accuracy is a guaranteed lower bound under norm-bounded attacks, while practical attack accuracy may be higher.
  • Certified robustness: PixelDP provides meaningful certified robustness bounds with reasonable accuracy degradation across all evaluated datasets and DNNs.For Inception on ImageNet and ResNets on CIFAR-10, it achieves 60% certified accuracy against 2-norm attacks up to 0.1, with 8.5- and 9.2-percentage-point degradation, respectively.
  • Comparisons: On SVHN, PixelDP reaches 92.9% clean accuracy versus 79.6% for the prior certified defense, and 55% versus 17% robustness at 2-norm attack size 0.5.The comparison uses the smaller prior defense model because that method does not scale to the largest datasets or complex architectures.
  • Comparisons: On CIFAR-10, PixelDP matches the best-effort defense closely, achieving 87% accuracy versus 87.3% while also matching its robustness to 2-norm bounded attacks.The evaluation reports this comparison on larger models and datasets.
  • Evaluation setup: PixelDP is evaluated on five datasets spanning MNIST, SVHN, CIFAR-10, CIFAR-100, and ImageNet, using both small and large networks.The datasets range from handwritten digits to the production-scale ImageNet dataset.

B. Impact of Noise (Q1)

The noise level used to construct a PixelDP network controls a trade-off between conventional accuracy and robustness to larger attacks. At a meaningful construction bound, the evaluated models retain substantial accuracy, including on ImageNet.

  • Impact of Noise: Higher construction attack bounds L require larger noise standard deviation σ and target robustness against larger attacks.PixelDP evaluates construction bounds L in {0.03, 0.1, 0.3, 1}.
  • Impact of Noise: At L = 0.1, ImageNet Inception-v3 accuracy is 68.3% versus 77.5% for the unprotected baseline.The passage characterizes this as reasonable degradation on a dataset without prior guarantees.
  • Impact of Noise: At L = 0.1, CIFAR-10 accuracy is 87% versus 95.5% without defense, closely matching the Madry model’s 87.3% accuracy.The comparison uses conventional accuracy.
  • Impact of Noise: At L = 0.1, SVHN PixelDP accuracy is 93.1% versus 96.3% for the unprotected network and 79.6% for the smaller RobustOpt model.The RobustOpt comparison uses a smaller DNN because its method is computationally intensive.
  • Impact of Noise: Increasing L progressively degrades conventional accuracy, with ImageNet falling to 57.7% at L = 0.3 and 37.7% at L = 1.0.On CIFAR-10, accuracy similarly decreases from 93.3% at L = 0.03 to 37.7% at L = 1.0.

C. Certified Accuracy (Q2)

PixelDP provides certified robustness bounds across large ImageNet and CIFAR-10 models, with the strongest certified accuracy depending on the attack construction bound and prediction threshold. Under attacks, PixelDP improves robustness on ImageNet and remains competitive with established defenses, while certified predictions trade coverage for precision and prediction incurs substantial overhead.

  • Certified accuracy: 59% certified accuracy is achieved on ImageNet for attacks smaller than 0.09 in 2-norm with construction attack bound L = 0.1.
  • Certified accuracy: 40% certified accuracy is achieved for attacks up to size 0.2 in 2-norm with construction attack bound L = 0.3.
  • Certified accuracy: Higher construction bounds L generally improve certified accuracy at higher prediction thresholds T, whereas lower-noise networks perform better at low T.On CIFAR-10, L = 0.03 is best up to T = 0.03, while L = 0.1 is better above that threshold; L = 0.3 exceeds L = 0.1 above T = 0.14.
  • Accuracy under attack: At ImageNet attack size Lattack = 0.5, baseline accuracy drops to 11%, while the L = 0.1 PixelDP model remains above 60%.At Lattack = 1.5, baseline accuracy is 0, while L = 0.1 remains at 30% and L = 0.3 exceeds 39%.
  • Accuracy under attack: For 2-norm attacks, PixelDP accuracy is on par with or slightly higher than Madry’s, while RobustOpt is below 20% at Lattack = 0.5 and PixelDP exceeds 55%.PixelDP is trained for 2-norm attacks, so its relative behavior differs under ∞-norm attacks.
  • Certified predictions and overhead: At T = 0.05, PixelDP’s robust predictions are 93.9% accurate and up to 10 percentage points more correct under attack for Lattack ≤ 1.1, covering above 60% of data points.More conservative tests yield more correct predictions but fewer certified predictions; 300 draws typically require 0.42 seconds, a 42× prediction overhead.

V. Analysis

PixelDP’s differential-privacy foundation supports network-agnostic certified defenses, while its guarantees and applicability depend on bounded outputs, sensitivity control, and Monte Carlo estimation. The approach broadens certified robustness beyond prior methods, but its relative advantage varies by attack and model setting.

  • Analysis: Monte Carlo integration makes PixelDP’s final certification probabilistic, although its uncertainty can be reduced arbitrarily with more network evaluations.The underlying differential-privacy mechanism does not introduce this measurement uncertainty.
  • Analysis: PixelDP can apply to tasks with meaningful p-norm input changes and bounded sensitivity, including multiclass classification and bounded-output regression.For regression, outputs must be bounded, or unbounded outputs require δ = 0.
  • Analysis: PixelDP’s post-processing property allows calibrated noise at one layer to carry robustness bounds through arbitrary downstream network computations.This supports a network-agnostic defense rather than requiring architecture-specific internal modifications.
  • Analysis: Randomization-based defenses become certified when noise is calibrated to sensitivity and formalized through differential privacy.The paper contrasts this with prior methods that either lacked formal guarantees or added insufficient noise.
  • Analysis: Unlike prior differentially private machine learning, PixelDP protects prediction stability to input changes rather than privacy of the training set.The two uses share DP theory and mechanisms but differ in goals, semantics, and algorithms.
  • Analysis: PixelDP’s certified 2-norm defense matches the effectiveness of the leading best-effort defense while scaling more broadly than prior certified defenses.The paper also evaluates certified 2-norm robustness on ImageNet using an autoencoder-based architecture.

Appendix

The appendix formalizes PixelDP’s multiclass certification condition and examines design choices affecting certified accuracy. Arg max scores improve certification bounds, while the preferable noise mechanism depends on noise level.

  • Appendix: A PixelDP classifier is robust to p-norm attacks of size L when its estimated lower winning-label score sufficiently exceeds estimated upper scores for all alternatives.The proposition states that this robustness holds with probability higher than η.
  • Appendix: The proof transfers score bounds from the original input to every perturbed input within the p-norm ball, yielding the robustness condition.The argument applies the differential-privacy stability relation to the estimated score bounds.
  • Design Choice: Arg max scores produce higher certified accuracy because they separate expected label scores further and permit tighter Clopper–Pearson measurement-error bounds.They are nevertheless empirically less robust under attack than softmax scores.
  • Design Choice: At low noise levels for 1-norm attacks, the Laplace mechanism outperforms the Gaussian mechanism on the evaluated ResNet.For L = 0.1, accuracy is 90.5% versus 88.9%, and maximum certified robustness is 0.22 rather than 0.19.

C. Attack Details

The evaluation uses strong adaptive attack procedures and compares PixelDP with models trained specifically for ∞-norm attacks. PixelDP is competitive in some settings but has substantially weaker ∞-norm certification than prior defenses.

  • Attack Details: All evaluations use a Carlini–Wagner attack specialized for PixelDP, alongside iterative PGD variants that average gradients over noise draws and repeat randomized attacks.The 2-norm PGD results were qualitatively identical, with slightly higher raw accuracy than the retained results.
  • Attack Details: The ∞-norm attack uses clipped perturbations, constant 0.003 steps, and max(L + 8, 1.5L) gradient steps.This procedure was used for comparisons with Madry and RobustOpt models.
  • Attack Details: PixelDP’s certified accuracy bounds remain valid regardless of the attack, so the evaluation includes sanity checks for gradient masking.The checks address whether defenses merely obfuscate gradients rather than remove adversarial examples.
  • ∞-norm Attacks: PixelDP’s current ∞-norm certification sizes are substantially lower than those of prior certified defenses evaluated on smaller networks and datasets.Matching the MNIST T∞ = 0.1 result would require a 2-norm bound T2 = 2.8, an order of magnitude higher than achieved.
  • ∞-norm Attacks: At L_attack = 0.01 on CIFAR-10, PixelDP accuracy is 69%, 8 percentage points below Madry’s, and PixelDP reaches 0 accuracy at L_attack = 0.06 while Madry remains at 22%.Madry was trained specifically against ∞-norm attacks.
  • ∞-norm Attacks: On SVHN, PixelDP is better than RobustOpt through L∞ = 0.015, after which RobustOpt is more robust.The reported advantage is attributed to PixelDP’s support for larger ResNet models.

E. Extension to regression

The regression extension handles signed outputs by decomposing them into positive and negative parts and applying separate differential-privacy bounds. It requires bounded outputs or pure DP for unbounded outputs, plus separate estimation of both components.

  • E. Extension to regression: A signed, bounded DP output is decomposed into nonnegative positive and negative components whose expected values are bounded separately.The signed expectation is then recovered by subtracting the negative-component expectation from the positive-component expectation.
  • E. Extension to regression: The corrected signed-output lemma enables PixelDP to extend from classification scores in [0, 1] to bounded regression outputs.An earlier incorrect claim for negative outputs did not affect the paper’s classification results.
  • E. Extension to regression: The expectation in the regression lemma is taken over the randomized mechanism’s internal randomness.The lemma applies to outputs bounded between a ≤ 0 and b ≥ 0.
  • E. Extension to regression: Supporting regression with unbounded outputs requires (ε, 0)-DP, while bounded outputs may use (ε, δ)-DP.Outputs can be bounded naturally by the task or by truncating them to a large range with comparatively small δ.
  • E. Extension to regression: Monte Carlo estimation for regression separately estimates the positive and negative components and bounds their errors with Hoeffding or empirical Bernstein inequalities.These estimates are combined with separate DP Expected Output Stability Bounds.
Loading 1802.03471v4…