ScaleCert: Scalable Certified Defense against Adversarial Patches with Sparse Superficial Layers
Authors: Husheng Han
Kaidi Xu
Xing Hu
Xiaobing Chen
Ling Liang
Zidong Du
Qi Guo
Yanzhi Wang
Yunji Chen
Venue: NeurIPS 2021 Poster (2021)
Keywords: Certified Defense
DNN Security
DNN Robustness

Abstract:     Adversarial patch attacks that craft the pixels in a confined region of the input images show their powerful attack effectiveness in physical environments even with noises or deformations. Existing certified defenses towards adversarial patch attacks work well on small images like MNIST and CIFAR-10 datasets, but achieve very poor certified accuracy on higher-resolution images like ImageNet. It is urgent to design both robust and effective defenses against such a practical and harmful attack in industry-level larger images. In this work, we propose the certified defense methodology that achieves high provable robustness for high-resolution images and largely improves the practicality for real adoption of the certified defense. The basic insight of our work is that the adversarial patch intends to leverage localized superficial important neurons (SIN) to manipulate the prediction results. Hence, we leverage the SIN-based DNN compression techniques to significantly improve the certified accuracy, by reducing the adversarial region searching overhead and filtering the prediction noises. Our experimental results show that the certified accuracy is increased from 36.3%  (the state-of-the-art certified detection)  to 60.4%on the ImageNet dataset, largely pushing the certified defenses for practical use.   

ScaleCert Scalable Certified Defense against
Adversarial Patches with Sparse Superficial Layers
Husheng 123+ Kaidi Xu+
Xing Hult
Xiaobing Chen 12, Ling Liang*
Zidong Du Qi Guo' Yanzhi Wang Yunji Chen
SKIL of Computer Architecture, Institute of Computing Technology, CAS University Chinese Academy of Sciences CCambricon Technologies
*Drexel University 'UC Santa Barbara Northeastern University (hanhusheng202, huxing, www.uhggcceeiiaoooiiooooo chenxiaobing duzidong guoqi, cyj]sicct...... ac. kx46@drexel. yanz. wwng@nnorthesstem. edu liangling@es uuss. edu
Abstract
Adversarial patch attacks that craft the pixels in confined region of the input images show their powerful attack effectiveness in physical environments even with noises deformations. Existing certified defenses towards adversarial patch attacks work well on small images like MNIST and CIFAR- 10 datasets, but achieve very poor certified accuracy on higher-resolution images like ImageNet. It is urgent to design both robust and effective defenses against such practical and harmful attack industry-level larger images. In this work, we propose the certified defense methodology that achieves high provable robustness for high-resolution images and largely improves the practicality for real adoption of the certified defense. The basic insight of our work is that the adversaria patch intends to leverage localized superficial important neurons (SIN) to manipulate the prediction results. Hence, we leverage the SIN-based DNN compression techniques significantly improve the certified accuracy, by reducing the adversarial region searching overhead and filtering the prediction noises. Our experimental results show that the certified accuracy is increased from 36.3% (the satte-of-the-are certified detection) to 60.4% the ImageNet dataset, largely pushing the certified defenses for practical use.
Introduction
Despite the promising opportunities and great success of deep neural network (DNN) techniques in computer vision tasks [9, 13], DNN techniques vulnerable to adversarial attacks that craft the input data with adversarial perturbations to manipulate the output [2, 20, 26). Recent studies reach a consensus that compared to the adversarial example attack, adversarial patch attack is more practical and well-demmnstrrted in physical environment with good effectiveness and transferability in both classification and detection systems [5, 14, 15, 23, 25, 28). The key difference between the adversarial example attack and patch attack is the constraint of perturbation. For adversarial example attack, the adversary perturbs all pixels the image with the fp-norm of the perturbation in prescribed bounds, while the adversarial patch attack only changes the pixels in a confined region without bounded constraints but free to choose the values. Consider the real-world condition, it's hard to define the -orm constraint of the perturbation due to the environment, viewpoint and object variation. Hence, the adversarial patch attack is much more appropriate to be mounted in the physical world. The success of practical adversarial patch attacks raises the importance and urgency of defense methodologies. Existing defending methodologies can be classified into two categories, heuristic defenses and certified defenses. For heuristic defense approaches, they have good efficiency
Equal contribution. f Corresponding author.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).

---

