Towards the first adversarially robust neural network model on MNIST

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_{\infty}$ norm bounded by $\epsilon=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 $$), then he can only trick the model on$\approx 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_{\infty}$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) (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 (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 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 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_{\infty}$ 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.

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 the models more robust against them (Madry et al., 2018; Szegedy et al., 2013; Tramèr 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 noticeable 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 overfits on the metric it is trained on ($L_{\infty}$) 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 (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 have not been found effective, see (Athalye et al., 2018). 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

The label distribution $p(y)$ can be estimated from the training data. To learn the class-conditional sample distributions $p({\bf x}|y)$ we use variational autoencoders (VAEs) (Kingma & Welling, 2013). VAEs estimate the log-likelihood $\log p({\bf x})$ by learning a probabilistic generative model $p_{\theta}({\bf x}|{\bf z})$ with latent variables ${\bf z}\sim p({\bf z})$ and parameters $\theta$ (see Appendix A.1 for the full derivation):

where $p({\bf z})=\mathcal{N}(\bf 0,\mathds{1})$ is a simple normal prior and $q_{\phi}({\bf z}|{\bf x})$ is the variational posterior with parameters $\phi$. 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_{\theta}({\bf x}|{\bf z})$ and $q_{\phi}({\bf z}|{\bf 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:

Optimization-based inference: The variational inference $q_{\phi}({\bf z}|{\bf x})$ is itself a neural network susceptible to adversarial perturbations. We therefore only use variational inference during training and perform “exact” inference over $p_{\theta}({\bf x}|{\bf z})$ during evaluation. This “exact” inference is implemented using gradient descent in the latent space (with fixed posterior width) to find the optimal ${\bf 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).

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 if $b<0.5$ or $1$ if $b\geq 0.5$ during testing.

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({\bf x}|{\bf z})$. Because we chose this posterior to be Gaussian, the class-conditional likelihoods can only change gracefully with changes in ${\bf 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,

for $d_{c}=\min_{z}\left\lVert{\bf G}_{c}({\bf z})-{\bf x}\right\rVert_{2}$. Now we can find $\epsilon$ for a given image ${\bf x}$ by equating $(\ref{equ:lb})=(\ref{equ:ub})$,

Note that one assumption we make is that we can find the global minimum of $\left\lVert{\bf G}_{c}({\bf z})-{\bf x}\right\rVert_{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.

We choose $\epsilon=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 $\epsilon$ interval. Finally, we perform another binary search between the adversarial and the original image to reduce the perturbation as much as possible.

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 attacks also don’t rely on gradients of the target model but instead compute them on a substitute: given an input ${\bf x}$ we first compute adversarial perturbations $\bm{\delta}$ on the substitute using different gradient-based attacks ($L_{2}$ and $L_{\infty}$ 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 $\epsilon$ for which ${\bf x}+\epsilon\bm{\delta}$ (clipped to the range ) is still an adversarial for the target model.

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_{\infty}$ 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).

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.

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_{\infty}$ defense (Madry et al., 2018)We used the trained model provided by the authors: https://github.com/MadryLab/mnist_challenge, 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 $\infty$. 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 $\epsilon_{L_{2}}=1.5$, $\epsilon_{L_{\infty}{}}=0.3$ and $\epsilon_{L_{0}}=12$ as thresholds.

Results

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_{\infty}$ and $L_{0}$.

For $L_{2}$ our ABS model outperforms all other models by a large margin.

For $L_{\infty}$, 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 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.

For the ABS models and the $L_{2}$ metric we estimate a lower bound of the robustness. The lower bound for the mean perturbationThe mean instead of the median is reported to allow for a comparison with (Hein & Andriushchenko, 2017). for the MNIST test set is $\epsilon=0.690\pm 0.005$ for the ABS and $\epsilon=0.601\pm 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. With adversarial training Hein & Andriushchenko (2017) achieve a mean $L_{2}$ robustness guarantee of $\epsilon=0.48$ while reaching 99% accuracy. In the $L_{inf}$ metric we find a median robustness of $0.06$.

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|{\bf x})\geq 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_{\infty}$ 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 (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_{\infty}$ / $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.

This work has been funded, in part, by the German Federal Ministry of Education and Research (BMBF) through the Bernstein Computational Neuroscience Program Tübingen (FKZ: 01GQ1002) as well as the German Research Foundation (DFG CRC 1233 on “Robust Vision”). The authors thank the International Max Planck Research School for Intelligent Systems (IMPRS-IS) for supporting L.S. and J.R.; J.R. acknowledges support by the Bosch Forschungsstiftung (Stifterverband, T113/30057/17); W.B. was supported by the Carl Zeiss Foundation (0563-2.8/558/3); M.B. acknowledges support by the Centre for Integrative Neuroscience Tübingen (EXC 307); W.B. and M.B. were supported by the Intelligence Advanced Research Projects Activity (IARPA) via Department of Interior / Interior Business Center (DoI/IBC) contract number D16PC00003.

References

A Appendix

This lower bound is commonly referred to as ELBO.

for $d_{c}=\min_{z}\left\lVert{\bf G}_{c}({\bf z})-{\bf x}\right\rVert_{2}$. The last equation comes from the solution of the constrained optimization problem $\min_{d}(d-\epsilon)^{2}d\,$ s.t. $\,d>d_{c}$. Note that a tighter bound might be achieved by assuming single $\bm{\delta}$ for upper and lower bound.

We proceed in the same way as for $L_{2}$. Starting again from

In this case there is no closed-form solution for the minimization problem on the RHS (in terms of the minimum of $\left\lVert{\bf G}_{c}({\bf z})-{\bf x}\right\rVert_{2}$) but we can still compute the solution for each given $\epsilon$ which allows us perform a line search along $\epsilon$ to find the point where equation 13 = equation 14.

A.5 Model & training details

The binary ABS and ABS have the same weights and architecture: The encoder has 4 layers with kernel sizes$=$, strides$=$ 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$=$, strides$=$ and feature map sizes$=$. 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 $\bm{\gamma}=[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 entropyNote that this solely scales the probabilities and does not change the classification accuracy. and providing a median confidence of $p(y|x)=0.9$ for our modified softmax (equation 8) are $\eta=0.000039$ and $\alpha=440$.

The CNN and Binary CNN share the same architecture but have different weights. The architecture has kernel sizes $=$, strides $=$, and feature map sizes $=$. 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 $\eta=143900$ and $\alpha=1$.

We adapted the pre-trained model provided by Madry et alhttps://github.com/MadryLab/mnist_challenge. Basically the architecture contains two convolutional, two pooling and two fully connected layers. The network is trained on clean and adversarial examples minimizing the cross cross-entropy loss. The parameters maximizing the test cross entropy and providing a median confidence of $p(y|x)=0.9$ for our modified softmax (equation 8) are $\eta=60$ and $\alpha=1$.

For a comparison with neural networks, we imitate logits by replacing them with the negative minimal distance between the input and all samples within each class. The parameters maximizing the test cross entropy and providing a median confidence of $p(y|x)=0.9$ for our modified softmax (equation 8) are $\eta=0.000000000004$ and $\alpha=5$.