The Space of Transferable Adversarial Examples

Introduction

Through slight perturbations of a machine learning (ML) model’s inputs at test time, it is possible to generate adversarial examples that cause the model to misclassify at a high rate . Adversarial examples can be used to craft human-recognizable images that are misclassified by computer vision models , software containing malware but classified as benign , and game environments that force reinforcement learning agents to misbehave .

Adversarial examples often transfer across models : inputs generated to evade a specific model also mislead other models trained for the same task. Transferability is an obstacle to secure deployment of ML models as it enables simple black-box attacks against ML systems. An adversary can train a local model—possibly by issuing prediction queries to the targeted model —and use it to craft adversarial examples that transfer to the target model . To defend against such attacks, it is necessary to have a better understanding of why adversarial examples transfer.

Empirical evidence has shown that, rather than being scattered randomly in small pockets, adversarial examples occur in large, contiguous regions . The dimensionality of these subspaces is relevant to the transferability problem: the higher the dimensionality, the more likely it is that the subspaces of two models will intersect significantly.

In this work, we thus directly estimate the dimensionality of these subspaces. We introduce methods for finding multiple orthogonal adversarial directions and show that these perturbations span a multi-dimensional contiguous space of misclassified points. We measure transferability of these subspaces on datasets for which diverse model classes attain high accuracy: digit classification (MNIST) and malware detection (DREBIN) . We use a balanced subset of the DREBIN dataset, pre-processed using feature selection to have $1{,}000$ features (in lieu of about $500,000$). The models we train get over $94\%$ accuracy on this dataset. For example, we find that adversarial examples that transfer between two fully-connected networks trained on MNIST form a 25-dimensional space.

In addition to sharing many dimensions of the adversarial subspace, we find empirically that the boundaries of this space lie at similar distances from legitimate data points in adversarial directions (e.g., indicated by an adversarial example). More surprisingly, models from different hypothesis classes learn boundaries that are close in arbitrary directions, whether adversarial or benign (e.g., the direction defined by two legitimate points in different classes). We find that when moving into any direction away from data points, the distance to the model’s decision boundary is on average larger than the distance separating the boundaries of two models in that direction. Thus, adversarial perturbations that send data points sufficiently over a model’s decision boundary likely transfer to other models.

The Limits of Transferability.

Given the empirical prevalence of transferability, it is natural to ask whether this phenomenon can be explained by simple properties of datasets, model classes, or training algorithms. In Section 5, we consider the following informal hypothesis: {quoting} If two models achieve low error for some task while also exhibiting low robustness to adversarial examples, adversarial examples crafted on one model transfer to the other.

This hypothesis is pessimistic: it implies that a model cannot be secure against adversarial examples transferred from other models (i.e, black-box attacks) unless it is also robust to adversarial examples crafted with knowledge of the model’s parameters (i.e., white-box attacks). While this hypothesis holds in certain contexts, we show that it is not true in the general case.

We derive sufficient conditions on the data distribution that imply a form of the above hypothesis for a set of simple model classes. Namely, we prove transferability of model-agnostic perturbations, obtained by shifting data points in the direction given by the difference in class means (in input space). These adversarial examples are by design effective against linear models. Yet, we show, both formally and empirically, that they can transfer to higher-order (e.g., quadratic) models.

However, we exhibit a counter-example to the above hypothesis by building a variant of the MNIST dataset for which adversarial examples fail to transfer between linear and quadratic models. Our experiment suggests that transferability is not an inherent property of non-robust ML models.

Our Contributions.

To summarize, we make the following contributions:

We introduce methods for finding multiple independent attack directions, enabling us to directly measure the dimensionality of the adversarial subspace for the first time.

We perform the first quantitative study of the similarity of models’ decision boundaries and show that models from different hypothesis classes learn decision boundaries that lie very close to one-another in both adversarial and benign directions.

In a formal study, we identify sufficient conditions for transferability of model-agnostic perturbations, as well as tasks where adversarial example transferability fails to hold.

Adversarial Example Generation

This work considers attacks mounted with adversarial examples to mislead ML models at test time. We focus on techniques that aim to fool a model into producing untargeted misclassifications (i.e., the model predicts any class other than the ground truth). We first introduce some notation.

Exploring the Space of Transferable Adversarial Examples