but lack robustness against a strong adaptive attack. For example, digital watermarking (DW) [8] utilizes the magnitude of the saliency maps to detect unusually dense regions and mask them out of the input. Local gradient smoothing (LGS) [19] pre-processes the image gradient of the classification function with a normalization and a thresholding step and then suppress the adversarial noise based on the gradient. However, these empirical defenses may be invalidated when confront with the strong adaptive attacker that has the white-box knowledge of the defense [3]. For certified defenses, they must be proved that have provable robustness, like [3] proposes the first certified defense based on the interval bound propagation (IBP) [7] that are commonly used in adversarial robustness certification problems. De-randomized smoothing (DS) [15] proposes the defense method extending randomized smoothing robustness schemes [4] with structured ablation. Moreover, a provable robustness defense based clipped BagNet [1] with small reception field is proposed by [33]. However, all of these certified studies achieve distinctly low certified accuracy for large scale datasets such as ImageNet [13]. A certified accuracy of 20.5%-36.3%%
from these methods can hardly be applied in the real world systems. It is a dilemma that certified robustness against such a practical and pernicious attack model can be hardly scaled for realistic usage.
To address this issue, in this paper, we propose the defenses with both certified robustness and good scalability for large scale dataset that used in practical scenarios. Inspired by the existing analysis on the unique distribution of the activation map yielded by adversarial patch attacked input [16, 19, 25], and substantial neural network compression techniques without sacrificing natural accuracy [10, 31], we observe that the adversarial patches rely on the localized superficial important neurons (SINs) to poison the output and can be exceedingly alleviated by utilizing the pruning techniques. We then propose the scalable certified (ScaleCert) defense with SIN-hased neural network sparsity approach. The results show that the certified accuracy of ScaleCert on ImageNet dataset achieves 60.4% against 1 Vo-ppxell patch, significantly surpassing the highest record of 36.3% in state-of-the-aa certified detection methods [24]. This is the first certified work that largely reduces the gap between clean and certified accuracy, retaining the high certified accuracy with good computing efficiency, which largely pushes the certified defenses for common practice in real adoption.
2 Problem Setup
In this section, we describe the formulation and important terminology of adversarial patch attack and certified defenses against it.
2.1 Adversarial Patch Attack Formulation
Given an input x E X' C [0, 1] Hx3 with a true label y², adversarial patch attack can manipulate the output label of victim model, M(-). by adding the patch perturbation on x. The goal of adversarial patch attack is to find an adversarial patch x that can be added on x to generate image x' e A(x) satisfying a constraint A such that M(x')= = y' F y² y can be a targeted label (targeted attack) or any arbitrary label not equal to the benign label y" (untargeted attack). The adversarial patch & can be generated by solving the follow equation:
x arg max Ex|logPr(M(x') =// x'EA(x)
(1)
The constrain A(x) is determined by the threat model. In this paper, the adversary is allowed to arbitrarily change pixels within a square contiguous region and locate this region anywhere on the image, which is similar to the previous works [15, 18, 25]. Formally, we use a binary pixel block p E (0, 1)Wx x to represent the restricted square region, where the pixels located the region are set to one, otherwise zero. For the purpose of stealthiness, p is extremely smaller than x, usually has the size of 1% to 5% of the x. The constraint set A(x) can be expressed as:
A(x) E (x' (1 p) x
(2)
where O refers to the element-wise product operator, and x is the adversarial patch we generated from Eq. (3).
'Coeriigg both certified recovery and detection methodologies. See Table 2 for more details.

---

2.2 Certified Defenses
Bounding the range a neural network outputs given a f--norm of input perturbation has become an
important theme for neural network verification and certified adversarial defense [4, 7, 21, 22, 27, 32]. Recently, researchers also shed light on generalizing the conventional input perturbation constraint to the adversarial patch formulation. Existing certified defenses against adversarial patch attacks can be classified into two major categories with different certification problems:
1) Certified defense for attack recovery. The classifier returns the assurance that the classification result will provably not change under any distortion within an adversarial constraint set for the input. It is a heritage from certified defenses towards adversarial example attacks. Formally, the classifier ensures M(xx) = M(x') Yo to produce certificate for an clean input X. for any adversarial example x' E A(x)), where A(x)) is the adversarial constraint set defined in Eq.( 2). Many existing studies extend the certified techniques in adversarial example attacks with the new constraints of patch perturbation to propose the certified defense against patch attacks. For example, [3] proposes their certified defense by extending interval bound propagation (IBP) [7] defense on patch attacks. [15] proposes the derandomized smoothing methodology based on structured ablation scheme by extending the randomized smoothing technique [4]. PatchGuard [25] leverages the DNN models with small reception fields to localize the adversarial features and proposes the robust masking defense to remove adversarial effect of these features.
2) Certified defense for attack detection. The classifier returns the assurance that the image is clean or alert when the image is an adversarial input. It relaxed certified problem compared to certified recovery. However, it is also an important and effective defense because occluding the adversarial patches can eliminate the adversarial effect. MRD [18] the first work that proposes the certified attack detection study. By examining the pattern of the prediction labels that occlude the windows of the images, the adversarial images can be certified detected. PatchGuard++ [24] aims to improve the certified detection rate by extending PatchGuard with the same insights of MRD.
For both certified recovery and detection defenses, the state-of-the-art approaches obtain low certified accuracy on large scale datasets and can be hardly adopted for practical use. As shown in Table 1, the best certified accuracy in recent literature is about 36.3% when the patch contains 1% pixels of the input image. Therefore, we confront with the dilemma of practicality and low certified provable robustness for the harmful and practical adversarial patch attacks. To address this issue, we aim to propose a defense methodology that bridges the gap between clean and certified accuracy and achieves both provable robustness and good scalability for large scale datasets.
Table Certified accuracy of state-of-the-an defenses on ImageNet.
Certified Defense
Certified Detection
Certified Recovery
(ImageNet, PatchSize=19)
PatchGuard++ [24]
PG-Mask- (G-Maak-BNN(55]
PG-Mask-DS [25)
CBN [1] DS [15]
Certified Accuracy
36.30%
32.30%
22.50%
21.90%
20.50%
3 ScaleCert Defense
In this section, we first use an empirical study to motivate the use of superficial important neurons (SIN) distribution to distinguish the adversarial patch and climinate the adversarial effect and noises. Then we propose the ScaleCert to defend against adversarial patch attack with SIN-based sparsification methodology. To note, Section 3.1 focuses empirical analysis based on the results of some specific adversarial patch attack methodology. However, the ScaleCert's robustness applies to any arbitrary adversarial patch attack. The provable robustness of this defense is demonstrated and analyzed in Section 3.3.
3.1 SIN in Patched and Benign Images
In observing that the adversarial patch determines the prediction results with a very small region of pixels for relatively broad range of input images, we thus perform superficial feature importance distribution analysis of patched images and benign images. Though neuron importance analysis has been widely used for abnormal input detection [6, 16, 29, 30], the metric in our methodology (superficial feature importance) is distinct from previous studies (deep feature importance). The latter focuses on the neurons that contribute significantly to the inference output, while superficial important
3

---

Berrign
Benign I-S Masted
.Attack Succ Rate
=Adv Dotection Rate
Patched
-0.02
Patched ISN Masked
0.
1.2
0.998
0.856
0.887
0.765
0.806
0.621
15
20
25
(b)
0.6
0.%%
0
Prndiction
0.4
2,8%
18.98
23.1%
1.0%
0.079
22.7%
SINS of benignjefti and patched imageinight) (a)
3.0%
0,001
0001
Benign Images
Patched Images
ImageKet
Regularization parameder
(c)
(d)
(9)
Figure 1: SIN analysis in benign and patched images.(a) A showcase of SINs in the benign and patched image. (b) The distance deviation of the SIN. (c) The average important neuron cluster
number distribution. (d) The prediction stability of moving out localized SINs in benign and patched images. (e) Adaptive attack effectiveness by steering around the detection of SINs
neurons refers to the neurons that contribute significantly to the shallow feature map values in the first (several) layer(s). Compared to deep important neurons (DIN), SIN has good discrimination to distinguish patched images, more straightforward correlation with the input adversarial regions, and smaller computing overhead without requirement for gradient calculation. More comparison between SIN and DIN Appendix A.3.
Specifically, we discover that the SIN of patched images exhibits extremely localized pattern and the adversarial patch effects can be eliminated if localized SINs are removed. For benign images, however, the prediction results do not rely on the localized SINs and thus being more stable. The infuition is that the prediction of typical DNN inference on the benign inputs depends on the deep features of the input image, while adversarial inputs have to strengthen the superficial features. Otherwise, its adversarial effect will fade out through the computation of all DNN layers. We quantitatively evaluate the impact of SIN during predictions of benign and patched images as follows.
1) Localized SIN Feature Analysis: SINs in patched images are much more localized than that in benign images. We show the Top-200 neurons in the activation map of the first layer for benign images and patched images in Figure 1(a). Then, we compare the standard deviation of distance between the Top-200 neurons to the central neuron of benign images and patched images for randomly-sclecter 10.000 images in ImageNet dataset. The patched images' distance deviation is much smaller than benign images, as shown in Figure ((b). Additionally, we also cluster the Top-k neurons with the classic MeanShift clustering algorithm and observe the cluster number of SINs in patched images is much less than that in benign images. As shown in Figure I(c), for patched images, about 75% of cases have only one cluster and 99% of cases have less than two clusters. While for benign images, more than 75% of the cases have more than three clusters. The results indicate that SINs are much more localized patched images in terms of both the distance and cluster number.
By occluding the localized SINs in a small window, the prediction results of patched images are unstable, while benign images seldom change. Specifically, we examine when moving the localized SIN features, how the prediction results are affected in patched images and benign images. We compare the prediction accuracy of benign objects and patched objects before and after moving out the localized SINs (I-SIN), as shown in Figure I(d). In this experiment, we consider ImageNet images that can be correctly classified by the model eliminate the interference of other factors. The results show that for benign images, the prediction accuracy is not sensitive to the localized SIN features. For the patched images, originally the prediction accuracy is extremely low because of the patch effects. After moving the localized important features, the detection rate increases drastically, which indicates that the patch effect has been effectively eliminated. The results show that the nature images perform robust classification without relying on extremely localized SIN features, while patches rely on the extremely localized SIN features to deccive and induce the object detector to output the incorrect results.
2) Prediction Stability Analysis:
10000 randomly-selecte
The adversarial patch attacks confront with the dilemma of either introducing large SINs or hardly affecting the prediction results. We perform the adaptive attacks on ImageNet dataset and the results are shown in Figure 1 (e). To steer clear of the detection based on SINs, the adversary trains the adversarial patch by taking the superficial activation value into consideration. Compared to Equation(1) 1), a penalty loss of activation value is considered with the parameter a, when is larger, the attack pays more attention to the stealthiness other than the attack effectiveness. In this way, the adversary aims to build the adversarial patch with both good poisoning effects, but also trying escape from the adversary candidate searching.
3) Adaptive Attack Against SIN-based Detection:

