Title: ONE BIT MATTERS: UNDERSTANDING ADVERSARIAL EXAMPLES AS THE ABUSE OF REDUNDANCY Anonymous

Abstract: Adversarial examples have somewhat disrupted the enormous success of machine learning (ML) and are causing concern with regards to its trustworthiness: A small perturbation of an input results in an arbitrary failure of an otherwise seemingly well-trained ML system. While studies are being conducted to discover the intrinsic properties of adversarial examples, such as their transferability and universality, there is insufficient theoretic analysis to help understand the phenomenon in a way that can influence the design process of ML experiments. In this paper, we deduce an information-theoretic model which explains adversarial attacks universally as the abuse of feature redundancies in ML algorithms. We prove that feature redundancy is a necessary condition for the existence of adversarial examples. Our model helps to explain the major questions raised in many anecdotal studies on adversarial examples. Our theory is backed up by empirical measurements of the information content of benign and adversarial examples on both image and text datasets. Our measurements show that typical adversarial examples introduce just enough redundancy to overflow the decision making of a machine learner trained on corresponding benign examples. We conclude with actionable recommendations to improve the robustness of machine learners against adversarial examples.

1. INTRODUCTION:

Deep neural networks (DNNs) have been widely applied to various applications and achieved great successes (Ciregan et al., 2012; Sallab et al., 2017; Hinton et al., 2012) . This is mostly due to their versatility: DNNs are able to be trained to fit a target function. Therefore, it raises great concerns given the discovery that DNNs are vulnerable to adversarial examples. These are carefully crafted inputs, which are often seemingly normal within the variance of the training data but can fool a well-trained model with high attack success rate (Goodfellow et al., 2015) . Adversarial examples can be generated for various types of data, including images, text, audio, and software (Carlini & Wagner, 2018; Ebrahimi et al., 2017) , and for different ML models, such as classifiers, segmentation models, object detectors, and reinforcement learning systems (Kos & Song, 2017; Huang et al., 2017) . Moreover, adversarial examples are transferable (Tramèr et al., 2017; Liu et al., 2017 )-if we generate adversarial perturbation against one model for a given input, the same perturbation will have high probability to be able to attack other models trained on similar data, regardless how different the models are. Last but not the least, adversarial examples cannot only be synthesized in the digital world but also in the physical world (Evtimov et al., 2017; Kurakin et al., 2016) , which has caused great real-world security concerns.

Given such subtle, yet universally powerful attacks against ML models, several defensive methods have been proposed. For example, Liu et al. (2018) ; Feinman et al. (2017) pre-process inputs to eliminate certain perturbations. Other work (Cao & Gong, 2017) suggest to push the adversarial instance into random directions so they hopefully escape a local minimum and fall back to the correct class. The authors are aware of ongoing work to establish metrics to distinguish adversarial examples from benign ones so that one can filter out adversarial examples before they are used by ML models. However, so far, all defense and detection methods have shown to be adaptively attackable. Therefore, intelligent attacks against intelligent defenses become an arms race. Defending against adversarial examples remains an open problem.

In this paper, we propose and validate a theoretical model that can be used to create an actionable understanding of adversarial perturbations. Based upon the model, we give recommendations to modify the design process of ML experiments such that the effect of adversarial attacks is mitigated. We illustrate adversarial examples using an example of a simple perceptron network that learns the Boolean equal operator and then generalize the example into a universal model of classification based on Shannon's theory of communication. We further explain how adversarial examples fit the thermodynamics of computation. We prove a necessary condition for the existence of adversarial examples. In summary, the contributions of the paper are listed below:

• a model for adversarial examples consistent with related work, physics and information theory;

• a proof that using redundant features is a necessary condition for the vulnerability of ML models to adversarial examples;

• extensive experiments that showcase the relationship between data redundancy and adversarial examples

• actionable recommendations for the ML process to mitigate adversarial attacks.

2. RELATED WORK:

