A Theory of Transfer-Based Black-Box Attacks: Explanation and Implications
Authors: Yanbo Chen
Weiwei Liu
Venue: NeurIPS 2023 poster (2023)
Keywords: Learning Theory

Abstract: Transfer-based attacks are a practical method of black-box adversarial attacks, in which the attacker aims to craft adversarial examples from a source (surrogate) model that is transferable to the target model. A wide range of empirical works has tried to explain the transferability of adversarial examples from different angles. However, these works only provide ad hoc explanations without quantitative analyses. The theory behind transfer-based attacks remains a mystery.
This paper studies transfer-based attacks under a unified theoretical framework. We propose an explanatory model, called the manifold attack model, that formalizes popular beliefs and explains the existing empirical results. Our model explains why adversarial examples are transferable even when the source model is inaccurate. Moreover, our model implies that the existence of transferable adversarial examples depends on the “curvature” of the data manifold, which quantitatively explains why the success rates of transfer-based attacks are hard to improve. We also discuss the expressive power and the possible extensions of our model in general applications.

A Theory of Transfer-Based Black-Box Attacks: Explanation and Implications
Yanbo Chen, Weiwei Liu"
School of Computer Science, Wuhan University National Engineering Research Center for Multimedia Software, Wuhan University Institute of Artificial Intelligence, Wuhan University Hubei Key Laboratory Multimedia and Network Communication Engineering, Wuhan University {yanbo. acad, 1iuweiwei863) (aagammmmlll..... com
Abstract
cunsfer-bbseed attacks [1] are practical method of black-box adversarial attacks in which the attacker aims to craft adversarial examples from a source model that is transferable to the target model. Many empirical works [2-6] have tried explain the transferability adversarial examples from different angles. However, these works only provide ad hoc explanations without quantitative analyses. The theory behind cransfer-based attacks remains a mystery.
This paper studies transfer-based attacks under a unified theoretical framework. We propose an explanatory model, called the manifold attack model, that formalizes popular beliefs and explains the existing empirical results. Our model explains why adversarial examples
transferable even when the source model is inaccurate observed in Papernot et al. [7]. Moreover, our model implies that the existence of transferable adversarial examples depends on the "curvature" of the data manifold, which further explains why the success rates of transfer- based attacks are hard to improve. We also discuss our model's expressive power and applicability.
Introduction
Machine learning (ML) models are vulnerable to adversarial examples [8, 9]. It has been observed that adversarial examples of one model can fool another model [9, 10], i.e., adversarial examples are transferable. Utilizing this transferability, researchers have developed some practical black-box attack methods, in which they first obtain source model and then use the adversarial examples of the source model to attack the target model [5, 11]. This type of attack is referred to in the literature transfer-based attacks (TBA).
TBAs have many intriguing properties. For instance, Papernot et [7] find that the adversarial examples of an inaccurate source model can transfer the target model with non-negligible success rate. Besides, the success rates of TBAs are constantly lower than other methods of black-box attacks [5, 6, 12]; the low success rate seems to be intrinsic property of TBAs.
Previous works have tried to explain these properties from different perspectives [2-6]. Unfortunately, these works only provide ad hoc explanations for the properties of TBAs without quantitative analyses under unified framework. For example, Dong et [6] suggest that the low success rates of TBAs are due to the adversarial examples of the source model falling into "non-adversarial region" of the target model, while the properties of such regions are not discussed quantitatively. As for cause of transferability, self-evident explanation is that the source and target models have similar decision boundaries [10]. However, these similarities are hard to characterize, and it even harder to associate
"Corresoondence to: Weiwei Liu <liuweiwei863 @ eegaal.ccmm com..
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

the decision boundary similarity with the properties of TBAs. More importantly, this explanation contradicts the abovementioned experimental results in Pupernot et al. [7]. i... adversarial examples are also transferable when the source and target model does not have similar decision boundaries. We refer the readers to Section for more related works. In summary, existing analyses make good sense under their respective settings, but it is unclear whether they are in accord with each other. It is natural to ask the following question:
Can we find a unified theoretical framework that explains the properties of TBAs?
This paper gives a positive answer to this question. More specifically, we propose an explanatory model, called the manifold attack model, that formalizes popular beliefs and explains the existing empirical results in a unified theoretical framework. Our model assumes that the natural data lies on dinndimenlional manifold [13-16] denoted by M: see Section 2 for more related works on this assumption. As the central part of our model, we specify a hypothesis class T and assume that both the source and the target model come from TM- The construction of T M is motivated by the following two widespread beliefs. In order to classify unseen data correctly, ML models are believed to have extracted semantic information (i.e., the ground truth) of the natural data after training. On the other hand, MI models are also able to learn non-robust features that generalize well in test phrases [17, 18]. These features reflect the geometrical information of the training data [17].
In our model, the hypothesis class M is designed to capture both semantic and geometric information of the data. As we will define in Section 4, the classifiers in FM can be decomposed into the product of a basis classifier fo and a multiplier d i..., f = fo & for Vf E FM. We characterize the semantic M (for k-class classification task) and capture this information by letting fo take different values on these sets. The geometrical information G is interpreted as the "approximated shape" of the data manifold, and we let ø concentrate around G. By multiplying fo and & together, we obtain a classifier that captures the semantic and geometry information of the training data. In brief, our model assumes that both the source and target models come from specified hypothesis class and the natural data is drawn from low-dimensional manifold.
information separated sets A A A
Despite its simple form, the manifold attack model provides us with powerful tools to theoretically an- alyze the properties of TBAs. More specifically, Theorem 4.8 proves that the off-manifold adversarial examples transferable when the source model is inaccurate, which explains the empirical results from Papernot et al. [7]. By further discussing the existence of off mffifolifold adversarial examples, we theoretically explain why the success rates of TBAs are hard to improve. Moreover, Theorem 4.13 quantitatively discusses the relationship between the existence of transferable adversarial examples and the "curvature" of the data manifold M, which formalizes the explanation in Dong al. [6].
In addition to the explanatory results, we further discuss the expressive power and the possible extensions of our model in general applications. Section 5.1 proves that our model is extensible, ie., we can replace the hypothesis class FM by the family of ReLU networks while proving similar results. Our model builds a bridge between the less developed theory behind TBAs and the huge amount of theoretical works analyzing ReLU networks. Furthermore, Section 5.2 demonstrate that the expressive power of our model is strong enough for the study of TBAs. We also provide a detailed discussion on the applicability of our model in Appendix A.
In summary, we propose model that is theoretically tractable and consistent with existing results. It formalizes widespread beliefs and explains the properties of TBAs under a unified framework. The remainder of this paper is structured as follows. Sections 2 and 3 introduce the related works and terminologies, respectively. We propose our model and present the explanatory results in Section 4. Section 5 makes further discussions on our model. Section 6 summarizes this paper. Some remarks and the omitted proofs can be found in the appendix.
Related Works
The related works of TBAs and the low-dimensional manifold assumption summarized as follows.
2.1 Transfer-Based Attacks
The research on the adversarial robustness of MI. can be roughly divided into adversarial attacks [8, 9, 19], defenses [20-22], and the analyses of the robustness of existing methods [23-26], Adversarial

---

attacks can be divided into two classes based on whether the attackers have the gradient information of the target model, i.e. white-box [27] and black-box [7] attacks. TBAs are one of the two main approaches to performing black-box attacks on MI models. Apart from TBAs, the other main approach the optimization-baseee attack that approximates the gradient of the target model and performs white-box attacks thereafter [28-30J. While TBAs require much less information from the target model (and thus more practical) than optimize-based attacks, the success rates of TBAS are constantly lower, even when the source models are almost accurate [2, 3, 5, 6, 11].
There are a few theoretical works that have tried to explain the properties of TBAs. However, these works rely heavily on either simple models or strong assumptions. Apart from those mentioned in Section 1, the seminal work of Goodfellow al. [9] tries to explain the transferability of adversarial examples using linear models. Charles et al. [31] theoretically prove, in the context of linear classifiers and two-layer ReLU networks, that transferable adversarial examples exist. However, [31] does not explain those properties of TBAs mentioned in Section 1. Gilmer et al. [32] assume that the natural data drawn from a "concentric spheres dataset", which can be viewed as a special form of the low- dimensional data manifold. In comparison to previous works, our model requires milder assumptions on both data distribution and hypothesis class, while providing a more detailed discussion of the properties of TBAs.
2.2
The Low- now-Dimensional Manifold Assumption
The low-dimensional manifold assumption is commonly seen in many areas of research, ranging from classic approximation theory [13, 14] to computer vision [15, 16]. Under this assumption, it is intuitive to divide the adversarial examples into two groups based on whether they lie on or off the data manifold. Both on- na-manifolld [15, 33] and off-manifold [32, 34] adversarial examples have been studied in many previous works. In most cases, a classifier is simultancously vulnerable to both on- and off- off-mmanioold adversarial examples [33].
In this paper, we discuss the transferability of both on- and off-manifold adversarial examples. We are mainly motivated by the techniques from Zhang et al. [35] and Li et al. [14]. The main results of Zhang et al. [35] decompose the adversarial risk based on the position of the adversarial example and discuss the existence of different types of adversarial examples; Zhang et al. [35] provides us with useful tools to analyze the existence of transferable adversarial examples. Li et al. [14] consider robust generalization and approximate continuous classifiers by ReLU networks. In this paper, prove that the hypothesis class FM in our model can also be approximated by ReLU networks.
3 Problem Setup
This section introduces the basic setups and terminologies. We use black triangle sign (A) to indicate the end of assumptions, definitions, or remarks.
3.1 Notations
Let Rd be the real vector space equipped with the lo-norm, where p E [1, too]. this paper, we consider the k-class classification problems (k 2) on Rd. Denote the data-label pairs by (x. y), in which is chosen from some label space y. By convention, we let y 1-1, 1} in binary classification and y (1, 2, ..... .I] when & Unless otherwise specified, we assume that the natural data lie on a low-dimensional manifold M c Rd. More specifically, we adopt the following assumption.
Assumption (Low-dimensional Manifold). Let M c [0. 11d be compact smooth manifold and assume that the dimension of M is less than d. Let 1) be some given continuous distribution that is supported M. We say that random variable natural data if D.
Denote the support set of D by supp(D). With slight abuse of notation, let also be mapping from supp(D) to y that assigns each natural data x ~ D with a true label y y(x). Notice that only natural data is endowed with true label. Since supp(D) c [O, 1) will make no distinction between R and [0, 1]dd in the remainder of this paper without loss of generality (WLOG).
"ooe realistic datasets supported on [0, 1f e.g., MNIST and Fashion- MNIST.
3

---

Let dp be the metric induced by the nn-nmmm and B(x;)) r) the 1p-ball around x with radius r. For any subset S C RR let dx S) == inf dx(X, x') be the distance between S and x. Let the classifiers f be functions defined on R When k > 2. we consider f(x) = ((),))))))))) ... (x)) that maps x E Rd to f(x)= E R For ease of notation, let y(f. x) == arg max (x) be the output class of f for Vx R.. Since D continuous, y(f.x) x) take unique value w.p. (with probability) I when x D. In binary classification problems, we consider f R _ R. and y x) = sign(f(x))
Given perturbation radius ō and natural data D, we call X, B(x; 5) an adversarial example of at x if yff.x x) * y(f, xa)- Given classifier f. let the standard risk of f be Raa(f) == PX-D ((f.x) # yx))], and the adversarial risk of with regard to (W.r.t)) 6 is defined as
Radv (f: 8) PX-D [x, E B(x; s.t. y(fxx) # x(fxx,)).
(I)
Since TBA is often against accurate target models in practice, our paper assumes that the standard risk of the target model f, is (a) O for the sake of simplicity. Given such accurate fi the goal of a TBA is to find adversarial examples of ft- Specifically, the attacker needs to obtain a source model fi and craft adversarial examples of f, using white-box attacks. Given natural data x D and an adversarial example X2 E 6) of fa at x, we say that X, transfers to fi if y(f, x) # y(f.
3.2 The On- and Off-Manifold Adversarial Examples
In this paper, the on- and off-manifold adversarial examples are defined as follows.
Definition 3.1 (On- and off manifold adversarial examples), For any given classifier f. perturbation radius 6 and natural data x ~ D, let x, E Bxx; d) be an adversarial example of f at x. We call xa an on-manifold adversarial example X2 E M. or an off-manifoll adversarial example if x, é M.
We say that a classifier f suffers from, or is vulnerable to (on-, off off-manifold) adversarial examples if Ix D B(x; 6) such that x, is an (on-, off-manifold) adversarial examples of f If f does not suffer from (on-, off-manifold) adversarial examples, then we consider it to be robust against (on-, off off-manifold) adversarial examples.
In most cases, the adversarial examples of f, are regarded as imperceptible to humans (c.g., in a cat- or-dog classification task, the adversarial examples of cat images still look like cats), which implies that adversarial examples are not naturally generated data. Otherwise, the adversarial examples would be endowed with the same label as their corresponding natural data, which leads to contradiction since (f) = O. In other words, adversarial examples should not lie in the support of D. To ensure this, we additionally assume that the natural data with different true labels other. Notice that there is an intrinsic connection between the natural data x and its true label y()), which is often referred to as "semantic information" of the natural data. In this paper, we formalize the semantic information of the natural data as family of sets (A j V), where
separated from each
: |x E supp(D) y(x) fl. Vj y.
In practice, the semantic information A' and A is often separated if i j (e.g., Remark A.1). In this paper, we assume that the semantic information is separated in the following sense.
Assumption (Separated Semantic Information). Given > for Vi # j V, we assume that A and A are 2A-separated. Here, for any given subsets E. F c Rd and > 0, we say that E and F are r-separated if dx,(), x2) 2/ r for Vx1 E and X₂ F.
With the help of Assumption 2, it is easy to check that the adversarial examples would not lie in the support set of D if A. In the rest of this paper, we will treat 8 and a as fixed parameters and always assume that 8 < A.
4 The Manifold Attack Model
Our proposed model specifies hypothesis class that has two components. The first one is a semantic classifier that tries to capture the semantic information of the natural data. Similar to Equation (2), we call (A/ j V) the semantic information learned by classifier if y(fx)= = for Vx E A/ and Vje E y. To avoid trivial discussion, we assume that A? # 0 for Vj y. The following definition specifies a family of classifiers that learn separated semantic information.

---

Definition 4.1 (Semantic classifier). We call fo semantic classifier if there is a family of pairwise 2d-separated set (A', y such that (A e e V) is the semantic information learned by fa-
It is easy to check that (h) = 0 A/ A/ for Vj y. Intuitively, the accuracy of a classifier depends how well it learns the semantic information of the natural data.
The second component of our model a function that captures the geometric structure of the data. Definition 4.2 (Concentration multiplier). Given G c Rd, we call concentration multiplier around G ((x) =
for Vx E G, and ((xi) < ((x;) for Vx,, X2 E Rd with d,(X), G) > dp(X2, G).
Intuitively, the geometric information G can be interpreted as the "approximated shape" of the natural data. The concentration multipliers would assign a much lower confidence score to those data points that are outside of far away from G. In the ideal case, G precisely captures the shape of M, which enables & to detect the off fff-fonifold data points (i.e., the out-of-disstrbutie (OOD) data [36, 37J.
As mentioned in Section 1, ML models often capture both the semantic and geometrical information of the natural data. Therefore, we assume that the source and target models can be decomposed into the product of a semantic classifier and concentration multiplier. More specifically, we consider the hypothesis class defined as follows.
Definition 4.3. Consider the k-class classification problems (k 2) on [O, 11d. Let Fy, and & be collection of semantic classifiers and concentration multipliers, respectively. When k > 2, let FM be the family of all classifiers f [0, 1]dd E that satisfy
(x) = 1 (x) (xxx for Vx [O, 1I and jj E y
In the binary classification case, we let f(x) = fb(x) o(x) for Yx E [0, 1J Here, fa and & are chosen from F. and O respectively. Since the semantic information is contented in the manifold, we additionally assume that UjEvA/ G, in which (A jE E V) is the semantic information learned by fo and is the approximated shape of M learned by db
Definitions 4.1 to 4.3 together with Assumptions and 2 establish the abstract framework for the manifold attack model. This model formalizes how a classifier captures the semantic and geometric information from natural data. It is worth noticing that choices of f E TM in Definition 4.3 remains largely arbitrary if we choose To (and () to be the family of all possible semantic classifiers (and concentration multiplier) introduced in Definition 4.1 (and Definition 4.2). In fact, for any f that learns 21- sepaartd semantic information (A/- j V and any & such that (f(x) 0) (δ(x) 0)
for Vx Rd, can simply let (x) (x) (x) o= (x) for vx # 0. It is easy to check that fo is semantic classifier as long as A n G # for Vj V.
The generality in Definition 4.3 comes at the expense of theoretical intractability. Take the semantic classifier for example. In Definition 4.1, fo cannot be determined by the semantic information it learns. Moreover, fo cannot even be parameterized according to this definition. There is an implicit tradeoff between generality and theoretical tractability: quantitative analysis of specific scenarios might need more delicate definitions. Next, we introduce one specific combination of fo and & to carry analyzing the properties of TBAs.
For the sake of simplicity, we only present analyses and results in the context of binary classification in Sections 4 and 5. For ease of notation, let A = [x y(x) 1) and B = Ix y(x) =1), i.e., the semantic information of binary natural data. The following proposition specifies a sub-family of semantic classifiers:
Proposition 4.4 (semantic classifier, binary case). Given 2d-separated sets A,, By c M. Define:
fx(x) = M(X:A, By) == dx B,) Ax(
d, B,) A,(x,Ay)
Then, So is semantic classifier. In particular, we can obtain from Equation (4) that fo(x) > if is closer (w.rt. dg) to A than By and fa(x) < O otherwise.
Let Fosn the collection of all semantic classifiers defined by Equation (4) for all possible 2d-separated Ay. B, M. The following proposition shows that semantic classifier can be accurate and robust.
5

---

M
M
A visualization of the manifold, semantic information, and adversarial examples. The manifold Mss is represented by the grid surface. For clarity, we only visualize the above half M and omit the below half. Left: the 21-separated semantic information A, B C. M is painted in dark blue. According to Equation (6), the adversarial examples f, = fg. Out lie the shaded bodies in light blue, which is outside of the data manifold. Right: the semantic information A, B of the natural data represented as the light blue area on M. The raised parts upon M are y) (painted in orange) and N2(B,) (painted in dark blue). The intersections of M and Na(Ay) (or N₂(By)) is Ay (or By). which are indicated by the areas surrounded by the inner contour lines. On the outer contour line of y and By, have onn- since dz(x, 5 By)) 8.
Figure 1:
Proposition 4.5. Take A = and By = B in Equation (4) and denote the corresponding classifier by fr. Then, for any given à 5 O, we have Raa(fr) Ruav ff, O.
Similar to Proposition 4.4, we specify a distance-based family concentration multipliers.
Proposition 4.6 (Concentration multiplier, binary case). For any given r > and G Rd, denote
(x) = ((x,,, == r dx,, G) 7 xxdx(x.G) G)¹ VXER
(5)
Then ((x) is concentration multiplier around G.
Propositions 4.4 and 4.6 introduce combination of fi and & in binary case. Both fo and ø can be parameterized by the semantic and geometrical information it learns. It also possible to extend our analysis other scenarios by specifying other combinations of and o which is out of the scope of our paper. In the following sections, we adopt the following assumption.
Assumption 3. The source and target model chosen from the hypothesis class given by Defini- tion 4.3, where Fú and & are the function classes introduced by Propositions 4.4 and 4.6.
With slight abuse of notation, we denote the hypothesis class in Assumption 3 by FM Intuitively, for any f= fo E Fxx the semantic classifier controls the accuracy of f. The similarity between A, B and A,, By reflects how well fa fits the natural data. Moreover, the overlapping area (A (AUB))(A,UB) should contain the training data of (and thus be non-empty) if f has reached zero training error. The concentration multiplier helps classification by assigning lower confidence scores on those x g G, but it might also bring in adversarial examples. Since we only impose mild conditions on the choice of G (i.e., Ay U By C G), FM can capture complicated geometrical information. We will come back to the expressive power of Ff at Section 5.2.
4.1 The Transferability of Adversarial Examples
As warm-up, we study the robustness of f FM against on- and off-manifoll adversarial examples without specifying fo and o. The following proposition shows that the vulnerability of e TM to on- and off- ofnifooofold adversarial examples are different.
Proposition 4.7. Let
6. Given Raseff:) O, can obtain (w.p. 1) that
1. f suffers from off manifold adversarial examples.
2. if fo captures the semantic information of the natural data (ie,, Ay and By), then is robust against on- on-manifold adversarial examples.

---

Remark. The results in Proposition 4.7 hold w.p. I since our proof ignores some minor events (e.g.. f(x) = 0) that occur w.p. O. For the sake of simplicity, we will not specify those events that happen almost surely in the rest of this paper.
The first result of Proposition 4.7 implies that f FM suffers from adversarial examples if and only if f suffers from off-manifold adversarial examples. In Section 4.2, we will discuss the existence of transferable adversarial examples based on this result.
We explain the properties of TBAs by proving the existence of f TM M that satisfies desired properties. First of all, we introduce a sub-family of TM M that is robust against on on-manifold adversarial examples. The following concentration multipliers force fo to concentrate around the data manifold, which brings off off-manifold adversarial examples to fo without introducing on-manifold adversarial examples. For any unspecified E (0, 1), let
aó cō-d,(k co-dp(x,M) ad + dd(xx
oon (x) == (xx; ad, M)
(6)
Consider the classifiers induced by Ooft f -o is clear from Equation (6) that f(x) = fx() when x M. Combining this with the separated assumptions of semantic information, we can see that doff blocks the on-manifold adversarial examples. Figure I demonstrates that the target model fi = f &ot is only vulnerable to off- perturbations. The following proposition shows that off iff-manifold adversarial examples are transferable even if the source model is inaccurate, which explains the phenomenon in Papernot et al. [7].
Theorem 4.8. Consider TBAs with perturbation radius ò E (), target model f, Sr -ooi and source model fa fb Oof, fo E Fb. Denote the semantic information of fo. by A and By. Then, for Vx E A U B, all adversarial examples (if exist) of f. at are transferable x , U By.
Theorem 4.8 proves that all of the adversarial examples of f, are transferable if the concentration multipliers of fi and f, are identical, given that (A U B) (A, U B,) * 0. In particular, f. is not neces- sarily accurate, which is consistent with the empirical results in Papernot et al. [7]. Theorem 4.8 also implies that the vulnerability of MI. models might be due to the non-robust geometrical information. Such vulnerability is transferable between models that learn similar geometrical information.
Next, we turn to the on- on-manifold adversarial examples. Proposition 4.7 shows that we cannot find an f E FM such that f suffers from only on-manifold adversarial examples. Instead, we specify family of concentration multipliers that blocks out off- manifold adversarial examples that is "directly above" the manifold. In this case, we consider Euclidean space Rd with 1z-norm and inner product (X1, x2) = x X2. For Vx E M, let T&Me c Rd be the tangent space of M at x, i.e., the space spanned by the possible tangent directions that pass through x. Now that we are considering an inner product space, let N,M C Rd be the normal space at x such that Yu E N&M and v E T.M, we have (u, v) 0.
M&M) for any given We call N,(S) a tubular neighborhood of S if for Vx' E N,(S), there is an unique x E S such that x' E MyM. For any semantic classifier fo with semantic information Ay and By, define
Denote N,(S) (x' E Rd: E s.I. d2(x, x') <,, X
O Dnd S M.
(x)
Don (x: ft) == 4(x; 6,
and consider f -on (: According to Equation (7), &an blocks the off-manifoll adversarial examples of ff 'that is "directly above" A and By. We use Figure to visualize our idea. The following proposition provides sufficient condition for adversarial examples that are not transferable.
Proposition 4.9. Consider TBA with perturbation radius ö (0, 2}, target model f. = fh (oa(s and source model fs fo &aal: fo). fo E Frr Denote
S == (A ( Swa := (A (BB
(8)
Then, for Vx E AAUR B. we have
U.S. 1. if B(x, MC Sen US wry, then fi and fs are both robust against adversarial examples;
2. if B(x, n MCAUE B and x E Ag U By, then the adversarial examples of fa at x (if exists) cannot transfer to fr-
We interpret S en (or S wrg) as the "correct (or wrong) semantic information" captured by fo. When S Sen supp(D) and S wig = 0 (i.c., fo captures the semantic information of the natural data), the
7

---

first result of Proposition 4.9 implies that large part of x supp(D) is robust against adversarial examples if we block the off-manifold adversarial examples that are "directly above" the semantic information. The second result of Proposition 4.9 implies that the potentially transferable adversarial examples are mostly located inside of the following set
(A U B) n wrw wry U. = (AAUB) UB)
or at least close to its boundary. Here, we interpret (AU B) n (A, B,) the semantic information not contained in the training data.
In summary, the results in this section together provide a general view of the role that on- and off- manifold adversarial examples play in TBAs. Although both on- and off-manifold adversarial exist, ML models seem to be more vulnerable to off-manifold adversarial examples, and the off-manifold adversarial examples seem to play a more important role in TBAs.
4.2 The Existence of Transferable Adversarial Examples
Dong et al. [2] argue that the low success rates of TBAs are possibly due to the adversarial examples of f, falling into a "non-adversarial region" of ft. In this section, we try to formalize this explanation and study the properties of such non-adversarial regions.
According Proposition 4.7. E FM suffers from adversarial examples if and only if f suffers from off-manifold adversarial examples. This section is devoted to discussing the possible non-existence of off-manifold examples. Before we delve into this problem, let introduce the notion of robust radius that is initially studied in the certified robustness problems [38, 39].
Definition 4.10 (Robust Radius, binary case). For any classifier f. the robust radius of f is defined as the minimum 2 O such that for Vx E A U B and X1 B(x, r), we have fxx) 2 O.
Denote the robust radius of f by ra(f). In our model, the robust radius of f E FM is controlled by 6. Based this notion, the following example demonstrates how the existence of off-manifold adversarial examples depends on the shape of the data manifold M.
Example 4.11. We use the same setting as Proposition 4.9 and consider the target model f. = -our- Given 0 < r1 < 12 < 8 < r3, denote Φi = ( r. M) and & $ar(: r2, M). Using Equation (6), we obtain that ro(ff &1)= ri < 5 and ra(fī (22 = r2 6. However, ra(f) < 6 does not imply that all x E A U B are vulnerable to adversarial examples.
We demonstrated our idea in Figure A. Denote the dark blue surface in Figure A.I by M2 == [x dx M) = r2). Observe that r2 is of the same magnitude as the "curvature" of M. we can find a Xo E A U B such that dz(x, M,,) 13 6, i.c., Xo is not vulnerable to adversarial examples. Note that all of such Xy together form the non-adversarial region in Dong et al. [2].
Example 4.1 shows that the existence of the adversarial examples of fo Hoef depends on the "curvature" of M, which seems to be a rather agnostic result. However, we can quantify the "curvature" of M by the following lemma.
Lemma 4.12 (Bredon [40]). Let M McT. Bd be compact smooth manifold, then there is a A > 0 such that M&M is tubular neighborhood of M.
Lemma 4.12 can be viewed as a variant of the tubular neighborhood theorem (cf. Bredon [40]). The constant is decided by M and can be used evaluate the "curvature" of M in Example 4. 1I. More specifically, the following proposition provides a sufficient condition for the existence of the off-manifold adversarial examples.
Theorem 4.13, Given perturbation radius 5 (0, A] and target model f, f Donkir. M). Let & be the constant specified in Lemma 4.1 Then, for Vx E A B, the off-manifold adversarial example of fi at exists if A.
Theorem 4. establishes quantitative relationship between the existence off-manifold examples and the "curvature" of the manifold.
8

---

5 Discussion
5.1 Approximation with ReLU Networks
In applications, the target and source models of TBAs are mosdy neural networks, c.g., ReLU networks. In this subsection, we use ReLU networks (ef. Definition 5.1) to approximate the classifiers f e FM Moreover, we recover some of the results in Section 4 based on the approximated classifier.
We start by introducing the family of ReLU networks. Denote the rectified linear unit (ReLU) by p(x) == max(x, 0), where 0 the zero vector in R and max(:.-) takes the entry-wise maximum of x and O. The family of deep ReLU networks defined as follows.
Definition 5.1 (Deep ReLU networks). For any bias vector b (b).-.. ,b.) and sequence of weight matrices W = (W,...' W.), we call function f E - a (deep) ReLU networks parametrized by and W
=r, + Wiplbr-i + Wi-ip(-..pp(i + Wix) for Vx e R.. Let W, be a matrix with m, rows and ny columns. We have n1 d, my and m, M/41 (I s Aisis-- 1-LL-1) 1).
(10)
The non-constant entries in b and W are called the parameters of J. We say that function is induced by ReLU networks if it can be expressed by the linear combination of finite many ReL.U networks.
It has been proven [14, 41-43] that ReLU networks can approximate (w.rt. the sup-norm) continuous functions with a bounded domain any precision. Here, we denote the sup-norm of function f c Rd - R by Il := supses lf(x). Specifically, we have:
function f [0, 11 - [-1,1] and precision 6 > O, Lemma 5.2 (Li et al. [14]). Given -uunecchtteuunnctinn
there is ReLU network f with O(1/e)))) Old + log(1/e)) parameters that satisfies Ilf flls> S
Lemma 5.2 provides a useful tool to approximate the Lipschitz functions from [0, 1J to [-1, 1]. It straightforward to check the Lipschitzness of f E FMM. As result, given > 0 and fET we can find an ReLU network f such that ||ʃ f'l.- < e. Unfortunately, can no longer be decomposed into the product of fo and Φb which invalidates most of the results in Section 4. We have to make a detour to approximate f FM. As a first step, we approximate fo and & by fo and ø, respectively.
Corollary 5.3. Let fo be a semantic classifier with semantic information A, and B, that satisfy 2d- 21-separated property. Given >>0 0, there is a ReLU network fo with O(11/26)) Old + log(//c)) parameters such that Ilfb follo S c.
Corollary 5.4. Given E > 0, r>> > O and S c [0, 113, there is a ReLU network T with ((1Ire))) Old d log(1/e)) parameters that can approximate d(;;,,) to precision e.
Corollaries 5.3 and 5.4 approximate fo and with ReLU networks. remains to approximate the product of two ReLU networks using the following lemma.
Lemma 5.5 (Yarotsky [41]). There is a function : [-1, 1J² - [-1,1] induced by ReLU network
with (E parameters such that x(x,y) = 0 if xy = 0, and
sup xyy[0,1]
[x(x,)) xyl S.
(11)
The above lemma constructs ReLU network that efficiently approximates the multiplying operator in ? The following proposition shows that we can approximate f E T with ReLU networks to any precision.
Proposition 5.6. Given 2, 8, > for any f F.M there is a ReLU network f with
1 1 _ O(d + +dlog(-)) + +Oogg )
Ommax de re
(12)
parameters that satisfies Ilf fll S
The following theorem partially recovers the results in Theorem 4.8 with ReLU networks.
Theorem 5.7. Consider TBAs with perturbation radius ó (0. 2/2), target model f. = fr don and source model f. fo 6ca. fo E T, Denote the semantic information of fo by Ay and B,. Given S 0.1, let f, and f, be ReLU networks that satisfy
Ilfi fillo &. - -fallo S.
(13)

---

Then, for Vx E (AUB) (Aj U BB), the adversarial examples Xa (if exist) of f, satisfies
f(x) f(x.)) & 2c(1 + e)² + 26
(14)
Notice that Equation (14) does not imply that the adversarial examples transferable. Instead, it can only reduce the confidence the decision made by fi- The results in Theorem 4.8 cannot be fully recovered. When f is close to zero, whether the approximated ReLU network f is greater less than zero is hard to decide.
The following theorem recovers Proposition 4.9 after modifying some parameters.
Theorem 5.8. Consider TBAs with perturbation radius ö (0, a/2], target model fi f Dot and source model f, = fo Pott fo E Fo. Denote the semantic information of fo by As and By. Given s 0.1, let Si and Is be ReLU networks that satisfy Equation (13). Then, for Vx A B, we have
1. if B(x.0)
U. wry, then fi and fs are both robust against adversarial examples;
2. if B(x,8) (Ox,8)MMAA McAUP B and x E As U By, then the adversarial examples of fu at x (if exists) cannot transfer to fi-
By approximating the classifiers in F we build bridge between the less-deve theory behind TBAs and the huge amount of theoretical works analyzing ReLU networks.
5.2 The Expressiveness of the Manifold Attack Model
In learning theory, the expressive power a hypothesis class F evaluates the performance of f e F in fitting natural data; [44] for comprehensive overview. Previous works have tried to explain the transferability based on less expressive hypothesis classes, e.g., linear classifiers [32] and the linear combination of "features" [17]. In this subsection, study the expressive power of our model.
The main goal of TBAs is not to the natural data. Instead, for any well-trained classifier f" [0. 1Jdd + 1-1, 1), i.e., (*) = O, the goal of our model is to find f E FM such that the adversarial examples of f fits those of r. More specifically, we have
Proposition 5.9. For any classifier f" with Rua(f*)= O and perturbation radius ō E (r,(f"), there is f F M such that 1) Raals) = Rs and for vx E AUBD B, if %, is an adversarial example of f at then exists x, E B(x.. (/4) such that x, is an adversarial example of f.
The above proposition implies that our proposed model can cover a wide range of classifiers and is thus sufficient for the study of TBAs on manifolds.
Conclusion
This paper explains the properties of TBAs under a unified theoretical framework. We suggest that off-manifold adversarial examples play a major role TBAs. In particular, we show that off-manifold adversarial examples are transferable when the source model is inaccurate. We also prove that the non-existence of off-manifold adversarial examples is one of the reasons why the success rates of TBAs hard to improve.
Acknowledgments and Disclosure of Funding
This work is supported by the National Natural Science Foundation of China under Grant 61976161, and the Fundamental Research Funds for the Central Universities under Grant 2042022rc0016.
References
[1] Nicolas Paperoot, Patrick D. McDaniel, and Ian J. Goodfellow. Transferability in machine learn- ing: from phenomena black-box attacks using adversarial samples. CoRR, abss/1605.07277 2016.
[2] Yinpeng Dong, Tianyu Pang, Hang Su, and Jun Zhu. Evading defenses to transferable adversarial examples by translation inniariiinnnnaaiiantt attacks. In CVPR, 2019.
10

---

[3] Cihang Xie, Zhishuai Zhang, Yuyin Zhou, Song Bai, Jianyu Wang, Zhou Ren, and Alan L. Yuille. Improving transferability of adversarial examples with ipput diversity. CVPR, 2019.
[4] Yinpeng Dong, Fangzhou Liao, Tiayu Pang, Hang Su, Jun Zhu, Xiaolin Hu, and Jianguo Li. Boosting adversarial attacks with momentum. In CVPR, 2018.
[5] Shuman Fang, Jie Li, Xianming Lin, and Rongrong Ji. Learning to learn transferable attack. In AAAI, 2022.
[6] Yinpeng Dong, Shuyu Cheng, Tianyu Pang, Hang Su, and Jun Zhu, Query-efficient black-box adversarial attacks guided by a transfer-based prior. IEEE Trans. Pattern Anal. Mach. Intell., 2022.
[7] Nicolas Papernot, Patrick D. McDanicl, Ian Goodfellow, Somesh Jha, Z. Berkay Celik, and Ananthram Swami. Practical black-box attacks against machine learning. In AsiaCCS, 2017.
[8] Christian Szegedy, Wojeiech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian J. Goodfellow, and Rob Fergus. Intriguing properties of neural networks. In ICLR, 2014.
[9] Ian J. Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adver- sarial examples. In ICLR, 2015.
[10] Florian Tramèr, Nicolas Papernt, Ian J. Goodfellow, Dan Boneh, and Patrick D. McDaniel. The space of transferable adversarial examples. CoRR, abs/1704.03453, 2017.
[11] Zhipeng Wei, Jingjing Chen, Micah Goldblum, Zuxuan Wu, Tom Goldstein, and Yu-Gang Jiang. Towards transferable adversarial attacks vision transformers. In AAAI, 2022.
[12] Zhichao Huang and Tong Zhang. Black-box adversarial attack with transferable model-based embedding. In ICLR, 2020.
[13] Minshuo Chen, Haoming Jiang, Wenjing Liao, and Tuo Zhao. Efficient approximation of deep relu networks for functions on low dimensional manifolds. In NeurlPS, pages 1172-8182. 2019.
[14] Binghui Li, Jikai Jin, Han Zhong, John E. Hoperoft, and Liwei Wang. Why robust generalization in deep learning is difficult: Perspective of expressive power CoRR, abs/2205. 2022.
[15] Wei-An Lin, Chun Pong Lau, Alexander Levine, Rama Chellappa, and Soheil Feizi. Dual manifold adversarial robustness: Defense against Ip and non-lp adversarial attacks. In NeurIPS, 2020.
[16] Cassidy Laidlaw, Sahil Singla, and Soheil Feizi. Perceptual adversarial robustness: Defense against unseen threat models. In ICLR, 2021.
[17] Andrew Ilyas, Shibani Santurkar, Dimitris Tsipras, Logan Engstrom, Brandon Tran, and Aleksander Madry, Adversarial examples are not bugs. they are features. In NeurlPS, 2019.
[18] Zeyuan Allen-Zhu and Yuanzhi Li. Feature purification: How adversarial training performs robust deep learning. In FOCS, 2021.
[19] Anirban Chakraborty, Manaar Alam, Vishal Dey, Anupam Chattopadhyay, and Debdeep Mukhopadhyay. Adversarial attacks and defences: A survey. CoRR, abs/ 18 810.00069, 2018.
[20] Boqi Li and Weiwei Liu. WAT: improve the worst-class robustness in adversarial training. In AAAI, 2023.
[21] Xiyuan Li, Xin Zou, and Weiwei Liu. Defending against adversarial attacks via neural dynamic system. In NeurlPS, 2022.
[22] Zekai Wang, Tianyu Pang, Chao Du, Min Lin, Weiwei Liu, and Shuicheng Yan. Better diffusion models further improve adversarial training. In ICML, 2023.
[23] Xinsong Ma, Zekai Wang, and Weiwei Liu. On the tradeoff between robustness and fairness. In NeurIPS, 2022.

---

[24] Zhengyu Zhou and Weiwei Liu. Sample complexity for distributionally robust learning under chi-square divergence. Journal of Machine Learning Research, 2023.
[25] Jingyuan Xu and Weiwei Liu. On robust multiclass learnability. In NeurIPS, 2022.
[26] Xin Zou and Weiwei Liu. Generalization bounds for adversarial contrastive learning. Journal ofMachine Learning Research, 2023.
[27] Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. In ICLR, 2018
[28] Pin- Yu Chen, Huan Zhang, Yash Sharma, Jinfeng Yi, and Cho-Jui Hsieh. ZOO: zeroth order optimization based black-box attacks to deep neural networks without training substitute models. In AlSec, pages 15 15-26, 2017.
[29] Andrew Ilyas, Logan Engstrom, Anish Athalye, and Jessy Lin. Black-box adversarial attacks with limited queries and information. In ICML, 2018
[30] Shuyu Cheng, Yinpeng Dong, Tianyu Pang, Hang Su, and Jun Zhu. Improving black-box adversarial attacks with transfer-based prior. In NeurlPS, 2019.
[31] Zachary Charles, Harrison Rosenberg, and Dimitris S. Papailiopoulos. A geometric perspective on the transferability of adversarial directions. In AISTATS, 2019.
[32] Justin Gilmer, Luke Metz. Fartash Faghri, Samuel S. Schoenholz, Maithra Raghu, Martin Wattenberg. and lan J. Goodfellow. Adversarial spheres. In ICLR, 2018
[33] David Stutz, Matthias Hein, and Bernt Schiele. Disentangling adversarial robustness and generalization. In CVPR, 2019.
[34] Xingjun Ma, Bo Li, Yisen Wang, Sarah M. Erfani, Sudanthi N. R. Wijewickrema, Grant Schoenebeck, Dawn Song. Michael E. Houle, and James Bailey. Characterizing adversarial subspaces using local intrinsic dimensionality. In ICLR, 2018.
[35] Wenjia Zhang, Yikai Zhang, Xiaoling Hu, Mayank Goswami, Chao Chen, and Dimitris N. Metaxas. A manifold view of adversarial risk. In AISTATS, 2022.
[36] Sachin Vernekar, Ashish Gaurav, Vahdat Abdelzad, Taylor Denouden, Rick Salay, and Krzysztof Czarnecki. -istti-disti detection in classifiers via generation. CORR, 190.4491,,,,,1, 2019.
[37] Dara Bahri, Heinrich Jiang, Yi Tay, and Donald Metzler. Label smoothed embedding hypothesis for out-of-distribution detection. CoRR, abs/2102.051311 2021.
[38] Linyi Li, Xiangyu Qi, Tao Xie, and Bo Li. Sok: Certified robustness for deep neural networks. CoRR, 1431,, 2020.
[39] Zekai Wang and Weiwei Liu. Robustness verification for contrastive learning. In ICML, 2022.
[40] Glen E. Bredon. Topology and Geometry. Springer, 1993.
[41] Dmitry Yarotsky. Error bounds for approximations with deep relu networks. Neural Networks, 2017."
[42] Zuowei Shen, Haizhao Yang, and Shijun Zhang. Deep network approximation characterized by number of neurons. CoRR, abs//996.054997 2019.
[43] Zuowei Shen, Haizhao Yang, and Shijun Zhang. Optimal approximation rate of relu networks terms of width and depth. CoRR, abs/2103.00502. 2021.
[44] Shai Shalev-Shwartz and Shai Ben-David. Understanding Machine Learning From Theory to Algorithms. Cambridge University Press, 2014.
[45] Yuan Yang. Cyrus Rashtchian, Hongyang Zhang, Ruslan Salakhutdinov, and Kamalika Chaudhuri. A closer look at accuracy vs. robustness. In NewrIPS, 2020.
12

---

A Further Discussions
The following remark provides an example of the semantic information dataset.
Remark A. (The semantic information of CIFAR-10). Generally speaking, "semantic" refers to the relationship between natural data and their true label, which should be consistent with human recognition. For example, the semantic information contained in the CIFAR-10 10 dataset is the true labels (e.g,, airplane, automobile, and bird) and their corresponding natural images (e.g., images of airliners, SUVs, and chickens), In this example, an image cannot simultancously include an airplane and an automobile since "the classes are completely mutually exclusive" in the CIFAR- --10 dataset (cf. the official website of CIFAR-10.)
It is also easy to check that the semantic information provided by CIFAR-10 is separated.
A.1 Visualization of the Non-Adversarial Region
We provide a visualization of Example 4.11 II in Figure A.I.
r2
rit
M
Y3
A
XO
Figure A.1: A visualization of Example 4.11. The data manifold M represented by the grid surface. Let the surface in light blue (or dark blue) be the contour surface that Φ1 0 (or Φ2 = 0). The distance between Xo and the dark blue surface is rs. which is greater than and r2. In this visualized example, Xy is robust against aff-foonfold adversarial examples.
A.2 The Applicability of the Manifold Attack Model
Recall that Assumption 3 asserts that the classifiers f E F can be decomposed into the product of semantic classifier fo and concentration multiplier In this section, empirically certify the following weaker version of Assumption 3.
Assumption (Manifold attack model, weaker version). Let f be the source or target model of TBA. Let Mi be compact smooth manifold that is not necessarily subset of M. Let Ns, Mi be tubular neighborhood of Mi for some Ai > O. We assume that for Vx Mi and for any non-zero 0.
NyMi, have f(x riu) f(x r24) holds for Vo,
By letting G = Mi in Definition 4.2, the classifier in Assumption 3 would also satisfy Assumption 4. In this sense, we claim that Assumption is weaker version of Assumption 3. Next, we validate Assumption 4 on low-dimensional lincarly separated data defined as follows. Given d x 0.
13

---

consider the x-dimensional manifold (in this case, a flat plane)
= ((11, .X,, .0) R, Vi= .x) cR.
(A.15)
Assume that the natural data is drawn from some continuous distribution D(x), say mixture of Gaussian distribution. For the sake of simplicity, let the natural data be linearly separable in the following sense. Given A > 0 and natural data (x1, ... Xa),, assume that [x1] > and the label of x decided by y(x) = 1 x1 > A, and y(x) = -1 xi -A.
In order to test Assumption 4, our goal is to train classifier that satisfies this assumption. The training setting is stated as follows. Given
O, let the training set N = (x1, X2, .xy] ~ be independent and identically distributed (i.idd)) random variables. For V1 s S N, denote the label of Xn by yv. Since D is continuous, we assume WLOG that
Dx)) (x)
(3 E R s. X; ax,) i=
(A.16)
holds for V1 s i & N. The hypothesis class is defined as F == (fn :we W R. where
X
fw (w,
(A.17)
|x||2
for Vx R. Consider the logistic loss function I(u) log(1 exp(-u)), Vu R, and the gradient
descent (GD) iteration
w(1 + 1) = w(1) - (wW(Lx(W(()
(A.18)
We can show (both empirically and theoretically) that:
The GD iteration converges to an accurate classifier
* *3M, such that f satisfies Assumption 4,
which implies that we can actually train an accurate classifier (instead of constructing one using oracle information) that satisfies assumption. The following section briefly introduces the setting and results of the experiment. The theoretical analysis is omitted.
A.2.1 Numerical Experiments
order to visualize our results, the manifold M set to be a 2-dimensional plane embedded R The distribution D is mixture of two Gaussian distributions with means (2, 2, 0) and (-2, -2, 0), and covariance or 0.5. The optimizer stochastic gradient descent (SGD), We train two-layer network, denoted by f. that reaches 100% testing accuracy. We check whether f satisfies Assumption 4. The experimental results are demonstrated in Figure A.2.
Hardware Specification and Environment Our experiments are conducted on an Ubuntu 64-bit Linux workstation, having 10-core Intel Xeon Silver CPU (2.20 GHz) and 4 Nvidia GeForce RTX 2080 Ti GPUs with 1GB graphics memory.
B
Complete Proofs
Proposition 4.4 (semantic classifier, binary case). Given 2d-separated sets Ay. By C. M. Define:
dx(x, By) (x(x,Ay) fa(x = fo(x,A,, By) d, B,) Ax(
(B.19)
Then, fo is semantic classifier: In particular, we can obtain from Equation (4) that fo(x) > if is closer (w.rt. dy) to Ay than By and fi(x) < otherwise.
Proof of Proposition 4.4. It is easy to check that fo(x) = when x E Ay and fo(x) = -1 when x E By. By definition, know that fo is semantic classifier.
Proposition 4.5. Take A₂ = and By = in Equation (4) and denote the corresponding classifier by fr. Then, for any given A 5 > 0, we have Rea(f))) Radv ff, ))= O.
14

---

z=0
z=3
26
03
z=5
z=7
10
08
06
02
0.
3
2
Figure A.2: The experimental results be interpreted as follows. Denote the vectors E R² by x = (x, y. 2). The bottom plane is the manifold, i.e., the (x, y)plane. For each sub-figure, we consider the score of f at (x, for a specific chosen from 30,3,5,7 7). The height of the surface is the score of f. Obviously, the score of f decreases as goes larger, which is in accord with the claim in Assumption 4.
Proof of Proposition 4.5. By Equation (4), we have
f()) Bx, VxeR
(B.20)
Clearly, we have fx) = 1 when x E A and fx) = - when x E B. Then, the standard risk of fü w.r.t. D(x) is
Raa(f)))= = FD (x)y < 0 E A| +P (5) <0| B| =0
(B.21)
Recall that A and B are 21-separated (cf. Assumption 2). For Vx A and x' E B(x, 6), we have (x,x, B) > 8, which implies that dx'x', B) Ax 0, and thus (x)) = (x') > For Vx E B, a similar deduction shows that (x)) 0 holds for vx' B(x, Together, we have
Rudi (/r, :PP 3x E B(x;0) s.t. <
(B.22)
+ P 3x' E B(x s.. f (x (f) < B =0,
which completes the proof.
Remark B.I. The construction of Equation (B.20) can be found in previous works [14, 45). In particular, Li et al. [14] uses the ReLU-approximation of f to study the robust generalization of deep neural networks.
Proposition 4.6 (Concentration multiplier, binary case). For any given r > and G c Rd, denote
dxd, G)
((x) ()x;,, + dx(xx VxeRd.
(B.23)
Then ((x) is concentration multiplier around G.
Proof of Proposition 4.6. For Yx E G, we have dp(x, G) 0. That is, ((x) for Yx E G. For Vx,, X2 s.t. dx(X), G) dx(x2, G), it is easy to check that Φ(x)) < d(x)).
15

---

Proposition 4.7. Let f fo. Given (a)(ff:) # O, we can obtain (w.p. 1) that
1. f suffers from off off-manifold adversarial examples.
2. if fu captures the semantic information of the natural data (i.e., A A, and B c Byh then is robust against on-manifold adversarial examples.
Proof of Proposition 4.7. We first prove the first result. By definition, there are 0 and G C R such that
f(x d,(x, By) dp)x.Ay)
dy(x, G)
(B.24)
dx(x, By) Ax) + d,(x, G)
Given Radv (f;v(f;)) # O, there is natural data x E supp(D) and Xn E B(x, 8) such that fxx)f(x)) < 0. If xо E Mr, there nothing to prove.
Otherwise, we have Na E M. Denote
To == (io, dp(xo. By)), - G)I. d,(x, xo)li.
(B.25)
Consider the non-empty set
B(x,)) B(XU.TU) M.
For Vx2 E B(xo, ro), there is
dp(x, dp(x, xo) dx( xx)) ()){00) <
(B.26)
is also easy to check that
(dp(xu. BB) d A))) (dp(X By) - dx(x) O. (r (r- dxx0, G)) (r- dp G))) 0.
(B.27)
which implies that f(x) < 0 and xy is an off-manifold adversarial example. As for the second result, since A c C,,, B C By, and A, U By C G, we have
r du, G)
1, where (x,x') r+ du G)
(B.28)
for Vx A and x' B(x, d) n M. We can easily obtain that fo(x) = f6(x', which implies that has no on- on-manifold adversarial examples.
Theorem 4.8. Consider TBAs with perturbation radius E (0, target model f; fr Pott and source model f. = fo aan. fo T Denote the semantic information of fo by A, and By. Then, for Vx U B, all adversarial examples (if exist) of fa at x are transferable if A U By.
Proof of Theorem 4.8. If fr is robust against adversarial examples, then there is nothing prove. Otherwise, consider x E Ay DA WLOG. By Equation (6), denote
fx(x) fx(x) (x) dp(x, B,) B dp(x.Ay)
ad- dx(x
(B.29)
dx(x, B,) Ay) aδ dx(xx M)
We can find adversarial example of f. x. Denote this adversarial example by X,, and we have fx(x,) < O. It is not hard to verify that (X., By) (x, A,) > O since ó < A, which implies that fi((x,) > 0. It is easy obtain that fx(x,) O and (xf((x)) O. We thus have aō (X, M), which implies that X, is off the manifold and the distance between X, and M is greater than aő. In particular, have
do (x,) < O,
(B.30)
which is independent of the choice of fo. Now consider f.(x) and f((x),, where
f(x) (x) (x) dx(x, B) (x, ad - dx(x, d,(xx, B) d (x, ad +
(B.31)
No matter A or E B, we have for Vx' B(x, o), there fx(x) f" (by the 21-separated property of and B). By Equation (B.30), we have f(x)ff((x)) fr (x) (x) 0. i.c., X, transfers to f, which completes the proof.
(B.32)
16

---

Proposition 4.9, Consider TBA with perturbation radius ô (0, A1, target model fr = Sb o,al: and source model fs fb cn fo). fo TT Denote
S on == (A
By). Swg. := := (B))))
(B.33)
Then, for Vx E A B, we have
1. if B(x, 8) Mc U. wry then fi and fs are both robust against adversarial examples:
2. if ( B and x Ay Bj, then the adversarial examples of Js (if exists) cannot transfer to fr.
Proof of Proposition 4.9. For the first results, it is easy check that (x) and (X,) 1 for Vx, E B(x, ö), which implies that f is robust against adversarial examples. It remains to prove the second result. By Equation (7), denote
dx B,) d2) aó dx Ns U dz(x, By) + A2) ad d2 No(A U B
fxx) = fo(x) (xn fb)
(B.34)
For Vx E A U B such that B(x, 8) n M c A U B and x E A U By, denote the unspecific adversarial example (if exist) of fs at by x. Assume that E A By WLOG. By definition, have
g f(x) fx(x= fxx) O.
(B.35)
By the 21-separated assumption of ,, and By, we have
fb(2,) O.
(B.36)
From (x())f((X))) < O, we can obtain that onn fo) (Nai fo) Since x E By, we have
d2(x, Ns(A, U By))
(B.37)
i... (x; fb) = 1. Combine this with oon (x: fo mm (x,: fb) O, we have (X,: fi) < <0, i.e.
az < d2 No(Ay U By)) d2 x) 5.
(B.38)
remains to show that fi(x,) > 0. By Equation (7), denote
dx(x, dz(x. aó d2(x, B))
f(x) = f7 o fā)
(B.39)
dz(x, B) + (x( aó + d2(x, U B))
By x A and the 21-separated assumption of and we have have E Na(A U B)), i.e., (x, fg) > O. Together, we have f((x)) f (X,) (xn(X fy) > 0. That is, X, is not an adversarial example f. which completes the proof.
fx,))) have,f
0. By B(x, 8) n M A, we
Theorem 4.13. Given perturbation radius d 2) and target model f. = f/ dontsr M). Let A be the constant specified in Lemma 4.12. Then, for Vx E A B, the off off-manifold adversarial example of at exists if < A.
Proof of Theorem 4.13. For Vx E AUB, let u E N&(M) be the normal direction at x with ||ul|2 1. Since r A, we can find no r such that ro A and < Ó. Denote
X,
Tou.
(B.40)
Clearly, we have x, B(x, 8). Since Na(M) is tubular neighborhood of M, have
dz(x,, M) ro >>> r.
(B.41)
which implies that x, is an off-manifold adversarial example of fi Notice that Equation (B.41) not necessarily holds when ro A.
Corollary 5.3. Let fo a semantic classifier with semantic information A, and By that satisfy 2d-separated property. Given e there is ReLU network with ((1/)e))) Oud + d dlo((1/e)) parameters such that Ilf flloo S
17