---

Adversary detection rate refers to the rate that detector correctly identifies the adversarial region in the adversarial inputs or the benign input with no adversarial region. The results show that, it is indeed that the adversary detection rate decrease to 82.1% when adversary attempts to reduce the activation magnitude in the first layer (ar increases from 0 to 0.01). However, compared to the gentle slope of adversary detection rate, the attack success rate decreases much more drastically. When is increased from 0 to 0.01, the adversarial attack success rate drops to 7.9%. These results indicate that the adversary cannot maintain the two goals of high attack success rate and good stealthiness in SINs simultaneously. The detailed attack setup and the datasets are covered in Appendix A.I.
These results show the empirical evidence to the hypothesis that the adversarial patch attacks rely on the strengths of localized SINs to effectively damage the prediction results of victim models. We leverage such insights to design ScaleCert certified defense methodology. Different from the motivation of previous studies [25], we don't constrain the reception field to localize the adversarial feature effect in the deep features, but focus on the elimination of poisoned SIN features. More comparison and discussion between these two design philosophies are provided in Appendix A.3.
3.2 ScaleCert Framework
SIN: Giving the feature map of the superficial important layer, we sort the neurons by the sum of their activation through channels and regard the top-k neurons as the SIN. SIN is not static but dynamic for each image during their inference. for occluding region Suppose we use the layer 8, and the Nt is notated as the feature map of i-th channel of layer The SIN(n=) is defined as follows:
SIN(n") = TN*)(N*) where === >
SIN-mask: SIN-maskin is dynamically generated according to SINs when taking in different inputs. Specifically, mINk is dimensional and is the same size as the feature map of the superficial important layer. Giving the feature map of the superficial important layer, SIN-mask is the mask where the positions of SINS are set to and others are set to O.
ScaleCert Overview. ScaleCert consists of three stages: 1) SIN-based Pruning: Calculating the SIN-mask, S, and pruning the rest of neurons. We first select the layer s as the superficial important layer, then we keep Top-k activation neurons only and prune other unimportant neurons of this layer, where k is the top-ranking ratio. 2) Occluding Prediction: With the SIN-mask of the superficial layer, we calculate the candidate searching region RR on the input image that contributes to the SIN. Then we impose sliding windows on x and check their overlaps with the candidate searching region R. ScaleCert makes inference by masking out every sliding window that w n R o 0 with dynamic baN-based pruning independently, and obtain the occluding prediction map. The size of sliding window w is k x k. where k equals to the sum of patch size (p) and an additional step (r-1) 1) (r is in the evaluation setting). Therefore, there are at least r X r windows that completely occlude the adversarial patch. 3) ScaleCert Detection: Finally, check the labels of the prediction map to detect whether there is an adversarial patch. If all the labels in the masked predictions are consistent, there is no attack and return the original model prediction M(x). ScaleCert leverages SIN- SIN-based sparsity to not only reduce the occluding windows, but more importantly filter out the noisy labels in trivial prediction maps and achieves the ofate-of-the-art certified accuracy.
Neural Network Sparsification. The key success factor of ScaleCert is leveraging the pruning technique on the superficial layer to improve certified accuracy and efficiency. In order to maintain the clean accuracy of our ScaleCert, we need to finetune the model with the sparse superficial layers. Figure 2 illustrates the the proposed winner-take-all dropout. We add the SIN-mask after the superficial layer(s) and prune the non non-important neurons according to the activation magnitude. Only the top-ranking neurons (winners) can forward their outputs to the following layers. To finetune the sparsified neural networks, we only update the top-ranking neurons selected by the SIN-mask. This finetuning procedure can be treated as a shallow layers channel pruning, the SIN-mask, S will also be updated during each iteration.
Occluding Prediction. With the SIN mask S, we first calculate the input region R that contributes to the SINs. The calculation procedure is as follows: for the neuron with the ordinate of (æ y,) in superficial neural network layer its antecedent neurons in layer
1 that contribute to the value of this neuron are in the square region with the top left ordinate (ar, 8, - Ps: Us * 8, ps)) and the bottom right ordinate (I, 8, Ps ke 1, yo * 3, Ps + kg 1), respectively, where p.. 8,
5

---

SIN-based Pruning
inference with
the first
Candidate Searching
Top-k Pruning
Sliding
Input
Superficial Layer
SIN Mask S
Candidate Searching Regions R
Window
Occluding
Benign Sample
sparsifled
Patch Detection using algorithm D
Top pruning
Adversarial Sample
22
Prediction Map
Occluded Images
Occluding Prediction
@ ScaleC ert Detection
Figure 2: ScaleCert Framework with three stages: SIN-based Pruning: Occlude Prediction; and ScaleCert Detection.
and k; are the padding size, stride size and kernel size of layer 8. Then, we can iteratively calculate region in the inference pyramid until back to the initial input layer and obtain region R. R. is the candidate region for occluding prediction, while all the pixels falling out this region cannot affect the prediction results because of the SIN mask.
Then we impose the sliding window w across all the R region and obtain the occluding prediction map by moving out the pixels in the sliding window. Note that, also mask the superficial features of occluding region by set their values as the lowest one in this feature map when masking the input pixels make the occluded region locates out of the SIN area, therefore, not affecting the prediction. The number candidate window w has been reduced because of SIN mask. To reduce the overhead of inference procedures in the further step, additionally propose merge adjacent occluding windows when the overlapped area among every two windows exceed the threshold (r). To note, the merging operations assure every occluding window that has overlap with R for the certified robustness.
Merged window
The overlapped area exceeds threshold
overlapped area not exceeds threshold
Windows still keep
(a)
(b)
Figure 3: Merge sliding occluding windows. (a) Original windows. (b) Merged windows.
Detection Methodology The detailed ScaleCert detection algorithm is given in Algorithm 1. ScaleCert only imposes sliding window on the R based on the SIN area since other neurons will be masked out during inference. Interestingly, the SIN-mask not only helps saving time but also filters out most noisy area on the original images so that makes the Y4 more consistent in SIN area and benefits on improving the clean accuracy on benign images. For patch attacked cases, there must be r x region that the label will changed when we masking out this area. So algorithm will alert (line 12) user and provide the potential patch location that can be used to empirically recover true label by occluding the area. some rarely happened cases, like there are noises on the input even in the SIN area, cannot make the promise decision, and conservatively raise alarm (line 14).

---

Algorithm Our adversarial patch detection algorithm
1: Inputs: image x, model M, sliding windows the input W and candidate searching region R.
2: Output: Prediction (x) or alert
3: $ 2-
4: y" +M(x)
5: for each w; E W do
6: if w, n R + then
D- Filter out some potential sliding windows Obtain the label according the mask-out input
7:
y/i M(x @ w.)) if
8:
# y then
9:
S (W.. 34)
P Collect potential malicious windows and prediction labels
10: if S + / then
11: if S contains y' and 3 y for Vw, E Ryxr then
return alert 13: else if MAJORITY VOTING(Y;) * y" then
12:
b Adversarial patch detected at Ryxr area
14:
return alert
D Possible adversarial patch with noises in S
else
16: return y²
b benign image with noises in S
17: else
18:
return y
benign image
Algorithm 2 Our certify algorithm
1: Inputs: image x, label model M, sliding windows on the input W and candidate searching
region R
2: Output: Whether the image x has provable robustness to label
3: for each w; E W do
4: if n R + 0 then
5:
1/4 - M(x o (1 w:))
6: if A y then
7:
return False
8: return True
3.3 Provable Robust Analysis
ScaleCert Certification this paper, we assume the attacker has full knowledge of our defense method and is allowed to arbitrarily change pixels in square region based any needed information of the threat model. Our detection defense method ScaleCert aims to provably ensure that certified image can be correctly classified or yields alarm together with potential patch location and maintain high accuracy on benign images.
Theorem If Algorithm returns True for a given image x, our defense in Algorithum can either make correct prediction or alert any adversarial image x' E A(xx)
The Algorithm 2 returns True indicates that all single sliding window that w; O R. * 0 do not affect the prediction results for image like Figure 4(b) while the effect of other windows are all eliminated since the top-k pruning like Figure 4(c). Then if we apply adversarial patch attack on which means any x' E A(x) can be fed to Algorithm 1, there are two possible cases:
Proof:
The adversarial patch overlaps with the SIN area of certified benign image like Figure 4(d) and leads a malicious label. For occluding windows that not overlap with the patch, the outputs not changed like Figure 4(e). However, consider of the size of our sliding window and the patch size are k x l and x p. and respect to the condition that 1: = p + adversarial patch like Figure 4(f), and the new pruned SIN area is the same as the benign images with same occluding window like Figure 4(b), the masked out prediction is exactly the true label. Therefore, in this case Algorithm 1 returns alert (line 12).
Case 1:
there must have
sliding windows that completely mask out the
Case The adversarial patch locates outside the SIN area like Figure 4(g) and outputs malicious label. Occluded images that not occluding the patch still maintain the malicious

---

Selected Top-k region
x
Occluding window
Adversarial patch
No patch attacked
Pruned
Pruned
Pruned
Pruned
X
Tap-k
Top-k
Top-k
Top-k
No occluding True
Occlude Top change the prediction
Occluce prumed region
Adv patch attacked
Pruned
Pruned
Pruned
Pruned
Pruned
W
Pruned
Top-k
Top-k
Top-k
Top-k
Top-k -k
Top-k
occluding (e) Occlude reglon
Occlude petch True label as (b).
(gi) No occludiing Malicious label
(h) Occlude Top-k region
Occiudle patch
Malicious label
Malicious label
Malicious label
True label as (c).
Alert triggered
Alert ts triggereg.
Patch locates at the SIN region
Patch is outside the SIN reglon
Figure 4: The certified benign image with only Top-k region retained(a) and occluded images that masking benign image out with occluding windows (b, c) are all classified as true label( label( Algorithhm 2). Attacked images that patch locates at the Top-k region(d, f) or outside the Top-k region (g, h, i) will alert (f, i) that ensures the correctness of certification.
labels. But, there also exists x windows that masked out the patch completely and recover the correct label like Figure 4()) which triggers the alarm (Algorithm line 12).
Note that, the line 13-16 16 in Algorithm I is not necessary to the certified defense, since the patch is provably caught in line 11 when the input x returns True in Algorithm 2. They are designed for the benign image with noises in SIN area both patch and noises happened in SIN area. In summary, Algorithm is a general empirical adversarial patch detection method but when combining with the Algorithm 2, it can conclusively output normal predictions on clean images but alert when attack takes place for the certified inputs.
Experiments
4.1 Experiment Sctup
Certified accuracy: note that our Algorithm I can return provable answer if the input image is benign can be recovered by our algorithms, but it may be incapable of rare examples that violate our assumption. So the certified accuracy we defined here is lower bound of the real certified accuracy.
Evaluation Metrics
Datasets and Models. We evaluate the clean and certified robustness results on the high resolution dataset with 224x 224 sizes (1000-class ImageNet [13]) and low resolution dataset with 32x 32 sizes (10-class CIFAR- 10 [12]). In our evaluation, we use ResNet50 [9] for ImageNet dataset and ResNet18 [9] for CIFAR-10 10 dataset. We train the models with pretrained weights and finetune them with SIN-based pruning and window occluding of random locations to improve the performance of inference.
Baselines. We compare the defense performance with the state-of-the-ar studies: PatchGuard++ [24], PG-mask-BN BN [25], PG-mask-DS [25], Clipped BagNet (CBN) [1], De-randomized Smoothing [15], and Interval Bound Propogation based certified defense (IBP) [3]. We use the optimal parameter settings in their configurations obtained from their reports.
Attack Patch Size We adopt the similar configurations from previous studies that defend against a single sequare adversairal patch that consists up to 1%, 2%, or 3% pixels of the ImageNet images, and 0.4% and 2.4% pixels of CIFAR-10 10 images. Additionally, we also report the extremely large patches with 5% and 8% in the Appendix A.4.

---