Given a benign sample x, an adversarial example x adv is generated by adding a small perturbation to x (i.e. x adv = x + ), so that x adv is misclassified by the targeted classifier g. Related work has mostly focused on describing the properties of adversarial examples as well as on defense and detection algorithms. Goodfellow et al. have hypothesized that the existence of adversarial examples is due to the linearity of DNNs (Goodfellow et al., 2015) . Later, boundary-based analysis has been derived to show that adversarial examples try to cross the decision boundaries (He et al., 2018) . More studies regarding to data manifold have also been leveraged to better understand these perturbations (Ma et al., 2018; Gilmer et al., 2018; Wang et al., 2016) . While these works provide hints to obtain a more fundamental understanding, to the best of our knowledge, no study was able to create a model that results in actionable recommendations to improve the robustness of machine learners against adversarial attacks. Prior work do not a measurement process or theoretically show the necessary or sufficient conditions for the existence of adversarial examples.

Several approaches have been proposed to generate adversarial examples. For instance, the fast gradient sign method has been proposed to add perturbations along the gradient directions (Goodfellow et al., 2015) . Other examples are optimization algorithms that search for the minimal perturbation (Carlini & Wagner, 2017b; Liu et al., 2017) . Based on the adversarial goal, attacks can be classified into two categories: targeted and untargeted attacks. In a targeted attack, the adversary's objective is to modify an input x such that the target model g classifies the perturbed input x adv as a targeted class chosen, which differs from its ground truth. In a untargeted attack, the adversary's objective is to cause the perturbed input x adv to be misclassified in any class other than its ground truth. Based on the adversarial capabilities, these attacks can be categorized as white-box and black-box attacks, where an adversary has full knowledge of the classifier and training data in the white-box setting (Szegedy et al., 2014; Goodfellow et al., 2015; Carlini & Wagner, 2017a; Moosavi-Dezfooli et al., 2015; Papernot et al., 2016b; Biggio et al., 2013; Fawzi & Frossard, 2015; Kanbak, 2017; Kurakin et al., 2016) , but zero knowledge about them in the black-box setting (Papernot et al., 2016a; Liu et al., 2017; Moosavi-Dezfooli et al., 2016; Mopuri et al., 2017) .

Interestingly enough, adversarial examples are not restricted to ML. Intuitively speaking, and consistent with the model that is presented in this paper, acoustic noise masking could be regarded as an adversarial attack on our hearing system. Acoustic masking happens, for example, when a clear sinusoid tone cannot be perceived anymore because a small amount of white noise has been added to the signal (Phillips, 1990) . This effect is exploited in MP3 audio compression and privacy applications. Similar examples exist, such as optical illusions in the visual domain (Ponomarenko et al., 2007) and defense mechanisms against sensor-guided attacks (Warm et al., 1997) in the military domain. 

3. A MODEL FOR ADVERSARIAL EXAMPLES:

Intuitively speaking, we want to explain the phenomenon shown in Figure 2a , which depicts a plane filled with points that were originally perfectly separable with two 2D linear separations. As the result of perturbing several points by a mere 10% of the original position, the separation of the two classes requires many more than two linear separators. That is, a small amount of noise can overflow the separation capability of a network dramatically. In the following section, we introduce an example model along which we will derive our mathematical understanding, consistent with our experiments in Section 4 and the related work mentioned in Section 2.

3.1. ADVERSARIAL EXAMPLES AND BOOLEAN FUNCTIONS:

Consider a perceptron network which implements the Boolean equal function ("NXOR") between the two variables x 1 and x 2 . The input x 3 is redundant in the sense that the result of x 1 == x 2 is not influenced by the value of x 3 .

The first obvious observation is that adding x 3 doubles the input space. Instead of 2 2 = 4 possible input pairs, we now have 2 3 = 8 possible input triples that the network needs to map to sustain the result x 1 == x 2 for all possible combinations of x 1 , x 2 , x 3 . The network architecture shown in Figure 1a , for example, theoretically has the capacity to be trained to learn all 8 input triples (Friedland & Krell, 2017) . Translating this example into a practical ML scenario, however, this would mean that we have to exhaustively train the entire input space for all possible settings of the noise. This is obviously unfeasible.

