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. Deep neural networks (DNNs) have been widely applied to various applications and achieved great successes BID5 BID36 BID16 . 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 BID14 . Adversarial examples can be generated for various types of data, including images, text, audio, and software BID4 BID6 , and for different ML models, such as classifiers, segmentation models, object detectors, and reinforcement learning systems BID20 BID17 . Moreover, adversarial examples are transferable BID38 BID23 )-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 BID7 BID21 , 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, ; BID9 pre-process inputs to eliminate certain perturbations. Other work BID1 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. 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 BID12 as well as molecular dynamics BID22 . 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 1Proof. 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 DISPLAYFORM0 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): DISPLAYFORM1 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.
A new theoretical explanation for the existence of adversarial examples
{"src": "scitldr-AIC_train", "paper_id": "B1enCo0cK7"}