4.2 Provable Robustness Results
The certified accuracy results of ScaleCert and other recent studies are presented in Table 2. For ScaleCert, 10 trials have been run to get the average results with different random seeds. The small variance that 0.89 for clean accuracy and 0.27 for certified accuracy for ImageNet with a patch of 1% pixels indicates that ScaleCert can give stable results. For PatchGuardd++ MRD, and ScaleCert, the certified accuracy refers to the certified detection accuracy. For others, the certified accuracy refers to the certified recovery accuracy. These results hold for any attack within the patch size constrain. We draw the following conclusions from the results.
Existing studies achieve good certified accuracy in low-resolution images, but very poor provable robustness in high-resolution images. For example, when patch size is 2.4% of the images, PatchGuard++, PG-Mask-DS. DS, PG-Mask-BN BN achieves 74.1%, 37.7%, and 47.3% of certified accuracy. For ImageNet dataset, their certified accuracy decreases to 33.9%, 19.0% and 26.0%. There are two potential reasons behind this phenomenon: 1) Deeper models are used for the classification of high-resolution images. With deeper layers, the reception field becomes larger even using BagNet with limited small kernel size. It is hard to distinguish and eliminate the adversarial effect at the deep feature extraction layer. 2) For high-resolution images, the random ablation in DS- algorithms unable to produce satisfactory accuracy due to the loss of the most information of the input images.
MRD and IBP are computational infeasible for high-resolution images. MRD requires to compute the prediction map for every occluding window, which introduces infeasible computational overhead with O( x H) inference rounds. For example, MRD requires about 36481 inference rounds when the patch is 2%, which costs about 49 s for V V100 GPU platform to verify single input image with 224x224 pixels even after parallelization optimization. As a comparison, our study reduces the candidate windows number to less than 100, which significantly removes the computation overhead.
ScaleCert outperforms other defenses with much certified accuracy for ImageNet datasets, which pushes the certified defenses into practical usage. ScaleCert achieves both good certified accuracy for low-resolution images and high-resolution images. For high resolution images, particularly, the experimental results show that ScaleCert achieves the best certified accuracy. Specifically, when patch contains 1% pixels of the input images, ScaleCert achieves 60.4%, largely surpassing the PatchGuard++ with 36.3% of certified accuracy. CIFAR- 10 images are very small with the only size of 32 32, and thus are much more sensitive to pruning operations and masking operations. Therefore the certified accuracy of ScaleCert drops slightly compared to MRD.
Table 2: Comparison of clean and certified accuracy under different defenses
Datasct
ImageNet
Cifar
Patch size
1% pixels
2% pixles
3% pixels
0.4% pixels
2.4% pixels
Accuracy
clean
robust
clean
robust
clean
robust
cleun
robust
clean
robust
IBP
computationally infeasible
65.8
$1.9
47.8
30.3
CBN
53.5
21.9
53.5
13.7
53.5
7.4
83.2
$1.0
83.2
16.2
Certified Recovery
DS
44.4
20.5
44.4
17.0
44.4
14.9
83.9
68.9
83.9
56.3
PG-Mask-DS DS
44.5
22.5
44.1
19.0
43.7
16.6
84.7
69.2
84.6
57.7
PG-Mask-BN
55.0
32.3
54.6
26.0
54.0
19.8
84.5
63.8
83.9
47.3
MR
computationally
infeasible
87.6
82.5
84.2
78.1
Certified Detection
PatchGuard++ ScaleCert
61.8
36.3
61.6
33.9
61.5
31.1
82.0
78.8
78.2
74.1
62.8
60.4
58.5
55.4
56.4
52.8
83.1
81.0
78.9
75.3
4.3 Detailed Analysis of ScaleCert
The insight of ScaleCert is to leverage the intrinsic differences of SINs in patched and benign images to achieve effective defenses. There are two key parameters affecting the clean and certified accuracy: the pruning rate in the shadow region and the occluding window size target the adversarial patch (more discussion in Appendix A.2). In the ScaleCert algorithm, some hyperparameters can affect these two important parameters: the winner rate of SIN mask (I), the overlap ratio for merging the searching window (T). and the superficial layer selection (l). We analyze the impact of k. r, (in Appendix A.4) on the certified defense effectiveness and efficiency.
Pruning Rate of SIN Mask: We test the vanilla model accuracy, clean accuracy, and certified accuracy with different winner rate k ranging from 10% to 20%, as shown in Table 3. The winner

---

rate refers to the top k neurons in superficial layer and pruning others. The results show that: 1) the vanilla model accuracy maintains when the top top-ranking rate larger than 10%. 2) The selection of the winner rate k is the tradeoff between the activation sparsification level and inference accuracy. On one hand, smaller k reduces more overhead of certified defenses by reducing the candidate sliding windows and filtering more noise prediction labels. On the other hand, it is more challenging to maintain the accuracy of the neural network with the heavy pruning activation map.
Table 3: Effect of Nop-Ranking rate
Pop-Ranking Rate
10%
15%
20%
Patch size
Model
Clean
Cert.
Model
Clean
Cert.
Model
Clean
Cert.
1%
73.6
61.4
56.0
74.2
60.5
58.4
75.0
62.8
60.4
2%
73.8
58.7
51.8
74.6
58.7
54.9
74.4
55.9
53.3
3%
73.2
54.0
48.6
74.3
57.3
49.6
74.2
56.5
51.6
Occluding Window Sizes. We also test the impact of overlap ratio threshold (7) when merging the occluding windows reduce the searching windows for the better computing efficiency. When is larger, less windows will be merged, resulting with larger candidate searching window number and smaller occluding window size. Larger occluding window may hurt the model prediction accuracy. Less candidate searching window can accelerate the detection procedure and remove noises in the prediction map. Hence, the selection of overlap ratio is the tradeoff between occluding window number and window size. As shown in Table 4, the results indicate that ScaleCert can achieve both good certified accuracy and introduce the smallest computing overhead, when overlap ratio threshold is 0.3. We achieve over 100x of speedup compared to MRD [17] and comparable computing overhead with PG-Mask-DS [25].
Table 4: Effect of overlap ratio threshold (PatchSize=2%, k= (00%
Overlap Ratio (T)
0.3
0.5
0.6
Candidates
25
36
64
Execution Latency (V100 GPU)
219ms
306ms
508ms
Occluding Window Size
77
64
58
Clean Accuracy
62.5
59.8
61.1
Certified Accuracy
56.6
55.2
56.0
4.4 Empirical recovery of ScaleCert
We evaluate the empirical recovery ability of our method on 10,000 randomly selected images that can be correctly by ResNet50 model from ImageNet. Firstly, for each image, square patch with 5% pixels is generated and placed on the image at random location. The classification accuracy drops to 14.0% after attack patchs. Then, we localize the patch of each image using algorithm We tear the localized patch areas off from each image and put the masked image into inference to get the recovery label. The classification accuracy significantly improved 85.8%, which empirically shows that ScaleCert can effectively recover the true label from patch attacks by occluding the patch regions.
5 Conclusion and Future Work
In this paper, we propose the certified defense methodology ScaleCert for the detection of adversarial patches in high resolution images. We observe that adversarial patch intends to leverage localized superficial important neurons (SIN) to manipulate the prediction results. Hence, we propose SIN-based sparse techniques to reduce the adversarial region searching overhead and filter the prediction noises, which significantly improves the certified accuracy with good computing efficiency.
Acknowledgements
This work is partially supported by the Beijing Natural Science Foundation (JQ18013), the NSF of China(under Grants 61 61925208, 62002338, U19B2019), Beijing Academy of Artificial Intelligence (BAAI) and Beijing Nova Program of Science and Technology (Z1911000011 1 19093). , CAS Project for Young Scientists in Basic Research YSBR-029), Youth Innovation Promotion Association CAS and Xplore Prize.
10

---

Broader Impact
As the widely usage of deep learning systems in the real world, our method can practically improve the robustness of DNN applications against adversarial patch attacks. Overall, we believe our paper has positive impact in the society but may potentially be misused to identify the weakness of DNNs.

---

References
[1] Wieland Brendel and Matthias Bethge. Approximating CNNs with bag-of-local loaa---- models works surprisingly well on ImageNet. In 7th International Conference on Learning Representations (ICLR), 2019.
[2] Nicholas Carlini and David Wagner, Adversarial examples are not casily detected: Bypassing ten detection methods. In Proceedings of the 10th ACM Workshop on Artificial Intelligence and Security, pages 3 14. ACM, 2017.
[3] Ping-Yeh Chiang, Renkun Ni, Ahmed Abdelkader, Chen Zhu, Christoph Studor, and Tom Goldstein. Certified defenses for adversarial patches. In 8th International Conference on Learning Representations (ICLR), 2020.
[4] Jeremy M. Cohen, Elan Rosenfeld, and J. Zico Kolter. Certified adversarial robustness via randomized smoothing. In Proceedings of the 36th International Conference on Machine Learning (ICML 2019), volume 97. pages 1310-1320, PMLR, 2019.
[5] Kevin Eykholt, Ivan Evtimov, Earlence Fernandes, Bo Li, Amir Rahmati, Chaowei Xiao, Atul Prakash, Tadayoshi Kohno, and Dawn Song. Robust physical Proceedings of the IEEE Conference Computer Vision and Pattern Recognition, pages
chysical-world world attacks on deep learning visual classification. In
2018.
[6] Yiming Gan, Yuxian Qiu, Jingwen Leng, Minyi Guo, and Yuhao 7hu. Ptolemy: Architecture support for robust deep learning. In 2020 53rd Annual IEEF/ACM International Symposium on Microarchitecttue (MICRO), pages 241-255. IEEE, 2020.
[7] Sven Gowal, Krishnamurthy Dvijotham, Robert Stanforth, Rudy Bunel, Chongli Qin. Jonathan Uesato, Relja Arandjelovic, Timothy Arthur Mann, and Pushmeet Kohli. Scalable verified training for provably robust image classification. pages 4841 4850,, 2019.
[8] Jamie Hayes. On visible adversarial perturbations & digital watermarking, In 2018 IEEE Conference on Computer Vision and Pattern Recognition Workshops (CVPR Workshops), pages 1597-1604, 2018.
[9] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference computer vision and pattern recognition, pages 770-778, 2016.
[10] Yihui He, Xiangyu Zhang, and Jian Sun. Channel pruning for accelerating very deep neural networks. In Proceedings of the IEEE International Conference on Computer Vision, pages 1389-1397 2017.
[11] Siddhant M. Jayakumar, Razvan Pascanu, Jack W. Rae, Simon Osindero, and Erich Elsen. Top-kast: Top-k always sparse training. In NeurlPS, 2020.
[12] Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. Technical Report 7R-2009, 2009.
[13] Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convolutional neural networks. In Advances in neural information processing systems (NIPS), pages 1097-1105, 2012.
[14] Mark Lee and Zico Kolter. On physical adversarial patches for object detection. arXiv preprint arXiv: /197, 2019.
[15] Alexander Levine and Soheil Feizi. (De)randomized smoothing for certifiable defense against patch attacks. In Conference on Neural Information Processing Systems, (NeurIPS), 2020.
[16] Fengting Li, Xuankai Liu, Xiaoli Zhang, Qi Li, Kun Sun, and Kang Li. Detecting localized adversarial examples: A generic approach using critical region analysis. arXiv preprint ttXiv:2102.0524/1 2021.
[17] Michael McCoyd, Won Park, Steven Chen, Neil Shah, Ryan Roggenkemper, Minjune Hwang, Jason Xinyu Liu, and David Wagner. Minority reports defense: Defending against adversarial patches. In International Conference on Applied Cryptogruphy and Network Security, pages 564-582. Springer, 2020.
[18] Michael McCoyd, Won Park, Steven Chen, Neil Shah, Ryan Roggenkemper, Minjune Hwang, Jason Xinyu Liu, and David A. Wagner. Minority reports defense: Defending against adversarial patches. In Applied Cryptography and Network Security Workshops (ACNS Workshops). volume 12418, pages 564-582. Springer, 2020.
[19] Muzammal Naseer, Salman Khan, and Fatih Porikli. Local gradients smoothing: Defense against localized adversarial attacks. In IEEE Winter Conference on Applications of Computer Vision (WACV), pages 1300-1307, 2019.
12

---

[20] Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties of neural networks. 2013.
[21] Shiqi Wang. Huan Zhang, Kaidi Xu, Xue Lin, Suman Jana, Cho-Jui Hsieh, and J Zico Kolter. Beta-crown: Efficient bound propagation with per-neuron split constraints for neural network robustness verification. In ICML 2021 Workshop on Adversarial Machine Learning, 2021.
[22] Eric Wong and Zico Kolter. Provable defenses against adversarial examples via the convex outer adversarial polytope. In ICML, 2018.
[23] Zuxuan Wu, Ser-Nam Lim, Larry Davis, and Tom Goldstein. Making invisibility cloak: Real world adversarial attacks on object detectors. In European Conference on Computer Vision, pages 1-17. Springer. 2020.
[24] Chong Xiang and Prateek Mittal. Patchguard+++ Efficient provable attack detection against adversarial patches. arXiv preprint 1rXiv:214.126000 2021.
[25] Chong Xiang, Arjun Nitin Bhagoji, Vikash Sehwag, and Prateek Mittal. Patchguard: A provably robust defense against adversarial patches via small receptive fields and masking. 2021.
[26] Kaidi Xu, Sijia Liu. Zhao, Pin-Yu Chen, Huan Zhang, Quanfu Fan, Deniz Erdogmus, Yanzhi Wang, and Xue Lin. Structured adversarial attack: Towards general implementation and better interpretability. In International Conference on Learning Representations, 2019.
[27] Kaidi Xu, Zhouxing Shi, Huan Zhang, Yihan Wang, Kai-Wei Chang, Minlie Huang, Bhavya Kailkhura, Xue Lin, and Cho-Jui Hsieh. Automatic perturbation analysis for scalable certified robustness and beyond. Advances in Neural Information Processing Systems (NeurIPS), 2020.
[28] Kaidi Xu, Gaoyuan Zhang, Sijia Liu, Quanfu Fan, Mengshu Sun, Hongge Chen, Pin-Yu Chen. Yanzhi Wang, and Xue Lin. Adversarial t-shirt! evading person detectors in physical world. In ECCV, pages 665-681, 2020.
[29] Zirui Xu, Fuxun Yu, and Xiang Chen. Dopa: A comprehensive cnn detection methodology against physical adversarial attacks. arXiv preprint arXiv:
2019.
[30] Zirui Xu, Fuxun Yu, and Xiang Chen. Lance: A comprehensive and lightweight enn defense methodology against physical adversarial attacks on embedded multimedia applications. In 2020 25th Asia and South Pacific Design Automation Conference (ASP- -AC)), pages 470 475. IEEE, 2020.
[31] Ruichi Yu, Ang Li. Chun-Fu Chen, Jui-Hsin Lai, Vlad Morariu, Xintong Han, Mingfei Gao, Ching-Yung Lin, and Larry Davis. Nisp: Pruning networks using neuron importance score propagation. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 9903,,20,, 2018.
[32] Huan Zhang, Hongge Chen, Chaowei Xiao, Bo Li, Duane Boning, and Cho-Jui Hsieh. Towards stable and efficient training of verifiably robust neural networks. In International Conference on Learning Representations, 2020.
[33] Zhanyuan Zhang, Benson Yuan, Michael McCoyd, and David Wagner. Clipped bagnet: Defending against sticker attacks with clipped ofg-of-features. features. In 3rd Deep Learning and Security Workshop (DLS), 2020.
[34] B. Zhou, A. Khosla, A. Lapedriza, A. Oliva, and A. Torralba. Learning deep features for discriminative localization. 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 2921 -2999. 2016.
13


