Countering the Attack-Defense Complexity Gap for Robust Classifiers
Authors: Samuele Marro
Michele Lombardi
Venue: Submitted to ICLR 2023 (2023)
Keywords: adversarial attacks
adversarial robustness
computational complexity
dataset

Abstract: We consider the decision version of defending and attacking Machine Learning classifiers. We provide a rationale for the well-known difficulties in building robust models: in particular we prove that, under broad assumptions, attacking a polynomial-time classifier is $NP$-complete, while training a polynomial-time model that is robust on even a single input is $\Sigma_2^P$-complete. We also provide more general bounds for non-polynomial classifiers. We then show how such a complexity gap can be sidestepped by introducing Counter-Attack (CA), a system that computes on-the-fly robustness certificates for a given input up to an arbitrary distance bound $\varepsilon$. We also prove that, even when attacked with perturbations of magnitude $\varepsilon^\prime > \varepsilon$, CA still provides computational robustness: specifically, while computing a certificate is $NP$-complete, attacking the system beyond its intended robustness is $\Sigma_2^P$-complete. Since the exact form of CA can still be computationally expensive, we introduce a relaxation of this method, which we empirically show to be reliable at identifying non-robust inputs. As part of our work, we introduce UG100, a new dataset obtained by applying a provably optimal attack to six limited-scale networks (three for MNIST and three for CIFAR10), each trained in three different manners.

Under review as a conference paper at ICLR 2023
COUNTERING THE ATTACK-DEFENSE COMPLEXITY GAP FOR ROBUST CLASSIFIERS
Anonymous authors Paper under double-blind review
ABSTRACT
We consider the decision version of defending and attacking Machine Learning classifiers. We provide a rationale for known difficulties building robust models by proving that, under broad assumptions, attacking polynomial-timm classifier is N P-complete in the worst case; conversely, training a polynomial-tin is robust on even a single input is Σg ccomllete, barring collapse of the Polynomial Hierarchy. We also provide more general bounds for pol-polyoomial classifiers. We point out an alternative take on adversarial defenses that can sidestep such a complexity gap, by introducing Counter-Attack (CA), system that computes on-the-fly robustness certificates for a given input up an arbitrary distance bound e. Finally, we empirically investigate how heuristic attacks approximate the true decision boundary distance, which has implications for heuristic version CA. As part of our work, we introduce UG100, dataset obtained by applying both heuristic and provably optimal attacks to limited-scale networks for MNIST and for CIFAR1O. We hope our contributions can provide guidance for future research.
model that
INTRODUCTION
Adversarial attacks, i.c. algorithms designed to fool machine learning models, represent a significant threat to the applicability of such models in real-world contexts (Brendel et 2019 Brown et al.
2017: Wu et al. 2020). Despite years of research effort, countermeasures (i.e. "defenses" to adversarial attacks are trequently fooled by applying small tweaks to existing techniques (Carlini
Wagner 2016 2017a Croce et al. 2022
He et al. 2017 Hosseini et al. 2019 Tramer et al. 2020).
We argue that this pattern is due to differences between the fundamental mathematical problems that defenses and attacks need to tackle. Specifically, we prove that while attacking a polynomial-time classifier is N P-complete in the worst case, training a polynomial-timg even on single input is ΣX -complete. We also provide more general bounds for non-polynomial classifiers, showing that a A-time classifier can be attacked in NA time. We then give an informal intuition for our theoretical results, which also applies to heuristic attacks and defenses. Our result highlights that, unless the Polynomial Hierarchy collapses, there exists a potential, structural, difficulty for defense approaches that focus on building robust classifiers at training time.
model that is robust
We then show that the asymmetry can be sidestepped by an alternative perspective on adversarial defenses, As an exemplification, we introduce new technique, named Counter-Attacl (CA) that, instead of training robust model, evaluates robstness on the fly for a specific input by running an adversarial attack. This simple approach, while very simple, provides robustness guarantees against perturbations of an arbitrary magnitude E. Additionally, we prove that while generating certificate P-complete in the worst case, attacking CA using perturbations of magnitude > is Eh -complete, which represents a form of computational robustness weaker than the one by (Garg et al. 2020), holding under much more general assumptions. CA can be applied in any setting where least untargeted attack is known, while also allowing to capitalize future algorithmic improvements: as adversarial attacks become stronger, so does CA.
Finally, we investigate the empirical performance of approximate version of CA where heuristic attack is used instead of an exact one. This version achieves reduced computational time, at the cost of providing only approximate guarantees. We found heuristic attacks to be high-quality approximators for exact decision boundary distances, in experiments over a subsample of MNIST and CIFAR 10 and small-scale Neural Networks. In particular, a pool of seven heuristic attacks

---

Under review as a conference paper at ICLR 2023
provided accurate (average over-estimate between 2.04% and 4.65%) and predictable (average R > 0.99) approximation of the true optimum. We compiled our benchmarks and generated adversarial examples (both exact and heuristic) in new dataset, named UG100, and made it publicly available" Overall, we hope our contributions can support future research by highlighting potential structural challenges, pointing out key sources of complexity, inspiring research on heuristics and tractable classes, and suggesting alternative perspectives on how to build robust classifiers.
RELATED WORK
2013 followed by (Hein & Robustness bounds for NNs were first provided in (Szegedy et al.
Andriushchenko 2017) and (Weng et al., 2018b). One major breakthrough was the introduction of automatic verification tools, such as the Reluplex solver (Katz et al. work also showed that proving properties of ReLU network is cPmcleeeeee. Researchers tried to address this issue by working in three directions. The first is building more efficient solvers based on alternative formulations (Dvijotham et al., 2018 Singh et al.] 2018: Tjeng et al.) 2019). The second involves training models that can be verified with less computational effort (Leino et al.) 2021 Xiao et al. 2019) or provide inherent robustness bounds (Sinha et al. 2018). The third focuses on guaranteeing robustness under specific threat models (Han al. 1021) or input distribution assumptions (Dan et al. 2020; Sinha et al., 2018). Since all these approaches have limitations that reduce their applicability (Silva & Najafirad, 2020), heuristic defenses tend to be more common in practice. Exact approaches can also be used to compute provably optimal adversarial examples (Carlini al. 2017 Tjeng et al. 2019), although generating them requires a non-trivial amount of computational resources. Refer to Appendix M for a more in-depth overview of certified defenses.
2017). However, the same
Another line of research has focused on understanding the nature of robustness and adversarial attacks. Frameworks such as (Dreossi et al., 2019), (Pinot et al. 2019) and (Pydi & Jog] 2021) focused on formalizing the concept of adversarial robustness. Some studies have highlighted trade-offs between robustness (under specific definitions) and properties such as accuracy (Dobriban et al., 2020 Zhang jt al. 2019), generalization (Min et al. (202T) and invariance Tramer et al.] (2020). However, some of these results have been recently questioned, suggesting that these trade-offs might not be inherent in considered approaches (Yang et al., 2020 Zhang et al.) 2020). Adversarial attacks have also been studied from the point of View of Bayesian learning to derive robustness bounds and provide insight into the role of uncertainty (Rawat et al. 2017 Richardson & Weiss 2021; Vidot et al.) 2021).
Adversarial attacks have also been studied in the context of game theory (Ren et al. (2021). identifying Nash equilibria between attacker and defender (Pal & Vidal Zhou et al. 2019).
Finally, some works have also focused the computational complexity of specific adversarial attacks and defenses. In particular, Mahloujifar & Mahmoody (2019) showed that there exist exact polynomial-time attacks against classifiers trained on product distributions. Similarly, Awasthi let al. (219)) showed that for degree-2 polynomial threshold functions there exists a polynomial- algorithm that either proves that the model is robust or finds an adversarial example. Other works have also provided hardness results; Degwekar et al. (2019) showed that there exist certain classification tasks such that learning a robust model is as hard as solving the Learning Parity with Noise problem (which is N P-hardd); [Song et al. (2021) showed that learning single periodic neuron over noisy isotropic Gaussian distributions in polynomial time would imply that the Shortest Vector Problem (conjectured to be N P-hard) can be solved in polynomial time. Finally, Garg et al. (2020) showed that, by requiring attackers to provide a valid cryptographic signature for inputs, it is possible to prevent attacks with limited computational resources from fooling the model in polynomial time.
3 BACKGROUND AND FORMALIZATION
Extensive literature in the field of adversarial attacks suggests that generating adversaria examples is comparatively easier than building robust classifiers (Carlini & Wagner 2016 201 7 Croce et al..
2022: He et al. 2017 Hosseini et al. 2019 Tramer al. 2020). In this section, we introduce some key definitions that we will employ to provide a theoretically grounded, potential, motivation for such
All our code, datasets, pretrained weights and results are available anonymously under MIT license http://aayyyymmaaaopp...eeeeeeee
2

---

Under review as a conference paper at ICLR 2023
discrepancy. We aim at capturing the key traits shared by most of the literature on adversarial attacks, so as to identify properties that are valid under broad assumptions.
We start by defining the concept of adversarial example, which intuitively represents modification of a legitimate input that is so limited as to be inconsequential from a practical perspective, but classified erroneously by target model. Formally, let X (1...., N) be discrete classifier. Let B, E) = {x's E -| x' z'Ilp S }} be a L ball of radius e and center æ. Then we have:
Definition 1 (Adversarial Example). Given an input æ, a threshold e, and a L norn
? an adversarial example is input x' (2) such that f f(x) C(æ),, where C(x) C (1....,N) \ {f(z)).
This definition is simplification compared to human perception, but it is adequate for a sufficiently small e, and is adopted in most of the relevant literature. An adversarial attack can then be viewed as an optimization procedure that attempts to find an adversarial example. We define an adversarial attack for a classifier f as a function af.p X X that solves the following optimization problem:
arg migmin fI - =lpp f(x') E C(z)}
x'EX
The attack is considered successful if the returned solution x' = (x)) also satisfies ||z' =llp faa'-xllz S c. We say that an attack is exact it solves Equation (T) to optimality; otherwise, we say that the attack is heuristic. An attack is said to be targeted if C(z)= (zx) = {8'} with o' + f(z); it is instead untargeted if Ca( = {I, NJ \ {.))). We define the decision boundary distance (x)) of given input æ as the minimum I, distance between x and another input x' such that f(x)) # fxx').
Note that this is also the value of (xxx - x IlIp for an exact, untargeted, attack.
Intuitively, a classifier is robust w.r.. an example x iff æ cannot be successfully attacked. Formally: Definition 2 ((s, Local Robustness). A discrete classifier f is (c, p)-locally robust w.r.t example I E X iff Va' E (x) we have f(x')= = f(x).
We then provide some additional definitions that are needed for our results, namely ReLU networks and FSFP spaces. ReLU networks are defined as follows:
Definition 3 (ReLU network). A ReLU network is composition of sum, multiplication by a constant,
and ReI.U activation, where ReLU TR. + B is defined as (eI = mar( 0)-
Note that any hardness result for ReLU classifiers also applies to the more general class of classifiers. Fixed-Size Fixed-Precision (FSFP) spaces, on the other hand, capture two common assumptions about real-world input spaces: all inputs can be represented with the same number of bits and there exists a positive minorant of the distance between inputs.
Definition 4 (Fixed-Size Sixed-Precisionn space). Given real p > O, a space X C is FSFP if there exists a E IR such that Vx. /xx||(aa') [r(x)) S v (where (r(x)] is the size of the representation of x))
and there exists a J E TR. such that μ > 0 and Vaz x! E X. (I|=' x ==1pp < 1 - x x').
Examples of FSFP spaces include most image encodings, as well as 32-bit and 64 IEE754 tensors. Examples of non-FSFP spaces include the set of all rational numbers in an interval. Similarly to ReLU networks, hardness results for FSFP spaces also apply to more general spaces.
4 AN ASYMMETRICAL SETTING
In this section, we provide a theoretically sound result that is a viable explanation for why attacks seem to outperform defenses. The core of our analysis is proving that attacks are less computationally expensive than defenses in the worst case, unless the Polynomial Hierarchy collapses. Specifically, we prove that the decision version of attacking a ReLU classifier is N Poocopllte
Theorem F (Untargeted L attacks against ReLU classifiers are NP PCoomplltte). Let U-ATT, be the set of all uples (xz, E, f) such that:
Ex' E B,(a,))){(z)) ((x)
where x E X, X a FSFP space and f is a ReLU classifier. Then U-ATT is N P-complete.
We use the term "norm" for 0 < < < 1 even if in such cases the I." function is not subadditive. 'The proofs of all our theorems and corollaries can be found in the appendices.
3

---

Under review as a conference paper at ICLR 2023
Corollary 1.1. For every 0 < p 0G, U-ATT, is N--NNNP-opoii -ccolpeeee
Corollary 1.2. Targeted L attacks (for 0 < p S x)) against ReLU classifiers are N P-complete. Corollary 1.3. Theorem 7 holds even if we consider the more general set of polynomial time classifiers w.r.t the size of the tuple.
Theorem I rrepessents a minor generalization of existing results in the literature (Katz et al. 2017) However, together with the following more general bound for non con-polynomill-tinn -imee classifiers, it lays the groundwork for our main result.
Theorem 2. Let A be a complexity class, let f be a classifier, let Z ((xx y= f(z), x E X and let U-ATT,(f)) without the ReLU classifier restriction. If y A, then for every < S 0o, U-ATT,() E NPA Corollary 2.1. For every 0 < p p 0c, if y E En, then U-ATT, (f) E
where U-ATT;, is the same as U-ATT, but (xx,,,)) E U-ATT; 9- f}, f}.,
The latter result implies that, if 2, E P. then (-ATT,(f) E NP. Informally, Corollary 2.1 establishes that, under broad assumptions, evaluating and attacking a classifier are in complexity classes that are strongly conjectured to be distinct, with the attack problem being the harder one.
The decision version of training robust model is even more complex (again in the worst case): Theorem 3 (Finding set of parameters that make ReLU network (c. p)-lccllly robust input is En complete). Let PL-ROB, be the set of tuples & v) such that:
30'. (vy(0') =1 = Vx' E (B,(x,)).fo (e) (x))
(3)
where x E X,, X is a FSFP space and uf a polynomial-tine function that is 1 iff the input is valid parameter set for f. Then PL-ROB Σ. -complete.
Corollary 3.1. PI.ROB,, is EJ ccomleete for all 0 < 5 cc.
Corollary 3.2. Theorem hoodss set of polynomial-time classifiers w.r.t. the size of the tuple.
holds even if. instead of ReLU classifiers, we consider the more general
Our results rely on worst-case constructions and assume that the Polynomial Hierarchy does not collapse; moreover, both NP and Σg can be solved via super-polynomial algorithms. That said, we believe our theorems to have strong practical relevance. First, the Polynomial Hierarchy collapse is strongly conjectured to be false; second, even super-polynomial algorithms can have dramatically different run times (e.g. SAT vs Quantified Boolean Formula solvers). Finally, generic classifiers can learn (and are known learn) complex input-output mappings with many local optima. Intuitively, this is the core of the scenario captured by our worst-case construction, and also what makes Equation (1) difficult to solve. Again intuitively, robustness requires solving nested optimization problem with universal quantification (since we need to guarantee the same prediction on all neighboring points), thus motivating the higher complexity class. For this reason, we think our results provide plausible explanation for the hardness gap that is routinely observed in the relevant literature. Of course, there are definitely sub-cases where the problem is simple enough for exact attacks to run in polynomial time (e.g. (Awasthi et al. 2019);; this suggests that, under specific circumstances, guaranteed robustness could be achieved at reasonable effort. By this argument, our proof also provides additional motivation for research on tractable classes of robust classifiers.
Additional Sources of Asymmetry There are additional, complementary. factors that may provide an advantage to the attacker. We review them informally, since they can support efforts to build more robust defenses. First, the attacker can gather information about the target model, e.g. by using genuine queries (Papernot et al., 2017), while the defender has such advantage. As a result, the defender often needs to either make assumptions about adversarial examples (Hendrycks & Gimpel 2017 Roth al., 2019) or train models identify common properties (Feinman et al.) 2017 Grosse et al. 2017). These assumptions can be exploited, such as in the case of Carlini & Wagner (2017a).
who generated adversarial examples that did not have the expected properties.Secon, Second, the attacker can focus on one input at the time, while the defender has to guarantee robustness on large subset of the input space. This weakness can be exploited: for example, MagNet (Meng & Chen 2017) relies on model of the entire genuine distribution, which can be sometimes inaccurate. Carlini & Wagner (2017b) broke MagNet by searching for examples that were both classified differently and mistakenly considered genuine. Finally, defenses cannot significantly compromise the accuracy of a model. Adversarial training, for example, often reduces the clean accuracy of the model (Madry et al. 2018), leading to trade-off between accuracy and robustness.
4

---