Our aim is to evaluate the dimensionality of the adversarial subspace that transfers between models. The FGM discussed above computes adversarial examples by taking one step in the unique optimal direction under a first-order approximation of the model’s loss. However, we know that adversarial examples form a dense space that is (1) at least two-dimensional , and (2) occupies a negligible fraction of the entire input space . This raises the question of how “large” this space is. We considered several techniques to find multiple orthogonal adversarial directions for an input point. Here, we only describe the most successful one. Others are described in Appendix B.

This technique directly estimates the dimensionality of the adversarial subspace under a first-order approximation of the loss function. For an input ${\bm{x}}$, we search the space of perturbations ${\bm{r}}$ (with $\norm{{\bm{r}}}_{2}\leq\epsilon$) that result in a significant increase in loss, i.e., $J({\bm{x}}+{\bm{r}},y)\geq J({\bm{x}},y)+\gamma$, for a $\gamma>0$. We recast this as the problem of finding a maximal set of orthogonal perturbations ${\bm{r}}_{1},{\bm{r}}_{2},\dots,{\bm{r}}_{k}$, satisfying $\norm{{\bm{r}}_{i}}_{2}\leq\epsilon$ and ${\bm{r}}_{i}^{\top}\nabla_{{\bm{x}}}J({\bm{x}},y)\geq\gamma$. We will need the following simple result:

2 Experiments

The GAAS method was the most successful at finding a large number of orthogonal attack directions (see Table 3 in Appendix B for results with other techniques). This gives further evidence that neural networks generalize in an overly linear fashion to out-of-sample data, as first argued by .

We repeat the experiment for two CNNs (model B in Table 2 as source, and A as target). The transfer rate for the FGM is lower for these models ($68\%$). We find fewer orthogonal perturbations on the source model ($15.18$), and, expectedly, fewer that transfer ($2.24$). Yet, with high probability, points in the spanned adversarial subspace mislead the source ($80\%$) and target ($63\%$) models.

Decision Boundary Similarity enables Transferability

Evidenced by Section 3, the existence of large transferable adversarial subspaces suggests that the decision boundaries learned by the source and target models must be extremely close to one another. In this section, we quantitatively characterize this similarity in both adversarial and benign directions. Our measurements show that when moving away from data points in different directions, the distance between two models’ decision boundaries is smaller than the distance separating the data points from either boundary. We further find that adversarial training does not significantly “displace” the learned decision boundary, thus leaving defended models vulnerable to black-box attacks.

Evaluating the decision boundary of an ML model in high-dimensions is usually intractable. We thus restrict ourselves to measuring similarity in three linear directions, which are representative of the model behavior on and off the data manifold. These are illustrated in Figure 3. Each direction is defined by a unit-norm vector relative to a data point ${\bm{x}}$ and some other point ${\bm{x}}^{\prime}$, as ${{\bm{d}}}_{\text{}}(f,{\bm{x}})\coloneqq\frac{{\bm{x}}^{\prime}-{\bm{x}}}{\norm{{\bm{x}}^{\prime}-{\bm{x}}}_{2}}$.

Legitimate direction—Written ${{\bm{d}}}_{\text{leg}}(f,{\bm{x}})$, it is defined by ${\bm{x}}$ and the closest data point ${\bm{x}}^{\prime}$ in the test set with a different class label than ${\bm{x}}$.

Adversarial direction—Written ${{\bm{d}}}_{\text{adv}}(f,{\bm{x}})$, it is defined by ${\bm{x}}$ and an adversarial example ${\bm{x}}^{\prime}\coloneqq adv(f,{\bm{x}})$ generated from ${\bm{x}}$ to be misclassified by $f$.

Random direction—Written ${{\bm{d}}}_{\text{rand}}(f,{\bm{x}})$, it is defined by ${\bm{x}}$ and an input ${\bm{x}}^{\prime}$ drawn uniformly over the input domain, conditioned on ${\bm{x}}^{\prime}$ being classified by $f$ in a different class than ${\bm{x}}$.

These directions are used to define two types of metrics:

Minimum Distances: Given one of the above directions ${{\bm{d}}}_{\text{}}$, the minimum distance from a point ${\bm{x}}$ to the model’s decision boundary is defined as:

Inter-Boundary Distances: We are interested in the distance between the decision boundaries of different models (i.e., the bi-directional arrows in Figure 3). For a point ${\bm{x}}$ and a direction ${{\bm{d}}}_{\text{}}$ computed according to $f_{1}$ (e.g., ${{\bm{d}}}_{\text{}}={{\bm{d}}}_{\text{adv}}(f_{1},{\bm{x}})$), we define the inter-boundary distance between $f_{1}$ and $f_{2}$ as:

