Towards Certified Defense for Unrestricted Adversarial Attacks
Authors: Shengjia Zhao
Yang Song
Stefano Ermon
Venue:  (2020)
Keywords: Adversarial Defense
Certified Defense
Adversarial Examples

Abstract: Certified defenses against adversarial examples are very important in safety-critical applications of machine learning. However, existing certified defense strategies only safeguard against perturbation-based adversarial attacks, where the attacker is only allowed to modify normal data points by adding small perturbations. In this paper, we provide certified defenses under the more general threat model of unrestricted adversarial attacks. We allow the attacker to generate arbitrary inputs to fool the classifier, and assume the attacker knows everything except the classifiers' parameters and the training dataset used to learn it. Lack of knowledge about the classifiers parameters prevents an attacker from generating adversarial examples successfully. Our defense draws inspiration from differential privacy, and is based on intentionally adding noise to the classifier's outputs to limit the attacker's knowledge about the parameters. We prove concrete bounds on the minimum number of queries required for any attacker to generate a successful adversarial attack. For a simple linear classifiers we prove that the bound is asymptotically optimal up to a constant by exhibiting an attack algorithm that achieves this lower bound. We empirically show the success of our defense strategy against strong black box attack algorithms.

Under review as a conference paper at ICLR 2020
TOWARDS CERTIFIED DEFENSE FOR UNRESTRICTED ADVERSARIAL ATTACKS
Anonymous authors Paper under double-blind review
ABSTRACT
Certified defenses against adversarial examples are very important in safety-critices applications of machine learning. However, existing certified defense strategies only safeguard against perturbation-baat adversarial attacks, where the attacker is only allowed to modify normal data points by adding small perturbations. this paper, we provide certified defenses under the more general threat model of unrestricted adversarial attacks. We allow the attacker to generate arbitrary inputs to fool the classifier, and assume the attacker knows everything except the classifiers' parameters and the training dataset used to learn it. Lack of knowledge about the classifiers parameters prevents attacker from generating adversarial examples successfully. Our defense draws inspiration from differential privacy, and is based intentionally adding noise to the classifier's s outputs to limit the attacker's knowledge about the parameters. We prove concrete bounds on the minimum number of queries required for any attacker generate successful adversarial attack. For a simple linear classifiers we prove that the bound is asymptotically optimal up to a constant by exhibiting an attack algorithm that achieves this lower bound. We empirically show the success of our defense strategy against strong black box attack algorithms.
INTRODUCTION
Classifiers trained using machine learning can often achieve high accuracy on test data coming from the same distribution as the training one. Unfortunately, for a class of inputs called adversarial examples (Szegedy et al., 2014), many classifiers can be fooled to give wrong predictions with high confidence. This poses significant security risk for real world deployment of machine learning models. To mitigate this threat, many methods have been proposed to defend against adversarial examples (see, e.g., Papernot et al. (2016); Song et al. (2018a); Ma et al. (2018); Buckman et al. (2018)). However, empirically grounded methods are often found to be ineffective using newer attack methods that they had originally not considered (Carlini & Wagner, 2017; Athalye et al., 2018). To end this arms race, defenses with certified theoretical guarantees against threat model have recently gained more traction (see, e.g., Raghunathan al. (2018); Wong & Kolter (2017); Dvijotham et al. (2018); Cohen et al. (2019)).
Existing certified defense methods are all restricted to perturbation-bast based attacks (Song et al., 201 2018a), a threat model where the attacker is only allowed to generate an adversarial example by perturbing existing data points using small adversarial noise. In addition, certified defense for one type of perturbation (e.g., based on la norm) can still be vulnerable to a different type of perturbation (e.g. spatial transform (Xiao et al., 2018)). Following Song et (2018b) and Brown et (2018), we consider the much more general threat model of unrestricted adversarial attacks, where the small perturbation restriction removed: any input is considered valid adversarial example as long as induces the classifier to predict a different label than oracle classifier. As shown in Song et al. (2018b), existing certified defenses are not robust to unrestricted adversarial attacks.
In this paper, we provide a defense strategy with (asymptotically) certified guarantees against unrestricted adversarial attacks. The attacker can use any strategy to choose any input, and the attack is successful as long the input is confidently classified into the wrong class by the target classifier. Note that in the white-box setup, where the attacker has access to all parameters of the classifier, defending against unrestricted adversarial examples is essentially impossible unless the classifier is

---

Under review as a conference paper at ICLR 2020
perfect, because the attacker can simply enumerate all possible inputs to find adversarial ones (we do not assume any computational restriction of the attacker). As a result, we focus our discussion on black-box unrestricted attacks, where the attacker does not know the exact parameters of the model nor the exact training data (otherise, the attacker could recover the parameters by simulating the learning algorithm), but can query the model for limited number of times before making unrestricted adversarial examples. For example, for online services, it is easy to limit the number of queries allowed per user.
Consider a classifier learned using empirical risk minimization. Because the training data are randomly drawn from the data-generating distribution, the parameters of the classifier will be random even if the training algorithm is deterministic. Since we assume a black-box setting where the attacker does not know the learned parameters or the training dataset, the attacker has to obtain extra information by querying the model, even though the exact training algorithm and even the data-generating distribution might known to the attacker. As a result, we can adopt methods similar to those used in differential privacy (Dwork et al., 2014) to reduce the amount of information about the parameters leaked from each query issued by the attacker.
We give concrete lower bounds the minimum number of queries an attacker needs in order to successfully generate adversarial examples. For most classifiers the guarantees are asymptotic, meaning that the guarantees are valid if the number of training examples is sufficiently large. For very simple classifiers we prove finite sample guarantees. Our bound is also asymptotically minimax optimal with respect to important parameters of the problem the dimension of the input and the size of the training set. We prove this by exhibiting a class of classifiers and a concrete attacking algorithm that successfully generates adversarial examples while querying no more than the minimum necessary according to the lower bounds (up to a constant).
Experimentally, we show that the defense strategy is effective against strong black-box unrestricted attacks, even when we use complex classifiers for which no theoretical guarantee with finite sample size is available. Compared models without any defense, the number of queries needed identify vulnerabilities often increases by order of magnitude using our defense strategy, with negligible effect on the accuracy on "clean" inputs. Providing finite sample guarantees for complex models such as deep neural networks is an open problem for future work.
2 PROBLEM DEFINITION
2.1 CLASSIFICATION
Given a training dataset {(x,, 31) E X x y) learning a classifier to predict the label y for an imput x. To simplify our discussion, we assume that X [],, and y = (-,, Let (g(w.-) X' - R) be a class of score functions with parameter w, whose signs determine the class labels, i.e., y = sign(g(w, (W, x)), where we define sign(x) = 1 when x O, and sign(z) = -1 otherwise. The model family is assumed to be well-specified, i.e., there exists a ground-truth parameter w such that the true labeling function is given by y sign(g(w*..) x)).
iid.
~ p" p²(x)p((y x). we consider the task of
We can use any learning algorithm to obtain w based on a training dataset. Since the training data are randomly generated from the underlying distribution p² (x)p"(( (y x), w is also a random vector and we denote its distribution as Pheara (w). With a reasonable learning algorithm, Pieaen (w) should be increasingly concentrated around w" while the size of the training dataset n grows. When deploying the classifier to real world applications, we might want to use a (possibly stochastic) surrogate score function f(w,-) : X + R which depends on the learned parameter w of our model. Usually, is just g( -), ). but to mitigate adversarial attacks we might choose f(w,,) :) to be some special classifier with defense strategy. To avoid low confidence incorrect predictions, we give no response when the confidence is low. Specifically, we allow a threshold E IR such that given an input query x, the predicted label
if f(W, x) > a if f(w,)) < aa otherwise.
y =
(1)
No response,
2

