Provably Robust Adversarial Examples
Authors: Dimitar Iliev Dimitrov
Gagandeep Singh
Timon Gehr
Martin Vechev
Venue: ICLR 2022 Poster (2022)
Keywords: Adversarial attacks
Robustness Certification
Abstract Interpretation
Deep Learning

Abstract: We introduce the concept of provably robust adversarial examples for deep neural networks – connected input regions constructed from standard adversarial examples which are guaranteed to be robust to a set of real-world perturbations (such as changes in pixel intensity and geometric transformations). We present a novel method called PARADE for generating these regions in a scalable manner which works by iteratively refining the region initially obtained via sampling until a refined region is certified to be adversarial with existing state-of-the-art verifiers. At each step, a novel optimization procedure is applied to maximize the region's volume under the constraint that the convex relaxation of the network behavior with respect to the region implies a chosen bound on the certification objective. Our experimental evaluation shows the effectiveness of PARADE: it successfully finds large provably robust regions including ones containing $\approx 10^{573}$ adversarial examples for pixel intensity and $\approx 10^{599}$ for geometric perturbations. The provability enables our robust examples to be significantly more effective against state-of-the-art defenses based on randomized smoothing than the individual attacks used to construct the regions.

Published as a conference paper at ICLR 2022
PROVABLY ROBUST ADVERSARIAL EXAMPLES
Dimitar L. Dimitrov !
Gagandeep Singh".. 2.3
Timon Gehr
Martin Vechev
1 ETH Zurich 2 University of Illinois, Urbana Champaign 3 VMware Research
(dimitar. dimitrov, timon. . gehr, martin, vechev @inf. ethz
ggnds@illinot
ABSTRACT
We introduce the concept of provably robust adversarial examples for deep neural networks - connected input regions constructed from standard adversarial examples which are guaranteed to be robust to a set of real-world perturbations (such changes in pixel intensity and geometric transformations). We present a novel method called PARADE for generating these regions in scalable manner which works by iteratively refining the region initially obtained via sampling until a refined region is certified to be adversarial with existing state-of-the-art verifiers. At each step, novel optimization procedure is applied to maximize the region's 's volume under the constraint that the convex relaxation of the network behavior with respect to the region implies a chosen bound on the certification objective. Our experimental evaluation shows the effectiveness of PARADE: successfully finds large provably robust regions including ones containing ~ 10573 adversarial exam- ples for pixel intensity and R3 10599 for geometric perturbations. The provability enables robust examples to be significantly more effective against state-of-the- art defenses based on randomized smoothing than the individual attacks used to construct the regions.
INTRODUCTION
Deep neural networks (DNNs) are vulnerable to adversarial attacks: small input perturbations that cause misclassification (Szegedy et al. (013). - This has caused increased interest in investi-
gating powerful attacks (Goodfellow et al. 2015 Carlini Wagner 2017; Madry et al. 2018 8)
Andriushchenko et al. 2019 Zheng et al. 2019 Wang et al. 2019 Croce & Hein 2019: Tramer ct 20.0))) An important limitation of existing attack methods is that they only produce a single concrete adversarial example and their effect can often be mitigated with existing defenses (Madry
ct al. 2018: Hu et al. 2019 Sen et al. 2020 Xiao et al., 2020 Pang et al.] 2020 Lécuyer et al.
2019 Cohen et al.| 2019 Salman et al. 2019 Fischer et al.) 2020 Li al. (020). The effectiveness
of these attacks can be improved by robustifying them: to consolidate the individual examples to produce large symbolic region guaranteed to only contain adversarial examples.
This Work: Provably Robust Adversarial Examples. We present the concept of a provably robust adversarial example a tuple consisting of an adversarial input point and an input region around capturing a very large set (e.g., > 10)00) of points guaranteed to be adversarial. We then introduce novel algorithm for generating such regions and apply to the setting of pixel intensity changes and geometric transformations. Our work relates to prior approaches on generating robust adversarial examples (Athalye et al.) 2018 Qin et al. 2019) but differs a crucial point: our regions are guaranteed to be adversarial while prior approaches are empirical and offer no such guarantees.
Main Contributions. Our key contributions are:
The concept of a provably robust adversarial example a connected input region capturing very large set of points, generated by set of perturbations, guaranteed to be adversarial.
A novel scalable method for synthesizing such examples called ProvAbly Robust ADversar- Examples (PARADE), based on iterative refinement that employs existing state-of-the techniques to certify the robustness. Our method is compatible with wide range of certifi-

---