We will therefore continue our analysis in a more practical setting. We assume a network like in Figure 1a is correctly trained to model x 1 == x 2 in the absence of a third input. One example configuration is shown. Now, we train weights w 1 and w 2 to try to suppress the redundant input x 3 by going through all possible combinations for w i ∈ {-1, 0, 1}. This weight choice is without losing generality as the inputs x i are ∈ {0, 1} (see Rojas (2013) ). An adversarial example is defined as a triple (x 1 , x 2 , x 3 ) such that the output of the network is not the result of x 1 == x 2 . Simulating through all configurations exhaustively results in Table 2b . The only case that allows for 100% accuracy, i.e., no adversarial examples, is the setting w 1 = w 2 = 0, in which case x 3 is suppressed completely. In the other cases, we can roughly say that the more the network pays attention to x 3 , the worse the result (allowing edges). That is, the result is better if one of the w i is set to 0 compared to none. Furthermore, the higher the potential, defined as the difference between the maximum and the minimum possible activation value as scaled by the w i , the worse the result is. The intuition behind this is that higher potential change leads to higher potential impacts to the overall network.

Using this simple model, one can see the importance of suppressing noise. Thresholds of neurons taking redundant inputs should be high, or equivalently, weights should be close to 0 (and equal to 0 in the optimal scenario). Now generalizing the example to a large network training images with 'real-valued' weights, it becomes clear that redundant bits of an image should be suppressed by low enough weights otherwise it is easy to generate an exponential explosion of patterns needed to be recognized. 

3.2. GENERAL MODEL:

The generalization of the example from the previous section is shown in Figure 1b . The model shows a machine learner performing the task of matching an unknown noisy pattern to a known pattern (label). For example, a perceptron network implements a function of noisy input data. It quantizes the input to match a known pattern and then outputs the results of the learned function from a known pattern to a known output. Formally, the random variable Y encodes unknown patterns that are sent over a noisy channel. The observation at the output of the channel is denoted by the random variable X. For example, X could represent image pixels. The machine learner then erases all the noise bits in X to match against trained patterns which are then mapped to known outputs Ŷ , for example, the labels. It is well known from the thermodynamics of computing (Feynman et al., 2000) that setting memory bits and copying them is theoretically energy agnostic. However, resetting bits to zero is not.

In other words, we need to spend energy (computation) to reset the noisy bits added by the channel and captured in the observation to get to a distribution of patterns Ŷ that is isomorphic to the original (unknown) distribution of patterns Y . Connecting back to the NXOR example from the previous section, Y would be the distribution over the input variables x 1 and x 2 . The noise added is modeled by x 3 and Ŷ is the desired output isomorphic to x 1 and x 2 being equal. Now assuming a fully trained model, this model allows us to explain several phenomena explored in the introduction and Section 2.

First, as illustrated in the previous section, we can view the machine learner as a trained bit eraser. That is, the machine learner has been trained to erase exactly those bits that are irrelevant to the pattern to be matched. This elimination of irrelevance constitutes the generalization capability. For a black box adversarial attack, we therefore just need to add enough irrelevant input to overflow this bit erasure function. As a result, insufficient redundant bits can be absorbed and the remaining bits now create an exponential explosion for the pattern matching functionality. In a whitebox attack, an attacker can guess and check against the bit erasing patterns of the trained machine learner and create a sequence of input bits that specifically overflows the decision making. In both cases, our model predicts that adversarial patterns should be harder to learn as they consist of more bits to erase. This is confirmed in our experiments in Section 4. It is also clear that the theoretical minimum overflow is one bit, which means, small perturbations can have big effects. This will be made rigorous in Section 3.3. It is also well known that, for example, in the image domain one bit of difference is not perceivable by a human eye. Training with noisy examples will most likely make the machine learner more robust as it will learn to reduce redundancies better. However, a specific whitebox attack (with lower entropy than random noise), which constitutes a specific perceptron threshold overflow, will always be possible because training against the entire input space is unfeasible.

Second, with training data available, it is highly likely that a surrogate machine learner will learn to erase the same bits. This means that similar bit overflows will work on both the surrogate and the original ML attack, thus explaining transferability-based attacks.

3.3. ABUSE OF REDUNDANCY:

In the following we will present a proof based on the model presented in Section 3.2 and the currently accepted definition of adversarial examples (Wang et al., 2016 ) that shows that feature redundancy is indeed a necessary condition for adversarial examples. Throughout, we assume that a learning model can be expressed as f (•) = g(T (•)), where T (•) represents the feature extraction function and g(•) is a simple decision making function, e.g., logistic regression, using the extracted features as the input. Definition 1 (Adversarial example (Wang et al., 2016) ). Given a ML model f (•) and a small perturbation δ, we call x an adversarial example if there exists x, an example drawn from the benign data distribution, such that f (x) = f (x ) and x -x ≤ δ.

