Title: TOWARDS THE FIRST ADVERSARIALLY ROBUST NEURAL NETWORK MODEL ON MNIST

Abstract: Despite much effort, deep neural networks remain highly susceptible to tiny input perturbations and even for MNIST, one of the most common toy datasets in computer vision, no neural network model exists for which adversarial perturbations are large and make semantic sense to humans. We show that even the widely recognized and by far most successful L ∞ defense by Madry et al. (1) has lower L 0 robustness than undefended networks and is still highly susceptible to L 2 perturbations, (2) classifies unrecognizable images with high certainty, (3) performs not much better than simple input binarization and (4) features adversarial perturbations that make little sense to humans. These results suggest that MNIST is far from being solved in terms of adversarial robustness. We present a novel robust classification model that performs analysis by synthesis using learned class-conditional data distributions. We derive bounds on the robustness and go to great length to empirically evaluate our model using maximally effective adversarial attacks by (a) applying decision-based, score-based, gradient-based and transfer-based attacks for several different L p norms, (b) by designing a new attack that exploits the structure of our defended model and (c) by devising a novel decision-based attack that seeks to minimize the number of perturbed pixels (L 0 ). The results suggest that our approach yields state-of-the-art robustness on MNIST against L 0 , L 2 and L ∞ perturbations and we demonstrate that most adversarial examples are strongly perturbed towards the perceptual boundary between the original and the adversarial class.

1. INTRODUCTION:

Deep neural networks (DNNs) are strikingly susceptible to minimal adversarial perturbations (Szegedy et al., 2013) , perturbations that are (almost) imperceptible to humans but which can switch the class prediction of DNNs to basically any desired target class.

One key problem in finding successful defenses is the difficulty of reliably evaluating model robustness. It has been shown time and again (Athalye et al., 2018; Athalye & Carlini, 2018; Brendel & Bethge, 2017 ) that basically all defenses previously proposed did not increase model robustness but prevented existing attacks from finding minimal adversarial examples, the most common reason being masking of the gradients on which most attacks rely. The few verifiable defenses can only guarantee robustness within a small linear regime around the data points (Hein & Andriushchenko, 2017; Raghunathan et al., 2018) .

The only defense currently considered effective (Athalye et al., 2018) is a particular type of adversarial training (Madry et al., 2018) . On MNIST, as of today this method is able to reach an accuracy of 88.79% for adversarial perturbations with an L ∞ norm bounded by = 0.3 (Zheng et al., 2018) . In other words, if we allow an attacker to perturb the brightness of each pixel by up to 0.3 (range [0, 1]), then he can only trick the model on ≈ 10% of the samples. This is a great success, but does the model really learn more causal features to classify MNIST? We here demonstrate that this is not the case: For one, the defense by Madry et al. (SOTA on L ∞ ) has lower L 0 robustness than undefended networks and is still highly susceptible in the L 2 metric. Second, the robustness results by Madry et al. can also be achieved with a simple input quantization because of the binary nature of single pixels in MNIST (which are typically either completely black or white) (Schmidt et al., 2018) . Third, it is straight-forward to find unrecognizable images that are classified as a digit with high certainty. Finally, the minimum adversarial examples we find for the defense by Madry et al. make little to no sense to humans.

Taken together, even MNIST cannot be considered solved with respect to adversarial robustness. By "solved" we mean a model that reaches at least 99% accuracy (see accuracy-vs-robustness trade-off (Tsipras et al., 2018; Bubeck et al., 2018) ) and whose adversarial examples carry semantic meaning to humans (by which we mean that they start looking like samples that could belong to either class). Hence, despite the fact that MNIST is considered "too easy" by many and a mere toy example, finding adversarially robust models on MNIST is still an open problem.

A potential solution we explore in this paper is inspired by unrecognizable images (Nguyen et al., 2015) or distal adversarials. Distal adversarials are images that do not resemble images from the training set but which typically look like noise while still being classified by the model with high confidence. It seems difficult to prevent such images in feedforward networks as we have little control over how inputs are classified that are far outside of the training domain. In contrast, generative models can learn the distribution of their inputs and are thus able to gauge their confidence accordingly. By additionally learning the image distribution within each class we can check that the classification makes sense in terms of the image features being present in the input (e.g. an image of a bus should contain actual bus features). Following this line of thought from an information-theoretic perspective, one arrives at the well-known concept of Bayesian classifiers. We here introduce a fine-tuned variant based on variational autoencoders (Kingma & Welling, 2013 ) that combines robustness with high accuracy.

In summary, the contributions of this paper are as follows:

