NETWORK ROBUSTNESS TO PCA PERTURBATIONS
Authors: Anan Kabaha
Dana Drachsler Cohen
Venue:  (2021)
Keywords: neural network robustness
adversarial examples

Abstract: A key challenge in analyzing neural networks' robustness is identifying input features for which networks are robust to perturbations. Existing work focuses on direct perturbations to the inputs, thereby studies network robustness to the lowest-level features. In this work, we take a new approach and study the robustness of networks to the inputs' semantic features. We show a black-box approach to determine features for which a network is robust or weak.  We leverage these features to obtain provably robust neighborhoods defined using robust features and adversarial examples defined by perturbing weak features. We evaluate our approach with PCA features. We show (1) provably robust neighborhoods are larger: on average by 1.8x and up to 4.5x, compared to the standard neighborhoods, and (2) our adversarial examples are generated using at least 8.7x fewer queries and have at least 2.8x lower L2 distortion compared to state-of-the-art. We further show that our attack is effective even against ensemble adversarial training. 

Under review as a conference paper at ICLR 2021
NETWORK ROBUSTNESS TO PCA PERTURBATIONS
Anonymous authors
Paper under double-blind review
ABSTRACT
A key challenge in analyzing neural networks' robustness is identifying input features for which networks are robust perturbations. Existing work focuses direct perturbations to the inputs, thereby studies network robustness to the lowest- level features. In this work, we take new approach and study the robustness of networks to the inputs' semantic features. We show a black-box approach to determine features for which a network robust or weak. We leverage these features to obtain provably robust neighborhoods defined using robust features and adversarial examples defined by perturbing weak features. We evaluate our approach with PCA features. We show (1) our provably robust neighborhoods are larger: on average by 1.5x and up to 4.5x, compared to the standard neighborhoods, and (2) our adversarial examples are generated using least 12.2x fewer queries and have at least 2.8x lower Le distortion compared to state-of-the-an We further show that our attack is effective against ensemble adversarial training.
INTRODUCTION
The reliability of deep neural networks (DNNs) has been undermined by adversarial examples: small perturbations to inputs that deceive the network (e.g.. [Gooffellow et al. (2015))- key step in recovering DNN reliability is identifying input features for which the network is robust. Existing work focuses on the input values, the lowest-level features, to evaluate the network robustness. For example, a lot of work analyzes networks' robustness to neighborhoods consisting of all inputs at certain distance from a given input (e.g., [Boopahh et al. (2019); Katz et al. (017);; Salman et al. (2019); (Singh et al. (2019a); Tjeng et al. (2019): Wang et al. (0018). Despite the variety of approaches introduced to analyze robustness, the diameter e (controlling the neighborhood size)
of the provably robust. neighborhoods is often very small. This may suggest an inherent barrier of neighborhoods. To illustrate, consider Figure [[a] and
the robustness of DNNs to distance-bass
Figure [[b] which are visibly the same but in fact each of their pixels differs by 0.026. That e is
the maximal one for which the Loo ball (x) (x is Figure T a))) was proven robust by ERAN (Singh
al. 2018 Gehr et al. 2018 state-of of-te-of-thearr robustness analyzer.
Feature-defined neighborhoods We propose to analyze network robustness to perturbations of high-level input features. A small perturbation to feature translates to changes of multiple input entries (e.g., image pixels) and as such may produce visible perturbations. To illustrate, consider neighborhood around Figure [[)) in which only the background pixels can change their color. It turns out that, for this neighborhood, ERAN the same robustness analyzer is able to prove a neighborhood which has 10972x more images. Figure ( shows maximally perturbed image in this neighborhood, and Figure [d) illustrates two other images in it. These images are visibly different from Figure a)). Proving such neighborhood robust, for many inputs, can suggest that the network is robust to background color perturbations, thereby provide insights to the patterns the network learned.
Key idea: robust features An inherent challenge in finding robust feature-defined neighborhoods is automatically finding good candidate features (c.g., background color). Part of this challenge stems from the substantial running time of any robustness analyzer on a single neighborhood. This makes brute-force search of deftree neighborhoods for large number of features and inputs futile. We propose sampling approach identify features which are likely to be robust for many inputs. We call these robust features. We experimentally observe that our robust features generalize to unseen inputs, even though they were determined from (small) set of inputs.

---

Under review as a conference paper at ICLR 2021
(a)
(b)
(c)
(c)
(c)
(f)
(8)
48
(h)
48
Figure 1: Network robustness to feature perturbations. (a) An image x from CIFARIO. (b) A maximally perturbed input from the maximally Los neighborhood (x) proven robust by ERAN. (c) A maximally perturbed input (sky color is blue instead of gray) from the maximally feature- defined neighborhood N Naky_color (x) proven robust by ERAN. (d) Other images in N Nekky_coooz (x).
(e) A traffic light image from Imagenet, correctly classified by Inception- V3. (f) Our caature-based adversarial example classified by the same model as crane. (g) A visualization of the difference. (h) Perturbations to the image using the second PCA feature (whose semantic meaning is sky color).
Feature-guided adversarial examples Dually to robust features, we define and identify weak features. We show how to exploit them in a simple yet effective black-box attack. Our attack perturbs given input based on the weak features and then greedily reduces the number of modified pixels to obtain an adversarial example which minimizes the L2 distance from the original input. Figure T Tillustrates our attack on ImageNet with the Inception V3 architecture (Szegedy et al. 2016). Figure (e) shows a traffic light image (correctly classified), Figure([[t shows our feature-guides adversarial example (classified as crane), and Figure [[g] visualizes the difference between the two images. We experimentally show that our attack is competitive with state-of ifae-oof-the-are practical black-box attacks (AutoZoom by [Tu et al. (2019) and GenAttack by Alzantot al. (2019) and fools the ensemble ad adversarial training defense by Tramèr et al. (2018). Our results strengthen the claim of Myas et al. (2019) who suggested that weak (non-robust) features of the data contribute to the existence of adversarial examples. However, unlike Ilyas et al. (2019), we do not focus on features that stem from the DNN. This allows us expose interesting patterns, expressed via simple functions, that the DNN has learned or missed.
PCA features We obtain an initial set of features by rumning principal component analysis (PCA). PCA provides us with an automatic way to extract useful features from a dataset. For example, the sky color feature of the airplane in Figure Ta) is in fact the second PCA dimension of this class of images in CIFARIO. Figure shows the effect of perturbing this feature by small constants (multiplied by 8 = 5) in the PCA domain and projecting it back to the image domain. Our choice of using PCA is inspired by earlier work. We hypothesized that DNN may learn (some) of the PCA features by relying on works that showed that PCA can capture semantic features of the dataset (e. Zhoua et al. (208); Dollifee (2002) and that DNNs learn semantic features (e.g.. Zeilerr & Fergus (2014)). Further, PCA has been linked to adversarial examples: several works showed how to detect adversarial examples using PCA (Hendrycks & Gimpel. 2017 Jere et al. 2019 Li Lij 2017), others utilized PCA to approximate an adversarial manifold (Zhang et al. 2020). 20. and others constructed an attack that modified only the first PCA dimensions (Carlini & Wagner, (017)). Computing the exact PCA dimensions requires perfect-knowledde (e.g., ImageNet). We show that an approximation of the PCA dimensions sufficient to obtain robust and weak features and that these can be computed from a small subset of the dataset (not used for training). The assumption that the attacker has access to a small dataset of similar distribution to the training set is often valid in practice (e.g., for traffic sign recognition benchmarks, like GTSRB, or face recognition applications).
of the dataset and is time-consuming for large datasets
We evaluate our approach on six datasets and various network architectures. Results indicate that (I) compared to the standard neighborhoods. our provably robust feature-guided neighborhoods have larger volume, on average by 1.5x and up 4.5x, and they contain 107 x more images (average is taken over the exponent), and (2) our adversarial examples are generated using at least 12.2x fewer queries and have at least 2.8x lower L2 distortion compared to of-te-of-the-an art practical black- box attacks. We also show that our attack is effective even against ensemble adversarial training.
To conclude, our main contributions are:
2

---

Under review as a conference paper at ICLR 2021
Definitions of networks' robustness and weakness feature perturbations (Section
A sampling algorithm for finding the most robust and weakest features (Section
Feature-based neighborhoods and their robustness analysis (Section
Feature-based adversarial examples (Section 5).
Instantiation with PCA features (Section (6)
Extensive evaluation of our approach (Section 7
2 ROBUST AND WEAK FEATURES
In this section, we define robust and weak features. We focus on classifiers, D: D: RR + R", given as black-box, and trained input-output pairs (x, sampled from distribution T. We denote by class(D(x)) the classification of x by D (i.e., the index i maximizing D(r).).
Features A feature function f gd + Rd is a bijective function mapping inputs to real-valued vectors. The assumption that is bijective simplifies definitions but these can be extended to other kinds of feature functions. The 1th component feature function f called the feature of f.
Feature perturbation For feature function f: Rd - Rdd index i, and scalar E R, we define the perturbation of x along feature by as follows: 2f.5 = (f(xx) + d(a)), where d(i) E R is vector whose entries are zero except for the 7th entry which is 6.
Network robustness to features perturbations Given feature function f. an index i, and a scalar 5 E R+, say the feature of is 8-robust if any perturbation to the feature up 5 does not decrease the class confidence of D on x denoted by CC(D, x) (shortly defined). Formally:
PP ((c,,)-7((V8'' E 60, (0).ccas((((Fa..)))))
class(D and (C(D,IJA48) 2 CC(D,=))
The expression [:] is the Iverson bracket: is if the formula evaluates to true, and otherwise. We define d-robustness for 5 R similarly (except that 8' [6, O)). If is 8-robust and 5 >> say the robustness direction of i is + (positive); otherwise if 5 < O the direction is (negative).
We define network weakness dually. The feature i of f is 8-weak if any perturbation the feature i up to changes the classification or decreases the class confidence. Formally, for ò E IR::
((x,))-T((68 E [0,6).clan (o..o..ls((((o) (((),s(((() * class (z)) or CC(D, CC(D, = 1.
Class confidence The definition of class confidence CC( x)) is orthogonal to our approach. One define the class probability. However, experimentally observed that it is better to relax the requirement about the absolute value and instead focus on the difference between the probability of the highest ranked class and the second highest, that is:
CC(D,
clt)) max ((x); liE co. (class(D(z))))
Most robust and weakest features Generally, we do not expect to find robust features if the features are defined orthogonally to the network's structure and parameters. However, we relax the definition and quantify the robustness level of feature, we can expose connections between the feature and the network's robustness behavior. We define the robustness level RL as:
RL P (c..))-((VV8' [0, ((aasss((((r,,.))))))))
class(D(z)) and (C..)))..))) Z C))D,.)))
We define the problem of finding the most robust features finding & features maximizing the robustness level. Dually, we define the weakness level and the problem of finding weakest features.
MOST ROBUST AND WEAKEST FEATURES VIA SAMPLING
In this section, we present our approach to approximate the most robust and weakest features via sampling. We approximate these features by checking robustness
inputs from set S (drawn from the distribution T) and by sampling the intervals [0, 6) and [-6, 0] at several points determined by step parameter 7). Algorithm depictt our computation. The time complexity of Algorithm
3

---

Under review as a conference paper at ICLR 2021
Algorithm 1:
S, 8))
Input: classifier D, input output pairs S, a feature function f. a number of features d, a number k; scalars á and (precondition: 0 < 7 S å and k S d.).
Output: most robust features and weakest features along with their direction.
RL = 00. ................................ 0]: W L [0, .........:. 0j:
for i E 0 .................... d 1] do
for 2x S do
r= true; w = true:
for 8' 77; 8; do
if class ((( # class class(((x)) or CC(D, < xC(D,z) then r=lase;
else w=false;
if r then RL[(i,
RL +) +
if w then W L[(( [Li // similar check for the negative direction (with -1 and -8) to update the key (i, -)
return The keys (index-directin pairs) of the k maximal entries in RL and W L
linear in d [0/n] (Ip + +b), where d is the number of features, Tp the time to compute the feature perturbation f.,,, and Tn the time run 2 f.5." through the classifier D. The number of queries to the network is at most 2- d- |S|. [5/n] + [S]. The term |S| counts the number of queries for computing class( (x)) and CC(D, x)) for every (x. E S, computed once at the beginning of Algorithm (this step is omitted from Algorithm [ simplicity's 's sake).
Our algorithm supports a trade-off between precision and performance: the larger the and the smaller the 7). the more precise the result, but with higher number of queries to the network. In practice, even though Algorithm[]]] iss exccuted once per dataset (after which many neighborhoods can be analyzed for robustness attacks), its running time be high. Thus, in our experiments, we set |SS] to 100, to 1, 000 (i.e., we do not scan all features), and v = 5. Despite these substantial restrictions, we still observe good results in practice (see Section 7). This encourages that even coarse search for robust and weak features is sufficient to obtain larger provably robust neighborhoods and adversarial example attack which competitive with state-of-the-art attacks.
MAXIMALLY ROBUST FEATURE-GUDDE NEIGHBORHOODS
In this section, we define reature-guider neighborhoods and explain how we find maximally robust neighborhoods. Given an input ær feature of f, and a scalar 8 E TR+ the (f, i, neighhoooor of x is the set 5 (x) = { 8' E [0, (the definitions for 5 E R are similar and thus omitted). Given a DNN D, we say that ///((zz (zz) is robust if D classifies all inputs in N (x) the same. Our goal is to find maximally robust (f, i, niighbboossss for a given x and feature of f (i.e., we look for maximal scalar 8 R To this end, we employ binary search in a given range [0, w (where N is a constant). In each iteration of the search, we reason about the robustness of the current neighborhood using an existing analyzer, shortly described. We note that for linear feature functions (e.g., PCA), the binary search is optimal. We further note that although our definition is general for any feature, larger neighborhoods are likely to be defined using the (most) robust features.
To verify robustness of given (f, i, 8) neighbooroood, we translate it to an -orm neighborhood. This neighborhood can be then analyzed using an existing local robust analyzer (e.g.. Gehr al. (2018): Katz et al. (2017); (Singh et al. (2019b)). In - neighborhoods, each input entry (e.g.. pixel) can be perturbed independently. Formally, given an input x and lower and upper bounds for every jth entry </,, ej. the Loe-norn neighborhood is: (xx) = {x' Vj, xtj E { - x + <5]]. (A special case is B. neighborhoods, in which all bounds are e, i.c., for all j. e/j = = = e.) For linear feature functions (e.g., PCA), we translate (f,i, neighboooossshsohoods -nom ones as follows:
(x) (x' Vj. [min((z, (If4)s))) max(a;, (1138))))}.
For other feature functions, one has obtain the minimal and maximal values of each input entry.
4

---

Under review as a conference paper at ICLR 2021
(a) (b)
(c) (d)
(e)
46
26
6
(f)
266 36
Figure 2: (a) frog from CIFARIO. (b) A maximally perturbed frog from the 0.00.024 (a) neighborhood - the maximal proven robust. (c) A maximally perturbed frog from the (PCA, 0, 6)- neighborhood (6 -.666). (d)+(e) Two other images in the (PCAA 0, neighbbooor of (f) Perturbations to x using the PCA feature 0 (whose semantic meaning is background lighting level).
FEATURE-GUIDED ADVERSARIAL EXAMPLES
In this section, we present our feature-guided attack which perturbs the weakest features. Our attack consists of two steps: perturbing the weakest features by a small and then greedily refining the adversarial example. In addition the expected parameters (the classifier D. the input-output pair (z, z), and the feature function f), the attack takes as input the set of weak features W consisting of indices and directions, a step scalar gado and maximal distortion scalar 8M The first step of the attack looks for the smallest S 5', with granularity 5ado for which f.,,, is an adversarial example. Here, z & = (f(x) + 6w), where ow E IRd is a vector whose entries are zero except for indices from W whose entries are or -5 depending on their direction. an adversarial example is found, the second step of the attack refines it by greedily attempting to recover pixels to their original value in æ, while still guaranteeing that the example is misclassified by D. To reduce the number of queries to D and converge faster to a minimal adversarial example, the attack attempts to recover groups of adjacent pixels (e.g., of size 50) together. it fails, cuts the group size in half. In practice, observe that this approach provides good balance between reducing the number of queries and recovering many input entries to their original value.
6 INSTANTIATION WITH PCA
In this section, we explain how we use PCA to instantiate our approach. We begin with brief background, then present our instantiation and exemplify PCA-guided neighborhoods and attacks.
Background PCA projects inputs into an (interesting) set of features (dimensions), each represents different aspect of the data and captures different amount of variance (information). Technically, PCA a statistical framework that projects a random variable such that the components {y, )d are uncorrelated and have maximal variance values. The set {ur)i_ is defined by = u! x E R. such that u, E Rd, where the u,-s are the principal components of x. The principal components are computed with the goals (1) maximizing the variance of the components [w: )d and (2) keeping these components uncorrelated. In practice, instead of the random variable x, we consider data matrix X, consisting of n input samples. Given the principal components, we define the PCA transformation matrix by U [u] U2 ... ual. We use U to project the dataset into the PCA domain and vice versa: XU E R Raxd X YUT E Raxd
Rdd onto a random variable y E Rd
PCA feature functions We observed that PCA provides better features when computed for inputs of the same class. Thus, for each class z, we define feature function PCA, the PCA transformation matrix computed from inputs with output z. As a result, Algorithm is executed times, where is the number of classes. The running time of computing the PCA feature functions c m d3). In practice, we only compute the first d = 1, 0000 PCA dimensions. Combined with the small size of (IS) 100 per class), the running time is few minutes per class.
US. where U₂
We next show an example of a (PCA, i, 5) neighborhood (Appendix A shows more examples). Figure 2aa) shows frog image x from CIFAR10. The maximal for which the B. Bx(x:) was proven
5

---

Under review as a conference paper at ICLR 2021
Traffic sign - Missile
Ostrich - Hartebeest
T. Blair - G. W. Bush
Figure 3: PCA-guided adversarial examples.
0.024. Figure bb) shows maximally perturbed image in this neighborhood. The maximal for which the N PC was proven robust by ERAN was 6.66 (the feature O represents lighting conditions). This PCA-guided neighborhood contains 10700x more images than the B. (x) neighborhood. Figure shows maximally perturbed image in this neighborhood, while Figure dj) and Figure 2(e) show two other images in it. Figure 2in) illustrates semantic meaning the feature we perturb (background lighting conditions): it shows several images obtained by first perturbing this feature in the PCA domain by small constant (a multiplication of 5) and then projecting the PCA perturbation back to the image domain.
robust by ERAN (Gehr et al. 2018)
Figure 3 shows examples of our PCA-guided attack (Appendix A has more examples). Each example shows a correctly classified input, our adversarial example, and the perturbation (scaled for better visualization). The leftmost example shows a traffic sign image from ImageNet whose adversarial example is classified as missile by Inception- V3. The middle example shows an ostrich image from ImageNet whose adversarial example is classified an hartebeest by the same model. The rightmost image shows an image of Blair whose adversarial example is classified by RESNET20 as Bush.
7 EVALUATION
In this section, we evaluate our approach and the applications from Sections aand
Setup We implemented our approach in Python using Py PyTorch (we also support Tensorflow models). We trained models and ran most experiments on a Tesla K80 GPU with 12GB RAM. Only for running FRAN (Gehr et al., 2018), we used a dual AMD EPYC 7742 server with 1TB RAM running Ubuntu 20.04.1. For computing the most robust and weakest features of a given class, we defined $ as set of 100 random inputs of that class (which were not part of the training set), d = 1, 000 (i.e., we considered only the first 1, 000 PCA features), & 250, and 8 = 1. For (f. i, neighbbbossssss we set N = 100. For our attack, we set 8ade = 0.1 and gar = 10. As an optimization, our approach attack iterates over & (50, 100, 250) to reduce the distortion level. We evaluate
on six datasets (described in Appendix BB. Each is split into a training set, a set for computing [] and ACA+Algori
evaluate neighborhoods and attack. Our attack was tested state-of-the-art networks, and our robustness analysis was done on networks taken from FRAN's repository (denoted by F) and networks whose size similar to the large networks from that repository. We trained most models, except for Inception-V. V3 for ImageNet (Szegedy et al. (2166) and the C&W models (Carlini & Wagner 2017 7) for MNIST and CIFARIO (and models marked with E).
PCA+ Algorithm analysis For each dataset, computed the first d PCA features from the set containing 100 images. This step took less than two minutes for all datasets. Then, for each model, computed the most robust and weakest features among these dimensions. This step is executed once, after which these features are used to define multiple neighborhoods and adversarial examples. This step is executed separately for each class and thus be naturally parallelized. The average running time of Algorithm | was less than 90 seconds for most datasets and models, and at most ten minutes for ImageNet. The number of queries is 2- |S| d classes. While this number is not negligible, it is done as a preprocessing step (similarly to training a model done by other attacks, e.g., et al. (2019)). The amortized added queries of this step over the dataset ranges from a handful of queries (for ImageNet) to a few dozens (for MNIST).
2 10 c, where is the number of
Feature-guided neighborhoods To evaluate robustness of i, (f.ii,)) -eiehboorhoods we ran several experiments. In each experiment, considered small models (3 x 100 and 5 x 5500,, medium-sized models (LeNet5 with ~10,000 neurons), models that are considered big for robustness analysis (C&W W with 77,000 neurons), convolutional
fixed model, dataset, a class, and robust feature i. We

---

Under review as a conference paper at ICLR 2021
Table 1: PCA-guided neighborhoods B. neighborhoods: is the neighhorhood volume, #im the number of images in it, and Iu - - the maximal pixel range. Results are averaged over ten images. We provide graphical interpretation our robust features Figure
Dataset
Model
Class
VPca
V.
#Cmpcs
#
Ju
I 4/PCA
Iu 4/c
MNIST
3 100
2
21.0
20.8
10
10820
0.247
0.046
MNIST
ConvSmall
0
62.6
66.7
1038s
10979
0.76
0.149
MNIST
ConvMaxpool
9
0
1.7
2,9
10a8
10
0,019
0,006
MNIST
VGG-based
0
2.6
1070
0.026
0.003
FMNIST
5 x 250
1
1
8.7
7.5
10208
10245
0,063
0,016
FMNIST
C&W
2
7
3.2
2.4
1087
0.033
0.003
LFW
LeNet5
2
9
9.4
6.6
10
10
0.038
0.008
LFW
C&W
0
2
6.4
4.5
10
0.023
0.004
LFW
C&W
2
9
7.6
5.3
10263
0.031
0.005
GTSRB
LeNetS
14
8
16.0
8.3
10
10347
0.097
0.01
GTSRB
C&W
3
3.5
10205
0.017
0.002
GTSRB
C&W
15
3
3.6
0.8
10"47
0.018
0.001
CIFARIO
LeNet5
9
5.5
4.3
10
0.005
0.001
CIFAR 10
ConySmall
O
1
235.4
186.4
3067
10 2841
0.176
0.063
CIFAR 10
ConvSmall
O
181.8
125.5
102944
1061
0.13
0.041
CIFARIO
Conv Big
3
5
92.9
64.7
102085
10
0.089
0.021
CIFARIO
ConvBig
0
47.9
45,4
104644
10
0.031
0.014
CIFARIO
C&W
1
0
6.4
4.9
10
0.005
0.002
Table 2: Our attack vs. AutoZOOM and C&W. Q4QQ is the number of queries to the network before/after postprocessing, and T.yLT2 is the L2 distance from the original image before/after postprocessing. We abbreviate RESNET with RES and Inception-V2 V3 with Inc
Dataset Model
Our attack
AutoZOOM
C&W
L
Q
L2
Q6
L
Q
L
Qo
L2
x10
x10
x10
x10
x10
x10
x10
MNIST
C&W
3.31
3.2
8.72
3.8
FMNIST
VGG13
0.82
2.6
2.55
19
2.18
3.8
4.54
102
1.87
LFW
RES20
0.40
0.9
1.82
1.60
3.8
3.70
56
0.16
GTSRB
RES20
0.30
3.1
1.24
23
0.94
3.8
3,94
272
0.18
CIFARIO
C&W
0.29
2.9
1.67
0.70
3.8
103
0.12
CIFARIO
RES50
0.27
3.4
1.11
14
0.71
3.8
2,06
70
0.13
CIFAR1O
VGGI6
0.28
3.3
1.69
32
1.52
3.8
7.75
39
0.20
ImageNet
Inc-V3
0.01
217
0.16
42
0.016
250
0.66
2654
0.003
models of different sizes from ERAN's repository, and VGG-based model that trained (~141,000 neurons). We computed the maximally robust (PCA, i, i, neighhhoooss for the first ten images of that class. Table reports the results: the average neighborhood volume (v= Mge e)), the number of images in the neighborhood (shown as a power of ten: 10"; we take the average over the exponent; for average 0, we write 1), and the maximal pixel range (i.e., max <) .j.). We compare our approach with the standard approach of computing maximally robust B. (z) neighborhoods (using binary search and ERAN). Results indicate that (1) our neighborhoods have larger volumes: on average by 1. 1.5x and up to 4.5x; (2) our neighborhoods have 10 more images (average is over the exponent) and, for deep networks or complex datasets, often the maximal B, neighborhood contains a single image, and (3) our neighborhoods have larger maximal pixel range. Figure Figure@iilustrates semantic meaning of the PCA features presented in Table I For each dataset, class, and feature, it shows three images: an initial image (middle) and two images obtained by perturbing the feature by +8 (for some 6). The three images are ordered by the feature's 's robustness direction: if the direction is positive, then the rightmost image is the perturbation with respect +8: otherwise, the rightmost image is the perturbation with respect 85 The arrows in the figure show the robustness direction.
illustrates the

---

Under review as a conference paper at ICLR 2021
mnist, class=2, 1=1
mnist, class=0, i=1
mnist, class=
mnist, class=0, 0,
fmnist, class=1,
2
Z
9 9
digit length
digit's inclination
digit's inclination
digit's roundness
pants' color
fmnist, dass=2, i=7
Ifw, class=2, i-9
Ifw, class=0, i=2
gtsrb, class=14, i=8
gtsrb, class= i=0
STOP
STOP
STOP
sleeve length
face orientation
background darkness
hexagonal shape
background brightness
gtsrb, class=15, i=3
cifar10, class=9, |=1
cifar10, class=0, i=1
cifar10, class=1, i=0
cifar10, class=3, i=5
light direction
color
sky color
lighting conditions
light direction
Figure 4:
Illustration of the semantic meaning of the PCA features used in Table I
Table 3: Our attack vs. AutoZOOM and GenAttack on models trained with ensemble adversarial training. 8% is the success rate and L2 is the L2 distance from the original image.
Dataset
Our attack
AutoZOOM
GenAttack
5%
La (x10
5%
L2 (x10
5%
La (x10
MNIST
100
3.4
65
2.3
95
18.7
F-MNIST
100
0.8
100
2.1
94
11.9
CIFARIO
100
0.3
100
1.3
100
5.1
PCA-guided adversarial examples We next evaluate our attack. In each experiment, fix dataset and model, and run our attack for 100 correctly classified inputs (not used during training or computing the most robust/weakest features). For each adversarial example, we measure the number of queries posed to the network and the T.2 distance from the original image. We measure these twice: (1) after perturbing the weakest features and obtaining the first adversarial example (denoted Q" and I.b) and (2) after the refinement postprocessing step (denoted Q and L2). We compare our approach with state-of-the ootth-ff-theart practical black-box attacks: AutoZOOM by Tu et al. (2019) (which also has refinement postprocessing step) and GenAttack by Alzantot et al. 2019). We also compare our attack to the C&W attack Carlini & Wagner (017), which is a white-box attack (with a full access to the model, including the internal layers unlike
setting which assumes access only to the input and output layers). Table showwws the results for our attack, AutoZoom, and C& W. all of which have success rate of 100%. Results indicate that (1) our attack obtains the initial adversarial examples (before postprocessing) with 12.2x fewer queries and with 2.5x less L2 distortion compared AutoZOOM. (2) considering postprocessing, our attack generates adversarial examples with fewer queries and 2.8x less L2 distortion compared to AutoZOOM, and (3) our black-box attack has 1.8x more L2 distortion than the white-box attack of C& W (this is expected as white-box setting provides the attacker with more knowledge). Due to lack of space, results for GenAttack are in Appendix [ Compared to GenAttack: (1) our attack obtains the initial adversarial examples with 18.7x fewer queries and with 4. Ix less L2 distortion, and (2) our final adversarial examples have 16.77 7x less L2 distortion but with 29x more queries.
We next evaluate our attack for the same 100 inputs models trained with ensemble adversarial training TTamer et al. 2018). To this end, we trained defended models for three datasets using trained RESNET50, RESNETZ and C&W models. We limited the query number to 10, 000. We compare our approach with AutoZoom and GenAttack. Table shows the results. Results indicate that our attack has higher success rate and in most it obtains smaller L, distortion.
In Appendix D we provide experiments comparing our approach to an attack which uses random PCA features instead of the weakest features. These experiments show the advantage of our attack.
8

---

Under review as a conference paper at ICLR 2021
8 RELATED WORK
Adversarial examples and PCA Several works consider PCA for finding and defending against adversarial examples. Some works use it to detect adversarial examples (Hendrycks & Gimpel. 2017] Jere et al., 2019 Li & Li 2017). Bhagoji et al. 2018) train a model using the top-k PCA components, while Carlini & Wagner. (017)) show that this approach is not immune to adversarial examples. These works focus employing PCA as detector of adversarial examples. In contrast, we PCA as a feature extractor. [Sanyal et al. (2020) show that encouraging DNNs to learn representations in lower-dimensional linear subspaces (including PCA) increases their robustness, Jeelly et al. (2018) study classification quality versus vulnerability to adversarial attacks through principal directions and curvatures of the decision boundary. Zhang et al. (2020) use PCA to approximate an adversarial region which enables them to generate adversarial examples without a classifier. In contrast, we look for connections between features and classifiers' behavior.
Feature analysis of DNNs Many works analyze a DNN with respect to features. Goswami et al. (2018) perturb face features manually, e.g., by covering the beard or eyes. Rozsa et al. (2019) focus on face images with pre-labeled features to study DNNs' robustness. Wicker et al. (0188) suggest using SIFT extract images' local features and perturb them. Xie et al. 2019) suggest to denoise the features of the hidden CNN layers to increase robustness. In contrast, we take black-box approach and automatically derive input features for which a DNN is robust. [yas al. (2019) and Goh (2019) define robust and non-robust features (differently from us) and show that adversarial examples are linked to non-robust features. However, their features are inferred from the DNN, unlike our approach which considers features computed from the dataset. Further, we provide an approach to approximate the most robust and weakest features from a large set of features using a black-box access to the DNN.
Gnd
Adversarial examples Many adversarial example attacks were introduced. Some are white-box attacks with full access to the model, e.g., FGSM (Goodfellow et al. 2015). IFGSM (Kurakin et al. 2017). PGD (Madry et al. 2018). C&W (Carlini & Wagner] 2017). and EAD (Chen al. 2018)) While successful, all rely on the assumption that the attacker has full access to the model's parameters, which is often not true in practice. This encouraged others to study black-box attacks which only assume access to network's 's input and output layers (i.e., with no information on the internal layers). Papernot al. (017) show a black-box attack relying on a substitute technique, where the adversary trains a representative network. Such methods suffer from low success-rate because they rely on the assumption of adversarial example transferability, which does not always hold. [Chnn et al. (2017) present black- black-box attack relying on pradient-estimatinn This approach obtains high success-rate however it is inefficient because it requires high number of queries to the network. Recent works introduce practical and efficient black-box techniques: AutoZoom (Tu al.) 2019) uses efficient random madiiet-estimation while GenAttack (Alzantot et al.) 2019) employs a genetic algorithm. In contrast these approaches, black-box box attack depends weak dataset's features.
Local robustness Several works present approaches to analyze local robustness of DNNs. An- derson et al. (2019); Gehr et al. (2018): Ghhrbbl et al. (2009); (ingh et al.] (2018) rely on abstract interpretation, Katz et al. (2017 7 extend the simplex method, Boopathy et al. (2019); Salman et al.) (2019) rely on linear relaxations, Dvijotham et al. (2018); Raghunathan et al. (2018) use duality, and Singh et al. (2019c); Wang et al. (2018) combine solvers with approximate methods. These works analyze the robustness of Loo -nom neighborhoods. BBlunovicc et al. (2019) Engstrom et al.) [Faizi et al. (017)): (Sinhh et al. (2019b) analyze robustness to geometric transtormations (e.g.. rotation, scaling). In contrast, we analyze robustness of neighborhoods defined by input features.
9 CONCLUSION
We presented the concept of network robustness and weakness to feature perturbations. We approxi- mated the most robust and weakest features via sampling and leveraged them to define feature- -guude neighborhoods and adversarial examples. Experimental results show that our provably robust feature- guided neighborhoods are much larger than the standard provably robust neighborhoods and that our adversarial examples require fewer queries and have lower T-z distortion compared vate-of-the-art
9

---

Under review as a conference paper at ICLR 2021
REFERENCES
Moustafa Alzantot, Yash Sharma, Supriyo Chakraborty, Huan Zhang, Cho-Jui Hsich, and Mani B. Srivastava. Genattack: practical black-box attacks with gradient- optimization. Proceedings of the Genetic and Evolutionary Computation Conference, GECCO, 2019.
Greg Anderson, Shankara Pailoor, Isil Dillig, and Swarat Chaudhuri. Optimization and abstraction: synergistic approach for analyzing neural network robustness. In Proceedings of the 40th (ACM) (SIGPLAN) Conference on Programming Language Design and Implementation, (PLDI), pages 731-744, 2019.
Mislav Balunovic, Maximilian Baader, Gagandeep Singh, Timon Gehr, and Martin T. Vechev. Certifying geometric robustness neural networks. In Annual Conference on Neural Information Processing Systems. pages 15287-15297, 2019.
Arjun Nitin Bhagoji, Daniel Cullina, Chawin Sitawarin, and Prateek Mittal. Enhancing robustness of machine learning systems via data transformations. In 52nd Annual Conference on Information Sciences and Systems, CISS, 2018.
Akhilan Boopathy, Tsui-We Weng, Pin-Y Yu Chen, Sijia Liu, and Luca Danie. Cnn-cert: An efficient framework for certifying robustness of convolutional neural networks. In The Thirty-Third AAAI Conference on Artificial Intelligence, AAAI, 2019.
Nicholas Carlini and David A. Wagner. Adversarial examples not easily detected: Bypassing ten detection methods. In Proceedings of the 10th ACM Workshop on Artificial Intelligence and Security, AlSec, 2017.
Nicholas Carlini and David A. Wagner. Towards evaluating the robustness of neural networks. In IEEE Symposium Security and Privacy, SP, 2017.
Pun-Yu Chen, Huan Zhang, Yash Sharma, Jinfeng Yi, and Cho-Jui Hsich. ZOO: zeroth order optimization based black-box attacks to deep neural networks without training substitute models. Proceedings of the 10th ACM Workshop on Artificial Intelligence and Security, 2017.
Pin-Yu Chen, Yash Sharma, Huan Zhang, Jinfeng Yi, and Cho-Jui Hsieh. EAD: elastic-net attacks to deep neural networks via adversarial examples. In Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, 2018.
Krishnamurthy Dvijotham, Robert Stanforth, Sven Gowal, Timothy A. Mann, and Pushmeet Kohli. A dual approach to scalable verification of deep networks. In Proceedings of the Thirty-Fourth Conference Uncertainty in Artificial Intelligence, UAI, 2018.
Logan Engstrom, Brandon Tran, Dimitris Tsipras, Ludwig Schmidt, and Aleksander Madry, Exploring the landscape of spatial robustness. In Proceedings of the 36th International Conference on Machine Learning.ICML, 2019.
Alhussein Fawzi, Seyed-Mohsen Moosavi-Dezfooli, and Pascal Frossard. The robustness of deep networks: A geometrical perspective. In IEEE Signal Process. Mag vol 34 number 6 pages 50-62, 2017.
Timon Gehr, Matthew Mirman, Dana Caatssllr-Chhen. Petar Tsankov, Swarat Chaudhuri, and Martin T. Vechev. A12: safety and robustness certification of neural networks with abstract interpretation. In IEEE Symposium Security and Privacy, pages 3-18, 2018.
Khalil Ghorbal, Eric Goubault, and Sylvie Putot. The zonotope abstract domain taylorl+ In Proc.
Computer Aided Verification (CAV). pages 627-633, 2009.
Gabriel Goh.
discussion of 'adversarial examples are not bugs, they are features': Two examples of useful, non-robust features. Distill, 2019. doi: 1/distiilllll.00001..... https://disiill.pu///9//ee http://000/////xxb//ueaaae bugs-diisuusioorrssposse..
Ian J. Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial
examples. In 3rd International Conference Learning Representations (ICLR), 2015.
10

---

Under review as a conference paper at ICLR 2021
Gaurav Goswami, Nalini K. Ratha, Akshay Agarwal, Richa Singh, and Mayank Vatsa. Unravelling robustness of deep learning based face recognition against adversarial attacks. In Proceedings of the Thirty-Second AAAI Conference Artificial Intelligence, 2018.
Dan Hendrycks and Kevin Gimpel. Early methods for detecting adversarial images. In 5th Interna- tional Conference on Learning Representations, Workshop Track Proceedings, 2017.
Andrew Ilyas, Shibani Santurkar, Dimitris Tsipras, Logan Engstrom, Brandon Tran, and Aleksander Madry. Adversarial examples not bugs, they are features. In Advances in Neural Information Processing Systems 32 Conference, 2019.
Malhar Jere, Sandro Herbig, Christine Lind, and Farinaz Koushanfar. Principal component properties of adversarial samples. CoRR 0bs//992.03440. 2019.
Saumya Jetley, Nicholas A. Lord, and Philip H. S. Torr With friends like these, who needs adversaries? In Anmual Conference on Neural Information Processing Systems 2018, 2018.
I.T Jolliffe. Principal Component Analysis. Springer. 2002.
Guy Katz, Clark Barrett, David L. Dill, Kyle Julian, and Mykel J. Kochenderfer. Reluplex: efficient SMT solver for verifying deep neural networks. In Computer Aided Verification 29th International Conference (CAV), pages 97-117, 2017.
Alexey Kurakin, Ian J. Goodfellow, and Samy Bengio. Adversarial machine learning at scale. In 5th International Conference Learning Representations, ICLR, 2017.
Xin Li and Fuxin Li. Adversarial examples detection in deep networks with convolutional filter statistics. In IEEE International Conference on Computer Vision, ICCV, 2017.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. In 6th International Conference Learning Representations, ICLR, 2018.
Nicolas Papernot, Patrick D. McDaniel, Ian J. Goodfellow, Somesh Jha, Z. Berkay Celik, and Ananthram Swami. Practical black-box attacks against machine learning. Proceedings the 2017 ACM on Asia Conference on Computer and Communications Security, AsiaCCS, 2017.
Aditi Raghunathan, Jacob Steinhardt, and Perey Liang. Certified defenses against adversarial examples. In 6th International Conference on Learning Representations, ICLR, 2018.
Andras Rozsa, Manuel Günther, Ethan M. Rudd, and Terrance E. Boult. Facial attributes: Accuracy and adversarial robustness. In Pattern Recognit. Lett., 2019.
Hadi Salman, Greg Yang, Huan Zhang, Cho-Jui Hsieh, and Pengehuan Zhang. convex relaxation barrier to tight robustness verification of neural networks. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems, 2019.
Amartya Sanyal, Varun Kanade, Philip HS Torr, and Puneet K Dokania. Robustness via deep low-rank representations. arXiv:1804.07090 2020.
Gagandeep Singh, Timon Gehr, Matthew Mirman, Markus Püschel, and Martin T. Vechev. Fast and effective robustness certification. In Advances in Neural Information Processing Systems 31 Conference, pages 10825-10836, 2018
Gagandeep Singh, Rupanshu Ganvir, Markus Püschel, and Martin T. Vechev. Beyond the single neu- ron convex barrier for neural network certification. In Advances in Neural Information Processing Systems 32: Annual Conference Neural Information Processing Systems 2019, NeurIPS 2019, 8-14 December 2019, Vancouver, BC, Canada, pp. 15072-15083, 2019a.
Gagandeep Singh, Timon Gehr, Markus Püschel, and Martin Vechev. An abstract domain for certifying neural networks. In Proc. ACM Program. Lang. pages 41:1-4, 2019b.
Gagandeep Singh, Timon Gehr, Markus Püschel, and Martin T. Vechev. Boosting robustness certification of neural networks. In 7th International Conference on Learning Representations, ICL.R, 2019c.
11

---

Under review as a conference paper at ICLR 2021
Christian Szegedy, Vincent Vanhoucke, Sergey loffe, Jonathon Shlens, and Zbigniew Wojna. Re- thinking the inception architecture for computer vision. In 2016 IEEE Conference on Computer Vision and Pattern Recognition, CVPR, pp. 2818-2826. IEEE Computer Society, 2016.
Vincent Tjeng, Kai Y. Xiao, and Russ Tedrake. Evaluating robustness of neural networks with mixed integer programming. In 7th International Conference on Learning Representations, ICLR, 2019.
Florian Tramèr, Alexey Kurakin, Nicolas Papernot, Ian J. Goodfellow, Dan Boneh, and Patrick D. McDaniel. Ensemble adversarial training: Attacks and defenses. In 6th International Conference on Learning Representations, ICLR, 2018.
Chun-Chen Tu, Pai-Shun Ting, Pin- Yu Chen, Sijia Liu, Huan Zhang, Jinfeng Yi, Cho-Jui Hsieh, and Shin-Ming Cheng. Autozoom: Autoencoder-hee based zeroth order optimization method for attacking black-box neural networks. The Thirty-Thiin Third AAAI Conference Artificial Intelligence, AAAI, 2019.
Shiqi Wang, Kexin Pei, Justin Whitehouse, Junfeng Yang, and Suman Jana. Efficient formal safety analysis of neural networks. Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems, 2018.
Matthew Wicker, Xiaowei Huang, and Marta Kwiatkowska. Feature- Feature-guided black-box safety testing of deep neural networks. In Tools and Algorithms for the Construction and Analysis of Systems- 24th International Conference, TACAS, 2018.
Cihang Xie, Yuxin Wu, Laurens der Maaten, Alan I.. Yuille, and Kaiming He. Feature denoising for improving adversarial robustness. In IEEE Conference on Computer Vision and Pattern Recognition, CVPR, 2019.
Matthew Zeiler and Rob Fergus. Visualizing and understanding convolutional networks. In Computer Vision ECCV 2014 13th European Conference., 2014.
Yonggang Zhang, Xinmei Tian, Ya Li, Xinchao Wang, and Dacheng Tao. Principal component adversarial example. IEEE Trans. Image Process., 2020.
Huiyu Zhoua, Yuan YuanbAbdul, and H.Sadkaa. Application of semantic features in face recognition. In Pattern recognition, vol 41, Pages 3251-3256., 2008
12

---

Under review as a conference paper at ICLR 2021
F-MNIST
Model: 2 x 100-fully connected
e 040 8 3.477 i=
1ppA 0.18, ju LPPCA 0.32
MNIST
Model: x 100-fully connected
0.047, 9. 62, 1=1
Iu PCA 0.13, - PCA -
GTSRB
Model: LeNet5
30
30
30
30
30
0. 0.000, 8 5. 44, i
1 PCA 0.36. uu
1 max
0.46
(a)
(b)
(c)
(d)
(e)
Figure 5: Examples of provably robust PCA-guided neighborhoods. (a) An input x. (b) A maximally perturbed input from the (x) neighborhood, for the maximal proven robust indicated the left). (c) A maximally perturbed input from the (PCA, A, 1, ô) nnighhoorhood of æ (6 is indicated the left). (d)+(e) Two input examples the (PCA, 1, 6) neighbooodd æ.
A ADDITIONAL EXAMPLES
In this section, we show more examples of provably robust feature- guiieed neighborhoods and PCA-guided adversarial examples.
In Figure 5
we show for each dataset:
image;
maximally perturbed input from the (x neighborhood, for the maximal that ERAN proved robust shown in the figure);
maximally perturbed input from the (PCA, A, 1, neeghhoooodood (ō is shown in the figure); two more input examples from the (PCA, 1, njiihhhooooo
In the figure, also indicate the average range of pixels (when translating the PCA features to the input domain) Iu - t0 and the maximal range of pixels Iu |PCAA In (x) neighborhoods, Iu 1--/e l/. for all pixels.
These examples demonstrate that (1) provably robust PCA-guided neighborhoods are larger than their corresponding (x) neighborhoods and (2) provably robust PCA-guided neighborhoods contain inputs which are semantically similar to the original image but are also visually different from it.
In Figure 6 show PCA-guided adversarial examples, for ImageNet and Inception-V V3 model, computed on correctly classified inputs. The figure shows: the original image (left), the PCA-guided adversarial example (center), and the perturbation (right).
B DATASETS
In this section, we describe the datasets we used our evaluation.
MNIST: 28 x 28 images of 0-9 digits, ten classes. 28 pixel images of fashion items, ten classes.
Fashion MNIST (F-MNIST):
CIFARIO: 32 x 32 x 3 pixel images, ten classes.
We imported these datasets from the PyTorch library. We also considered the following datasets:
LFW sklearn version: 62 x 47 images of funneled faces, each classified as person. In total, there are 5,749 different people (i.e., classes) and the dataset contains 13,233 images. We ignored classes with fewer than 100 samples, and thus remained with 1,140 samples and five classes (Colin Powell, Donald Rumsfeld, George W. Bush, Gerhard Schroeder. and Tony Blair). We imported this dataset from the sklearn library.
13

---

Under review as a conference paper at ICLR 2021
French buildog - Pig
!pod
Window screen
Basketbal Strainer
Library Bookshop
Grand >iano> Oscilloscope
Traffic light>> Barometer
Rifle > Six-gun
Purse Caldron
Bagel >
Granny Smith
Ostrich > Bustard
Figure 6: PCA-guided adversarial examples for ImageNet Inception- V3 model.
Table 4: Our attack vs. GenAttack. is success rate, Q4QQ is the number of queries before/after postprocessing, and L8/L2 is the L2 distance from the original image before/after postprocessing.
Dataset
Model
Our attack
GenAuack
S
L2
L2
Q+
L2
X x10 3
x x10
x10
x x10%
MNIST
C&W
1
3.31
3.2
8.72
86.
13.8
71.4
F-MNIST
VGG13
0.82
2.6
2.55
18.9
0.95
11.3
158.8
LFW
RESNET20
0.40
0.9
1.82
8.8
11.2
236.4
GTSRB
RESNET20
0.30
3.1
1.24
22.8
200.8
CIFARIO
C&W
0.29
2.9
1.67
57.1
5.7
56.6
CIFARIO
RESNETS0
0.27
3,4
1.11
14.1
5.5
37.2
CIFARIO
VGG16
0.28
3.3
1.69
31.6
0.97
5.8
402.8
ImageNet
Inception- V3
0.11
0.16
42.3
0.66
3762.5
The German Traffic Sign Recognition Benchmark (GTSRB): 60,000 images of 43 differ- ent traffic signs (taken from http: http:/anncccaaaaeeee/ee ini rub. de/). We cropped the images using the coordinates that the dataset provided, and resized to x 32.
ImageNet: 299 x 299
images of 1,000 different objects. Our attack eval- uated on a small subset, taken from hattp://wwwweezsonnal. www.h. -tintu/ Down oado/ www.oloddddaannnni.eooe imaggnea.nnnn... cacpeeeetetttteeeeeeeeeeee npy/imagenets test data.rpy.
with images from 10 classes. We used a pretrained Inception- V3 model, taken from http:/
as uudaviciiiss www.aiis..du/ddaaseeeeeeeeee www v3 201 6 08 28 frozen. tar.
C COMPARISON TO GENATTACK
this section, we compare our attack to GenAttack (Alzantot et al. 2019) on 100 correctly-classifeed inputs. Since GenAttack has no postprocessing step, only report the number of queries Q and the L2 distortion. We limited the query number both approaches to 5,000 (for lower number of queries, GenAttack has lower success rate). Table shows the results. Results indicate that (1) attack obtains the initial adversarial examples with 18.7x fewer queries and with 1x less L2 distortion, and (2) final adversarial examples have 16.7x less 7.2 distortion but with 29x more queries.
14

---

Under review as a conference paper at ICLR 2021
Approach Random Baseline
Our Appreach Randem Baseline
Our Approach
Our Appreach
RESNET20 Random Baseline
Alestlet Random Baseline
MNIST
F-MNIST
CIFAR-10
3.0
Jeocces Ratre
0.0
0.9
0.0
5% Esucess
9.4
0.
0.0
[Buumbe Features)
100
200
0.0
25
((Nmmbe Features)
0.0
25
30
100
200
250
0.0
0.0
0.4
Kolumber of Features)
0.0
(Number Fentures)
25
Figure 7: Success rate of PCA-guided adversarial examples vs. random baseline as a function of
Table 5: Our L2 distortion in the PCA domain.
Dataset
Model
Le x10
MNIST C&W
3.35
F-MNIST
VGG13
0.83
LFW
RESNET20
0.28
GTSRB
RESNET20
0.23
CIFARIO
C&W
0.204
CIFARIO
RESNETSO
0.201
CIFAR10
VGG16
0.206
ImageNet
Inception V3
0.0026
D COMPARISON TO RANDOM BASELINE
In this section, we show the advantage of using the weakest PCA features in our attack over randomly- picked PCA features. In each experiment, fix dataset and model and shows the success rate (S) as a function of the number of weak features (k). The success rate is the fraction of inputs for which the PCA-guided perturbation (Section [5) resulted in an adversarial example. We compare our approach to random baseline which generates perturbations using k random PCA features. Results indicate that: (1) our approach succeeds in generating adversarial examples for all models (though smaller models are easier to fool); (2) using weak features has significantly better success rate than randomly selected features: on average 6x higher and up to 32x; (3) in most cases, the higher the k, the higher the success rate.
attack. Figure
E DISTORTION IN THE PCA DOMAIN
In this section, we report the T.2 distortion of our attack in the PCA domain. Table summarrize the results for all the benchmarks T
15


Reviews:
[{"review_id": "z5Y_khAH6en", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The overall quality of the paper is good. This paper proposed a feature perturbation procedure, as a comparison to the commonly used perturbation to the original input data. Given access to a feature mapping and a black-box classifier, the proposed procedure is able to select the most robust/weak features. This then can be used for two important tasks: to determine a robust neighborhood for a data point using the robust features and to design adversarial examples using the weak features. For the first task, the feature-based robust neighborhood proposed by this paper is shown by experiments to contain far more points than the traditional input-based neighborhood. For the second task, the feature-based adversarial examples require less query to the black-box classifier and have less distortion from the original data points compared with other competitive methods, and thus are more human-imperceptible. These characteristics make the procedure appealing.\nTherefore, the main contribution of the paper (i.e., the perturbation procedure) is important to the ML community and worth further explorations. \nThe clarity of the paper is good. There is no difficulty in understanding the content and experimental details are provided. \n\nCons:\n1. The overall running time of Alg 1 is a concern. \n2. When generating the adversarial examples, a greedy recovery is performed which may be time-consuming when the data dimension is high. \n3. The effectiveness of the proposed procedure seems to strongly depend on the feature mappings. The performance under mapping other than PCA is unknown. \n\nOther comments:\n1. The experiment showed good results with PCA feature mapping. Are there any other feature mappings that might work well with this proposed procedure (Alg 1)?", "extra_scores": {}, "extra_text": {}}, {"review_id": "UwP9cRuyw0q", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors study the problem of adversarial robustness, aiming to find regions of the input space for which a classifier is robust. Instead of the standard approach of defining a neighborhood around each data point based on some $\\ell_p$-norm, they use PCA to identify directions along which the model is robust or brittle. They then use these methods to identify large regions of input space for which models are robust and, in a complementary direction, to craft imperceptible adversarial examples with few model queries.\n\nIn general, understanding the set of perturbations that our models are robust to is an important research question. Unfortunately, the current paper does not go into significant depth. \n\n**Robustness neighborhoods.** Τhe input robustness regions computed using this approach are rather unintuitive. What insight is gained by reading Table 1? Do these robustness regions correspond to something concrete and meaningful (e.g., diagonal stripes, brightness) that we can convey to human users of the model? What fundamentally new understanding do we obtain via this analysis?\n\n**New adversarial attacks.**  The space of existing adversarial attacks is huge. By now, there exist so many different approaches for computing examples that fool models. From that perspective, it is not clear what the new attack proposed offers. Similarly to the point above, since these directions do not necessarily capture something human-understandable it is unclear how they reveal a fundamentally new model vulnerability.\n\nOverall, while the research direction is interesting, further exploration is needed to reach novel insights about these models.\n\nOther comments (not affecting score):\n- The large numbers representing \"number of images\" are somewhat misleading. How can we quantify whether these images are actually distinct. I do not think that these number convey significant information and I would thus recommend removing them.\n- https://arxiv.org/abs/1807.04200 and https://distill.pub/2019/advex-bugs-discussion/response-3/ also study model robustness to PCA-based perturbations and might thus be worth discussing.\n\n====== POST-RESPONSE UPDATE ======\n\nI appreciate the author's response and the additional illustrations provided. At the same time, my concerns remain:\n- I still disagree with the claim that PCA directions are \"semantic and meaningful.\" Yes, some of them might correspond to image changes that are intuitive, e.g., Figure 4, but it is still impossible to draw any such conclusions without manually inspecting individual directions. In other words, what do I learn about my model by reading Table 1?\n- I understand the process of counting the number of images. However, I still think that it is a fundamentally flawed metric. Based on this definition of \"distinct\", if I change the value of a single pixel by 1/255 I get a distinct image. This is clearly not an intuitive behavior. As a model designer, what do I understand about my model by look at these astronomical numbers.\n\nOverall, while I still find the broad direction interesting, I believe that the paper has fundamental issues and is hence unsuitable for publication.", "extra_scores": {}, "extra_text": {}}, {"review_id": "UcSpguEQmx", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The present paper proposes to consider features derived from PCA for the purposes of adversarial attack and defense. They argue that, based on these features, they can verify larger neighborhoods and provide stronger attacks. The neighborhoods are based on the ERAN verifier and the attacks are in comparison to a recent attack called AutoZoom. Defense performance is measured in number of images in the neighborhood, and attack performance in terms of L2 distance.\n\nI was, in general, confused by many of the choices in the paper. The paper proposes to use PCA features, but then measure attack in L2 distance; if the argument is that PCA is a better basis, then why use the pixel-space L2 metric? It seems this could only help to the extent that methods such as projected gradient descent (PGD) are failing to find the optimal L2 attack. Measuring defense capability in terms of number of images also seems like an odd choice, as usually we choose some perceptually meaningful norm and measure according to that. I had also not been familiar with the ERAN verifier prior to this paper, despite being an expert on neural network verification, and it isn't obvious to me whether we should consider it to be competitive with other SDP and LP-based verification methods. Moreover, the PCA features are only used to determine the side lengths of a hyperrectangle that is provided to the verifier, so that this is a fairly indirect test of whether PCA features are useful for defense (indeed, I would like to see a more crisp formulation of what \"useful for defense\" is meant to mean, since they aren't used to change the model itself).\n\nIn the experimental comparison of attacks, standard baselines such as PGD and C&W are missing, such that it is difficult to interpret the results. I checked the AutoZoom paper (the main method compared to) and it also does not compare to PGD, so I feel that the present paper does not provide evidence that the method performs better than baselines.\n\nI think the authors could improve the paper by more crisply articulating its goals, and either using more standard experimental setups and metrics or defending its deviation from these.\n\n== Update after author response ==\n\nThanks for your response. I believe it is widely agreed upon that black box evaluation is not meaningful in security settings, and that we should use white box attacks. Therefore, I don't find the justification for omitting PGD and CW convincing. I also still do not feel that counting images in pixel space is a meaningful metric. Therefore, I have kept my original score.", "extra_scores": {}, "extra_text": {}}, {"review_id": "7C7OVt7HjM", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This work proposes a method to find weak and robust features via sampling, and utilises the method to (a) define feature-guided neighborhoods and (b) to improve score-based black-box adversarial attacks.\n\nI examine the two main contributions (a) and (b) separately. The feature-guided neighourhoods are basically defined as 1D linear subspaces around a given sample x. The subspaces are usually defined along PCA-projections of the data set, although the definitions would also allow non-linear subspaces. The work claims that along some of these directions a classifier D is robust, and that using verification techniques one can show that these robust subspaces can be much larger than simple epsilon-ball neighbourhoods. While this claim might be true, the significance of this insight is unclear to me. Of course, if carefully chosen, one can find large neighbourhoods in which a classifier does not change its decision - but I fail to see what insights can be taken away.\n\nIn a second step, this work computes weak features, i.e. directions in the pixel space along which the classifier D is generally susceptible, and uses this to perform a score-based adversarial attack. The work claims higher robustness with fewer iterations than AutoZOOM and GenAttack. This is indeed an interesting direction, but the work misses a lot of relevant prior work on this area that should be discussed and compared against (in particular many other score-based but also decision-based attacks, one would need to take into account the number of queries needed to find the weak PCA directions to compare against other attacks, etc.).\n\nIt might be beneficial to remove the discussion of the neighbourhoods and to concentrate on the improvement of black-box attacks (which would have be shown much more convincingly).", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: I agree with the majority of reviews that this paper is not sufficiently convincing. 
Decision: Reject