Under review as a conference paper at ICLR 2023
5 SIDE-STEPPING THE COMPUTATIONAL ASYMMETRY
The limitations imposed by Theorem cannot be addressed directly in the general case (barring collapse of the Polynomial Hierarchy). However, they be sidestepped by changing perspective: we exemplify this by introducing an alternative approach to provide robust classification, which also allows us take advantage of existing defenses. Instead of obtaining a robust model from scratch, we propose to evaluate the robustness of the classifier on a case-by-case basis, flagging the input if a robust answer cannot be provided. Specifically, given a norm-order p and threshold E, we propose to:
Design model that is as robust as possible using available and practically viable defenses; For every input received, determine if the model is (e, (e.cally robust on the input by running an adversarial attack on the input;
If the attack succeeds, flag the input.
We name this technique Counter-Artack (CA), Instead of attempting to build robust model, CA ensures that answers from a partially robust model are flagged as unreliable when they could be the result of an attack. This approach, while very simple, can take advantage of existing defenses, provides robustness guarantees, and considerably hard fool, as we will later prove.
The behavior in case input is flagged depends on the context. Examples include relying slower but more robust model (e.g. a human), or rejecting the input altogether. This kind of approach is viable in all cases where the goal is to support (rather than replace) human decision-making.
Note that the flagging rate of CA is heavily dependent on the robustness the model: model that robust on the entire input distribution will have flagging rate of zero. Therefore, any improvement in the field of adversarial defenses also decreases the flagging rate of CA. Moreover, if there are known robustness bounds, they can be exploited to simplify the attack: for example, if the model is known to be (Ecert, poobutt on æ, with Eeett < E, the attack can focus on searching adversarial examples in (x, s) \ (x ceert). At the same time, developing stronger and faster attacks also benefits CA, since better attacks can find adversarial examples more quickly.
The major drawback of CA is that it requires running exact adversarial attack every input. We will investigate a possible mitigation for this phenomenon based on employing heuristic attacks, which still provide significant degree of robustness (see Section (6). Finally, we stress that CA is just one of potentially several alternative paradigms that could circumvent the computational asymmetry. We hope our contribution will encourage other researchers to investigate this direction.
5.1 FORMAL PROPERTIES
When used with exact attack, CA provides formal robustness guarantees for arbitrary p and Theorem 4. Let < p S do and let E > O. Let f. X- {I.....N] .N y be a classifier and let a be an
exact attack. Let S8 X (I,..., N} (*) be defined as:
[Ca(w) = f(xx) (1),,(x) - æ1lp
(4)
otherwise
Then Vx X an LP attack on with radius greater than equal to and with & fails.
The notation (z) refers to the classifier f combined with CA, relying on attack a. The condition & C(x) requires that the input generated by the attack should not be flagged by CA.
Corollary 4.1. Let 1 I p S oo and let E > O. Let f be classifier on inputs with n elements that uses CA with norm p and radius e. Then for all inputs and for all S r < p, L' attacks of radius greater than equal and with and * & C(x) will fail. Similarly, for all inputs and for all > p. L" attacks of radius greater than or equal n² - -e and with * & C(ax) will fail (treating x0 as 0).
Since the only expensive step in CA consists in applying adversarial attack to an input, the complexity is the same as that of a regular attack. CA can therefore represent a more feasible task compared to training robust model.
Attacking with a Higher Radius In addition to robustness guarantees for a chosen e, CA provides form of computational robustness even beyond its intended radius. To prove this statement, we first.
5

---

Under review as a conference paper at ICLR 2023
formalize the task of attacking CA (referred to Counter-CA, CCA) involves finding, given a starting point æ, an input x' E Bp(x,E) E') that is adversarial but not flagged by CA, ie. such that f(x') E ((x) A Vx" E (f)=(,))f(x=)) f(z'). Note that. for e' E, no solution exists, since x E Bp(x', ,e) and (() + f(r').
Theorem 5 (Attacking CA with a higher radius is Σς complete), Let CCAp be the set of all tuples (a, f) such that:
3x' By(a, E C(x) AY=" e Bpla' ())f(") f(x'))
(5)
where x E X, X FSFP space, e' >E,, e, & C()) f is ReLU classifier and whether an output is in C(x") ) for some x² can be decided in polynomial time. Then CCA is E2 -complete.
Corollary 5.1. CCA, is Eh -complete for all 0 < S xc.
Corollary 5.2. Theorem 5 holds even if. instead of Rel.U classifiers, we consider the more general set of polynomial classifiers w.r.t. the size of the tuple.
In other words, under our assumptions, fooling CA is harder than running it. This phenomenon represents form of computational robustness, a term introduced by Garg et al. (2020) in a very different setting where genuine examples can be cryptographically signed. Corollary 2. also implies that, unless the Polynomial Hierarchy collapses, it is impossible to obtain a better gap between running the model and attacking (e.g. P-time model that is 2 -hard to attack). Note that while Theorem 5 shows that fooling CA is Σ/ coomllete in general, attacking can be expected to be easy in practice when e' > E: this is however very extreme case, where the threshold may have been poorly chosen or the adversarial examples might be visually distinguishable from genuine examples.
5.2 USING HEURISTIC ATTACKS WITH CA
CA in its exact form has limited scalability due to Theorem T This could be addressed by using approaches with guaranteed bounds, as suggested in Section [5] by simply relying heuristic attacks. In this second scenario, to compensate for the heuristic nature of the employed attacks, can flag the input æ' if the attack fails find an adversarial example in radius of e + b(a),, where 6 X + _ is a buffer model. The idea behind b is that if heuristic attack can identify an adversarial example within a radius of + b(x'), an exact attack would be able to find an adversarial example within radius e.
The effectiveness of this approach depends on how well heuristic attacks approximate the decision boundary distance, which is an interesting topic for investigation by itself. Note that consistency of the estimation is in fact more important than its accuracy: if a heuristic attack overestimates (a())) in predictable manner, we train buffer model accurately correct the error.
With this approach, if the heuristic attack finds an adversarial example with distance less than E, we can confidently flag the input (i.e. false positives are guaranteed be impossible). However, if the distance is above e, it is possible to have a false negative. Note that using approaches with guaranteed bounds would lead to complementary situation.
Fooling the Heuristic Attack- Based CA The fact that the heuristic relaxation of CA can over- estimate the decision boundary distance means that it is possible to generate ad examples with 5' < E. Specifically, if an adversarial example ad for an input æ is such that (add S and fdvd # f(x) but [|a,,((=ddr) - > E + b(x CA will incorrectly accept add However, there are several informal considerations suggesting that fooling CA might be harder than running it. Such considerations are backed by empirical evidence in Section O First, both CA and CCA need to attack the same model, but CCA has at most as much information regarding the target model as CA, thus making the attacker at most as sample efficient as the defender. Second, fooling CA involves solving a nested optimization problem, while CA only needs to solve one; specifically, verifying the feasibility of CCA solution involves running CA on the solution. Finally, as better attacks are developed the chances of CA being fooled become slimmer, since these attacks will be less likely to find sub-optimal adversarial examples.

---

Under review as a conference paper at ICLR 2023
6 EMPIRICAL INVESTIGATION OF HEURISTIC ATTACKS
Section 5.2 introduced the problem of investigating how accurately heuristic attacks can approximate the true decision boundary distance, which is needed for the heuristic version of CA to work, but also an interesting topic per se. In this section, we test whether ||æ ævIlp. where 24 is an adversarial example found by heuristic attack, is predictably close to the true decision boundary distance (i.e. oz (z)). Consistently with Athalye et al. (2018) and Weng et al. (2018a), we focus on the 7 norm. Additionally, we focus pools of heuristic attacks. The underlynn ying rationale is that different adversarial attacks should be able to cover for their reciprocal blind spots, providing a more reliable estimate. Since this evaluation is empirical, it requires sampling from chosen distribution, in our case specific classifiers and the MNIST (LeCun et al., 1998) and CIFARIO (Krizhevsky et al., 2009) datasets. This means that the results are not guaranteed for other distributions, or for other defended models: studying how adversarial attacks fare in these cases is an important topic for future work.
Experimental Setup We randomly selected ~2.3k samples each from the test set of two datasets, MNIST and CIFAR10. 10. We used three architectures per dataset (named A, B and C), each trained in three settings, namely standard training, PGD adversarial training (Madry et al., 2018) and PGD adversarial training with ReLU loss and pruning (Xiao et al. 2019) (from now on referred to as ReLU training), for a total of nine configurations per dataset. Since our analysis requires computing exact decision boundary distances, and size and depth both have strong adverse impact on solver times, we used small and relatively shallow networks with parameters between -2k and -80k. Note that using (more scalable) NN verification approaches that can provide bounds without tightness guarantees not an option, as they would prevent us from drawing any firm conclusion. For this reason, the natural accuracies for standard training are significantly below the state of the art (89.63% 95.87% on MNIST and 47.85% 55.81 1 on CIFAR Adversarial training also had a negative effect natural accuracies (84.54% 94.24% MNIST and 45.19% 51.35% CIFAR10), similarly to ReLU training (83.69%- 93.57% on MNIST and 32.27% 37.33% on CIFAR1O).
We first ran pool of heuristic attacks on each example, namely (Kurakin et al.) 2017 Brendel et al. 2019 Carlini & Wagner [017c] Gooosavi-Dezfoll et al.] 2016 Goodfellow et al., [201 Madry et al.
2018). as well as simply adding uniform noise the input. Our main choice of attack parameters
(from now on referred to as the "strong" parameter set) prioritizes finding adversarial examples at the expense of computational time. For each example, we considered the nearest feasible adversarial example found by any attack in the pool. We then ran the exact solver- based attack MIPVerify (Teng et al. 2019), which is able to find the nearest adversarial example to a given input. The entire process (including test runs) required -45k core-hours on an HPC cluster. Each node of the cluster has 384 GB of RAM and features two Intel CascadeLake 8260 CPUs, each with 24 cores and a clock frequency of 2.4GHz. We removed the examples for which MIPVerify crashed in at least one setting, obtaining 2241 examples for MNIST and 2269 for CIFARIO. We also excluded from our analysis all adversarial examples for which MIPVvrrfy did not find optimal bounds (atol 1e-5, rtol Ie-10), which represent on average 11.55% of the examples for MNIST and 16.30% for CIFAR 10. Additionally, we ran the same heuristic attacks with faster parameter set (from now referred to as the "balanced" set) on a single machine with an AMD Ryzen 5 1600X six-core 3.6 GHz processor, 16 GBs of RAM and an NVIDIA GTX 1060 GB GPU. The process took approximately 8 hours. Refer to Appendix G for more comprehensive overview of our experimental setup.
Distance Approximation Across all settings, the mean distance found by the strong attack pool is 4.09+2.02% higher for MNIST and 2.21#1.16% higher for CIFARIO than the one found by MIPVerify. For 79.81+15.70%% of the MNIST instances and 98.40#1.6344 of the CIFARIO ones, the absolute difference is less than 1/255, which is the minimum distance in 8-bit image formats. The balanced attack pool performs similarly, finding distances that are on average 4.65+2.1 16% higher for MNIST and 1.04# higher for CIFAR10. The difference is below 1/255 for 77.78+16.084 of MNIST examples and 18.74+1..139 133% of CIFARIO examples. We compare the distances found by the strong attack pool for MNIST A and CIFAR10 (using standard training) with the true decision bound distances in Figure |
Refer to Appendix forr the full data.
For all datasets, architectures and training techniques there appears to be strong, linear, correlation between the distance of the output of the heuristic attacks and the true decision boundary distance. We chose to measure this by training linear regression model linking the two distances. For the
7

---

Under review as a conference paper at ICLR 2023
10-
-10-2
8
Estimated Distance
6-
Estimated Distance
4-
2-
0
1
8
0
3
True Distance
-10
True Distance
-10
(a) MNIST A
(b) CIFARIO A
Figure I: Distances of the nearest adversarial example found by the strong attack pool compared to those found by MIPVerify MNIST A and CIFAR1O A with standard training. The black line represents the theoretical optimum. Note that no samples are below the black line.
strong parameter set, we find that the average R² across all settings is 0.992#0.000 for MNIST and 0.997=0.003 for CIFAR1O. The balanced parameter set performs similarly, achieving an R of 0.990=0.0006 006 for MNIST and 0.998=0.002 for CIFARIO. From these results, we conjecture that increasing the computational budget of heuristic attacks does not necessarily improve predictability, although further tests would be needed to confirm such a claim. Note that such a linear model can also be used as a buffer function for heuristic CA. Another (possibly more reliable) procedure would consist in using quantile fitting: results for this approach are reported in Appendix H
Attack Pool Ablation Study Due to the nontrivial computational requirements of running several attacks on the same imput, we now study whether is possible to drop some attacks from the pool without compromising its predictability. Specifically, we consider all possible pools of size n (with a success rate of 100%) and pick the one with the highest average R2 value over all architectures and training techniques. As show in Figure adding attacks does increase predictability, although with diminishing returns. For example, the pool composed of the Basic Iterative Method, the Brendel & Bethge Attack and the Carlini & Wagner attack achieves its own a R² value of 0.988+0.000 for MNIST+strong, 0.986#0.00 005 for MNIST+balanced, 0.935#0.045 for CIFAR I 1++strong and 0.993+00003 for CIFAR 10bbalanced. Moreover, dropping both the Fast Gradient Sign Method and uniform noise leads to negligible (& 0.001) absolute variations in the mean R². These findings suggest that, as far as consistency is concerned, the choice of attacks represents more important factor than the number of attacks in a pool. Refer to Appendix J for a more in-depth overview of how different attack selections affect consistency and accuracy.
Efficient Attacks We then explore if it possible to increase the efficiency of attacks by optimizing for fast, rather than accurate, results. We pick three new parameter sets (namely Fast-100, Fast- 1k and Fast-1Ok) designed to find the nearest adversarial examples within the respective number of calls to the model. We find that while Deepfool is not the strongest adversarial attack (see Appendix I it provides adequate results in very few model calls. For details on these results see Appendix K
Fooling the Heuristic Attack-Based CA An open question from Section 5.2 is the empirical difficulty of fooling the version of CA based on heuristic attacks. Specifically. we carried on limited experimentation by attempting to fool a CA-defended model. We used Deepfool Fast- 1k as a heuristic attack for CA, then we built proof-of-concept CCA implementation based on the PGD method, thus setting a baseline for attacks against CA. This variant uses a custom loss Loca(R, y) = LPOD (æ. y) + a|I (z)p(,))l,. which rewards adversarial examples with over- estimated decision boundary distances. We then vary À in order to test various trade-offs between the two terms. In order to estimate the gradient of the second term, we use Natural Evolution Strategies (Wierstra et al. 2014). As a sanity check, we also attack using uniform noise. Due to the high computational requirements of such experiment (30-60 minutes and 1.2M model
8

---

Under review as a conference paper at ICLR 2023
0.988
0.980
Best Re
Best Re
0.980
0.981
0.992
Stoong Ralanced
0.990
Strong
Ralanced
2
4
5
7
2
5
#Attacks in Pool
#Attacks in Pool
(a) MNIST
(b) CIFARIO
Figure 2: Best mean R² value in relation to the number of attacks in the pool.
calls per sample on the GTX 1060 machine), only attack MNIST A Standard and CIFARIO A Standard on 100 samples each. For comparison, running DeepFool on ten 250-clement batches takes approximately 10 seconds. Overall, the attacks have success rate of 0% 3%. However, find that increasing (while keeping constant) increases the success rate, up to 100% for E' 10 E. This suggests that the difference between e' and grows, does the feasibility of fooling CA, which is consistent with our analysis. More in-depth results of our experiments can be found in Appendix
UG100 Dataset We collect all the adversarial examples found by both MIPVerify and the heuristic attacks into new dataset, which we name UG 100. UG100 can be used to benchmark new adversarial attacks. Specifically, we can determine how strong an attack is by comparing it to both the theoretical optimum and heuristic attack pools. Another potential application involves studying factors that affect whether adversarial attacks perform sub-optimally.
7 CONCLUSION
We proved that attacking is N P-complete in the worst case, while training robust model is E complete, barring collapse of the Polynomial Hierarchy. We then showed how such a structural asymmetry can be sidestepped by adopting different perspective on defense. This is exemplified by Counter-Attann a technique that can identify non-robust points in NP time. We showed that CA provide robustness guarantees up to arbitrary The CA approach naturally benefits from improvements in the field of adversarial attacks, and can be combined with other forms of defense. Due to its independence from the specific characteristics of the defended model, CA also be applied to non-ML tools (e.g. signature-bast based malware detectors). We also believe that it should showed that
be possible extend CA beyond classification. Finally, in empirical evaluation heuristic attacks can provide an accurate and consistent approx approximation of the true decision boundary, which has implications for the viability of heuristic version of CA. While our investigation limited to small scale networks, we expect improvements in the field of NN verification will enable testing whether the observed results generalize to larger architectures.
Overall, we hope that our contributions can provide broad benefits to the field of adversarial robustness by 1) highlighting a potential, structural, challenge; 2) pointing out how that can be sidestepped by change in perspective; 3) showing a proof-of-concept defense based on this idea; 4) providing an experimentation and dataset serve as baseline and starting point.
REPRODUCIBILITY
We provide all our code and data in the repository linked in Section I Additionally, we report the key reproducibility information in Section 6 while all the other information can be found in Appendices
To ensure maximum reproducibility, we also used consistent seeds across all experiments (one for parameter tuning and one for actual experiments). We also made sure to only rely on tools that are either open open-source or for which there are free academic licenses. Concerning theoretical results, we provide full proofs of all theorems and corollaries in the appendices. Finally,
G and L

---

Under review as a conference paper at ICLR 2023
for users with slow internet connection, also provide UG100 in JSON format (containing only the found adversarial distances).
REFERENCES
Anish Athalye, Nicholas Carlini, and David Wagner. Obfuscated gradients give false sense of security: Circumventing defenses to adversarial examples. In International Conference on Machine Learning, pp. 274-283 PMLR, 2018.
Pranjal Awasthi, Abhratanu Dutta, and Aravindan Vijayaraghavan. On robustness to adversarial examples and polynomial optimization. Advances in Neural Information Processing Systems, 32, 2019.
Wieland Brendel, Jonas Rauber, Matthias Kümmerer, Ivan Ustyuzhaninov, and Matthias Bethge. Accurate, reliable and fast robustness evaluation. Advances in Neural Information Processing Systems, 32, 2019.
Tom B Brown, Dandelion Mané, Aurko Roy, Martín Abadi, and Justin Gilmer. Adversarial patch. arXiv preprint (7t.:0:/7/1..06... 2017.
Nicholas Carlini and David Wagner. Defensive distillation not robust to adversarial examples. arXiv preprint arXiv:1607.043)) 2016.
Nicholas Carlini and David Wagner. Adversarial examples easily detected: Bypassing detection methods. In Proceedings of the 10th ACM Workshop on Artificial Intelligence and Security, pp. 3-14. 2017a.
Nicholas Carlini and David Wagner. Magnet and "efficient defenses against adversarial attacks" are not robust adversarial examples. arXiv preprint 171 20176 7b.
Nicholas Carlini and David Wagner. Towards evaluating the robustness of neural networks. In 2017 IEEE Symposium Security and Privacy (SP), pp. 39-57. IEBE, 2017c
Nicholas Carlini, Guy Katz, Clark Barrett, and David Dill. Provably minimally-distore adversarial examples. arXiv preprint
2017.
Nicholas Carlini, Florian Tramer, Zico Kolter, et (certified!!) adversarial robustness for free! arXiv preprint arXiv:2206. 2022.
Jeremy Cohen, Elan Rosenfeld, and Zico Kolter. Certified adversarial robustness via randomized smoothing. In International Conference Machine Learning, pp. 1310-1320. PMLR, 2019.
Francesco Croce, Sven Gowal, Thomas Brunner, Evan Shelhamer, Matthias Hein, and Taylan Cemgil. Evaluating the adversarial robustness of adaptive test-time defenses. arXiv preprint NXXV:2202.13711, 2022.
Chen Dan. Yuting Wei, and Pradeep Ravikumar. Sharp statistical guaratees for adversarially robust gaussian classification. In International Conference on Machine Learning. pp. 2345-2355. PMLR, 2020.
Akshay Degwekar, Preetum Nakkiran, and Vinod Vaikuntanathan. Computational limitations in robust classification and win-win results. In Conference on Learning Theory, pp. 994-1028, PMLR, 2019.
Gavin Weiguang Ding, Luyu Wang, and Xiaomeng Jin. AdverTorch v0.1: An adversarial robustness toolbox based on pytorch. arXiv preprint 1rXiv.1902.07623, 2019.
Edgar Dobriban, Hamed Hassani, David Hong, and Alexander Robey. Provable tradeoffs in adversar- ially robust classification. arXiv preprint arXiv:2006.0511 2020.
Tommaso Dreossi, Shromona Ghosh, Alberto Sangiovanni- Vinceetelli, and Sanjit A Seshia. A
formalization of robustness for deep neural networks. arXiv preprint arXiv: /0033, 2019.
10