In the adversarial direction, the inter-boundary distance is directly related to adversarial example transferability. If the distance is small, adversarial examples crafted from $f_{1}$ that cross the decision boundary of $f_{1}$ are likely to also cross the decision boundary of $f_{2}$: they transfer.

2 Experiments with the MNIST and DREBIN Datasets

We study three models trained on the MNIST and DREBIN tasks: a logistic regression (LR), support vector machine (SVM), and neural network (DNN architecture C in Table 2). For all pairs of models, we compute the mean inter-boundary distance in the three directions: legitimate, adversarial and random. The mean minimum distance in the same direction acts as a baseline for these values.

Minimum Distance Measurements: Distances to the decision boundary are indicated by filled black bars in Figure 4. As expected, the distance is smallest in adversarial directions. Moreover, decision boundaries are further away in random directions than in directions between the different classes. This corroborates the observation that random noise does not usually cause misclassification .

Inter-Boundary Distances: We now compare inter-boundary distances (hatched bars) with minimum distances (filled black bars). For most pairs of models and directions, the minimum distance from a test input to the decision boundary is larger than the distance between the decision boundaries of the two models in that direction. For the adversarial direction, this confirms our hypothesis on the ubiquity of transferability: for an adversarial example to transfer, the perturbation magnitude needs to be only slightly larger than the minimum perturbation required to fool the source model. The results with the SVM as source model are quantitatively different (the inter-boundary distances in the adversarial directions are much larger). This is likely due to our SVM implementation using a “one-vs-rest” strategy, which yields a different optimization problem for crafting adversarial examples.

3 Impact of Adversarial Training on the Distance between Decision Boundaries

Surprisingly, it has been shown that adversarial examples can transfer even in the presence of explicit defenses , such as distillation or adversarial training . This suggests that these defenses do not significantly “displace” a model’s decision boundaries (and thus only marginally improve its robustness). Rather, the defenses prevent white-box attacks because of gradient masking , i.e., they leave the decision boundaries in roughly the same location but damage the gradient information used to craft adversarial examples. Hereafter, we investigate to what extent adversarial training displaces a model’s decision boundaries.

We repeat the measurements of minimal and inter-boundary distances with a pair of DNNs, one of which is adversarially trained. We use the undefended model as source, and target the adversarially trained model. For all directions (legitimate, adversarial and random), we find that the inter-boundary distance between the source and target models is increased compared to the baseline in Figure 4. However, this increase is too small to thwart transferability. In the adversarial direction, the average inter-boundary distance increases from $0.32$ (when the target is undefended) to $0.63$ (when the target is adversarially trained). The total perturbation required to find a transferable input (the minimum distance of $1.64$ summed with the inter-boundary distance) remains smaller than the adversarial perturbation of norm $5$. Thus, adversarial perturbations have sufficient magnitude to “overshoot” the decision boundary of the source model and still transfer to the adversarially trained model.

The transferability of adversarial examples from undefended models to adversarially trained models is studied extensively by Tramèr et al. . The insights gained yield an improved adversarial training procedure, which increases the robustness of models to these black-box transferability-based attacks.

Limits of Transferability

Recall the hypothesis on the ubiquity of transferability formulated in the introduction: {quoting} If two models achieve low error for some task while also exhibiting low robustness to adversarial examples, adversarial examples crafted on one model transfer to the other. We first derive conditions on the data distribution $\mu$ under which a form of this hypothesis holds. However, we also show a counter-example: a specific task for which adversarial examples do not transfer between linear and quadratic models. This suggests that transferability is not an inherent property of non-robust ML models and that it may be possible to prevent black-box attacks (at least for some model classes) despite the existence of adversarial examples. We consider adversaries that attack a target model by transferring adversarial examples crafted on a locally trained model. Note that if an adversary can mount a model theft attack that recovers a sufficiently close approximation of the target model, then any model vulnerable in a white-box setting can be attacked.

We present sufficient conditions under which a specific type of adversarial perturbation transfers from input space to richer latent feature spaces in binary classification tasks. These perturbations are model agnostic; they shift data points in the direction given by the difference between the intra-class means. We consider binary classifiers $f({\bm{x}})={\bm{w}}^{\top}\phi({\bm{x}})+b$ defined as the composition of an arbitrary feature mapping $\phi({\bm{x}})$ and a linear classifier. These include linear models, polynomial models and feed-forward neural networks (where $\phi$ is defined by all but the last layer of the network).

