PaperlayerView exact revision on arXiv

Source-linked AI summary

Robustness Certificates for Sparse Adversarial Attacks by Randomized Ablation

Alexander Levine, Soheil Feizi

arXiv:1911.09272v1cs.LGstat.ML

TL;DR

Certifiable defenses have largely focused on additive-noise smoothing for L1 and L2 attacks, leaving sparse L0 attacks as a distinct target. This paper uses randomized ablation to certify robustness to sparse attacks, with nontrivial certificates on MNIST, CIFAR-10, and ImageNet and an empirical defense on MNIST.

  • Problem

    Randomized smoothing had mostly addressed L1 and L2 attacks, while sparse L0 attacks require a certifiable defense against perturbations to a limited number of features.

    Source: Introduction · pp. 1–2

  • Method

    The method randomly ablates most input pixels and uses base-classifier votes to certify robustness against arbitrary sparse attacks.

    Source: Introduction · pp. 2–3

  • Results

    The method produces nontrivial robustness certificates on MNIST, CIFAR-10, and ImageNet, and is an effective empirical defense against L0 attacks on MNIST.

    Source: Conclusion · p. 9

  • Takeaways & Limitations

    Despite using slightly fewer pixels from the original image, each ablated classification retains over twice the information about that image.

    Source: Comparison to (Lee et al. 2019) · p. 8

    In the multiclass certificate, bounds must hold simultaneously across classes, which can increase estimation error when the number of classes is large.

    Source: Practical Robustness Certificates · p. 4

Abstract

from arXiv · show

Recently, techniques have been developed to provably guarantee the robustness of a classifier to adversarial perturbations of bounded L_1 and L_2 magnitudes by using randomized smoothing: the robust classification is a consensus of base classifications on randomly noised samples where the noise is additive. In this paper, we extend this technique to the L_0 threat model. We propose an efficient and certifiably robust defense against sparse adversarial attacks by randomly ablating input features, rather than using additive noise. Experimentally, on MNIST, we can certify the classifications of over 50% of images to be robust to any distortion of at most 8 pixels. This is comparable to the observed empirical robustness of unprotected classifiers on MNIST to modern L_0 attacks, demonstrating the tightness of the proposed robustness certificate. We also evaluate our certificate on ImageNet and CIFAR-10. Our certificates represent an improvement on those provided in a concurrent work (Lee et al. 2019) which uses random noise rather than ablation (median certificates of 8 pixels versus 4 pixels on MNIST; 16 pixels versus 1 pixel on ImageNet.) Additionally, we empirically demonstrate that our classifier is highly robust to modern sparse adversarial attacks on MNIST. Our classifications are robust, in median, to adversarial perturbations of up to 31 pixels, compared to 22 pixels reported as the state-of-the-art defense, at the cost of a slight decrease (around 2.3%) in the classification accuracy. Code is available at https://github.com/alevine0/randomizedAblation/.

Introduction

The introduction motivates certifiable defenses for sparse L0 attacks and proposes randomized ablation as a smoothing method. It also establishes notation for images with ablated pixels and for counting pixel changes.

Introduction

  • Existing L0 defenses can be vulnerable to newly developed attacks, while empirical evaluations do not provide a general proof of security.The L0 metric counts changed pixels and poses a distinct challenge because it is non-differentiable.Source: Introduction · p. 1
  • For k = 45 retained pixels, the method guarantees robustness against attacks perturbing 8 or fewer pixels, with about 97% test accuracy.The figure reports median certified robustness over the MNIST test set.Source: Figure 1 · p. 2
  • Randomized ablation drops most pixels before classification; when corrupted pixels are omitted, clean and attacked images often produce the same ablated sample, enabling certificates for sparse attacks.A sufficiently large vote gap supports a high-probability robustness guarantee.Source: Introduction · p. 2
  • The proposed defense is based on randomized ablation, characterizes guarantees against arbitrary sparse attacks, and is evaluated on MNIST, CIFAR-10, and ImageNet.The introduction distinguishes its provable guarantee from a related pixel-ablation defense without a robustness certificate.Source: Introduction · p. 3

