Efficient Certified Defenses Against Patch Attacks on Image Classifiers
Authors: Jan Hendrik Metzen
Maksym Yatsura
Venue: ICLR 2021 Poster (2021)
Keywords: robustness
certified defense
adversarial patch
aversarial examples

Abstract: Adversarial patches pose a realistic threat model for physical world attacks on autonomous systems via their perception component. Autonomous systems in safety-critical domains such as automated driving should thus contain a fail-safe fallback component that combines certifiable robustness against patches with efficient inference while maintaining high performance on clean inputs. We propose BagCert, a novel combination of model architecture and certification procedure that allows efficient certification. We derive a loss that enables end-to-end optimization of certified robustness against patches of different sizes and locations. On CIFAR10, BagCert certifies 10.000 examples in 43 seconds on a single GPU and obtains 86% clean and 60% certified accuracy against 5x5 patches.

Published as a conference paper at ICLR 2021
EFFICIENT CERTIFIED DEFENSES AGAINST PATCH AT- TACKS ON IMAGE CLASSIFIERS
Jan Hendrik Metzen & Maksym Yatsura
Bosch Center for Artificial Intelligence, Robert Bosch GmbH
1, 71272 Renningen, Germany (janhendril metzen, maksym. www.sm..ytttuuaaaaaaa.....maa @eeeuurrrredeeeeeeeeee êde. www.bbs.ch.....o........... com
ABSTRACT
Adversarial patches pose a realistic threat model for physical world attacks on autonomous systems via their perception component. Autonomous systems in safety-critical domains such as automated driving should thus contain fail-safe fallback component that combines certifiable robustness against patches with effi- cient inference while maintaining high performance on clean inputs. We propose BAGCERT, a novel combination of model architecture and certification procedure that allows efficient certification. We derive loss that enables end-to-end op- timization of certified robustness against patches different sizes and locations. On CIFAR 10, BAGCERT certifies 10,000 examples in 43 seconds single GPU and obtains 86% clean and 60% certified accuracy against x 5 patches.
INTRODUCTION
of the most relevant threat models for attacks autonomous systems such as highly automated cars or robots. In this threat model, an attacker can freely control a small subregion of the input (the "patch") but needs leave the rest of the input unchanged. This threat model is relevant because it corresponds to a physically realizable attack (Lee & Kolter [019): an attacker can print the adversarial patch pattern, place it in the physical world, and it will become part of the input of any system whose field of view overlaps with the physical patch. Moreover, once an attacker has generated a successful patch pattern, this pattern can be easily shared, will be effective against all systems using the same perception component, and an attack can be conducted without requiring access to the individual system. This makes for instance attacking entire fleet of cars of the same vendor feasible.
Adversarial patches (Brown et al. 2017)
While several empirical defenses were proposed (Hayes) 2018 Naseer et al., 2019: Selvaraju al, 2019 Wu et al. (020)), these only offer robustness against known attacks but not necessarily against more effective attacks that may be developed in the future (Chiang et al. (2020). In contrast, certified
defenses for the patch threat model (Chiang al. 2020 Levine & Feizi 2020; Zhang al.) 2020 Xiang et al.) (020) allow guaranteed robustness against all possible attacks for the given threat model. Ideally, certified defense should combine high certified robustness with efficient inference while maintaining strong performance on clean inputs. Moreover, the training objective should be based on the certification problem avoid post-hoc calibration of the model for certification.
Existing defenses do not satisfy all of these conditions: Chiang et al.] (2020) proposed an approach that extends interval-bound propagation (Gowal et 2019) the patch threat model. In this ap- proach, there is a clear connection between training objective and certification problem. However, certified accuracy is relatively low and clean performance severely affected (below 50% on CI- FAR10). Moreover, inference requires separate forward passes for all possible patch positions and thus computationally very expensive. Derandomized smoothing (Levine & Feizi 2020) achieves much higher certified and clean performance on CIFARIO and even scales to ImageNet. However, inference is computationally expensive since it is based on separately propagating many differently ablated versions of single input. Moreover, training and certification are disconnected and sepa- rate tuning of parameters of the post-hoe certification procedure on some hold-out data is required, drawback shared also by Clipped Bag Zettang/ al. (2020) and PatchGuard (Xiang al. 2020

---

Published as a conference paper at ICLR 2021
In this work, propose BAGCERT, which combines high certified accuracy (60% on CIFARIO for x 5 patches) and clean performance (86% on CIFARIO), efficient inference (43 seconds on a single GPU for the 10.000 CIFARIO test samples), and end-to-end training for robustness against patches of varying size, aspect ratio, and location. BAGCERT is based on the following contributions:
We propose three different conditions that can be checked for certifying robustness. One of these corresponds to the condition proposed by Levine & Feizi (2020). However, we show that an alternative condition improves certified accuracy of the same model typically by roughly 3 percent points while remaining broadly applicable.
We derive a loss function that directly optimizes for certified accuracy against uniform distribution of patch sizes at arbitrary positions. This loss corresponds to specific type of the well known class of margin losses.
Similarly to Levine & Feizi (2020), we classify images via majority voting over large number of predictions that are based on small local regions of single input. However, the proposed model achieves this via single forward-pass on the unmodified input, by utilizing a neural network architecture with very small receptive fields, similar to BagNets (Brendel & Bethge 2019). This enables efficient inference with surprisingly high clean accuracy and was concurrently proposed by /Zhang et al. (2020) and Xiang et al. (2020).
2 RELATED WORK
Adversarial Patch Attacks Vulnerability of image classifiers to adversarial patch attacks was first demonstrated by [Bronn et al. (2017). They show that specifically crafted physical adversarial patch is able to fool multiple ImageNet models into predicting the wrong class with high confi- dence. Numerous patch attacks were proposed for object detection (Liu et al. [209 Lee & Kolter, 2019 Thys et al. 2019; Huang et al. 2019) and optical flow estimation (Ranjan et al. 2019)). The versatility of these attacks allows them perform efficiently in the black box setup (Croce al., 2020) as well as suppressing detected objects in a scene without overlapping any of them (Lee & Kolter 2019). Following Athalyy et al. (2018b), adversarial patches can be printed out and placed in the physical world to fool different models independently from the scaling, rotation, brightness and other visual transformations. These factors make adversarial patch attacks a non-negligible threat for the safety-critical perception systems (Thys et al. 2019).
Heuristic Defenses Against Patch Attacks Several heuristic defenses against adversarial patches such as digital watermarking (Hayes) 2018) or local gradient smoothing (Naseer et al.) 2019) have been proposed. However, similarly the results obtained for the norm-bounded adversarial attacks (Athalye et al. (018a)), it was demonstrated that these defenses can be easily broken by white-box attacks which account for the pre-processing steps in the optimization procedure (Chiang et al., 2020). The role of spatial context in the object detection algorithms which makes them vulnerable to the patch attacks was investigated by Saha al. (2019) and an empirical defense based on Grad- CAM (Selvaraju et al. 2019) was proposed. Existing augmentation techniques based on adding Gaussian noise patch (Lopes et al, al, 2019) or a patch from a different image (Yun et al.)
al.] 2019) increase robustness against occlusions caused by adversarial patches. Wu et al. (2020) propose defense that uses adversarial training to increase robustness against occlusion attacks.
Certified Defenses Evaluating defense methods using their performance against empirical attacks can lead the false sense of security since stronger adversaries might be developed in the future that break the defenses (Athalye et al. 2018a Uesato et al.) 2018). Therefore, it is important to have guarantees of robustness. Numerous works were proposed in the field of certified robustness ranging from complete verifiers finding the worst-case ad adversarial examples exactly (Huang et al.) Tjeng & Tedrake, (017)) to faster but less accurate incomplete methods that provide an upper bound on the robust error (Gehr et al.] 2018 Wong & Kolter 20188) Wong et al., 2018 Gowal et al.) Another line of work is based on Randomized Smoothing (Lecuyer et al. 2019 Li et al, Cohen et al. 2019). which exhibits strong empirical results and scales to ImageNet, however at the cost of increasing inference time by orders of magnitude. Certified defenses crafted for the patch attacks were first proposed by Chiang et al. (2020). They adapt the IBP method (Gowal et al.)
2017
2019.
2019
2019) to the patch threat model. Although their approach allows to obtain robustness guarantees, it
only scales to small patches and causes significant drop in clean accuracy. Levine & Feizi (002))
2