We first observe that ∀x, x ∃δ such that x -x ≤ δ =⇒ f (x) = f (x ) is the generalization assumption of a machine learner. The existence of an adversarial x is therefore equivalent to a contradiction of the generalization assumption. This is, x could be called a counter example.

Practically speaking, a single counter example to the generalization assumption does not make the machine learner useless though. In the following, and as explained in previous sections, we connect the existence of adversarial examples to the information content of features used for making predictions.

Definition 2 (Feature redundancy). Let X and Y represent the random variables corresponding to features and unknown pattern, respectively. Let T min Y (X) denote the minimal sufficient statistic of X, i.e., T min Y (X) = arg min T (X):I(X;Y )=I(T (X);Y ) H(T (X)), where T (X) is the sufficient statistic for Y . The redundancy of using T (•) as the feature extractor for predicting Y is defined as

EQUATION

Theorem 1. Suppose that the feature extractor T (X) is a sufficient statistic for Y and that there exist adversarial examples for the ML model f (•) = g(T (•)), where g(•) is an arbitrary decision making function. Then, T (X) is not a minimal sufficient statistic.

We leave the proof to the appendix. The idea of the proof is to explicitly construct a feature extractor with lower entropy than T (X) using the properties of adversarial examples. Theorem 1 shows that the existence of adversarial examples implies that the feature representation contains redundancy. We would expect that more robust models will generate more succinct features for decision making. We will corroborate this intuition in Section 4.2.

4. EXPERIMENTAL RESULTS:

In this section, we provide empirical results to justify our theoretical model for adversarial examples.

Our experiments aim to answer the following questions. First, are adversarial examples indeed more complex (e.g. they contain more redundant bits with respect to the target that need to be erased by the machine learner)? Here we define the model capacity as the minimal number of parameters needed to memorize all the training data. To explore the capacity, we first build an MLP model with one hidden layer (units: 64). This model is efficient enough to achieve high performance and memorize all training data (with ReLU). After that, weights are reduced by randomly setting some of their values to zero and marking them untrainable. The error is set to evaluate the training success (training accuracy is larger than 1 -). We explore the minimal number of parameters and utilize binary search to reduce computation complexity. Finally, we change different and repeat the above steps. As 

4.2. INPUT COMPLEXITY ESTIMATION:

We now investigate if there are possible ways to exploit the higher complexity of adversarial examples to possibly detect adversarial attacks. That is to say, we need a machine-learning independent measure of entropy to evaluate how much benign and adversarial examples differ. For images, we utilized Maximum Likelihood (MLE), Minimax (JVHW) (Jiao et al., 2014) and compression estimators for (Goodfellow et al., 2015) , DeepFool (Moosavi-Dezfooli et al., 2015) , CW (L 2 ) (Carlini & Wagner, 2017a )) on both MNIST and CIFAR-10 dataset. These are four metrics for entropy measurement, all of which indicate higher unpredictability with the value increasing. For compression estimation, prior work (Friedland et al., 2018) has found that an optimal quantification ratio exists for DNNs and appropriate perceptual compression is not harmful. Therefore, we consider such information as redundancy and set the quality scale to 20 following their strategy. We also reproduce the experiments in our settings and obtain the same results shown in Figure 5 . As shown in Table 1 , the benign images have smallest complexity in all of the four metrics, which suggests less entropy (lower complexity) and therefore higher predictability. Similarly, we also design four metrics for text entropy estimation including mean bits per character, byte-wise entropy (BW), bit-wise entropy (bW) and compression size. More specifically, BW and bW are calculated based on the histogram of the bytes or the bits per word. It is worthwhile to note that all of the metrics are measured on adversarial-benign altered pairs, because adversarial algorithms only modify specific words of the texts. In our evaluations, FGSM, FGVM (Miyato et al., 2015) and DeepFool attacks are implemented. From Table 2 , we can draw the conclusion that adversarial texts introduce more redundant bits with regards to the target function which results in higher complexity and therefore higher entropy. A reduction of adversarial attacks via entropy measurement is therefore potentially possible for both data types.

4.3. OUTPUT COMPLEXITY ESTIMATION:

Inspired by Theorem 1, we investigate the relation between feature redundancy and the robustness of a ML model. We expect that more robust models would employ more succinct features for prediction. To validate this, we design models with different levels of robustness and measure the entropy of extracted features (i.e., the input to the final activation layer for decisions). In experiments, we choose All-CNNs network for it has no fully-connected layer and the last convolutional layer is directly followed by the global average pooling and softmax activation layer, which is convenient for the estimation of entropy. In other words, we can estimate the entropy of the feature maps extracted by the last convolutional layer using perceptual compression and MLE/JVHW estimators. Specifically, we train different models on benign examples and control the ratios of adversarial examples in adversarial re-training period to obtain models with different robustness. In general, the larger ratio of adversarial examples we re-train, the more robust models we will obtain. The robustness in experiments is measured by the test accuracy on adversarial examples. Then we obtain the feature maps on adversarial examples generated by these models and compress them to q = 20, following Friedland et al. (2018) . Finally, we measure the compressed entropy of using MLE and JVHW estimator like Section 4.2. As illustrated in Figure 6 , the estimated entropy (blue dots) decreases as the classification accuracy (red dots) increases for all the three adversarial attacks (FGSM, DeepFool, CW) and the two datasets (MNIST, CIFAR), which means that the redundancy of last-layer feature maps is lower when the models become more robust. 

5. CONCLUSION AND RECOMMENDATIONS:

Our theoretical and empirical results presented in this paper consistently show that adversarial examples are enabled by irrelevant input that the networks was not trained to suppress. In fact, a single bit of redundancy can be exploited to cause the ML models to make arbitrary mistakes. Moreover, redundancy exploited against one model can also affect the decision of another model trained on the same data as that other model learned to only cope with the same amount of redundancy (transferability-based attack). Unfortunately, unlike the academic example in Section 3.1, we almost never know how many variables we actually need. For image classification, for example, the current assumption is that each pixel serves as input and it is well known that this is feeding the network redundant information e.g., nobody would assume that the upper-most left-most pixel contributes to an object recognition result when the object is usually centered in the image.

Nevertheless, the highest priority actionable recommendation has to be to reduce redundancies. Before deep learning, manually-crafted features reduced redundancies assumed by humans before the data entered the ML system. This practice has been abandoned with the introduction of deep learning, explaining the temporal correlation with the discovery of adversarial examples. Short of going back to manual feature extraction, automatic techniques can be used to reduce redundancy. Obviously, adaptive techniques, like auto encoders, will be susceptible to their own adversarial attacks. However, consistent with our experiments in Section 4.2, and dependent on the input domain, we recommend to use lossy compression. Similar results using quantization have been reported for MP3 and audio compression (Friedland et al., 2018) as well as molecular dynamics (Liu, 2018) . In general, we recommend a training procedure where input data is increasingly quantized while training accuracy is measured. The point where the highest quantization is achieved at limited loss in accuracy, is the point where most of the noise and least of the content is lost. This should be the point with least redundancies and therefore the operation point least susceptible to adversarial attacks. In terms of detecting adversarial examples, we showed in Section 4 that estimating the complexity of the input using surrogate methods, such as different compression techniques, can serve as a prefilter to detect adversarial attacks. We will dedicate future work to this topic. Ultimately, however, the only way to practically guarantee adversarial attacks cannot happen is to present every possible input to the machine learner and train to 100% accuracy, which contradicts the idea of generalization in ML itself.

There is no free lunch. A PROOF OF THEOREM 1

Proof. Let X be the set of admissible data points and X denote the set of adversarial examples,We prove this theorem by constructing a sufficient statistic T (X) that has lower entropy than T (X). Consider

T (x ) = T (x ) if x ∈ X \ X T (x) if x ∈ X (2)

where x is an arbitrary benign example in the data space. Then, for all x ∈ X , g(T (x)) = g(T (x )).

It follows that T (x) = T (x ), ∀x ∈ X . On the other hand, T (x) = T (x) by construction.

Let the probability density of T (X) be denoted by p(t), where t ∈ T (X ), and the probability density of T (X) be denoted by q(t) where t ∈ T (X \ X ). Then, q(t) = p(t) + w(t) for t ∈ T (X \ X ), where w(t) corresponds to the part of benign example probability that is formed by enforcing an originally adversarial example' feature to be equal to the feature of an arbitrary benign example according to (2). Furthermore, t∈T (X \X ) w(t) = t∈T (X ) p(t). We now compare the entropy of T (X) and T (X): H(T (X)) -H(T (X)) 