Published as a conference paper at ICLR 2022
cation techniques making it easily extendable to new adversarial attack models. We make the code of PARADE available at httttpps//ggihhie wtt..///tttt////aaaaaaaaaoo qit
A thorough evaluation of PARADE, demonstrating it can generate provable regions con- taining ~ 10573 concrete adversarial points for pixel intensity changes, in = 2 minutes, and R 10999 concrete points for geometric transformations, CIFAR 10 network. We also demonstrate that our robust adversarial examples are signifi- cantly more effective against state-of-the-as defenses based on randomized smoothing than the individual attacks used to construct the regions.
R 20 minutes, on a challenging
2 BACKGROUND
We now discuss the background necessary for the remainder of the paper. We consider a neural network f: Ii I with / layers, no input neurons and ny output classes. While our method can handle arbitrary activations, we focus on networks with the widely-used ReLU activation. The network classifies an input æ to class y(x) with the largest corresponding output value, i.e., ((z) = argmax, (z))s. Note for brevity we omit the argument to y when it is clear from the context.
2.1 NEURAL NETWORK CERTIFICATION
In this work, we rely on existing state-of-the-at neural network certification methods based on convex relaxations to prove that the adversarial examples produced by our algorithm are robust. These certification methods take convex input region I C I and prove that every point in I is classified as the target label y/ by f. They propagate the set I through the layers of the network, producing convex region that covers all possible values of the output neurons (Gehr et al. 2018). Robustness follows by proving that, for all combinations of output neuron values in this region, the output neuron corresponding to class y/ has a larger value than the one corresponding to any other class y * yt.
Commonly, one proves this property by computing a function Ly: 1 - IR for each label y # yt. such that, for all x E I, we have (x) & [f(=)]p. [f(r))g g- For each Ly. one computes minzez (2:) to obtain a global lower bound that is true for all I. If we obtain positive bounds for all y + yr. robustness is proven. To simplify notation, we will say that the certification objective L(x)) is the function (x) with the smallest minimum value I. We will call its corresponding minimum value the certification error. We require (2) to be a linear function of x.. This requirement consistent with many popular certification algorithms based on convex relaxation, such as CROWN Zhang et al. 2018), DeepZ (Singh et al.) (018a)) and DecpPoly (Singh et al. 2019). Without loss of generality, for the rest of this paper, we will treat DeepPoly as our preferred certification method.
2.2 CERTIFICATION AGAINST GEOMETRIC TRANSFORMATIONS
DeepPoly operates over specifications based on linear constraints over input pixels for verification. These constraints are straightforward to provide for simple pixel intensity transformations such as adversarial patches (Chiang et al. 2020) and T (Carlini & Wagner] 2017) perturbations that provide a closed-fore formula for the input region. However, geometric transformations do not yield such linear regions. To prove the robustness of our generated examples to geometric transformations, rely on DeepG (Balunović et al. 2019) which, given a range of geometric transformation parameters, creates an overapproximation of the set of input images generated by the geometric perturbations. DeepG then leverages DeepPoly to certify the input image region. When generating our geometric robust examples,
work directly in the geometric parameter space and, thus, our input region I and the inputs to our certification objective [xx are also in geometric space. Despite this change, as our approach is agnostic to the choice of the verifier, in the remainder of the paper we will assume the certification is done using DeepPoly and not DeepG, unless otherwise stated.
2.3 RANDOMIZED SMOOTHING
Randomized smoothing (éeuyeer al. 2019 Cohen et al. 2019) is a provable defense mechanism against adversarial attacks. For chosen standard deviation a and neural network f as defined above, randomized smoothing computes smoothed classifier g based on f, such that g(x) = argmax (zy(z + +c) c) with random Gaussian noise ~ (O, a² This construction of allows
2

---

Published as a conference paper at ICLR 2022
Cohen et al. (2019) to introduce the procedure CERTIFY that provides probabilistic guarantees on the robustness of 9 around a point x:
Proposition 1. (From Cohen et al. (2019)) With probability at least 1 - a over the randomness in CERTIFY, if CERTIFY returns a class and radius R (i.e does not abstain), then g predicts y within radius R around g( + 6) y, for all ||ā]|2 < R.
We define adversarial attacks on smoothed classitiers, follows:
Definition 1 (Adversarial attack on smoothed classifiers). For a fixed a, or and an adversarial distance R' IR="0 call TR adversarial attack the smoothed classifier g at the point E _ if f x||2 < R' and g(x) # g()).
Similarly to generating adversarial attacks on the network f. need to balance the adversarial distance R' on g. If too big - the problem becomes trivial; if too small - no attacks exist. We outline the exact procedure definition, we define the strength of an attack ğ as follows:
use to heuristically select R' in Appendix C.4 Using the above
Definition 2 (Strength of adversarial attack on smoothed classifiers). We measure the strength of an attack ā in terms of Rode- the radius around こ, whose L2 ball is certified to be the same adversarial class as z the smoothed network g using CERTIFY for chosen a and
Intuitively, this definition states that for points i for which Radv bigger, the smoothed classifier is less confident about predicting the correct class, since more adversarial examples are sampled in this region and therefore, the attack on g is stronger. We use this measure Section 5 compare the effectiveness of our adversarial examples to examples obtained by PGD on g.
3 OVERVIEW
Existing methods for generating robust adversarial examples focus on achieving empirical robustness (Qin et al. 2019 Athalyy et al. 2018). .. In contrast, we consider provably robust adversarial examples, defined below:
Definition 3 (Provably Robust Adversarial Example). We define a provably robust adversarial example to be any large connected neural network input region, defined by a set of perturbations of an input, that can be formally proven to only contain adversarial examples.
In this section, outline how PARADE generates such regions. The technical details given in Section 4 To generate a provably robust adversarial example, ideally, we would like to directly maximize the input region's 's size, under the constraint that it only contains adversarial examples. This leads to multiple challenges: Small changes of the parametrization of the input region (e.g., as a hyperbox) can lead to large changes of the certification objective, necessitating a small learning rate for optimization algorithms based on gradient descent. At the same time, the optimizer would have to solve a full forward verification problem in each optimization step, which is slow and impractical. Additionally, like Balunovic & Vechev (2020). we empirically observed that bad initialization of the robust region causes convergence local minima, resulting in small regions. This can explained by the practical observation in Jovanović et al. (202T), which shows that optimization problems involving convex relaxations are hard to solve for all but the simplest convex shapes. We now provide an overview of how generate robust adversarial regions while alleviating these problems.
Our method for generating robust examples the shape assumes algorithm A that generates adversarial examples and a neural network verifier V. We require V to provide the certification objective L(x) as a linear function of the network's 's input neurons (whose values can be drawn from the input hyperbox). algorithm into two steps, descrihed in Section 3.1 and Section (32,, to address the challenges outlined above. An optional final step, illustrated in Figure 2 and outlined in Appendix E demonstrates the extension of PARADE to generate polyhedral examples.
hyperbox shown in Figure and
described in Section 2
We split
3.1 COMPUTING AN OVERAPPROXIMATION REGION
In the first step, compute overapproximation hyperbox O by fitting hyperbox around samples obtained from A. is represented as a dashed blue rectangle in Figure Intuitively, we use O to restrict the search space for adversarial regions to part of the input space that A can attack.
3

---

Published as a conference paper at ICLR 2022
Overapproximation Box
Underapproximation Box
Upper
Choaen
Get Target
Provable
Fit Box
Initialize
Adjust Box
Generate somples by altacking the network
Genorato an overapprovimation box from samples
3. Try to varily the network and Creste larget hyperplane
Adjust the target hyperplane's bias and shrink box accordingly
Figure I: Overview of PARADE. The green triangle denoted T represents the ground truth adversarial region and the red crosses represent the attacks obtained by A. The dashed blue and violet dotted rectangles denoted O and U. represent the fitted overapproximation and underapproximation boxes, respectively. The solid black lines represent hyperplanes generated by the verification procedure, while their dash-dotted counterparts represent the hyperplanes after bias- bias-adjjstment. The arrows going out of the hyperplanes represent the direction of their corresponding half-spaces.
3.2 COMPUTING AN UNDERAPPROXIMATTONN REGION
In the second step, we compute the robust adversarial example as hyperbox 44 represented as a dotted violet rectangle in Figure We will refer to 2/ as underapproximation hyperbox distinguish from the polyhedral robust example P generated in Appendix B U is obtained by iteratively shrinking O until arriving provably adversarial region. We denote the hyperbox created at iteration i of the shrinking process with Ut where Uo = O. At each iteration i, we compute the certification objective L'- (z) of the region U4_1 computed in the previous iteration. If the objective is proven to be positive, we assign /A to 1, as in Step in Figure and return. Otherwise, we solve an optimization problem, optimizing a surrogate for the volume of (4; C U1- under the constraint that min (x) 2 1 for chosen bound p:-1 2 0. We describe the optimization problem involved in the shrinking procedure the next paragraph. In Section we will present and motivate our choice of P:-1. In Appendix D.2 we further discuss sufficient condition under which the overall procedure for generating L/ is guaranteed to converge and why this condition often holds in practice.
An important property of our choice of Pi-1 is that it becomes smaller over time and thus forces the certification objective increase over time until becomes positive. We note that optimizing [.xr) this way is simpler than directly optimizing for 2/ by differentiating through the convex relaxation of the network. In particular, our method does not require propagating gradient through the convex relaxation of the network and the convex relaxation is updated only once per iteration. Additionally, it allows PARADE to work with convex relaxation procedures that are not differentiable, such as the DeepG method employed in this paper. The resulting hyperbox U/ is provable adversarial region.
Shrinking 14 There are multiple ways to shrink 24-1 so that the condition minzeu, (i-1(2) 2 -Pi-1 is satisfied. We make the greedy choice to shrink 24-1 in way that maximizes proxy for the volume of the new box U4 We note this may not be the globally optimal choice across all iterations of the algorithm, however, and that even achieving local optimality in terms of volume of U4; is hard problem as it is non-convex in high dimensions.
One possible solution to the shrinking problem is use scheme that we call uniform shrinking, where all lower bounds [ , and upper bounds [u'=1]; 15 in each dimension j of the hyperbox U4-1 changed by the same amount. The optimal amount for this uniform shrinking scheme can then be selected using a binary search. While this gives an efficient shrinking algorithm, in practice we observe that uniform shrinking produces small regions. This expected, as may force all dimensions of the hyperhox to be shrunk by large amount even though it might be enough to shrink only along some subset of the dimensions.
In contrast, our shrinking scheme adjusts each [r'-1], and [u' individually. While this shrinking scheme is more powerful, optimizing the size of U4 with respect to its lower and upper bounds [t'), and [u'], becomes more complex. We approach the problem differently in the high dimensional input setting related Loe perturbations and the low dimensional setting related geometric changes.
Shrinking for Lox. Transformations. For the high-dimensional setting of Los pixel transformations, we maximize E [w"]] where [w]], [u*]; - [['], denotes the width of the j"h dimension of U. The linear objective allows for solutions where small number of dimensions are shrunk width
4

---

Published as a conference paper at ICLR 2022
in favor of allowing most imput dimensions to retain a big width. As result, in our computed region 24 there are few pixels that can only take a single value while most other pixels can take a big range of values. Since, Zi=j [w*], I5 is a linear function of [[6 and [u' the optimization can be posed as Linear Program (LP) (Schriiver 1998) and be efficiently solved with LP solver to obtain optimal values for [u*], and [[]J w.r. the objective, as we show in Appendix B.2
Shrinking for Geometric Transformations. As discussed in Section 2.2 we generate provably robust examples to geometric transformations in the cow-dimensional geometric parameter space. Therefore, the resulting region U4 is also www-imensional. We found that maximizing the logarithm of the volume of (4; is more effective in this setting, as this objective encourages roughly equally-sized ranges for the dimensions of U4; We solve the optimization problem using PGD, which can lead to merely locally-optimal solutions for the volume of U4 We, therefore, rely on multiple initializations of PGD and choose the best result. Appendix B.3 describes the process in detail.
3.3 PROVABLY ROBUST POLYHEDRAL ADVERSARIAL EXAMPLES
We remark that our provably robust adversarial examples are not restricted to hyperbox shapes. Appendix Appendix[[desrribnn describes an optional final step of PARADE that generates provably robust polyhedral adversarial examples ア from Li and O. P is iteratively cut from O, such that P 2 l is ensured. Therefore, represents a bigger region, but takes additional time to compute. The computation of P. requires V that accumulates imprecision only at activation functions, such as ReLUU or sigmoid, in order to work. This property is violated by DeepGis 's handling of the geometric transformations. For this reason, we only apply it in the Lov -tarasssforraioon setting. We refer interested readers to Appendix for information on how we generate polyhedral adversarial examples.
4 PARADE: PROVABLY ROBUST ADVERSARIAL EXAMPLES
We now present PARADE more formal terms. We already discussed how to compute O in Section 3 We use [ compute U, which is the output of PARADE. It requires neural network f I + RR with 7 layers, adversarial target class Vt, an overapproximation hyperbox O, speed//recision trade-off parameter [0, 1], maximum number of iterations Wit, an early termination threshold and a certification method V that takes a neural network f, a hyperbox U4-1 and target Br and returns a linear certification objective L/-1 (x).
As described in Section 3.2, the al- gorithm generates a sequence of hy- perboxes Uo 2 21 2 2 Uu with Uu O and returns the first hyperbox from the sequence proven to adversarial by V. At each iter- ation, the algorithm attempts to tify the hyperbox from the previous iteration 24-1 to be adversarial by computing the certification error ei (Line 4 and checking if it is positive (Line 5). If successful, U; is re- turned. Otherwise, we use L' generated by our attempt at verifying 24-1 (Line 4 and generate the con- straint mill (x: 2 -P4-1 based on a parameter Pi-1 2 We note that min L Lx-)(x) is func- tion of the hyperbox 24, parametrized by its lower and upper bounds. In or- der to shrink U4-1 we optimize the lower and upper bounds of U4; explicitly, such that the constraint holds true for the bounds. Next, we specify and motivate choice of Pi-1-
Algorithm 1 GENERATE_ UNDERAPPROX
I: fune GENERATE UNDERAPPROX S, O, V, Ve, C, Win L)
Un =0
3:
for E L'-1(x,,
uu} do (x), d-1 V(J, =V[[,u--1,1)
4:
5:
if 2 then
6:
return 14-1
7:
end if
-c" 1-1,,
Pa-1
9:
if p: S t then
10:
Pi-1 =0
11:
end if
12:
if Lox trosstansff t formation then
13:
U. = Shrink LP(4:-1, -i-1 (x), (x)) Pi-1)
14:
else
15:
44. = Shrink PGD(U--,, - (x), p1-1) end if
16:
17:
end for
18:
return FaivedToConverge
19:
end fune
At each iteration i, we use the constraint min (x1(x) 2 -Pi-1 to shrink U4-1 (Line I2 by calling either the SHRINK IP or SHRINK_PGI optimization procedures. SHRINK T.P and
16
5

---

Published as a conference paper at ICLR 2022
Table I: Comparison between different methods for creating adversarial examples robust to intensity changes. Column depicts the preturbation radius used by adversarial algorithm A. Columns #Corr, #lmg, #Reg show the number of correctly classified images, adversarial images and adversarial regions for the network. For each method columns #VerReg, Time and #Size show the number of verified regions, average time taken, and number of concrete adversarial examples inside the regions.
BASKLINK
PARADE Box
PARADE POLY
DARASET
MOUeL
PComm
FReG
#VEeRou
SIzE
*V2nRoU
TIME
5oze
YYEARGG
TIME
SizeO
8 X 200
0,045
97
22
51
41
2728
16"4
53
114%
10'21
53
1556
MNIST
CONVERALL
0.12
100
21
32
31
171.5
10
32
74.5
10914
32
141 5
110M
CaRvErG
0.05
98
39
1933
109
18
880
10
26
5616
CIFARIO
CORVBIG
CONVSMANT
0.008
0.008
50
25
36
26
238.8
479
10
10
36
113.
4045
10775
36
2645
6105
100h
SHRRIKK PGD are detailed in Appendix B.2 and Appendix B.3 respectively. To enforce progress of the algorithm, we require the constraint to remove non-zero volume from Ui 1. Let p be any upper bound on pi-1- for which if p--1 exceeds p;-1 the constraint mingeu, L' (x) ス P is trivially satisfied with 24
41 We can show pi min L - (z) one such upper bound, as we have: minzeu: L (x) 2 mingeut- L (x) = -p; p where the inequality follows from U4 S Ui-1- We show the hyperplane L (x) - p denoted as Upper in Step 3 in Figure We note that Upper always touches U by construction. Decreasing the value of P:-1. increases the volume removed from Ui as demonstrated by the other two hyperplanes in Step 3 in Figure Additionally, we require P 2 0 because any value of p:-1 S 0 creates a provably adversarial
region Us and choosing P.-1 < 0 generates smaller region 24 than choosing P = 0. We denote the hyperplane corresponding to p = 0 in Figure I as Provable. We, thus, use P:-1 E [0, PT
We note that while p:-1 = 0 is guaranteed to generate a provable region Ug it is often too greedy. This is due to the fact that with an imprecise V. (x) itself is also imprecise and, therefore more precise certification method may certify 24 as adversarial for pt-1 > 0. Further, as the region 44-1 shrinks, the precision of V increases. Thus, V might be capable of certifying U4 for Pi-1 > 0. since on the next iteration of the algorithm the more precise certification objective (xx) will be used for certifying the robustness of the smaller 24 We choose p:-1 heuristically, by setting P:-1 = p c, for chosen parameter E [0. 1). This is depicted in Line 8 in Algorithm [ The closer c to 1, the bigger the chance that the modified region will not verify, but, also, the bigger the region we produce and vice versa. Thus, balances the precision and the speed of convergence of the algorithm. We empirically verify the effect of c on our regions in Appendix A. The hyperplane resulting from = 0.65, denoted as Chosen, is shown in Step 3 in Figure 1
Finally, if at some iteration i, the Upper hyperplane gets closer than a small threshold t to the Provable hyperplane, that is P S I, we set p;-1 0 to force the algorithm terminate (Line TOP. This speeds up the convergence of PARADE in the final stages, when the precision loss of V is not too big.
5 EXPERIMENTAL EVALUATION
We now evaluate the effectiveness of PARADE on realistic networks. We implemented PARADE
in Python and used Tensorflow (Abadi et al. 2015) for generating PGD attacks. We use Gurobi 9.0 (Gurobi Optimization, LLC 2020) for solving the LP instances. We rely on ERAN (Singh et al. 2018b) for its DeepPoly and DeepG implementations. We ran all our experiments on a 2.8 GHz 16 core Intel(R) (R) Gold 6242 processor with 64 GB RAM.
Neural Networks. We use MNIST (LeCun et al. 1998) and CIFARIO (Krizhevsky 2009) based neural networks. Table Sj Appendix I.1 shows the sizes and types of the different networks. All networks our Loo experiments, except the CIFAR10 ConvBig, are not adversarially trained. In our experiments, normally trained networks were more sensitive to geometric perturbations than for Tr Therefore, we use DiffAl-trained (Mirman et al., 2018) networks which tend to be less sensitive against geometric transformations. Our deepest network is the MNIST 8 x 200 fully-connected network (FFN) which has 8 layers with 200 neurons each and another layer with 10 neurons. Our largest network is the CIFARIO ConvBig network with 6 layers and x 62K neurons. This network is among the largest benchmarks that existing certification methods can handle in a scalable and precise manner. We compare the methods on the first 100 test images of the datasets, standard practice in the certification literature (Balunović et al.] (2019] Singh et al. 2019). while filtering the crosgly-classified ones. For each experiment, tuned the value of c balance runtime and size.

---

Published as a conference paper at ICLR 2022
Table 2: Comparison between methods for creating adversarial examples robust to geometric changes.
Columns #Corr, #lmg, #Reg show the number of correctly classified images, adversarial images and adversarial regions for the network. For each method columns #VerReg, Time and #Splits show the
number of verified regions, average time taken, and number of splits used to verify. Under and Over show median bounds on the number of concrete adversarial examples inside the regions.
BASELINE
PARADE
DATASET
TRANSTORM
4COR2
AEMG
#RtI
VVisftnn
TIME:
457L.75
4V22RBG
TIME
#SPLITS
UNDER
OvER
CONVSHALL
MNIST
ROT Sc118) Sei0,003
Sc020) TC-L-7.1.7.4-774
Sec20j R21
38
56
54
10
4700.
432333
774
570.
182s1
-00
10
1070
100
CONVBIG
MNIST
Scc20) TEO, 1.O.1)
R(30) Sc115) Stz/0003)
Scr15) R/9) (C5.0.05) 0.055
95
95
95
39
34
40
46
52
30
2
9
512.5
435.
501
3x28282
25432
43232
42
44
46
8355
5378
4415
2818181
1x2x1
2N1X1
1644
-007
1004
100
Rx2.5) Sc(10) Say0.02)
34
29
1829
5x2x2
1369
10
10
CIFAR
CONVSNACL
ScrS) R(3) 0.0,).01)
1YO.1
21
25
2189
SX2X2X2
1451
281x181
1004
5.1 ADVERSARIAL EXAMPLES ROBUST TO INTENSITY CHANGES
Table 1 summarizes results on generating examples robust to intensity changes, whose precise definition is in Appendix B.I Further, Appendix F.2 shows images of the examples obtained in our experiment. We compare the uniform shrinking described in Section 3 used a baseline, against the PARADE variants for generating robust hyperbox and polyhedral adversarial examples. In all experiments, we compute O using examples collected within an L. ball around a test image with the radius e specified in Table II The values of e are chosen such that the attack has a non non-trivial probability (> 0 but < 1) of success. Additional details about the experimental setup are given in Appendix
For the hyperbox adversarial examples obtained by both PARADE and the baseline, we calculate the size of the example in terms of the number of concrete adversarial examples it contains and we report the median of all regions under the Size columns in Table T For the polyhedral adversarial examples, we report the median number of concrete adversarial examples contained within overapproximated hyperbox around the polyhedral region in the SizcO column. We note that our hyperbox regions are contained within our polyhedral regions by construction and, thus, the size of the hyperbox regions acts as an underapproximation of the size of our polyhedral regions. We also report the average runtime of all algorithms on the attackable regions.
We note that for MNIST ConvBig and x 200, the regions obtained for O produced huge certification error 1000, which prevented our underapproximation algorithm 1/ converge on these networks. To alleviate the problem, we used uniform shrinking to lower the error to under 100 first. We then used the obtained box in place of O. We conjecture the reason for this issue is the huge amount of imprecision accumulated in the networks due to their depth and width and note that the uniform shrinking on these networks alone performs worse. For each network, in Table T. we report the number of distinct pairs of an image and an adversarial target on which A succeeds (column #Reg), as well as the number of unique images on which A succeeds (column #Img). We note that #Reg > #Img. We further report the number of test images that are correctly classified by the networks (column #Corr). The table details the number of regions on which the different methods succeed (column #VerReg), that is, they find a robust adversarial example containing > 1000 concrete adversarial examples. As can be seen in Table T PARADE Box creates symbolic regions that consistently contain more concrete adversarial examples (up 10573 images CIFARIO ConvBig) g) than the baseline while being faster. PARADE also succeeds more often, failing only for a single region due to the corresponding hyperbox O also containing < 1000 concrete examples versus 53 failures for the baseline. Overall, our method, unlike the baselines, generates robust examples containing large number of examples in almost all cases in which the image is attackable, in a few minutes.
5.2 ADVERSARIAL EXAMPLES ROBUST TO GEOMETRIC CHANGES
Next, we demonstrate the results of our algorithm for generating examples robust to geometric transformations, whose precise definition is given in Appendix B.1 Here, PARADE relies on DeepG for robustness certification, as detailed in Section 2 To increase its precision, DeepG selectively employs input space splitting, where each split is verified individually. This strategy is effective due to the low dimensionality of the input space (3 to 4 geometric parameters in our experiments). To this end, we uniformly split our method's 's initial region O, instead, where all splits are individually shrunken and their sizes are summed. We compare PARADE against a baseline based on a more aggressive uniform splitting of O that does not our shrinking procedure. Since the cost and
7

---

Published as a conference paper at ICLR 2022
Table 3: The robustness of different examples to L2 smoothing defenses.
MNIST
CIFAR
METHOD
8x200
CONYSMALE
CONVBIG
CONYSMALL
ConvBIG
BASELINE
0.55
0.38
0.59
0.53
0.26
PARADE
1.00
1.00
1.00
1.00
1.00
INDIVIDUAL ATTACKS MEAN
0.29
0.16
0.18
0.48
0.25
INDIVIDUAL ATTACKS 95% PERCENTILE
0.53
0.44
0.51
0.61
0.37
precision of verification increases with the number of splits, to allow for fair comparison we select the number of baseline splits, so the time taken by the baseline similar or more than for PARADE.
Table summariis the results for PARADE and the baseline on the MNIST and CIFAR10 10 datasets. Further, Appendix F3 shows visualizations of the adversarial examples obtained in the experiment. The Transform column in Table represents the set of common geometric transformations on the T
images. Here, R(x) signifies a rotation of up to =.. degrees; Sc(z), scaling of up to +., (mm). shearing with factor up to +m%; B(y, 3), changes in contrast between +%% and brightness between =,%; and T(x,, Fy yd. Du). translation of up to 21 pixels left, 2, pixels right, y/ pixels down and you pixels up. The selected combinations of transformations contain < 4 parameters, as is standard for assessing adversarial robustness against geometrical perturbations (Balunović et al.) 2019). Unlike DeepG, we chose only combinations of parameters, as they are more challenging. The chosen combinations ensure that all transformations from DeepG are present. Similar to Loos we chose the parameter bounds such that the attack algorithm has non-trivial probability of success. Additional details about the experimental setup are given in Appendix
We note that in this setting PARADE creates robust regions in the geometric parameter space, however since we are interested in the number of concrete udversarial images possible within our computed regions, we use DeepG to compute a polyhedron overapproximating the values of the pixels inside the region. For each polyhedron, we compute underapproximation and overapproximation hyperboxes, resulting in a lower and an upper bound on the number of concrete examples within our computed regions. The underapproximation hyperbox is computed as in Gopinath et al. (2019) and the overapproximation is constructed by computing the extreme values of each pixel. The medians of the bounds are shown in the Over and Under columns in Table For all experiments, the baseline failed to generate regions with > 1000 examples on most images and, thus, we omit its computed size to save space. On the few images where it does not, the size generated by PARADE is always more.
We report the number of concrete examples, the number of splits, the average runtime on attackable regions, and the number of successfully verified regions for both the baseline and PARADE in the that in a similar or smaller amount of time, #Splits, Time, and # #VerReg columns. adversarial examples for most regions O while the baseline PARADE is capable of generating robust fails for most. Further, our regions are non-trivial as they contain more than 10 concrete adversarial attacks. We note that the runtimes for generating robust examples in this setting is higher than in Table 1 This is due to both the inefficiency of the attack and the time required for the robustness certification of a single region. Due to the flexibility and the generality of our method, we believe can be easily adapted to more efficient attack and certification methods in the future.
5.3 ROBUSTNESS OF ADVERSARIAL EXAMPLES TO RANDOMIZED SMOOTHING
Next, we show that our adversarial examples robust to intensity changes are significantly more effective against state-of-the-ar defenses based on randomized smoothing compared to the concrete attacks by A generated for our examples, as well as the baseline from Table [ We note that our setting is different than Salman et al. (2019) which directly attacks the smoothed classifier. Instead, we create examples with PARADE on the original network f with A., based on the L2 PGD attack and evaluate them g. For all methods, we calculate the quantity Rady for g. introduced in Definition 2 that measures the adversarial attack strength on g. For PARADE and the baseline we select ă in Definition as the middle point of the underapproximation box projected back to the Lz2 ball, with center x and radius the adversarial distance R'. For the concrete attacks, 7 simply the attack itself. We exclude images whose adversarial distance R' is more than 33% bigger than the certified radius R of x, as we consider them robust to attacks. We experiment with networks f with the same architectures as in Table [
We supply additional details the experimental setup in Appendix C.4
In Table 3 we show the ratio between the adversarial strengths Radv of all other methods and PARADE averaged across the first 100 test images. The last two rows in Table depict the mean and the 95% percentile of the strength ratio across the attacks generated by A. We note the smaller the ratio in Table 3 is, the weaker the attacker is with respect PARADE. We observe that our examples
8

---

Published as a conference paper at ICLR 2022
produce attacks the smoothed classifier g with average strength ranging from 2x to 6x larger compared to the alternatives. We conjecture, this is caused by our examples being chosen such that the regions around them have comparatively higher concrete example density. We note the uniform baseline also largely performs better than the mean individual attack, further supporting our claim.
5.4 COMPARISON WITH EMPIRICALLY ROBUST EXAMPLES
We compare our provably robust adversarial examples to empirically robust adversarial exam- ples (Athalye et al. 2018) - large input regions, defined by a set of perturbations of an image, that are empirically verified to be adversarial. The empirical verification is based on calculating the expectation over transformations (EoT) of the obtained region defined in Athalye et al. (2018). We consider region to be an empirically robust adversarial example demonstrate that EoT is a limited measure, as it is not uniform. That is, empirically robust adversarial examples can exhibit high EoT - e.g 95%, while specially chosen subregions incur very low EoT scores. In Appendix C.S we discuss our extension to Athaayy et al. (2018) used in this experiment.
has an EoT 2 90%. We
We execute the experiment on the first MNIST ConvBig transformation in Table 2 We note that the algorithm from Athhayy et al.) (2118) relies sampling and does not scale to high dimensional Loe perturbations. The algorithm produces 24 different regions, significantly less than our 44 provable regions. The 24 empirically robust adversarial examples produced achieve average EoT of 95.5%. To demonstrate the non-uniformness of the empirical robustness, for each region, we considered a subregion of the example, with dimensions of size 10% of the original example, placed at the corner of the example closest to the original unperturbed image. We calculated the EoT of these subregions and found that 14/24 regions had an EoT of 50%, with 9 having an EoT of 0%.
This demonstrates that the fundamental assumption that the EoT of a region is roughly uniform throughout does not hold and instead it is possible and even common in practice that a significant part of an empirically robust example is much less robust than the remaining region. Further, this often happens close to the original input image, thus providing the misleading impression that an empirically robust adversarial example is a much stronger adversarial attack than it actually is. This misleading behaviour suggests that provably robust adversarial examples, which cannot exhibit such behaviour by construction, provide more reliable method of constructing adversarial examples invariant to intensity changes and geometric transformations. We note that a limiting factor to the practical adoption of our method remains scalability to real world networks and datasets such as ImageNet, due to the reliance on certification techniques that do not scale there yet. We note that our method is general and efficient enough to directly benefit from any future advancement in verification.
5.5 COMPARISON WITH LIU ET AL. 2019
In this section, we extend the method proposed in Liu et al. (2019) to generate provably robust hyperbox regions against pixel intensity changes and compare the resulting algorithm PARADE. As the code provided in Liu et al. (2019) only applies to fully connected networks, we applied both their approach and PARADE on new 8x200 MNIST fully connected network with the same architecture as the one used in Table I To facilitate simpler comparison, the network was trained using the code provided in Liu al. (2019). We initialized both methods with the same overapproximation hyperbox O and compare the shrinking phase. With similar runtime (> 200s), out of 84 possible regions, PARADE and Liu et al. (2019) created 84 and 76 regions with median underapproximatton volume of 181 and 10t6, respectively. We point out that our method is capable of creating polyhedral regions and handle the geometric perturbations, while Liu et al. (2019) cannot.
CONCLUSION
We introduced the concept of provably robust adversarial examples- - large input regions guaranteed to be adversarial to a set of perturbations. We presented a scalable method called PARADE for synthesizing such examples, generic enough to handle multiple perturbations types including pixel intensity and geometric transformations. We demonstrated the effectiveness of PARADE by showing creates more and larger regions than baselines, in similar or less time, including regions containing a 10573 adversarial examples for pixel intensity and x 10399 for geometric transformations.

---

Published as a conference paper at ICLR 2022
REFERENCES
Martín Abadi, Ashish Agarwal, Paul Barham, Eugene Brevdo, Zhifeng Chen, Craig Citro, Greg S. Corrado, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Ian Goodfellow, Andrew Harp, Geoffrey Irving. Michael Isard, Yangqing Jia, Rafal Jozefowicz, Lukasz Kaiser, Manjunath Kudlur, Josh Levenberg. Dan Mané, Rajat Monga, Sherry Moore, Derek Murray, Chris Olah, Mike Schuster, Jonathon Shlens, Benoit Steiner, Ilya Sutskever, Kunal Talwar, Paul Tucker, Vincent Vanhoucke, Vijay Vasudevan, Fernanda Viégas, Oriol Vinyals. Pete Warden, Martin Wattenberg, Martin Wicke, Yuan Yu, and Xiaoqiang Zheng. TensorFlow: Large-scale machine learning on heterogeneous systems, 2015. URL tensorflow.org.
org/ Software available from
Maksym Andriushchenko, Francesco Croce, Nicolas Flammarion, and Matthias Hein. Square attack: query-efficient black-box adversarial attack via random search, 2019.
Anish Athalye, Logan Engstrom, Andrew Ilyas, and Kevin Kwok. Synthesizing robust adversarial examples. In Proc. International Conference on Machine Learning (ICML), volume 80, pp. 284 293, 10-15 Jul 2018.
Mislav Balunovic and Martin Vechev. Adversarial training and provable defenses: Bridging the gap. 2020.
Mislav Balunović, Maximilian Baader, Gagandeep Singh, Timon Gehr, and Martin Vechev. Certifying geometric robustness of neural networks. Advances in Neural Information Processing Systems 32, 2019.
Nicholas Carlini and David A. Wagner. Towards evaluating the robustness of neural networks. In Proc. IEEE Symposium on Security and Privacy (SP). pp. 39-57, 2017.
Ping-yeh Chiang, Renkun Ni, Ahmed Abdelkader, Chen Zhu, Christoph Studer, and Tom Gold- stein. Certified defenses for adversarial patches. In 8th International Conference on Learning Representations (ICLR (an0ecanc)lled) International Conference on Learning Representations, 2020.
Jeremy Cohen, Elan Rosenfeld, and Zico Kolter. Certified adversarial robustness via randomized smoothing. International Conference on Machine Learning, pp. 1310-1320. PMLR, 2019.
Francesco Croce and Matthias Hein. Minimally distorted adversarial examples with fast adaptive boundary attack, 2019.
Ruediger Ehlers. Formal verification of piece-wise linear feed-forward neural networks. In D. D'Souza and K. N. Kumar (eds.), International Symposium on Automated Technology for Verification and Analysis, pp. 269-286. Springer, 2017.
Logan Engstrom, Brandon Tran, Dimitris Tsipras, Ludwig Schmidt, and Aleksander Madry, Exploring the landscape of spatial robustness. In International Conference on Machine Learning, pp. 1802- 1811. PMLR, 2019.
Mare Fischer, Maximilian Baader, and Martin T. Vechev. Certified defense to image transformations via randomized smoothing. In Proc. Neural Information Processing Systems (NeurIPS), 2020.
Marguerite Frank and Philip Wolfe. An algorithm for quadratic programming. Naval research logistics quarterly, 3(1-2):95-10, 1956.
Timon Gehr, Matthew Mirman, Dana Drachsler-Coher Cohhn, Petar Tsankov, Swarat Chaudhuri, and Martin Vechev. Ai2: Safety and robustness certification of neural networks with abstract interpretation. In 2018 IEEE Symposium on Security and Privacy (SP), pp. 3-18. IEEE, 2018
Ian Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. In International Conference on Learning Representations (ICLR), 2015.
Divya Gopinath, Hayes Converse, Corina Pasareanu. and Ankur Taly. Property inference for deep neural networks. In 2019 34th IEEE/ACM International Conference on Automated Software Engineering (ASE), pp. 797-809. IEEE, 2019.
10

---

Published as a conference paper at ICLR 2022
Gurobi Optimization, LLC. Gurobi optimizer reference manual, 2020. gurobi. com
URL http:/ /ttp://Www Www.
Shengyuan Hu, Tao Yu, Chuan Guo, Wei-Lun Chao, and Kilian Q. Weinberger. A new defense against adversarial images: Turning weakness into strength. In Proc. Neural Information Processing Systems, (NeurlPS), pp. 1633-1644, 2019.
Max Jaderberg, Karen Simonyan, Andrew Zisserman, and Koray Kavukcuoglu. Spatial transformer networks. arXiv preprint arXiv: 506.0202000. 2015.
Nikola Jovanović, Mislav Balumović, Maximilian Baader, and Martin Vechev. Certified defenses: Why tighter relaxations may hurt training. arXiv preprint arXiv:2102.067000 2021.
Alex Krizhevsky. Learning multiple layers of features from tiny images. 2009.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86( (6(11):227--222) 1998.
Mathias Lécuyer, Vaggelis Atlidakis, Roxana Geambasu, Daniel Hsu, and Suman Jana. Certified robustness to adversarial examples with differential privacy. In 2019 IEEE Symposium on Security and Privacy, SP, pp. 656-672. IEEE, 2019.
Linyi Li, Maurice Weber, Xiaojun Xu, Luka Rimanic, Tao Xie, Ce Zhang, and Bo Li. Provable robust learning based on transformatiinnsseeciie smoothing. CoRR, abs/2002.12395 2020.
Chen Liu, Ryota Tomioka, and Volkan Cevher. certifying non-uniform bounds against adversarial attacks. In International Conference on Machine Learning, pp. 4072-4081. PMLR, 2019.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant adversarial attacks. In Proc. International Conference on Learning Representations (ICLR), 2018.
Matthew Mirman, Timon Gehr, and Martin Vechev. Differentiable abstract interpretation for provably robust neural networks. International Conference on Machine Learning, pp. 3578-3586. PMLR, 2018.
Tianyu Pang, Kun Xu, Yinpeng Dong, Chao Du, Ning Chen, and Jun Zhu. Rethinking softmax cross-entropy loss for adversarial robustness. In Proc. International Conference on Learning Representations, ICLR, 2020.
Yao Qin, Nicholas Carlini, Garrison Cottrell, Ian Goodfellow, and Colin Raffel. Imperceptible, robust, and targeted adversarial examples for automatic speech recognition. In International conference machine learning, pp. 5231-5240 PMLR, 2019.
Hadi Salman, Jerry Li. Ilya P. Razenshteyn. Pengchuan Zhang, Huan Zhang, Sébastien Bubeck, and Greg Yang. Provably robust deep learning via adversarially trained smoothed classifiers. In Proc. Neural Information Processing Systems (NeurIPS), pp. 12389-1330,, 2019.
Alexander Schrijver. Theory of linear and integer programmiing. John Wiley & Sons, 1998.
Sanchari Sen, Balaraman Ravindran, and Anand Raghunathan. EMPIR: ensembles of mixed pre- cision deep networks for increased robustness against adversarial attacks. In Proc. International Conference Learning Representations, ICLR, 2020.
Gagandeep Singh, Timon Gehr, Matthew Mirman, Markus Püschel, and Martin Vechev. Fast and effective robustness certification. In Advances in Neural Information Processing Systems, pp. 10802-10813, 2018a.
Gagandeep Singh, Jonathan Maurer, Matthew Mirman, Timon Gehr, Adrian Hoffmann, Petar Tsankov, Dana Drachsler Cohen, Markus Püschel, and Martin Vechev. ERAN: ETH Robustness Analyzer for Neural Networks, 2018b. htL.httss::/// wttpgttthhhu...o... com/ wetchhaari/eee
Gagandeep Singh, Timon Gehr, Markus Püschel, and Martin Vechev. An abstract domain for certifying neural networks. Proceedings of the ACM on Programming Languages, 3(POPL):41, 2019.
11

---

Published as a conference paper at ICLR 2022
Christian Szegedy, Wojeiech Zaremba, llya Sutskever, Joan Bruna, Dumitru Erhan, lan Goodfellow, and Rob Fergus. Intriguing properties neural networks. arXiv preprint arXiv:1312.6199, 2013.
Yusuke Tashiro, Yang Song, and Stefano Ermon. Output diversified initialization for adversarial attacks. arXiv preprint arXiv:2003.068/) 2020.
Florian Tramèr, Nicholas Carlini, Wieland Brendel, and Aleksander Madry. On adaptive attacks to adversarial example defenses. CoRR, abs/2002.08347, 2020..
Shiqi Wang, Yizheng Chen, Ahmed Abdou, and Suman Jana. Enhancing gradient-based attacks with symbolic intervals, 2019.
Chang Xiao, Peilin Zhong, and Changxi Zheng. Enhancing adversarial defense by k-winners-take-all. In Proc. International Conference Learning Representations, ICLR, 2020.
Huan Zhang, Tsui- Wei Weng. Pin- Yu Chen, Cho-Jui Hsieh, and Luca Daniel. Efficient neural network
robustness certification with general activation functions. In Advances in neural information processing systems, pp. 4939-4948, 2018.
Tianhang Zheng, Changyou Chen, and Kui Ren. Distributionally adversarial attack. Proc. AAAI Conference Artificial Intelligence, 33:2253-225 -2600, 07 2019.
12

---

Published as a conference paper at ICLR 2022
Table 4: Comparison between regions created with different values for the parameter c introduced in Algorithm| I on the MNIST ConvBig Sc(20) 1(0,1,0,1) experiment. Columns Under and Over show the median bounds on the number of concrete adversarial examples contained within the regions. The columns Time and #It depict the average time and number of iterations taken by Algorithm [
#VERREG
UNDER
OVER
TIME
#IT
0.45
25
-0
< 10
264
1.6
0.55
36
> 10
< 10
333 S
2.9
0.65
42
1061
< 10174
441
4.5
0.75
44
> 10
< 110281
5855 S
6.7
0.85
44
> 10213
< 10
871
10.6
A ADDITIONAL EXPERIMENTS
A.1 DEPENDENCE OF PARADE ON THE VALUE OF
In this section, we examine the effect of the parameter c, introduced in Algorithm 1 on the size of our provably robust adversarial examples. We show how the number of conerete adversarial examples contained in our regions robust to geometric transformations vary, as a function of c. Table [ depicts the results the MNIST ConvBig scaling and translation experiment, originally depicted in Table The columns Time and #It depict the average time and number of iterations taken by Algorithm in order converge. Similarly to Table 2 the #VerReg column depicts the number of verified regions. The results correspond to our intuition for c: the higher the value of с is, the greater the volume produced by our method and vice versa. Further, we observe that for higher values of e, our algorithm succeeds to produce significantly more verified regions. We chose the value = 0.65 for the experiments in Table in the main body of the paper, as it represents good trade-off between the speed and the number of regions recovered, shown in Table
B FURTHER DETAILS ON OUR ALGORITHM DESIGN
B.1 ADVERSARIAL EXAMPLE DEFINITIONS
In this section, we provide precise definitions of our adversarial examples robust to pixel intensity changes and geometric changes, used in Table and Table 2
B. ADVERSARIAL EXAMPLES ROBUST TO Loe PIXEL INTENSITY CHANGES
Definition 4. For an image r E I neural network f. adversarial budget E R, and adversarial class yt + f(x), a convex region I S Re called an adversarial example around robust to pixel intensity changes, for all points 7 E I it is satisfied that | xo/o0o S and yt: = f()).
B.1.2 ADVERSARIAL EXAMPLES ROBUST TO GEOMETRIC CHANGES
Definition 5. Let T 12 x IR Te be a geometric perturbation that takes an image x E Ro and a vector E IR' of geometric parameters, bounded within the hyperbox [p' pp",,,, given by the lower and upper bound vectors p'. .p" E RR,, and produces geometrically transformed version of the image, denoted F, that should be classified the same as x. For image E RR neural network I, and adversarial class yt. # [xx), corvex region I C R is called an adversarial example around robust to the geometric perturbation T, iff for all points E I it is satisfied that p E (p', ,p'" and yt = f(T(x)))
We note that this definition allows for T be a complex composition of simple geometric transfor- mations such as rotations and translations, as it is the case in Table In this case, is a vector of the parameters of all transformations. We further note that while Definition geometric parameters one can also look at I. the region in image space obtained by propagating all possible ò through T. DeepG Balunović et al. (2019) overapproximates the later region in image space with a polyhedra to produce the polyhedral region I in image space. In Table 2] report the underapproximation and overapproximation sizes of I in terms of number of concrete images contains.
in terms of the
13

---

Published as a conference paper at ICLR 2022
Algorithm 2 [GD_PROJECT
I: func [GD__PRIECT((( (", ut, 1'=1, u² hp, a, b, P.-1)
2: Ie Clip(l', 1'm u² u²=)) u' Clip( u', u²=1)
4:
val = hp u'
5:
if val 2 -Pi-1 then
6: return 11, u²
7:
end if
8:
T'Jaso
P 10:-00011110
val
uu') u'Ja<o- = [v ( (91-1-b)
9:
10:
Clip(l', : 1-=, u
11: u² Clip(ui u', 1', u²=1)
RETURN 1 n²
12:
end func
B.2 DETAILED DESCRIPTION OF SHRINK LP
In this section we describe in detail the function SHRINK_LA LP, used to shrink 24,1 to Us when generating examples robust to pixel intensity changes, based on the parameters (x:) and pt-1- SHRINK_I. defines two sets of LP variables for the lower bounds / E R and the upper bounds u' E R0 of U4 As described in Section 3.2 the LP optimizes the sum of widths of the dimensions Uf i... Σ ([u"), [('
Recall that T (x:) ) is a linear function of æ and, thus, can be represented as T,f-((x) aa +b. As described in Section 3.2 the we define needs enforce mingeu, I, [x² 2 -P--1- We rewrite mingeu, (z) as:
hp( I", u²)) max(0, a) -1' min(0, a) - +
Since hp("', w²) is linear function of l' and u', add the constraint hp(1", u²) 2 P;-1 to the LP. This results in the LP problem:
7, argmax Σ ([w')) [1'1))
s.t. hp 2 Pi-1 S [1',, [w'] S |u' for all j.
where 1i-1 uu=11 E wh represent the lower and upper bounds of the second constraint enforces
U: C U;-1 and 7 u² e TR denotes the LP solution. Finally, SHRINK_LA outputs the hyperbox
24: [','].
B.3 DETAILED DESCRIPTION OF SHRINK_ PGD
In this section we describe in detail the function SHRINK_ PGD, used to shrink Ui- to Ui for generating regions robust to geometric transformations, based on the parameters L (z" and pi-1-
SHRINK PGD relies on PGD to optimize the log volume of U4 with respect to its lower and upper bounds, described in Section 3.2 The optimization problem can be written as:
7 T argmax Ene
j=1 log [u'l; [19]g)
s.t. hp("" u²) > Pi-1 11 - [r),
- [w',,
< ju' for all j.
where the same notations as in the previous section. Since we rely PGD, we need to define how to project values of ( and u' that violate the constraints in Equation
Algorithm 2 demonstrates the heuristic notations above, and treats I and u', as the concrete values of 1 and u² to be projected, instead of treating them variables.
for the projection. Algorithm Santtmmmssighhu slightly abuses the
first clips 1 and u² to enforce U, C (Line 2 B). It then checks whether hp(l', w') 2 -P:1 is satisfied and if returns (Line 4 7. Otherwise, all elements of I' corresponding positive values
14

---

Published as a conference paper at ICLR 2022
Table 5: Neural networks used in our experiments. For each, we list the number layers and neurons, well as, their type (fully connected (FFN) convolutional (Conv)).
DATASET
MODEL
TYPE
NEURONS
LAYERS
8 x 200
FFN
1,610
MNIST
CONVSNALS
CONV
3,604
3
CONVBIS
CONV
48,064
CONVSMALS
CONV
4,852
3
CIFARIO
CONvBEC
CONV
62,464
of a, [2'as and all elements of u' corresponding to negative values of a, [u']acu, are adjusted by a factor Ph-1-b where val = hp(I", u²) - b. This enforces hp(l', u²) 2 -Pi-1 (Line 8 In rare cases the second projection can result in values of 1 and u² violating U; C U Our solution is clip again (Line I0
val
After the last clipping operation, in the rare case mentioned above the returned values for I' and u² violate hp((", u²) -P However, did not find this to be problem in practice, as it occurs rarely. Further, one can view such violations, as choosing a different value for in Algorithm resulting in different value for PP--1
C FURTHER DETAILS ON EXPERIMENTAL SETUP
C.1 NETWORKS
Table shows the architectures of the networks on which we evaluate.
C.2 FURTHER DETAILS ON THE EXPERIMENTAL SETUP IN SECTION 5.1
In this section, we provide further details on the experimental setup in Section this experiment, for creating O (Frank & Wolfe 1956) and PGD with step size 0.le and 0.01e, respectively. For the PGD examples, use output diversification TTshiro al. 2020) with 5 iterations. Throughout the experiment, we set 0.99 and multiply it by factor of 0.99 at each iteration of Algorithm
2500 adversarial examples each from the Frank-Wolfe optimization algorithm
C.3 FURTHER DETAILS ON THE EXPERIMENTAL SETUP IN SECTION 5.2
In this section, we provide further details on the experimental setup in Section For all experiments in Table compute O using random sampling attacks which the ffute-of-the-att for geometric transformations (Engstrom et al. 2019). For the dimensional experiments, we rely on 15000 random samples, while for the 4D configurations for the 4 dimensional CIFAR 10 experiment, where we use c = 0.75 to increase the precision of we execute SHRRINK_ PGD with 50 initialization and 200 PGD steps of size 5 x 10-5, For CIFAR10 experiments, we use 500 initialization and 50 PGD steps instead.
50000. We
0.65 for all experiments, except
PARADE. For the MNIST experiments in Table 2
C.4 DETAILED DESCRIPTION OF EXPERIMENTAL SETUP SECTION 5.3
Neural networks In Section 5.3 we experiment with networks f with the same architectures in Table Following the standard practices for training networks used alongside smoothing, outlined in Cohen et al. (2019), we trained the networks images with added Gaussian noise with standard deviation 0.15.
need to select and compute Radv using Definition [ For all methods we use a = 0.005, as suggested by Cohen et al. (2019). We select the value that produces the biggest adversarial strength Radv for method and use it for computing Rgt for all methods. We note that tuning o for the individual attacks generated by A is very computationally intensive and therefore avoid it.
Selecting and a In the experiments in Section 5.3
15

---

Published as a conference paper at ICLR 2022
In this paragraph, detail how the adversarial distance R' is chosen. We choose heuristically, for each individual z. For each æ, we select R' by searching for the smallest adversarial distance f. where at least 10% of 500 attacks with A on succeed but exclude images 2, whose R' is more than 33% bigger than the certified radius of g. This procedure allows us to select the adversarial distance R², that is neither problem trivial, as outlined in Section 2.3 In particular, for this choice of R' the smoothed classifier g is likely to be attackable, since f contains enough attacks for high density input adversarial region to exist. On top of that, the exclusion of images z with too big adversarial distance R' experimentally allowed us to exclude trivial attacks, for which x: is attackable for most classes on g.
Selecting R'
small, nor too big, which is important avoid making the
C.5 DETAILED DESCRIPTION OF ADAPTED BOT USED IN EXPERIMENTS IN SECTION 5.4
produce the empirically robust adversarial examples for the experiment Section 5.4 We define an optimization procedure, where seek a hyperbox geometrie region Hemp C I to defined in terms of the lower bound temp E Rn and the upper bound Vemp E 3R vectors. We seek to find Zemp within the set of allowed geometric transformations I RT such that Zemp is an empirically robust adversarial example with maximal log volume, and high Eo Similarly to AAthalye et (2018) EoT is calculated on set of samples from Memp We rely on differentiable bilinear interpolation (Jaderberg et al., 2013) to allow gradients to flow through the geometric transformations we consider and optimize Temp and Uemp using PGD.
In this section, diseuss the extension of Athalye et al. 2018) )
D ANALYSIS OF ALGORITHM
In this section, we analyze the properties of PARADE.
D.I SOUNDNESS OF ALGORITHM I
Theorem 1. If Algorithm converges, it returns provably robust region U.
Proof. Algorithm T can only complete its execution using Line or Line 18 Since we assume the algorithm successfully converged, returning at Line 18 is impossible. Therefore, the algorithm must have returned the region 14-1 at Line and, therefore, eiーl must non-negative (otherwise we would not have taken the right branch at Line However, ei is obtained by executing the verifier V on U at Line By the definition of our verifier V, returns non-negative ed only if 1 is provably robust. This finishes our proof.
D.2 CONVERGENCE OF ALGORITHM
In this subsection, we demonstrate that Algorithm I converges exponentially fast under a suitable assumption for the monotonicity of the neural network certification method V. To this end, we introduce the following definition of monotonicity of V, that we will leverage for the rest of the subsection.
Definition 6. Let V(f.I, y1) be neural network certification method that returns the certification objective (x) for an input region I and target Yt on the neural network f. We call V objective- monotonic if for all ff and input regions and y with X C y the property:
min L 1xx(x) xEX
min L2 (xx xEX
is satisfied.
Intuitively, Definition 6 states that a verifier is objective-monotonicc if the certification objective produced for smaller region X' is always higher (closer to verification) than the certification objective produced for a bigger region }, when both of them are optimized over the smaller region X.
We note that most practical neural network certification methods, including DeepPoly, are not objective-monotonic that is one find triples f, X' and y violating the definitions above.
16

---

Published as a conference paper at ICLR 2022
However, in practice we find that for all practical neural network certification methods the definitions hold for most triples. This is expected, as for violating triples we know that the overapproximation generated for X' needs to be larger than the one generated for V. Intuitively, if that was the case for large portion of the triples, the certification method will not be tight.
Next, leverage this defition demonstrate that algorithm converges exponentially fast under the idealized condition that the certification method used is objective-monotonie
Theorem 2. For objective-monotore certification methods V in Algorithm [ the certification error at the i-th iteration e' converges exponentially fast towards 0 (towards certification).
Proof. To prove Theorem we will leverage the definition of objective-monotorie certification method above to bind the certification error between consequitive iterations of Algorithm [ We will then use the bound to derive bound on the certification error e' in terms of the intial certification error e.. Finally, we will use the bound to show the exponential convergence.
Since U, S 11 we can apply Definition to get the inequality:
min L L'(x) 2 min L L (z). sElf:
xell;
By construction of U4, we further know:
min
(x) 2 Pi-1 = e--1
EEM4
Combining both inequalities and noting that e² = min L' (x)),, we get:
2e--1. c.
Since Equation Cicautioonooldr holds for all i, we can apply it recursively on its right-hand side to get:
e' e.
(3)
We recall that e' is negative unless U4 verifies. Therefore by Equation fast towards 0, regardless of e
converges exponentially
E PROVABLY ROBUST POLYHEDRA ADVERSARIAL EXAMPLES
In this section, we show an extension PARADE that allows adversarial examples represented as a general polyhedron shapes P in the neural network imput space. The approach relies on the underapproximation and overapproximation boxes 2/ and O presented in the main body, to guide the search of /P and is demonstrated in Figure The results of the method presented in this section were shown in Table Section 5.1
generate provably robust
E. BACKGROUND
Our method for generating polyhedral robust adversarial examples requires more restricted form for V, compared to the algorithms presented in the main body. In this subsection, we discuss the relevant background and the additional requirements we pose on V and introduce the relevant notation for the rest of this section.
For this section, we will focus on ReLU-based neural networks. We note that our concepts can easily be extended to networks with other activation functions such as sigmoid or tanh. We consider neural network with / layers , ft.
The first - layers are of the form [x(x) max A; + b:) for E {I...., 1} and the final layer is of the form f((x) A₁ x + b,. The neural network is the composition of all layers: = fi ... f1. Let be the number of neurons in layer i. If
ef, is the input to the j-th ReLU activation in layer and 2T, is the corresponding ReLU output, we can represent the neural network as the following system of constraints: For E {1......] and j E {1, (1,...,,d, n4),
2i = [0ol,
Σ
[A 2
2N max(0, 2
17

---

Published as a conference paper at ICLR 2022
Polyhedral Region
Adjust Planeei
Intialize
Vartfes
Planes
Try to serty by networrs and haporp
Adjust hypersoones tiases until they do underspreemmaiin
Reprot until polyhecin rogion
Figure 2: Overview of our method for generating provably robust polyhedral adversarial examples. The green triangle denoted T represents the ground truth adversarial region. The dashed blue rectangle denoted O and the violet dotted rectangle denoted 2/ represent the fitted overapproximation and underapproximationn boxes, respectively. The solid black lines represent hyperplanes generated by the certification procedure V, while their dash-dotted counterparts represent the hyperplanes after bias-adjustment. The small arrows going out of the hyperplanes in Step and Step 2 represent the direction which is retained by the hyperplanes' corresponding half-spaces. The output polyhedral region denoted P is shown in red in Step 3.
2/j
+ psi
Mio
Maj
Ni.
No.
2
Fi.j
2
21.3
2.
2
li.j
1i,9
Ug
(a)
(b)
(c)
Figure 3: Convex approximations for the ReL.U function: (a) shows the triangle approximation Ehlers (2017) with the minimum in the input-output plane, (b) and (c) show the two convex
approximations used in DeepPoly Singh et al. (2019). In the figure, A / 4,)) and
Mij -4i uig/ l..)). The ligure is taken from Singh al. (0119).
Here, zh, describes the j-th of no input activations. We call the two types of constraints affine constraints and ReLU constraints, respectively. We additionally constrain our inputs 2 be points inside polyhedron P C RTo. An adversarial class y/ has the highest score on all inputs P if min zf.y) 0 with respect to all constraints for all y E {1...., ni} \ {y,). The goal in verify that this is true.
section will be to find large polyhedron P for which
Linear approximations of ReLU As reasoning about neural network constraints directly is often intractable, given bounds ligj S 2f, S Mi.j. the triangle approximation (Ehlers) 2017) relaxes the ReLU constraints such that all involved inequalities are linear:
= 2 2
= 2 0,
= - X 2 + P4..
Figure 3
(a) visualizes the triangle approximation. Here, Aı, = uu,s/ 4.j) and pt.5 = 4.j u/.s/ u - 4.)) are selected such that this set of constraints describes the convex hull of the ReLU constraints in the (zf 2[,) 2f,)-plane plaan and the given bounds.
The DeepPoly approximation (Singh et al. 2019) further relaxes the triangle approximation by keeping only one the lower bounds on each variable 2 It picks either 2[,; 2 of, or 2 2 0. whichever minimizes the area of the resulting triangle in the (2f 2T,) -plane. Figure (bb) and (c) show the two convex relaxations used in DeepPoly.
18

---

Published as a conference paper at ICLR 2022
We can obtain 4,3 and W4 by optimizing each component of 2i according to the previously determined constraints for layers O,..., i. We note that in the special case where 14,, S or 4. 2 0, no approximation is needed and 2 is directly assigned 0 or "i,z respectively. Neurons for which the approximation is needed are called undecided.
Computing neuron bounds Most verification algorithms based convex relaxation start with chosen input region for which they calculate the bounds L and Us, of æf, in layer-by-layer fashion, where the constraints for previous layers are used to derive the bounds for layer i. In addition to DeepPoly and the triangle approximation, this is also true for other commonly used convex relaxation algorithms such as CROWN (Zhang et al. 2018) and DeepZ (Singh al. 2018a).
Next, we briefly descrihe how the bounds are computed for particular layer in DeepPoly. We focus on DeepPoly since it is the particular convex relaxation algorithm chose to employ in this section. For all neurons, DeepPoly stores a single linear lower and upper bound inequality. These inequalities bound the neuron's value in terms of the values of neurons from previous layers in the network. For ReLU neurons, these are the inequalities described above. For affine neurons, these are simply the affine transformations, where the affine equality is converted a pair of inequalities.
To arrive at the bounds l and i of 2[.) DeepPoly repeatedly backsubstitutes variables in the linear inequalities of oi with their corresponding linear inequalities from previous layers. The process continues until we arrive at linear inequalities Lt, S 2², S (z))) with (z)(2) a, and (z)(2) = T.j x + bi.j denoting linear functions in terms of input variables r E u with coefficients ( Da.j E R090 and Le., bi.j E R. The final bounds lijj and Wi,j are obtained by optimizing the respective functions Tn,((z) (z)) and (z) over the input region.
We note that our algorithm does not depend on details of DeepPoly's backsubstitution algorithm: only requires the existence of linear functions Li)(x: and (z) bounding neuron values 2 in terms of input activations. This makes it compatible with other popular verification algorithms based on convex relaxation, such as CROWN (Zhang et al. 2018) and DeepZ (Singh et al. 2a).
Certification Objective To certify the robustness of an input region, V needs to certify that min(2" 27,,, - > 0 for all E {I....,n n }. To calculate lower bounds on those min- ima, a common trick to introduce an affine layer that computes the objectives z 2f,8 for d
each We will refer to this layer as objective layer. To obtain lower bounds on our objectives, we compute lower bounds of the corresponding neuron activations in the objective layer with the usual backsubstitution procedure.
For the rest of the section we will denote the backsubstituted linear lower bounds on our objectives in terms of input activations for given target yo with (z) G1+1,y + b1+1. for each y.
Finally, verify that (if, zT,y) > 0, it suffices to show that (x) (x) >> 0 for each point
in the input region and all * y1- We note that the function denoted L (x) in this section corresponds to the function denoted Ly (x) in the main body.
E.2
COMPUTING P
The algorithm for computing P is presented in Algorithm
It takes input:
The neural network f. as described in Section E.
The underapproximation hyperbox U4
The overapproximation hyperbox O.
A neural network certification method V(f. Pi-1, i, j) that takes neural network f. polyhedron Pn-1 at iteration it 1, the layer number and the neuron number and returns the linear functions Li,3 (z) and (z) and the corresponding concrete bounds 45,5 and Uayj (See Section E.II.
The adversarial attack's 's target class ye-
The maximum number Pa of iterations used to generate the polyhedron P.
The algorithm computes P, such that U/ C P S O is satisfied. We motivate this choice by noting that know that 2/ is certifiably robust and it is therefore lower bound on P. The algorithm generates
19

---

Published as a conference paper at ICLR 2022
Algorithm 3
1: func GEN POLY( f. U, O, V, Ut. Ph)
Po R0=0
3: for E (1, do
4:
hs.. Ver Gen Obj Planes( f. 2, Pa-1, 1, V, y1)
5:
hss Gen Bound Planes( f. U, Pa- V
Pa = Add Planes( Pa-1; hsb h8.)
7:
if Ver then
8:
return Pa-1 end if
9:
10:
end for
return CaivedToConverge
12:
end fune
Algorithm 4 BENGGOOOS LLL__BBB__AAAAA PLANES
1:
fune GEN OBJ PLANES( S, u, Pa mb)
hs. =
3: Ver True
4: for E fl,...,,it (8r} do V(f, Pa- 1 1+1, v)
5:
Li-1.g - 1u-
if ly S then
7:
Ver = False
8:
(z) = Adjust Bias(U, (+)xx()))
9:
hs. += (L)+),(()) 20]
10: end if
11: end for
12: return hs Ver
13:
end fune
sequence of polyhedra Po ... ... Pp with Po = O. At each iteration, it computes two sets of half-space constraints - hs (Line and hs ((Line corresponding to the neurons in the objective and the affine layers the network. We detail how these constraints are computed in the next two paragraphs. We add these constraints to the polyhedron from the last iteration Pa-1 to obtain Pa (Li The algorithm terminates when Pa-1 certified to be robust (Line 7- p and Pa-1 is returned. The result of our algorithm is represented by the red region denoted as P in Step 3 in Figure 2 We note that, since Po O, P S O is guaranteed by construction, as each subsequent iteration of the algorithm shrinks the polyhedron further. However, U C P depends the choice of the half-space constraints.
Generating Certification Objective Constraints Algorithm 4etaills the procedure use to collect the half-space constraints corresponding to the objective layer of the network. To obtain constraints from V. first compute the linear functions L4+1, and their respective certification errors by for all output classes y E (1..... .......ny } \. {ye} (Line 5). We know that adding the constraints 1,,1,1/)))) > 0 our polyhedron Pa-1 will result in certifiably robust region Pn. however the region will not obey U4 C Pu.- Therefore, we instead adjust the bias of constraints, so that the resulting hyperplanes T4 (I) = do not intersect (Line 8). This process is depicted geometrically in and will be described in more detail below. All resulting bias-adjusted hyperplanes are collected in the set hs (Line and returned. We note that if by > 0 for some y, the half-spaces are trivial. That TL++1.v (x) 2 0) n Pa-1 Pa-1, and thus they are filtered out of hs. (Line 6). In addition to detecting the trivial constraints, we use the certification errors ly to check Pa-1 is certifiably robust and return the result alongside hs a in Line
Step in Figure and
L1+1.e (x)
Issues Related to Using Only Objective Constraints In our experiments, we found that only adding bias-adjusted objective constraints leads to slow convergence of our algorithm. In particular, we found that the first few iterations of the algorithm result in a substantial improvement in the certification objective. However, after this initial fast progress, we observe that the change in the certification objective becomes very small. The reason for this is that the generated constraints from consecutive executions of V are very similar. We conjecture that the underlying reason is that the constraints no longer change the input shape enough to substantially change the convex approximation of the
20

---

Published as a conference paper at ICLR 2022
Algorithm 5 GEN BOIN__BOND__LAAATE
1: fune BEIN_BOUD___ PLANNS(S U, Pa-1, V)
h8,
3: for i (1, 1/ do
4: for j (1, do Li,(x), (i)( way =V(,, Pa-1, i, if 11, S and u., 2 then
5:
7:
(x) = Addjust Bians_ [z)(
8:
(z)(z) = Adjust Bias( (z))
9:
hss += [+) 2 0, Uis(x) 2 0]
10: end
11: end for
12: end for
13: return hss
14:
end func
network. This is in contrast to what we observe when computing the underapproximation hyperbox region U. The difference between the two settings comes from the number of added constraints per iteration. For U, usually many lower and upper bounds are adjusted each iteration, while the objective constraints added are much less, especially for the pixel intensity changes experiment, where the input is very nigh-dimensional.
Generating Constraints from Affine Layers To facilitate faster convergence, we generate addi- tional constraints for all undecided neurons in the network. We generate two constraints, one with respect to the lower bound of the neuron (x) 0 and one with respect to the upper bound (Z) < 0. Algorithm 5 describes the process. (x) and (z)( are computed by V (Line alongside their concrete bounds 4.5 and us.j. The concrete bounds are used to check which neurons are undecided (Line 6).
The generated constraints have the effect of making the neurons decided, while also enforeing
substantial change in the convex relaxation of the neural network. Note that the newly obtained
constraints are bias-adjusted similar to the objective constraints described above (Line 7 We point out that the bias adjustment described below takes care of the problem that Li, (z) 2 0 and
Ui. (x) < 0 cannot be simultaneously true. Empirically, these hyperplanes serve an important role for improving the convergence rate of our algorithm. Algorithm Cjolllect them in the set hs, 6 (Line and returns them to be added to Pa-1-
Hyperplane bias adjustment So far, we have discussed how constraints are generated but not how we adjust their biases. The bias adjustment algorithm is given in Algorithm 6 The bias adjustment for a lower bound constraint ha(x) 2 O enforces that the intersection of the constraint and the
given underapproximation hyperbox 24 is U. It does by computing hmiin min()(()))(Line)) 2 æsut
and changing the given constraint to hxx)= 2 Amin (Line 4). The optimization Amin min(h(#))
zetl
is analytically solvable, as demonstrated Section B.2 Note that our algorithm adjusts only the constraints with negative hani (Line 3) since constraints with positive Amin already satisfy the
property. The following lemma shows the soundness of our adjustmjstt algorithm:
Lemma 3.
The intersection of the bias-adjusted half-space constraint π(xx)) 2 0 defined in Algo- rithm with with
U is U.
Proof. By the construction of hmin. for all points x E l we have h(z) 2 hmin. We distinguish two cases for the value of haain - non-negative and negative.
If Amin 2 O. the bias adjustment badj is assigned
and h(x) h(z). Since h(x) > hmin for all points x E u, h((z) = h(x) 2 Amin 2 0 for all points x E U. Therefore, there does not exist point in 24 for which the bias-adjusted half-space constraint h(x) 2 0 is violated. If
hinin < 0, the bias adjustment dayj is assigned to huin and h(x)) = h(x) Amiu- Therefore,
hxx)) h(x:)) Amin 2 hmin hmin for all points E U. Analogously to the other case,
21

---

Published as a conference paper at ICLR 2022
Algorithm 6 ADJUST_BIAS
1: func ADJUST BIAS(UA Ut, h(z))
Amin (in(
HEll
3: bulj min( O, Amin
4: h(xr) = h(x)- balj
5: return h(z))
6: end fune
Mx)) 2 0 is not violated by the points in U. Since in both cases h(x) 2 0 is not violated by any points in M4 the intersection of the constraint and U is simply U.
The bias adjustment for upper bound constraints Mx) 2 O is achieved by calling Algorithm 6 with -h(z), as Line 8 in Algorithm 5
Adapting DeepPoly Polyhedral Input Regions Out of the box, DeepPoly only handles tification of hyperbox input regions. This is because in order to obtain the concrete bounds 4, minger Li,j (x) and Uij max,er (z)(2) for an input region I C Ie it uses the an- alytical solution of the optimization problems discussed in Section B.2 In order to use DeepPoly for polyhedral region I, we solve the optimization problem using an Linear Program (LP). This is computationally expensive - it involves solving two LP instances per neuron. For large networks, this can be prohibitive.
To alleviate this issue, in the first iteration of Algorithm 3 we remember which neurons are undecided. The computation of the undecided neurons the first iteration can done using regular DeepPoly, solve the LP instances only for the undecided neurons, while
as Po- O. In future iterations using the Po bounds for the decided neurons. This optimization is sound, since we have Pi: S Po by construction. This improves the performance substantially- - for most certifiably robust input regions in Resed networks we have just a few undecided neurons.
Proving that P constraints U and contained within O In this paragraph, we present proof for the desired property of Algorithm 3 that P constraints U and is contained within O.
Theorem 4. For all polyhedral regions P generated by Algorithm 3 u C O holds.
Proof. To prove P C O, we leverage the fact that the polyhedra P is constructed from the overap- proximation box O by intersecting with the half-space constraints hbj, and hbb Since all constraints only reduce the volume of the polyhedra, it follows by induction over the generated half-space constraints that PP S O for all i. Therefore, P O.
To prove 41 C P. we note that the generated half salce constraints hbj, and hb; chosen such that hbj, nu = 21 and hb, nu = l for all (See Lemma 3). By applying this property by induction over the generated half-space constraints, it follows that C P, for all i. Therefore, U C P.
F VISUALISATION OF ROBUST ADVERSARIAL EXAMPLES
F.I DISCUSSION
Figure 4 shows an adversarial region provably robust intensity changes containing 10284 adversarial images produced by our method on MNIST ConvBig. The original image is of the digit 5, and all images in our region are classified as by the network. The colorbar in Figure FigureAquantifie the number of values each pixel can take in our inferred region. The yellow and violet colors represent the two extremes. The intensity of the yellow-colore contribute to more adversarial examples. The intensity of the purple-colored varies the least, thus the adversarial examples in our region are sensitive to the intensity values of these pixels. In our region, the intensity of most background pixels on the edges of the image vary lot, these are green. Violet and green color are more evenly distributed among pixels closer to the foreground (part of the digit "5"). Further, the intensity of several pixels in the foreground can also vary significantly. We
pixels can vary the most, thus these pixels
22

---

Published as a conference paper at ICLR 2022
Figure 4: Adversarial region robust to pixel intensity changes.
note that all yellow pixels oceur in the foreground. In summary, region capture examples that can be generated by significant variations in the intensities of several background and foreground
pixels. We supply visualizations for all of the experiments described in Section 5.1 and 5.2 in the next two sections.
F.2 ADVERSARIAL EXAMPLES ROBUST TO INTENSITY CHANGES
In Figure --8 we visualise adversarial examples provably robust to pixel intensity changes for the different networks in Table | For all figures, the colorbar on the right-hand side quantifies the number of values each pixel can take in our inferred region. The yellow and violet colors represent the two extremes. The intensity of the yellow-colore pixels can vary the most, thus these pixels contribute more to the adversarial examples.
In Figure 5 we show adversarial examples for the MNIST ConvBi g network. The 3 sub-figures represent the digits Our regions are of size 10220, 10284, and 10262, respectively.
and 3, but the images our regions are classified as 3, and 8, respectively.
5
9
(c)
Figure 5: Sensitivity of probably robust adversarial examples based on pixel intensity changes on the MNIST ConvBig network.
In Figure 6 we show adversarial examples for the MNIST Convšmall network. The 3 sub-figures represent the digits 2, 9, and 9, but the images in our regions are classified as 3, 5, and 4, respectively. Our regions of size 100 10852 and 10708 respectively.
In Figure 7 we show adversarial examples for the MNIST x 200 network. The 3 sub-figures represent the digits 5, 9, and 2, but the images in regions classified as 8, and 3, respectively. Our regions are of size 10 48 10 28 and 157 respectively.
In Figure 8 we show adversarial examples for the CIFAR10 ConvSmall network. The sub-fig -ib-fiiures represent a boat, a bird, and another bird, but the images in our regions are classified as an airplane, frog, and dog, respectively. Our regions are of size 10626 10563, and 10608 respectively.
23

---

Published as a conference paper at ICLR 2022
2
(a)
(h)
(c)
Figure 6: Sensitivity of probably robust adversarial examples based pixel intensity changes on the MNIST ConvSmal Smallmall network.
5
2
(a)
(h)
(c)
Figure Sensitivity of prohably robust adversarial examples based on pixel intensity changes on the MNIST & 200 network.
(a)
(c)
Figure 8: Sensitivity of prohably robust adversarial examples based pixel intensity changes the CIFARIO ConvSmall network.
F.3 ADVERSARIAL EXAMPLES ROBUST GEOMETRIC CHANGES
we visualise adversarial examples provably robust to geometric perturbations for For all figures, the colorbar on the right-hand side quantifies number of values each pixel can take in our inferred region. The yellow and violet colors represent the two extremes. The intensity of the yellow-colore contribute more to the adversarial examples. For all figures, the subfigures represent an adversarial example for each of the rows in Table
In Figure 9
the different networks Table 2
pixels can vary the most, thus these pixels
In Figure show adversarial examples for the MNIST ConvBig network. The 3 sub-figures represent the digits 6, 1, and 3, but the images in our regions are classified as 5, 8, and 7, respectively. Our regions have underapproximations of size 10959 10 10 and 1 respectively.
6
3
(a)
(b)
(c)
Figure 9: Sensitivity of probably robust adversarial examples based on geometric perturbations. Subtigures (a), (b) and (c) correspond the first, second, and third geometric perturbations for the MNIST ConvBig network in Table 2, respectively.
In Figure 10 show adversarial examples for the MNIST Convšmall network. The sub-fiee figuuis represent the digits 6, 1, and 3, but the images our regions are classified as 5, 8, and 7, respectively. Our regions of size 10115 1082 and 10 respectively.
24

---

Published as a conference paper at ICLR 2022
6
C
3
(a)
(h)
(c)
Figure 10: Sensitivity of probably robust adversarial examples based geometric perturbations. Subfigures (a), (b) and (c) correspond to the first, second, and third geometric perturbations for the MNIST ConvSmall 1 network in Table 2 respectively.
25


Reviews:
[{"review_id": "_fAuCG6CMN2", "reviewer": "Reviewer_N75e", "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": "### Strength\n\nThis paper has clearly stated its objective, the approach and the corresponding evaluations. The proposed technique is designed for a concrete objective, generating provably-robust adversarial examples. The approaches are well-documented in the paper and evaluations are conducted over several datasets and models. \nThe paper has spent a lot of space explaining the technique from a high-level perspective down to its implementation details, which helps the reader to better understand the algorithm. \n\n### Weakness\n\nMy concerns of the paper mainly focus on the following three aspects: \n\n1. Motivation of the “provable” part of the adversarial examples is missing. This paper relates to the prior work in generating robust adversarial examples [1, 2], where they can serve as a good motivation to generate “robust'' adversarial examples”: these papers discuss several physical distortions in applying the adversarial examples into the real-world cases for images and audio. In the other word, these distortions are real-world adversaries for artificial adversarial examples. However, the motivation for the “provable” part is missing to me. I understand the “provable” part can be related to a counter problem, probably-robust networks. The provably-robust network is motivated to build networks where the robustness can be guaranteed for all possible attacks and the evaluations are free from the choice of adversaries. To that end, can the authors explain more about the motivation for “provably”-robust adversarial examples? A follow-up question is: does the robust region proposed in this paper actually contain the physical distortions that may be encountered in the real-word cases [1, 2] and how often? It seems that the more important part we need to prove is that these regions are guaranteed to contain all or part of the distortions you can possibly encounter so that an adversary does not need to worry about that an adversarial example fails in practice. \n\n2. Important experimental setups and discussions are missing. \n- Unfortunately with some amount of time during my review I can not locate the concrete definitions and actual implementations of the intensity changes and geometric changes as mentioned in Table 1 and 2. This information should be helpful to understand the importance of the results. \n\n- How “provable” is evaluated? Table 1 and 2 seem to only evaluate how big the region is and Table 3 seems to use randomized smoothing as an attack to adversarial examples generated by the proposed approach. However, the motivation of the paper mostly relies on [1, 2], where the “robustness” of an adversarial example is actually not designed against a prediction defense, i.e. randomized smoothing, but transformations and distortions.\n\n- Unless I misunderstand the results, Table 1 and 2 seem to only aggregate over less than 100 examples per dataset and it may take up to ~5000s for one example in CIFAR. I understand that the bottleneck is that the verifier is usually resource-consuming. If that is the case, the authors may need to convince the readers under what circumstances this trade-off between resource and probably-robustness is worthwhile compared to the fast empirical approaches. \n\n3. Writing. I find the writing of the method part is well-organized and polished, which makes me enjoy the reading of the approach. However, the experiment part is relatively dense and sometimes even difficult to read when a lot of notations and symbols appear in the paragraph without sufficient explanations to remind the reader what they refer to. Also, it would be best to add explanations to notations in the captions of figures and tables so the reader does not have to search for what is measured in the table. \n\n[1] Athalye, A., Engstrom, L., Ilyas, A., & Kwok, K. (2018, July). Synthesizing robust adversarial examples. In International conference on machine learning (pp. 284-293). PMLR.\n\n[2] Qin, Y., Carlini, N., Cottrell, G., Goodfellow, I., & Raffel, C. (2019, May). Imperceptible, robust, and targeted adversarial examples for automatic speech recognition. In International conference on machine learning (pp. 5231-5240). PMLR.\n", "summary_of_the_paper": "The manuscript introduces a definition of provablely-robust adversarial examples, a set of examples that are verified to be classified as different labels compared with the input of interest. The main idea of the technique is to shrink a box-like region from an over approximation to a verifiable smaller sub-region such that a robustness verifier will return robust for all points in that particular sub-region. In the evaluation part, the author demonstrates the effectiveness of the approach with several experiments, i.e. robustness against intensity transformation and randomized smoothing defense. \n", "summary_of_the_review": "Overall I incline to a weak rejection at this stage of the reviewing process but I am open to any discussions. The reasons that prevent me from giving higher scores are the insufficient descriptions of the motivations and the current way the experiment sections are written with, which I have mentioned in my main review.", "strength_and_weaknesses": "", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "R6LtOybiofH", "reviewer": "Reviewer_XdXU", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The term \"provably robust\" appears misleading; there is no theory showing that the examples must be adversarial.\n\nWhile authors highlight that there are massive amount of adversarial examples (say $10^{573}$) produced by the algorithms, such number seems really dependent on particular problems while lacking a theoretical justification.\n\nOn the novelty of the algorithms, I feel it relies many black-box components and their properties; which lowers the technical contribution if the work.\n\n\n**Updates after discussion**\n\nI agree that the paper brings out interesting ideas and the experimental results are convincing. However, I also feel authors need to tune down the contributions on the theoretical part because many of the guarantees hinge on black-box components that are leveraged from prior works.", "summary_of_the_paper": "The main contribution of the paper is a framework that will output a large batch of adversarial examples, assuming access to a few black-box mechanisms.", "summary_of_the_review": "See above.", "strength_and_weaknesses": "", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "LZXEZbxL1WA", "reviewer": "Reviewer_A11V", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "# Strengths\n\n- **Originality**: The paper presents a novel algorithm to generating provably robust adversarial examples corresponding to semantically meaningful regions.\n- **Quality**:\n  - The paper demonstrates that the algorithm can scale to generate provably robust adversarial examples of non-trivial size on networks of non-trivial size.\n  - The experiments in the paper have clearly been carried out with an attention to detail.\n- **Clarity**:\n  - The paper describes the algorithm in sufficient detail to enable reproducibility. (In particular, the appendix explains important details that would be required to re-implement the approach.)\n- **Significance**:\n  - The approach presented is modular, using existing certification algorithms as a subroutine. This has two key benefits:\n    - Improvements to existing certification algorithms can be used to improve the search efficiency for provably robust adversarial examples\n    - Certifiers which handle new classes of transformations could be used to generate provably robust adversarial examples for these classes of transformations.\n  - While this paper focuses on adversarial examples, the approach can be used in any setting where we are interested to find large regions of input space with a constant classification (or, more generally, where a linear function of some neuron activations exceeds a threshold). I can imagine this being applied to better understanding/visualizing how the output of a neural network varies as the inputs change.\n\n# Areas for Improvement\n\n## Originality\n\n- In the introduction, the paper states that \"our regions are guaranteed to be adversarial while prior approaches are empirical and offer no such guarantees\". Section B.2. mentions Liu et al., which \"is also capable of generating provably robust hyperbox regions\". Is the statement in the introduction wrong?\n\n## Quality\n\n- The baseline used seems to be a straw man, since it is simply \"our method\" but with uniform rather than adaptive shrinking; I would always expect \"our method\" to outperform the baseline. I would prefer to see the comparison to Liu et al. (and any other methods that produce provably adversarial regions if they exist) in the main body of the paper instead.\n- In Table 2, the transforms selected appear quite arbitrary; in particular, they appear like they could have been cherry-picked to flatter the presented approach. Some detail on how the transformations were selected would alleviate this concern.\n\n## Clarity\n\n- Experimental setup for Section 5.3:\n  - I struggled to understand what experiment was run in this section and what the results in Table 3 show. I understand that the goal of this section is to show that robust adversarial examples are significantly more effective against defenses based on randomized smoothing, but the setup for the experiment is still not clear to me. I'd be happy to discuss this with the authors, but some preliminary questions:\n    - What are the units of 'robustness'?\n    - Is the result for \"Ours\" normalized to 1?\n    - Table 3:\n      - Are the results for \"baseline\" and \"ours\" mean, or some other summary statistic?\n      - What result exactly is shown for \"individual attacks\"? Were multiple attacks generated for each image, or was the individual attack the attack that was used to determine the value of $R'$?\n- Reporting # of concrete examples:\n  - In Table 1, the SizeO column reports an _upper bound_ on the number of concrete examples in the polyhedral region. This is not immediately clear from the description; a reasonable reader might expect that this is just the number of concrete examples. I would request that the authors either:\n    - Estimate the actual number of concrete examples\n    - Clearly indicate in the table description that this is an overestimate\n    - Remove the SizeO column.\n  - I have a similar concern with the \"Over\" column in Table 2; I don't see how an overestimate of the number of concrete examples in the region is relevant.\n\n# Additional Comments\n\n## Clarity\n\nHere are some issues with clarity that do not constitute major issues, but would still improve the paper significantly if addressed. At the high level, he paper appears to be trying to squeeze too many results in, leading to important details being omitted.\n\n### Missing Details\n\n- Section 5.3: \"We exclude images whose radius is too big\" - what constitutes too big? For these images, what is the robustness to $L_2$ smoothing defenses of adversarial examples generated by your method?\n- Table 1 / Table 2: Is the time reported here a median or average, and is it only for instances where the methods succeed?\n- Table 2: The value of #Splits is listed but no guidance is provided to the reader as to how to interpret the result. I would recommend moving this information to the appendix or adding an interpretation.\n- Definition 2: \"whose $L_2$ ball is certified as adversarial\" - I didn't find a definition in the paper of what it means for the $L_2$ ball to be adversarial. (I would have assumed that this means that every sample in the ball has a different classification as compared to $x$, and not that every sample has to have the same classification as $\\tilde{x}$, but the rest of the paper seems to suggest the latter definition.)\n\n### Miscellaneous Points\n\n- Section 3 (Overview): \"... assumes an algorithm $\\alpha$\" - the variable $\\alpha$ is already used above to indicate the probability that `CERTIFY` fails. I'd recommend using a different variable here.\n- Section 3.2 (Computing an Underapproximating Region): \"sacrificing a few pixels where the network is not very robust\" - did you mean where the _adversarial example_ is not very robust here? If the network is not robust for a certain pixel, it doesn't make sense to me to sacrifice _those_ pixels ...\n- Section 5.1: \"Column #Regions\" is referenced, but it is \"#Reg\" in both tables.\n\n## Spelling / Grammar\n\n- Section 2.2 (Geometric Certification): \"creates overapproximation of the region\" -> \"creates an approximation of the region\"\n- Figure 1: \"repred crosses\" -> \"red crosses\"?\n\n# Questions\n\nThis is out of the scope of this paper, but the result in Section 5.4 suggests that it might be possible to find perturbations to empirically robust adversarial examples (empirically verified by an EoT approach) that result in a correctly classified image. Do you have any sense whether it would be possible to consistently find such \"dis-adversarial attacks\" on empirically robust adversarial examples?", "summary_of_the_paper": "This paper presents a novel algorithm for identifying \"provably robust adversarial examples\": large regions in the input space that provably contain only adversarial examples.\n\nEach region corresponds to a single adversarial example $\\tilde{x}$ found in the center of the region, along with all the points that can be generated by applying a sequence of transformations to $\\tilde{x}$. The transformations considered in the paper are semantically meaningful changes to the original image. Critically, we can be guaranteed that $\\tilde{x}$ will be misclassified even if _it_ is perturbed.\n\nThe paper demonstrates that the algorithm can generate regions of non-trivial size on networks of non-trivial size. For example, for a CIFAR10 classifier with 6 layers and ~62k neurons, it finds axis-aligned regions containing a median of $10^{573}$ adversarial examples. In addition, the paper shows that provably robust adversarial examples can be used to create adversarial examples to $L_2$-smoothed classifiers that are more robust to $L_2$ noise as compared to adversarial examples generated directly via PGD attacks.", "summary_of_the_review": "Overall, I recommend accepting the paper. The paper presents a novel approach to finding large regions of adversarial examples, with strong experimental evidence that it scales well. The details provided would enable other researchers to reproduce the presented approach. Most importantly, this approach is likely to be something that other researchers can use and build upon.\n\nHaving said that, the paper has some issues with clarity. Details are provided in the main review, but I'd like to highlight in particular Section 5.3, which I found particularly hard to parse.\n\nN.B. My current recommendation for this paper as-is is 6, but I'd be quite happy to upgrade the recommendation to 8 if the bulk of my concerns around clarity are addressed.\n\n--- \n\n## After Paper Discussion Period\nDuring the paper discussion, the authors addressed the bulk of my concerns around clarity, and I've upgraded my recommendation to 8 as a result.", "strength_and_weaknesses": "", "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": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: In this paper, authors introduce and study provably robust adversarial examples. Reviewers had mixed thoughts on the work. One reviewer mentioned that the "provable" robustness is somehow overstated in the work: looking at the title and abstract, it sounds like the paper develops a new algorithm that is guaranteed to be robust, but in reality the robustness hinges on the black-box verifiers (which is acknowledged by the authors during discussion). I agree with this. This should be more clearly stated in the work. I strongly suggest authors to calibrate exaggerated statements of contributions in the revised draft. Having said this, reviewers liked the the experimental study of the paper and found it to be comprehensive and convincing.
Decision: Accept (Poster)