---

Under review as a conference paper at ICLR 2023
Krishnamurthy Dvijotham, Robert Stanforth, Sven Gowal, Timothy A Mann, and Pushmeet Kohli, A dual approach to scalable verification of deep networks. In UAI, volume 1. pp. 3, 2018.
Reuben Feinman, Ryan R Curtin, Saurabh Shintre, and Andrew B Gardner. Detecting adversarial samples from artifacts, arXiv preprint arXiv: 00410, 2017.
Sanjam Garg, Somesh Jha, Saeed Mahloujifar, and Mahmoody Mohammad. Adversarially robust learning could leverage computational hardness. Algorithmic Learning Theory, pp. 364-385. PMLR, 2020.
Ian Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. In International Conference on Learning Representations, 2015. URL http://
arxiv v. orggabs/1412 6572
Kathrin Grosse, Praveen Manoharan, Nicolas Papernot, Michael Backes, and Patrick McDaniel. On the (statistical) detection of adversarial examples. arXiv preprint arXiv:/702.06280, 2017.
Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual, 2022. URL https: www gurobi com
Husheng Han, Kaidi Xu, Xing Hu, Xiaobing Chen, Ling Liang, Zidong Du, Qi Guo, Yanzhi Wang. and Yunji Chen. Scalecert: Scalable certified defense against adversarial patches with sparse superficial layers. Advances in Neural Information Processing Systems, 34, 2021.
Warren He, James Wei, Xinyun Chen, Nicholas Carlini, and Dawn Song. Adversarial example defenses: ensembles of weak defenses are not strong. In Proceedings of the 11th USENIX Conference on Offensive Technologies, pp. 15-15, 2017.
Matthias Hein and Maksym Andriushchenko. Formal guarantees on the robustness a classifier against adversarial manipulation. Advances in Neural Information Processing Systems, 30, 2017.
Dan Hendrycks and Kevin Gimpel. Early methods for detecting adversarial images. International Conference Learning Representations (Workshop Truck), 2017.
Hossein Hosseini, Sreeram Kannan, and Radha Poovendran. Are odds really odd? bypassing statistical detection of adversarial examples. arXiv preprint 1rXiv:1907.121:3. 2019.
Robin Jia, Aditi Raghunathan, Kerem Göksel, and Percy Liang. Certified robustness to adversarial word substitutions. arXiv preprint arXiv: pttp:/9990009000 2019.
Guy Katz, Clark Barrett, David Dill, Kyle Julian, and Mykel Kochenderfer. Reluplex: An efficient smt solver for verifying deep neural networks. arXiv preprint arXiv:1702.01135, 2017.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint 14Xiv:1412.6900 2014.
Roger Koenker and Gilbert Bassett Jr. Regression quantiles. Econometrica: journal of the Economet- ric Society, pp. 33-50, 1978.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. Technical report, 2009.
Alexey Kurakin, Ian Goodfellow, and Samy Bengio. Adversarial machine learning at scale. 2017.
Yann LeCun, Corinna Cortes, and Christopher J.C. Burges. The MNIST database of handwritten digits.
www..nnc...//e//////iieeeeeeeeee 1998.
Klas Leino, Zifan Wang, and Matt Fredrikson. Globally-robust neural networks. In International Conference on Machine Learning, pp. 6212-6222. PMLR, 2021.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. In International Conference on Learning Representations, 2018.
11

---

Under review as a conference paper at ICLR 2023
Saeed Mahloujifar and Mohammad Mahmoody. Can adversarially robust learning leverage computa- tional hardness? In Algoritiiic Learning Theory, pp. 581-609. PMLR, 2019.
Dongyu Meng and Hao Chen. Magnet: a two-pronger pro-pronged defense against adversarial examples. In Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, pp. 135-147, 2017.
Yifei Min, Lin Chen, and Amin Karbasi. The curious case of adversarially robust models: More data can help, double descend, or hurt generalization. In Uncerlainty in Artificial Intelligence, pp. 129-139. PMLR, 2021.
Seyed-Mohsen Moosavi-Dezfoolle Alhussein Fawzi, and Pascal Frossard. Deepfool: a simple and accurate method to fool deep neural networks. In Proceedings of the IEEE Conference Computer Vision and Pattern Recognition, pp. 2574 2582, 2016.
Ambar Pal and René Vidal. A game theoretic analysis of additive adversarial attacks and defenses. Advances in Neural Information Processing Systems, 33:1345 1355, 2020.
Nicolas Papernot, Patrick McDaniel, Ian Goodfellow, Somesh Jha, 2. Berkay Celik, and Ananthram Swami. Practical black-box attacks against machine learning. In Proceedings of the 2017 ACM Asia Conference on Computer and Communications Security, pp. 506-519, 2017.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang. Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high-performance deep learning library. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' d'Alché-Bus Buc. E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems 32, pp. Associates, Inc., 2019.
Curran
Rafael Pinot, Florian Yger, Cédric Gouy-Pailler, and Jamal Atif. A unified view on differential privacy and robustness to adversarial examples. arXiv preprint arXiv: 2019.
Muni Sreenivas Pydi and Varun Jog. The many faces of adversarial risk. Advances in Neural Information Processing Systems, 34, 2021.
Aditi Raghunathan, Jacob Steinhardt, and Percy Liang. Certified defenses against adversarial examples. arXiv preprint wrXiv:1801.09344 2018.
Jonas Rauber, Roland Zimmermann, Matthias Bethge, and Wieland Brendel. Foolbox native: Fast adversarial attacks to benchmark the robustness of machine learning models in pytorch, tensorflow, and jax. Journal of Open Source Software, 5(53):2607, 2020.
Ambrish Rawat, Martin Wistuba, and Maria- Nicolae. Adversarial phenomenon in the eyes of bayesian deep learning. arXiv preprint 171 2017.
Jie Ren, Die Zhang, Yisen Wang, Lu Chen, Zhanpeng Zhou, Yiting Chen, Xu Cheng, Xin Wang, Meng Zhou, Jie Shi, al. A unified game-theoretic interpretation adversarial robustness. arXiv preprint arXiv:2 /tti:://11.033666 2021.
Fitan Richardson and Yair Weiss. bayes-optimal view adversarial examples. Journal of Machine Learning Research, 22(221):1-28, 2021.
Kevin Roth, Yannic Kilcher, and Thomas Hofmann. The odds are odd: A statistical test for detecting adversarial examples. In International Conference on Machine Learning, pp. 5498-5507, PMLR, 2019.
Hadi Salman, Mingjie Sun, Greg Yang, Ashish Kapoor, and Zico Kolter. Denoised smoothing: provable defense for pretrained classifiers. Advances in Neural Information Processing Systems, 33:21945-21933 2020.
Samuel Henrique Silva and Peyman Najafirad. Opportunities and challenges in deep learning adversarial robustness: A survey. arXiv preprint arXiv:2007.00753, 2020.
12

---

Under review as a conference paper at ICLR 2023
Gagandeep Singh, Timon Gehr, Matthew Mirman, Markus Püschel, and Martin Vechev. Fast and effective robustness certification. Advances in Neural Information Processing Systems, 31, 2018.
Aman Sinha, Hongseok Namkoong, Riccardo Volpi, and John Duchi. Certifying some distribu- tional robustness with principled adversarial training. In International Conference on Learning Representations, 2018.
Min Jae Song, Ilias Zadik, and Joan Bruna. On the cryptographic hardness of learning single periodic neurons. Advances in neural information processing systems, 34:29602-22615, 2021.
Larry J Stockmeyer. The polynomial-time hierarchy. Theoretical Computer Science, 3(1):1-22, 1976.
Christian Szegedy, Wojeiech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties of neural networks. arXiv preprint arXiv:1312 1.X.::13/2.619,, 2013.
Vincent Tjeng, Kai Y Xiao, and Russ Tedrake. Evaluating robustness of neural networks with mixed integer programming. In International Conference on Learning Representations, 2019.
Florian Tramèr, Jens Behrmann, Nicholas Carlini, Nicolas Papernot, and Jöm-Henrik Jacobsen. Fun- damental tradeoffs between invariance and sensitivity to adversarial perturbations. In International PMLR, 2020.
Conference on Machine Learning, pp.
Florian Tramer, Nicholas Carlini, Wieland Brendel, and Aleksander Madry. On adaptive attacks to adversarial example defenses. Advances in Neural Information Processing Systems, 33:1633-1645, 2020.
Guillaume Vidot, Paul Viallard, Amaury Habrard, and Emilie Morvant. A pac-bayes analysis of adversarial robustness. arXiv preprint arXiv:2102.11065 2021.
Lily Weng, Huan Zhang, Hongge Chen, Zhao Song, Cho-Jui Hsieh, Luca Daniel, Duane Boning, and Inderjit Dhillon. Towards fast computation of certified robustness for relu networks. In International Conference on Machine Learning. pp. 1276-5285 PMLR, 2018a.
Tsui- Tei Weng, Huan Zhang, Pin- Yu Chen, Jinfeng Yi, Dong Su, Yupeng Gao, Cho-Jui Hsieh, and Luca Daniel. Evaluating the robustness of neural networks: An extreme value theory approach. In International Conference Learning Representations, 2018b.
Daan Wierstra, Tom Schaul, Tobias Glasmachers, Yi Sun, Jan Peters, and Jürgen Schmidhuber. Natural evolution strategies. The Journal of Machine Learning Research, 15(1) (1499999,, 2014.
Zuxuan Wu, Ser-Nam Lim, Larry S Davis, and Tom Goldstein. Making an invisibility cloak: Real world adversarial attacks on object detectors. In European Conference on Computer Vision, pp. 1-17. Springer, 2020.
Kai Y Xiao, Vincent Tjeng. Nur Muhammad Shafiullah, and Aleksander Madry. Training for faster adversarial robustness verification via inducing relu stability. In International Conference on Learning Representations, 2019.
Yao-Yuan Yang, Cyrus Rashtchian, Hongyang Zhang, Russ R Salakhutdinov, and Kamalika Chaud- huri. closer look at accuracy vs. robustness. In Advances in Neural Information Processing Systems, volume 33, pp. 8588-8601, 2020.
Bohang Zhang, Tianle Cai, Zhou Lu, Di He, and Liwei Wang. Towards certifying l-infinity robustness using neural networks with l-inf-dist neurons. In International Conference on Machine Learning. pp. 12268-12377 PMLR, 2021.
Hongyang Zhang. Yaodong Yu, Jiantao Jiao, Eric Xing, Laurent El Ghaoui, and Michael Jordan. Theoretically principled trade-off between robustness and accuracy. In International Conference Machine Learning, pp. 7472-7482. PMLR, 2019.
Jingfeng Zhang, Xilie Xu, Bo Han, Gang Niu, Lizhen Cui, Masashi Sugiyama, and Mohan Kankan- halli. Attacks which do not kill training make adversarial learning stronger. In International Conference on Machine Learning, pp. 1228-11287. PMLR, 2020.
Yan Zhou, Murat Kantarcioglu, and Bowei Xi. A survey of game theoretic approach for adversarial machine learning. Wiley Intendisciplinary Reviews: Data Mining and Knowledge Discovery, 9()): e1259, 2019.
13

---

Under review as a conference paper at ICLR 2023
A PROOF PRELIMINARIES
A.1 NOTATION
We use fe to denote the i-th output of network. We define
f(x) arg max fa
for situations where multiple outputs are equal to the maximum, we use the class with the lowest index.
A.2 1 ARITHMETIC
Given two FSFP spaces X and X' with distance minorants and μí, we can compute new positive minorants after applying functions to the spaces as follows:
Sum of two vectors: μX+ -min(,,
Multiplication by a constant: Pa asp
ReLU: (e)LU( = J..
Since it is possible to compute the distance minorant of a space transformed by any of these functions in polynomial time, it is also possible compute the distance minorant of a space transformed by any composition of such functions in polynomial time.
A.3 FUNCTIONS
We now provide an overview of several functions that can be obtained by using linear combinations and ReLUs.
max Carlini (2017) showed that we can implement the max function using linear combinations and ReI.Us as follows:
max(x, y) ReLU - y) +
We can also obtain an n-ary version of max by chaining multiple instances together.
step If X is a FSFP space, then the following scalar function:
stepo(z) (ReLU(x) - ReLU(x 44)
(8)
such that Vo E X, stepo (2;: is 0 for x; & 0 and I for x; > 0.
Similarly, let step1 be defined follows:
step1 (x) 1 (ReLU(I ReLU(z))
(9)
1
Note that Vi. X, step: (x,) = 0 for 0 and (t.p)(x.) = 1 for 2 0.
Boolean Functions
We then define the Boolean functions not : {0, - {0, 1), and 1]2-
(0, 1), (0, 1) and if 10, {0,1) 1) as follows: not(x)
(10)
and(x, y) = step1 (x + 2)
(11)
or(x, y) slepi (xr + y)
(12)
(a b, c) or(and(nol((), b), and(a, c))
(13)
where (a b, c) returns 5 if a = 0 and c otherwise.
Note that obtain n-ary variants of and and or by chaining multiple instances together.
14

---

Under review as a conference paper at ICLR 2023
en Given set f(21,1....- .... 21.s)..... 1, 2n,3) of Boolean atoms (i.e. (1,5 Iy
m for a certain k) defined on an n-long Boolean vector æ, cnfa(2) (z) returns the following Boolean
function:
cnfg(ar) =
A 1= 11
(1)
(14)
We refer to 3CNF formula.
Since enjl only uses negation, conjunction and disjunction, it can be implemented using respectively neg, and and Note that, given
build en f/z in polynomial time w.r.t the size of 2.
Comparison Functions follows:
We can use stepo, step1 and neg to obtain comparison functions as
geq(x, k) = step1 (x k)
(15)
gt(x, k) stepo (z, k)
(16)
leq(x, k) = not x. k))
(17)
[t( k) not(geq(1,, k))
(18)
eq(x, k) = and(geq(a, xx k), leg(a, k))
(19)
Moreover, we define open 1R3 + {0, 1} as follows:
open(r, b) and(gl(a, a) Mxx b))
(20)
B PROOF OF THEOREM
B.I U-ATT NP
To prove that U-ATT NP, show that there exists polynomial certificate for U-ATT that can be checked polynomial time. The certificate is the value of æ', which will have a representation of the same size (due to the FSFP space assumption) and can be checked by verifying:
l s' ooo See E, which can be checked in linear time:
fo(x') + f(x), which can be checked in polynomial time.
B.2 U-ATT IS NP-HARD
We will prove that U-ATT P-Had by showing that 3SAT S U-ATT
Given set of 3CNF clauses z {[ 212, ,ia)...., f [2ml 2m2, 2m3 }} defined on Boolean variables .I,..., En, we construct the following query g(z) for U-ATTxo:
<()) = (+)
(21)
1) is vector with elements. Verifying q(x) U-ATT is equivalent to where (x)) = (.....,,)) checking:
Bo' Boo (10) 11 ((x') # ((x(1)
(22)
Note that a E Box (z(()), 1) is equivalent to æ E [0, 1]"
Truth Values
We will encode the truth values of follows:
x
- =
(23)
o E
5.
1
5 =1
(24)
We can obtain the truth value of scalar variable by using isT(x;) gt (z,, 2). Let bin(x) (rii)(())....... isT is.(r))
15

---