Under natural assumptions, any linear classifier with low risk will be fooled by perturbations in the direction of the difference in class means (this follows from a result by Fawzi et al. ). Moreover, for classifiers over a richer latent feature set (e.g. quadratic classifiers), we relate robustness to these perturbations to the extent in which the direction between the class means in input space is preserved in feature space. This is a property solely of the data distribution and feature mapping considered.

For a fixed feature mapping $\phi$, we consider the perturbation (in feature space) that shifts data points in the direction given by the difference in intra-class means. Let

where $\mu_{-1}$ and $\mu_{+1}$ respectively denote the data distributions of the positive and negative class. For an input $({\bm{x}},y)$, we define the feature-space perturbation ${\bm{r}}_{\phi}\coloneqq-\epsilon\cdot y\cdot\hat{{\bm{\delta}}}_{\phi}$, where $\hat{{\bm{v}}}$ denotes a non-zero vector ${\bm{v}}$ normalized to unit norm. For large $\epsilon$, the feature-space perturbation ${\bm{r}}_{\phi}$ will fool any model $f$ if the weight vector ${\bm{w}}$ is aligned with the difference in class means ${\bm{\delta}}_{\phi}$, i.e. we have:

For some tasks and model classes, we empirically show that the assumption in (5) must hold for $f$ to obtain low error. Following , we need $\epsilon\approx\norm{{\bm{\delta}}_{\phi}}_{2}$ on average to fool $f$ (see Appendix C.2). For tasks with close class means (e.g., many vision tasks ), the perturbation is thus small.

Do model-agnostic perturbations in input space transfer to models over richer latent feature spaces? Let ${\bm{\delta}}$ and ${\bm{r}}$ denote the difference in means and model-agnostic perturbation in input space, i.e.,

If the weight vector ${\bm{w}}$ is aligned with the difference in class means in feature space ${\bm{\delta}}_{\phi}$, a sufficient condition for transferability is that ${\bm{r}}$ gets mapped to a perturbation in feature space that is closely aligned with ${\bm{\delta}}_{\phi}$, i.e., $\phi({\bm{x}}+{\bm{r}})\approx\phi({\bm{x}})+{\bm{r}}_{\phi}$. Specifically, consider the orthogonal decomposition

where ${\bm{\delta}}_{\phi}^{\bot}$ is orthogonal to ${\bm{\delta}}_{\phi}$ and of equal norm (i.e., $||{\bm{\delta}}_{\phi}^{\bot}||_{2}=||{\bm{\delta}}_{\phi}||_{2}$). Intuitively, we want $\alpha$ to be large, and $\beta$ small. If so, we say the mapping $\phi$ is pseudo-linear in ${\bm{r}}$. Our main theorem (which we prove in Appendix C.2) is as follows:

Experiments on MNIST.

We empirically assess the validity of our analysis on the binary task of distinguishing $3$’s and $7$’s from the MNIST dataset. We use linear models, quadratic models ($f({\bm{x}})={\bm{x}}^{\top}A{\bm{x}}+b$, where $A$ is a symmetric matrix), DNNs and CNNs. All models are interpreted as having the form $f({\bm{x}})={\bm{w}}^{\top}\phi({\bm{x}})+b$ for some appropriate mapping $\phi$.

All models satisfy the assumption in Equation (5): the linear model in feature space is strongly aligned with the difference in class means. In fact, we find that any linear or quadratic model that does not satisfy this assumption has low accuracy for this task. We use the mean-shift perturbation ${\bm{r}}$ defined in (6) with $\epsilon=4$. Examples of perturbed inputs are in Figure 5; the correct labels are self-evident despite the appearance of a faint “ghost” digit in some images.

Table 1 reports the accuracy of each model on clean data and perturbed inputs. All models are partially fooled by these small model-agnostic perturbations. In addition, we report whether each model satisfies the technical conditions of Theorem 2 (i.e., the pseudo-linearity of mapping $\phi$ with respect to the perturbation ${\bm{r}}$). Since the quadratic feature mapping satisfies these conditions, any quadratic classifier with high accuracy (and thus positive alignment between ${\bm{w}}$ and ${\bm{\delta}}_{\phi}$) will be vulnerable to these perturbations. Thus, any accurate pair of linear and quadratic classifiers for this task will exhibit transferability. This is a special case of the hypothesis formulated at the beginning of this section. The pseudo-linearity condition does not hold for the CNN: the perturbation direction is not sufficiently preserved in feature space for our result to hold unconditionally. However, our bounds are (expectedly) somewhat loose and we find that the CNN still misclassifies $24\%$ of perturbed samples.

