Title: PROVABLE DEFENSES AGAINST SPATIALLY TRANSFORMED AD-VERSARIAL INPUTS: IMPOSSIBILITY AND POSSIBILITY RESULTS

Abstract: One intriguing property of neural networks is their inherent vulnerability to adversarial inputs, which are maliciously crafted samples to trigger target networks to misbehave. The state-of-the-art attacks generate adversarial inputs using either pixel perturbation or spatial transformation. Thus far, several provable defenses have been proposed against pixel perturbation-based attacks; yet, little is known about whether such solutions exist for spatial transformation-based attacks. This paper bridges this striking gap by conducting the first systematic study on provable defenses against spatially transformed adversarial inputs. Our findings convey mixed messages. On the impossibility side, we show that such defenses may not exist in practice: for any given networks, it is possible to find legitimate inputs and imperceptible transformations to generate adversarial inputs that force arbitrarily large errors. On the possibility side, we show that it is still feasible to construct adversarial training methods to significantly improve the resilience of networks against adversarial inputs over empirical datasets. We believe our findings provide insights for designing more effective defenses against spatially transformed adversarial inputs.

1. INTRODUCTION:

Despite their tremendous success in computer vision and pattern recognition (LeCun et al., 2015) , neural networks are inherently vulnerable to adversarial inputs -those maliciously crafted samples to trigger target networks to misbehave -which hinders their application in security-critical domains (Szegedy et al., 2014; Goodfellow et al., 2015; Sharif et al., 2016; Eykholt et al., 2017) . This serious vulnerability has spurred intensive research effort, leading to an arms race between developing more powerful attacks (Szegedy et al., 2014; Moosavi-Dezfooli et al., 2015; Papernot et al., 2016a; Carlini & Wagner, 2017; Meng & Chen, 2017; Xu et al., 2018) and designing more robust defenses (Papernot et al., 2016b; Madry et al., 2018; Tramèr et al., 2018; Kannan et al., 2018) . For example, defensive distillation (Papernot et al., 2016b) , originally considered as an effective defense, was later shown to be ineffective against stronger attacks (Carlini & Wagner, 2017) .

To end this constant arms race, several provable defense methods (Bastani et al., 2016; Raghunathan et al., 2018; Wong & Zico Kolter, 2018) have been proposed recently. Motivated by that most existing attacks generate adversarial inputs by directly modifying the pixel values of benign inputs, where the perturbation "imperceptibility" is often quantified by its L p norm, such provable defenses, by reducing the upper bound of the worst-case loss that can be caused by norm-bounded perturbation, provides the following guaranteed protection: for a given network and test input, no attack is able to force the error to exceed a certain threshold.

The effectiveness of these provable defenses hinges on modeling the upper bound of the worstcase loss under norm-bounded perturbation. While most existing attacks indeed use L p norm to quantify the perturbation imperceptibility, it has long been recognized that this is not an ideal metric (Johnson et al., 2016; Isola et al., 2016) . Recently, spatial transformation has been proposed as a new approach for generating adversarial inputs (Xiao et al., 2018; Engstrom et al., 2017b) : instead of directly modifying pixel values, it changes their spatial positions (e.g., via rotation and shifting), which is shown to better preserve the identity and structure of the original image (Zhou et al., 2016) . It is observed that spatial transformation-based adversarial inputs are often perceptually less distinguishable from pixel perturbation-based counterparts, as shown in Figure1. However, for spatial transformation, it is insensible to measure the perturbation imperceptibility using L p norm; rather, alternative metrics such as the total variation (Rudin et al., 1992) are used to quantify the magnitude of spatial deformation. In other words, spatially transformed adversarial inputs are inherently not norm-bounded, which thus raises an important and intriguing question:

Does there exist provable defenses that provide a given network with guaranteed protection against spatially transformed adversarial inputs?

In this paper, we present a systematic investigation to answer this question. Under the setting of a neural network with one hidden layer, we conduct both analytical and empirical studies on the existence of provable defenses. Our findings convey mixed messages. The impossibility results indicate that such defenses may not exist in practice. We show that for any given networks, it is possible to find benign inputs and imperceptible transformations to produce adversarial inputs that force arbitrarily large errors. Meanwhile, the possibility results imply that while the worst case can be arbitrarily bad, it is still possible to construct adversarial training methods to significantly improve the robustness of given networks over empirical datasets.