• We show that MNIST is unsolved from the point of adversarial robustness: the SOTA defense of Madry et al. (2018) is still highly vulnerable to tiny perturbations that are meaningless to humans. • We introduce a new robust classification model and derive instance-specific robustness guarantees.

• We develop a strong attack that leverages the generative structure of our classification model.

• We introduce a novel decision-based attack that minimizes L 0 .

• We perform an extensive evaluation of our defense across many attacks to show that it surpasses SOTA on L 0 , L 2 and L ∞ and features many adversarials that carry semantic meaning to humans.

We have evaluated the proposed defense to the best of our knowledge, but we are aware of the (currently unavoidable) limitations of evaluating robustness. We will release the model architecture and trained weights as a friendly invitation to fellow researchers to evaluate our model independently.

2. RELATED WORK:

The many defenses against adversarial attacks can roughly be subdivided into four categories:

• Adversarial training: The training data is augmented with adversarial examples to make models more robust (Madry et al., 2018; Szegedy et al., 2013; Tramèr et al., 2017; Ilyas et al., 2017) . • Manifold projections: An input sample is projected onto a learned data manifold (Samangouei et al., 2018; Ilyas et al., 2017; Shen et al., 2017; Song et al., 2018) . • Stochasticity: Certain inputs or hidden activations are shuffled or randomized (Prakash et al., 2018; Dhillon et al., 2018; Xie et al., 2018) . • Preprocessing: Inputs or hidden activations are quantized, projected into a different representation or are otherwise preprocessed (Buckman et al., 2018; Guo et al., 2018; Kabilan et al., 2018) .

There has been much work showing that basically all defenses suggested so far in the literature do not substantially increase robustness over undefended neural networks (Athalye et al., 2018; Brendel & Bethge, 2017). The only widely accepted exception according to Athalye et al. (2018) is the defense by Madry et al. (2018) which is based on data augmentation with adversarials found by iterative projected gradient descent with random starting points. However, as we see in the results section, this defense is limited to the metric it is trained on (L ∞ ) and it is straight-forward to generate small adversarial perturbations that carry little semantic meaning for humans.

Some other defenses have been based on generative models. Typically these defenses use the generative model to project onto the (learned) manifold of "natural" inputs. This includes in particular DefenseGAN (Samangouei et al., 2018) , Adversarial Perturbation Elimination GAN (Shen et al., 2017) and Robust Manifold Defense (Ilyas et al., 2017) , all of which project an image onto the manifold defined by a generator network G. The generated image is then classified by a discriminator in the usual way. A similar idea is used by PixelDefend (Song et al., 2018) which uses an autoregressive probabilistic method to learn the data manifold. Other ideas in similar directions include the use of denoising autoencoders (Liao et al., 2017) as well as MagNets (Meng & Chen, 2017) , which projects or rejects inputs depending on their distance to the data manifold. All of these proposed defenses except for the defense by Ilyas et al. (2017) have been tested by Athalye et al. (2018) ; Athalye & Carlini (2018) ; Carlini & Wagner (2017) and others, and shown to be ineffective. It is straight-forward to understand why: For one, many adversarials still look like normal data points to humans. Second, the classifier on top of the projected image is as vulnerable to adversarial examples as before. Hence, for any data set with a natural amount of variation there will almost always be a certain perturbation against which the classifier is vulnerable and which can be induced by the right inputs.

We here follow a different approach by modeling the input distribution within each class (instead of modeling a single distribution for the complete data), and by classifying a new sample according to the class under which it has the highest likelihood. This approach, commonly referred to as a Bayesian classifier, gets away without any additional and vulnerable classifier. A very different but related approach is the work by George et al. (2017) which suggested a generative compositional model of digits to solve cluttered digit scenes like Captchas (adversarial robustness was not evaluated).

3. MODEL DESCRIPTION:

Intuitively, we want to learn a causal model of the inputs (Schölkopf, 2017) . Consider a cat: we want a model to learn that cats have four legs and two pointed ears, and then use this model to check whether a given input can be generated with these features. This intuition can be formalized as follows. Let (x, y) with x ∈ R N be an input-label datum. 

EQUATION

where p(z) = N (0, 1) is a simple normal prior and q φ (z|x, y) is the variational posterior with parameters φ. The first term on the RHS is basically a reconstruction error while the second term on the RHS is the mismatch between the variational and the true posterior. The term on the RHS is the so-called evidence lower bound (ELBO) on the log-likelihood (Kingma & Welling, 2013) . We implement the conditional distributions p θ (x|z, y) and q φ (z|x, y) as normal distributions for which the means are parametrized as DNNs (all details and hyperparameters are reported in Appendix A.7).