Experiments on DREBIN.

We evaluated the same model-agnostic perturbations on the DREBIN dataset. It is noteworthy that on DREBIN, the class mean is less semantically meaningful than on MNIST (i.e., the mean feature vector of all malware applications is unlikely to even belong to the input space of valid programs). Yet, the same perturbation (followed by rounding to binary features) reliably fools both a linear model and a DNN. By modifying fewer than $10$ of the $1000$ binary features on average, the accuracy of the linear model drops to $65\%$ and that of the DNN to $72\%$.

2 XOR Artifacts

The previous analysis shows that transferability can be inherent if models are defined on (or learn) feature representations that preserve the non-robustness of input-space features. We now show that if models were to learn very different sets of (possibly non-robust) features, transferability need not hold. As a thought-experiment, consider two models trained on independent subsets of the input features. In this setting, adversarial examples crafted to specifically mislead one of the models would not transfer to the other. However, it is expected that adversarial examples crafted on a model trained over the full feature set would still transfer to both models. Hereafter, we ask a more realistic question: for a given task, can models with access to the same set of input features learn representations for which adversarial examples do not transfer to one another—even when these models are not robust to their own adversarial examples. We provide a simple example of a task for which this is true.

Both models trained on this data remain vulnerable to small, but different, adversarial perturbations. The linear model is fooled by standard FGM examples and the quadratic model is fooled by flipping the sign of the two center pixels. Neither of these perturbations transfers to the other model. Fooling both models simultaneously requires combining the perturbations for each individual model. Our experiment on this artificially altered dataset demonstrates how different model classes may learn very different concepts that, while strongly predictive, have little correspondence with our visual perception of the task at hand. It is interesting to consider whether any real datasets might exhibit a similar property, and thus result in learned models exhibiting low transferability.

Acknowledgments

We thank Ben Poole and Jacob Steinhardt for feedback on early versions of this work. Nicolas Papernot is supported by a Google PhD Fellowship in Security. Research was supported in part by the Army Research Laboratory, under Cooperative Agreement Number W911NF-13-2-0045 (ARL Cyber Security CRA), and the Army Research Office under grant W911NF-13-1-0421. The views and conclusions contained in this document are those of the authors and should not be interpreted as representing the official policies, either expressed or implied, of the Army Research Laboratory or the U.S. Government. The U.S. Government is authorized to reproduce and distribute reprints for government purposes notwithstanding any copyright notation hereon.

References

Appendix A Neural Network Architectures

Appendix B Finding Multiple Adversarial Directions

Our first two techniques iteratively solve some optimization problem with an additional constraint enforcing orthogonality of the solutions. The latter two estimate the dimensionality of the adversarial space more directly, using first-order approximations of the model’s output or loss.

Consider an analog of the FGM with a second-order approximation of the loss function. That is, we want a perturbation ${\bm{r}}$ that solves $\max_{\|{\bm{r}}\|\leq\epsilon}\ {\bm{g}}^{\top}{\bm{r}}+\frac{1}{2}{\bm{r}}^{\top}H{\bm{r}}$, where ${\bm{g}}=\nabla_{{\bm{x}}}J({\bm{x}},y)$ is the gradient and $H=\nabla^{2}_{{\bm{x}}}J({\bm{x}},y)$ is the Hessian of the loss function.

We can find orthogonal perturbations as follows: Given a first solution ${\bm{r}}_{1}$ to the above optimization problem, we substitute ${\bm{g}}$ and $H$ by ${\bm{g}}^{\prime}\coloneqq P{\bm{g}}$ and $H^{\prime}\coloneqq P^{\top}HP$, where $P$ is a projection matrix onto the space orthogonal to ${\bm{r}}_{1}$. The solution ${\bm{r}}_{2}$ to the updated problem is then orthogonal to ${\bm{r}}_{1}$.

Convex Optimization for Piecewise Linear Models.