It is evident that U 1 ≥ 0. Note that for any p(t), there always exists a configuration of w(t) such that U 2 ≥ 0. For instance, let t * = arg max t∈T (X \X ) p(t). Then, we can let w(t * ) = t∈T (X ) p(t) and w(t) = 0 for t = t * . With this configuration of w(t), U 2 = (p(t * ) + w(t * )) log((p(t * ) + w(t * )) -p(t * ) log p(t * ) (6) Due to the fact that x log x is a monotonically increasing function, U 2 ≥ 0.

To sum up, both U 1 and U 2 are non-negative; as a result, H(T (X)) > H(T (X)) (7) Thus, we constructed a sufficient statistic T (•) that achieves lower entropy than T (•), which, in turn, indicates that T (X) is not a minimal sufficient statistic.

B SUPPLEMENTARY EXPERIMENTAL RESULTS:

Apart from the adversarial examples, we also observed the same phenomenon for random noise that redundancy will lead to the failure of DNNs. We tested datasets with different signal-to-noise ratios (SNR), generated by adding Gaussian noise to the real pixels. The SNR is obtained by controlling the variance of the Gaussian distribution. Finally, we derived the testing accuracy on hand-crafted noisy testing data. As shown in Figure 7a and 7b, a small amount of random Gaussian noise will add complexity to examples and cause the DNNs to fail. For instance, noisy input sets with one tenth the signal strength of the benign examples result in only 34.3% test accuracy for DenseNet on CIFAR-10. This indeed indicates, and is consistent with related work, that small amounts of noise can practically fool ML models in general.

:



Figures and Tables:

Figure 1: (a) A perceptron network implementing the Boolean equality of x 1 and x 2 with added redundancy x 3 (see Section 3.1). (b) Shannon channel model of machine learning inspired by MacKay (2003). (see Section 3.2).

Figure 2: (a) A network trained on XOR cannot separate the two classes anymore perfectly once we add 10% of noise to some of the inputs. (b) Suppression capability of adversarial attacks against the Boolean equality network.

Figure3: Comparison of estimated model capacity (minimal number of parameters required) as a function of allowed error under different attack algorithms on MNIST. The results are obtained based on the MLPs with and without non-linear activation functions (e.g. ReLU). Note that the non-linear models can generalize the data better, so the is fixed in a much smaller range.

Figure 5: Classification accuracy as a function of the JPEG compression quality q. The shadow curve represents the properly scaled version of the theoretical curve in Friedland et al. (2018).

Figure 6: Estimated entropy of the output layer under All-CNNs architecture with different robustness. Three adversarial attacks (FGSM, DeepFool, CW) are tested on MNIST and CIFAR classification dataset. Note that only the adversarial examples that successfully fool the networks are calculated.

Comparison of complexity for benign and adversarial examples on MNIST and CIFAR-10.

Table content: <table><tr><td>Dataset</td><td>Examples</td><td colspan="4">H (MLE) H (JVHW) Original Size Compressed Size</td></tr><tr><td/><td>Benign</td><td>1.741</td><td>1.887</td><td>988.89 B</td><td>431.40 B</td></tr><tr><td>MNIST</td><td>FGSM (2015) DeepFool (2015)</td><td>2.488 4.844</td><td>2.601 5.088</td><td>1690.36 B 1654.99 B</td><td>503.54 B 510.41 B</td></tr><tr><td/><td>CW (L2) (2017a)</td><td>4.094</td><td>4.301</td><td>1159.01 B</td><td>437.27 B</td></tr><tr><td/><td>Benign</td><td>9.595</td><td>7.104</td><td>1845.98 B</td><td>741.36 B</td></tr><tr><td>CIFAR-10</td><td>FGSM (2015) DeepFool (2015)</td><td>9.937 9.675</td><td>7.710 7.147</td><td>2717.01 B 1880.41 B</td><td>872.40 B 743.02 B</td></tr><tr><td/><td>CW (L2) (2017a)</td><td>9.621</td><td>7.113</td><td>1850.54 B</td><td>741.56 B</td></tr></table>

Comparison of complexity for benign and adversarial examples on IMDB and Reuters2.

Table content: <table><tr><td>Dataset</td><td>Examples</td><td colspan="4">Mean Bits H (BW) H (bW) Compressed Size</td></tr><tr><td/><td>Benign</td><td>4.556</td><td>0.569</td><td>0.99775</td><td>2.235 B</td></tr><tr><td>IMDB</td><td>FGSM (2015) FGVM (2015)</td><td>4.671 4.701</td><td>0.584 0.588</td><td>0.99926 0.99944</td><td>3.027 B 3.481 B</td></tr><tr><td/><td>DeepFool (2015)</td><td>4.632</td><td>0.580</td><td>0.99953</td><td>3.156 B</td></tr><tr><td/><td>Benign</td><td>4.946</td><td>0.618</td><td>0.99457</td><td>1.934 B</td></tr><tr><td>Reuters2</td><td>FGSM (2015) FGVM (2015)</td><td>5.032 5.035</td><td>0.629 0.629</td><td>0.99712 0.99754</td><td>3.181 B 3.237 B</td></tr><tr><td/><td>DeepFool (2015)</td><td>5.202</td><td>0.650</td><td>0.99545</td><td>3.301 B</td></tr><tr><td colspan="3">three kind of adversarial examples (FGSM</td><td/><td/><td/></tr></table>

Beilun Wang, Ji Gao, and Yanjun Qi. A theoretical framework for robustness of (deep) classifiers against adversarial examples. arXiv preprint arXiv:1612.00334, 2016.Berndt Warm, Detlev Wittmer, and Matthias Noll. Apparatus for defending against an attacking missile, February 4 1997. US Patent 5,600,434.

Table content: <table/>

Peer review (iclr2019):
 Summary: In this work, the authors study the problem of adversarial examples in ML from an information-theoretic point of view. They explore connections between feature redundancy and adversarial perturbations. They provide a combination of empirical and theoretical studies to justify this connection. Quality, Originality and Novelty: While the high level idea studied in this paper is interesting, however it has been suggested before in prior work [Tsipras et al., 2018]. Thus, I do not find the analysis in this paper novel or convincing. There also seem to be some technical flaws in the examples used to corroborate the claims. The experimental justification provided is lacking, as analysis is largely restricted to simple models and does not include state-of-the-art attacks. Specific Comments: Section 2: - The authors are misinformed about the lack of prior work to theoretically understand the cause of adversarial examples. Many aspects of this problem have been analyzed in previous work. Some (non-exhaustive) related work - [Papernot et al., 2016, Fawzi et al., 2018, Schmidt et al., 2018, Bubeck et al., 2018, Tsipras et al., 2018]. - I do not understand the comment on optical illusions, etc. There seems to be a misunderstanding about the definition of adversarial examples. In the standard setting, adversarial examples are defined as small perturbations, which are imperceptible to humans, that cause models to classify otherwise benign inputs incorrectly. Note that the ground truth label for adversarial perturbations is determined by human classification and thus instances such as optical illusions are not adversarial examples since humans do not consider them to be part of the same class. Section 3: - The setting discussed by the authors in Figure 2a does not fit in to the standard adversarial threat model. If you consider the colored regions to be ground truth labels for the points then the colored points are not adversarial examples, but are perturbations that truly switch the underlying label of the data point. The goal of adversarially robust machine learning is not to be resilient to arbitrary magnitudes of noise, but specifically small perturbations that do not change the underlying class of a data point. In fact, in the example provided, if an ML model truly learns the linear separators then it is robust to adversarial examples. - The authors state that “random noise overflows the separation capability of a network”. As mentioned in comment 1 above, the colored points in Figure 2a are not adversarial examples. Hence it is not clear why this comment about *large* random noise applies to imperceptible adversarial perturbations. Further, it is important to note that the “true” decision boundary of the task is not affected by the presence of adversarial examples. In fact, we expect adversarial examples to capture invariances that we believe would be present in a classifier that was able to learn this true boundary. - The authors seem to conflate random noise with adversarial perturbations. It is well known that random noise is not an adversarial perturbation for state-of-the-art ML models. - Section 3.1: The example about the boolean circuit that the authors provide is extremely confusing and also likely incorrect. It is unclear what threat model the authors assume here. The authors seem to consider inputs for which the model predicts an incorrect output as adversarial examples. But these do not come from benign inputs unless we allow very large perturbations (for instance an l_inf eps = 1). Under such large perturbations, a model with both w_1, w_2 = 0 could also be made to “fail” by flipping x_1 or x_2. - Section 3.2: -> I had a hard time trying to understand the discussion in this section. The authors use phrases such as “bit eraser” and “overflowing decision making” which have not been properly defined in the paper. It is also unclear what the threat model being considered is. It seems as though the authors consider standard ML models as bit erasers that can already disregard redundant inputs. If this is the case, it is not clear to me what the authors mean by: “For a black box adversarial attack, we therefore just need to add enough irrelevant input to overflow this bit erasure function.” Is the attacker allowed to append an arbitrary bits to the input at test time? This is not true of standard attack models where the number of bits of the input data are fixed, and hence not clear why adversarial examples would need more bit erasures. -> It is well-known that training with random noise is not enough to build robust models. -> The authors make a broad claim about transferability, but do not provide sufficient evidence to support it. Given that we train ML models with millions of parameters on a much smaller set of training samples, it is unclear to me why different models would consistently identify the same set of redundant features. - Section 3.3: The claim that the existence of adversarial examples is a failure of standard generalization is incorrect. In the standard ML setting, we seek to minimize expected population loss on samples from the distribution. In the adversarial setting, we seek to minimize the loss on *worst-case* perturbations of inputs drawn from the distribution. This is a different and much more challenging statistical problem and likely requires more data [Schmidt et al, 2018] and compute [Bubeck et al, 2018] as has been studied out prior works. -Section 4: --> Section 4.1: I do not entirely understand the setup of this experiment. Do the authors retrain after setting weights to 0? Or do they simply try setting different fractions of weights to zero until the train error hits eps. It is not clear to me that setting random weights to zero is a good way to evaluate the complexity of robust models (i.e., those trained on adversarial examples). It has been noted in prior work that these robust models already tend to be sparser than standard models, so setting random weights to zero could indeed have a larger impact on these models. Did the authors verify how many of the weights are away from zero for robust models before clipping the weights? If these were included, the plots might change. The plots in Figure 4 actually contradict the authors claim that adversarial examples are harder to memorize, since the training accuracy plots look very similar for all datasets. The test accuracy plots are indeed different, but this could be because robust learning is a statistically more complex problem and needs more data as has been studied in prior work [Schmidt et al, 2018]. --> Section 4.2: The authors should provide more details as to how they estimate the various statistics, at least in the appendix. It is hard to draw inferences from these tables without details about the procedure to generate these statistics, how these adversarial examples were constructed (what was the epsilon, did the authors use code released by prior art) and what the models were on which these examples were generated. --> Section 4.3: Similar insights about feature redundancy in robust models have been observed in prior work [Ross et al., 2017, Tsipras et al., 2018]. - Section 5: Using lossy compression as a defense against adversarial examples has been tried in prior art and is known to be unsuccessful [Athalye et al., 2018]. References: Papernot, Nicolas, et al. "Towards the science of security and privacy in machine learning." arXiv preprint arXiv:1611.03814 (2016). Fawzi, Alhussein, Hamza Fawzi, and Omar Fawzi. "Adversarial vulnerability for any classifier." arXiv preprint arXiv:1802.08686 (2018). Bubeck, Sébastien, Eric Price, and Ilya Razenshteyn. "Adversarial examples from computational constraints." arXiv preprint arXiv:1805.10204 (2018). Schmidt, Ludwig, et al. "Adversarially Robust Generalization Requires More Data." arXiv preprint arXiv:1804.11285 (2018). Ross, Andrew Slavin, and Finale Doshi-Velez. "Improving the adversarial robustness and interpretability of deep neural networks by regularizing their input gradients." arXiv preprint arXiv:1711.09404 (2017). Tsipras, Dimitris, et al. "Robustness May Be at Odds with Accuracy." arXiv preprint arXiv:1805.12152 (2018). Athalye, Anish, Nicholas Carlini, and David Wagner. "Obfuscated gradients give a false sense of security: Circumventing defenses to adversarial examples." arXiv preprint arXiv:1802.00420 (2018).