We study the problem of designing provably optimal adversarial noise algorithms that induce misclassification in settings where a learner aggregates decisions from multiple classifiers. Given the demonstrated vulnerability of state-of-the-art models to adversarial examples, recent efforts within the field of robust machine learning have focused on the use of ensemble classifiers as a way of boosting the robustness of individual models. In this paper, we design provably optimal attacks against a set of classifiers. We demonstrate how this problem can be framed as finding strategies at equilibrium in a two player, zero sum game between a learner and an adversary and consequently illustrate the need for randomization in adversarial attacks. The main technical challenge we consider is the design of best response oracles that can be implemented in a Multiplicative Weight Updates framework to find equilibrium strategies in the zero-sum game. We develop a series of scalable noise generation algorithms for deep neural networks, and show that it outperforms state-of-the-art attacks on various image classification tasks. Although there are generally no guarantees for deep learning, we show this is a well-principled approach in that it is provably optimal for linear classifiers. The main insight is a geometric characterization of the decision space that reduces the problem of designing best response oracles to minimizing a quadratic function over a set of convex polytopes. In this paper, we study adversarial attacks that induce misclassification when a learner has access to multiple classifiers. One of the most pressing concerns within the field of AI has been the welldemonstrated sensitivity of machine learning algorithms to noise and their general instability. Seminal work by has shown that adversarial attacks that produce small perturbations can cause data points to be misclassified by state-of-the-art models, including neural networks. In order to evaluate classifiers' robustness and improve their training, adversarial attacks have become a central focus in machine learning and security BID21 BID17 BID23 .Adversarial attacks induce misclassification by perturbing data points past the decision boundary of a particular class. In the case of binary linear classifiers, for example, the optimal perturbation is to push points in the direction perpendicular to the separating hyperplane. For non-linear models there is no general characterization of an optimal perturbation, though attacks designed for linear classifiers tend to generalize well to deep neural networks BID21 .Since a learner may aggregate decisions using multiple classifiers, a recent line of work has focused on designing attacks on an ensemble of different classifiers BID31 BID0 BID13 . In particular, this line of work shows that an entire set of state-of-the-art classifiers can be fooled by using an adversarial attack on an ensemble classifier that averages the decisions of the classifiers in that set. Given that attacking an entire set of classifiers is possible, the natural question is then:What is the most effective approach to design attacks on a set of multiple classifiers?The main challenge when considering attacks on multiple classifiers is that fooling a single model, or even the ensemble classifier (i.e. the model that classifies a data point by averaging individual predictions), provides no guarantees that the learner will fail to classify correctly. Models may have different decision boundaries, and perturbations that affect one may be ineffective on another. Furthermore, a learner can randomize over classifiers and avoid deterministic attacks (see Figure 1 ). c 2 c 1 Figure 1 : Illustration of why randomization is necessary to compute optimal adversarial attacks. In this example using binary linear classifiers, there is a single point that is initially classified correctly by two classifiers c1, c2, and a fixed noise budget α in the ℓ2 norm. A naive adversary who chooses a noise perturbation deterministically will always fail to trick the learner since she can always select the remaining classifier. An optimal adversarial attack in this scenario consists of randomizing with equal probability amongst both noise vectors.In this paper, we present a principled approach for attacking a set of classifiers which proves to be highly effective. We show that constructing optimal adversarial attacks against multiple classifiers is equivalent to finding strategies at equilibrium in a zero sum game between a learner and an adversary. It is well known that strategies at equilibrium in a zero sum game can be obtained by applying the celebrated Multiplicative Weights Update framework, given an oracle that computes a best response to a randomized strategy. The main technical challenge we address pertains to the characterization and implementation of such oracles. Our main contributions can be summarized as follows:• We describe the Noise Synthesis FrameWork (henceforth NSFW) for generating adversarial attacks. This framework reduces the problem of designing optimal adversarial attacks for a general set of classifiers to constructing a best response oracle in a two player, zero sum game between a learner and an adversary; • We show that NSFW is an effective approach for designing adversarial noise that fools neural networks. In particular, applying projected gradient descent on an appropriately chosen loss function as a proxy for a best response oracle achieves performance that significantly improves upon current state-of-the-art attacks (see results in Figure 2 ); • We show that applying projected gradient descent on an appropriately chosen loss function is a well-principled approach. We do so by proving that for linear classifiers such an approach yields an optimal adversarial attack if the equivalent game has a pure Nash equilibrium. This result is shown via a geometric characterization of the decision boundary space which reduces the problem of designing optimal attacks to a convex program; • If the game does not have a pure Nash equilibrium, there is an algorithm for finding an optimal adversarial attack for linear classifiers whose runtime is exponential in the number of classifiers. We show that finding an optimal strategy in this case is NP-hard.Paper organization. Following a discussion on related work, in Section 2 we formulate the problem of designing optimal adversarial noise and show how it can be modeled as finding strategies at equilibrium in a two player, zero sum game. Afterwards, we discuss our approach for finding such strategies using MWU and proxies for best response oracles. In Section 2 .1, we justify our approach by proving guarantees for linear classifiers. Lastly, in Section 3, we present our experiments.Additional related work. The field of adversarial attacks on machine learning classifiers has recently received widespread attention from a variety of perspectives BID1 BID9 BID25 BID3 . In particular, a significant amount of effort has been devoted to computing adversarial examples that induce misclassification across multiple models BID22 BID21 . There has been compelling evidence which empirically demonstrates the effectiveness of ensembles as way of both generating and defending against adversarial attacks. For example, BID31 establish the strengths of ensemble training as a defense against adversarial attacks. Conversely, provide the first set of experiments showing that attacking an ensemble classifier is an effective way of generating adversarial examples that transfer to the underlying models. Relative to their investigation, our work differs in certain key aspects. Rather than analyzing adversarial noise from a security perspective and developing methods for black-box attacks, we approach the problem from a theoretical point of view and introduce a formal characterization of the optimal attack against a set of classifiers. Furthermore, by analyzing noise in the linear setting, we design algorithms for this task that have strong guarantees of performance. Through our experiments, we demonstrate how these algorithms motivate a natural extension for noise in deep learning that achieves state-of-the-art results. Designing adversarial attacks when a learner has access to multiple classifiers is a non-trivial problem. In this paper we introduced NSFW which is a principled approach that is provably optimal on linear classifiers and empirically effective on neural networks. The main technical crux is in designing best response oracles which we achieve through a geometrical characterization of the optimization landscape. We believe NSFW can generalize to domains beyond those in this paper.
Paper analyzes the problem of designing adversarial attacks against multiple classifiers, introducing algorithms that are optimal for linear classifiers and which provide state-of-the-art results for deep learning.
{"src": "scitldr-AIC_train", "paper_id": "rkl4M3R5K7"}