---

Proof of Corollary 5.3. According to Lemma 5.2, our goal is to upper bound the Lipschitz constant / of fr- By definition, it suffices upper bound the supremum of
[ By) Ay By)
dp(x1.X2) X2)
(B.42)
Ap(X2,Aj) (x) dp(x1, dp(x2, Ay) + dx(x2, By)
(x)))
dp(Xi.X2) X2)
We only need to consider three cases:
1. both of x1 X2 E A, B,,
2. both of X1, E (A, U By)", and
3. either or X2 is in A U B
When X1, X2 E Ay U By, trivial verification shows that S J. We now turn to the second case. By symmetry, let
Ax( > 0. Ax) d,(x,, d,(x2, A,) + dx(x2, By)
d, A,)
(B.43)
By simplifying Equation (B.42), we can obtain that A BB) - fu(x;Ay,.Bp)
dx(x1,X2) X2)
Ax(
dp(x2,Ap
Xx)
AT) d,(x,, By)
Ap(x2.Ay) + d By)
Af) Ay)
dx(x2, BB)
(B.44)
21
dx((1, X2)
dn Af) dp By)
dx(X), By) dp(x2, By)
Af))
dp(x1, X2)
dp(X2, Ay) + dx(X2. By)
(1 -1-1+11
21
which implies that 5 1 in this case. Finally, we consider the third case. We assume WLOG that E Ay and X2 E (A, U By) Substitute into Equation (B.42), we have
Ap(
dp(x2.A))
X2) X2)
dx( dp(x1, Bf) dp(x2, A5) + dx(x2, By)
(B.45)
Ap(
dx))))x2)
Ay) (x By) 21
To up above, we have sup 1. which implies that is L-Lipschitz continuous, is required.
Corollary 5.3. Given E > 0, >>>> 0 and c [0, 1I there is a ReLU network with (((Ire))) Old dog((1/e) parameters that approximate r,;r,S) precision
Proof of Corvllary 5.3. We prove this corollary similar manner as Corollary 5.3, i.e., we upper bound the supremum of
(0(x;;r,5) ((x2rr,S) Xx)
dp(x), (x(x),S)
Xx) x2)
r+ (x,,)) S)
(B.46)
d,(x), X2)
r+ (x(,(x,,5)
r S)
We also consider three cases in this proof:
1. both of X1 E or
18

---

2. both of X1, E S and
3. either X or X2 is in S.
In case 1, we once that O. When both of X1 Se, we assume WLOG that d)(Xi.5) > dp(x2. By Equation (B.46), we have
S) (r+ dr, dp(x,. $ xx(
(B.47)
Analysis similar to Equation (B.47) shows that
( dx(x2,
$
!
(B.48)
xx(x),x2)
To up above, have s s to which implies that is L-Lisschitz continuous, is required. Proposition 5.6. Given e, e, 0, for any f e FM, there is ReLU network f with
O(max 2 _ 11) Odd + =dlo(())) +) +Olggg --))
(B.49)
de
parameters that satisfies IIf ~o S.
Proof of Proposition 5.6. This proposition can be derived directly from Lemma 5.5, Corollary 5.3, and Corollary 5.4.
Theorem 5.7. Consider TBAs with perturbation radius ö (0, a/2), target model fi = fī Don and source model fa fo dott fo E Fr. Denote the semantic information of fo by Ay and By. Given E s 0.1,, let and Is be ReLU networks that satisfy
Il fills= S &,llfs fallos SE
(B.50)
Then, for Vx (AU U By), the adversarial examples xa (if exist) of F, satisfies
f(() f((x)) s 2c(1 + +)² +
(B.51)
Proof of Theorem 5.7. Consider x A WLOG. If f, is robust against adversarial examples x E B(x, 8) n M C Ay, then there is nothing to prove. If not, denote the adversarial example of f. at by X₁. Since x A, M, there is
f,(x) f(() (x)(() - E (1 - e)² - ->>
(B.52)
and we thus have f(())) < <.. By X, B(x; o) and the assumption 6 < 414 we have
2d.(Xa. A,)
26
fo(x,) = dx(2a, By) (p(Na.
(B.53)
21 2
To obtain 8(fo, &on (xx) < O, there must be fo(x,) Danl (Xa) < E, which implies that
ton(X,) 2E.
(B.54)
Now consider (x( and f(xx).. By definition, we have (x) (x) 6, E). (1- and thus
(1-
6,
<].
f(() = 2 S (1 e)2 +
(B.55)
Similar to Equation (B.53), there is
(x,
(x.) = dx(x,, B) + d, (Xa. A) $
(B.56)
Combining Equations (B.54) to (B.56) together, we have
f(x) f(xx) s 2e(1 e)² + 26
(B.57)
as is required.
19

---

Theorem 5.8. Consider TBAs with perturbation radius d E (0, 2/21, target model fi = f Don and source model f. = fo Dot. fo T. Denote the semantic information of fo by A and By. Given E 0.1,, les ft and fs be ReLU networks that satisfy Equation (13). Then, for Vx A B, we have
1. if B(x,0) MC U.S. wry. then f. and fs are both robust against adversarial examples:
2. if n McAU B and x E A U By, then the adversarial examples of fs at x (if exists) cannol transfer to Ji
Proof of Theorem 5.8. The proof of the first result is also straightforward, which is omitted here. It remains to prove the second result. By Equation (7), denote
d=(x. By) Ay) aó d2(x, No(A, UB)) fx()= = fa(x) onn (x; fi) d2(x, By) d2(x, Ay)
(B.58)
aó d2 No U
For Vx E A O B such that 8) MCAUI B and A, U By, denote the unspecific adversarial example (if exist) of fa at by X2. Assume that x E An Ay WLOG. By definition, we have
fx()) E - 1.1 + e].
(B.59)
By the 2A- 2A-separated assumption of A, and By, we have and
fx(x)) E [1 - E. 1 + e].
(B.60)
Since x E Ay U By, we have x E No(A, U By) and
Jnn (x: fo) E [1 - e,,
(B.61)
which implies that
f,(x) X(f oon fa))()) (1 - 0. From (xx)) < O, we can obtain that fx(x)) < O, which implies that (Nai fo) fb(x)< <6,
(B.62)
(B.63)
which implies that
& (aai 1-E
<E
(B.64)
By definition, we have
= x(;; (ca(::))) (1 -6² - 0.
(B.65)
By A and the 2 2e-separdted assumption of A and B, have
(d) 2
28
hxxx== 1 dx(Xx. B) + dx(xx.. A)
(B.66)
21 2
By ((x we have x, E No(A B)), i.e.,
6on(X. S1) E [1
-1--6 - l
(B.67)
Together, we have
1- E 0.
f(xx,) 2 (x)x)))))))))
(B.68)
which completes the proof.
Proposition 5.9. For any classifier f with Raa(f")= 0 and perturbation radius e (r)(f"),)), there is f F such that
1. Raalf) Rua(f"), and
2. for E A B, Na is an adversarial example of f at x, then exists X, B(x,, 1/4) such that X,, is adversarial example of f.
20

---

Proof of Proposition 5.9. Define the following set
S. == [x [0. (0.1 A Ex' EAUBLLX E B(x;O), 0),
(B.69)
and let
G= Bixx
(B.70)
By definition, AU B e G. Consider
f(x) = fx)) (000)))44
(B.71)
Since AU B E G. we have Rad(f) = Rx) = Rsa(f)) For Vx EAU B, if X, is an adversarial example of f" at x, then
ro(f))
S (x G) ra(f)
(B.72)
4
2
which implies that exists X B(2,, )/4) such that X,, an adversarial example of f.
21