---

Published as a conference paper at ICLR 2021
Sea Sc
X
fe
R
g
L
cc
Sc
ks=3
2R
ks=1
ks=3
-1
0
+1
Figure 1: Illustration of BAGCERT training for a ID input and two classes. An input X is processed by region scorer fa. consisting of 3-layer CNN with kernel sizes 3, 1, and 3. The resulting con- tinuous region scores are passed through a Heaviside step function (replaced by a sigmoid in the backward pass) obtain binary region scores for every class. The differences Á between and non-true class scores are then processed by spatial aggregation in this case simply summing them via g = ... The resulting value is maximized by passing into margin loss L.
proposed (dndooizde smoothing: they train a base classifier for classifying images where all but small local region is ablated. inference time, many (or even all) possible ablations are classified and majority vote determines the final classification. If this majority vote is with sufficient margin, the decision provable robust against patch attacks because a patch will be completely ablated in most of the inputs and can thus only influence minority of the votes. This method provides sigmificant accuracy improvement when compared to (Chiang et al., 2020) and allows training and certifying ImageNet models. However, its inference in block-smoothing mode is computationally expensive. A last line of work is based on using models with small receptive fields such as BagNets (Brendel & Bethge, 2019): ZZhng al. (2020) apply a clipping function while Xiang al. (2020) apply a "detect-and sirret--nd-maskk -mak"" filter to the logits of pretrained BagNets before global averaging. Using small receptive fields limits the number of region scores affected by local patches while clipping and masking ensure that few very large region scores cannot dominate the global average. We note that these approaches do not train models directly for certified robustness but rather achieve it by applying post-hoc procedures that come with additional hyperparameters that require careful tuning.
3 METHOD
We introduce BAGCERT, a framework which consists of novel conditions for certifying robustness, specific model architecture, and a new end-to-end training procedure. BAGCERT allows end-to-end training of classifiers whose robustness against adversarial patch attacks can be certified efficiently. We outline our approach for the task of image classification but note that it can be extended to other tasks with grid grid-structured inputs. We refer Figure for an illustration of the training phase and to Figure 5 in the supplementary material for an illustration of certification of BAGCERT.
Threat Model We consider threat model in which attacker can conduct an image-dependent patch attack. Let j0, 1] xh., Xcin be an input image of resolution Win x hin with Cin. channels. Let p patch and feasible regions / as L. For example, for patch p E [0, m consisting of n pixels, L could be the set of all wp x hp rectangular regions of an image x with Wp hp = n.. We define an operator A such that A(x. p, is the result of placing patch onto image over region I. We assume that the attacker has white- box knowledge of the model and conducts an input- attack, that is attack region and inserted patch p be chosen for every input independently.
a region an image x having the same size as patch p. We denote a set of
3

---

Published as a conference paper at ICLR 2021
3.1 CERTIFICATION
We base our method for certification on assuming certain structure of the classifier. More specifi- cally, we decompose the classifier into two components:
A region scorer fo that maps from inputs x to region scores 8 E {0, W Xhout X Cous, where Wout x hout the output resolution, Cout is the number of classes, and f trainable parameters. Please note that we allow Le + 1.
A spatial aggregator y that maps from region scores s (global) class scores S [0, 1]sou,, In this work, we restrict g to be monotonically increasing, that is: for class e and two patch score maps g(1) and g(2) with $2,.c $...cc Vi,j. require g(s 2 g(s(2)), Ve.
(1) (2)
Generally, we base certification on upper bounding the effect of an actual attack in the threat model. For this, we only exploit architectural properties of f and that are valid for any choice of model parameters 0. More specifically, we only exploit the output dependency map R of f. which we define as R(1) = {(i,j) 3r, 0, fo(A(a p, 1)), * fo(x)),))- Informally, R(()) is the set of all indices of the score map that can be affected by a patch applied at region 1, for any choice of input x, patch p. and parameters 0. That is: the set of all outputs of fe whose receptive fields overlap with
We discuss options for and the resulting in Section 3.2
For input a with class label et and s fo(x), we define the "worst-case" score map 8 "
if (i,j) & R()) if (i,5) E R(!) A Ac Ct
(s,
0
if (i,j) E R(I) Ac= Ct
Moreover, we define A.j.c 81.j.c Sig.e and similarly A ure that AiJ = A..j. v(t,j) & R(I) and A. (i, E R(I), c c..
".j. follows directly
For certifying robustness in the threat model for input x with class label as we need to show g(fel (A(x, p. p,))),, > ((fo(A(z, p. ())) Ve & vave Ltp. For this, suffices to check
Condition 3.1.
> (( (s, Vc & a. v
Proof. Consider arbitrary E L and p and let adv = fo(A(z, p,)).. With ande i.j.c E {0, 13 we obtair
Lijo ( =1
whe (s, 1) (1,,c(8,1)
if (i.j) R(I) if (i.j) R(I) Ac# if (1.J) E R(I) Ac=
wee
(s, =
With y being monotonically increasing, we obtain g(sado) )a > g(s and for all * Ce g(s (1)) 2 g( )e Condition 3.1 implies g(gado) )e, g(gado) )c to +
Checking the Condition 3.1 requires one forward-pass through fo to obtain s = fo (x) and [C] times the construction g " and the evaluation of g. We consider special case where this can be implemented very efficiently.
3.1.1 SPATIAL SUM AGGREGATION
For the case = 9=95(6 (s) =
Lislijl 8t,j Condition 3.1
MWalt Bous
simplifies to
Condition 3.2. min E Aisic > [R(I) V
offec (.j(((())
'We would like to note that these are "trivial" lower and upper bounds for sadv and we see the potential to improve upon these bounds in future work, for instance by relaxing E [0, 1] Khont cout and applying interval hound propagation (Gowal et al. (019). However, the proposed simple bounds have the advantage of requiring additional forward passes through the model and thus being computationally efficient.
4

---

Published as a conference paper at ICLR 2021
Proof. For all of ct, we exploit v(i,f) R(I)
A ije
-..
With Condition 3.2
obtain
Mouts
Wouts
Mouthhout
(I(s" - (0(s""(())
Σ
Σ
S Sig.c
Σ
Σ
We J.j.c
1.j (()
(.jE((()
Σ
[R(()] 0.
()GN()
Rout
We note that Σ Aij.c [= Aij.c (.)E(())
E Aija. For the special case that all R(1) (JER(I)
rectangular, DiJER()) Dijje can be computed efficiently for all I E C simultaneously via integral images/summed -area tables (Crow 1984h. For instance, R(() is rectangular for being rectangular input patches and the R resulting from an CNN with grid-aligned kernels.
For the case that the RT(() are not all rectangular and |C] becomes large, checking Condition 3.2 can become prohibitively expensive. For this case, we derive condition that corresponds to an upper bound on Condition 3.2 and can be evaluated in constant time with respect to [c]
houe
Condition 3.3. min
Σ
Aigie > 2Hmaa (C) with Rmaz (C) = max [A(())
off
TEC
Proof. Aisic S implies
Σ
Diso S [R(I) S Rmar (C). For all c * o, using Condition 3.3
(SER(U)
Wourshoou Σ
Σ Aij..c ())
Aijo
Σ Aijoc. > 2Rmaa (L) R (C) 2 I(()) (JEN((
1= 1=1,==
We note that Condition 3.3 corresponds to the condition proposed by Levine & Feizi (2020). is, however, strictly weaker condition than Condition 3.2 Thus, Condition 3.2 is preferable if all R(()) are rectangular or |C] is of moderate size. We refer to Figure in the supplementary material for an illustration of Condition and 3.3
3.2 MODEL
Crucially, the quality of the certification depends on (mma(()) maXiec [[(]]: the larger this quantity becomes, the larger the left-hand side of Condition 3.2 or Condition 3.3 needs to be to fulfill the condition. We focus on the specific case where fo is realized by a convolutional neural network (CNN). In that case, R(()) is determined fully by 1 and the receptive field of the CNN. [ A
More specifically, obtain R(I)= = {(t,j) (i, el: li -
< [2,
for a receptive field size of wry x h and ignoring operation strides.
Receptive field sizes of CNNs determined by the shapes of the convolutional kernels as well as operation strides. We propose using standard CNN architectures such as ResNets but replacing most convolutions, using stride in (nearly) all operations, and removing all dense layers. This results in a network with very small receptive field sizes and thus small R(I). We note that the proposed architecture is similar BagNets (Brendel & Bethge 2019 and using this type of model was concurrently proposed for certifying robustness against patch attacks by and Xiang al. (2020). BagNets obtain surprisingly high classification accuracy despite small receptive field sizes (Brendel & Bethge (019). Importantly, in contrast to BagNets, we do not apply global average pooling on the final feature layer. This results in a dense output of shape Wont X hout Cout- The ratios Win/Won /Wott and hin/how depend on the strides applied in the network and control mostly the computational overhead. We note that the cost for forward/backwaar passes in BagNets Because of the small receptive fields of BagNets, [R(]) is small if is a small contiguous region of the input, such rectangular patch.
3 x 3 convolutions by
Zhang al. (2020) and
in the same order of magnitude those of corresponding residual network.
5

---

Published as a conference paper at ICLR 2021
0, for r < 0
We apply a Heaviside step function H 1, for 2 0 as final layer of fo, which en-
sures (X) E {0.1) Wouu x hout Xouut Similar to clipping Zhang et al. (020) and masking (Xiang et al. 2020) this also ensures that patch cannot flip the global classification by perturbing local score so strongly that it dominates the globally aggregated score. However, since H constant nearly everywhere, it does not provide useful gradient information and thereby precludes end-to- end training. We address this by applying a straight-throughh type trick (Bengio et al. 2013) where replace H in the backward pass by its smooth approximation, the logistic sigmoid function s(x) = 1te-z- That is, we use H (x) in the forward pass but replace the true gradient of H with (x) == (xxx = s(x) - s())). We explore alternatives to the Heaviside step function in Section A.3 in the appendix.
While the proposed model computes fe(X) in single forward-pass, and controls [R(() indirectly via the architecture of f. we note that alternative models are compatible with BAGCERT. For in- stance, one could compute every element of the output ši, via separate forward pass of an arbitrary model on an ablated (Levine & Feizi| 2020) or cropped version of the input similar to Mask-DS- ResNet (Xiang et al. 2020). This also ensures that specific element of the output depends only on the cropper/non-ablated part of the input. While these works are more flexible in terms of model architecture, they require a number forward passes proportional to the resolution of the output s, which would make inference (and end-to-end) training computationally much more expensive.
3.3 END-TO-ENT TRAINING
Having derived conditions that can be used for certifying robustness against patch attacks in Section 3.1 as well as differentiable model for the region scorer f in Section 3.2 we now define loss function for end-to-end training. We restrict ourselves to the case of spatial sum aggregation gy.
We recall Condition 3.3 min E Li=l,j=1 Aijie > 2Rmaz(L) The corresponding loss for this
oéc,
can be defined as Lu (A,c, ct Rmmz)
H(min EMonn hous Aij.c I 2/maa), that is: the loss is catee
1 if there is target class c such that Elert Ai.j.c becomes smaller/equal two times the size of the maximum affected patch score region. However, this requires choosing L and the resulting R (C) before training, which is undesirable. Instead, stay agnostic with respect to the specific L and simply assume a uniform distributior for Rmme(() that is Rmaa( ~ U(0,, R). Here, R corresponds to the maximum patch size (in region score space) we consider. This results in the loss
Wouesbouu Σ
/ p( p(R)) ar R)dR
1 11 (min
(R(A,C)
Digo S 21)dd
oFc
==
R
Wout, Ponut
H (min ofes
Σ
Dusic > 2R)dR
R
i=1==1
Baue Σ
Rout
1
1 min( min
Aigoo R)) = 1- min min
Aijjes 21).
R
2
cfce
2R
1=1,==
f=1,==1
In practice, we minimize AA, - -min
houe Zi=lj=1
M) with M
2R
ofcs
Wout hout
Wout -hout
This loss can be interpreted as margin loss with margin M, where the margin corresponds to twice the maximum patch size in region score space against which we want to become certifiably robust.
One-hot penalty While we do not strictly enforce E. 81..c = 1, we sometimes found it ben- eficial add term in the loss that encourages S = 95 (s) being approximately "one-hot", that is Looh (S) maxe#ccmo Se S Seman with Ciazz arg max, S.. Since S. E [0, 1]. it holds that Los (S) E [-1, 0] and Lot (S) = -1 iff Semaz 1 and S. 0 Ve # Cmaa- The term (S)
We note that other choices than the uniform distribution would be an interesting direction for future work, in particular if the defender has prior knowledge ahout more likely patch sizes and shapes.

---

Published as a conference paper at ICLR 2021
CIFAR10 patch)
Ima geat patch
60
DS (=2))=25)
25.0
Certified Tap1. Accuracy
rt=29
(8S, thetam0.3)
Mask-BN
40
Mask-DS
CBN
ff-9
f==11
ff=13
Masik BN
10.0
Mask
5.0
75
80
95
45
50
Top1 Accuracy
Top1 Accuracy
Figure 2: Clean versus certified accuracy on CIFARIO and ImageNet for BAGCERT with different receptive fields and train margins (M E (0.25, 5, 0.75, 1.0) for CIFARIO, M = 0..5 for Ima- geNet) when certifying via Condition 3.3 (circles) and Condition 3.2 (stars), same setting connected by thin line. Smaller M generally corresponds to larger clean accuracy for CIFAR10 Baselines are Derandomized Smoothing (DS) (Levine & Feizi, 2020p, Masked BagNet (Mask-BN) and Masked DS-ResNet (Mask-DS) (Xiang et al.] (022)) and Clipped BagNet (CBN) (Zhang et al., 2020). Re- sults for these basclines are taken from the respective papers.
prevents training from prematurely converging to solution where sa,.c is approximately constant for all i.j. e, which we observed otherwise for tasks with many classes (e.g. ImageNet). The total loss becomes Liotal = Ln(A A ct) + Lot (S), where a controls the strength of this one-hot penalty.
4 EXPERIMENTS
We perform an empirical evaluation of BAGCERT on CIFARIO (Krizhevsky 2009) and ImageNet Russakkvsky al. 2015). We report clean and certified accuracy and compare to Interval Bound Propagation (IBP) Chiang et al.] 2020), Derandomized Smoothing (DS) (Levine & Feizi 2020), Clipped BagNet (CBN) (Zhang al. 2020), and PatchGGarr (Xiang et al. 2020). For DS, we focus on block-smoothing and for GutchG we focus on the masked Bag (Mask-BN) because column smoothing for DS (and the derived Mask- DS for PatchGuard) perform poorly for non-square patches that are "short-but-wide" (see Figure 4 We notice that column smoothing and Mask- perform better than column smoothing and Mask-BN against square-patches; however, there reason attacker should prefer square over non-square rectangular patches. Details the BAGCERT model architecture and training can found in Appendix A Morcover, we focus on certified accuracy, lower bound on the actual robustness of model. Results for accuracy against strong adversarial patch attack, corresponding to an upper bound on actual robustness, are discussed in Section A.2 in the appendix.
Figure shows results for different methods against 5 x 5 patches for CIFAR 10 corresponding to 2.4% of the image size and patches of 2% of the image size for ImageNet. For CIFARIO. when cer- tifying accuracy via Condition 3.3 the Pareto frontier of BAGCERT follows closely the one reported for DS with block smoothing and 0.3. This is somewhat surprising given that both model and training procedure are very different and only the condition for certifying robustness is identical. We hypothesize that both approaches have reached close to optimal Pareto frontiers when certifying robustness via Condition 3.3 However, as Table [ shows, BAGCERT requires (depending on its receptive field size) only between 39.0 and 48.5 seconds for certifying all 10.000 test examples on single Tesla V100 SXM2 GPU while DS with block smoothing requires 788 seconds. BAGCERT also clearly dominates Mask-BN BN and CBN, which utilize similar model architecture, as well as IBP (not shown) which reaches 47.8% clean and 30.3% certified accuracy. Moreover, when ap- plying Condition 3.2 for certification, certified accuracy is increased by approx. 3 percent points without changes in clean accuracy or any noticeable increase in certification time. In summary, the

---

Published as a conference paper at ICLR 2021
RF of BAGCERT
5
9
11
13
DS (BS)
DS (CS)
Certification time (seconds)
39.0
40.6
43.2
45,9
48.5
788.0
28.0
Number of parameters
28M
38M
47M
57M
66M
11M
11M
Table I: Certification time for 10.000
CIFARIO 10 test examples and number of model parameters.
Margin M=0.5
100
RF
Margin
0.5
Certified Accuracy
75
0.75
11
1.0
13
IB
50
DS (BS, s=12)
DS (BS, s-12) Mask-BN
Mask-BN
CBN
[5
(10, 10)
(15, (0,
5)
Figure 3: Certified accuracy against square patches of different sizes on CIFARIO. Shown is the performance for different receptive fields of BAGCERT (left) and train margins (right). Lines corre- spond to the same model (without retraining), evaluated against patches of different size.
strongest BAGCERT model with receptive field and margin A 0.5 can certify all 10.000 test examples in 43.2 seconds, reaching clean accuracy of 86% and certified accuracy of 60%.
On ImageNet, BAGCERT also dominates all baselines in terms of certified accuracy, reaching 18.9%
via Condition 3.3 and 22.9% via Condition 3.2 for receptive field size 17 and margin M 0.25.
Running certification for the entire validation set 50.000 images takes roughly minutes.
Figure shows accuracy of BAGCERT certified via Condition 3.2 for square patches of different sizes on CIFAR10. Again, baselines are dominated for both 2 and single configuration of BAGCERT with receptive field size 7 and margin M 0.5 performs close to optimal for all patch sizes and can certify non-trivial performance for up to 10 10 patch size. This implies that single model can be used for broad range of threat models. Figure shows a similar analysis for non-square patches of a total size 24 pixels. While BAGCERT with the same configuration as above achieves certified accuracy of 40% or performance of DS with column smoothing varies greatly with aspect ratio. In particular, "short- but-wide" patches of shape 24 or 12 2 reduce certified accuracy of column smoothing close to 0%. Since there is no reason to assume attackers will restrict themselves to square patches, we do consider DS with column smoothing or Mask-DS (Xiang al.) 2020) general patch defenses, despite good performance for square patches and efficient certification according to Table [
patches. Moreover,
for any patch aspect ratio,
CONCLUSION AND OUTLOOK
We have introduced novel framework BAGCERT that combines efficient certification with end-to- end training for certified robustness. The main contributions are a model architecture based on CNN with small receptive field, certification conditions that are applicable to broad range of mod- els, and a margin-loss based objective that is derived from the certification condition. The resulting model achieves high certified robustness against patches with broad range of sizes, aspect ratios, and locations on CIFARIO and ImageNet. Promising directions for future work are the exploration of other choices for the spatial aggregation function (such ones using the "detect-and maak"" mechanism from PatchGuard (Xiang et al.) (020)) and corresponding certification conditions and losses that can be used for end-to-end training. Moreover, the development of alternative choices
8

---

Published as a conference paper at ICLR 2021
Margin
RF-7
60
Certified Accuracy
Margin
0.25
0.5
0.75
5m4)
(24, 1) (12,
(6, (4, 6) Patch shape
12) 01. 24) 124. (12, (8.
(6, 4) 6)
(3,8)
121 (4)
Patch shape
Figure 4: Certified accuracy against non-square patches of total size 24 pixels on CIFARIO. Shown is the performance for different receptive fields of BAGCERT (left) and train margins (right) com- pared to Derandomized Smoothing with spond to the same model (without retraining), evaluated against patches of different aspect rations.
(Levine Feizi 2020). Lines corre-
for models with small receptive fields could be promising, such ones based on learnable receptive fields or based on self self-attention. Moreover, applying BAGCERT to other modalities than images would be an exciting avenue.
REFERENCES
Anish Athalye, Nicholas Carlini, and David Wagner. Obfuscated gradients give false sense of security: Circumventing defenses to adversarial examples. In Proceedings of the 35th Interna- tional Conference on Machine Learning (ICML), 2018a. URL/ mlr.
press/ ltess/v80/athhee http//////ttaaalleeeea html
Anish Athalye, Logan Engstrom, Andrew Ilyas, and Kevin Kwok. Synthesizing robust adversarial examples. In International Conference on Machine Learning (ICML), 2018b. URL http:
abs
Yoshua Bengio, Nicholas Léonard, and Aaron Courville. Estimating or Propagating Gradients Through Stochastic Neurons for Conditional Computation. arXiv e-prints, art. arXiv:1308.3432, August 2013.
Wieland Brendel and Matthias Bethge. Approximating CNNs with fag-o--sloal--eatuurss models works surprisingly well imagenet. In International Conference Learning Representations, 2019.
Tom Brown, Dandelion Mane, Aurko Roy, Martin Abadi, and Justin Gilmer, Adversarial patch. In Conference on Neural Information Processing System (NIPS), 2017. URL https://arxiv. org/pdf/1112. 09 09665. fddf arXiv: 1712.09665.
Ping-yeh Chiang, Renkun Ni, Ahmed Abdelkader, Chen Zhu, Chris Studor, and Tom Goldstein. Cer- tified defenses for adversarial patches. In International Conference on Learning Representations, 2020.
Jeremy Cohen, Elan Rosenfeld, and Zico Kolter. Certified adversarial robustness via random- ized smoothing. volume 97 of Proceedings of Machine Learning Research, pp. 1310-1322 Long Beach, California, USA, 09-11 Jun 2019. PMLR. URL Tress//97/come 9c htm
mlr.
Francesco Croce, Maksym Andriushchenko, Naman D. Singh, Nicolas Flammarion, and Matthias Hein. Sparse-rs: versatile framework for qufryeefficient sparse black-bor box adversarial attacks. CoRR, 2020. BBll/htppss//axxxvvorr///aaas 12880

---

Published as a conference paper at ICLR 2021
Franklin C. Crow. Summed-ares tables for texture mapping. In Proceedings of the 1 11th Anmual Conference on Computer Graphics and Interactive Techniques, SIGGRAPH '84, PP. 207212, New York, NY, USA. 1984. Association for Computing Machinery. ISBN 0897911385 doi: 10.1145/800031 1808600. htl.tttps://doi.rrggg 0ttpr///....11/000031103 808600)
Xavier Gastaldi. Shake-Share Shake regularization. arXiv e-prints, art.
May 2017.
Timon Gehr, Matthew Mirman, Dana Prachsler-Cohen. Petar Tsankov, Swarat Chaudhuri, and Martin T. Vechev. A12: safety and robustness certification of neural networks with abstract in- terpretation. In 2018 IEEE Symposium on Security and Privacy, (SP), 2018. URL https:
1109/1109500
0011.00058
Sven Gowal, Krishnamurthy (Di) Dvijotham, Robert Stanforth, Rudy Bunel, Chongli Qin, Jonathan Uesato, Relja Arandjelovic, Timothy Mann, and Pushmeet Kohli. Scalable verified training for provably robust image classification. The IEEE International Conference on Computer Vision (ICCV), October 2019.
Jamie Hayes. On visible adversarial perturbations & digital watermarking, In IEEE Con- ference on Computer Vision and Patten Recognition Workshops (CVPR), 2018. URL
cttpi__epppp__ 2018 wwwwwwwpswwww.... w32/
html http//ayyssooo.iillleeeeeeeeeeea
Cacpaaa____________ 2018 oappraarrraaccccaae2_._pepppe..e Bacel_ppppeeeee pater.html
Kaiming He. Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for im-
age recognition. In Computer Vision and Pattern Recognition (CVPR), 2016. URL https:
//arcii..rrg/ab///552...000
Xiaowei Huang, Marta Kwiatkowska, Sen Wang. and Min Wu. Safety verification of deep neural networks. In Computer Aided Verification 29th International Conference (CAV), 2017. URL https: .or./rrggoooo............... /0. 1007/978 3-319-3-6----9 63387-9-1
Yi Huang, Adams Wai Kin Kong, and Kwok- Yan Lam. Adversarial signboard against object detec- tor. In British Machine Vision Conference (BMVC), 2019.
Sergey loffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. Proceedings of the 32nd International Conference on Inter- national Conference on Machine Learning- Volume 37, ICML' 15, pp. 448456. JMLR.org, 2015.
Alex Krizhevsky. Learning multiple layers of features from tiny images. University of Toronto, 05 2009.
M. Lecuyer, V. Atlidakis, Geambasu, D. Hsu, and S. Jana. Certified robustness to adversarial examples with differential privacy. In 2019 IEEE Symposium on Security and Privacy (SP), pp- 656-672, 2019.
Mark Lee and J. Zico Kolter. On physical adversarial patches for object detection. Interna- tional Conference on Machine Learning (Workshop), 2019. http://///axxx ottpiis//rg//////////////o
1906. 11897
Alexander Levine and Soheil Feizi. (De)Randomized Smoothing for Certifiable Defense against Patch Attacks. arXiv e-prints, art. arXiv:2002.107:3 February 2020.
Bai Li, Changyou Chen, Wenlin Wang, and Lawrence Carin. Certified adversarial robust- ness with additive noise. Advances in Neural Information Processing Systems 32, pp. 9464-9474. Curran Associates, Inc., 2019. URL http: httt://paperrs wttppeerr.iips..cc/aaoppaaaa 1-63-certified adversarias - with leth-additiveee noise. pdf
robustness
Xin Liu, Huanrui Yang, Ziwei Liu, Linghao Song. Yiran Chen, and Hai Li. DPATCH: an adversarial patch attack on object detectors. In Workshop on Artificial Intelligence Safety 2019 co-located with the Thirty-Third AAAI Conference on Artificial Intelligence 2019 (AAAI-19), 2019. URL
http:// httt:://ceurws: wwwoor//// /Vol/Vol-oa 2200-230111 /ttVVVVll2l//pppeee.aa
Raphael Gontijo Lopes, Dong Yin, Ben Poole, Justin Gilmer, and Ekin D. Cubuk. Improving bustness without sacrificing accuracy with patch gaussian augmentation. CoRR, 2019. URL
http:://rxiv... wwtpaarwwwww...aa////aaaaaeaea/e
10

---

Published as a conference paper at ICLR 2021
1. Loshchilov and F. Hutter. Sgdr: Stochastic gradient descent with warm restarts. In International Conference on Learning Representations (ICLR) 2017 Conference Track, April 2017.
Alcksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. In International Conference Learning Representations, 2018. URL https:://///. http//aaivviv. wrw. als 1006 06083
Muzammal Nascer, Salman Khan, and Fatih Porikli. Local gradients smoothing: Defense against
localized adversarial attacks. In IEEE Winter Conference Applications of Computer Vision (WACV), 2019. httpp:://d....rg///ll wtt.oo/......////...... 11099/111111.0 2019. 00143]
Anurag Ranjan, Joel Janai, Andreas Geiger, and Michael Black. Attacking optical flow. In International Conference Computer Vision (ICCV), 2019.
Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeey Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, Alexander C. Berg, and Li Fei-Fei. ImageNet Large Scale Visual Recognition Challenge. International Journal of Computer Vision (IJV), 1 11133)221--25, 2015. doi: 10. 1007/0 1263-015-0816yy.
Aniruddha Saha, Akshayvarun Subramanya, Koninika Patil, and Hamed Pirsiavash. Adver- sarial Patches Exploiting Contextual Reasoning in Object Detection. arXiv e-prints, art. 1XXi:1910000066 Sep 2019.
Ramprasaath R. Selvaraju, Michael Cogswell, Abhishek Das, Ramakrishna Vedantam, Devi Parikh, and Dhruv Batra. Grad-CAM: Visual Explanations from Deep Networks via Gradient-Based Localization. International Journal of Computer Vision, October 2019. ISSN 1573-1405.
Simen Thys, Wiebe Van Ranst, and Toon Goedemé. Fooling automated surveillance cameras: Ad- versarial patches to attack person detection. In IEEE Conference on Computer Vision and Pattern Recognition Workshops (CVPR), 2019.
Vincent Tjeng and Russ Tedrake. Verifying neural networks with mixed integer programming. CoRR, 2017. URL BRtp:::::/axxx wttpa/lv.rggaa/////.//oa 07356
Jonathan Uesato, Brendan O' Donogguue Pushmeet Kohli, and Aäron van den Oord. Adversarial risk and the dangers of evaluating against weak attacks. In Proceedings of the 35th International Con- ference on Machine Learning (ICML), 2018. URL http:///proceeannss mllr. press/ .a..mmll
Eric Wong and J. Zico Kolter. Provable defenses against adversarial examples via the convex outer adversarial polytope. In Jennifer G. Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference on Muchine Learning (ICML), 2018.
mlr. wtw.pres//vll //tr/s///////ngg/// Sa html
Eric Wong, Frank Schmidt, Jan Hendrik Metzen, and J. Zico Kolter. Scaling provable adversarial defenses. In Advances in Neural Information Processing Systems 31: Annual Conference Neurul Information Processing Systems 2018 (NeurIPS), 2018. http:ttt/p::::srs..... nips.
Tong Wu, Liang Tong, and Yevgeniy Vorobeychik. Defending against physically realizable attacks on image classification. In International Conference on Learning Representations (ICLR), 2020.
URL httptttss///xxi..coom org/ abs./909/..0 09552]
Chong Xiang, Arjun Nitin Bhagoji, Vikash Schwag, and Prateek Mittal. PatchGuard: Provable Defense against Adversarial Patches Using Masks on Small Receptive Fields. arXiv e-prints, art. arXiv:2005. 10884, May 2020.
Sangdoo Yun, Dongyoon Han, Scong Joon Oh, Sanghyuk Chun, Junsuk Choe. and Youngjoon Yoo. Cutmix: Regularization strategy to train strong classifiers with localizable features. The IEEE International Conference Computer Vision (ICCV), October 2019.
Zhanyuan Zhang, Benson Yuan, Michael McCoyd, and David Wagner. Clipped BagNet: Defend- ing Against Sticker Attacks with Clipped Bag-of feattures.. In 3rd Deep Learning and Security Workshop (DLS), 2020.
11

---

Published as a conference paper at ICLR 2021
A APPENDIX
A.1 EXPERIMENTAL DETAILS
A.1.1 CIFAR10
We use the following class of models for CIFARIO: we use ResNet (He et al.) 2016) base architec- ture, consisting of single 3x3 convolution stem, followed by 8 residual blocks. We use stride one all operations (that is: output resolution 32 32) and use constant width of 768 throughout convolution with 10 outputs. All layers use batch
the network. The last layer consists of a normalization (loffe & Szegedy 2015) and ReLU, Blocks get assigned either a kernel size of I or 3, depending on the desired receptive field of the network. The following table summarizes the kernel-sizes of different blocks used in the experiments:
RF of BAGCERT
stem
b1
b3
b4
b5
b6
b7
b8
5
3
3
7
3
3
1
1
1
9
3
3
11
3
3
3
1
13
3
3
3
3
1
Residual blocks shake-shake regularization (Gastaldi) (017) in the batch-wise mode. For resid- ual blocks with kernel size 3, special form of shake-shake regularization is used: the first residual 3 convolution followed by 1 convolution, while the second residual path applies first a x 1 convolution followed by a 3 x 3 convolution. This increases diversity of paths without changing the total receptive field of the network. Besides that, no additional regularization is applied, that is weight decay is 0.0, and the one-hot penalty is set to
path applies
0.0.
For training, we the Adam optimizer with learning rate 0.001, batch size 96, and train for 350 epochs. We apply cosine decay learning rate schedule (Loshchilov & Hutter (2017) with warmup of epochs. Moreover, we apply random horizontal flips and random crops with padding 4 for data augmentation.
A.1.2 IMAGENET
We work on 224 x 224 inputs, which are extracted by rescaling the shorter side of the image to 256 pixels and extracting random crop (training phase) center crop (test phase) of size 224 224. Note that this input resolution differs from the 299 x 299 resolution used by Derandomized Smooth- ing Levine& Feizi (2020). In order achieve comparable results, we evaluate against patches of size 32x32xx3 32 (32" (322/224 2244- se 2.04%) while DS test against patches of size 42 x 42 (42 /2992 x 1.97%).
We the following class of models for ImageNet: We use a ResNet base architecture, consisting of a single 3x3 convolution stem, followed by 8 residual blocks. We use stride 2 in blocks 1 and 3 and stride otherwise (that is: output resolution 56 56). We use width in the stem and the first two blocks, width 128 in blocks 3 and 4, width 256 in blocks 5 and 6, and width 512 in convolution with 1000 outputs. All layers use
blocks and The last layer consists of batch normalization and ReLU. Blocks get assigned either kernel size of 1 or 3, depending on the desired receptive field of the network. The following table summarizes the kernel-sizes of different blocks used in the experiments:
RF of BAGCERT
stem
bl
b2
b3
b4
b5
b6
b7
b8
17
3
3
1
3
1
1
25
3
3
1
29
3
3
3
1
3
1
We apply neither shake-shake regularization nor weight decay. However, we set the one-hot penalty the Adam optimizer with learning rate 0.00033, batch size 64, and
to = 1.0. For training, train for 60 epochs. We apply a cosine decay learning rate schedule with a warmup of 10 epochs. Moreover, apply random horizontal flips for data augmentation.
12

---

Published as a conference paper at ICLR 2021
Condition 3.3
Sc
X
fe
E
R
g
4
< Rmar (C) =
Sc Sc
ks=1
ks=3
-1
0
+1
Condition 3.2
Scc
8c
lec WC
X
fo
R
A
g
WC
Scz Sg
0
ks=3
ks=3
Figure 5: Illustration of BAGCERT certification for ID input and classes. We assume for this example that L. consists only of single element; that is: the attacker can only place a patch at location (0). shown by the checkerboard pattern in the input. The resulting R(l)) consists the three top elements in region score space (shown again by checkerboard pattern). Accordingly, Rmaa (L) 3. (Top) Certification via Condition 3.3 The regular network output +4 is compared to M (C) +6. Since 4 < 6, the robustness of the prediction cannot be certified. (Bottom) Certification via Condition 3.2; region scores are replaced by g"e based on R(l). The resulting network output is +1, which is greater than O. Thus, robustness of prediction be certified.
13

---

Published as a conference paper at ICLR 2021
Region (True class)
Region (Target class)
Clean image
Region Scores (True class)
Region Scores (Target class)
Adversarial image
Figure 6: Illustration of an adversarial patch attack and its effect on region scores. Top row corre- sponds the clean image (left), the resulting score maps for the true class (middle), and the score maps for the chosen target class (right). The bottom row shows the same for the image with an adversarial 5 x patch inserted the chosen region The red rectangle corresponds R(I).
A.2 ROBUSTNESS AGAINST HEURISTIC PATCH ATTACK
While the certification conditions proposed in Section 3.1 allow computing a lower bound of model's robustness against a specific type of patch attack, model's true robustness against such attacks can be anywhere between this lower bound and the clean accuracy. In order to determine a tighter upper bound on robustness than clean accuracy. we perform heuristic adversarial patch attack on the model and evaluate the model's accuracy on inputs that were modified by the attacker. Our threat model from Section 3 allows
attacker to place an arbitrary patch E [0. 1 1|mxx at and
an arbitrary region 1 E We employ the following approach: we first select a region 1" target class c* and (once selected) keep this region and target class fixed and optimize the patch p accordingly. Please note that no guarantee exists that actually the best region for an attack or the best patch are determined; thus, the resulting adversarial accuracy is only an upper bound.
Specifically, we focus in this evaluation on consists of all possible 5 5 subregions of 32 x 32 input. Ideally, one would perform independent attacks at all possible regions E L. However, this becomes quickly computationally intractable. We exploit specific design choices of BAGCERT particularly problematic for model on an input assuming a spatial sum aggregation is applied. For this, we make directly use of Condition 3.2 and choose it, arg minu Lije Dij This choice corresponds assuming a maximally effective patch attack that is able achieve A.,j. -1 j) R(I) A practical patch attack might not be able to achieve this ideal outcome (see also Figure ( and thus 1", c* are not necessarily optimal. However, they are reasonable choices that can be determined efficiently.
square patches on CIFAR-10. Accordingly, C
select region and target class that may be
Once 1" and are fixed, we perform a PGD attack (Madry al. 2018 with 100 steps, step size of 0.025, and the objective of maximizing the loss LR from Section 3.3 with margin M 1. An illustration of such an attack is shown in Figure
Figure 7 shows scatter plots of clean versus adversarial accuracy (left) and certified versus adversar- ial accuracy (right) for the BAGCERT models also shown in Figure Interestingly, while clean and adversarial accuracy are highly correlated, the same does not hold true for certified and adversar- ial accuracy. In particular, adversarial accuracy seems to favor slightly larger receptive fields than certified accuracy. A potential reason for this can be seen in Figure 6 while a patch attack is typi- cally effective for flipping the score of true and target class for the inner part of R(!), it seems lot harder to flip also scores close to the boundary of R(I). For larger receptive fields of the model, this boundary effect seems to be amplified since the patch is smaller relative the receptive field size.
14

---

Published as a conference paper at ICLR 2021
RF
5
75
Adversarial Accuracy
70
75
85
90
95 30
50
60
Clean Accuracy
Certfied Accuracy
Figure 7: Scatter plots of clean versus adversarial accuracy (left) and certified versus adversarial accuracy (right). Color encodes different receptive filed sizes.
80
Certified Tap1 Accuracy
Top1 Accurary
60
Heaviside step
sigmaid
40
softmax
20
40
60
20
40
60
Epachs
Epochs
Comparison of Heaviside step function with alternative choices such as element-wise sigmoid or channel-wise softmax for five independent runs with different random seeds.
Figure 8:
We consider reducing this gap between certified and adversarial accuracy further (that is: making bounds tighter) important future work. This will require both developing more effective attacks as well as improving certification procedures.
A.3 EXPLORING ALTERNATIVES TO THE HEAVISIDE STEP FUNCTION
In this section, we explore alternative to the Heaviside step function as the last layer in the region scorer fo (see Section 3.2h. For this, relax region scores be arbitrary values between 0 and 1, that is we have Jo(x) E [0, 1o x xhout Cout, More specifically, we explore the element- wise sigmoid function si(Fi.j.c) 14e and the channel-wise softmax function sm(F.j.))
Exe F. Note that for the channel-wise softmax, E. St.ie 1, while this not enforced by
Piile
element-wise sigmoid and Hcaviside step function.
Figure g shows clean and certified accuracy (via Condition 3.2) on validation data during model training for five independent runs with the same configuration but different random seeds. The Heaviside step function ensure stable convergence to high clean and certified accuracy in all five runs (please note that performance is slightly lower than in Figure because training was stopped after 75 epochs). The channel-wise softmax also shows consistent convergence, albeit to a lower level of performance. We attribute this to the hard constraint Σ. 8i.j. 1 for region scores,
15

---

Published as a conference paper at ICLR 2021
which is too restrictive for small and ambiguous regions. For the sigmoid function, nearly the performance of the Heaviside step function while four other runs become unstable early during training and converge to chance level. Further hyperparameter tuning might be able to fix the convergence of models with the sigmoid function. However, we stick to the Heaviside step function since it provides stable performance without requiring further manual tuning.
reaches
16


Reviews:
[{"review_id": "wCjfEX7E1Kv", "reviewer": "AnonReviewer1", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper presents a provable defense method called BAGCERT against patch attacks which uses an invariant of BagNet for certification. By using the network with small receptive fields, this paper first analyzes the worst-case classification. The basic certification process is created by using a novel aggregation function. Finally, after using the same certification conditions as the Derandomized smoothing (Levine & Feizi, 2020), the certification could be evaluated within constant time. To further reduce the impact of the adversarial patch, the proposed method uses the certification condition as the objective loss to train the network. Empirical studies show the superiority of BAGCERT over other approaches.\n\nAdvantages: \n1.The paper gives good formal descriptions and rigorous proofs. \n2.The certification section is well structured. The narrative is logically layered and well-organized. \n3. The paper gives a SOTA certified accuracy with high clean accuracy on ImageNet. \n\nConcerns: \n1. Overall, the paper uses essentially the same certification conditions as the Derandomized smoothing except that it replaces the network architecture with BagNet. In addition, the table that describes certification time shows that number of parameters of the proposed method is much larger than Derandomized smoothing. Is it fair to compare accuracy under networks with varying numbers of parameters that differ too much (38M:11M)?\n2. Could you provide the training cost compared with Derandomized smoothing? In theory, the method is faster. \n3. The description of R(l) in 3.1 is so unclear that it is difficult to understand the meaning of R(l).\n4. The supplementary material should give some experimental results of the application of the proposed method to practical examples, for example, can you provide some results that uses some existing patch attack methods for evaluation?\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "MwVKmHxYUdW", "reviewer": "AnonReviewer5", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\nThis paper deals with obtaining verified bounds on the accuracy of a model under attack restricted to patch modification (only a small, localized group of pixels can be modified). As opposed to previous methods (Chiang et al, 2020) which simply applied existing verification methods to the problem by enumerating possible patch locations, the proposed approach consist in modifying the structure of the network such that predictions are made densely and then aggregated. The dense prediction means that only some of the predictions can be affected by the adversarial patch, and so the certification process can use this to reason about the robustness at the aggregation level.\nFor network with small receptive fields, this will be particularly efficient (few predictions can be affected) so the authors propose to use CNN with small filter convolution in order to make the network more verifiable. Incorporating the verification procedure into the training objective is also described.\n\nThe proposed method achieves comparable or better results in terms of verified accuracy and nominal accuracy, while being significantly faster.\n\nComments:\n- Figure 1 is quite helpful for understanding the principle of the proposed architecture.\n- Why is it necessary to have the heaviside step function in the forward pass? Why wouldn't using the sigmoid function in the forward pass work? That way, the gradient used would actually corresponds to the objective.\n- All the reasoning for robustness is here done at the aggregation phase, essentially enforcing that even flipping completely a prediction for a localized region does not change the global prediction. Could this be combined with the method of Chiang et al. to show that some regions can't be changed by more than a certain amount? This might allow the certification method to deal with networks with larger receptive fields?\n\nOpinion:\nThe paper provides a simple, interesting approach, and describes it clearly. The empirical performance is also validated on both CIFAR and ImageNet.", "extra_scores": {}, "extra_text": {}}, {"review_id": "Ev-AhjOKGA4", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper investigates provable defenses to visible adversarial perturbations. Specifically the authors concentrate on defending against adversarial patches as introduced by Brown et al. [1] and not on other formulations of visible adversarial noise such as LaVAN (Karmon et al. [2]). The provable defense builds upon work by Xiang et al. [3], who utilise robust aggregation and BagNets to show the model can always recover correct predictions on certified images against any adversarial patch. The idea behind the defense is to constrain the receptive field size in convolutional layers; given a small adversarial patch and a large receptive field, the adversarial patch will be present in most extracted features, and so is more likely to change the model’s prediction. By limiting the size of the receptive field, the adversarial patch can only infect a small number of extracted features, after which the extracted features are binarized and robustly aggregated. The authors also introduce a new margin-based loss that encourages the model to be certifiable. Experiments with small adversarial patches on CIFAR-10 and ImageNet point to the efficacy of the approach. BagCert appears to outperform related certifiable approaches to patch attacks. The main boon of this approach lies in the fast certification time, since a constant number of forward-passes are required. The authors additionally have experiments showing the equivalence in robust accuracy against different shaped patches covering the same overall area size. Overall, I thought the paper was well-written, easy to follow and contains some interesting ideas. However, it is difficult to assess the level of technical contribution made here, since the core contributions in this work are also contained in Xiang et al [3].\n\nAs alluded to above, my main concern is the level of technical contribution made in this work. As far as I understand, this work is grounded in the ideas presented by Xiang et al [3] who use small receptive fields as a building block for robust classification. The main differences lie in the method of robust aggregation and that, here, the authors introduce a regularisation loss that encourages the model to be certifiable. As far as I could tell, a similar loss could have been introduced using the Xiang et al. approach and it is not specific to using the heaviside method of discretisation. It would be helpful if the authors please delineate the differences and contributions between this work and Xiang et al.? It is slightly disingenuous to say these works are concurrent contributions as stated in the contributions sections, since this work has been submitted ~4-5 months after Xiang et al. [3] was made publicly available.\n\nCould this defense be applied to attacks that contain multiple, small localised patches (c.f. Karmon et al. [2])? I think the answer is probably yes, but it would be great to see an analysis in this direction.\n\nThe condition of a small receptive field implies an inherent trade-off between clean and robust accuracy. How should one tune the receptive field size to minimise this trade-off? This defense in its current formulation seems to be quite specific to image classification. Could this be extended to other modalities of data that use architectures that often extract global (instead of local) structure within data inputs (e.g. Transformers and NLP tasks)?\n\nIn the experiments, are the results compared against vanilla implementations of related approaches, or against approaches with relevant hyperparameters tuned? For example, when comparing with Xiang et al. [3], did you perform a sweep over receptive field sizes that minimise the clean-robust accuracy trade-off, or a sweep over the detection threshold, T? \n\nAs far as I understand, in Levine et al. [4], band smoothing can certify both column and row based patches (as opposed to square patches). In Figure 4, did the authors try to compare against row-based smoothing techniques (in addition to column smoothing)? I expect that this may solve the problem of zero certified accuracy on row patches. I encourage the authors to check this as it seems the Levine et al. [4] approach is outperforming BagCert for non-square adversarial patches.\n\n\n[1] Brown, Tom B., et al. \"Adversarial patch.\" arXiv preprint arXiv:1712.09665 (2017).\n\n[2] Karmon, D., Zoran, D., and Goldberg, Y. Lavan: Localized and visible adversarial noise. arXiv preprint arXiv:1801.02608, 2018.\n\n[3] Xiang, Chong, et al. \"PatchGuard: Provable Defense against Adversarial Patches Using Masks on Small Receptive Fields.\" arXiv preprint arXiv:2005.10884 (2020).\n\n[4] Levine, Alexander, and Soheil Feizi. \"(De) Randomized Smoothing for Certifiable Defense against Patch Attacks.\" arXiv preprint arXiv:2002.10733 (2020).\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "4P_QTkuPr00", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper considers a problem of the defense against adversarial patch insertion attacks for image classification. Namely, it considers rectangular adversarial patches of fixed sizes and aspect ratios inserted in arbitrary locations of input images and requires from the desired model to obtain good classification performance on both clean and corrupted versions of datasets. Moreover, it is desired for results on the corrupted data to have certified robustness (theoretically guarantied classification performance given the model and the parameters of the attack).\n\nTo deal with this problem, this work uses a combination of ideas. Following prior work, it proposes to use CNN architectures with small receptive fields that compute class predictions for every spatial region in output feature maps, and to aggregate these predictions in a voting manner to obtain final class probabilities. The authors formally address the problem of certification and derive a novel stronger certification condition (compared to prior work), which allows to guarantee better performance for the proposed models. Moreover, the authors propose a novel training objective which is based on the certification condition, which allows for an end-to-end optimization of the model directly for the certified performance, in contrast to performing post-hoc adjustments to achieve certified robustness with pretrained models. \n\nIn practice, the proposed approach achieves superior certified performance on CIFAR10 and ImageNet datasets, while maintaining high clean accuracy. Additionally the certification process is reported to be about an order of magnitude faster compared to prior work. The approach is also shown to be more robust to rectangular adversarial patches.\n\nPros:\n1) The paper is well-written and is pleasant to follow.\n2) The proposed certification condition and training objective are novel and, as far as I can tell, are technically sound.\n3) Formal analysis incorporates and properly relates the certification condition from prior work.\n4) Experimental results are convincing and additionally include efficiency comparison.\n\nCons:\n1) Might be not a con, but for me it is not clear which protocol is used for evaluations in experiments with varying patch sizes. Do I understand correctly that each point in figures 3 and 4 was obtained by retraining models from scratch with the chosen patch configuration? If that is the case, you can not imply that a single model is robust for different kinds of attacks, in that case it is the configuration of the model which is robust, but you will still need unique model parameters for any specific patch configuration.\n\nQuestion:\n1) Is it possible to apply the developed certification condition to prior work? It seems that prediction by region voting is the only requirement for applicability. If so, have you tried to use it on any prior works?\n2) When you derive the objective from the certification condition 3.3 you assume that the size of the maximum affected patch score region is uniformly distributed. As far as I understand, this makes the objective robust to variations in patch sizes and geometry. In practice though, it is harder to certify robustness for larger stretched patches (Figures 3, 4). Does it make sense to consider distributions for $R^{max}(\\mathcal{L})$ with densities shifted towards larger values?\n\nOverall, I believe this is a strong paper, containing both theoretical and practical novel contributions and I think it should be accepted.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper develops a novel provable defense against patch-based adversasrial attacks on image classification system, by combining a novel architecture and certification procedure. The theoretical and experimental contributions are convincing and clearly advance the state of the art in provable defenses against adversarial perturbations.

The questions raised by the reviewers were addressed convincingly by the authors during the rebuttal phase, leading to unanimous consensus amongst reviewers towards acceptance. I recommend acceptance.
Decision: Accept (Poster)