In summary, to our best knowledge, this work represents the first in-depth study on provable defenses against spatial transformation-based adversarial attacks. We provide both impossibility and possibility results regarding the existence of such defenses. We believe that our findings will highlight the fundamental difference of spatial transformation-and pixel perturbation-based attacks from the defender's perspective, and inspire designing more effective defenses against spatially transformed adversarial inputs.

2. BACKGROUND:



2.1. SPATIAL TRANSFORMATION:

We model a network as a function f . For simplicity, we focus on a binary classification task ('+' and '-') (the extension to the multi-class setting given in the appendix), in which the network predicts the class of a given input x as f (x) > 0 as '+' and f (x) < 0 as '-'. In adversarial attacks, the adversary crafts an adversarial input x by applying perturbation r to a benign input x: x = g(r; x), with the objective of forcing x to be misclassified. To maximize the attack evasiveness, the adversary also desires to preserve x's perceptual quality in x.

According to their perturbation types, existing adversarial attacks can be categorized as either pixel perturbation-based attacks or spatial transformation-based attacks. Figure 1 compares two versions of adversarial inputs with respect to the same benign input.

In spatial transformation attacks, instead of directly modifying x's pixel values, the adversary applies a spatial transformation (e.g., shifting and rotation) over x to generate x. Specifically, we use the per-pixel flow field (displacement) r to synthesize x using the pixels of x. Let xi be x's i-th pixel and (ũ i , ṽi ) be its position in x. We optimize the amount of displacement with a flow vector r i := (∆u i , ∆v i ), which goes from x to x. The position of xi 's corresponding pixel in x is derived as:

(u i , v i ) = (ũ i + ∆u i , ṽi + ∆v i ).

As (u i , v i ) may be fractional numbers and do not necessarily lie on the integer grid, we use the differentiable bilinear interpolation to compute xi 's pixel value:

xi = j∈N (i)