---

Under review as a conference paper at ICLR 2020
PROTOCOL 1. THE ATTACK DEECNDEE PROTOCOL Attacker knowledge: w", Plearn (W), (T, g.. f(.,)) Interacting procedure:
1. The allucker chooses the distributions qr, 1,... T and Qattack defined as below.
2. The defender samples ~ Plearu (w).
3. For t < -.,....T
(a) The attacker observed 01:-11 (x1, .M (X--1; and sample X qr (x(x||01=-1) as the next query.
(b) The defender sends 24 f(w,,x, xx) to the attacker.
4. The attacker samples Qattack 01:7), where q is probability distribution on X. The attacker outputs (x))
Figure
The attack-defense protocol
2.2 PERFORMANCE EVALUATION
We evaluate the expected performance of the classifier f(w,x) test distribution v(x)pp(( (y x).
The traditional setting in statistical machine learning assumes that g(x) = (x). adversarial settings, however, xx) is the distribution of adversarial examples and is very different from (" (x).
Since we consider unrestricted attacks, we assume no relationship between g(x) and (x).
The classifier f(w, x) make two kinds of errors for given input x. First, f(w, x) might give response. We call this the no-response error, which is denoted as
NR(x; a) & I[If(w, x) a))
where L[P] is the indicator function whose value is when the property P holds; other produces Secondly, f(w, x) can produce wrong prediction with high confidence. We call this the margin error, which defined as
ME(x; a) = [lg(w", < On f(w, > a) + +(g((w" (w", x) > wwfffw,www < -a). <aa)
An ideal classifier f(w, should minimize the expected no-response error Ex(x)) [NR(x; a)) and (M{x))MM(xx [ME(x; a)] simultaneously. When defending against an adversary, the margin errors are more important because confident but wrong prediction is arguably more harmful than giving no prediction at all. Consequently, we only focus on bounding the margin errors achievable by attackers in the sequel. We will only consider no response error for clean data x p² (x).
margin error By(x)
2.3 THE ATTACK- DEERNNE PROTOCOI.
In Figure 1, we provide specific protocol of attack and defense to capture our assumptions of the threat model. Since we consider the threat model of unrestricted adversarial attacks, we assume the attacker to be fully general: The attacker is allowed to use any adaptive set of intermediate distributions {q. 01:-1))
issue queries based on all previous observations. For the final attack distribution q. the attacker is allowed to sample it from any distribution of distributions Qumeck (g OI.)). We call a specific choice of {ge(x 11)= and Qutuck an altack strategy, and specific choice of Plearn (w) and ((, a defense stralegy. We additionally allow the allacker to know the exact defense strategy. Note that when the attack and defense strategies are fixed beforehand, the attack-defense protocol defines a joint probability over w, 01.7 and q.
The protocol can be modified in the defender's favor if defender only sends ye according to Eq. instead of 24. However, using allows normal users (sampling from p (x)) to get confidence score, and any certified defense results are more general (they are still true if attacker only has access to yt).
Intuitively, the attack strategy is successful under the attack-defense protocol, if with high probability the final attack distribution q incurs large expected margin errors for f (ww x). To formalize this intuition, define winning strategy of the attacker follows.

---

Under review as a conference paper at ICLR 2020
Definition 1. For given defense strategy. attack strategy in the attack- protocol is an (a,?t V/ 8) wwiining strategy if with probability at least % the attacker outputs a q such that PTς(x) [ME(x; ai] 2 6.
In the following part, we will propose concrete defense strategy and prove that no winning strategies can exist under some conditions.
TOWARDS A CERTIFIED DEFENSE
In order for certified defense strategy exist we need some reasonable conditions the problem. All the proof's are available in the appendix.
3.1 DEFENSIBILITY
For an omniscient attacker who knows f((,,)) and g(w"..) (this is beyond the capabilities granted by our attack-defense protocol), there will not be any effective defense strategies unless f'(w, x) never produces wrong predictions. This is because the attacker can simply enumerate an input Xbad so that [,(,, Xbad) g(w", Xbad) is maximal, and set gxx) 8xomd (here 6x denotes point mass distribution on x). This results in the maximal average margin error for f(w,x).
defense protocol, the attacker does not have access f(w, -). The randomness of Plearn (w) makes it more difficult for the attacker to infer w through queries. To guarantee the existance of certified defense for all attacks, we need to make sure the randomness of Plearn (w) is sufficient such that no fixed distribution g(x) can incur large average margin error for f(w,)) )) with high probability for random draw of w (w). We formalize this intuition as the following condition.
Under
and hence do not know
Condition 1. Given a classifier -(-,)), margin a, and true parameter w", a distribution Pleam [aaa (w) is t-defensible Vx E X, we have Pr (w) (wwll//wwwwww.... x) g(w", x 2 al Se
In other words, the above condition says that if Plearn (w) is t-defensible, there will not exist any x E X' such that g(w,x) significantly deviates from the ground-trus score g(w", xx) with large probability over Pleara (we)
3.2 QUERY PRIVACY
As discussed before, the attacker cannot find an attack distribution g a-priori to fool f(w,,) when Plearn (w) is t-defensible. strive for successful attacks, the attacker must then obtain more information about the specific w used by the defender through queries. Therefore, a successful defense strategy should not leak too much information through each query from the attacker. We formalize this intuition as follows.
Condition 2. A defense strategy in the allack-defense protocol is s-query private for any x E X have T(2; W x) S 8.
3.3 CERTIFYING THE DEFENSE STRATEGY
To satisfy this condition and prevent leakage of information on w, we take inspiration from differential privacy and perturb the scores with Gaussian noise. By adding the right amount of noise, we hope to hit the sweet spot where the accuracy clean input ~ p² (x) is mostly preserved, while at the same time the attacker obtains least information from queries. We use the following stochastic surrogate function f(..)) the key of our defense strategy.
f(w. x) g(w, x) (0)
As the first main result of our paper, the following theorem asserts that under the above two conditions no attacker has winning strategy using limited number of queries.
Theorem 1. Suppose Plearn (w) is t-defensible, and the defense strategy is s-private. Va > 0, 0 <
y, 8 1, for 72 I 3log2/8
a² there is no (2a, 7/, 25) winning strategy ifT < (1tt+ 8- log 2).
4

---

Under review as a conference paper at ICLR 2020
Note that in the definition above implicitly depends on r². Adding more noise (larger r2) reduces the amount of leaked information on w.
In practice, it can be hard to verify the defensibility of Plearn (w) or the query- of the defense strategy for complicated models. In the following, we show examples of simple models where these two conditions either strictly satisfied or asymptotically satisfied in the limit of infinite data. In the next section, we will first show that for logistic regression and kernel logistic regression models, the conditions hold asymptotically when the models are well-specified. After that, we show that the conditions can hold exactly for a simple naïve Bayes model. We leave the analysis of defensibility and quuryy-rrvace for more complicated models an open problem for future research.
3.4 ASYMPTOTIC ANALYSIS OF (KERNEL) LOGISTIC REGRESSION
We start by considering linear model g(w, x) (w, x), where (---) denotes the inner product Euclidean space. One common approach to learning this model is logistic regression. When the model is well-specified, i.e., there exists w such that p"(v x) I+expl-9(w p[w"xx)) x]) we can prove that Plearn converges in distribution to a Gaussian distribution with mean w as n + co. Specifically, we have the following lemma.
Lemma 1. Assume that |w"'l I X. Given i..dd samples {(x, k)) ~ p'(x)p" (y | x), the estimator Wn obtained by solving the following functionn
Y1
log(1 + (w.xi)))
max |
12
is consistent. Moreover,
Vn(Ww, w") $ N),,
where Σ 1allpyy=1xx// xx ply y x) x))xx!|))
The asymptotic Gaussianity of Plearn (w) greatly facilitates the investigation in its defensibility. However, the assumption that a linear model g(w, x) being well-specified is rather restrictive, We therefore additionally consider a generalization called kernel logistic regression, where g(w,x) (w, ((x)). Here o(x) is the natural basis vector of the Reproducing Kernel Hilbert Space H corresponding kernel k(;,,), and
(:-)) to denote the inner product in H. When the kernel universal (Micchelli et al., 2006), e.g., the Gaussian RBF kernel, functions in RKHS can approximate any bounded continuous function arbitrarily well w.r.t. the uniform norm. Therefore, it is a much milder assumption that there exists w E H such that p (y x) T-exp(- yyw" [x(")d(x)))
For kernel logistic regression, can similarly prove that Pieara (w) is asymptotically Gaussian (see Lemma 6 in the appendix), with asymptotic variance
Σ4 = (Ex (pv = x) - ply = & ((x)))
where @ denotes the tensor product.
For both logistic regression and kernel logistic regression, under the assumptions of well-specification and in the asymptotic regime, can prove both defensibility and query privacy. Formally,
Proposition For logistic regression, the asymptotic distribution of Piearn (w) æ| defensible and our defense strategy is distribution of Piearn (w) is 2
na²
[ query private. For kernel logistic regression, the asymptotic -query private.
2nT3
na²
defensible, and our defense is Faxlon
2ny
Therefore, our defense strategy is asymptotically certified for logistic regression and kernel logistic regression models.
3.5 NON-ASYMP VERIFICATION OF ASSUMPTIONS
Asymptotic conditions hold for sufficiently large training set size but to be fully verifiable need results that hold for finite n. These bounds are very difficult to obtain, and we show some bounds for very simple classifiers (naive Bayes).
5

---

Under review as a conference paper at ICLR 2020
Before showing the results for naive Bayes classifiers we first show defensibility of computing averages.
Proposition 2. Let p(x) be any distribution with covariance E. and w = pxxx) [x]. Xy Xi.'.
Let
na² p(x) and X, then the distribution of w is +2/3do defensible.
X,,
Note that the results of this theorem almost as good we knew the distribution p(x) is Gaussian (0, Σ). In that case, we can apply Proposition 1 and conclude that it is 2d]
no² defensible.
The following Corollary shows similar bound for naive Bayes classifier. This is direct outcome of the above proposition.
Corollary 1. Let pxlly = 0) and p(xly = 1) be distributions with covariance E, and w = Bpix/y=1) x] Pppxxy=0) [x] Let X1,"" ,x,,, p(xly 0) and " p(aly 1). If choose 1 Σ, x E. x4, then it is 4dl +4 44/3da defensible.
na²
Therefore, we can use the training data to upper bound non-asymptotic certificate of defensibly.
واح] (El Karoui et al., 2008) and obtain
For query privacy asymptotiiicc guarantees are casier to get. All we need is upper bounding the covariance spectral radius of Plearn (w).
Proposition 3. If g(w, x) = (w,x) and Pleara(w) has covariance E, it 27 query private.
d|
RATE ANALYSIS AND MINIMAX OPTIMALITY
To demonstrate more concrete asymptotic rates, we will analyze a simple setup. We study classifier with g(w, x) (w, x) and Plearn (w) ((w",, for some b (we need to fixed as we analyze the asymptotic rate when d + oo). ||w" Ioo <
((="" o² where o² 1/n. We also assume that
We give example of classifier where this distribution could arise in the appendix. Based this setup, we have the following specialization of Theorem 1.
Corollary 2. There is no (2a, 7, 252) winning strategy if T 2d log 2/8 + o(n) if we choose
n
a²
2 log 2/8-
This bound is desirable >>> dimensions).
1 (there a large margin) and n > d (more data than input
4.1 AN ATTACKER STRATEGY
Corollary is the minimum number queries any attacker strategy needs to win. Now we show concrete attacker strategy that (almost) achieves this lower bound.
The concrete attacker strategy is shown below. Intuitively, the attacker queries each the d dimen- sions of the input Rd to find out the sign of w w" The attacker finds x such that (x, w*) large but (x, w < O.
PROTOCOL. 2. THE SIGN ATTACK PROTOCOL.
1. Defender samples Pleam (w).
2. For round 1,.....
(a) Attacker chooses X, 6t mad where e; is the i-th basis vector for R2d
(b) Defender sends = (x,, w) + (00 r2) to attacker.
3. Attacker computes w, avg[ 2, X; = e.}. Without loss of generality (by re-indexing the dimensions) [w] wi]
ww", For I....., Ad choose x; -iinn (w]) and
for = Ad, ... d choose X; = sign W: w Attacker chooses the smallest À such that
(x, w") < She outputs a delta distribution on this x as his attack distribution.

---

20a Under review as a conference paper at ICLR 2020
Theorem 2. For any 0 7 < 1, 0, if d is sufficiently large, the attacker in Protocol 2 is d² and we choose 7² 2 2og. it is 20a*"²² in S 160a 160n2lng 2/g 2/a de
(a, 1, 2 winning strategy if
a²
(a, 2 winning strategy when T 20 if we choose 7² 72=00 =.
The extra condition n S 160a log 2/6 ensures that adversarial examples actually exist; if the classifier is sufficiently accurate (i.e. w w I a), then no example will be falsely classified.
de
4.2 RATE SUMMARY AND COMPARISON
Note that Corollary 2 is lower bound on required number of queries: attacker have high x'n²y success rate unless T 2dt log 2/8 while Theorem 2 an upper bound: with T = de there is at least one attacker that can achieve high success rate. The two bounds have the same asymptotic with respect to a, n and d, which shows that the bound is asymptotically optimal with respect these parameters.
To better study the asymptotic behavior for large and large n, we will choose a = Vd. For both methods (x)) (N)(()) can be arbitrarily small for sufficiently large This proved in the Appendix. We have the following rates for the smallest T such that an attacker can have (a, 1, -²²) winning strategy for any 0 and
vd. With this choice of a, T no longer depend d for both upper and lower bounds, and we can get:
For defended classifier with 7²
log 2/8 we have = O(n²) queries.
a²
For undefended classifier with 7² 0 we have T O(n).
EXPERIMENTS
5.1
LINEAR MODELS
We will first verify our method empirically on linear classification tasks. We will use two classification datasets.
Synthetic Gaussian. For this dataset we randomly sample w from a standard Gaussian, sample p(xly = 1) nt + (0, o² and p(x|y 0) -w- NO, 5²1) and finally clip to between [-,, We choose such that w" the optimal logistic regression weight for p(y|x) = I x))
Mnist. Because linear models cannot classify MNIST with high accuracy, we use deep network features (last layer of pretrained AlexNet) the input X' instead of the pixel space. We train with the entire dataset and use the resulting vector as w* (for the attacker).
Attack Methods. We will use two attacking method: the first one is the attack strategy of Protocol 2 (which we will denote the sign attack); the second one is Simba (Guo et al., 2019), a recently proposed black-box attacking algorithm with very good empirical performance.
Classifiers. We will use two classifiers, the naive Bayes classifier defined in Corollary 1 and logistic regression. For both classifiers we choose a such that the no-response rate on p" (x) (estimated using the validation dataset) is no more than 10%. We either choose 72 = 0 (undefended) or 72 2log 278 as in Theorem (defended) where 5 is chosen to be 5%.
o²
5.1.1 RESULTS
The results are shown in Figure 2. For defended classifier, the number of queries required for successful attack typically increases by order of magnitude. In addition, the effect on the clean data p" is almost negligible. Another interesting observation is that, the naive Bayes classifier actually performs much better in terms of adversarial robustness than logistic regression. We conjecture that this is because logistic regression has high parameter estimation variance tr (Co((w) compared to naive Bayes. This indicates that adversarial robustness has very different requirements compared to classification accuracy. Even though logistic regression usually performs better in classification unless the training data size is tiny (Ng & Jordan, 2002), its adversarial robustness is poor.
7

---

Under review as a conference paper at ICLR 2020
atack suicets 122
training set s220
rate
training sot size
13' number of etlacker queries
10
number of attecker queries
number of training samples
training size 158
trainine 528 1064
attack success rato
rate
defended rign
600
belrndd 18 asaiiracc
20 number of attecker cueries
12"
se"
207
number of attacker quories
rumber of trainin samples
trainng set size 4175
trairing set size = 328/8
arror on bast sat samples
attack succest rana
etock SUCUESS FO22
NC celended Undefoonee
edleced cag
15"
2ut of
number Of attacker queress
number of attacker queries
number of training samples
Figure 2: Success rate of attacker vs. number of queries on synthetic dataset and MNIST. Left to
right: Left and Middle: the number of attacker queries vs. attack success rate for different training
set sizes. Right: the no-answer (NR) and margin error (ME) on clean data x ~ p (z). Top to bottom:
Top:
naive Bayes classifier trained on synthetic Gaussian; Middle: naive Bayes classifier trained on MNIST; Bottom: logistic regression trained synthetic Gaussian. Logistic regression trained on MNIST fails to achieve robustness for the training set sizes we experimented (up 10k). For both cases, defended classifiers require orders of magnitude more queries for successful adversarial attack, while the adverse effect on clean data x ~ p" (x) is negligible.
5.2 DEEP MODELS
Our theoretical guarantees are far from effective for deep models. It is unlikely the analysis will be ef- fective for current network architectures, so special
architectures and analysis will be necessary for cer- tified defense under out framework. Nevertheless we perform simple experiments to empirically verify that our defense strategy can effectively protect our model against black box attack methods. The setup is identical to (Guo et al., 2019) on ImageNet, except add a threshold put sigmoid probabilities: no class has a predicted probability greater than the threshold a, the model answers "I don't 't know". Here we choose a 0.7.
Attack success
undefended ME
undefended defended ME defended NR
deep networks
the out-
500
1000
1500
2000
2500
3000
queries
Figure Success rate vs. number of queries for Simba attacker on Inception network. We adjust the threshold such that both methods have similar no response rate (NR) the clean data. The undefended network is signif- icantly more vulnerable attack.
The results are shown in Figure 3. Similar to linear models, defended models require orders of magni- tude more queries to attack. We hope these promising experimental performance will motivate further the- oretical analysis and empirical investigation.
6 DISCUSSION
In this paper we propose new type of adversarial defense guarantee, one based on the concept of defensibility and query privacy. We show theoretical guarantees for simple classifiers and good empirical performance for complex classifiers.
Several open questions remain to be answered. The first one to verify defensibility and query privacy for more complex classifiers. The second one is to design classifiers with better defensibility and query privacy properties. The third one is large scale empirical investigation of the defense strategy or similar defense strategies, i.e. studying the performance of adding noise different layers of deep neural network against a larger suite of black box attack algorithms. We hope our work can serve first step in this exciting direction of research.
8

---

Under review as a conference paper at ICLR 2020
REFERENCES
Anish Athalye, Nicholas Carlini, and David Wagner. Obfuscated gradients give a false sense of security: Circumventing defenses to adversarial examples. arXiv preprint arXiv:1802.0044 002000000000000. 2018.
Tom B Brown, Nicholas Carlini, Chiyuan Zhang, Catherine Olsson, Paul Christiano, and Ian Good- fellow. Unrestricted adversarial examples. arXiv preprint urXiv:180900835. 2018.
Jacob Buckman, Aurko Roy, Colin Raffel, and Ian Goodfellow. Thermometer encoding: One hot way to resist adversarial examples. In International Conference on Learning Representations, 2018.
URL aattps:///ppereeeeee net forumt
Nicholas Carlini and David Wagner. Towards evaluating the robustness of neural networks. In 2017
IEEE Symposium Security and Privacy (SP), pp. 39-57. IEEE, 2017.
Jeremy M Cohen, Elan Rosenfeld, and J Zico Kolter. Certified adversarial robustness via randomized smoothing. arXiv preprint arXiv: 02918, 2019.
Krishnamurthy Dvijotham, Robert Stanforth, Sven Gowal, Timothy A Mann, and Pushmeet Kohli. A dual approach to scalable verification of deep networks. In UAI, pp. 550-559, 2018.
Cynthia Dwork, Aaron Roth, al. The algorithmic foundations of differential privacy. Foundations and Trends 2 in Theoretical Computer Science, (1:4::111-07)) 2014.
Noureddine El Karoui al. Spectrum estimation for large dimensional covariance matrices using random matrix theory. The Annals of Statistics, 36(6))2757-2790 2008.
Chuan Guo, Jacob Gardner, Yurong You, Andrew Gordon Wilson, and Kilian Q Weinberger. Simple black-bor adversarial attacks. arXiv preprint arxiv:1905.07721, 2019.
Xingjun Ma, Bo Li, Yisen Wang, Sarah M Erfani, Sudanthi Wijewickrema, Grant Schoenebeck, Dawn Song, Michael E Houle, and James Bailey. Characterizing adversarial subspaces using local intrinsic dimensionality. arXiv preprini 1oX1::1801.02613, 2018.
Charles Micchelli, Yuesheng Xu, and Haizhang Zhang. Universal kernels. Journal of Machine Learning Research, 7(Dec))2611-26677 2006.
Andrew Y Ng and Michael I Jordan. On discriminative vs. generative classifiers: A comparison of logistic regression and naive bayes. In Advances in neural information processing systems, pp. 841-848, 2002.
Nicolas Papernot, Patrick McDaniel, Xi Wu, Somesh Jha, and Ananthram Swami. Distillation as defense to adversarial perturbations against deep neural networks. In 2016 IEEE Symposium on Securityy and Privacy (SP), pp. 582-592 IEEE, 2016.
Aditi Raghunathan, Jacob Steinhardt, and Perey Liang. Certified defenses against adversarial examples. In International Conference on Learning Representations, 2018. URL https:// openreview. net. fortt//frum?e/ (iwrrummdddBysoooo----
Yang Song, Taesup Kim, Sebastian Nowozin, Stefano Ermon, and Nate Kushman. Pixeldefend: Leveraging generative models understand and defend against adversarial examples. In Interna- tional Conference on Learning Representations, 2018a. URL https: / wwwppppeewwwwnneeeeeeeeeeee Forum?id=xJuyGaa
Yang Song, Rui Shu, Nate Kushman, and Stefano Ermon. Constructing unrestricted adversarial examples with generative models. In Advances Neural Information Processing Systems, pp. 5312-8323, 2018b.
Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties of neural networks. In International Conference on Learning Representations, 2014. URL http: /ttp///axvvvv//av/ org wtt/abs/////ooooooo//..///..seet 1312. 6199.
Eric Wong and Zico Kolter. Provable defenses against adversarial examples via the convex outer adversarial polytope. arXiv preprint arXiv: 2017.
Chaowei Xiao, Jun- Yan Zhu, Bo Li, Warren He, Mingyan Liu, and Dawn Song. Spatially transformed adversarial examples. arXiv preprint arXiv: 1801,0262,, 2018.

---

Under review as a conference paper at ICLR 2020
A APPENDIX
A.1 PROOFS RELATED TO THE LOWER BOUND OF T
Proof of Theorem I. If strategy is (2xx 7; 26) winning then with probability Y
Pr P x) g(w", x) + +NN(0, 2 2aj 2 28 ((x)
(3)
Because (g(w, g(w", x) + (V) S l9(w, g(w", x)1 (V(0, If Eq.(3) is true
one of the following must be true
Pr(l 7 al 28 8
(4)
Pr lrl,o(w,)) g(w", ,x) 2 al ((x)
2
(5)
For Eq.(4) we can bound by
PO( -2) (O,
< 2e 27
Therefore, (4) is false if the RHS is less than 8, which is when 72
o²
2og 278"
now we show the condition for (5) to be true. We first define the following notation.
X(w)= = [x: g (W, x) g g(w", x)1 2 a
(x) = {w (g(w, x) g(w www"xx" x)] 2 a}
Let q be any distribution on X. let ((w(w)) denote the probability mass assigns to X'ww..
The following lemma is needed.
Lemma 2. In out tttack-defenss protocol, if with probability at least 7, we have Pr[lg(w,x))
g(w", x)1 2 a] 6, then ((::01:)) 7(1 + log 6) log 2.
Therefore, if I(w: 01:)) < yt + log 5) - log Eq. (5) is false with at least y probability. If we additionally have the condition that the attack-defense protocol is s-private, by sequence of data processing inequalities, and by the fact that x, only depends on w through oue,, and yr only depends on x, and w, we have
I(w: = I(W; I(::
Brl, S I(w; + I(W::1/le (xT)
Σ I(w:y Ts
Therefore Eq. (5) false with at least v probability
T(y: w xx) S sT 7t + log 5) log2
which is equivalent T < (xt log log What remains prove Lemma 2, which we do below.
Proof of Lemma 2. By the condition of defensibility we have
E E (w) (W))( = E. (piean(() Byy(x) [T(x E X())) = Rx(x) [T(w E M(x))
= Eg(xe) Erown (w) [[(w E M M())) & Bepc))e--] e -t
We abbreviate E (w) by Ew. Define s(q: w) max(g(XX(w)) e then
=e Ew Ewls(g:w)) < Ew (w + Ew '1 < = -
In addition we have E. (Qw) (sq: w ))] = Eg [E (s(: w))ll S tt- Finally by Donsker-
Varadhan inequality.
E Eqgi w) [log s(q; w)] < ELL Q)))(()) + Ew log EQ( le lox stow)]
< I(g; w) log Ew Eggg)) [s(g:
< I(g: w) - + log
10

---

Under review as a conference paper at ICLR 2020
Suppose ò e- log ( 2 log d if and only if log s(q: w) 2 logô. In addition, because for all q and w, log s(g; w) 2 -t, so log s(q: w) + t is a non-negative random variable, and we can apply Markov inqquality get (where the probability and expectation are taken with respect to w ~ Plearn (w) and o ~ Q( w))
7 (r(a((X(w)) 5] = Pr [log ((X 2 log 6] = Pr[log s(;; w) 2 log 6]
= Pr[log (g; w) + + 2 log 8 + + Ellog (q; w) + t
[[; w) + log 2
log ō + t
log +t
Rearranging we get
Il: w) 2 7(1 + log 8) - log
Finally because g is function of o17,, we have by data processing I(w;o1:T) I(w; 2 >(1 + log 8) log 2
Proof of Corollary 2. First by Lemma 4 we know that Piearn (w) is -dffensiee and 2 query 20za
_²
private. We apply Theorem and choose 7² = 2 2og to conclude that there is no (2a, 7, 26) winning strategy if
2T² T T o²d 2220d + y 1og2]
( a²
a²n
( a²n
(? 2d
+ log 6 log
dlog 2/6
A.2 PROOFS RELATED TO THE SIGN ATTACK
Proof of Theorem 2. Under the distribution in Protocol 2, denote
* ($1,'.. ... xa)= = (sign [W] - wi), ... sign(Wa- - wā))
Also denote the probability of attacker producing x given forecaster choose w as q(x w). By observ- ing the protocol we know that this distribution is factorized, i.e. q(x w) g(8) w) -.- (Sa w). Also denote b' = sign(w (w- w") as the true sign of the error.
Step 1: We show that if q(>; = b9 w) 2 1/2 + B, r") is likely large
Lemma 3. Under the distribution defined in Protocol 2. suppose for all i we have g(x, = 6, w) 2
1/2 + B, then
V2
Pr (x,r")
3do 2 21 280d/a
Proof of Lemma 3. The proof idea is to first lower bound the expectation, then lower bound the deviation from the expectation.
# = [x) Σ E[xr;;] = Σ B| x; Pr = b;] E # by] Prix; * bjj
2v2
> Σ Blrr2 -)r (8) = - 2/ [11]
3do
Vx
Then because (x, r-* Σ, & where (x,r,, = 1, ... d} are independent mixtures of Gaussian. In addition R has a Gaussian tail
Pr[Kar 2 c) < Pr | 2 c) < A so it is o² 22/2-sub Gaussian. Combined we have (x, r") r² d /2-uub Gaussian. Therefore
24
Pr((X,r') cal <
2
11

---

Under review as a conference paper at ICLR 2020
If plug in 30 have
V2
Pr (x,r") S
3do v
S e
284
Step 2: Lower bound on q(8; = b w) The first step is to show that X; = b; with non-negligible
probability. Because W, w. (r) 7/T) and if -² 1 20
TVT
Pr[&: = b,] = Pr[ -//)) - (V((002))1 +
(6)
107
The proof of the above statement relies on the following Lemma
Lemma 4. Let x ~ NO0, a²), y (N(, be independent random variables, then if 2 2b, then
b - Pr(x I [ull S + xa.
10a
Proof of Lemma 4.
+ |
Pr[s S [y]] = By [Pr[x <
|bllv]] = Eyy
Because & is concave
[0, +00) we have
y
y
(0 + 1/2
1
bv 2
Eyy
En
E,I [vll
+
2
2
2Ta V
2
Ta
2
For lower bound we have for any u 2 O.
Ey
y
Ey [(lvvl s ub)
[8l s (ub/a) -1/2)
1/2 -
]
+ Ey, 1(1y)] > ub)
(x)
ub
ub
a
o ((ub/a) 1/2 By [1[[y]] S ub)lel
ub
According to Wikipedia for truncated Gaussians, we know that [yy[y/0 < / < ub] = b 6000
b(() 400 so
E, [L(bv] < ub) [y]] E,, [|alll/ ub] Pr[pe| < ub] (8) ((u) 2(2(u)) 4())
D(u) +00)
2b(((0) o(u))
26
(1 - - 2²/2 g(u)b
v 2m
In addition by the concavity of t on [0, +00) we have
ub
ub
ub
1
ub
ub
+
N
a
a a
a
a
Combining the above results we have
y
(ubb/a) 1/2 ( 2 + g(u)
ub
b
E
+
2
Now we can plug in numerical results. Let u 1, and if b/a S 1/2 we get the results in the Lemma.
Step 3: Bound the agreement between and x. note that x can have high value of (8, r*), but this is not useful unless in the final x outputted, a large proportion of the dimensions is equal to x. In other words, we need to show that À cannot be too large.
Lemma 5. In Protocol 2, Vs > bound on w*|
<
sv bdd with probability 1 - =s/22 where b an upper
12

---

Under review as a conference paper at ICLR 2020
To simplify analysis, will assume that d is large enough such that À $ 1/2 with probability 1 - 7/2.
Proof of Lemma 5. We know that ||w"]loo < and ||l|| d, then by Hölder inequality have
|| 1 (w" w*) ) S || I oo S bd.
For any choice of > because the distribution of Xxd:d do not depend on Wadst and by symmetry arguments x,, Äd, ... dd are i..d. Bernoulli distributions with zero mean, so they are 1/2
Sab-Gaassiin. We know that (Xxd:d: Wid.)) is Ei conclude for any
(w, 12
I bd sub-Gaussian. We can
2
2
2
Pr[(Xxd:d (idaa) 2 sVbdl se-
Because the assumption (without loss of generality) that /wil 2 |w5 2.. w we know that
[| 2 1/|w*||1 Xd, so (X1:ad, wixxa) -ilalallll < ddd, with probability least
1 1/
02/2
(x, w) (X1:Ad: Wixx)) + (Xxd:d, Wita) I -dd + sv
note that the algorithm will choose the smallest such that (x, w) < 0. In particular, it will not choose λ such that (x, w) < -b, so we have with probability at least 1 - /2 Ad 2 -b,
or < wvdd-h d
Step 4: Combining the Results. Finally are in position bound ME(x) and prove Theorem 2.
We know that Vi = -,.... Ad, the distribution of r, is independent of the choice of x,, (X1:td; Fisdd)
is E x²0² Ado sub-Gaussian so for any 0 we have
Pr[(Xindd: rixaa 8V <vdda e 2/2
By Lemma 3 we have
V2 B(1 A)do
Pr (Xxdid, Tdda) 2
V 301
2 21 21-228(1-A1d7)
Combined we have
V2 VT
Pr (x,r")
3(1 (ddo sV 2 1 2 21--28(1-)d//-- - -22/2
And if we plug in the above condition that À < 1/2 (which is true with probability - 7/2) we have
V2
Pr (x, (x,r') 2
3do
sv2da
2da
2 Bd/a -2/12
2
TvT By previous analysis we know 3 2 10r so we can choose a sufficiently large and given the choice of s we can choose sufficiently large such that
2 1 oVT
Pr (x,r")
do
2 7/2
2/ 10T
So if TVT do 2 we have 2 107
Pr [r((x,r") 2 al 2 2-
note that ME(x) = 1 whenever (x, r*) + N(00 72) 2 a. Because of the symmetry of the Gaussian
distribution, this happens with 1/2 probability if (x, r() a. Therefore we have
1
Pr(ME(x) 1] (1)))
2
We can rewrite the condition as
400ma?n272 400maan² 2n2
T
dc
64d2
13

---

Under review as a conference paper at ICLR 2020
In particular choose T
20a nn"
This is true if the condition if Lemma 4 is true. That is Such T could exist if
d²
T/VT 2 20, or T S 7² /402=
a'n
log 2/6
a²n 8 log 2/8
20a2n2
d2
d2
160 log 2/6
Conversely if = O, we have B|][r:][]]] = /2Ta when 7 we have (when d is sufficiently large)
In addition by Lemma 5 for large d, À - 0, so
v
To
To Vx
Pr
x
= Pr
||rrl| 2
- +do00 1
VT
We can similarly show that (r(ME((x) = 1] 2 [1 - ?) if To/Va 2 a, which becomes the
condition I' 2 VTayn. We choose T = 2a / to satisfy it.
A.3 PROOFS RELATED TO THE CONDITIONS
Proposition 4 (Representer Theorem with Hard Constraints). The optimal solution
log(1 e )(l
W/ arg |1,, 52
min
can be represented as where og is a function of (1,,, 1
Wn a1)(x,),
Proof of Proposition 4. We first make a critical observation that 1(x, y: w) = log(1 + (-w(w)(()))
is convex w.r.t. w. We can then the convex duality theory to obtain the following equivalent optimization problem.
max Σ log(1 e ((x,)()))))) + [[[[w]] - 22), 0.
Due to the traditional representer theorem, we know that w' = 1i=1 a saddle point of the max-min problem. This completes our proof.
=E (x(H)))(xx )x(x;), where (w", f²))
Proof of Proposition I. For logistic regression, first we observe that because ||x||oo S 1, it must be that ||x||2 S vd. Let Σ Q" AQ where Q is orthonomal and A is diagonal. Because Q is orthonormal, ||Qx||2 S Vd, then
x
Ex
<
sup vIl
Ag
sup 1 =d
Σ EARD' <
sup Ari Asi
Σ NN
= -1|A||2 d = 1|112 d
now we can bound defensibility by (x, w²) ~ NN T /n) and
Σx
< Pr N (0, |>ح| 2 <
no2
Pr
N
0,
> a
e शلo
We also bound mutual information by
I(2; w x) H((+x)
H H (. = H(N(0, x'xxXxXEXXXX +2)) ((N
1
x xTEx/I0 /n + 72
< 1
|E1| d
E| d
=
log
22
2
log
1
nr²
<
2nT²
14

---

Under review as a conference paper at ICLR 2020
We prove similar results for kernel logistic regression. note that Σ A-!, where
a Ep(x) pp = 1 x)p(y = -1 x))(x) & o(x) E H. @ H. We will first show that A is a bounded operator. This is because for all f E H. we have
|A = | = 1 x x)p
(f.
P
x)p(1 1 x))
< Elp(y = x)p(μ = -1 x) [[x(() [|/I]]
Elp(y x)p(y I
||fll
4
Equivalently, ||A I 1 Due to the Bounded Inverse Theorem, E = A-1 is also a bounded operator
and therefore [ xo. Therefore, for any x X,
(0(x), Ex(x)) < | [E S |E
As result,
Pr[N'(o, (6(x), Ex(x))) 2 and S Pr N (0, 1
2 a
e
2
n
The mutual information can be bounded by
T(2; w x) = H((xx) H(//w, x) = (O (0(x). [x(x))/n +2)) H(N(O, x2))
(Ø(x), Ex(x)) 72
|>
= 2
log
72
S 2
log
1+
nr²
2n
Proof of Proposition 2.
We know that for any Xo X
27
E[(xo, r) =
E
1
Σ (xo+ xi)
=
(xo, x:) (x0: xi))
2
112
E
(xus x2
+E
X x; x Xu
n12
n22
i
Ex(x0, x
1
Σ
x
E
xx
E[ [3}] TT Xg
E [ xx
xo]
1
xx
Exo
-
d
|>>|
n
n
inj
Because Bl(xo, r)] = O, Var r) = El(xo: r) v d |وااا by Bernstein incquality
Pr 2 a) Se 2
Proof of Proposition 3. Proof of this proposition utilizes the fact that Gaussian distributions have highest entropy among distributions with the same covariance. Let (we,x) -N(0, +?), because
Var = =x"'n T'' + 72 s dp(E) 72, (2)x)) & 1 log (dp(E) + 72).
dp(2i) +
dp(2))
[(z;w|z) = (2|æ)) H (( w)
< log
2
72
2,
15

---

Under review as a conference paper at ICLR 2020
Proof of Lemma 1. Let denote [(x,, y; w) log(1 + e -()(w)))). In order learn w, minimize the negative likelihood function P, y; w), and denote w, & arg min (x, y; w). We will first prove that Wn L w. As the first step, we prove the uniform law of large numbers of [(x, ys w). notice that
E sup
[Pa1 y3 w) - PI(x, 25 w|ll
[w]l
sup
[E v. w.) - (''(x',''s
sup
PP x, yj w) - ((x'v':w))
EI
sup
e(([xx. us: w) - 1xx 2/5 w²)
||
2
-
sup
(x y6: w)
11
||
4
4 E
E
sup
< xx)
supp
(w,
c2x,)
11
/|
m
||
(18) 8A
(éis)
8A
Σ 6
6
n
8A
vn'
where (i) is due the Ledoux- Seduux-Talagrand contraction theorem, (di) is due to Cauchy-Schwarz, and (iii) is due to Jensen's inequality. Using Markov's inequality, we can conclude that with probability 1 8,
8A
sup ||
[P y: w) - Pl(x, w)|
Vno"
Therefore, with probability 1 1- 8, Pl(x, Pl(x, yi w*) can be bounded
0 S Pl(x, wx) PI(x, y: w:)"
= =PI(x, yi w..) Prl(x, -
- P.l(x, Pa - Pl(x, My w*)
< 16A
Vnd
Furthermore, the smoothness of Pl(x, yi w) guarantees that when ||w,, - -w'll small enough,
Pl(x, w.) Pl(x, w*) = P y: w TW w*)
+ 2 (w, - TV2 w (w,, ww) + o(Ilw, w/ll)
Amin
|/ w'1l2
Amin (Cov (Col/VPl(xx y w || - - w=
where (i) is due to Bartlett's identity, and Amin denotes the smallest eigenvalue. Combining the fact
that Pl(x y; w.) 2, Pl(x. y: w*) and Pl(x, yi w..) Pl(x, y; w²) 2 O([w,, - w*ll²), we can conclude that with probability 1 5, there exists large enough such that Vn
I|w. w/
64A
A Cooo/VPl(xx w)))
and simple corollary,
W, B w
16

---

Under review as a conference paper at ICLR 2020
Because wn minimizes (x, y; w). we have that whenever l|w, -w < X, VP,, y; 0.
This equivalent to saying that /nVP,, yy; w.)) 2x O. Using Taylor expansion, we obtain VX,,(x yú wn) + P, w w")(w,,,, (wn, op ww) VP,,(x, yi w.) (
which is equivalent
(x,(PV"(xx w") + (P, - P)V yi w*) + (1))
Combining the central limit theorem and Slutsky's theorem, we have
CovlV/(( Vn(w,, w") E(0, "/ y:
Bartlett's identity asserts that [|V2[(x, y: w")] variance of Vn(Wa, - ww) can be simplified to
Cov/Vi(x, y w)) Therefore, the asymptotic
XXT
Σ a Cov|Vi(x, yi w -1==
(1 + co(w xx)2
xw)
-1
Ex
(1 + elw elw"xxj22 XXT
(Ex (1 Pw- )xxx)
where Pw
Lemma 6. Assume that there exists w E H such that p
p"(y (y x) I+expl- ceoxp(-v(ww v(w (bx)) Assume
further that [["]| S X, and Vx k(xx,) S 1. Suppose we are given dataser {(x;, y:) b= (dd. p" (x)pp" (y) x). Let Wn be the solution to the following objective
log(1 + =.(.
min |w
1=1
Then we have w. Pg w", and
Vn(wn. ww) NO.
where
En (Ex(ply x) ply 1 & o(x)))
Proof of Lemma 6. Let denote l(x, y: w) log(1 [ +e v/w. Ln(w)= E ((x,, y1i w). and L(w)= [E[((x, yr w)]. Now, we prove the uniform convergence of Ln to L. Denote B A
{w/ ||/l| < 22}, and consider the expected error
sup in (w) - L(w)] L
= E
sup [in(w) E(((x,(()))) yr w)]]
LEBB
E
sup
1xx;, w) - E
[(x 3/4 w)
WEB
< EE
sup
Gx|((; My w) - 1(x] v/: w)]
WEB
< 2F
sup
(x w)
wEB
2R (x, 8: w)
Now let X(w) A 1 EE e,1(x,, y:s w). note that 1(x, y: w) is a 1-Lipschitz function w.r.t. ((w,o(x) Using the Ledoux-Tii Ledoux-Tallarand contraction theorem, conclude that R( y; w)) S
17

---

Under review as a conference paper at ICLR 2020
(R(y(w, o(x))) which can be bounded by noticing that
R(y(w, (()))((()))))))))))))))))))))( = E
sup WEB
Gife (w (x:))
1=1
E
sup wEB
(w,
+x)10(xx))
18
[w]]]] 1llH
X2
n
IF
n1
VX2
E
k(xi, xs)
n
where we assume that k(x, x) 1, which is satisfied by many universal kernels, such as Gaussian RBF. Taken together, we have
[i, (w) I(W)]] 11
A -m
E
sup
LoEB
With Markov inequality, we have V5 > 0,
4
Pr[sup (w) I.(w)] 8)
wEB
The uniform convergence concludes that L(Wx) Dg L(w"). Using the same arguments as in the proof of Lemma conclude that w,. 3 w".
next, we prove the asymptotic normality of w.. First, we note that 1(x, y: w) is Fréchet differentiable w.r.t. w. This can be verified by the chain rule of Fréchet derivatives, because ((x, y; w) is Fréchet differentiable w.r.t. (w, d(x)), and (w, (xx)) is Fréchet differentiable w.r.t. w. Then, we need to focus on the differentiability of
V Vwl(x,y:w) = (
1 el((,((())
Let g(w) A Vwl(x, yi w): + H. We can further take the Gâteaux derivative g(w) to get dg(wo + 1(w wo)) e ww
(1 + (w wwwp:/owttwwwwwowot wo). (w Wo: (ox)))
dt
and even compute higher-order Gâteaux derivatives
dl gl (wo + t(w - wo)) (e//ott(w-wo).coo (( -1) (w wo, (
di2
+ +1)
Using fundamental theorem of calculus for Gâteaux derivatives, we obtain
f/¹ dg(wo + t(w - Wo))
g(w) = :((o)) +
dt
di
=g(wo)+ {"² dg(wo + 1(w wo))
(1 1" (oo(wo wo + +(( wo))
dt + Jo
dudv.
dt
dt2
1=0
1=w
18

---

Under review as a conference paper at ICLR 2020
note that
I.. J." g + -(o))
dudv
20 S
1
l| wo. (xx)) +)I| =[[lw--"I]) w'll,
dt2
t=
we have
e (x))
g(w) = I( (wo) +
(x) @ ((x)(w wo) + +p(()( - -wo)
(1 + ex(wo.d(x))
Using the same arguments as in the proof of Lemma 1, we can assert that g(wn) = opl (1) Now
we can expand f(w,). in the neighborhood of w to get VnPa V (x,(x, (1)
evlw",
=VnPa Vwl +
Pr ( culw (ww (x) 00 ((x) (x)) + +z((1)) (w ww)
VnPa V
eo(w" (6())
cvrl" xxx))
vn (1+ (0lewr (x) ((x) (Pn P)
(1 evrlwe -0x)) o(xxx + +2((1) (w (w- w*)
ell("" .0(x))
=VTPa (wl,,.)) +
(I ( x(x) & ((x) + tzp(1) (w w*),
where (i) is due to the law of large numbers. Because of Vx k(x.x) x) S 1, the (weak) law of large numbers and the central limit theorem still holds for random variables in H. For the former, we can prove using McDiarmid's inequality, symmetrization, and Jensen's inequality. For the latter, the proof is the same as the traditional proof of CLT using characteristic functions. Similarly, Slutsky's theorem still holds. As a result, the asymptotic distribution of vn(w, w") is again Gaussian, with mean O and variance
Σ = ([Ex(pw- (1 Pw }0(x) o(x)))
where
Pw
1 -we-(w".x(x))
A.3.1 ADDITIONAL. EXAMPLES AND PROOFS FOR SECTION 4
An example where Plearn (w)) N(ww,, , o²1) Let Bera(p) be the d dimensional Bernoulli distri- bution where each dimension independently takes 1 with probability y and -1 with probability p.
Let (xx be defined by p(v) Ber, (1 (1 and p(aly = 1) = (3/4(3/4) and p(al = 0) =
Bera(1/4). We choose w" = - 2 ... b)) and the ground truth score function is Iw- (x) = (I, w*).
We draw a dataset of size n from the distribution {01.81, 01. 1.....,,,,3 FT, 3n to learn w the algorithm
Σmnge x, Σumz=- x; Then by CLT we have Piearn (w) = -=w"","") simply takes the average Eng,z1
E.,
where x² = 3/4n. note that it is possible to obtain non-asympiotic results because w is actually distributed as a multinomial, but we will use the convenience of a Gaussian distribution.
Proof of no-response rate. When v and 0 we have
Pr [R(()) < Pr pr (x)
Pr [[(( w) s a s ([( d/2 vd
= Pr W (0, do s d/2 - vdl 7 0
Similarly for = Vd and a
2/0 we have
Pr [NR(=)) < Pr [2,,, w) +N(0 22) S al s Pr [(x,)*) + +N 5/2 s/22 vd
(x)
Pr N 0, 0.
2 2l0g
d
<d/2
Vd
78+0 0
19


Reviews:
[{"review_id": "r1guL36CFS", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Although this paper's title contains \"certified defense\" and \"unrestricted adversarial attack\",  what I believe this paper is doing is analyzing the query complexity of query-based black-box attacks under simple linear models such as logistic regressions (or kernelized versions). The authors considered a binary classifier with the additional capability of giving \"no response\" when the confidence is low.  In addition, the output of the classifier has to be perturbed by a random Gaussian vector. The authors then define several metrics including defensibility and query privacy to develop the query complexity on the considered model. The authors tested the query performance on two attacks: (1) the sign attack proposed by the authors and (2) the simba attack proposed by Guo et al. \n\nI have several concerns regarding this paper:\n\n1. In my perspective, the title is very misleading and does not properly justify the claims made in this paper. \"Certified defense\" usually refers to consistent top-1 prediction of a perturbed data sample under a defined threat model. The paper reads like the authors are actually certifying the defined defensibility metric but without a threat model to certify. In addition, the attack setting is limited to black-box attacks (i.e. zero-order adversary), whereas in certified defense the attack assumption is white-box. \n\n2. It is also very unclear how unrestricted attack plays a role in the studied problem.  In the introduction, the authors' definition of adversarial examples is \"any input is considered a valid adversarial example as long as it induces the classifier to predict a different label than an oracle classifier.\" But what is the oracle classifier? How do we justify the credibility of the \"adversarial examples\" in the experiments?\n\n3. Only two black-box attacks were compared in this paper, one is the sign attack proposed by the authors, the other is the simba attack proposed by Guo et al. To my knowledge, simba attack paper has not been published at any peer-reviewed venue. In other words, both attacks are not widely recognized attacks or methods from published papers. Therefore, the performance evaluation is not fully justified. Since there are many black-box attacks from published papers, why not do performance analysis on those attacks?\n\n4. Similar to 3, the classifier setting is also uncommon. Although I am happy to see classifiers have the ability to give no-response,  admittedly this type of classifier is rarely used in practice, not to mention the analysis is tied with Gaussian perturbation on the output. The technical contributions can be limited if the main contribution of this paper is characterizing the query complexity (or defensibility) of an uncommon classifier with Gaussian perturbation on the output. I believe providing more insights on how the analysis can be useful to mainstream classifiers are critical and necessary.\n\n***Post-rebuttal comments\nI thank the authors for the response. I hope the comments areuseful for preparing a future version of this work.\n***", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "HJemqGSatB", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors propose a new certified defense strategy that considers unrestricted black box attacks.  The paper provides bounds for the minimum number of queries needed for the attacker to attack the classifier successfully and then the authors prove that they can devise a defender to be robust against that attack. Here are a few points to consider:\n1.\tThe paper is a bit difficult to understand (also not well-structured). The specific contributions are not quite clear with respect to the existing literature (which is reviewed in a sparse manner in the paper). Especially, the novelty of the theory and analysis presented here is a bit difficult to assess. \n2.\t The results are not really validating the points they make in the analysis (for example in part 4.2 they talk about upper and lower bounds for number of queries as a function of τ, α, etc. but they never provide some plots or tables regarding that in the results section).\n4.\tAlso, in Fig 2, it is hard to grasp the performance of the defended vs undefended classifiers with respect to the lower and upper bound that they have computed theoretically in the previous section.\n5.\tThey emphasize on the “defensibility” and “query privacy” in the analysis but they do not provide anything in the results section considering them.\n6.\tAs this is primarily a theoretical paper, focusing on simple classifiers is probably okay, but some sort of empirical comparison with other certified defense strategies is necessary. Just claiming that none of the existing methods would work for unrestricted attacks will not work is not sufficient. Some empirical results to show the specific advantages (e.g., at what budget the existing methods start to fail and the proposed method continues to perform well). ", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "BJxBz-t7cH", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper proposes adding noise to the output of scoring function to defend from black-box attacks. This topic is actually very interesting so I enjoyed reading the paper, although it is currently only working for logistic regression and Naive Bayes and there are several unclear parts. I have several concerns about this paper, especially the claim of robust towards arbitrary perturbation. \n\n- My main concern is about the assumption of the attacker. Based on the discussions in Section 3, it seems the authors assume that the query complexity of attacker relies on how many queries the attacker needs to recover a w that is close enough to w*. I don't think this is the correct assumption for the current attacks --- given an example, black box attacks are trying to find some x' for each x without trying to recover  or even estimate w. Therefore I wonder why the query complexity can be linked to the complexity of estimating w and is there any further assumption you need to make? \n\nIf the goal is to protect w, then this has been studied in several privacy/security papers and it's a different topic from adversarial attack. So the connection here is important but somehow unclear in the current draft. \n\n- For the experiments, to justify it is robust to attack I think it's important to try on various black-box attacks, including ZOO (Chen et al., 2017), Natural evolution strategy (Ilyas et al., 2018), Nattack (Li et al, 2019). For decision-based black box settings Boundary attack (Brendel et al., 2018) and OPT-attack (Cheng et al., 2019). \n(Not saying you should try all of them, but I feel more than 1 attack is needed to justify the claim). \n\n- Some unclear points that need further clarification: \n\nI feel assuming there's an optimal w* that correctly classifies data is unrealistic. Is is possible to relax this? \n\nCondition 1: I fail to understand how is this related to q (attacker)? This seems only guaranteeing there's a majority mass of w centered at w*. \n\nCondition 2: What is I ? (I didn't see the definition). \n\n- Some related work: \nIn DNN defense there are some related work on adding random noise. In [1], I think they only require adding a random layer which can be in the final layer of network, corresponding to adding random to the scoring function. In [2], they assume adding randomness to each layer so only adding random to final layer is a special case of that. I know the guarantees here are very different from those papers, but it will be nice to have some discussions. \n\n[1] \"Certified Robustness to Adversarial Examples with Differential Privacy\" Lecuyer et al., (S&P'19)\n[2] \"Towards Robust Neural Networks via Random Self-ensemble\" Liu et al., (ECCV '18)\n\n======\n\nThank you for the response and the additional experiments. I feel the paper has some interesting ideas and could be improved by a more careful writing and slightly adjusting the claim. I will rate the current draft borderline but slightly leaning to reject. ", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a certified defense under the more general threat model beyond additive perturbation. The proposed defense method is based on adding noise to the classifier's outputs to limit the attacker's knowledge about the parameters, which is similar to differential privacy mechanism. The authors proved the query complexity for any attacker to generate a successful adversarial attack. The main objection of this work is (1) the assumption of the attacker and the definition of the query complexity (to recover the optimal classifier rather than generating an adversarial example successfully) is uncommon, (2) the claim is misleading, and (3) the experimental evaluation is not sufficient (only two attacks are evaluated). The authors only provided a brief response to address the reviewers’ comments/questions without submitting a revision. Unfortunately none of the reviewer is in support of this paper even after author response.

Decision: Reject