Under review as a conference paper at ICLR 2023
Definition of
We define f as follows:
fi (x) (isz)) en
(25)
fa( = not(fi (x))
(26)
where enfy (z) and (sr(") (+) is defined as follows:
iss! (x)) = and (gg (111)) 2 ,...,,, eq Fns 1
(27)
Note that f is designed such that fxx(+)) O, while for x' & x f(x') = 1 iff the formula is true for the variable assignment bin (x').
Lemma 1. E 3SAT = (()) E U-ATT
Proof. Let E 3SAT. Therefore 3x* {0, 13th such that cafs(=)(x") = Since bin(x=) = x²
and * x5)), f(x*) which means that it is valid solution for Equation (22) From this we can conclude that ((2) E U-ATTxx
Lemma 2. ((2) E U-ATT = ZE ESAT
Proof. Since (()) E U-ATT F E [0, 1J" \ (x(*) that is a solution to Equation 22 (i.e. f(x') 1). Then en obin((b)(
which means that there exists ø (i.c. bin(x")) such that f a) = 1. From this we can conclude that # E 3SAT.
Since:
q(z) can be computed in polynomial time; q(z) E 3-ATT>::
z E 3SAT
q(z) E U-ATT
E 3SAT.
we can conclude that 3SAT S U-ATT
B.3 PROOF OF COROLLARY
B.3.1 U-ATT, NP
The proof is identical to the one for U-ATT
B.3.2 U-ATT, IS NP-HARD
The proof that ((2) E U-ATT,
=2 2 35AAAA is very similar to the one for U-ATT Since
((2) E U-ATT,, we know that Fxr E (z())))), \ (ax(*))_((x") = 1, which means that there exists a & (i.e. bin(xx) such that ( 1. From this we can conclude that z E 3SAT.
The proof that 3SAT = ((2) E U-ATT, is slightly different, due to the fact that since xx & (x(x(()), 1) we need to different input to prove that Ex' ()((=())..((())) =
Let 0 < < dc. Given positive integer n and a real 0 < p < oo, let (p))(T) be a positive minorant of the _ norm of vector the L sphere of radius For example, for 2, 2 and 1, v suitable. Note that, for 0 p < oc and n, r > any positive value less than or equal to (r) <
Let AS. Therefore Fx. {0, 13" such that en cnfa(=)(x") Let "* be defined as:
Pp. (2)
xx = 0
(28)
Pp. =
By construction, xx E B, (x))), Pp. (t)). Additionally, bin(x"*) x=, and since we know that z is true for the variable assignment x. we can conclude that f(x**) = 1. which means that x** is valid solution for Equation (22h. From this conclude that g(z) U-ATT,
16

---

Under review as a conference paper at ICLR 2023
B.4 PROOF OF COROLLARY
The proof is identical to the proof of Theorem (for oc) and Corollary 1.1 (for 0 < o0). with the exception of requiring f(x') 1.
B.5 PROOF OF COROLLARY
The proof that attacking a polynomial-time timee classifier is in NP is the same as that for Theorem
Attacking polynomial-time classifier is NP-hard due the fact that the ReLU networks defined in the proof of Theorem D are polynomial-time classifiers. Since attacking a general polynomial-timg classifier a generalization of attacking ReLU polynomial-timg classifier, the problem is N P-hard.
C PROOF OF THEOREM 2
Proving that U-ATT,(1) NPA means proving that it can be solved in polynomial time by non-deterministic Turing machine with an oracle that can solve a problem A. Since Z E A, we do so by picking non-deterministic Turing machine with access to oracle that solves Zy. We then generate non-deterministically the adversarial example and return the output of the oracle. Due the FSFP assumption, know that the size of this input is the same as the size of the starting point, which means that it can be generated non-detene -onddttermiiittcally in polynomial time. Therefore, U-ATT,(f) NP4
C.1 PROOF OF COROLLARY 2.1
Follows directly from Theorem and the definition of X.
D PROOF OF THEOREM
D.1 PRELIMINARIES
11,3STA the set of all z such that:
Ve3g. 9)
(29)
where R(2, 1) = ( In. , ).))
Stockmeyer 1976 showed that 1T,SAT is III" ccomllete. Therefore, coII,35AT, which is defined as the set of all such that:
Eavū-R($. ()
(30)
ΣP complete.
D.2 PL-ROB E DP
PI-ROBx E Eff if there exists a problem A E P and a polynomial such that VT = (x, So, uy):
e' PL-ROB = Byllyl ((IT) A Vz < <([F)) = (T,y.2, z) E A))
(31)
This can be proven by setting y 0', xx' and A the set of triplets (T, 0' x²) such that all of the following are true:
vy((')= 1;
| x ||0 5 3;
fo(w) fo(x').
Since all properties be checked in polynomial time, A E P and thus PT-ROB E EPP.
17

---

Under review as a conference paper at ICLR 2023
D.3 & is Eg- -HARD
We will prove that p is Σ2 hhard by showing that col1235AT & PL-ROB
Let na be the length of à and let ny be the length of y-
Given a set of 3CNF clauses, we construct the following query g(z) for PL-ROB:
((z) = (ax(e) 22' So vz)
(32)
where xx(1 = 2.....: :) is vector with ng elements and yy that 0' E {0, 1) can be checked in polynomial time w.r.t the size of the input.
o {0, 1)a2. Note
Truth Values We will encode the truth values of & as set of binary parameters 0', while we will encode the truth values of using x' through the same technique mentioned in Appendix B.2
Definition of fo We define fo as follows:
.))) where enjā is defined over A and bin( us- ing the same technique mentioned in Appendix B.2 and (szl*())) and:= 2); Sa.0(3> (x) = (fo (æ)).
fo,1 = (x)) enfz
Note that fo(x for all choices 0. Additionally, fo is designed such that:
x (5) ( :/2
Va' E Boo
{x (*))) (.,0'.(u)(()) = = (fer = + bin((in (33)
Lemma 3. 2 E colI235AT AT = ((=) E PI-ROBx
Proof. Since = E coll,35 AT, there exists a Boolean vector x" such that Vý.-R((x" "')"",)))))) 9)
Then both of the following statements true:
vy(x*) 1, since xt E {0, 1M==;
Va' E Boo (a)(1), (a)(t)))).far (x') = O, since fa-(x') = > R(w", bin(()))))
Therefore, x² is a valid solution for Equation 3 and thus q(z) E PL-ROB
Lemma 4, ((2) E PI-ROB = E coTT23SAT
Proof. Since ((z) E PI-ROBxo. there exists 0" such that:
(0 1A Var (xo e). (x') so. (x))))
(34)
Note that 0* E {0. 12 since e Moreover, Vý.-R(0" ÿ). since bin(g) and fe- (i) = + R g)
Therefore, 0" is valid solution for Equation (30). which implies that colI,3SAT.
Since:
q 2)) can computed in polynomial time;
z E AT
= (()) E PT. Bxe:
q(z) E PL-ROB, = 3S.
conclude that co < PI-ROB
18

---

Under review as a conference paper at ICLR 2023
D.4 PROOF OF COROLLARY 3.1
D.4.1 PL-ROB, DE
The proof is identical to the one for PL-ROB
D.4.2 PL-ROB, DS HHADD
We follow the same approach used in the proof for Corollary 1.1
Proof of g(z) PL-ROB,
coIL,3AAT If q()) E PL-ROBp. it means that
30" (ur == = Vad E Bp (z(() -f))(((()))))) 0). Then Vÿ, there exists corresponding
input y² E Bp (ar(t) 1) defined as follows:
Pp.m
J 0
(35)
Pp..
D. =
such that (y**)) = D. Since yd* E Bp (0), 4), cn (0", bin(y")) = 0, which means that R(O", 1) is false. In other words, = -O. ÿ) ie. colI23SAT.
Proof of z E 3SIL one for Theorem 3
q(z) E PL-ROB, The proof is very similar to the corresponding
I col123SAT, then Et *rg.-Ri g). Set 0+ = o² We know that fā (x(()) = O. We also know that Va' E Bp (x))), 2) \ (w(+)), J. (fa-(1) =1 = enl (0" x') 1). In other words, Va' Bp (x(*), 1) (x(s)) (x=) = + R(0 ((0*,bin(x')) Since R(O", .)) is false for all choices of y. Va' E Bp (z)*), (z) fo- (x') = O. Given the fact that fo- (xx()) = O, we can
conclude that 0* satisfies Equation
D.5 PROOF OF COROLLARY 3.2
Similarly to the proof of Corollary 1.3 it follows from the fact that ReLU classifiers are polynomial- time classifiers (w.r.t. the size of the tuple).
E PROOF OF THEOREM 4
There are two cases:
Vas E Bp(x,)) [xx): then the attack fails because f(x) & C(æ);
Ea' E Br(x,)).f f)'f(x) A f()): then due to the symmetry of the L norm æ E B, e)).
Since f(x) o f(x'), x is valid adversarial example for æ', which means that f f(x')
Since * & C(x), the attack fails.
E. PROOF OF COROLLARY
Assume that Vie |arl|/ 2 v/ |0 [|p and fix (+) X. Let a' E (x(()), ne) ) be an adversarial example. Then | - -1 < ne, and thus v/|æz - x (0 I ne. Dividing by n, we get ||æ x=() l|p S e, which means that (s) is valid adversarial example for æ'' and thus x' is rejected by p-CA.
We now proceed to find the values of 1)-
E.
1 15r <
We will prove that ||a]||- 2 ||
19

---

Under review as a conference paper at ICLR 2023
Case p Consider ||ll
is such that |/e||p and for all we have lesl s 1. Since
r < p. for all 0 I t we have |
I ldl". Therefore:
1/r
1/r
||e|l, Σ eill)
2
Σ
leil
= Ieelpp/ =1
(36)
Then, since | 2 1:
x |, = ||>|||||||| pe Ir = || ||p|||||||/ 2 |||||
(37)
Since ||||| 2 | for all p and since the expressions on both sides of the inequality are compositions of continuous functions, as p + we get | 2 ||0||00.
Case p oo
E.1.2 r>p
We will prove that | 2 n - 11111p.
Case < 00
Hölder's inequality states that, given a. B 2 such that + = 1 and given f and
we have:
llfal1 - ||fl|a/ll||
(38)
Setting a -pp 3= 1, f (l,.... ......,).... and g = (af..... ,.), ). we know that:
11fal11 Ei=i(1 (1 x ||>1
|1/la = -Ei 1) 1//0 = n1//a;
|9lll (Ei=1 ) p/r
CEin 1
|| ls.
Therefore
||0| S n//a1//a Jr. Raising both sides to the power of 1/p, we get ||0/|b S /ppc))))
[
Therefore:
||ا||| S (r (rr-///6r)(1z |+||,
n
(39)
Dividing by no we get:
| ||0|||
(40)
Case Since the expressions on both sides of the inequality are compositions of continuous
functions, as r + oo we get ||0||/0 2 n ||r|pp
F PROOF OF THEOREM 5
F.1 CCA. E Eg
CCAx EP iff there exists problem A E and polynomial p such that VT (x, f)
I' CCAx + By./yl p ((T)) (Vz. (1= s p((1)) = (T y) A))
(41)
This can be proven by setting y æ'.z xx and A the set of all triplets (T, , x") such that all of the following are true:
x - x' lloo E
[ax') C(x))
|ar" x' 11 S
f(x") f(x')
Since all properties can be checked in polynomial time, A E P.
20

---

Under review as a conference paper at ICLR 2023
F.2 CCAx E2-Ha. -HARD
We will show that CCAx is Dg hard by proving that coll,3SAT S CCAx
First, suppose that the length of æ and ý differ. In that case, we pad the shortest one with additional variables that will not be used.
Let n be the maximum of the lengths and ý.
Given set of 3CNF clauses, we construct the following query ((z) for CCA..c:
q(z) (xx(),
...55' Cu. h)
(42)
where 1 <> < 5 and (x()) = ( ( is a vector with n elements. Verifying ((z) E CC is
equivalent checking:
2 ((aa)) + 1(x)) A (Ya" B (ar M(x") = =maa'))
Rr' E B
(43)
Note that x' E [0, 1).
Truth Values
We will encode the truth values of & and ý as follows:
1
x E
0,
d; 0 9:
1 1
x
d; 0 9
4 2
(44)
1 3
x!!
1 V 91 O
2' 4 3
x
d;
1
A 11
Let cxr(x) = gt (I,, $). Let:
1 Ti: 7 2
3 7
(gi(a) = or open
open
Tii
(45)
Note that (x returns the truth value of dt and egg (x!") returns the truth value of ú (as long as the input is within one of the ranges described in Equation (44)).
Invalid Encodings All the encodings other than the ones described in Equation 44 are not valid. We define inup as follows:
im)p(x) or or (out edge(()))
(46)
where out(z;) = or(leq(z; 0), geg(x;, 1)) and
edge(a:) or (eu Fin (a: 4) eq
1) _
3 4
Iin
ee Iin
(47)
On the other hand, we define iner follows:
iney (x: = or or
(48)
21

---

Under review as a conference paper at ICLR 2023
Definition of h Let be Boolean formula defined over (x) and el that returns the value of R (using the same technique as cn.fz).
We define h as two-class classifier, where:
(1(2) = or(inur(2), onddfot g(x)))
(49)
and ha( (h1 (a=)).
Note that:
If x; = 2 for some i, the top class is I; therefore, h(x((+)
Otherwise, if is not valid encoding, the top class is O;
Otherwise, the top class if ((el))(())))))) (x), e( true and otherwise.
Lemma 5. coll23SAT = q(z) CCA,
Proof. If = E col123SAT, then there exists a Boolean vector xt such that Vg.-R((#* ((="","000 9)
We now prove that setting æ' xx satisfies Equation (5) First, note that h((=") which satisfies
h(x') # h(x). Then we need to verify that vx" E (x
x", ())x(())) = 0.
For every x" E (xo 7),, we know that x" (1-7n) 7, >))" There are thus two cases:
x" is not valid encoding, i.e. x. < 50V= 1v.," { }} for some i. Then h(=")) O. Note that, since y 2 1-7; ? [ y, 1 7]. so it is not possible for x" to be an invalid encoding that is classified as 1;
x" is valid encoding. Then, since 7 1. el*) x². Since h(o") iff R(el*) (x"), e(") is true and since R(x", ÿ) false for all choices of g. h(x")( = 0.
Therefore, x" satisfies Equation 43 and thus ((z) E CCAxx
Lemma 6. q(z) E CCAxcc = E Ao
Proof. Since q(z) CCA, there exists xx E B (axlt), ( 1) such that Mx*)) * h(x(+)) and Vo" & (x(("))(((") = h(x²). We will prove that (xx) is a solution to coll23S
Since h(x()))= = 1, h(x*) = 0, which means that Vx"" E B (2= ())("))))) =
We know that xt E Boc (x), 1) = [0, We first prove by contradiction that x'
(l0, 1 - -3-7)um u + y, 1))". If xt E 7.2 + 7] for some i, then the vector (=w)) defined as follows:
(w) 2 i=j
(50)
xx
otherwise
such that (:)) E Boo (xf,7) 7) and h (w) = (since inur (xr(w) = 1). This contradicts the fact
that Vx" E (,(x",))) h)))()))))))))))))))))))))))))) O. Therefore, x² E (10, 1 - U + 1))"
As consequence, Vo" Boc 7) e))e(()(()"))
(x*))
We now prove that "ar" E Boo 77) such that elv) (x**)= Dj We construct such "** as follows. For every i:
(x)) and (x=) ) = 0, set a²* equal to a value (0, 1):
(x=) and e(v) (x*) 1, set x equal a value in ():
(xx) and (x:") 0, set ar!" equal value in (1 7, 3):
22

---

Under review as a conference paper at ICLR 2023
If (x=) and (x1) 1. set x²"" equal to value in (2: 1).
By doing so, have obtained a"* such that x"* Bao ,n) ,7 and e(w) (x*** - ""
Since:
(x*) e (x*) for all æ";
h(a²) 0 for all æ":
h(x=) = 1 iff ((el=)()))) e(v) (x=") is true;
R(e())(**) (.))))))))))))))) 90)) is false for choices of y". other words, #t is a solution to Equation 30 and thus coIly3SAT.
Since:
(22) can be computed in polynomial time;
z E coII23SAT
= q(z) E c
(()) E CC
2 cTT
conclude that coII23SAT S CCA.
F.3 PROoF OF COROLLARY 5.1
The proof of CCAp E D/ is the same as the one for Theorem 5
For the hardness proof, follow a more involved approach compared to those for Corollaries and 3.1
First, let pppn. be the value of epsilon such that Pp.. ($pp..) +.- In other words, (x(x((*), p is an L ball that contains [0, 1j", while the intersection of the corresponding L sphere and [0, 1]" is the set {0, 13 (for < oc).
Let (x) be defined as follows:
1 (x)) = or or eg Fi, 2
Ieg(a: ()eeee)),,eeeeee geg(zs;; 11)
(51)
Let (x) be defined as follows:
1) ba
Jis 3/4 1)))
in (x) = or ori=l....
or eq
Iis 7
(52)
We define h as follows:
11 = or (inu (nd[not(inn/
(53)
with 16(x) = (x))
Note that:
If s; E (-o0, 0) (2) [1, oo) for some then the top class
Otherwise, if is not valid encoding, the top class is O: Otherwise, the top class if ((el)))))
true and otherwise.
Finally, let 8 < < }. Our query is thus:
((x) = (x)()) , Cu. N²)
(54)
23

---