x j max (0, 1

EQUATION

where j iterates over N (i): the set of pixels adjacent to (u i , v i ) (top-left, top-right, bottom-left, and bottom-right) in x. Under this setting, diff can be instantiated with the total variation Rudin et al. (1992) , which compares the spatial movement distance for any two adjacent pixels:

diff (r) = i j∈N (i) (||∆u i -∆u j || 2 2 + ||∆v i -∆v j || 2 2 ) (2)

where i iterates over all the pixels.

We now derive its matrix form. Let r ∈ R d×2 : r = [r (u) , r (v) ] be the flow field, where r (u) and r (v) respectively represent the transformation along the horizontal and vertical directions. We assume r (u) = r (v) and will justify this assumption in § 3. With a little abuse of notations, let r = r (u) = r (v) . Let M (t) be the top neighbor matrix, with the i-th row being the top neighbor j of the i-th pixel (i.e., the one-hot encoding of j). Similarly, we define M (b) , M (l) , and M (r) respectively as the bottom, left, and right neighbor matrices. We have the proposition (proof in appendix): Proposition 1. The magnitude of spatial transformation can be specified as:

diff (r) = √ 2r M M r where M M = i∈{t,b,l,r} I -M (i) I -M (i) .

Therefore, the constraint on the spatial transformation magnitude can be given as:

diff (r) = M r ≤ (3) 2.2 ADVERSARIAL LOSS Let g(r;

x) be the adversarial attack that applies the transformation r to x to generate the adversarial input x, i.e., x = g(r; x) and x = g(0; x). Therefore, for a given benign input x, we define the margin between f (x) and f (x) as the adversarial loss. Formally,

adv (x, r) def = f (x) -f (x) 2 = f • g(r; x) -f (x) 2 Note that adv (x, r) is a function of r.

In the case of bilinear interpolation as defined in Eqn (1), g is differentiable with respect to r. Let g j be the j-th element of g and r i be r's i-th element. Note that in Eqn (1), xi only depends on r i . Thus, ∂gj ∂ri = 0 for i = j. Meanwhile,

∂g i ∂r i = j x j max (0, 1 -|ṽ i + r i -v j |) 0 |ũ i + r i -u j | ≥ 1 1 ũi + r i ≥ u j -1 ũi + r i < u j

where sub-gradients are used (Jaderberg et al., 2015) due to the discontinuities of interpolation.

The Jacobian Dg of g is a diagonal matrix with its i-th diagonal element given by ∂gi ∂ri . Further, the gradient of f with respect to g is given as: ∇f = ∂f ∂g1 , ∂f ∂g2 , . . . , ∂f ∂g d .

Putting everything together using the chain rule, we have the gradient of f • g with respect to r as:

∇(f • g)(r; x) = (Dg) ∇f

We now compute adv (r; x) using the integration along the line from x to x = f • g(r; x):

adv (x, r) = 1 0 (∇(f • g)(zr; x)) rdz (4)

3. IMPOSSIBILITY RESULTS:

Next we present the negative results for provable defenses against spatially transformed adversarial inputs. Intuitively, we show that given a classifier f and a threshold δ > 0, if the perturbation magnitude is allowed to be reasonably large, the adversary is able to find an input x * and its corresponding spatial transformation r * such that the adversarial input causes f to misclassify the adversary input g(r * ; x * ) with a large margin adv (x * , r * ) ≥ δ.

Specifically, we consider the maximum influence of spatial transformation on the adversarial loss via the following supremum:

sup x ∞≤1, M r ≤ adv (x, r)

We then find a particular input-transformation pair

(x * , r * ) such that f •g(r * ; x * )-f (x * ) represents a lower bound of this supremum. Apparently, if f • g(r * ; x * ) -f (x * ) ≥ 2δ

, the supremum of adv (x, r) must exceed δ. Next we present the concrete attack for a network with one hidden layer.

3.1. LOWER BOUND ATTACK:

For a network with one hidden layer, we have f (x) = v σ(W x) where W and v respectively represent the weights of the first and second layers of the network, and σ is the activation function (e.g., ReLU). In this case, we have ∇f = W diag(v)∇σ, where (∇σ

) i = ∂σ(yi)

∂yi with y i = (W g(r; x)) i . Substituting it into Eqn (4), we have:

EQUATION

We consider a linear approximation of adv (x, r):

˜ adv (x, r) = (∇σ(W x)) diag(v)W diag(x)r

The following theorem finds a lower bound of the supremum of ˜ adv (x, r) (proof in appendix).

Theorem 1. For a given network f , assuming W has rank d and

W d is a rank-d submatrix of W , sup x ∞≤1, M r ≤ ˜ adv (x, r) ≥ M -1 diag(x * )W diag(v)∇σ(W x * ) where x * = π ∞ (W -1 d 1)

(1 is an all-one vector). The lower bound is attained when

EQUATION

Theorem 1 gives the initial setting of (x * , r * ). We further increase the adversarial loss by improving both x * and r * . Let r (i) = (2i-1) 2n r. We compute the midpoint approximation of Eqn (5):

EQUATION

where we divide the interval [0, 1] into n intervals.

Updating x * To update x * , we consider x as a symbolic vector. Yet, it is difficult to optimize Eqn (7) with respect to x directly as ∇σ also depends on x. Instead, we update ∇σ and x alternatively.

Let x k be the current setting of x * . We update x * as follows. Let α i be the coefficient of x's i-th element in Eqn ( 7) with ∇σ computed based on x k . We set x k+1 = [sign(α 1 ), sign(α 2 ), . . . , sign(α d )] , which maximizes Eqn (7) under fixed r, fixed ∇σ and the constraint of x ∞ ≤ 1. We repeat this procedure until convergence.

Updating r * Meanwhile, for fixed x * , we may also increase the adversarial loss by refining r * using the integration approximation. Let r k be the current setting of r * . We update r * using the rule of:

EQUATION

Intuitively, we find r k+1 that aligns with the summation in Eqn (7) under M r k+1 ≤ .

Algorithm 1 sketches the attack against a given network. After initialization (line 1-3), it updates x * and r * alternatively until convergence (line 4-8). 

3.2. EMPIRICAL EVALUATION:

Next we empirically validate the above analytical result. We mainly use MNIST (LeCun et al., 1998) as the benchmark dataset and a network with one hidden layer (with 512 hidden neurons) as the target model f . We consider three variants of f : (i) f nt -f is normally trained, (ii) f rd -f is randomly initialized, and (iii) f at -f is adversarially trained (Madry et al., 2018) . We first measure the quality of lower bounds given by Algorithm 1. With respect to each of the networks, under different setting of , we measure the estimation by Algorithm 1 (with respect to adv ) and that by Theorem 1 (with respect to ˜ adv ). Figure 2 shows the results. It is clear that as varies from 0 to 7.84, the adversarial loss increases in an exponential manner, indicating that with reasonably transformation magnitude, it is possible to find (x * , r * ) that forces arbitrarily large error. Also note that Algorithm 1 provides much higher-quality estimation of adversarial loss compared with the initial estimation by Theorem 1. Figure 3 shows a set of samples of benign and adversarial inputs (and their associated flow fields).

Figure4 shows that Algorithm 1 typically converges fast under varied setting of network and , which validates our analysis of the performance of Algorithm 1.

4. POSSIBILITY RESULTS:

Despite the impossibility results for provable defenses against spatial transformation-based attacks, in this section, we show that it is still possible to construct adversarial training methods that significantly improve DNN resilience on empirical datasets.

4.1. ADVERSARIAL TRAINING:

To this end, we establish an upper bound on adv (x, r) and reduce this upper bound in training f to improve its robustness. Specifically, we consider the integration form of adv (x, r) in Eqn (4).

adv (x, r) = 1 0 (∇(f • g)(zr)) rdz ≤ max z∈[0,1], M r ≤ (∇(f • g)(zr; x)) r

In the following, we derive its upper bound form for a network with one hidden layer.

We have the following derivation regarding adv (x, r):

adv (x, r) ≤ max ∇σ,Dg,r (∇σ) diag(v)W Dgr (i) ≤ max ||s||∞≤1,Dg,r s diag(v)W Dgr (ii) ≤ 2 max ||s||∞≤1,||t||∞≤1 s diag(v)W diag(λ)t

In (i), we use the assumption that the non-linear activation function applied element-wise has bounded gradients ∇σ ∈ [0, 1], which holds in many settings (e.g., for ReLU, ∇σ ∈ [0, 1]; for sigmoid, ∇σ ∈ [0, 1/4]). In (ii), we use the following results. As M r = defines an ellipsoid E centered at 0, diag(z)r with z ∞ ≤ 1 corresponds to the union of the set of ellipsoids mirrored to E along the axises. We can thus bound diag(z)r using the axis aligned bounding box (AABB) of these ellipsoids. We have the following proposition (proof in appendix): Proposition 2. The AABB of the ellipsoid defined by M r = is given by

[-λ i , λ i ] (1 ≤ i ≤ d),

where λ 2 i is the i-th diagonal element of the matrix (M M ) -1 .

Because diag(v)W diag(λ) is not necessarily positive (negative) semidefinite, the above formulation is in general a non-convex optimization problem, which is similar to the NP-hard MAXCUT problem. We thus resort to the Semidefinite Programming (SDP) relaxation.

We first re-parameterize the variables as:

z def = s t P def = 0 diag(v)W diag(λ) diag(λ)W diag(v) 0

we obtain the formulation: adv (x, r) ≤ max

||z||∞≤1 z P z

Using the fact that z P z = tr(zz P ), we first have: max

||z||∞≤1 z P z = max Z=zz , z ∞ ≤1

tr(ZP )

By relaxing Z = zz and z ∞ ≤ 1 with Z 0 and diag(Z) ≤ 1 (Boyd & Vandenberghe, 2004) , we have the following convex SDP problem: max tr(ZP )

s.t. diag(Z) ≤ 1 Z 0

which is efficiently solvable using off-the-shelf SDP optimizers.

Next we empirically validate the above analytical results. Following the same setting as in § 3, we mainly use MNIST (LeCun et al., 1998) as the benchmark dataset and a two layer neural network as the target network model f . We consider four variants of f : (i) f nt -f is normally trained, (ii) f at f is adversarially trained (Madry et al., 2018) , (iii) f is trained with regularized bounds, and (iv) f stn -f is trained with spatial transformer network. For (iii), we consider three types of bounds: Frobenius -f fro , spectral -f spe , and SDP f sdp (our proposed method). The implementation details are presented in the appendix. Upper Bounds We evaluate the different upper bounds on adversarial loss. For each of the networks described above, we compute the 0/1 loss based on the Frobenius, spectral, and SDP bounds respectively, with results shown in Figure 5 . It is observed that all the bounds are fairly loose: the estimated adversarial loss goes to 1 as reaches 0.1. This again echos the impossibility results found in § 3. However, our proposed SDP bound is slightly tighter than alternative bounds under f sdp .

Model Robustness We also observe that f sdf is more robust than alternative models under varying perturbation budget. Specifically, we plot both the success rates of spatial transformation attacks and the test accuracy of different models under varying τ in Figure 6 . Here τ controls the allowed magnitude of spatial transformation, with τ = 0.05 used in (Xiao et al., 2018) . For f sdp , it is observed that there are the reduction of around 0.1 for attack success rates and the gain of around 0.08 for adversarial test accuracy, compared with other training objectives. 

5. RELATED WORK:

Adversarial Inputs Due to their increasing use in security-critical domains, machine learning models are becoming the targets of malicious attacks (Barreno et al., 2010; Biggio & Roli, 2018) . Compared with simple models (e.g., decision tree, support vector machine, and logistic regression), securing deep neural networks deployed in adversarial settings poses even more challenges due to their significantly higher model complexity (LeCun et al., 2015) . A variety of adversarial attacks have been proposed, including both white-box attacks (Szegedy et al., 2014; Goodfellow et al., 2015; Moosavi-Dezfooli et al., 2015; Papernot et al., 2016a; Kurakin et al., 2016; Carlini & Wagner, 2017; Meng & Chen, 2017; Xu et al., 2018) and black-box attacks (Papernot et al., 2016; Liu et al., 2016; Reddy Mopuri et al., 2017) .

Spatial Transformation While most state-of-the-art attacks directly modify the pixel values of benign images, recent work (Xiao et al., 2018; Engstrom et al., 2017b) has proposed to use spatial deformation as an alternative to generate adversarial inputs. Compared with pixel perturbation, spatial transformation tends to better preserve the perceptual quality of original images. Yet, besides their perceptual superiority, thus far little is known about the security properties of spatially transformed adversarial inputs.

Provable Defenses Another line of research has focused on improving model resilience against adversarial attacks by developing new training and inference strategies (Goodfellow et al., 2015; Huang et al., 2015; Papernot et al., 2016b; Ji et al., 2018; Madry et al., 2018; Tramèr et al., 2018; Kannan et al., 2018 ). Yet, the fundamental challenges of defending against adversarial attacks stem from their adaptive nature. Existing defenses, once deployed, can be easily circumvented by adaptive attacks. This arms race between attacks and defenses has motivated the development of provable defenses (Bastani et al., 2016; Raghunathan et al., 2018; Wong & Zico Kolter, 2018) , which ensure that for a given network, no attack is able to force the error to exceed a certain threshold. However, existing provable defenses all assume norm-bounded perturbation.

It is an open question whether such defenses exist for spatial transformation-based attacks.

6. CONCLUSION:

This work represents the first systematic study on provable defenses against spatial transformationbased adversarial attacks. Our findings include both possibility and impossibility results. We show that such provable defenses do not exist in practice. For any given networks, the adversary is able to find legitimate inputs and imperceptible transformations to generate adversarial inputs that force arbitrarily large errors. Yet, we also show that it is still possible to construct adversarial training methods to significantly improve the robustness of given networks against adversarial inputs over empirical datasets. We hope this work may inspire designing more effective defenses against spatial transformation-based attacks and adversarial attacks in general. 4) are achieved when r (u) = r (v) .