Reviews:
[{"review_id": "p4StAhXIFx", "reviewer": "Reviewer_KVUg", "summary": "This paper provides a analysis of transfer-based attacks within a unified theoretical framework. The authors introduce the manifold attack model, which serves as an explanatory tool, formalizing commonly held beliefs and shedding light on previously observed empirical results. Through their model, they elucidate the phenomenon of transferability in adversarial examples, even when the source model is inaccurate, by highlighting the role of the data manifold's curvature. ", "questions": "None", "limitations": "Yes", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The paper addresses the crucial problem of transfer-based attacks, which are a significant threat to the security and robustness of machine learning models.", "weaknesses": "One major concern with this paper is the lack of sufficient quantitative analyses. While the proposed manifold attack model offers a theoretical framework for understanding transfer-based attacks, it would greatly benefit from concrete quantitative analyses to support its claims. One suggestion is to fit the model using low-dimensional data and perform a thorough verification. This would not only provide empirical evidence for the effectiveness of the proposed model but also enhance the paper's credibility by demonstrating its applicability in practical scenarios. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer KVUg:\n\nThank the reviewer for providing helpful comments and constructive feedback. We will clarify the possible confusion in our response.\n\nAs its title suggests, our paper's primary effort is to explain the properties of TBAs from a theoretical perspective. We propose an explanatory model that is consistent with existing results. In other words, the existing quantitative analyses (e.g., Dong et al., 2022; Papernot et al., 2017; Tramèr et al., 2017) could already support our claims. Besides, we also provide a detailed discussion in Appendix A on the reason why further empirical verification is unnecessary for validating our proposed model. \n\nHowever, we are indeed inspired by the reviewer's suggestion. We fit the proposed model using (synthetic) low-dimensional data and conduct numerical experiments on neural networks. A summary of the experiments and the corresponding analysis can be found in the global response.\n\nThanks again for the reviewer’s comments and feedback. We hope that we have addressed the reviewer's concerns. Please let us know if there are any further questions.\n\n**References**\n\nYinpeng Dong, Shuyu Cheng, Tianyu Pang, Hang Su, and Jun Zhu. Query-efficient black-box adversarial attacks guided by a transfer-based prior. IEEE Trans. Pattern Anal. Mach. Intell., 2022.\n\nNicolas Papernot, Patrick D. McDaniel, Ian J. Goodfellow, Somesh Jha, Z. Berkay Celik, and Ananthram Swami. Practical black-box attacks against machine learning. In AsiaCCS, 2017.\n\nFlorian Tramèr, Nicolas Papernot, Ian J. Goodfellow, Dan Boneh, and Patrick D. McDaniel.  The space of transferable adversarial examples. CoRR, abs/1704.03453, 2017."}, {"review_id": "TZZ3HtAMOJ", "reviewer": "Reviewer_rJF7", "summary": "This paper proposes an explanatory model for the transferability phenomenon of adversarial examples. This model involves a specific hypothesis class that can be decomposed into a “semantic classifier” and a “geometric multiplier.” The authors then use a specific choice of these classifiers to explain two interesting observations in the literature that lacks any theoretical understanding. Finally, the paper also tries to establish a relationship between the proposed model to ReLU neural networks. \n\n---\n\nAfter reading the rebuttal and the other reviews, I decide to raise the score from 4 to 5.", "questions": "1. Is the following statement from L145-146 contradictory?\n    \n    > In most cases, the adversarial perturbations are regarded as imperceptible to humans, which implies that adversarial examples are **not** naturally generated data.\n    \n    I can potentially agree that adversarial examples are not in support of $D(\\mathbf x)$ because we don’t simply find adversarial examples by sampling from $D(\\mathbf x)$. However, the reasoning above does seem contradictory to me.\n    \n2. Can the authors justify the need to differentiate the support of $D(\\mathbf x)$ from the natural image manifold $\\mathcal M$? I am wondering if we can simply unify the two. Here’s my reasoning: based on the paper, my understanding is that $D(\\mathbf x)$ represents train/test data of the given classification task (e.g., cats vs dogs), and $\\mathcal M$ represents a space of all possible natural images. So the support of $D(\\mathbf x)$ is a subset of $\\mathcal M$ (please correct me if my understanding is incorrect). Coming back to the cats vs. dogs example, I can see that there is the “noisy” version of the adversarial examples which I’d regard as in **neither** $\\mathcal M$ nor the support of $D(\\mathbf x)$. Another type of adversarial example might be the **imperceptible** one which I see as something in **both** $\\mathcal M$ and support of $D(\\mathbf x)$. Now this makes me wonder what are the adversarial examples that are in $\\mathcal M$ but **not** on the support of $D(\\mathbf x)$? In other words, as far as I know, there are no adversarial examples that look like a snake (or any other objects) in the cats vs. dogs task, for example. So if there are no adversarial examples that fit this last category, can we just unify $\\mathcal M$ and the support of $D(\\mathbf x)$? What would be the implication in this case?\n3. An issue with the assumption on L222 that states\n    \n    > we let the semantic classifier of $f_t$ be the classifier $f^*_b$ in Proposition 4.4.\n    \n    I interpret this assumption as that the semantic classifier is perfect, and the adversarial examples simply exist because of the geometric multiplier. If I understand correctly, this also implies that $f_t$ does not have on-manifold adversarial examples which I think is not very accurate as the previous work has shown both on- and off-manifold adversarial examples on typical neural networks. Can the authors discuss more the implications of this assumption (e.g., Why is it reasonable? What would fail if we don’t assume this?)?", "limitations": "I do not see an explicitly listed limitation section. Please refer to the Weaknesses section.", "rating": 5, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "1. This paper provides an easy-to-follow and intuitive model for explaining the transferability of adversarial examples. The decomposition into on- and off-manifold components makes a lot of sense here and is also fairly novel.\n2. The paper provides a lot of clear definitions and background which makes it self-contained. I really appreciate the efforts that go into making this paper comprehensive and easy to read.\n3. The problem of transferability is indeed not well-explored theoretically. This paper fills in the gap in my understanding fairly well by formalizing many concepts that have been floating around in the literature.", "weaknesses": "My main concern about this work is the applicability of the model. The results depend on rather strong assumptions about a specific model, and I am not fully convinced that this model accurately describes a neural network. I list more detailed comments below:\n\n1. All of the results in the paper are based on a specific form of semantic classifier and concentration multiplier from Proposition 4.3 and 4.5, respectively. I wonder if all the results also hold for all combinations of semantic classifiers (Definition 4.1) and concentration multipliers (Definition 4.3).\n2. Proposition 4.7, 4.8, and Example 4.10 are shown for a specific choice of the concentration multiplier (i.e., $\\phi_{\\mathrm{on}}$ or $\\phi_{\\mathrm{off}}$). This further limits the applicability of these statements. Can the authors justify why these specific choices are reasonable?\n3. Proposition 4.6 also seems to hold generally. We can see off-manifold adversarial examples as an $\\epsilon$-expansion of the data manifold $\\mathcal M$ so if an adversarial example exists in $\\mathcal M$, then there must also exist its off-manifold version. Therefore, in my opinion, the major results of the paper start from Proposition 4.7 onward.\n4. Section 5.1 shows that the hypothesis class $\\mathcal F_{\\mathcal M}$ can be approximated with ReLU neural networks, but I believe a reverse statement would be much more powerful. The current result is perhaps not surprising given that it is well-known that a neural network is a universal function approximator. In other words, it is more important for the results in this paper to be relevant in practice if a neural network can be approximated by some $f \\in \\mathcal F_{\\mathcal M}$. \n5. I can see that Section 5.2 and Proposition 5.9 attempt to show the universality of the model which partially addresses my first concern. However, I would hope to see a stronger result showing that typical (or even toy-ish) neural networks can indeed be decomposed into the very specific form of semantic classifier and concentration multiplier used in the proofs. It would be powerful evidence for convincing the community that the proposed explanatory model is truly applicable to neural networks. My suggestion is to rely on an empirical experiment on synthetic toy datasets, which have well-defined on- and off-manifold subspaces.\n6. It will also be a big plus if the authors can use the developed model to predict some undiscovered empirical behavior of the transferability phenomenon.\n\n### Minor typo\n\n1. Missing parenthesis in Equation (7).\n\nI am happy to reconsider my rating if the authors can address my concerns during the rebuttal period.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer rJF7:\n\nThanks to the reviewer for appreciating our effort and providing constructive feedback. We will reply to the reviewer’s concerns point by point in our response. Due to limited space, we will replace $\\mathcal{M}$ and $\\mathbf{x}$ by $M$ and $x$.\n\n**Weakness 1** \n\nIt is true that the main results are based on a specific form of $f_b$ and $\\phi$.\nDefinitions 4.1 and 4.2 only provide abstract definitions of $f_b$ and $\\phi$ that might better reveal the motivation and intuitions, while specific definitions (e.g., Proposition 4.3 and 4.5) are necessary for quantitative analysis. It is easy to check that $f_b$ and $\\phi$ defined by Definitions 4.1 and 4.2 cannot even be parametrized (uniquely decided by the corresponding semantic/geometrical information). Therefore, it is necessary to specify a \"specific form\" (i.e., Proposition 4.3 and 4.5) of $f_b$ and $\\phi$ to obtain quantitative results.\n\nBack to the reviewer’s concern. Since a specific form of $f_b$ and $\\phi$ is necessary, our results do not hold for all combinations of $f_b$ and $\\phi$ defined by Definition 4.1 and 4.2. However, we can replace the specific forms in Proposition 4.3 and 4.5 with other specific forms. According to the proofs, we believe that any $f_b$ and $\\phi$ that is somehow continuous (w.r.t. the distance to semantic/geometrical information) can derive similar results. \n\n**Weakness 2** \n\nIn this paper, we only impose mild assumptions on the manifold $M$ (i.e., smooth and compact), the distribution $D$ (i.e., continuous and supported on M), and the geometrical information $G$ (i.e., $G \\subset \\mathbb{R}^d$ in Proposition 4.5). To perform a more delicate analysis, it is necessary to introduce stronger assumptions on at least one of M, $D$, or $G$. This paper further assumes that $G = M$ in $\\phi_{off}$ and $G = \\mathcal{N}\\_{\\delta}(A_f \\cup B_f)$ in $\\phi_{on}$. Alternatively, by introducing stronger assumptions on $M$ and $D$, it is possible to extend our results to any $\\phi$ defined in Proposition 4.5. However, this analysis is beyond the scope of this paper.\n\nGenerally speaking, the manifold attack model enables us to construct a variety of different classifiers that have different desirable properties by choosing different $f_b$ and $\\phi$. In this paper, we choose the two specific $\\phi$ in Equations (6) and (7) for the following reason. Intuitively, we believe that the off-manifold adversarial examples are more transferable than the on-manifold ones. Therefore, the \"desirable properties\" of our paper is that a classifier suffers from (almost) only either of the on- or off-manifold adversarial examples. We construct such classifiers (by specifying $\\phi$ in Equations (6) and (7)) and prove that they are consistent with existing empirical results (cf. Lines 26-36), which provides possible reasons for the properties of TBA. Any other specific choices of $f_b$ or $\\phi$ would be good if their combination could also explain the properties. We make our choices because we think they sufficiently solve our problems.\n\n**Weakness 3** \n\nThe reviewer’s understanding of $D$ and $M$ may not be correct. In the binary case, the support set of $D$ equals $A \\cup B$ (Line 189). The relationship between $A \\cup B$ and $M$ is visualized in Figure 1. Apart from natural data, there are also noise vectors in $M$ that lie outside of $A \\cup B$. In the cats vs. dogs examples, these noise vectors are more likely to be unrecognizable than look like a snake or any other object, even if they also lie in $M$. On the other hand, any $x \\in [0,1]^d$ would be recognizable or even imperceptible to humans if $x$ is close enough to $A \\cup B$, regardless of whether $x \\in M$ or not.\n\nInformally speaking, we can see the adversarial examples as lying in an expansion of the combination of the semantic and the geometrical information of the classifier, instead of an expansion of $M$. Therefore, Proposition 4.6 does not hold generally by intuition.\n\n**Weakness 4** \n\nThe contributions of Section 5.1 are twofold\n1. The universal approximation theorem has its assumptions and target functions. Approximating functions on a manifold is a stronger result than the universal approximation theorem. \n2. More importantly, we show that after approximating $f \\in F_M$ by ReLU networks, one of the main results in our paper (i.e., Proposition 4.7) can be partially recovered.\n\nAdmittedly, a reverse statement would be much more powerful. We discuss the possibility of such approximation in the global response.\n\n**Weakness 5** \n\nSee the global response.\n\n**Weakness 6** \n\nApart from the main explanatory results in Proposition 4.7 and 4.12, our work also proves some minor non-explanatory results. Propositions 4.6 and 4.8 can be viewed as our predictions of the undiscovered empirical behaviors.\n\n**Question 1** \n\nApologies for the unclear representation. We leave out the assumption of this statement that the adversarial examples should be w.r.t. accurate classifiers and natural data. Assume that an adversarial example is also naturally generated. Since the perturbation is imperceptible, the ture labels (notice that only natural data have ture label) and the predicted labels (of the accurate classifier) of the adversarial example and its corresponding natural data should both be the same, which leads to contradiction.\n\n**Question 2** \n\nWe have replied to this question in Weakness 3.\n\n**Question 3**\n\n$f_t = f_b^* \\cdot \\phi$ does not implies that $f_t$ have no on-manifold adversarial examples. We explain this in the binary case. Since $\\phi$ not necessarily learns the exact shape of $M$ (i.e., it is possible for some $x \\in M$ that $\\phi(x) < 0$), the sign of $f_t$ could be different from $f_b^{*}$, which leads to on-manifold adversarial examples.\n  \nThanks again for the reviewer’s comments and feedback. We hope that we have addressed the reviewer's concerns. Please let us know if there are any further questions.\n"}, {"review_id": "NGishjFJ27", "reviewer": "Reviewer_9Mj1", "summary": "The paper proposes a new framework, manifold attack models, to explain the transferability of adversarial examples. The model divides adversarial examples into on-manifold examples and off-manifold examples, where the former one lies in the low dimensional manifold of natural data. The paper show that off-manifold adversarial examples are transferable when the source model is inaccurate. It also prove that the non-existence of off-manifold adversarial examples is one of the reasons why the success rates of TBAs are hard to improve.", "questions": "See Weakness.", "limitations": "See Weakness.", "rating": 5, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 4, "strengths": "1. The paper takes a large step towards an very important and interesting problem, why adversarial examples are transferable across different models. It conducts  in-depth theoretical analysis into the problem, which previous works did not perform.\n2. The theoretical analysis successfully explain find several practical properties of the adversarial examples: (1) an inaccurate source model can transfer to the target model with a non-negligible success rate; (2) the success rates of TBAs are constantly lower than other methods of black-box attacks.\n\nI think the paper makes great contribution towards understanding adversarial examples if the statements are correct. But I cannot judge their correctness based on the current version (see weakness).", "weaknesses": "The paper is very hard to read. I suggest the authors to format their presentation of the work in the following aspects.\n\n1. Clearly states the assumption of each proposition and theorem. For example, I think one assumption of propositions in Section 4 is the specific forms of the classifiers, which are not clearly stated.\n2. Formally states their propositions and theorems using mathematical languages. For example, replace \"suffers from off-manifold adversarial examples\" in Proposition 4.6. with formal mathematical equations and explain the meaning of the equations after the theorem.\n3. Reduce the number of propositions and give one main theorem for one conclusion with one main theorem.\n\nIn addition, it is hard to evaluate the correctness of the these theorems without mathematical languages in current version.\n\nAnd I think the paper also make strong assumption that the classifier need to have certain forms, which limits the contribution of the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer 9Mj1:\n\nThanks to the reviewer for providing helpful comments and constructive feedback. Apologies for the possible confusion due to the unclear presentation. We will restate and clarify our contributions in our response. \n\nFirst of all, we would like to clarify that the results from Proposition 4.3 to Proposition 5.9 are rigorously written in mathematical language.\nOur paper seems to include some \"mathematically informal\" language for the following reason. During the writing of this paper, we intentionally adopt some terminologies (e.g., suffer from, be vulnerable to, transfer to, and be robust against) from previous empirical works, expecting to create some connections between previous works and ours. We will explain the meaning of these terms later in this response. We will also restate the assumptions as required by the reviewer.\n\nAs for the concern that this paper provides too many propositions, we will rewrite the propositions that are directly related to our main explanatory results (i.e., Propositions 4.7 and 4.12) as theorems. The propositions that only related to minor results would stay unchanged.\n\nLast but not least, we must clarify that the assumptions in this paper are actually much milder than those in previous theoretical works that study TBA (Lines 90-99). We provide a detailed discussion on the reasonableness of the assumption \"the source and target model could be decomposed into the product of a semantic classifier and a concentration multiplier\" in the global response. \n\nThanks again for the reviewer’s comments and feedback. We hope that we have addressed the reviewer's concerns. Please let us know if there are any further questions.\n\n**Restating Terms and Assumptions**\n\nWe first restate the major assumptions of our paper.\n\n**Assumption R.1 [cf. Line 120-122]** Let $\\mathcal{M} \\subset [0,1]^d$ be a compact smooth manifold. Assume that the dimension of $\\mathcal{M}$ is less than $d$. Let $D$ be some given continuous distribution that is supported on $\\mathcal{M}$. We say that a random variable $x$ is natural data if $x \\sim D$.\n\nThere is a typo in the definition of adversarial examples in Line 130. In practice, we only care about the adversarial examples of natural data $x \\sim D$ instead of any $x \\in \\mathbb{R}^d$.\n\n**Assumption R.2 [cf. Line 178-184]** Let $f$ be the source or target model of a TBA. If $k=2$, we assume that $\\exists f_b, \\phi$ such that $f(\\mathbf{x}) = f_b(\\mathbf{x}) \\cdot \\phi(\\mathbf{x})$ for $\\forall \\mathbf{x} \\in [0,1]^d$. If $k > 2$, we assume that $\\exists f_b, \\phi$ such that $f^{(j)}(\\mathbf{x}) = f_b^{(j)}(\\mathbf{x}) \\cdot \\phi(\\mathbf{x}), \\forall 1 \\leq j \\leq k$ for $\\forall \\mathbf{x} \\in [0,1]^d$. Here, $f_b$ and $\\phi$ are semantic classifiers and concentration multipliers defined in Definitions 4.1 and 4.3, respectively.\n\nNext, the \"mathematically informal\" terms are restated as follows.\n\nGiven perturbation radius $\\delta$ and $x \\in \\mathbb{R}^d$, a data point $x_a \\in B(x;\\delta)$ is called an **adversarial example** of $f$ at $x$ if $y(f,x) \\neq y(f,x_a)$. \n\nWe say that a classifier **suffers from**, or **is vulnerable to** (on-, off-manifold) adversarial examples if $\\exists x \\sim D, x_a \\in B(x;\\delta)$ such that $x_a$ is an (on-, off-manifold) adversarial example of $f$ at $x$. \n\nWe say that a classifier is **robust against** (on-, off-manifold) adversarial examples if this classifier does not suffer from (on-, off-manifold) adversarial examples. \n\nWe say that an adversarial example $x_a$ of $f_s$ at $x$ **transfers to** $f_t$ if $x_a$ is also an adversarial example at $x$ of $f_t$.\n"}, {"review_id": "r3Aw8U4SzU", "reviewer": "Reviewer_HLto", "summary": "The paper focuses on a black-box adversarial attack method called the transfer-based attacks (TBA). The paper establishes a unified framework that explains the properties of TBAs, which has never been done by previous work. More specifically, the paper explains \n1. why adversarial examples are transferable when the source model is inaccurate\n2. why TBA’s success rate is hard to improve.\nThe paper also discuss\n1. how to approximate their model with ReLU networks\n2. the expressive power of their model\n", "questions": "1. The authors claim (l. 26-26, l. 90-91) that previous works “rely heavily on either simple models or strong assumptions”, but the references seem to be out of date. The authors should include more related work in the past few (2-3) years.\n2. It is not proper to claim that the proposed model “explains that properties of TBAs” (l. 39). It seems that this paper only explains those properties of TBA that is mentioned in l.26-35 and l. 82-89. If there are any other properties of TBA that cannot be explained by the proposed model? \n", "limitations": "N/A", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper provides theoretical explanation for the properties of TBA. Comparing to previous works in this area, the paper is based on milder assumptions, provides more delicate results, and can view some previous works as special cases. The paper also discusses the proposed model’s expressive power and approximates the model with ReLU networks. ", "weaknesses": "1. The paper does not quantitatively discuss how $f_b$ and $\\phi$ control the semantic and geometrical information of the classifier. The intuition behind these two functions are not clear enough.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer HLto:\n\nThanks to the reviewer for appreciating our effort and providing helpful feedback. We will clarify the reviewer’s concerns in this response.\n\n**(Weakness 1)**\n\nIn this paper, we assume that the source and target model can be decomposed into the product of a semantic classifier $f_b$ and a concentration multiplier $\\phi$. In the global response, we further discuss the reasonableness of this assumption. Informally speaking, the intuition behind this assumption is that the classifier can capture both semantic and geometrical information of the natural data (Lines 45-49).\n\nIn our analysis, $f_b$ and $\\phi$ can be parameterized by the semantic and geometrical information, respectively. Here, the semantic information is represented by subsets of $\\mathcal{M}$. Consider the binary classification example. The semantic information of natural data is $A = \\{\\mathbf{x} : y(\\mathbf{x}) = 1\\}$ and $B = \\{\\mathbf{x} : y(\\mathbf{x}) = -1\\}$ (Line 193), and the semantic information learned by $f_b$ is $A_f$ and $B_f$ (Proposition 4.4). We do not quantitatively discuss the relationship between $A$, $B$, $A_f$, and $B_f$ (i.e., how $f_b$ controls the semantic information of natural data) since our paper only imposes mild assumptions on the manifold $\\mathcal{M}$ (i.e., smooth and compact) and the distribution $D$ (i.e., continuous and supported on $\\mathcal{M}$). By introducing stronger assumptions on $\\mathcal{M}$ and $D$, it is possible to perform quantitative analysis on how $f_b$ controls the semantic information of natural data. However, this analysis is beyond the scope of this paper.\n\nWe can do the same analysis on concentration multipliers and geometrical information, which is omitted here.\n\n\n**(Question 1)**\n\nTo the best of our knowledge, there has been no theoretical work that explains the transferability of adversarial examples in the past two to three years. This is mainly due to the limited information provided by the black-box attack model. \n\n**(Question 2)**\n\nApologies for the possible misunderstanding. Our paper mainly discusses the following two properties of TBAs:\n+ The adversarial examples of an inaccurate source model can transfer to the target model.\n+ The success rates of TBAs are hard to improve.\n\nTo the best of our knowledge, the above properties are the only two that satisfy the following criteria: \n+ The property commonly held by different methods of TBAs. \n+ The property cannot be explained by existing theory. \n\nThat is why we only explain these two properties in this paper.\n \nThanks again for the reviewer’s comments and feedback. We hope that we have addressed the reviewer's concerns. Please let us know if there are any further questions.\n"}, {"review_id": "u7qQuK38Fw", "reviewer": "Reviewer_b7e2", "summary": "This paper proposes an explanatory model for transfer-based attacks (TBAs). This model formalizes two popular intuitions and specify a hypothesis class $F_M$. By assuming that the source and target models come from $F_M$, this paper explains the properties of TBA. This paper also discusses some properties of the model itself.", "questions": "+ Are there any similar definitions about the semantic/geometrical information in previous works?\n+ Whether the manifold attack model can be used to derive probabilistic bound on the success rate of TBAs?", "limitations": "N/A", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "+ Technically solid paper with rigorous mathematical proofs.\n+ The way that this paper formalizes semantic/geometric information is very interesting. The proposed model greatly simplifies the analysis while not making too much assumptions. This technique might be useful in other fields of research like transfer learning and domain adaptation.", "weaknesses": "+ The main results (Section 4) of this paper are not well-organized. It seems that the authors have put all related results in just one section, which would confuse the readers that are not familiar with this topic.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer b7e2:\n\nThanks to the reviewer for appreciating our effort and providing helpful feedback. We will reply to the reviewer’s concerns point by point in our response.\n\n**(Weakness 1)**\n\nThis paper tries to explain several parallel properties of TBAs. As a result, it is hard to integrate the propositions in section 4 into two to three main theorems. As a remedy, we will rewrite the propositions that are directly related to our main explanatory results (i.e., Propositions 4.7 and 4.12) as theorems in future revisions.\n\n**(Question 1)**\n\nIn our paper, Definition 4.1 and 4.2 provide the abstract definitions to semantic classifiers and concentration multipliers. As mentioned in section 1 (Lines 45-49), these two concepts are motivated by empirical works, e.g., Ilyas et al., 2019 and Allen-Zhu and Li, 2021. To the best of our knowledge, there is no similar definitions about the semantic classifier or geometrical multiplier in previous works. As for the specific form of $f_b$ and $\\phi$ in Proposition 4.3 and 4.5, we are largely inspired by Li et al., 2022, as we have mentioned in the related works.\n\n**(Question 2)**\nOur proposed model can be used to derive probabilistic bound on the success rate of TBAs. In fact, Gilmer et al., 2018 study the transferability of adversarial examples from a probabilistic point of view. The data model in Gilmer et al., 2018 can be view as a special case of our proposed model. However, deriving probabilistic bound require much stronger assumptions on the distribution $D$ and the manifold $\\mathcal{M}$, which is beyond the score of our paper.\n\nThanks again for the reviewer’s comments and feedback. We hope that we have addressed the reviewer's concerns. Please let us know if there are any further questions.\n\n**Reference**\n\nAndrew Ilyas, Shibani Santurkar, Dimitris Tsipras, Logan Engstrom, Brandon Tran, and Aleksander Madry. Adversarial examples are not bugs, they are features. In NeurIPS, 2019.\n\nZeyuan Allen-Zhu and Yuanzhi Li. Feature purification: How adversarial training performs robust deep learning. In FOCS, 2021.\n\nBinghui Li, Jikai Jin, Han Zhong, John E. Hopcroft, and Liwei Wang. Why robust generalization in deep learning is difficult: Perspective of expressive power. CoRR, abs/2205.13863, 2022.\n\nJustin Gilmer, Luke Metz, Fartash Faghri, Samuel S. Schoenholz, Maithra Raghu, Martin Wattenberg, and Ian J. Goodfellow. Adversarial spheres. In ICLR, 2018.\n"}]

Author rebuttal:
Dear Reviewers:

Thanks to the reviewers for their helpful comments and constructive feedback. We adopt the suggestion of verifying our assumption from multiple reviews. In this response, we further discuss the reasonableness of our assumption and provide a brief summary of the additional numerical experiment.

The reviewers' major concern is about the reasonableness of the assumption that is formalized as follows:

**Assumption R.2 [cf. Line 178-184]** Let $f$ be the source or target model of a TBA. If $k=2$, we assume that $\exists f_b, \phi$ such that $f(\mathbf{x}) = f_b(\mathbf{x}) \cdot \phi(\mathbf{x})$ for $\forall \mathbf{x} \in [0,1]^d$. If $k > 2$, we assume that $\exists f_b, \phi$ such that $f^{(j)}(\mathbf{x}) = f_b^{(j)}(\mathbf{x}) \cdot \phi(\mathbf{x}), \forall 1 \leq j \leq k$ for $\forall \mathbf{x} \in [0,1]^d$. Here, $f_b$ and $\phi$ are semantic classifiers and concentration multipliers defined in Definitions 4.1 and 4.3, respectively.

Assumption R.2 suggests that a neural network can be exactly (or approximately) decomposed into the product of two functions of specific forms. As is commented by Reviewer rJF7, such results can be viewed as the "reverse of the universal approximation theorems". To the best of our knowledge, there are no existing theoretical or empirical results that prove similar results. 

Here, we take a step back and consider the following weaker version of Assumption R.2. For the sake of simplicity, we only consider the binary classification in Euclidean space (cf. Lines 246-252). Recall that given compact smooth manifold $\mathcal{M}$, exists $\Delta > 0$ such that $\mathcal{N}_{\Delta}\mathcal{M}$ is a tubular neighborhood of $\mathcal{M}$ (cf. Lemma 4.12).  

**Assumption R.3** Let $f$ be the source or target model of a TBA. Let $\mathcal{M}\_1$ be a compact smooth manifold that is not necessarily a subset of $\mathcal{M}$. Let $\mathcal{N}\_{\Delta\_1}\mathcal{M}\_1$ be a tubular neighborhood of $\mathcal{M}\_1$ for some $\Delta_1 > 0$. We assume that for $\forall \mathbf{x} \in \mathcal{M}\_1$ and for any non-zero $ \mathbf{u} \in N\_{\mathbf{x}} \mathcal{M}\_1$, we have: $f(\mathbf{x} + r_1 \mathbf{u}) > f(\mathbf{x} + r_2 \mathbf{u})$ holds for $\forall \Delta > r_2 > r_1 > 0$.

By letting $G$ in Definition 4.2 take $G = \mathcal{M}\_1$, the classifier in Assumption R.2 would also satisfy Assumption R.3. Next, we verify this assumption on low-dimensional linearly separated data. Given $d > \kappa > 0$, consider the $\kappa$-dimensional manifold (in this case, a flat plane) $\mathcal{M} = \\{ (x_1, x_2, \cdots, x_{\kappa -1}, x_{\kappa} , 0, \cdots, 0) : x_i \in \mathbb{R}, \forall i = 1, 2, \cdots, \kappa \\} \subset \mathbb{R}^d$.
Assume that the natural data $\mathbf{x} \in \mathcal{M}$ is drawn from some continuous distribution $D(\mathbf{x})$, say, a mixture of Gaussian distribution.

For the sake of simplicity, let the natural data be linearly separable in the following sense.
Given $\lambda > 0$ and natural data $\mathbf{x} = (x_1,\cdots, x_d)$, we assume that $|x_1| > \lambda$, and the label of $\mathbf{x}$ is decided by $y(\mathbf{x}) = 1$ if $x_1 > \lambda$, and $y(\mathbf{x}) = -1$ if $x_1 < -\lambda$.

Our goal is to train a classifier that satisfies Assumption R.3.
Here, we briefly introduce the (theoretical) training settings.
Given $N > 0$, let the training set $S_N = \\{ \mathbf{x}_1, \mathbf{x}_2, \cdots, \mathbf{x}_N \\} \sim D^N(\mathbf{x})$ be independent and identically distributed (i.i.d.) random variables.
For $\forall 1 \leq n \leq  N$, denote the label of $\mathbf{x}_n$ by $y_N$.
Since $D$ is continuous, we assume without loss of generality that $\left( \exists a \in \mathbb{R} \ s.t. \ \mathbf{x}_i = a \mathbf{x}_j \right) \implies i=j$ holds for $\forall 1 \leq i, j \leq N$. 

The hypothesis class is defined as $\mathcal{F}\_{\mathbf{w}} = \\{ f\_{\mathbf{w}}: \mathbf{w} \in \mathbb{R}^d \\}$, where $f\_{\mathbf{w}}(\mathbf{x}) = \langle \mathbf{w}, \frac{\mathbf{x}}{ || \mathbf{x} ||\_2}  \rangle$ for $\forall \mathbf{x} \in \mathbb{R}^d$.
Consider the logistic loss function $\ell(u) := \log (1 + \exp(-u)),\ \forall u \in \mathbb{R}$, and the gradient descent (GD) iteration $\mathbf{w}(t+1) = \mathbf{w}(t) - \eta  \nabla_{\mathbf{w}} \mathcal{L}_N(\mathbf{w}(t))$.
We can show that (formal statements and proofs are not provided in this response due to limited space):
+ The GD iteration converges to an accurate classifier $\hat{f}$,
+ $\exists \mathcal{M}_1$ such that $\hat{f}$ satisfy Assumption R.3,

which implies that **we can actually train an accurate classifier (instead of constructing one using oracle information) that satisfies our assumption.**

We also validate this assumption on neural networks based on numerical experiments. We modify the above theoretical training setting by:
+ In order to visualize our results, the manifold $\mathcal{M}$ is set to be a 2-dimensional plane embedded in $\mathbb{R}^3$.
+ The distribution is a mixture of two Gaussian distributions with means $(2,2,0)$ and $(-2,-2,0)$ and covariance $\sigma = 0.5$.
+ The loss function is the binary cross-entropy loss (i.e., the logistic loss).
+ The optimizer is SGD.

We train a two-layer network, also denoted by $\hat{f}$, that reaches 100% testing accuracy.
We check whether $\hat{f}$ satisfies Assumption R.3. 
The corresponding experimental results are presented in the attached PDF file.
The experimental results can be interpreted as follows. Denote the vector $\mathbf{x} \in \mathbb{R}^3$ by $\mathbf{x} = (x,y,z)$. The bottom plane is the manifold, i.e., the $(x,y)$-plane. For each sub-figure, we consider the score of $\hat{f}$ at $(x,y,z)$ for a specific $z$ chosen from $\\{0, 3,5,7 \\}$. The height of the surface is the score of $\hat{f}$. Obviously, the score of $\hat{f}$ decreases as $z$ goes larger, which in accord with the claim in Assumption R.3. 

Meta-review: This paper proposes a unified theoretical framework to explain the properties of transferable black-box attacks. To this end, the authors introduced an explanatory model called the manifold attack model, and showed that the transferable adversarial examples exist off-manifold and provide theoretical explanations for common beliefs in the field.

The paper initially received two Strong Accept and three Borderline Rejects. The critical concerns raised by the reviewers were about the soundness of the assumptions such as the generality of the analysis based on the specific form of the classifier, and the lack of quantitive analysis. The authors provided comprehensive responses in the rebuttal, most of which successfully resolved the concerns. As a result, the reviewers updated their recommendations to two strong accept, two borderline accept, and one borderline reject. The negative reviewer however did not respond to the rebuttal.

After reading the paper and discussions, AC agrees with the reviewers that the theoretical explanation of the paper is sound and novel, and hence recommends acceptance. The authors should update the camera-ready paper to include the changes suggested by the reviewers during the review process.
Decision: Accept (poster)