Our Analysis by Synthesis model (ABS) is illustrated in Figure 1 . It combines several elements to simultaneously achieve high accuracy and robustness against adversarial perturbations:

• Class-conditional distributions: For each class y we train a variational autoencoder VAE y on the samples of class y to learn the class-conditional distribution p(x|y). This allows us to estimate a lower bound y (x) on the log-likelihood of sample x under each class y. • Optimization-based inference: The variational inference q φ (z|x, y) is itself a neural network susceptible to adversarial perturbations. We therefore only use variational inference during training and perform "exact" inference over p θ (x|z, y) during evaluation. This "exact" inference is implemented using gradient descent in the latent space (with fixed posterior width) to find the optimal z y which maximizes the lower bound on the log-likelihood for each class: *

EQUATION

Note that we replaced the expectation in equation 2 with a maximum likelihood sample to avoid stochastic sampling and to simplify optimization. To avoid local minima we evaluate 8000 random points in the latent space of each VAE, from which we pick the best as a starting point for a gradient descent with 50 iterations using the Adam optimizer (Kingma & Ba, 2014). • Classification and confidence: Finally, to perform the actual classification, we scale all * y (x) with a factor α, exponentiate, add an offset η and divide by the total evidence (like in a softmax),

EQUATION

We introduced η for the following reason: even on points far outside the data domain, where all likelihoods q(x, y) = e α * y (x) + η are small, the standard softmax (η = 0) can lead to sharp posteriors p(y|x) with high confidence scores for one class. This behavior is in stark contrast to humans, who would report a uniform distribution over classes for unrecognizable images.

To model this behavior we set η > 0: in this case the posterior p(y|x) converges to a uniform distribution whenever the maximum q(x, y) gets small relative to η . We chose η such that the median confidence p(y|x) is 0.9 for the predicted class on clean test samples. Furthermore, for a better comparison with cross-entropy trained networks, the scale α is trained to minimize the cross-entropy loss. We also tested this graded softmax in standard feedforward CNNs but did not find any improvement with respect to unrecognizable images. On important ingredient for the robustness of the ABS model is the Gaussian posterior in the reconstruction term which ensures that small changes in the input (in terms of L2) can only entail small changes to the posterior likelihood and thus to the model decision.

4. TIGHT ESTIMATES OF THE LOWER BOUND FOR ADVERSARIAL EXAMPLES:

The decision of the model depends on the likelihood in each class, which for clean samples is mostly dominated by the posterior likelihood p(x|z). Because we chose this posterior to be Gaussian, the class-conditional likelihoods can only change gracefully with changes in x, a property which allows us to derive lower bounds on the model robustness. To see this, note that equation 3 can be written as, *

EQUATION

where we absorbed the normalization constants of p(x|z) into C and G c (z) is the mean of p(x|z, c).

Let y be the ground-truth class and let z * x be the optimal latent for the clean sample x for class y. We can then estimate a lower bound on * y (x + δ) for a perturbation δ with size = δ 2 (see derivation in Appendix A.4), *

EQUATION

Likewise, we can derive an upper bound of * y (x + δ) for all other classes c = y (see Appendix A.5), *

EQUATION

)

for d c = min z G c (z)x 2 . Now we can find for a given image x by equating (7) = ( 6),

EQUATION

)

Note that one assumption we make is that we can find the global minimum of G c (z)x 2 2 . In practice we generally find a very tight estimate of the global minimum (and thus the lower bound) because we optimize in a smooth and low-dimensional space and because we perform an additional brute-force sampling step. We provide quantitative values for in section 7.

5. ADVERSARIAL ATTACKS:

Reliably evaluating model robustness is difficult because each attack only provides an upper bound on the size of the adversarial perturbations (Uesato et al., 2018) . To make this bound as tight as possible we apply many different attacks and choose the best one for each sample and model combination (using the implementations in Foolbox v1.3 (Rauber et al., 2017) which often perform internal hyperparameter optimization). We also created a novel decision-based L 0 attack as well as a customized attack that specifically exploits the structure of our model. Nevertheless, we cannot rule out that more effective attacks exist and we will release the trained model for future testing.

Latent Descent attack This novel attack exploits the structure of the ABS model. Let x t be the perturbed sample x in iteration t. We perform variational inference p(z|x t , y) = N (µ y (x t ), σ q I) to find the most likely class ỹ that is different from the ground-truth class. We then make a step towards the maximum likelihood posterior p(x|z, ỹ) of that class which we denote as xỹ ,

EQUATION