∆f (x, r) margin between f • g(r; x) and f (x) ∇f (•) gradient of f Dg(•) Jacobian matrix of g π 2 (•) L 2 projection π 2 (z) = z z π ∞ (•) L ∞ projection π ∞ (z) = z z ∞

Proof. (Proposition 3) Consider the first-order approximation of Eqn (4). Recall that r = [r (u) , r (v) ] and notice that ∇g(0) = [x, x] according to Eqn (2.2). We can rewrite the above expression as:

adv (x, r) = tr (diag(∇f (x)) [x, x]) r (u) , r (v) s.t. √ r (u) M 2 r (u) + r (v) M 2 r (v) ≤ x ∞ ≤ 1

Due to the symmetry of r (u) and r (v) , the extreme values of ∆f (x, r) is attained when r (u) = r (v) .

Proof. (Proposition 1):

We derive the following matrix form for Eqn (2):

EQUATION

where I denotes the identity matrix, and tr is the trace operator. We have the following proposition to simplify the notation (proof in Appendix).

We first prove that i∈{l,r,t,b} (I -

M (i) ) (I -M (i) ) is diagonally dominant. It suffices to show that each matrix (I -M (i) ) (I -M (i)

) is diagonally dominant. Without loss of generality, assume M (i) corresponds to the top neighbor matrix.