Reviews:
[{"review_id": "rukWBVuc3QH", "reviewer": "Reviewer_1feY", "summary": "The proposed approach presents scalable certified defense against adversarial patch attack.  The method relies on pruning unimportant neurons and identifying regions in the input image which contain the adversarial patch. Once the patch location is identified, the label is predicted is using prediction consistency. A certification algorithm is provided which shows significant improvements over previous methods on ImageNet. ", "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": "Strengths:\n\n— The method shows significant improvement compared to previous approaches on ImageNet, addressing an important problem of scalability for defenses against adversarial patch attacks.\n\n — The paper is well written and easy to follow.\n\n— Detailed ablation study shows effect of individual component of the algorithm.\n\nWeaknesses:\n\n— Results are shown on only adversarial patch attack, which is one form of physical world attack. Other attack formulations such as Adversarial framing and Adversarial camouflage are not considered.\n\n— Other large scale datasets such as Places can be considered for large scale datasets. ImageNet being an object centric dataset might be helpful in identifying the \n\npatched region.\n\nAdditional Comments:\n\n— Adversarial framing [1] and Adversarial camouflage[2] are more recent forms of physical world attack. Does the proposed approach defend well against such attacks?\n\n— Although the proposed approach works well on ImageNet, more explanation is required for explaining the drop in performance w.r.t both clean and certified accuracy on Cifar10. This gap increases as the size of patch increases.\n\n— The choice of superficial layer is an important experiment which does not lead to clear understanding of the method. Why does the performance drop for Layer 2 and increase again for Layer3 in Table 7 of the appendix?  A more thorough analysis seems necessary.\n\n[1] -  arXiv:1812.04599\n\n[2] - arXiv:2003.08757 \n\n-----POST REBUTTAL-----\nThe authors have addressed most of my concerns. Having gone through other reviews and the rebuttal, I agree that this is a good paper and I raise my score to 6.  I encourage the authors to include the discussion on the drop in performance for low resolution datasets and the guidelines for superficial layer selection.   ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have not addressed limitations and societal impact of their work. A discussion on this seems to be missing from the appendix. ", "review_text": "", "extra_scores": {"ethical_concerns": "There are no ethical concerns with this paper.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "mt_UTGgdyx", "reviewer": "Reviewer_3JJX", "summary": "This paper proposes to leverage superficial important neurons (SIN) to prune DNN to reduce the sensitivity of DNN to adversarial patches, thus resulting in certified defense of adversarial patches. The approach outperforms existing approaches largely on large ImageNet dataset.", "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": "Pros:\n- The usage of SIN, or general interpretation/compression technique, for certified defense is quite novel.\n\n- The empirical evidence that motivates the method seems compelling.\n\n- Strong empirical results.\n\nCons:\n- Method: \n1. The proposed method, ScaleCert, is an attack detection method that does not aim to recover from the attack. The certification counts the input benign example as \"certified\" as long as the method outputs the correct label or raises an alert. Thus, in contrast to attack recovery methods, the proposed method is less useful in practice than what the certification result indicates since it may be too conservative for slightly patched inputs.\n\n2. If I understand correctly, the SIN mask should be static given a model? Does it mean that the model only uses sparse, scattered, and tiny regions to sense the whole image space? If this is the case, how does the masked model preserve high benign accuracy given diverse key regions across different benign input images? Is the SIN mask generated only based on training dataset statistics?\n\n3. The approach is limited to CNNs.\n\n- Empirical result: \n1. As shown in Table 2, the method is not as good as existing methods on low-resolution image datasets like CIFAR-10.\n\n2. It would enhance the paper if there are more studies about the empirical patch detection ability, given that Line 14 in Algorithm 1 provides the ability to locate the patch.\n\n- Writing: The details on SIN is lacking in this paper. For example, what is the formal definition of SIN? How does SIN determine what neurons to mask? How does the static SIN mask be generated in experiments?\n\nMinor: Line 348, \"sparese\" => \"sparse\"\n\nIn summary, given the strong empirical results, interesting findings, and novel techniques, I weekly support the acceptance of the paper. If my concerns can be adequately addressed, especially those on SIN, I would consider raising my score.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors adequately addressed the limitations.\nThe authors may need to include the discussion about the potential negative societal impact of their work if the manuscript is accepted.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "YoJZa2bbSrR", "reviewer": "Reviewer_sS3e", "summary": "This paper proposed an algorithm called ScaleCert that attempted to improve the accuracy of certified detection against large-resolution adversarial samples. The experimental analysis about the motivation in the paper is great, the logic is clear and easy to understand, and the experiments prove the efficiency (time consuming) of the method.", "questions": "", "limitations": "", "rating": 6, "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": "1.\tAlthough the related work mentions attack recovery and robust detection, the title as well as the abstract make this work appear not to be doing adversarial detection and may mislead researchers in the field of adversarial machine learning.\n2.\tAlthough the authors' analysis is better, I still have doubts about whether ScaleCert is provable. On the one hand, some adversarial patches can make the activation values of the network concentrated in the wrong places, such as [1], and it is possible to circumvent detection; on the other hand, there is no guarantee that the pruned network can always classify the images correctly after masking different locations, that is, the adversary can carefully design patches to lower the activation values to circumvent detection, but make the non-patched regions wrongly classified after being masked. And according to the algorithm, the patch may be detected, but causes a false alarm, and such a patch is harmful to the subsequent processing. Summing up the above two points I think ScalCert is a detection with high security for general attacks, but not provable.\n3.\tWhy is the clear ACC of 2% size patch lower than the 3% case in the ImageNet experiment in Table 2? Detection accuracy should not be compared to the accuracy of robust defense, which are two completely different tasks. Experiments should give AUC values and not just detection accuracy. These experiments make me unconvinced of the validity of the method.\n\n\n[1] Subramanya, Akshayvarun, Vipin Pillai, and Hamed Pirsiavash. 2019. \"Fooling network interpretation in image classification.\" In Proceedings of the IEEE International Conference on Computer Vision, 2020-29.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "They have mentioned the limitations in the Appendix; the certified accuracy of ScaleCert maybe a little bit worse than the original accuracy. I don't see that is a limitiation to me. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "AqNDSbx7U-5", "reviewer": "Reviewer_EwCy", "summary": "In this paper, the authors propose a scalable certified defense framework to detect patch attacks. The authors empirically show that patch attacks rely on localized Superficial Important Neurons (SINs) to cause misclassification. By occluding image patches corresponding to these localized neurons, the predictions on patched images become unstable, while those of benign images rarely change. The proposed approach ScaleCert uses these SINs to check if a patch attack is present by occluding certain candidate regions and observing if the prediction changes. The proposed method leads to significant improvements in certified detection accuracy on ImageNet, while having lower computational cost, thus promoting its usage in the real world.", "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": "Strengths:\n -  While many existing certified detection methods (MRD, PatchGuard++) are based on the idea of occluding patches in the input image, and observing the stability of the output prediction, the key insight in this work is in the SIN-based pruning step, where top-k neurons are retained and the rest are pruned. This improves the scalability of the approach and also leads to less noise in prediction labels, improving the certified accuracy significantly at a low computational cost\n -  The results show huge improvements in certified detection accuracy on ImageNet, achieving 60.6% against 1%-pixel patches, significantly surpassing the highest record of 36.3% in current state-of-the-art methods. The work also doesn’t incur a huge computational cost compared to other defenses, which is beneficial for real-world adoption.\n -  The paper is clearly written and well organized. It provides enough information for the reader to reproduce its results. \n\nQuestions for rebuttal/ suggestions for improvement:\n -  Could the authors share the execution latency on Imagenet for PatchGuard++ as well, which can be compared with the results in Table-4? \n -  Could the authors clarify how the top-k neurons are found for a given layer? Is it an average/ max across all activations at that layer? \n -  The process of certification and inference seem to be quite similar. For a clean input image, if occlusion prediction gives consistent outputs and if the prediction is same as the true label, it is said to be certified. The same process is also used during inference of a clean image for prediction. So does this mean that the difference between clean and certified accuracy is from images whose predictions are consistent and incorrect? It would be worth visualizing such images to see if they are confusing visually as well. \n -  Adding more detailed captions to tables and figures would improve the readability. The x-axis label for Fig.1(e) is missing. \n -  It could be made more clear throughout the paper that this is a certified detection method rather than a certified prediction/recovery method, perhaps in the title as well. It seems unfair to directly compare certified accuracy of recovery methods to detection methods as it’s easier to detect whether a patch is present than it is to predict the correct class in any patched image. A note on why this method cannot be used for certified prediction would also help the reader understand the same better. \n\nLimitations/ Possible concerns: \n -  As seen in Table-5 of the Supplementary, clean accuracy drops significantly for 5% and 8% pixel patch attacks. \n -  The process of selecting only top-k neurons for inference could potentially make the network more vulnerable to minor distribution shifts such as addition of gaussian noise/ other corruptions when compared to a normally trained model. \n\n\n**Update Post-Rebuttal**\n\nI thank the authors for their detailed replies to clarify all concerns. Although the work is novel and shows a large improvement over prior work, there are many unclear parts and missing details, specifically about the certification, due to which I lower my score to 6. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No\n\nLimitations: The proposed method detects the presence of a patch, and does not recover the true label. \n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors develop a novel scalable robustness certification technique to certify robustness of deep networks to adversarial patches. The paper provides a theoretically and empirically interesting contribution to the literature on robustness and verification of deep networks. 

In the initial reviews, several concerns were raised around the correctness of the proposed approach. These were adequately addressed in the rebuttal. The paper would be acceptable for publication provided that the authors make the revisions suggested by the reviewers during the rebuttal phase in the camera ready version.

Specific detailed feedback from the reviewers on how to improve the paper:

1. L254-255 in the main paper needs to be rephrased to indicate that only sliding windows that overlap with  (corresponding to the benign image) do not affect prediction results for the image . Justification of why this is sufficient for certification needs to be included. This could include the figure shared by the authors in the rebuttal to illustrate that the top-k region of the attacked image cannot differ by more than a fixed amount from the top-k region of the original image. In addition, for the cases when the patch is occluded completely, the top-k region of the attacked image would be a subset of the top-k region of the benign image. This can be formally stated and proved.
2. It could be made more clear throughout the paper that this is a certified detection method rather than a certified prediction/ recovery method, perhaps in the title as well. It seems unfair to directly compare certified accuracy of recovery methods to detection methods as it’s easier to detect whether a patch is present than it is to predict the correct class in any patched image. A note on why this method cannot be used for certified prediction would also help the reader understand the same better.
3. Results on execution latency on ImageNet for PatchGuard++ (shared in the rebuttal) could be included
4. Details on how the top-k neurons are computed could be included
5. Adding detailed captions to tables and figures would improve the readability. The x-axis label for Fig.1(e) is missing
6. A discussion on false alarms and what is done to reduce this could be included.
7. Clearly define SINs and states the important properties of SINs, e.g., what is the SIN of the masked region?
8. Clearly and formally define the inference protocol. It seems to be first computing SINs then dynamically pruning the network to only pass the signals for top-k SIN neurons. The final inference protocol that takes windows into account runs multiple  inferences independently --- the top-k SINs are independently computed for each masked input.
9. A detailed proof of Theorem 1 with more illustrations.
10. Training details for reproducibility. The current submission lacks many training details nor contains code implementation. Please make sure to include them especially the description of training details.
11. Compress Section 3.1 to gain space.
12. Authors should include the discussion on the drop in performance for low-resolution datasets and the guidelines for superficial layer selection.
13. Comparison of provable detection and provable recovery should not be placed in the main text. The comparison is meaningless due to the difference in settings.
14. The statement related to the algorithm is not very clear. I suggest that the authors clearly explain the algorithm in future revisions. In addition, Line 246-257 is copied from PatchGuard++, which is not allowed.
15. Reporting error bars of results (shared in the rebuttal)
16. A discussion on limitations could be included: sub-optimal performance on low-resolution datasets, a large drop in clean accuracy with large patch attacks, and limited generalization (only works for image CNNs due to exploiting localized low-level features).
Decision: Accept (Poster)