We choose = 10 -2 and iterate until we find an adversarial. For a more precise estimate we perform a subsequent binary search of 10 steps within the last interval. Finally, we perform another binary search between the adversarial and the original image to reduce the perturbation as much as possible.

Decision-based attacks We use several decision-based attacks because they do not rely on gradient information and are thus insensitive to gradient masking or missing gradients. In particular, we apply the Boundary Attack (Brendel et al., 2018) , which is competitive with gradient-based attacks in minimizing the L 2 norm, and introduce the Pointwise Attack, a novel decision-based attack that greedily minimizes the L 0 norm. It first adds salt-and-pepper noise until the image is misclassified and then repeatedly iterates over all perturbed pixels, resetting them to the clean image if the perturbed image stays adversarial. The attack ends when no pixel can be reset anymore. We provide an implementation of the attack in Foolbox (Rauber et al., 2017) . Finally, we apply two simple noise attacks, the Gaussian Noise attack and the Salt&Pepper Noise attack as baselines. Transfer-based attacks Transfer attacks also don't rely on gradients of the target model but instead compute them on a substitute: given an input x we first compute adversarial perturbations δ on the substitute using different gradient-based attacks (L 2 and L ∞ Basic Iterative Method (BIM), Fast Gradient Sign Method (FGSM) and L 2 Fast Gradient Method) and then perform a line search to find the smallest for which x + δ (clipped to the range [0, 1]) is still an adversarial for the target model.

Gradient-based attacks:

We apply the Momentum Iterative Method (MIM) (Dong et al., 2017 ) that won the NIPS 2017 adversarial attack challenge, the Basic Iterative Method (BIM) (Kurakin et al., 2016) (also known as Projected Gradient Descent (PGD))-for both the L 2 and the L ∞ norm-as well as the Fast Gradient Sign Method (FGSM) (Goodfellow et al., 2014) and its L 2 variant, the Fast Gradient Method (FGM). For models with input binarization (Binary CNN, Binary ABS), we obtain gradients using the straight-through estimator (Bengio et al., 2013) .

Score-based attacks:

We additionally run all attacks listed under Gradient-based attacks using numerically estimated gradients (possible for all models). We use a simple coordinate-wise finite difference method (NES estimates (Ilyas et al., 2018) performed comparable or worse) and repeat the attacks with different values for the step size of the gradient estimator.

Postprocessing (binary models only) For models with input binarization (sec. 6) we postprocess all adversarials by setting pixel intensities either to the corresponding value of the clean image or the binarization threshold (0.5). This reduces the perturbation size without changing model decisions.

6. EXPERIMENTS:

We compare our ABS model as well as two ablations-ABS with input binarization during test time (Binary ABS) and a CNN with input binarization during train and test time (Binary CNN)-against three other models: the SOTA L ∞ defense (Madry et al., 2018) 1 , a Nearest Neighbour (NN) model (as a somewhat robust but not accurate baseline) and a vanilla CNN (as an accurate but not robust baseline), see Appendix A.7. We run all attacks (see sec. 5) against all applicable models.

For each model and L p norm, we show how the accuracy of the models decreases with increasing adversarial perturbation size (Figure 2 ) and report two metrics: the median adversarial distance (Table 1 , left values) and the model's accuracy against bounded adversarial perturbations (Table 1 , right values). The median of the perturbation sizes (Table 1 , left values) is robust to outliers and summarizes most of the distributions quite well. It represents the perturbation size for which the particular model achieves 50% accuracy and does not require the choice of a threshold. Clean samples that are already misclassified are counted as adversarials with a perturbation size equal to 0, failed attacks as ∞. The commonly reported model accuracy on bounded adversarial perturbations, on the other hand, requires a metric-specific threshold that can bias the results. We still report it ( 

7. RESULTS:

Minimal Adversarials Our robustness evaluation results of all models are reported in Table 1 and Figure 2 . All models except the Nearest Neighbour classifier perform close to 99% accuracy on clean test samples. We report results for three different norms: L 2 , L ∞ and L 0 .

• For L 2 our ABS model outperforms all other models by a large margin.

• For L ∞ , our Binary ABS model is state-of-the-art in terms of median perturbation size. In terms of accuracy (perturbations < 0.3), Madry et al. seems more robust. However, as revealed by the accuracy-distortion curves in Figure 2 , this is an artifact of the specific threshold (Madry et al. is optimized for 0.3). A slightly larger one (e.g. 0.35) would strongly favor the Binary ABS model. • For L 0 , both ABS and Binary ABS are much more robust than all other models. Interestingly, the model by Madry et al. is the least robust, even less than the baseline CNN.

In Figure 3 

8. DISCUSSION & CONCLUSION:

In this paper we demonstrated that, despite years of work, we as a community failed to create neural networks that can be considered robust on MNIST from the point of human perception. In particular, we showed that even today's best defense is susceptible to small adversarial perturbations that make little to no semantic sense to humans. We presented a new approach based on analysis by synthesis that seeks to explain its inference by means of the actual image features. We performed an extensive analysis to show that minimal adversarial perturbations in this model are large across all tested L p norms and semantically meaningful to humans. Note that our architecture derives its robustness from its design and does not require any additionally training with adversarial examples.

We acknowledge that it is not easy to reliably evaluate a model's adversarial robustness and most defenses proposed in the literature have later been shown to be ineffective. In particular, the structure of the ABS model prevents the computation of gradients which might give the model an unfair advantage. We put a lot of effort into an extensive evaluation of adversarial robustness using a large collection of powerful attacks, including one specifically designed to be particularly effective against the ABS model (the Latent Descent attack), and we will release the model architecture and trained weights as a friendly invitation to fellow researchers to evaluate our model.

Looking at the results of individual attacks (Table 1 ) we find that there is no single attack that works best on all models, thus highlighting the importance for a broad range of attacks. Without the Boundary Attack, for example, Madry et al. would have looked more robust to L 2 adversarials than it is. For similar reasons Figure 6b of Madry et al. (2018) reports a median L 2 perturbation size larger than 5, compared to the 1.4 achieved by the Boundary Attack. Moreover,the combination of all attacks of one metric (All L 2 / L ∞ / L 0 Attacks) is often better than any individual attack, indicating that different attacks are optimal on different samples.

Our conceptual implementation of the ABS model with one VAE per class neither scales efficiently to more classes nor to more complex datasets (a preliminary experiment on CIFAR10 provided only 54% test accuracy). However, first experiments on two class CIFAR indicate that the proposed model is also robust on CIFAR (we reach a median L2 robustness of 2.6 compared to 0.8 for a vanilla CNN, see Appendix A.1) for details). To increase the accuracy, there are many ways in which the ABS model can be improved, ranging from better and faster generative models (e.g. flow-based) to better training procedures.

In a nutshell, we demonstrated that MNIST is still not solved from the point of adversarial robustness and showed that our novel approach based on analysis by synthesis has great potential to reduce the vulnerability against adversarial attacks and to align machine perception with human perception.

A APPENDIX:

A.1 TWO CLASS CIFAR

We estimate the robustness of our ABS model on two class CIFAR (airplane vs. automobile). Preliminary results suggest that our robustness is not limited to MNIST.

In order to adapt to CIFAR, we modified the ABS slightly by modifying encoder and decoder to fit (32x32x3) CIFAR images. We also increased the number of dimensions in the latent space form 8 to 20. where p(z) = N (0, 1) is a simple normal prior. Based on the idea of importance sampling using a variational posterior q φ (z|x) with parameters φ and using Jensen's inequality we arrive at

Model:

= log dz q φ (z|x) q φ (z|x) p θ (x|z)p(z), = log E z∼q φ (z|x) p θ (x|z)p(z) q φ (z|x) , ≥ E z∼q φ (z|x) log p θ (x|z)p(z) q φ (z|x) , = E z∼q φ (z|x) log p θ (x|z) + log p(z) q φ (z|x) , = E z∼q φ (z|x) [log p θ (x|z)] -DKL [q φ (z|x)||p(z)] .

This lower bound is commonly referred to as ELBO.

A 

(x + δ) = max z -DKL [N (z, σq1)||N (0, 1)] - 1 2σ 2 Gy(z) -x -δ 2 2 + C, ≥ -DKL [N (z * x , σq1)||N (0, 1)] - 1 2σ 2 Gy(z * x ) -x -δ 2 2 + C,

where z * x is the optimal latent vector for the clean sample x for class y,

EQUATION

A.5 DERIVATION III: 

EQUATION

EQUATION

let y be the predicted class and let z * x be the optimal latent for the clean sample x for class y. We can then estimate a lower bound on * y (x + δ) for a perturbation δ with size = δ ∞ , * y

(x + δ) = max z -DKL [N (z, σq1)||N (0, 1)] - 1 2σ 2 Gy(z) -x -δ 2 2 + C, ≥ -DKL [N (z * x , σq1)||N (0, 1)] - 1 2σ 2 Gy(z * x ) -x -δ 2 2 + C,

where z * x is the optimal latent for the clean sample x for class y. 

In this case there is no closed-form solution for the minimization problem on the RHS (in terms of the minimum of Gc(z) -x 2 ) but we can still compute the solution for each given which allows us perform a line search along to find the point where equation 13 = equation 14.

A.7 MODEL & TRAINING DETAILS:

Hyperparameters and training details for the ABS model The binary ABS and ABS have the same weights and architecture: The encoder has 4 layers with kernel sizes= [5, 4, 3, 5] , strides= [1, 2, 2, 1] and feature map sizes= [32, 32, 64, 2 * 8] . The first 3 layers have ELU activation functions (Clevert et al., 2015) , the last layer is linear. All except the last layer use Batch Normalization (Ioffe & Szegedy, 2015) . The Decoder architecture has also 4 layers with kernel sizes= [4, 5, 5, 3] , strides= [1, 2, 2, 1] and feature map sizes= [32, 16, 16, 1] . The first 3 layers have ELU activation functions, the last layer has a sigmoid activation function, and all layers except the last one use Batch Normalization.

We trained the VAEs with the Adam optimizer (Kingma & Ba, 2014) . We tuned the dimension L of the latent space of the class-conditional VAEs (ending up with L = 8) to achieve 99% test error; started with a high weight for the KL-divergence term at the beginning of training (which was gradually decreased from a factor of 10 to 1 over 50 epochs); estimated the weighting γ = [1, 0.96, 1.001, 1.06, 0.98, 0.96, 1.03, 1, 1, 1] of the lower bound via a line search on the training accuracy. The parameters maximizing the test cross entropy3 and providing a median confidence of p(y|x) = 0.9 for our modified softmax (equation 8) are η = 0.000039 and α = 440. For our latent prior, we chose σq = 1 and for the posterior width we choose σ = 1/ √ 2

Hyperparameters for the CNNs The CNN and Binary CNN share the same architecture but have different weights. The architecture has kernel sizes = [5, 4, 3, 5] , strides = [1, 2, 2, 1], and feature map sizes = [20, 70, 256, 10] . All layers use ELU activation functions and all layers except the last one apply Batch Normalization. The CNNs are both trained on the cross entropy loss with the Adam optimizer (Kingma & Ba, 2014) . The parameters maximizing the test cross entropy and providing a median confidence of p(y|x) = 0.9 of the CNN for our modified softmax (equation 8) are η = 143900 and α = 1.

:

We used the trained model provided by the authors: https://github.com/MadryLab/mnist_challenge

The mean instead of the median is reported to allow for a comparison with(Hein & Andriushchenko, 2017).

Note that this solely scales the probabilities and does not change the classification accuracy.

https://github.com/MadryLab/mnist_challenge

Figures and Tables:

Figure 1: Overview over model architecture. In a nutshell: I) for each sample x we compute a lower bound on the log-likelihood (ELBO) under each class using gradient descent in the latent space. II) A class-dependent scalar weighting of the class-conditional ELBOs forms the final class prediction.

Binarization (Binary ABS only): The pixel intensities of MNIST images are almost binary. We exploit this by projecting the intensity b of each pixel to 0 if b < 0.5 or 1 if b ≥ 0.5 during testing. • Discriminative finetuning (Binary ABS only): To improve the accuracy of the Binary ABS model we multiply * y (x) with an additional class-dependent scalar γ y . The scalars are learned discriminatively (see A.7) and reach values in the range γ y ∈ [0.96, 1.06] for all classes y.

Figure 2: Accuracy-distortion plots for each distance metric and all models. In (b) we see that a threshold at 0.3 favors Madry et al. while a threshold of 0.35 would have favored the Binary ABS.

Figure 3: Adversarial examples for the ABS models are perceptually meaningful: For each sample (randomly chosen from each class) we show the minimally perturbed L 2 adversarial found by any attack. Our ABS models have clearly visible and often semantically meaningful adversarials. Madry et al. requires perturbations that are clearly visible, but their semantics are less clear. imperceptible. The Nearest Neighbour model, almost by design, exposes (some) adversarials that interpolate between two numbers. The model by Madry et al. requires perturbations that are clearly visible but make little semantic sense to humans. Finally, adversarials generated for the ABS models are semantically meaningful for humans and are sitting close to the perceptual boundary between the original and the adversarial class. For a more thorough comparison see appendix Figures 5, 6 and 7.

Figure5: L 0 error quantiles: We always choose the minimally perturbed L 0 adversarial found by any attack for each model. For an unbiased selection, we then randomly sample images within four error quantiles (0 -25%, 25 -50%, 50 -75%, and 75 -100%). Where 100% corresponds to the maximal (over samples) minimum (over attacks) perturbation found for each model.