Let A = I -M (i) . Consider the i-th pixel. We differentiate three cases: (i) if i is on the top boundary, it must be the top neighbor of another pixel j; (ii) if i is on the bottom boundary, it must be the bottom neighbor of another pixel k; (iii) otherwise, i is the top neighbor of some j and the bottom neighbor of some k.

Consider the i-th column of A. We have: (i) A ii = 0, A ji = -1, and A ri = 0 for r = i, j; (ii)

A ii = 1, A ri = 0 for r = i; (iii) A ii = 1, A ji = -1, and A ri = 0 for r = i, j. Now we compute Z = A A. First consider the diagonal element Z ii : (i) Z ii = 1; (ii) Z ii = 1; and (iii) Z ii = 2. Then consider the off-diagonal element Z ij : (i) if i is j's top neighbor, then Z ij = -1, and Z ij = 0 otherwise; (ii) if i is j's bottom neighbor, Z ij = -1, and Z ij = 0 otherwise; (iii) if i is j's top neighbor or bottom neighbor, Z ij = -1, and Z ij = 0 otherwise.

In all the cases, Z ii ≥ 0 and

|Z ii | ≥ j =i |Z ij |, i.e.

, Z is diagonally dominant with real nonnegative diagonal elements. Thus, i∈{l,r,t,b} (I -M (i) ) (I -M (i) ) is positive semidefinite. Using the spectral decomposition, we can rewrite it as: i∈{l,r,t,b} (I -M (i) ) (I -M (i) ) = M M , where M is a square matrix of the same rank as i∈{l,r,t,b} (I -

M (i) ) (I -M (i) ).