Preliminaries and Notation

  • The preliminaries define L0 distance as the number of pixel locations where images differ and use NULL to mark ablated pixels, distinct from black-valued pixels.For color images, a difference in any channel at a pixel location counts once.Source: Preliminaries and Notation · p. 3

Certifiably Robust Classification Scheme

The scheme defines a smoothed classifier by aggregating base-classifier predictions over uniformly sampled k-pixel subsets. Its certificate bounds how class probabilities can change under at most ρ pixel changes, then uses probability bounds to certify the perturbed classification.

Certifiably Robust Classification Scheme

  • The smoothed classifier returns the class with the highest probability after the base classifier evaluates an image with a uniformly sampled set of k pixels retained.Here, k is the retention constant; the base classifier is trained on images with some pixels ablated.Source: Certifiably Robust Classification Scheme · p. 3
  • When retained pixels exclude every changed index, the ablated versions of x and x′ are identical, bounding the difference in their class probabilities.The resulting bound depends on k and ρ.Source: Certifiably Robust Classification Scheme · pp. 3–4
  • If the lower bound on class i's probability minus Δ exceeds 0.5, the certificate guarantees g(x′) = i with probability at least 1 − α for perturbations of at most ρ pixels.The certificate applies to the population value of g(x′), not necessarily its empirical estimate.Source: Practical Robustness Certificates · p. 4
  • Separate sampling estimates the certificate probabilities and the smoothed classifier’s prediction; the classifier may abstain when top-class probabilities are too similar.Increasing the sample count can make estimation error arbitrarily small, and the estimation failure rate is independent of the certificate’s failure rate.Source: Practical Robustness Certificates · p. 4
  • In a multiclass setting, simultaneous bounds for all classes can increase estimation error when the number of classes is large.The stated total failure rate for the simultaneous bounds is 1 − α.Source: Practical Robustness Certificates · p. 4
  • Training uses ablated images and the same retention constant k as testing, with the same pixels ablated across images in each minibatch.For grayscale inputs, NULL is encoded as (0, 0), distinct from black, white, and gray; color inputs use six channels.Source: Architectural and training… · p. 5, Encoding SNULL · p. 5

Results

The results assess L0 certificates and empirical attack robustness on MNIST, CIFAR-10, and ImageNet. They also show how retained-pixel count affects MNIST certificates and report overfitting in CIFAR-10 base classifiers.

Results on MNIST

  • On MNIST, certified robustness and accuracy both rise with k initially, but beyond k = 45 robustness falls while accuracy continues to increase.The authors attribute the reversal to the certificate bound growing faster with perturbation size as k increases.Source: Results on MNIST · p. 5, Table 1 · p. 6
  • For the proposed MNIST classifier, the median empirical attack magnitude was 31 pixels, while the median certified lower bound was 8 pixels, placing them in the same order of magnitude.The Pointwise attack used a 275-image MNIST test subset, and abstention counted as a successful attack.Source: Results on MNIST · p. 6, Table 2 · p. 6

Results on CIFAR-10

  • At k = 150 on CIFAR-10, median certified robustness was 4 pixels and classification accuracy was 85.22%.The authors report that the accuracy–robustness trade-off was more pronounced on CIFAR-10 than on MNIST.Source: Results on CIFAR-10 · pp. 6–7
  • CIFAR-10 base classifiers significantly overfit; ResNet50 still overfits, but for k > 25 it overfits less than ResNet18.The higher-capacity model’s generalization-gap improvement was slight, and certificates were computed using ResNet18.Source: Table 5 · p. 7, Results on CIFAR-10 · p. 7

Results on ImageNet

  • 33 pixels was the median ImageNet certificate among correctly certified images at k = 1000; the corresponding medians among non-N/A certificates were 63 pixels at k = 500 and 16 pixels at k = 2000.Only 61% of the tested images were certified for the correct class, so misclassified images skew the overall median.Source: Results on ImageNet · p. 7, Table 6 · p. 7

Discussion

The discussion compares randomized ablation with Lee et al. (2019)’s randomized-noising certificate and examines the information carried by ablated samples and alternative NULL encodings.

Comparison to Lee et al. (2019)

Information content

Certification parameters

  • Repeating MNIST and ImageNet certifications with Lee et al. (2019)’s empirical certification parameters did not change the median robustness certificates.The comparison used 100 samples to select the class and 100,000 to bound it, with 99.9% confidence.Source: Comparison to (Lee et al. 2019) · p. 8

Information content

  • More than twice the information about the original image is available per ablated classification despite using slightly fewer pixels.The information calculation assumes a uniformly distributed dataset, an assumption the paper says does not hold for image classification.Source: Comparison to (Lee et al. 2019) · p. 8

Alternative encodings of SNULL

  • Using the training-set mean pixel value for NULL on MNIST and CIFAR-10 caused only marginal decreases in accuracy and certificate sizes.The tested retention values were k = 45 for MNIST and k = 75 for CIFAR-10.Source: Alternative encodings of SNULL · p. 8, Table 8 · p. 8
  • A mean-valued NULL remains distinguishable as an ablated pixel because the mean is not necessarily a common pixel value.Figure 4 contrasts NULL encodings and shows that random-noise replacement makes the image less easily distinguishable.Source: Alternative encodings of SNULL · p. 8, Figure 4 · p. 8

Conclusion

The conclusion presents randomized ablation as a smoothing-based certification method for sparse attacks. It reports non-trivial certificates on three datasets and an effective empirical defense on MNIST.

Conclusion

  • The method adapts smoothing-based robust classification to adversaries that perturb a limited number of input features.The conclusion models it after randomized smoothing for L1 and L2 attack models.Source: Conclusion · p. 9
  • The method produces non-trivial robustness certificates on MNIST, CIFAR-10, and ImageNet.Source: Conclusion · p. 9
  • The method is an effective empirical defense against L0 attacks on MNIST.Source: Conclusion · p. 9

MNIST

The supplied MNIST material points to the model architecture and training-parameter tables.

MNIST

  • The text directs readers to Tables 9 and 10 for the MNIST experiment details.Source: MNIST · p. 10
  • The MNIST base-classifier architecture is documented in Table 9.Its 2D convolution layers use 4-by-4 kernels, stride 2, and padding 1.Source: Table 9 · p. 10
  • MNIST training parameters are listed in Table 10.Source: Table 10 · p. 10

Training Parameters for CIFAR-10

The CIFAR-10 training-parameter table accompanies a ResNet18 base classifier modified to accept six input channels.

Training Parameters for CIFAR-10

Training Parameters for ImageNet

The ImageNet base classifier uses ResNet50 with its input channels increased from 3 to 6; training parameters are listed in Table 12.

Training Parameters for ImageNet

Mutual information derivation for Lee et al.

The derivation assumes a uniformly distributed original image and models each pixel as retained or replaced by a different value. Independence and symmetry then simplify the mutual-information expression to the one given in the text.

Mutual information derivation for Lee et al.

  • The derivation assumes the original image is uniformly distributed over S^d, with each component independently uniform on S.Each output component retains its original value with probability κ or takes a uniformly selected different value with probability 1 − κ.Source: Mutual information derivation for Lee… · p. 10
  • Independence across pixel pairs allows the mutual-information expression to be factorized.The derivation then applies entropy and mutual-entropy definitions.Source: Mutual information derivation for Lee… · p. 10
  • By symmetry, the altered pixel Y◦ is also uniformly distributed on S.The joint probabilities are separated into equal-value and distinct-value cases.Source: Mutual information derivation for Lee… · pp. 10–11
  • The equal-value joint probability is |S|^-1κ, while distinct-value probabilities account for replacement and uniform selection among other values.The resulting terms are constants, so summing over S and distinct pairs reduces to multiplying by their counts; the derivation simplifies to the expression in the text.Source: Mutual information derivation for Lee… · p. 11

Additional Adversarial Examples

Figure 5 shows additional MNIST adversarial examples generated against the robust classifier using the Pointwise attack with k = 45.

Additional Adversarial Examples

  • Figure 5 presents MNIST adversarial examples generated by the Pointwise attack against the robust classifier.The examples use k = 45.Source: Figure 5 · p. 12
  • The figure’s examples are generated on MNIST.They are additional examples for the paper’s robust classifier.Source: Figure 5 · p. 12
  • The Pointwise attack is shown with k = 45.The caption does not report an outcome comparison.Source: Figure 5 · p. 12

Related papers

Loading 1911.09272v1…