Under review as a conference paper at ICLR 2023
Proof of colly3SAT = g(z) E CCAp x² be defined as follows:
If coll23SAT, then Ex* Vy.-RR('', ÿ) Let
x = 0
27
(55)
x
Note that:
x" E Bp (x(*), spp.a);
(x*")) =x";
f(**)) O, since x" E ( 3)";
Since 7 < +. there is no such that Ex" B,(x"",)))""" E (-o0, 0| U {2} u [1,
For all x" E Bp(w"", ,7)):
x" is not valid encoding (i.e. xy G1 3 for some i), then 1((x") = O: iff (xe") elx) (x²)) is true.
Otherwise, Ht' (l(x")
Therefore, since Vý. RR."" f0((""'0) ÿ). we know that Vx" E Bp(x" -))f(x=)) = O. In other words, xx
a solution to Equation (5)
Proof of g(z) E CCAp that 3xr E Bp (z((), Eppna) (h'(*") h(z())))(())) A Va" E Bp(x", (') = hl(x)). In other (1'(x') (ppp..)((((("))))))
coll33AT If g(z) E CCAp, then we know
words, 3x* E Bp (ax()) (pp..)
Vx" E Bp(x" ()M((() = 0).
We will first prove by contradiction that x= E ((7 - u + 1-))-
First, suppose that ot (-o0, 0) U (1, some Then 11(x*) = due to the fact that fner((x")
Second, suppose that x E 10, U - 1 for some i. Then a (w), defined as follows:
0
|0,''l i=j i=jハ [1 [1
((n)))
1
(56)
j j
is such that (w)) E B,(x",77' but hi (x(xx"))) 1. Finally, suppose that x; E [
7, 2 + > for some i. Then x (w), defined as follows:
(w)
2
i=j
(57)
xjj
otherwise
such that (w))) E Bp(x", but h1 (x(()) 1. Therefore, xx E ((7, - 71) ( + 7/ - -²
As consequence Vz" E (x 7 (x)) (x") cla)
From this, due to the fact that 7 > 1 and that p > O, we can conclude that for all ÿ. there exists x" E Bx(x" ,') such that:
x E
0,
for xt E
7/, 7
. 0
1
for x E
(212 7
-i -1
4
(58)
1
3
x"
for ø E
+ /
.9 0
2
4
x
for ot E
+ x
.9
4'
24

---

Under review as a conference paper at ICLR 2023
In other words, for all there exists corresponding x" By(x" , such that elu) (x0) ÿ. Therefore, since h' (æ*) 1 ift R(el=)(a")) (x"), (x")) is true and since Væ" E By(x", B'((",,''.h( ?2) can conclude that Vý. V).-R(((()) (x*) ÿj. In other words, E col1238AT.
F.4 PROOF OF COROLLARY 5.2
Similarly the proof of Corollary it follows from the fact that ReLU classifiers are polynomial- time classifiers (w.rt. the size of the tuple).
G FULL EXPERIMENTAL SETUP
All our code is written in Python + PyTorch (Paszke et al. 2019), with the exception of the MIPVerify interface, which is written in Julia. When possible, most experiments were run in parallel, in order to minimize execution times.
Models All models were trained using Adam (Kingma & Ba 2014) and dataset augmentation. We performed manual hyperparameter and architecture search to find a suitable compromise between accuracy and MIPVerify convergence. The process required approximately 4 months. When performing adversarial training, following (Madry et al. 2018) we used the final adversarial example found by the Projected Gradient Descent attack, instead of the closest. To maximize uniformity, we used for each configuration the same training and pruning hyperparameters (when applicable), which report in Table I We report the chosen architectures in Tables 2 and while Table 4 outlines their accuracies and parameter counts.
UG100 The first 250 samples of the test set of each dataset were used for hyperparameter tuning and were thus not considered in our analysis. For our G100 dataset, sampled uniformly across each ground truth label and removed the examples for which MIPVerify crashed. Table details the composition of the dataset by ground truth label.
Attacks For the Basic Iterative Method (BIM), the Fast Gradient Sign Method (FGSM) and the Projected Gradient Descent (PGD) attack, we used the implementations provided by the AdverTorch library (Ding et al., 2019). For the Brendel Bethge (B&B) attack and the Deepfool (DF) attack, we used the implementations provided by the Foolbox Native library (Rauber et al. 2020). The Carlini Wagner and the uniform noise attacks were instead implemented by the authors. We modified the attacks that did not return the closest adversarial example found (i.e. BIM, Carlini & Wagner, Deepfool, FGSM and PGD) to do so. For the attacks that accept as a parameter (i.e. BIM, FGSM, PGD and uniform noise), for each example of e, followed by a binary search. In order to pick the attack parameters, we first selected the strong by performing an extensive manual search. The process took approximately 3 months. We then modified the strong set in order to obtain the balanced parameter set. We report the parameters of both sets (as well as the parameters of the binary and decay searches) in Table
first performed initial search with decaying value
MIPVerify We ran MIPVerify using the Julia library MIPVerify.jl jl and Gurobi (Gurobi Optimization
LLC, 2022). Since MIPVerify can be sped up by providing a distance upper bound, we used the same pool of adversarial examples utilized throughout the paper. For CIFAR10 we used the strong parameter set, while for MNIST we used the strong parameter set with some differences (reported in Table(7). Since numerical issues might cause the distance upper bound computed by the heuristic attacks to be slightly different from the one computed by MIPVerify, we runs, each with a different correction factor (1.05, 1.25, 1.5, 2). and picked the first factor that caused MIPVerify to find feasible (but not necessarily optimal) solution. If the solution was not optimal, we then performed a main run with higher computational budget. We provide the parameters of MIPVerify in Table We also report in Table the percentage of tight bounds for each combination.
series of exploratory
25

---

Under review as a conference paper at ICLR 2023
Table I: Training and pruning hyperparameters.
Value
Parameter Name
MNIST
CIFAR10
Common Hyperparameters
Epochs
425
Learning Rate
le-4
Batch Size
32
128
Adam
(0.9, 0.999)
Flip %
50%
Translation Ratio
0.1
Rotation (deg.)
15
Adversarial Hyperparameters (Adversarial and ReLU only)
Attack
PGD
Attack #lterations
200
Attack Learning Rate
0.1
Adversarial Ratio
1
0.05
2/255
ReLU Hyperparameters (ReLU only)
LI Regularization Coeff.
2e-5
le-5
RS Loss Coeff.
1.2e-4
1e-3
Weight Pruning Threshold
le-3
ReLU Pruning Threshold
90%
Table 2: MNIST Architectures.
(a) MNIST A
Input
Flatten
Linear (in 784, out 100)
ReLU
Linear (in 100, out 10)
Output
(b) MNIST B
Input
Conv2D (in = out 4, 5x5 kernel, stride = 3, padding 0)
ReLU
Flatten
Linear (in = 256, out = 10)
Output (c) MNIST C
Input
Conv2D (in = 1, out 8, 5x5 kernel, stride 4, padding 0)
ReLU
Flatten
Linear (in = 288, out = 10)
Output
26

---

Under review as a conference paper at ICLR 2023
Table CIFARIO architectures.
(a) CIFARIO A
Input
Conv2D (in = out 8, 3x3 kernel, stride = 2, padding 0)
ReLU
Flatten
Linear (in 1800, out 10)
Output
(b) CIFARIO
Input
Conv2D (in = 3, out 20, 5x5 kernel, stride 4, padding = 0)
ReLU
Flatten
Linear (in = 980, out = 10)
Output
(c) CIFARIO
Input
Conv2D (in
8, 5x5 kernel, stride padding
ReLU
Conv2D (in out 8, 3x3 kernel, stride 2, padding 0)
ReLU
Flatten
Linear (in = 72, out 10)
Output
Table 4: Parameter counts and accuracies of trained models.
Architecture
#Parameters
Training
Accuracy
Standard
95.87%
MNIST A
79510
Adversarial
94.24%
ReLU
93.57%
Standard
89.63%
MNIST
2674
Adversarial
84.54%
ReLU
83.69%
Standard
90.71%
MNIST C
3098
Adversarial
87.35%
ReLU
85.67%
Standard
53.98%
CIFAR1O A
18234
Adversarial
50.77%
ReLU
32.85%
Standard
55.81%
CIFARIO B
11330
Adversarial
51.35%
ReL.U
37.33%
Standard 47.85%
CIFARIO
1922
Adversarial
45.19%
ReLU
32.27%
27

---

Under review as a conference paper at ICLR 2023
Table 5: Ground truth labels of the UG100 dataset.
(a) MNIST
(b) CIFARIO
Ground Truth
Count
%
Ground Truth
Count
%
0
219
9.77%
Airplane
228
10.05%
228
10.17%
Automobile
227
10.00%
2
225
10.04%
Bird
228
10.05%
3
225
10.04%
Cat
228
10.05%
225
10.04%
Deer
226
9.96%
5
220
9.82%
Dog
227
10.00%
227
10.13%
Frog
227
10.00%
7
221
9.86%
Horse
227
10.00%
225
10.04%
Ship
225
9.92%
9
226
10.08%
Truck
226
9.96%
H QUANTILE-BASER CALIBRATION
The buffer function in CA can be empirically calibrated so as to control the chance of false positives (i.e. inputs wrongly reported not robust) and false negatives (i.e. non-robust inputs reported as being robust).
Given the strong correlation that observed between the distance of heuristic adversarial examples and the true decision boundary distance, using linear model for 6, seems a reasonable choice. Under this assumption, the buffer value depends only on the distance between the original example and the adversarial one, i.e. on d(x, (x)). This property allows us to rewrite the main check performed by CA as:
- - b(x) = an - af,(0), Se
(59)
The parameters @1, can then be obtained via quantile regression (Koenker & Bassett Jr using the true decision boundary distance (i.e. (x)) as a target.
1978 by
The approach provides simple, interpretable mechanism to control how conservative the detection check should be: with small quantile, CA will tend to underestimate the decision boundary distance, leading to fewer missed detections, but more false alarms; using a high quantile will lead to the opposite behavior.
We test this type of buffer using 5-fold cross-validation each configuration. Specifically, calibrate the model using 1%, 50% and 99% as quantiles. Tables [0 to [3] provide a comparison between the expected quantile and the average true quantile of each configuration the validation folds. Additionally, we plot in Figures to 8 the mean Fi score in relation to the choice of
I ADDITIONAL RESULTS
Tables 14 to 17 detail the performance of the various attack sets on every combination, while Figures to 14 showcase the relation between the true and estimated decision boundary distances.
J ABLATION STUDY
We outline the best attack pools by size in Tables 18 to 21 Additionally, we report the performance
of pools composed of individual attacks in Tables 22 25
Finally, detail the performance of
dropping specific attack in Tables 26 to 29
K FAST PARAMETER SET TESTS
We list the chosen parameter sets for Fast-100, Fast- Ik and Fast-10k in Table 30
We plot the difference between the distance of the closest adversarial examples and the true decision boundary
28

---

Under review as a conference paper at ICLR 2023
Table 6: Parameters of heuristic attacks.
MNIST
CIFAR10
Attack
Parameter Name
Strong
Balanced
Strong
Balanced
Initial Search Factor
0.75
Initial Search Steps
30
BIM
Initial Search Factor
0.75
Binary Search Steps
20
#lterations
2k
200
5k
200
Learning Rate
1e-3
le-2
le-5
le-3
Initial Attack
Blended Noise
Overshoot
1.1
LR Decay
0.75
Brendel & Bethge
LR Decay Every Steps #lterations
50
5k
200
5k
200
Learning Rate
le-3
le-3
le-5
le-3
Momentum
0.8
Initial Directions
1000
Init Steps
1000
Minimum т
le-5
Initial
1
т Factor
0.95
0.9
0.99
0.9
Initial Const
le-5
Const Factor
2
Maximum Const
20
Reduce Const
False
Carlini & Wagner
Warm Start
True
Abort Early
True
Learning Rate
le-2
le-2
le-5
lc-4
Max Iterations
1k
100
5k
100
T Check Every n Steps
Const Check Every n Steps
5
Iter. Check Every n Steps
Disabled
#lterations
5k
Candidates
Deepfool
Overshoot
le-5
Loss
Logits
Initial Search Factor
0.75
FGSM
Initial Search Steps
30
Initial Search Factor
0.75
Binary Search Steps Starting E
20
1
Initial Search Factor
0.75
Initial Search Steps Initial Search Factor
30
0.75
PGD
Binary Search Steps
20
#lterations
5k
200
5k
200
Learning Rate
le-4
le-3
lc-4
le-3
Random Initialization
True
Initial Search Factor
0.75
Initial Search Steps
30
Uniform Noise
Initial Search Factor
0.75
Binary Search Steps
20
Runs
8k
200
8k
200
29

---

Under review as a conference paper at ICLR 2023
Table 7: Parameter set used to initialize MIPVerify for MNIST. All other parameters identical to the strong MNIST attack parameter set.
Attack Name
Parameter Name
Value
#lterations
5k
BIM
Learning Rate
le-5
Brendel Bethge
Learning Rate
le-3
Tau Factor
0.99
Carlini & Wagner
Learning Rate
le-3
#lterations
5k
Table 8: Parameters of MIPVerify.
Value
Parameter Name
Exploration
Main
Absolute Tolerance
le-5
Relative Tolerance
le-10
Threads
Timeout
120
7200
Tightening Absolute Tolerance
le-4
Tightening Relative Tolerance
le-10
Tightening Timeout (s)
20
240
Tightening Threads
Table 9: MIPVerify bound tightness statistics.
Architecture
Training
% Tight
Standard
95.40%
MNIST A
Adversarial
99.60%
ReLU
82.46%
Standard
74.61%
MNIST B
Adversarial
85.68%
ReLU
75.55%
Standard
86.21%
MNIST C
Adversarial
97.28%
ReLUU
95.63%
Standard
81.18%
CIFARIO
Adversarial
82.50%
ReLU
92.73%
Standard
56.32%
CIFARIO
Adversarial
58.88%
ReLU
81.67%
Standard
100.00%
CIFARIO C
Adversarial
100.00%
ReLU
100.00%
30

---

Under review as a conference paper at ICLR 2023
Table 10: Expected vs true quantile for MNIST strong with 5-fold cross validation.
Architecture
Training
Expected Quantile
True Quantile
1.00%
0.99#1 1.2%
Standard
50.00%
49.93+2.35%
99.00%
95.60+3.77%%
1.00%
1.11=0.53%
A
Adversarial
50.00%
50.25+1.58%%
99.00%
89.8416.42%%
1.00%
1.11#0.45%
ReLU
50.00%
50.02+1.72%
99.00%
91.95+5.644 6.6%
1.00%
1.07:0.48%
Standard
50.00%
49.80 00,8000.766 76%
99.00%
97.76+0.71
1.00%
1.22+1.00 .01 %
B
Adversarial
50.00%
49.8 29.88+4.663 4.63%
99.00%
98. 98.10+0.36%
1.00%
1.04+0.774 77%%
ReLU
50.00%
49.98+3.
99.00%
97.69+1.418
1.00%
1.07+00.7%%
Standard
50.00%
50.17+1 .64%
99.00%
98.73+0.42%%
1.00%
1.05:
Adversarial
50.00%
49.87+3.588
99.00%
99.00+0.479%
1.00%
1.06+0.67%%
ReLU
50.00%
50.02+1 .85%
99.00%
93.9943.51 1%
31

---

Under review as a conference paper at ICLR 2023
Table 11: Expected vs true quantile for MNIST balanced with 5-fold cross validation.
Architecture
Training
Expected Quantile
True Quantile
1.00%
1.30#0.79% 49.98+3. 10%
Standard
50.00%
99.00%
93.99+2.59%
1.00%
0.97=0.40%
A
Adversarial
50.00%
50. 10.1121.11 14%
99.00%
90.44+1.9099
1.00%
1.0240.31
ReLU
50.00%
50,02+ 1.05%
99.00%
95. 15+2.22822%
1.00%
1.0340.36%
Standard
50.00%
49.98&0.mm 70%
99.00%
98.88+0.455 45%%
1.00%
1.17=0.97%
B
Adversarial
50.00%
50. 1.:44.54%
99.00%
98.69+0.59%
1.00%
1.04+0.49%
ReLU
50.00%
50.34+2.4999
99.00%
98.73+0.53%
1.00%
1.07+0.33%
Standard
50.00%
49.98+0.91 %
99.00%
98.88+0.55%
1.00%
1.1020.37%
Adversarial
50.00%
50.1244.1 15%
99.00%
99.00#0.355
1.00%
1.06+0.679%
ReLU
50.00%
50.
101112+2667 2...67%
99.00%
98.62+0.5005
32

---

Under review as a conference paper at ICLR 2023
Table 12: Expected vs true quantile for CIFARIO strong with 5-fold cross validation.
Architecture
Training
Expected Quantile
True Quantile
1.00%
1.09=0.86%%
Standard
50.00%
50.09 84%
99.00%
98.82+0.66
1.00%
1.05#0.239%
A
Adversarial
50.00%
49.86#3.599 3.5%%
99.00%
08.90=0.6255
1.00%
0.97+0.4
ReLU
50.00%
49.93+3.Mm 49%%
99.00%
97.66*1.35%4
1.00%
0.98+0.18%
Standard
50.00%
49.9 19.91=1.111 18%
99.00%
98. 08.84+0.56%
1.00%
0.91+0.4883 +0.48%
B
Adversarial
50.00%
50.00
99.00%
98.69+0.722 72%
1.00%
1.10=0.72%
ReLU
50.00%
49.98+2.22
99.00%
98.85+0.61 %
1.00%
0.93+0.60%
Standard
50.00%
50.00 1.66
99.00%
98.71+0.71 %
1.00%
1.0920.17%9
Adversarial
50.00%
50.1442.6 %
99.00%
98.27+0.88 81 %
1.00%
1.01+0.6255
ReLU
50.00%
50.02+2.0 09%
99.00%
96.1742.44 17.1..4.40%
33

---

Under review as a conference paper at ICLR 2023
Table 13: Expected vs true quantile for CIFARIO balanced with 5-fold cross validation.
Architecture
Training
Expected Quantile
True Quantile
1.00%
0.95#0.61% 50.32+2.38%%
Standard
50.00%
99.00%
98.87=0.59%%
1.00%
1.05+0.23%
A
Adversarial
50.00%
50.23+2.655
99.00%
98.81+0.96%%
1.00%
4.1445.3200
ReLU
50.00%
50.37
99.00%
94.62+2.87%
1.00%
1.0=+0.6%%
Standard
50.00%
49.91+2.78%
99.00%
98.93+0.73%
1.00%
1.13+00557%
B
Adversarial
50.00%
50.18
99.00%
08.82+0.711
1.00%
1.23++0.384
ReLU
50.00%
50. +0.38%
99.00%
98.77+0.51 %
1.00%
0.98+0.50%%
Standard
50.00%
20.0992.211 %
99.00%
98.85+0.439
1.00%
1.09+0.26%
Adversarial
50.00%
49.9 19.96+2.722
99.00%
98. 86.66%0
1.00%
1.01+0.36%
ReLU
50.00%
49.93 .60%%
99.00%
97.93+0.633
Table 14: Performance of the strong attack on MNIST.
Architecture
Training
Success Rate
Difference % Below 1/255
R
Standard
100.00%
1.51%
98.16%
0.996
MNIST
Adversarial
100.00%
2.48%
81.43%
0.994
ReLU
100.00%
2.14%
84.33%
0.995
Standard
100.00%
3.38%
97.36%
0.995
MNIST B
Adversarial
100.00%
4.34%
75.09%
0.991
ReLU
100.00%
4.80%
68.02%
0.992
Standard 100.00%
4.52%
96.92%
0.996
MNIST C
Adversarial
100.00%
8.76%
48.78%
0.981
ReLU
100.00%
4.84%
68.24%
0.988
34

---

Under review as a conference paper at ICLR 2023
0.96
0.95
Mean Fi
Mean
0.85
0.85
1%
50%
50%
99%
99%
6
8
10
8
10
-10-2
-10-
(a) MNIST A Standard Strong
(b) MNIST A Standard Balanced
0.95
0.95
Mean Fi
Mean
0.85
1%
50%
50%
90%
0.8
10
15
20
25
-10
-10
(c) MNIST A Adversarial Strong
(d) MNIST A Adversarial Balanced
0.95
0.95
Mdean Fi
Mean Fi
0.9
0.9
1%
1%
50%
50%
90%
99%
0.8
0.8
-10-2
-10-a
(c) MNIST A ReLU Strong
MNIST ReLU Balanced
Figure 3: Fi scores in relation to for MNIST A for each considered percentile. For ease of visualization, we the graph cutoff at 0.8. We also mark 8/255 (a common choice for E) with a dotted line.
35

---

Under review as a conference paper at ICLR 2023
0.96
0.95
Mean Fi
Mean
0.9
0.85
1%
50%
50%
99%
99%
0.8
6
2
8
10
14
-10-2
-10
(a) MNIST B Standard Strong
(b) MNIST B Standard Balanced
0.95
0.95
Mean F1
Mean Fr
0.9
0.9
0.85
1%
0.85
50%
50%
90%
99%
0.8
0.8
10
20
30
25
30
-10
-10
(c) MNIST B Adversarial Strong
(d) MNIST Adversarial Balanced
0.95
0.95
Mdean Fi
Mean Fi
0.9
0.9
1%
1%
50%
50%
90%
99%
0.8
0.8
-10-2
-10-a
(c) MNIST B ReLU Strong
MNIST ReLU Balanced
Figure 4: Fi scores in relation to E for MNIST B for each considered percentile. For ease of visualization, we the graph cutoff at 0.8. We also mark 8/255 (a common choice for E) with a dotted line.
36

---

Under review as a conference paper at ICLR 2023
0.96
0.95
Mean Fi
Mean
0.85
0.85
1%
50%
50%
99%
99%
2
8
10
12
10
12
-10-2
-10
(a) MNIST C Standard Strong
(b) MNIST C Standard Balanced
0.95
0.95
Meau Fr
Mean
0.9
0.85
0.85
50%
50%
90%
10
15
25
5
20
-10
-10
(c) MNIST C Adversarial Strong
(d) MNIST C Adversarial Balanced
0.95
0.95
Mdean Fi
Mean Fi
0.9
0.9
1%
1%
50%
50%
90%
99%
0.8
0.8
-10-2
-10-2
(c) MNIST C ReLU Strong
MNIST ReLU Balanced
Figure 5: Fi scores in relation to E for MNIST C for each considered percentile. For ease of visualization, we the graph cutoff at 0.8. We also mark 8/255 (a common choice for E) with a dotted line.
37

---

Under review as a conference paper at ICLR 2023
0.95
0.95
Meen Fi
Moan Fi
0.9
0.9
0.85
0.85
50%
-10-2
-10-2
(a) CIFARIO A Standard Strong
(b) CIFARIO A Standard Balanced
0.95
0.95
Mean Fi
Mean
0.9
0.85
1%
50%
50%
99%
0.8
2
8
14
2
14
-10
(c) CIFARIO A Adversarial Strong
(d) CIFARIO Adversarial Balanced
0.95
0.95
Mean F1
Mean Fi
0.9
0.9
0.85
1%
0.85
1%
30%
50%
99%
99%
2
8 10
14
2
8
10
12
14
-10
-10
(c) CIFARIO A ReLU Strong
(f) CIFARIO A ReLU Balanced
Figure 6: F, scores in relation to e for CIFARIO for each considered percentile. For ease of visualization, we set the graph cutoff at Fi 0.8. We also mark 8/255 (a common choice for e) with a dotted line.
38

---

Under review as a conference paper at ICLR 2023
0.95
0.95
Meaa Fi
Moun Fi
0.9
0.9
0.85
0.83
-10
-10-2
(a) CIFARIO B Standard Strong
(b) CIFARIO B Standard Balanced
0.95
0.95
Mean F
Meen
0.9
0.85
1%
0.85
1%
50%
50%
99%
99%
2
1
6
8
10
12
2
6
10
12
-10
(c) CIFARIO B Adversarial Strong
(d) CIFARIO Adversarial Balanced
0.95
0.95
Mean Fi
Mean
0.85
1%
0.85
1%
50%
50%
95%
99%
10
12
6
8
10
12
-10-2
-10=2
(e) CIFARIO B ReLU Strong
(1) CIFARIO ReLU Balanced
Figure Fj scores in relation to e for CIFAR1O for each considered percentile. For ease of visualization, we set the graph cutoff at Fj 0.8. We also mark 8/255 (a common choice for E) with dotted line.
39

---

Under review as a conference paper at ICLR 2023
0.95
Mesa Fi
Mean Fi
0.9
0.85
0.85
1%
50%
50%
99%
99%
-10-2
-10-2
(a) CIFAR1O C Standard Strong
(b) CIFARIO C. Standard Balanced
0.96
0.95
Mean Fi
Meaa
0.85
0.85
1%
50%
50%
91%
99%
2
6
2
8
10
-10-2
-10-2
(c) CIFARI0 C Adversarial Strong
(d) CIFAR10 C. Adversarial Balanced
0.95
0.95
Mean Fi
Mean
0.85
0.85
50%
99%
0.8
0.8
5
15
10
15
.10
-10
(c) CIFARIO C ReLU Strong
(f) CIFARIO C ReLU Balanced
Figure 8: F, scores in relation to e for CIFARIO for each considered percentile. For ease of visualization, we the graph cutoff at Fi 0.8. We also mark 8/255 (a common choice for e) with a dotted line.
40

---

Under review as a conference paper at ICLR 2023
Table 15: Performance of the balanced attack set MNIST.
Architecture
Training
Success Rate
Difference
Below 1/255
R²
Standard
100.00%
1.68%
97.94%
0,995
MNIST A
Adversarial
100.00%
2.87%
77.64%
0.993
ReLU
100.00%
2.55%
80.86%
0.993
Standard
100.00%
4.09%
96.55%
0.995
MNIST B
Adversarial
100.00%
4.90%
72.60%
0.988
ReLU
100.00%
5.53%
62.96%
0.989
Standard 100.00%
5.43%
96.04%
0.995
MNIST C
Adversarial
100.00%
9.50%
48.43%
0.977
ReLU
100.00%
5.28%
66.96%
0.986
Table 16: Performance of the strong attack set on CIFAR1O.
Architecture
Training
Success Rate
Difference
Below 1/255
R²
Standard
100.00%
1.62%
100.00%
0.999
CIFARIO A
Adversarial
100.00%
4.42%
95.88%
0.995
ReLU
100.00%
0.26%
100.00%
1.000
Standard
100.00%
1.44%
100.00%
0.999
CIFARIO
Adversarial
100.00%
3.17%
97.69%
0.997
ReLU
100.00%
1.38%
98.81%
0.999
Standard 100.00%
2.11%
100.00%
0,999
CIFARIO
Adversarial
100.00%
3.10%
97.14%
0.996
ReLU 100.00%
2.35%
96.12%
0.990
Table 17: Performance of the balanced attack set on CIFARIO.
Architecture
Training
Success Rate
Difference % Below 1/255
R
Standard
100.00%
1.71%
100.00%
0.999
CIFAR1O A
Adversarial
100.00%
4.18%
96.57%
0.995
ReLU
100.00%
0.18%
100.00%
1.000
Standard
100.00%
1.53%
100.00%
0.999
CIFARIO B
Adversarial
100.00%
2.92%
98.46%
0,996
ReLU
100.00%
1.19%
98.94%
0.999
Standard
100.00%
2.06%
100.00%
0.999
CIFAR1O C
Adversarial
100.00%
3.12%
97.28
0.996
ReLU
100.00%
1.45%
97.44%
0.995
Table 18: Best pools of given size by success rate and R² for MNIST strong.
Attacks
Success Rate
Difference
1/255
R²
PGD
100.00+0.000
10.98
51 31.83327.78%
0.975+0.010
C&W, PGD
(00.00=0.0055
7.99+3.31 %
60.68+25.43%
0.986+0.005
B&B, C&W, PGD
100.00+0.000)
4.71+1.97%
17.97+15.52%
0.989+0.004
4
B&B, C&W, DE, PGD
100.00=0.00 00%%
4.36+2.03%
79.02+15.62%%
0.991#0.005
No FGSM, Uniform
100.00+0.000
4.09+2.02%
79.81+15.70%
0.992+0.008
No Uniform
100.00+0.009,
4.09+2.02%
75.81+15.70%
0.992+0.00
All
100.00+0.00%
4.09+2.02%
79.81+15.70%
0.992+0.00
41

---

Under review as a conference paper at ICLR 2023
-10-2 2
-10
Estimated Distance
Estimated Distance
4
2
0
2
6
0
2
6
True Distance
-10-2
True Distance
-10 2
(a) MNIST A Standard Strong
(b) MNIST A Standard Balanced
2
2
20
20
Esthnated Distance
Estimated Distance
13
15
10
10
5
5
0-
0
10
15
20
0
10
15
20
True Distance
-10-2
True Distance
-10-2
(c) MNIST A Adversarial Strong
(d) MNIST A Adversarial Balanced -10
-10-2
30
30
Estimated Distance
Estimated Distance
20
20
10
10
0
15
20
25
30
20
30
True Distance
-10-2
True Distance
-10-2
(c) MNIST A ReLU Strong
MNIST ReLU Balanced
Figure 9: Decision boundary distances found by the attack pools compared to those found by MIPVerify on MNIST A. The black line represents the theoretical optimum. Note that no samples are below the black line.
42

---

Under review as a conference paper at ICLR 2023
-10-2
-10-2
Estimated Distance
10
Estimated Distance
10
5
12
True Distance
-10
True Distance
-10
(a) MNIST Standard Strong
(b) MNIST B Standard Balanced
-10-2
-10
30
30
Estimated Distance
Estimated Distance
20
20
10
10
25
10
20
True Distance
-10-2
True Distance
-10-2
(c) MNIST B Adversarial Strong
(d) MNIST Adversarial Balanced
10-2
-1022
30
30
Estimated Distance
Estimated Distance
20
20
10
10
0
15
20
25
30
0
15
20
30
True Distance
-10
True Distance
-10
(c) MNIST B ReLU Strong
(1) MNIST B ReLU Balanced
Figure 10: Decision boundary distances found by the attack pools compared to those found by MIPVerify on MNIST B. The black line represents the theoretical optimum. Note that no samples are below the black line.
43

---

Under review as a conference paper at ICLR 2023
2
Estimated Distance
Estimated
4
4
0
0
4
8
True Distance
-10
True Distance
-10
(a) MNIST C Standard Strong
(b) MNIST C Standard Balanced
2
20
20
Esthnnted Distance
Estimated Distance
15
15
10
10
0-
0
5
10
15
20
0
5
10
15
20
True Distance
-10-2
True Distance
-10-2
(c) MNIST C Adversarial Strong
(d) MNIST C Adversarial Balanced
-10-2
-10
30
Estimated Distance
Pxtimated Distance
20
10
10
0
10
25
20
25
30
Distance
-10-2
True Distance
-10-2
(c) MNIST C ReLU Strong
MNIST ReLU Balanced
Figure 11: Decision boundary distances found by the attack pools compared to those found by MIPVerify on MNIST C. The black line represents the theoretical optimum. Note that no samples are below the black line.
44

---

Under review as a conference paper at ICLR 2023
-10-2
-10-2
2-
Estinsted
Estimated
0
2
True Distance
-10
True Distance
-10
(a) CIFARIO Standard Strong
(b) CIFARIO A Standard Balanced
-1-2
-10-2
Estimated Distauce
Estimated Distaure
True Distance
-10
True Distance
-10
(c) CIFAR 10 A Adversarial Strong
(d) CIFARIO Adversarial Balanced
-10-
-10-2
13
15
Estimated Distence
Estimated Distance
10
10
5-
5
0
0
0
6
12
14
0
6
12
14
True Distance
-10-2
True Distance
-10-2
(e) CIFARIO A ReLU Strong
(f) CIFARIO A ReLU Balanced
Figure 12: Decision boundary distances found by the attack pools compared to those found by MIPVerify CIFARIO A. The black line represents the theoretical optimum. Note that no samples are below the black line.
45

---

Under review as a conference paper at ICLR 2023
-10-2
-10-2
Estimated Distance
Estimated Distance
1.5
1.5
True Distance
-10-2
True Distance
-10-2
(a) CIFARIO Standard Strong
(b) CIFARIO B Standard Balanced
-10-1
-10-2
Estimsted Distance
Estimsted Distance
0
3
4
0
2
5
True Distance
-10-2
True Distance
-10
(c) CIFARIO B Adversarial Strong
(d) CIFARIO B Adversarial Balanced
-10-2
-10-2
Estimated Distance
Estimated Distance
10
10
Zook.
12
14
12
14
True Distauce
True Distauce
-10"
(e) CIFARIO B ReLU Strong
(I) CIFARIO ReLU Balanced
Figure 13: Decision boundary distances found by the attack pools compared to those found by MIPVerify on CIFARIO B. The black line represents the theoretical optimum. Note that no samples below the black line.
46

---

Under review as a conference paper at ICLR 2023
-10
-10
1800
Estinsted
Estimated
1
2
3
1
2
3
True Distance
-10-2
True Distance
-10-2
(a) CIFARIO Standard Strong
(b) CIFARIO Standard Balanced
-10
-10-2
Estimated Distauce
Esstiaated Distanre
4
2
4
True Distance
.10
True Distance
-10
(c) CIFARIO C Adversarial Strong
(d) CIFARIO Adversarial Balanced
-10-2
-10-2
15
15
Estimated Distance
Estimated Distance
10
10
3-
0-
0
0
10
15
0
5
10
True Distance
-10-2
True Distance
-10-2
(e) CIFARIO C ReLU Strong
(I) CIFARIO C ReLU Balanced
Figure Decision boundary distances found by the attack pools compared to those found by MIPVerify on CIFARIO C. The black line represents the theoretical optimum. Note that no samples are below the black line.
47

---

Under review as a conference paper at ICLR 2023
Table 19; Best pools of given size by success rate and R for MNIST balanced.
72
Attacks
Success Rate
Difference
1/255
R
BIM
100.00=0.00%
11.72+4.18%
50.92+26.43%
0.965#0.010
BIM, B&B
100.00=0.0095
6.11+2.28%
73.23+15.909%
0.980=0.007
BIM, B&B, C&W
100.00=0.000 00%
5.29+2.06%
75.72+ 10%%
0.986+0.00
BIM. B&B, C&W, DF
100.00=0.009%
4.85+2.10%
17.33+15.85%
0.989#0.005
No FGSM, Uniform
100.00=0.00%
4.65+2.16%
17.78=16.08%
0.990+0.000
6
No Uniform
100.00=0.005
4.65+2.16%
77.78
0.990=0.006
All
100.00=0.005%
4.65+2.16%
77.78#16.08%
0.990+0.006
Table 20; Best pools of a given size by success rate and R for CIFARIO strong.
Attacks
Success Rate
Difference
1/255
R²
DF
100.0000.00%%
6.11+3.49%
95.06+4.819
0.989#0.011
2
DE, PGD
100.00=0.000
4.71+2.37%
96.3243.56%%
0.995=0.007
3
C&W, DE, PGD
100.00=0.009
2.54+1.30%
98.1742.009%
0.996#0.006
4
B&B, C&W, DF, PGD
0et.0000.0050
2.21#1.16%
98.40=1.63%
0.997
5
No FGSM, Uniform
1.0.0000.00P0
2.21+1.16%
98.40=1.63%%
0,997=0.000
6
No Uniform
100.00=0.00%%
2.21=1.16%
98.40=1.63%
0.997=0.003
7
All
100.00#0.00%%
2.21+1.16%
98.40+1.63%
0.997=0.003
Table 21: Best pools of a given size by success rate and 1t² for CIFARIO balanced.
78
Attacks
Success Rate
Difference
1/255
R²
DF
100.00=0.000 000
6.11=3.4999
95.06+4.811
0.989#0.011
B&B, DF
100.00=0.000
2.52+1.51%
98.23#1.8199
0.995+0.000
BIM, B&B, DF
100.00=0.00%
2.21#1.25%
98.53#1.52%
0.997+0.002
BIM, B&B, C&W, DF
100.00=0.00%%
2.06+1.16%
98.73#1.32%%
0.998+0.002
No FGSM, Uniform
100.00=0.005%
2.04+1.13%
98.74*1.299
0.998
No FGSM
100.00=0.005h
2.04+1.13%
08.74+1.299
0.998+0.002
All
100.00#0.00%
2.04+1.13%
98.74+1.29%
0.99840.002
Table 22: Performance of individual attacks for MNIST strong.
Attack
Success Rate
Difference
1/255
R²
BIM
100.00+0.000
10.90+4.42% 18.50+7.09%
53.57+28.07%
0.96640.012
B&B
99 99.9940.01 %
58.78+9.91%
0.812+0.044
C&W W
100.00+0.009.
17.5242.7499
48.02421.24 22.2
0.910+0.024
Deepfool
100.00+0.00%
21.59+7.739%
44. 44.15+200.026%
0.923+0.027
FGSM
99.72+0.51
44.43+15.76%%
28.20+17.308
0.761
PGD
100.00+0.009
10.98+4.41%
51.83+27.788 78%
0.975#0.010
Uniform
99.5240.9158
414.47+140.54%
0.82+0.55%
0.623
Table 23: Performance of individual attacks for MNIST balanced.
Attack
Success Rate
Difference
1/255
R²
BIM
100.00+0.00%
11.7244.189
50.92426.4344
0.965+0.010
B&B
99.99+0.088
18.65+7.29%
58.43+9.6
0.81240.039
C&W
100.00+0.009%
22.55+3.839%
38.95+22.499 49%
0.90420.025
Deepfool
100.00+0.008
21.59+7.73%
44.15+20.02%
0.923+0.027
FGSM
99.72+0.519%
44.43+11.766%
28.20+17.309%
0.761 1321
PGD
100.00+0.000
16.2346.5994
18.08+28.88%
0.905+0.070
Uniform
98.66+1.99
521.61+181.40%
0.57+0.38%
0.484+0.
48

---

Under review as a conference paper at ICLR 2023
Table 24: Performance of individual attacks for CIFARIO strong.
Attack
Success Rate
Difference
1/255
R²
BIM
91.96+7.40%%
19.9745.95%
80.32+12.97%
0.934+0.041
B&B
100.00=0.000 000%
508. 508.66+196. 196.37%
42.7447.85%
0.174=0.074
C&W
99.98=0.02%
10.6743.64%
90.0945.51%
0.926#0.030
Deepfool
000.00=0.0055
6.11
95.0614.81%
0.989#0.011
FGSM
100.00=0.000 -.0%%
31.80+11.125
69.20=17.72%
0.847#0.122
PGD
100.00=0.009%
19.36#5.999%
77.23
0.952+0.027
Uniform
99.99:0.02%
1206.794277.6%%
2.48+0.88%
0.910#0.044
Table 25: Performance of individual attacks for CIFARIO balanced.
Attack
Success Rafe
Difference
1/255
R²
BIM
100.00=0.00% 000%
19.23+5.92%
77.33
0.954+0.025
B&B
100.00=0.000
50.64452.17%
81.20=10.684
0.615#0.349
C&W
99.89=0.09%
17.44+4.01%
84.82+8.519
0.923+0.026
Deepfool
100.00=0.00%%
6.1113.49%
95.06+4.819%
0.989#0.011
FGSM
100.00=0.00%
31.80=11.12%
69.20=17.72%%
0.847+0.123
PGD
100.00+0.0044
20.1846.56%
76.97=16.07%
0.947+0.031
Uniform
99.85=0.26%%
1617.744390.50%
1.80+0.67%
0.85340.068
Table 26: Performance of pools without a specific attack for MNIST strong.
Dropped Attack
Success Rate
Difference
1/255
R²
None
100.00=0.000 000%
4.0942.02%
79.8 00.81115.70%
0.992+0.00 005
BIM
000.0000.00%
4.35+2.03%
79.02+15.6245
0.991
B&B
100.00=0.005%
6.76+3.31%
64.46+25.01 %
0.990+0.008
C&W
100.00=0.00%
4.65+2.20%
77.70+16.02%
0.989 006
Deepfool
100.00#0.00 00%0
4.33+1.97%
79.04+15.75c0
0.990#0.00 004
FGSM
100.00=0.009%
4.09+2.02%
79.81
0.992+0.009
PGD
100.00=0.009%
4.2621.999
79.36#15.599
0.991
Uniform
100.00+0.00%%
4.09+2.02%
79.81
0.992+0.005
Table 27: Performance pools without specific attack for MNIST balanced.
Dropped Attack
Success Rate
Difference
1/255
R²
None
100.00=0.00% 000%
4.65+2.163
77.78+16.08%
0.990+0.00k
BIM
100.00=0. 0..0%
5.13+2.27%
76.14+15.988
0.988+0.000 0.0
B&B
100.00=0.00 000%
7.93+3.69%
60.79+25.999 99.9%
0.987+0.000
C&W
100.00=0.00%
4.93+2.22%
77.05+15.96%
0.988+0.006
Deepfool
100.00=0.00%
5.03+2.14%
76.34+16.36%
0.988+0.005
FGSM
100.00+0.000
4.65+2.16%
17.78+16.08%
0.990#0.006
PGD
100.00=0.00%
4.85+2.
77.33+15.855
0.989+0.005
Uniform
100.00+0.009f
4.65+2.169
77.78+16.08%
0.990+0.006
49

---

Under review as a conference paper at ICLR 2023
Table 28: Performance of pools without a specific attack for CIFARIO strong.
Dropped Attack
Success Rate
Difference
1/255
R
None
100.00=0.009
1.21 16%
98.4041. .63%
0.997+0.003
BIM
100.00=0.009:
2.21
1.63%
0.997+0.003
B&B
100.00=0.005
2.54#1.300
98. 98.1722000%
0.996
C&W
100.00=0.00%
3.83+2.06%
96. 96.84%3.12%
0.996+0.000
Deepfool
100.00=0.00%
95.65+3.10% 1.02+1.19%
0.992#0.005
FGSM
100.00#0.00%
2.21+1.16%
98.40#1.63%
0.99740.003
PGD
100.00=0.00%
2.50=1.4889
98. 1.93%
0.995#0.005
Uniform
100.00+0.00%
1.61+
18.60%
0.99740.003
Table 29; Performance of pools without specific attack for CIFAR10 balanced.
Dropped Attack
Success Rate
Difference
1/255
R
None
100.00=0.005
2.04#1.13%
98.74+1.29%%
0.998+0.000
BIM
100.00=0.005
2.07=1.15%
98.72+1.311 %
0.998#0.002
B&B
100.00=0.00%
4.08+1.952
97.26+22.70%
0.996+0.000
C&W
100.00=0.009
2.18
18.54+11.50%
0.997+0.002
Deepfool
100.00#0.009%
4.00
95. 13.8933.13%
0.993+0.003
FGSM
100.00=0.005
2.04+1.13%
08.74+1.2994
0.998+0.002
PGD
100.00+0.009.
1.06+1.16%
98.73+1.325
0.998+0.002
Uniform
100.00=0.00%
2.04+1.13%
98.74+1.2998
0.998+0.002
distance in Figures 15 to 23
We do not study the Brendel & Bethge the Carlini & Wagner attacks due to the fact that the number of model calls varies depending on how many inputs are attacked at the same time. Note that, for attacks that do not have the 100% success rate, the mean adversarial example distance can increase with the number of steps as new adversarial examples (for inputs for which there were previously no successful adversarial examples) are added.
while we plot the R²2 values in Figures 24 to 32
L RESULTS FOR ATTACKS AGAINST CA
We report the parameters for the variant of our attack in Table 31 while we report its success rate in Table 32) We set e' equal to (0.025, 0.05, 0.1) for MNIST and {2/255, 4/255, 8/255] for CIFAR 10. Note that, since Deepfool is a deterministic attack, no measures against randomizations taken.
50

---

Under review as a conference paper at ICLR 2023
Table 30: Parameters for the Fast-100, Fast- Ik and Fokt-10k sets.
MNIST
CIFARIO
Attack
Parameter Name
100
1k
10k
100
1k
10k
Initial Search Factor
N/A
Initial Search Steps
N/A
Binary Search Steps
10
20
20
10
20
20
BIM
Starting
0.5
0.1
#Iterations
10
50
500
10
50
500
Learning Rate
0.1
0.01
le-3
0.01
le-3
le-3
#lterations
100
500
500
500
Candidates
10
Deepfool
Overshoot
0.1
le-5
le-5
le-4
Loss
Logits
Initial Search Factor
0.75
0.5
Initial Search Steps
30
10
FGSM
Binary Search Steps
20
Starting
0.1
Initial Search Factor
N/A
0.5
0.5
N/A
0.5
0.75
Initial Search Steps
N/A
10
10
N/A
10
30
Binary Search Steps
10
10
10
20
PGD
Starting
0.1
0.1
0.1
#Iterations
10
50
500
10
50
200
Learning Rate
0.1
0.01
1e-3
0.01
1e-3
1e-3
Random Initialization
True
Initial Search Factor
0.75
0.75
0.75
0.25
Initial Search Steps
30
30
30
5
Uniform Noise
Binary Search Steps Starting
20
20
20
15
1
0.5
Runs
200
500
200
10
50
500
Table 31: Parameters for the variant of the PGD attack.
Parameter
Value
X
[10-1 10-2, ,, 102 104)
NES Estimation Samples
200
NES Estimation
10-4
PGD Iterations
400
PGD
10-3
Table 32: Success rate of the pool composed of the anti-CA variant of PGD and uniform noise for the architectures.
Multiplier
Multiplier
1x
2x
5x
10x
1x
2x
5x
10x
0.025
0%
23%
95%
100%
2/255
0%
34%
96%
100%
0.05
3%
41 1
97%
100%
4/255
1%
50%
100%
100%
0.1
2%
50%
96%
100%
8/255
1%
58%
100%
100%
MNIST Standard
(b) CIFARIO Standard
51

---

Under review as a conference paper at ICLR 2023
109
100
Heuristie Distance Exsett Distance
Heuristic Distance Exceet Distance
10-1
10-1
10
10
10-3
10-3
10-4
10a
10a
10
10a
Calls to the Model
Calls to the Model
(a) MNIST A Standard Fast-100
(b) CIFARIO A Standard Fast-100
10
10"
Henristic Distance- Excect Distance
Henristic Distance- Excect Distance
10
10
10-2
10
10-3
10-3
10-1
10a
10a
10
10a
10a
10
Calls to the Model
Calls to the Model
(c) MNIST A Standard Fast-1k
(d) CIFARIO Standard Fast-1k
10
10"
Henristic Distance Exces Distance
Henristic Distance- Excact Distance
10
10
10
10-2
10-3
10
10-4
10a
10
10a
10a
10a
10a
Calls to the Model
Calls to Model
(e) MNIST A Standard Fast-10k
(f) CIFARIO Standard Fast-10k
BIM
Deepfool
Fast Gradient
PGD
Uniform
Figure 15: Mean difference between the distance the closest adversarial examples and the exact decision boundary distance for MNIST & CIFARIO A Standard. A dashed line means that the attack found adversarial examples (of any distance) for only some inputs, while the absence a line means that the attack did not find any adversarial examples. The loosely and densely dotted black lines respectively represent the balanced and strong attack pools. Both axes are logarithmic.
52

---

Under review as a conference paper at ICLR 2023
109
100
Heuriatic Distance Excect Distance
Heuristic Distance Excect Distance
10
10
100
10-2
10-2
10-3
10
10-3
10a
10a
10
10a
Calls to the Model
Calls to the Model
(a) MNIST A Adversarial Fast-100 100
(b) CIFARIO A Adversarial Fast-100
109
109
Henristic Distance Excoct Distance
Henristic Distance- Excect Distance
10
10-2
10
10-3
10
10-3
10
10a
10
10a
10a
10a
Calls to the Model
Calls to the Model
(c) MNIST A Adversarial Fast-lk
(d) CIFARIO A Adversarial Fast-1k
10
10"
Henristic Distance Excact Distance
Henristic Distance- Excact Distanne
10-1
10
10
10
10
10
10-3
10a
16
10a
10a
10a
10a
Calls to the Model
Calls to Model
(e) MNIST Adversarial Fast-10k
(f) CIFARIO A Adversarial Fast-10k
BIM
Deepfool
Fast Gradient
PGD
Uniform
Figure 16: Mean difference between the distance the closest adversarial examples and the exact decision boundary distance for MNIST & CIFAR1O A Adversarial. A dashed line means that the attack found adversarial examples (of any distance) for only some inputs, while the absence of a line means that the attack did not find any adversarial examples. The loosely and densely dotted black lines respectively represent the balanced and strong attack pools. Both axes are logarithmic.
53

---

Under review as a conference paper at ICLR 2023
109
100
Heuristic Distance Excect Distance
Heuristie Distance Excect Distance
10
10
10-
10-2
10
10-8
10a
10a
10
10a
Calls to the Model
Calls to the Model
(a) MNIST A ReLU Fast-100
(b) CIFARIO A ReLU F00
109
10"
Henristic Distance Excoett Distance
Henristic Distance- Exceet Distance
10
10-1
10
10
10-2
10
10-8
10
10a
10
10a
10a
10a
Calls to the Model
Calls to the Model
(C) MNIST ReLU Fast-Ik
(d) CIFARIO A ReLU Fast-lk
10
10P
Henristic Distance Excect Distance
Henristic Distance Excact Distance
10
10
10
10-5
10
10-3
10a
10
10a
10a
10a
10a
Calls to the Model
Calls to Model
(e) MNIST ReLU Fast-10k
(I CIFARIO A ReLU Fast- 10k
BIM
Deepfool
Fast Gradient
PGD
Uniform
Figure 17: Mean difference between the distance the closest adversarial examples and the exact decision boundary distance for MNIST & CIFARIO A ReLU. A dashed line means that the attack found adversarial examples (of any distance) for only some inputs, while the absence a line means that the attack did not find any adversarial examples. The loosely and densely dotted black lines respectively represent the balanced and strong attack pools. Both axes are logarithmic.
54

---

Under review as a conference paper at ICLR 2023
109
100
Heuristic Distance Excec Distance
Heuristic Distance Exceet Distance
10
10
10
10-1
10-3
10a
10a
10
10a
Calls to the Model
Calls to the Model
(a) MNIST B Standard Fast-100 100
(b) CIFAR 10 B Standard Fast-100
10
10"
Henristic Distance Excect Distance
Henristic Distance- Excect Distance
10
10-1
10
10-2
10
10-4
10-3
10
10a
10
10a
10a
10a
Calls to the Model
Calls to the Model
(c) MNIST B Standard Fast-Ik
(d) CIFARIO Standard Fast-Ik
10
109
Henristic Distance Excact Distance
Henristic Distance- Excact Distance
10
10-1
10-2
10-2
10-8
10-3
10
10a
10
10a
10a
10a
10a
Calls to the Model
Calls to Model
(e) MNIST B Standard Fast-10k
CIFARIO Standard Fast-10k
BIM
Deepfool
Fast Gradient
PGD
Uniform
Figure 18: Mean difference between the distance the closest adversarial examples and the exact decision boundary distance for MNIST & CIFARIO 10 B Standard. A dashed line means that the attack found adversarial examples (of any distance) for only some inputs, while the absence a line means that the attack did not find any adversarial examples. The loosely and densely dotted black lines respectively represent the balanced and strong attack pools. Both axes are logarithmic.
55

---

Under review as a conference paper at ICLR 2023
109
100
Heuristie Distance Excect Distance
Heuristic Distance Excect Distance
10
10
10-2
10
10
10
10a
10a
10
10a
Calls to the Model
Calls to the Model
(a) MNIST B Adversarial 100
(b) CIFARIO B Adversarial Fast- 100
10"
10"
Henristic Distance Excoet Distance
Henristic Distance- Excect Distance
10-1
10
10-2
10-3
10
10
10a
10ah
10
10a
10a
10*
Calls to the Model
Calls to the Model
(c) MNIST B Adversarial Fast-lk
(d) CIFARIO B Adversarial Fast-Ik
10
10"
Henristic Distance Excet Distance
Henristic Distance- Excact Distanne
10-1
10
10-2
10-3
10-2
10
10a
16
10a
10a
10a
10a
Calls to the Model
Calls to the Model
(e) MNIST Adversarial Fast-10k
(f) CIFARIO Adversarial Fast-10k
BIM
Deepfool
Fast Gradient
PGD
Uniform
Figure 19: Mean difference between the distance the closest adversarial examples and the exact decision boundary distance for MNIST & CIFARIO B Adversarial. A dashed line means that the attack found adversarial examples (of any distance) for only some inputs, while the absence of a line means that the attack did not find any adversarial examples. The loosely and densely dotted black lines respectively represent the balanced and strong attack pools. Both axes are logarithmic.
56

---

Under review as a conference paper at ICLR 2023
109
100
Heuristie Distance Excect Distance
Heuristic Distance Excect Distance
10
10-1
10
10
10a
10a
10
10a
Calls to the Model
Calls to the Model
(a) MNIST B ReLU Fast-100
(b) CIFARIO B ReLU Fast-100
109
10"
Henristic Distance Excoet Distance
Henristic Distance- Excect Distance
10
10-1
10-2
10-2
10-3
10a
10ah
10
10a
10a
Calls to the Model
Calls to the Model
(c) MNIST ReLU Fast-lk
(d) CIFARIO B ReLU Fast-1k
10"
109
Henristic Distance Excec Distance
Henristic Distance- Excact Distanne
10-1
10-1
10-2
10-2
10-3
10a
10
10a
10a
10a
10a
Calls to the Model
Calls Model
(e) MNIST ReLU Fast-10k
(I CIFARIO B ReLU Fast-10k
BIM
Deepfool
Fast Gradient
PGD
Uniform
Figure 20: Mean difference between the distance the closest adversarial examples and the exact decision boundary distance for MNIST & CIFARIO ReLU. A dashed line means that the attack found adversarial examples (of any distance) for only some inputs, while the absence a line means that the attack did not find any adversarial examples. The loosely and densely dotted black lines respectively represent the balanced and strong attack pools. Both axes are logarithmic.
57

---

Under review as a conference paper at ICLR 2023
109
100
Heuriatic Distance Excet Distance
Heuristic Distance Excect Distance
10
10
10
10-3
10-3
10
10a
10a
10
10
Calls to the Model
Calls to the Model
(a) MNIST C Standard Fast-100
(b) CIFARIO C Standard Fast-100
109
10"
Henristic Distance Excect Distance
Henristic Distance- Excect Distance
10
10-1
10-2
10-2
10-3
10-3
10
10
10ah
10
10a
10a
10a
Calls to the Model
Calls to the Model
(c) MNIST C Standard Fast-Ik
(d) CIFARIO Standard Fast-Ik
10
109
Henristic Distance Excect Distance
Henristic Distance- Excact Distanne
10-1
10
10-2
10
10-3
10-3
10-1
10a
10
10a
10a
10a
10a
Calls to the Model
Calls to the Model
(e) MNIST C Standard Fast-10k
CIFARIO Standard Fast-10k
BIM
Deepfool
Fast Gradient
PGD
Uniform
Figure 21: Mean difference between the distance the closest adversarial examples and the exact decision boundary distance for MNIST & CIFARIO C Standard. A dashed line means that the attack found adversarial examples (of any distance) for only some inputs, while the absence a line means that the attack did not find any adversarial examples. The loosely and densely dotted black lines respectively represent the balanced and strong attack pools. Both axes are logarithmic.
58

---

Under review as a conference paper at ICLR 2023
100
100
Heuristic Distance Exsect Distance
Heuristie Distance Excect Distance
10-1
10-2
10-3
10-2
10
10a
10a
10
10a
Calls to the Model
Calls to the Model
(a) MNIST C Adversarial Fast-100
(b) CIFARIO C Adversarial Fast- 100
10"
10"
Henristic Distance Excoet Distance
Henristic Distance- Excect Distance
10
10
10-2
10-3
10-2
10
10
10a
10
10a
10a
10*
Calls to the Model
Calls to the Model
(c) MNIST C Adversarial Fast-lk
(d) CIFARIO C Adversarial Fast-1k
10
109
Henristic Distance Excet Distance
Henristic Distance- Excact Distanne
10
10
10
10-3
10-2
10
10a
10at
10a
10a
10a
10a
to the Model
Calls Model
(e) MNIST Adversarial Fast-10k
(f) CIFARIO C Adversarial Fast-10k
BIM
Deepfool
Fast Gradient
PGD
Uniform
Figure 22: Mean difference between the distance the closest adversarial examples and the exact decision boundary distance for MNIST & CIFARIO C Adversarial. A dashed line means that the attack found adversarial examples (of any distance) for only some inputs, while the absence of a line means that the attack did not find any adversarial examples. The loosely and densely dotted black lines respectively represent the balanced and strong attack pools. Both axes are logarithmic.
59

---

Under review as a conference paper at ICLR 2023
109
10
Heuristie Distance Excset Distance
Heuristle Distance Excect Distance
10-1
10
10-3
10a
10ah
10
10a
Calls to the Model
Calls to the Model
(a) MNIST C ReLU 100
(b) CIFARIO C ReLU Fast-100
109
10"
Henristic Distance Excoet Distance
Henristic Distance- Excect Distance
10-1
10
10
10
10-3
10a
10ah
10
10a
10a
10a
Calls to the Model
Calls to the Model
(c) MNIST ReLU Fast-Ik
(d) CIFARIO C ReLU Fast-1k
10
109
Henristic Distance Excect Distance
Henristic Distance- Excact Distanne
10-1
10
10-2
10-3
10a
10
10a
10a
10a
10a
Calls to the Model
Calls to Model
(e) MNIST ReLU Fast-10k
(I CIFARIO ReLU Fast-10k
BIM
Deepfool
Fast Gradient
PGD
Uniform
Figure 23: Mean difference between the distance the closest adversarial examples and the exact decision boundary distance for MNIST & CIFARIO ReLU. A dashed line means that the attack found adversarial examples (of any distance) for only some inputs, while the absence a line means that the attack did not find any adversarial examples. The loosely and densely dotted black lines respectively represent the balanced and strong attack pools. Both axes are logarithmic.
60

---

Under review as a conference paper at ICLR 2023
0.6
0.6
11²
0.4
0.4
0.2
10a
10a
10
10a
10a
10
Calls the Model
Calls the Model
(a) MNIST A Standard Fast-100
(b) CIFAR 10 A Standard Fast-100
0.6
0.6
112
0.4
0.4
0.2
0.2
10a
10ah
10a
10a
10a
10
Calls the Model
Calls to the Model
MNIST A Standard Fast-lk
(d) CIFARIO Standard Fast-
0.8
0.8
0.6
0.6
R2
0.4
0.4
0.2
0.2
10a
10a
10a
10a
10ah
Calls to the Model
Calls to the Model
(c) MNIST A Standard Fast-10k
(f) CIFARIO Standard Fast- 10k
BIM
Deeplool
Fast Gradieent
PGD
Uniform
Figure 24: R² of linear model for the heuristic adversarial distances given the exact decision boundary distances for MNIST & CIFARIO A Standard. A dashed line means that the attack found adversarial examples (of any distance) for only some inputs, while the absence of a line means that the attack did not find any adversarial examples. The loosely and densely dotted black lines respectively represent the balanced and strong attack pools. The axis is logarithmic.
61

---

Under review as a conference paper at ICLR 2023
0.8
0.6
0.6
0.4
0.4
0.2
0.2
10a
10a
10
10a
10a
10
Calls the Model
Calls to the Model
(a) MNIST Adversarial Fast- 100
(b) CIFARIO A Adversarial Fast-100
0.8
0.8
0.6
0.6
11
0.4
0.4
0.2
0.2
10a
10a
10a
10a
10a
10
Calls the Model
Calls to the Model
(c) MNIST A Adversarial Fast-1k
(d) CIFARIO A Adversarial Past-1k
1
0.8
0.8
0.6
0.6
R2
0.4
0.4
0.2
0.2
10a
10ah
10a
10a
10ah
10a
Calls to the Model
Calls to the Model
(c) MNIST Adversarial Fast- 10k
(f) CIFARIO A Adversarial Fast-10k
BIM
Deeplool
Fast Gradieet
PGD
Uniform
Figure 25: R² of linear model for the heuristic adversarial distances given the exact decision boundary distances for MNIST & CIFARIO A Adversarial, A dashed line means that the attack found adversarial examples (of any distance) for only some inputs, while the absence of line means that the attack did not find any adversarial examples. The loosely and densely dotted black lines respectively represent the balanced and strong attack pools. The axis is logarithmic.
62

---

Under review as a conference paper at ICLR 2023
0.6
0.6
11²
0.4
0.4
0.2
0.2
10a
10a
10
10a
10a
10
Calls the Model
Calls the Model
MNIST A ReLU Fast-100
(b) CIFARIO A ReLU Fast-100
0.8
0.8
0.6
0.6
11
12
0.4
0.4
0.2
0.2
10a
10a
10a
10a
10a
10
Calls the Model
Calls to the Model
(c) MNIST A ReLU Fast-1k
(d) CIFARIO A ReLU Fast-Ik
0.8
0.8
0.6
0.6
R2
0.4
0.4
0.2
0.2
10a
10ah
10a
10a
10a
Calls to the Model
Calls to the Model
(e) MNIST A ReLU Fast- 10k
(f) CIFARIO A ReLU Fast- Past-10k
BIM
Deeplool
Fast Gradient
PGD
Uniform
Figure 26: R² of linear model for the heuristic adversarial distances given the exact decision boundary distances for MNIST & CIFARIO A ReLU. A dashed line means that the attack found adversarial examples (of any distance) for only some inputs, while the absence of a line means that the attack did not find any adversarial examples. The loosely and densely dotted black lines respectively represent the balanced and strong attack pools. The axis is logarithmic.
63

---

Under review as a conference paper at ICLR 2023
0.8
0.6
0.6
11²
0.4
0.4
0.2
10a
10a
10
10a
10a
10
Calls the Model
Calls to the Model
(a) MNIST B Standard Fast-100
(b) CIFARIO 10 B Standard Fast- 100
0.8
0.8
0.6
0.6
112
R
0.4
0.4
0.2
0.2
10a
10a
10a
10a
10a
10
Calls the Model
Calls to the Model
(c) MNIST B Standard Fast- 1k
(d) CIFARIO Standard Fast- 1k
0.8
0.8
0.6
0.6
R2
0.4
0.4
0.2
0.2
10a
10a
10a
10a
10ah
10a
Calls to the Model
Calls to the Model
(e) MNIST B Standard Fast-106
(1) CIFARIO Standard Fast- 10k
BIM
Deeplool
Fast Gradieent
PGD
Uniform
Figure 27: R² of linear model for the heuristic adversarial distances given the exact decision boundary distances for MNIST & CIFARIO B Standard. A dashed line means that the attack found adversarial examples (of any distance) for only some inputs, while the absence of a line means that the attack did not find any adversarial examples. The loosely and densely dotted black lines respectively represent the balanced and strong attack pools. The axis is logarithmic.
64

---

Under review as a conference paper at ICLR 2023
0.6
0.6
11²
12
0.4
0.4
0.2
10a
10a
10
10a
10a
10
Calls the Model
Calls the Model
MNIST Adversarial Fast-100 100
(b) CIFARIO B Adversarial Fast-100
0.6
0.6
0.4
0.4
0.2
0.2
10a
10a
10a
10a
10a
10
Calls the Model
Calls to the Model
(c) MNIST B Adversarial Fast-lk
(d) CIFARIO B Adversarial Fast- 1k
0.8
0.8
0.6
0.6
R2
0.4
0.4
0.2
0.2
10a
10ah
10a
10a
10ah
Calls to the Model
Calls to the Model
(e) MNIST Adversarial Fast- 10k
(f) CIFARIO B Adversarial Fast-10k
BIM
Deeplool
Fast Gradieett
PGD
Uniform
Figure 28: R2 of linear model for the heuristic adversarial distances given the exact decision boundary distances for MNIST & CIFARIO B Adversarial. A dashed line means that the attack found adversarial examples (of any distance) for only some inputs, while the absence of line means that the attack did not find any adversarial examples. The loosely and densely dotted black lines respectively represent the balanced and strong attack pools. The axis is logarithmic.
65

---

Under review as a conference paper at ICLR 2023
0.6
0.6
I1
0.4
0.4
0.2
10a
10a
10
10a
10a
10
Calls the Model
Calls the Model
MNIST B ReLU Fast-100
(b) CIFARIO B ReLU Fast-100
0.8
0.6
0.6
11
0.4
0.4
0.2
0.2
10a
10a
10
10a
10a
10
Calls the Model
Calls to the Model
(c) MNIST B ReLU Fast-1k
(d) CIFARIO B ReLU Fast-Ik
0.8
0.8
0.6
0.6
R2
0.4
0.4
0.2
0.2
10a
10ah
10a
10a
10a
Calls to the Model
Calls to the Model
(e) MNIST B ReLU Fast-100
i CIFARIO B ReLU Fast-10k
BIM
Deeplool
Fast Gradient
PGD
Uniform
Figure 29: R² of linear model for the heuristic adversarial distances given the exact decision boundary distances for MNIST & CIFARIO 10 B ReLU. A dashed line means that the attack found adversarial examples (of any distance) for only some inputs, while the absence of a line means that the attack did not find any adversarial examples. The loosely and densely dotted black lines respectively represent the balanced and strong attack pools. The axis is logarithmic.
66

---

Under review as a conference paper at ICLR 2023
0.8
0.6
0.6
11²
0.4
0.4
0.2
0.2
10a
10a
10
10a
10
10
Calls the Model
Calls to the Model
(a) MNIST C Standard Fast-100
(b) CIFARIO C Standard Fast- 100
0.8
0.8
0.6
0.6
112
0.4
0.4
0.2
0.2
10a
10a
10a
10a
10a
10
Calls the Model
Calls to the Model
(c) MNIST C Standard Fast-Ik 1k
(d) CIFARIO C Standard Fast- 1k
0.8
0.8
0.6
0.6
0.4
0.4
0.2
0.2
10a
10ah
10a
10a
10ah
10a
Calls to the Model
Calls to the Model
(e) MNIST C Standard Fast- 10k
(1) CIFARIO Standard Fast- 10k
BIM
Deeplool
Fost Gradieent
PGD
Uniform
Figure 30: R² of linear model for the heuristic adversarial distances given the exact decision boundary distances for MNIST & CIFARIO C Standard. A dashed line means that the attack found adversarial examples (of any distance) for only some inputs, while the absence of a line means that the attack did not find any adversarial examples. The loosely and densely dotted black lines respectively represent the balanced and strong attack pools. The axis is logarithmic.
67

---

Under review as a conference paper at ICLR 2023
0.6
0.6
I1²
18
0.4
0.4
10a
10a
10
10a
10a
10
Calls the Model
Calls the Model
MNIST Adversarial
(b) CIFAR10 C Adversarial Fast-100
0.6
0.6
11
0.4
0.4
0.2
0.2
10a
10a
10a
10a
10a
10
Calls the Model
Calls to the Model
(c) MNIST C Adversarial Fast-lk
(d) CIFARIO C Adversarial Fast- 1k
0.8
0.8
0.6
0.6
12
0.4
0.4
0.2
0.2
10a
10ah
10
10a
10a
Calls to the Model
Calls to the Model
(e) MNIST C Adversarial Fast- 10k
(f) CIFARIO C Adversarial Fast-10k
BIM
Deeplool
Fast Gradieet
PGD
Uniform
Figure 31: R² of linear model for the heuristic adversarial distances given the exact decision boundary distances for MNIST & CIFARIO C Adversarial. A dashed line means that the attack found adversarial examples (of any distance) for only some inputs, while the absence that the attack did not find any adversarial examples. The loosely and densely dotted black lines respectively represent the balanced and strong attack pools. The axis is logarithmic.
line means
68

---

Under review as a conference paper at ICLR 2023
0.6
0.6
11²
12
0.4
0.4
10a
10a
10
10a
10a
10
Calls the Model
Calls the Model
MNIST C ReLU Fast-100
(b) CIFARIO ReLU Fast-100
0.6
0.6
11
0.4
0.4
0.2
0.2
10a
10a
10a
10a
10a
10
Calls the Model
Calls to the Model
(c) MNIST C ReLU Fast-1k
(d) CIFARIO C ReLU Fast-Ik
0.8
0.8
0.6
0.6
12
0.4
0.4
0.2
0.2
10a
10a
10a
10a
10a
Calls to the Model
Calls to the Model
(e) MNIST C ReLU Fast-100 10k
i CIFARIO C ReLU Fast-10k
BIM
Deeplool
Fast Gradient
PGD
Uniform
Figure 32: R² of linear model for the heuristic adversarial distances given the exact decision boundary distances for MNIST & CIFARIO 10 C ReLU. A dashed line means that the attack found adversarial examples (of any distance) for only some inputs, while the absence of a line means that the attack did not find any adversarial examples. The loosely and densely dotted black lines respectively represent the balanced and strong attack pools. The axis is logarithmic.
69

---

Under review as a conference paper at ICLR 2023
M OVERVIEW OF CERTIFIED DEFENSES
In order to put our defense into context, we provide a slightly more in-depth overview of common approaches to certified robustness, as well their strengths and weaknesses.
Initially, theoretical work focused on providing robustness bounds based on general properties. For example, Szegedy et al. (2013) computed robustness bounds against L.2-bounded perturbations by studying the upper Lipschitz constant of each layer, while Hein & Andriushchenko (2017) achieved similar results for L'-bbunded perturbations by focusing on local Lipschitzness. While these studies do not require any modifications to the network or distribution hypotheses. in practice the provided bounds are too loose to be used in practice. For this reason, WWng al. (2018b) derived stronger bounds through a local Lipschitz constant estimation technique; however, finding this bound is computationally expensive, which is why the authors also provide a heuristic to estimate it.
Similarly, solver-based approaches provide tight bounds but require expensive computations. For example, Reluplex was used to verify networks at most ~300 ReLU nodes (Katz al. (017). Tjeng et al. (2019) was able to although large networks are still not feasible to verify. Solver-friendly training techniques can boost the performance of verifiers (such in (Xiao al. 2019 ); however, this increase in speed often comes at the cost of accuracy (see Section 6).
MIP-base formulation significantly speed up verification,
Another solution to the trade-off between speed and bound tightness is to focus specific (and more tractable) threat models. For example, Hann et al. (2021) provide robustness guarantees against adversarial patches (Brown al.] 2017), whileeJaa al. (009) focus adversarial word substitutions. In the same vein, |Raghunathan et al. (2018) provide robustness bounds for specific architectures (i.e. 1 I-layer and 2-layer neural networks). while Zhang ct al. (2021) introduce custom neurons that, used in place of regular neurons, provide L robustness guarantees. These techniques thus trade generality for speed.
The most common approach, however, consists in providing statistical guarantees. For example, Sinha al. (2018) showed that using a custom loss can bound the adversarial risk. Similarly, |Dan et al.) (2020) proved adversarial risk bounds for Gaussian mixture models depending the "adversarial Signal-to-Noite Ratio". Finally, [Chhnn al. (20T9) introduced a smoothing- -based certified defense that, due to its high computational cost, replaced by Monte Carlo estimate with given probability of being robust. This work was later expanded upon in (Salman et al. (2220) and (Carlini et al.) 2022). The main drawback of these techniques is the fact that they cannot be used in contexts where statistical guarantees are not sufficient, such as safety-critical applications.
All of these certified defenses prioritize certain aspects (speed, strength, generality) over others. In the context this (simplified) framework, CA in its exact form can be thus considered a defense that prioritizes strength and generality speed, similarly Katz al. (2017) and TTeng al. (2019).
70


Reviews:
[{"review_id": "kOEFqIcCDn", "reviewer": "Reviewer_mBWL", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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": "This paper proves that attacking a polynomial-time classifier is NP-complete, and training a polynomial-time model that is robust on a\nsingle input is Σ_2^P-complete. The authors proposed a method that evaluates on the fly if a model is robust on a specific point by running\nan adversarial attack on the input. Based on this, the authors proposed a dataset of provably optimal adversarial examples found on\nimages of MNIST and CIFAR10 for 6 small-scale Neural Networks.", "summary_of_the_review": "In general, I think the proposed method is well-motivated and the studies are solid. So I recommend a weak accept.", "strength_and_weaknesses": "Strength:\nThe authors provided a thorough theoretical analysis of the complexity of neural network adversarial robustness. The proposed counter-attack method is very simple but is able to take advantage of existing defenses and provide robustness guarantees. The authors also showed detailed information about their experiments.\nWeakness:\n1. In the main text, it would be great if the authors can present a table for comparison between CA and existing defense methods on their certified robustness accuracy, as well as adversarial accuracy under different attacks. \n2. Please refrain from only using color to distinguish curves in Figure 2, as it may not be friendly to readers with color blindness.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "j7P69hj_Zo-", "reviewer": "Reviewer_wxLx", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "To improve the attack-defense gap for robust classifiers, the paper suggests using a sample-specific attack-based flag, Counter-Attack(CA),  that tells the user if there are adversarial samples within a $\\epsilon$-ball of the given sample. In the case of a perfect attack, the authors show that Counter-Attack also provides a computational robustness guarantee that it is hard to find unflagged adversarial examples beyond the threat models $\\epsilon$ radius. \n\nHowever, the paper also formally proves that, under broad assumptions, attacking a polynomial-time classifier is $NP$-complete, while training a polynomial-time model that is robust on even a single input is $\\Sigma^P_2$-complete. They also extend these results to the case of general non-polynomial time classifiers.\n\nThe authors suggest using a heuristic attack to flag examples for practical purposes. To improve the validity of this approach, the authors recommend using a higher radius for the heuristic attacks to make up for their relative weakness to a perfect attack. To this end, the authors study the consistency between the average distance of an adversarial example found by the heuristic attacks vs. the perfect attack or MNISt and CIFAR10 datasets. The empirical results show that for a well-chosen suit of attacks, the gap is pretty consistent in the evaluated examples.", "summary_of_the_review": "The idea of using the success of a suit of heuristic attacks to flag vulnerable examples is interesting, but it is not clear if there is a specific use case where it would help. Although the paper establishes some interesting theoretical results for the power of this method when used with a perfect attack, none of the guarantees extend to the setting of heuristic attacks. The empirical evidence provided to show the effectiveness is only limited to a very small set of architectures for shallow neural networks. It is not clear if these observations hold in general. As for the setting of shallow neural networks, some of the formal verification methods already provide good bounds. \n\nI feel the paper provides some interesting results that might serve as an interesting starting point for further investigation. However, it does not provide enough justification to use the proposed Counter-Attack method.", "strength_and_weaknesses": "Strengths\n- The complexity results for attacking polynomial models and training robust polynomial models provide a reasonable explanation for the hardness of doing these tasks on practical datasets.\n- The empirical results showing that the attack radius achieved by a suit of weaker attack strongly correlates with the actual radius of the decision boundary around an example is very interesting and provides a good justification for the CA approach.\n\nWeakness\n- The underlying ideas presented in the paper are not very novel. Similar hardness results for ReLU networks do exist in previous papers. The flagging of specific examples provides a heuristic guarantee in contrast to the solid theoretical guarantees provided by other certification methods. The use case of Counter-Attack is not very clear to me.\n-  Due to the computational limitations of the MIP solvers, the empirical justification for the method is only shown on small neural networks. It is not clear whether these results extend to general neural networks with more complicated architectures.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "L31jw2016_Y", "reviewer": "Reviewer_2UCv", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper aims to study the “computational complexity” of attacking versus that of defending machine learning models against adversarial attacks, which are test-time attacks that find so-called adversarial examples.\n\nAn adversarial example for an input x is a bounded perturbation of x that is misclassified.\n\nThe paper studies the worst-case computational complexity of finding adversarial examples (for a given perturbation threshold) vs. training a robust model. It is shown that in the *worst case* (even for basic ReLU models):\nFinding adversarial examples is NP complete, while\nFinding robust models is Sigma-2 complete. Sigma-2 is a bigger than (or equal to) complexity class than NP (and is conjectured to be strictly bigger).\n\nThe paper then defines a way of perhaps defending adversarial examples by trying to test robustness of the points one by one, and abstaining from answering when there is a non-robustness evidence. In particular, the paper applies a class S of attacks on each point, using a specific perturbation eps. Then, the thesis is that if we don’t find an example with eps perturbations, then perhaps it is relatively safe to assume that there is no such example for smaller eps’ < eps. The paper verifies this experimentally for small models for which the exact robustness can be computed.\n\nEvaluation: I think the formulation of the problem this way has serious limitations that could prevent us from using these results for any real world insights. So I cannot support acceptance. See my comments below.\n\nConsidering NP completeness to reflect “easier task” than being Sigma-2 complete is both correct (theoretically) and wrong (practically). Theoretically, Sigma-2 is a “harder class” as it contains NP, but when it comes to running algorithms efficiently, there is no difference between them, as they both contain problems that we don’t know how to solve in polynomial time. So, there is a fundamental difference between the “computational approach” of this paper and that of e.g., Garg et al (cited work) where the distinction there is drawn between poly-time vs. non-poly-time algorithms. This makes the theoretical insight of this paper quite irrelevant to practice.\n\nThe paper does not pay attention that their notion of adversarial examples might *not* lead to misclassified inputs. For example, suppose we perturb x into x’ and the model changes the label for x’ while the true label is the changed label. (e.g., changing a cat image to a dog image while the model predicts the dog as dog). This should not constitute an adversarial example. E.g., see the work of “revisiting adversarial examples” by Suggala et al. Without this subtle point being fixed, it is hard to interpret the results of the paper as attacks. This might seem like a minor thing, but it becomes clear that it is a major issue when one notices that hardness of robust or non-robust learning of a task crucially depends on *what class of concept functions* we want to learn. E.g., one can show that simple function classes *can* be learned robustly and the literature is full of such results. This shows another flaw with the formulation of the problem in this paper.\n\nThe computational complexity of adversarially robust learning is an *average-case* phenomenon. Namely, we would like to know, what is adversary’s chance of making x misclassified, when we (say i.i.d) sample the training set, then train (perhaps in a randomized way) a model, and then pick x at random, and finally let adversary perturb x. So, even though the perturbation itself is studied in the worst-case, the whole problem is average-case. As an example, breaking crypto-systems is an average case task, even though one can find specific ciphertex whose complexity *in the worst case* is NP complete, yet finding NP complete encryption schemes is a major open question in cryptography.\n\nBy now, there is a rich literature on “certifying” robustness of decisions per instance. The paper seems to invent the wheel here and give a *weaker* certification than what those works offer, in terms of its guarantee. While other works on certification are provably right, here we only get a heuristic claim. This looks like a step back.\n\nIn addition, there is also a (by now rich) line of work on “abstaining” from answering queries for the sake of robustness. This paper’s approach is different, but still quite relevant, to that line of work. So it is good to do a discussion and compare. (As I understand those works try to abstain from answering the perturbed inputs, while this paper’s approach is to not answer even when x is not perturbed, but is just close to a dangerous perturbation). My understanding is that this approach hurts the correctness/accuracy much more, as it might abstain from answering normal instances as well.\n", "summary_of_the_review": "Interesting direction for studying the complexity of adversarial examples vs defending against test time evasion attacks. The weakness is that the formulation of the problem does not give an actual insight on how much is the running time of those tasks in practice, as the formulation is in the worst case and there is no major difference between NP completeness and sigma-2 completeness in practice; they are both not feasible. See more details in the detailed review.\n", "strength_and_weaknesses": "Strength: aiming for a computational understanding of the adversarial example phenomenon and explaining why defending is hard.\n\nMild weakness: the NP completeness results, as formulated, are rather trivial. For example, if we allow the model to compute SAT instances, is is clear that finding a \"close point that is misclassified\" could be NP complete, because one can choose the model and the input in such a way that doing so is the same as solving an arbitrary SAT instance.\n\nWeakness: there are several severe limitations on how much one can interpret the results of this paper in relation with practice. The experimental part is extensive, but its guarantee is only heuristic while there is a line of work on provably certifying robustness of decisions.\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject