{'fraction_non_alphanumeric': 0.034815944920392757, 'fraction_numerical': 0.011931306967100888, 'mean_word_length': 4.647006847802077, 'pattern_counts': {'":': 0, '<': 2, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Towards the first adversarially robust neural network model on MNIST

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 defense by Madry et al. (1) overfits on the L-infinity metric (it's highly susceptible to L2 and L0 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 Lp 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 (L0). The results suggest that our approach yields state-of-the-art robustness on MNIST against L0, L2 and L-infinity perturbations and we demonstrate that most adversarial examples are strongly perturbed towards the perceptual boundary between the original and the adversarial class.


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 ) 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  is a particular type of adversarial training . 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. overfits on L ∞ in the sense that adversarial perturbations in the L 2 and L 0 metric are as small as for undefended networks. Second, the robustness results by Madry et al. can also be achieved with a simple input quantisation because of the binary nature of single pixels in MNIST (which are typically either completely black or white) . 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 (Gilmer 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  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 minimzes 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.
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 . The only noticeable exception according to  is the defense by  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 overfits on 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 used the generative model to project the input or the hidden activations 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 use an autoregressive probabilistic method to learn the data manifold. Other ideas in similar directions include the use of denoising autoencoders in (Gu & Rigazio, 2014) and  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 have not been found effective, see . 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.

MODEL DESCRIPTION
Intuitively, we want to learn a causal model of the inputs. 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. Instead of directly learning a posterior p(y|x) from inputs to labels we now learn generative distributions p(x|y) and classify new inputs using Bayes formula, The label distribution p(y) can be estimated from the training data. To learn the class-conditional sample distributions p(x|y) we use variational autoencoders (VAEs) (Kingma & Welling, 2013). VAEs estimate the log-likelihood log p(x) by learning a probabilistic generative model p θ (x|z) with latent variables z ∼ p(z) and parameters θ (see Appendix A.1 for the full derivation): where p(z) = N (0, 1) is a simple normal prior and q φ (z|x) 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) and q φ (z|x) as normal distributions for which the means are parametrized as deep neural networks (all details and hyperparameters are reported in Appendix A.5).
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) 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) 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: * 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), 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.
• 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.5) and reach values in the range γ y ∈ [0.96, 1.06] for all classes y.

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, * 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.2), * Likewise, we can derive an upper bound of * y (x + δ) for all other classes c = y (see Appendix A.3), * for d c = min z G c (z) − x 2 . Now we can find for a given image x by equating (7) = (6), 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.

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 ), σ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 asxỹ, 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.  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.

Gradient-based attacks
Postprocessing (binary models only) For models with input binarization (see 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.

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  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.5. 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 (Table 1, right values) for completeness and set L2 = 1.5, L∞ = 0.3 and L0 = 12 as thresholds.

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 Table 1: 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, L∞ = 0.3 and L0 = 12 (right value, gray). "w/ GE" indicates attacks that use numerical gradient estimation.
• 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 we show adversarial examples. For each sample we show the minimally perturbed L 2 adversarial found by any attack. Adversarials for the baseline CNN and the Binary CNN are almost 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.
Lower bounds on Robustness For the ABS models and the L 2 metric we estimate a lower bound of the robustness. The lower bound for the mean perturbation 2 for the MNIST test set is = 0.690±0.005 for the ABS and = 0.601±0.005 for the binary ABS. We estimated the error by using different random seeds for our optimization procedure and standard error propagation over 10 runs.   Distal Adversarials We probe the behavior of CNN, Madry et al. and our ABS model outside the data distribution. We start from random noise images and perform gradient ascent to maximize the output probability of a fixed label such that p(y|x) ≥ 0.9 of the modified softmax from equation (8). The results are visualized in Figure 4. Standard CNNs and Madry et al. provide high confidence class probabilities for unrecognizable images. Our ABS model does not provide high confident predictions in out of distribution regions.

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 overfits the L ∞ metric and 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.
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 (  Figure 6b of  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.
The naive 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, 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.  Figure 5: 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%). 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 = δ ∞ ,