An entirely different approach to finding adversarial examples was proposed by Bastani et al. for the (ubiquitous) case where the model $f$ is a piecewise linear function (here we identify the output of $f$ with the vector of unnormalized log-probabilities preceding the softmax output). Instead of relying on a linear approximation of the model’s output, their idea is to restrict the search of adversarial perturbations for an input ${\bm{x}}$ to the convex region $Z({\bm{x}})$ around ${\bm{x}}$ on which $f$ is linear.

Let ${\bm{x}}$ be a point that $f$ classifies as class $s$ (i.e., $\operatorname*{arg\,max}f_{i}({\bm{x}})=s$). Further let the “target” $t$ be the class to which $f$ assigns the second-highest score. The approach from consists in finding a perturbation ${\bm{r}}$ as a solution to a convex program with the following constraints, denoted $C({\bm{x}})$:

${\bm{x}}+{\bm{r}}\in Z({\bm{x}})$, which can be expressed as a set of linear constraints (see for more details).

$\|{\bm{r}}\|\leq\epsilon$ (although Bastani et al. focus on the $l_{\infty}$ norm, any convex norm can be used).

$f_{t}({\bm{x}}+{\bm{r}})<f_{s}({\bm{x}}+{\bm{r}})$.

If all constraints are satisfied, ${\bm{x}}+{\bm{r}}$ must be misclassifed (possibly as another class than the target $t$).

We suggest an extension to this LP for finding orthogonal adversarial directions. After finding a solution ${\bm{r}}_{1}$ with constraint set $C({\bm{x}})$, we extend the constraints as $C^{\prime}({\bm{x}})\coloneqq C({\bm{x}})\wedge({\bm{r}}^{\top}{\bm{r}}_{1}=0)$, and solve the convex program again to find a new solution ${\bm{r}}_{2}$ orthogonal to ${\bm{r}}_{1}$. This process is iterated until the constraints are unsatisfiable.

Independent JSMA.

For discrete features, such as in the DREBIN dataset, it is difficult to find (valid) orthogonal perturbations using the previous methods.

Instead, we propose a simple non-iterative variant of the Jacobian-based Saliency Map Attack (JSMA) from . This iterative method evaluates the Jacobian matrix of the model $f$ and ranks features in a saliency map that encodes the adversarial goal . A few input features (typically one or two) with high saliency scores are perturbed (i.e., increased to their maximum value) at each iteration, before repeating the process with the modified input.

We compute the saliency map as in and rank the features by their saliency scores. Given a target dimensionality $k$ and a maximal perturbation budget $B$, we group the most salient features into $k$ bins of at most $B$ features each, such that the sum of saliency scores in each bin are roughly equal (we greedily add new features into the non-full bin with lowest total score). As the $k$ sets of features are independent by construction, they naturally yield orthogonal perturbations. We repeat this process for multiple values of $k$ to estimate the dimensionality of the adversarial space.

B.1 Prefiltered Evaluation of the Transfer Rate

To evaluate the transferability from one model to another, we report accuracy in “the prefiltered case,” as done by . That is, we report the accuracy of the target model on adversarial examples that meet three criteria: 1) the original example did not fool the first model, and 2) the adversarial example successfully fools the first model. Departing from the metric used by , we also require that 3) the original example did not fool the target model. This evaluation metric focuses on the transferability property rather than effects like natural inaccuracy of the models or failure of the adversarial example construction process. Accuracy in this prefiltered case can be considered the "transfer rate" of the adversarial examples.

B.2 Experiments

This attack is not interesting for rectified linear units, because the Hessian of the logits with respect to the inputs is zero (or undefined) everywhere. In order to study this attack with a nonzero Hessian, we use hyperbolic tangent rather than rectified linear units in the source model. Yet, we still find that $H$ has only small entries and that the optimal solution to the quadratic problem is close to perfectly aligned with the gradient. The best solution that is orthogonal to the gradient is non-adversarial. Thus, the second-order approximation is of little use in finding further adversarial directions.

Convex Optimization.

On the source model f${}_{\text{src}}$, the LP yields an adversarial example for $93\%$ of the test inputs. By solving the LP iteratively, we find a little over $2$ orthogonal perturbations on average, and $47$ for the “most vulnerable” input. As we restrict the search to a region where the model is linear, these orthogonal perturbations span a dense subspace. That is, any perturbation of norm $\epsilon$ in the spanned subspace is also adversarial.

However, the transfer rate for these perturbations is low ($17\%$ compared to $95\%$ for the FGM). When considering the full adversarial subspace, the transferability increases only marginally: for $70\%$ of the inputs, none of the successful perturbations on model f${}_{\text{src}}$ transfers to model f${}_{\text{target}}$. Thus, although the LP approach may find smaller adversarial perturbations and in more directions than methods such as FGM , we also find that it is less effective at yielding transferable perturbations. The approach of Bastani et al. sometimes fails to produce adversarial examples. For instance, for architecture C in Table 2 and perturbations $\norm{{\bm{r}}}_{2}\leq 5$, the obtained LP is solvable for $0\%$ of tested inputs, whereas the FGSM always yields a successful adversarial example.

Independent JSMA.

We evaluated the JSMA variant on the DREBIN dataset, for the same DNN models as above. With a maximal budget of $10$ flipped features per perturbation, we find at least one successful perturbation for $89\%$ of the inputs, and $42$ successful independent perturbations on average. Of these, $22$ transfer to the target model on average.

Although we did not verify that all these perturbations truly retain the (non)-malicious nature of the input program, we note that flipping a random subset of $10$ input features does not cause the models to misclassify at a higher rate than on clean data. As our pre-processing of the DREBIN dataset selects those features that have a large impact on classification (and thus are often useful to adversaries), we don’t expect the number of independent perturbations to increase significantly for variants of DREBIN with larger feature dimensionality.

Appendix C Proofs

We begin with the upper bound. Let $\hat{{\bm{r}}}_{i}\coloneqq\frac{{\bm{r}}_{i}}{\norm{{\bm{r}}_{i}}_{2}}$. Note that if ${\bm{r}}_{1},{\bm{r}}_{2},\dots,{\bm{r}}_{k}$ are orthogonal, we have

which implies $k\leq\left\lfloor\frac{1}{\alpha^{2}}\right\rfloor$. If $\alpha<\frac{1}{\sqrt{d}}$, the bound $k\leq d$ is trivial.

The vectors ${\bm{r}}_{i}\coloneqq Q^{\top}{\bm{e}}_{i}$ for $1\leq i\leq k$ (these are the first $k$ rows of $Q$) are orthonormal, and satisfy ${\bm{g}}^{\top}{\bm{r}}_{i}=\norm{{\bm{g}}}_{2}\cdot{\bm{z}}^{\top}{\bm{e}}_{i}=\norm{{\bm{g}}}_{2}\cdot k^{-\frac{1}{2}}\geq\norm{{\bm{g}}}_{2}\cdot\alpha$.

C.2 Proof of Theorem 2

A simple adaption of the analysis of Fawzi et al. (for the case of linear models) yields

Lemma 3 is an extension of the result of Fawzi et al. , who show that if the difference in class means is small, any linear model with low risk can be fooled by small perturbations along the direction of ${\bm{w}}$. Because we are interested in the simple “model-agnostic” perturbation that directly follows the difference of means, the magnitude of the perturbation further depends on the alignment $\Delta$ between ${\bm{w}}$ and ${\bm{\delta}}_{\phi}$, which is positive according to the assumption in Equation (5).

We now consider transferability of the perturbation ${\bm{r}}$ in input space. Recalling (7), we can write

Assume $\Delta\gg L(f)$ and suppose first that $\beta=0$. Then, according to Lemma 3, on average, the minimal value of $(-y\cdot\alpha)$ to get $f$ to misclassify is $\approx 1$. However, the contribution of $\beta\cdot{\bm{\delta}}_{\phi}^{\bot}$ has to be taken into account. Note that $\hat{{\bm{w}}}^{\top}\hat{{\bm{\delta}}}_{\phi}^{\bot}\leq 1-\Delta$. Thus, we have

In the worst case, the absolute magnitude of $\alpha$ should be increased by $\frac{1-\Delta}{\Delta}\absolutevalue{\beta}$ to ensure that any non-adversarial contribution of the orthogonal component of the perturbation is canceled out. Thus, in expectation, we need $-y\cdot\alpha\geq 1+\frac{1-\Delta}{\Delta}\absolutevalue{\beta}$ to have $f$ misclassify with non-zero probability. Note that this bound is expected to be loose in practice, as the orthogonal component ${\bm{\delta}}_{\phi}^{\bot}$ is unlikely to be maximally aligned with ${\bm{w}}$.

Appendix D Appendix: Additional Distance Measurements