Figure 6: L 2 error quantiles: We always choose the minimally perturbed L 2 adversarial found by any attack for each model. For an unbiased selection, we then randomly sample 4 images within four error quantiles (0 -25%, 25 -50%, 50 -75%, and 75 -100%).

Figure 7: L ∞ error quantiles: We always choose the minimally perturbed L ∞ adversarial found by any attack for each model. For an unbiased selection, we then randomly sample images within four error quantiles (0 -25%, 25 -50%, 50 -75%, and 75 -100%).

can estimate an upper bound on * c (x + δ) on all other classes c = y, * c(x + δ) ≤ -DKL [N (0, σq1)||N (0, 1)] + C -min z 1 2σ 2 Gc(z) -xδ 2 2 , ≤ -DKL [N (0, σq1)||N (0, 1)] + C -min z,δ 1 2σ 2 Gc(z) -xδ 2 2 , = -DKL [N (0, σq1)||N (0, 1)] + C -min (z) -x]i -δi) 2 , = -DKL [N (0, σq1)||N (0, 1)] Gy(z * x ) -x]i| ≤ ([Gy(z * x ) -x]i -) 2 if [Gy(z * x ) -x]i > ([Gy(z * x ) -x]i + ) 2 if [Gy(z * x ) -x]i < .

Results for different models, adversarial attacks and distance metrics. Each entry shows the median adversarial distance across all samples (left value, black) as well as the model's accuracy against adversarial perturbations bounded by the thresholds L2 = 1.5,

Table content: <table><tr><td/><td>CNN</td><td>Binary CNN</td><td>Nearest Neighbor</td><td>Madry et al.</td><td>Binary ABS</td><td>ABS</td></tr><tr><td>Clean</td><td>99.1%</td><td>98.5%</td><td>96.9%</td><td>98.8%</td><td>99.0%</td><td>99.0%</td></tr><tr><td>L2-metric ( = 1.5)</td><td/><td/><td/><td/><td/><td/></tr><tr><td>Transfer Attacks</td><td colspan="6">1.1 / 14% 1.4 / 38% 5.4 / 90% 3.7 / 94% 2.5 / 86% 4.6 / 94%</td></tr><tr><td>Gaussian Noise</td><td colspan="2">5.2 / 96% 3.4 / 92%</td><td colspan="4">∞ / 91% 5.4 / 96% 5.6 / 89% 10.9 / 98%</td></tr><tr><td>Boundary Attack</td><td colspan="6">1.2 / 21% 3.3 / 84% 2.9 / 73% 1.4 / 37% 6.0 / 91% 2.6 / 83%</td></tr><tr><td>Pointwise Attack</td><td colspan="6">3.4 / 91% 1.9 / 71% 3.5 / 89% 1.9 / 71% 3.1 / 86% 4.6 / 94%</td></tr><tr><td>FGM</td><td colspan="2">1.4 / 48% 1.4 / 50%</td><td/><td>∞ / 96%</td><td/><td/></tr><tr><td>FGM w/ GE</td><td colspan="3">1.4 / 42% 2.8 / 51% 3.7 / 79%</td><td colspan="3">∞ / 88% 1.9 / 68% 3.5 / 89%</td></tr><tr><td>DeepFool</td><td colspan="2">1.2 / 18% 1.0 / 11%</td><td/><td>9.0 / 91%</td><td/><td/></tr><tr><td>DeepFool w/ GE</td><td colspan="6">1.3 / 30% 0.9 / 5% 1.6 / 55% 5.1 / 90% 1.4 / 41% 2.4 / 83%</td></tr><tr><td>L2 BIM</td><td colspan="2">1.1 / 13% 1.0 / 11%</td><td/><td>4.8 / 88%</td><td/><td/></tr><tr><td>L2 BIM w/ GE</td><td>1.1 / 37%</td><td colspan="5">∞ / 50% 1.7 / 62% 3.4 / 88% 1.6 / 63% 3.1 / 87%</td></tr><tr><td>Latent Descent Attack</td><td/><td/><td/><td/><td colspan="2">2.6 / 97% 2.7 / 85%</td></tr><tr><td>All L2 Attacks</td><td colspan="6">1.1 / 8% 0.9 / 3% 1.5 / 53% 1.4 / 35% 1.3 / 39% 2.3 / 80%</td></tr><tr><td>L∞-metric ( = 0.3)</td><td/><td/><td/><td/><td/><td/></tr><tr><td>Transfer Attacks</td><td colspan="6">0.08 / 0% 0.44 / 85% 0.42 / 78% 0.39 / 92% 0.49 / 88% 0.34 / 73%</td></tr><tr><td>FGSM</td><td colspan="2">0.10 / 4% 0.43 / 77%</td><td/><td>0.45 / 93%</td><td/><td/></tr><tr><td>FGSM w/ GE</td><td colspan="6">0.10 / 21% 0.42 / 71% 0.38 / 68% 0.47 / 89% 0.49 / 85% 0.27 / 34%</td></tr><tr><td>L∞ DeepFool</td><td colspan="2">0.08 / 0% 0.38 / 74%</td><td/><td>0.42 / 90%</td><td/><td/></tr><tr><td>L∞ DeepFool w/ GE</td><td colspan="6">0.09 / 0% 0.37 / 67% 0.21 / 26% 0.53 / 90% 0.46 / 78% 0.27 / 39%</td></tr><tr><td>BIM</td><td colspan="2">0.08 / 0% 0.36 / 70%</td><td/><td>0.36 / 90%</td><td/><td/></tr><tr><td>BIM w/ GE</td><td>0.08 / 37%</td><td colspan="5">∞ / 70% 0.25 / 43% 0.46 / 89% 0.49 / 86% 0.25 / 13%</td></tr><tr><td>MIM</td><td colspan="2">0.08 / 0% 0.37 / 71%</td><td/><td>0.34 / 90%</td><td/><td/></tr><tr><td>MIM w/ GE</td><td>0.09 / 36%</td><td colspan="5">∞ / 69% 0.19 / 26% 0.36 / 89% 0.46 / 85% 0.26 / 17%</td></tr><tr><td>All L∞ Attacks</td><td colspan="6">0.08 / 0% 0.34 / 64% 0.19 / 22% 0.34 / 88% 0.44 / 77% 0.23 / 8%</td></tr><tr><td>L0-metric ( = 12)</td><td/><td/><td/><td/><td/><td/></tr><tr><td>Salt&amp;Pepper Noise</td><td colspan="6">44.0 / 91% 44.0 / 88% 161.0 / 88% 13.5 / 56% 146.0 / 94% 165.0 / 94%</td></tr><tr><td>Pointwise Attack 10x</td><td colspan="6">9.0 / 19% 11.0 / 39% 10.0 / 34% 4.0 / 0% 22.0 / 77% 16.5 / 69%</td></tr><tr><td>All L0 Attacks</td><td colspan="6">9.0 / 19% 11.0 / 38% 10.0 / 34% 4.0 / 0% 21.5 / 77% 16.5 / 69%</td></tr></table>