PROOF OF THEOREM 2:

Proof. Recall that M r = defines an ellipsoid. It is straightforward to see that the supremum of ∆f (x, r) = v diag(x)r is attained only if r lies on the ellipsoid boundary. Otherwise, suppose r 0 = arg max r ∆f (x, r) and M r 0 < . Note that f (x, r) ≥ 0. We may extend r 0 to the ellipsoid boundary to further increase ∆f (x, r). Thus, we only need to consider the case of M r = . For convenience, we rewrite the ellipsoid in the following form: r = M -1 s with s = .

Thus, sup x,r ˜ adv (x, r) = sup x,s v diag(x)M -1 s, which represents the maximum projection of s on M -1 diag(x)v. Note that s lies on the ball of s = and that

M -1 diag(x)v = M -1 diag(v)x.

We have the formulation as follows:

EQUATION

which is attained by

s = π 2 (M -1 diag(v)x).

It is noted that without the constraint of x ∞ ≤ 1, the supremum above is attained by assigning x the primary eigenvector v * of diag(v)M -2 diag(v). We thus set x = π ∞ (v * ), which leads to:

sup x ∞≤1, M r ≤ ˜ adv (x, r) ≥ M -1 diag(v)π ∞ (v * )

PROOF OF THEOREM 1

Proof. Similar to the proof of Theorem 2, it is easy to see that the supremum of ∆f (x, r) is attained only if r lies on the ellipsoid boundary of M r = . For convenience, we redefine the ellipsoid as: r = M -1 s with s = .

According to the definition, we have:

sup x ∞≤1, M r ≤ ˜ adv (x, r) = sup s ≤ , x ∞≤1 (∇σ) diag(v)W diag(x)M -1 s

As s lies on the ball of s = , for fixed x, we have:

sup x ∞≤1, M r ≤ ˜ adv (x, r) = sup x ∞≤1 M -1 diag(x)W diag(v)∇σ

which is achieved by s = π 2 (M -1 diag(x)W diag(v)∇σ).

We then define the following auxiliary function:

φ(x) = 1 2 M -1 diag(x)W diag(v)∇σ 2

Recall that in the case that σ is ReLU, (∇σ) i = 1 if (W x) i > 0 or (∇σ) i = 0 otherwise. Observe that φ(x) has the absolute lower bound of 0, which can be achieved when x = 0, i.e., all the neurons in the first layer are inactive. We attempt to increase φ(x) by maximizing the number of active neurons.

For a practical neural network f , we may consider each column of W as a basis function. We thus assume W has full column rank, i.e., rank(W ) = d. Therefore, by properly setting x, we may make at least d dimensions of W x larger than 0. Let W d be the submatrix of W that consists of d independent rows of W . We consider x * = π ∞ (W -1 d 1) where 1 is an all-one vector. It is easy to verify that (i) W d x * > 0, i.e., ∇σ(W d x * ) = 1 and x 0 ∞ ≤ 1. That is, x * is a valid input and activates at least d neurons in the first layer of the network. We have the following lower bound:

sup x ∞ ≤1, M r ≤ ˜ adv (x, r) ≥ M -1 diag(x * )W diag(v)∇σ(W x * ) .

6.3. RESULTS FOR LINEAR CLASSIFIERS:



In the case of single-layer neural network (i.e., linear classifier), we have f (x) = v x, where v is the weights of the network. In this case, we have the following result:

EQUATION

To find x * and r * , we consider a linear approximation of adv (r; x):

˜ adv (x, r) = v Dg(0; x)r = v diag(x)r

where Dg(0; x) = diag(x) according to Eqn (1). Theorem 2 finds a lower bound of the supremum of ˜ adv (x, r) (proof in appendix).

Theorem 2. For a single-layer network f , we have

sup x ∞ ≤1, M r ≤ ˜ adv (x, r) ≥ M -1 diag(v)x *

where x * = π ∞ (v * ) and v * represents the primary eigenvector of diag(v)M -2 diag(v). The bound is attained when

EQUATION

)

While Theorem 2 finds high-quality setting of (x * , r * ), we may further increase the adversarial loss by approximating Eqn (11). Let r (i) = 2i-1 2n r. We compute the midpoint approximation of Eqn (11):

EQUATION

where we divide the interval [0, 1] into n subintervals.

Updating x *:

We first update x * to maximize Eqn (13) With fixed r. To this end, we consider x as a symbolic vector in Eqn (13). Let α i be the coefficient of x's i-th element in Eqn (13). We set x * = [sign(α 1 ), sign(α 2 ), . . . , sign(α d )] , which maximizes Eqn (13) under fixed r and the constraint of x ∞ ≤ 1.

Updating r * Let r k be the setting of r * at the k-th iteration. With x * fixed, we may update r * as follows:

EQUATION

Intuitively, to maximize Eqn (13), we find r k+1 that aligns with the direction of the summation (i) in Eqn (13) under M r k+1 ≤ . 

M r ≤ ǫ M -1 0 0 1 r ≤ ǫ r = ǫλ 1 ǫλ 2 r = -ǫλ 1 -ǫλ 2

Attack:

Algorithm 2 sketches the attack against a given single-layer network. After initialization (line 1-3), it updates x * and r * in an interleaving manner (line 4-7).

Algorithm 

In the case of single-layer network (i.e., linear classifier), we have:

EQUATION

where the last inequality follows from the fact that as defined in Eqn (1), under bilinear interpolation, the diagonal elements of Dg(zr; x) vary within the interval of [-2, 2] .

Let λ = [λ 1 , λ 2 , . . . , λ d ] .

We have the following derivation of Eqn (15) (note that we reparameterize r with t):

adv (x, r) ≤ 2 max t ∞ ≤1 v diag(λ)t (16) = 2 v diag(λ) 1

where the upper-bound is attained when t = sign(v diag(λ)).

Note that this upper bound is irrelevant to the original input x and solely dependent on the network's properties (i.e., v and λ). Thus, it only needs to be computed once for a given network.

6.6. EXTENSION TO MULTI-CLASS CASES (IMPOSSIBILITY):

We can extend Algorithm 2 and Algorithm 1 for a K-class classifier f (•). We considerthe CW attack and take κ = 0: adv (r) = max

EQUATION

For the most popular gradient-based adversarial attack methods, their update rules of r at t-th iteration are:

EQUATION

)

where α is learning rate. Let y such that arg max y =ỹ σ y (g(r; x)) = y , then according to the chain rule, we have ∂ max y = ỹ σy•g ∂r (r; x) = ∂σ y •g ∂r (r; x). Then we derive a simple work around: at each iteration, we only update based on the two classes case between class y (-) and ỹ(+).

6.7. EXTENSION TO MULTI-CLASS CASES (POSSIBILITY):

We extend the proposed SDP training objective to multiple classes case. Here we only consider a two-layer neural network, it is straightforward to apply the extension to a one-layer network. Similar to Eqn (9), we define:

P ij def = 0 diag(v i -v j )W diag(λ) diag(λ)W diag(v i -v j ) 0

for all pair of classes i(+), j(-). Then we have

ij adv (x, r) ≤ max diag(Z)≤1,Z 0 tr(ZP ij ) def = q ij (x)

For an image x with class y, the attack is failed if and only if max i =y iy adv (x) ≤ 0. Therefore, we take max i =y q iy (x) as the upper bound.

6.8. ADDITIONAL EXPERIMENTAL RESULTS:



IMPLEMENTATION DETAILS:

For the empirical evaluation (ii), we follow the experimental setup in Raghunathan et al. (2018) and evaluate the part with a two-layer network f with 500 hidden units. We construct a set of variants of f using different training methods. We report our training objectives and details below:

1. f nt -f is normally trained, with cross-entropy loss and without explicit regularization.

2. f fro -f is trained with Hinge loss Frobenius norm regularization (Fro-NN) and λ ( W F + v 2 ) with λ = 0.08.

3. f spe -f is trained with hinge loss and a regularizer λ ( W 2 + v 2 ) with λ = 0.09.

4. f stn -f is trained with hinge loss and a three layer spatial transformer network with 100 hidden units processes input images before feeding them to classification network. 6. f sdp -f is the upper bound we derived in Eqn ( 9), and we follow the implementation of SDP-NN in Raghunathan et al. (2018) . In particular, we also optimize the dual form of Eqn (9) so that we can backpropagate through both the classification loss and the SDP regularization term.

The other naive bounds used in the § 4: 

:



Figures and Tables:

Figure 1: (a) benign input, (b) pixel perturbation-based adversarial input, (c) spatial transformationbased adversarial input, and (d) flow vector of spatial transformation.

Figure 2: Lower bounds of adversarial loss by Algorithm 1 (w.r.t. adv ) and Theorem 1 (w.r.t. ˜ adv ).

Figure 5: 0/1 adversarial loss for different variants of f on MNIST based on Frobenius, spectral and SDP upper bound.Upper Bounds We evaluate the different upper bounds on adversarial loss. For each of the networks described above, we compute the 0/1 loss based on the Frobenius, spectral, and SDP bounds respectively, with results shown in Figure5. It is observed that all the bounds are fairly loose: the estimated adversarial loss goes to 1 as reaches 0.1. This again echos the impossibility results found in § 3. However, our proposed SDP bound is slightly tighter than alternative bounds under f sdp .

Figure 6: (a) Spatial transformation attack success rate versus τ under different training objectives. (b) Test accuracy of spatial transformed adversarial inputs for different training objectives and τ (τ = ∞ corresponds to benign cases).

Figure 7: Bounds of diag(s)r, where the dashed area corresponds to diag(s)r that satisfies ||M r|| ≤ and ||s|| ∞ ≤ 1.

. f at -f is trained with cross-entropy loss with an adversarial training regularization against spatial transformed adversarial examples. We take regularization coefficient λ r = 0.3 for training and λ = 0.05 for regularizing the diff . Due to Xiao et al. (2018) taking L-BFGS for solving the optimization problem, it is very slow to generate adversarial examples on the fly. Instead, we generate a pool of adversarial examples every k = 3 epochs, and sample adversarial example from pools during training.

Figure 8: Lower bounds estimated with respect to different networks.1. Spectral bound diff (x, r) ≤ W 2 v 2 2. Frobenius bound diff (x, r) ≤ W F v 2

Figure 9: Samples of benign and adversarial inputs found by Algorithm 1 under f rd .

T. Zhou, S. Tulsiani, W. Sun, J. Malik, and A. A. Efros. View Synthesis by Appearance Flow. ArXiv e-prints, 2016.

Table content: <table><tr><td>APPENDIX</td></tr><tr><td>6.1 NOTATIONS AND SYMBOLS</td></tr><tr><td>Symbol Description</td></tr><tr><td>x genuine input</td></tr><tr><td>x adversarial input</td></tr><tr><td>f (•) classifier</td></tr><tr><td>r flow vector</td></tr><tr><td>g(r; x) spatial transformation r on x</td></tr></table>

Symbols and notations.

Table content: <table/>

: spatial transformation // initialization v * ← primary eigenvector of diag(v)M -2 diag(v); x

Table content: <table/>

Peer review (iclr2019):
 This paper proposed a defense against spatially transformed adversarial inputs and give the two main results on possibility (still possible to construct adversarial training methods to improve robustness) and impossibility (always exist spatially-transformed adversarial examples for any given networks and thus no certified defense) The topic of studying certified defenses on adversarial examples is important, and I think the direction of dealing with spatially-transformed adversarial examples is interesting. However, this paper only analyze a simple one hidden layer neural network and the technique (e.g. sec 4, possibility result) does not seem to easily scale to deeper networks and networks with other types of layers (e.g pooling layers). Also, I also feel the clarity of the paper should be improved. Here are some questions: 1. Are there other metrics to measure spatial transformation? For the current setting as introduced in sec 2.1, it looks like there is no a uniform spatial transformation on the full image but rather different transformation applied on different local areas. Does it make more sense to say rotate the full image by some angle or shift it by some distance? 2. What is the pi_infty and pi_2 in Theorem 1? Why is it called Lower bound attack in sec 3.1? 3. What is the difference between f_fro, f_spe and f_sdp? 4. In Figure 6 (b), is the classification accuracy the nominal test accuracy of a classifier? If so, then the accuracy is too low (<90% for mnist) and thus considering the corresponding attack rates (Fig 6(a)) on these models are not meaningful. Please explain.