Accuracy and estimated robustness on two class CIFAR.

Table content: <table><tr><td/><td/><td/><td>CNN</td><td>ABS</td></tr><tr><td/><td colspan="2">Accuracy</td><td>97.1%</td><td>89.7%</td></tr><tr><td/><td colspan="3">Median L 2 distance 0.8 (with BIM) 2.5 (with Latent Descent attack)</td></tr><tr><td colspan="2">A.2 FIGURES</td><td/></tr><tr><td/><td>CNN</td><td/></tr><tr><td>1.Quantile</td><td>5→3</td><td>1→5</td></tr><tr><td/><td>9→3</td><td>5→3</td></tr><tr><td>2.Quantile</td><td/><td/></tr></table>

.4 DERIVATION II: LOWER BOUND FOR L 2 ROBUSTNESS ESTIMATION

Table content: <table/>

)for dc = minz Gc(z) -x 2 . The last equation comes from the solution of the constrained optimization problem min d (d -) 2 d s.t. d > dc. Note that a tighter bound might be achieved by assuming single δ for upper and lower bound.

Table content: <table/>

Peer review (iclr2019):
 In this paper, the authors argued that the current approaches are not robust to adversarial attacks, even for MNIST. They proposed a generative approach for classification, which uses variational autoencoder (VAE) to estimate the class specific feature distribution. Robustness guarantees are derived for their model. Through numeric studies, they demonstrated the performance of their proposal (ABS). They also demonstrated that many of the adversarial examples for their ABS model are actually meaningful to humans, which are different from existing approaches, such as SOTA. Overall this is a well written paper. The presentation of their methodology is clear, so are the numerical studies. Some comments: 1) it was not very clear to me that the authors were estimating the p(x) for each y. The transition from p(x|y) to p(x) at the end of page 3 was astute and confused me. The authors should make it more clear. 2) it would be beneficial if the authors could comment on the how strict/loose the lower bound of (2) is, as it is critical in estimating the class specific density.