Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 6: Marginally above acceptance threshold
review_content: 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].

As 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.

Could 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.

The 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)?

In 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? 

As 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.


[1] Brown, Tom B., et al. "Adversarial patch." arXiv preprint arXiv:1712.09665 (2017).

[2] Karmon, D., Zoran, D., and Goldberg, Y. Lavan: Localized and visible adversarial noise. arXiv preprint arXiv:1801.02608, 2018.

[3] Xiang, Chong, et al. "PatchGuard: Provable Defense against Adversarial Patches Using Masks on Small Receptive Fields." arXiv preprint arXiv:2005.10884 (2020).

[4] Levine, Alexander, and Soheil Feizi. "(De) Randomized Smoothing for Certifiable Defense against Patch Attacks." arXiv preprint arXiv:2002.10733 (2020).

review_title: Promising results on certifiable robustness to visible adversarial noise. Hard to decipher the level of technical contribution.

final_score: rating: 7: Good paper, accept
review_content: Summary:
This 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.
For 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.

The proposed method achieves comparable or better results in terms of verified accuracy and nominal accuracy, while being significantly faster.

Comments:
- Figure 1 is quite helpful for understanding the principle of the proposed architecture.
- 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.
- 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?

Opinion:
The paper provides a simple, interesting approach, and describes it clearly. The empirical performance is also validated on both CIFAR and ImageNet.
review_title: Simple approach to verified robustness to patch attack producing good results.

final_score: rating: 7: Good paper, accept
review_content: 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).

To 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. 

In 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.

Pros:
1) The paper is well-written and is pleasant to follow.
2) The proposed certification condition and training objective are novel and, as far as I can tell, are technically sound.
3) Formal analysis incorporates and properly relates the certification condition from prior work.
4) Experimental results are convincing and additionally include efficiency comparison.

Cons:
1) 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.

Question:
1) 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?
2) 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?

Overall, I believe this is a strong paper, containing both theoretical and practical novel contributions and I think it should be accepted.
review_title: Convincing novel training and robustness certification approach for adversarial patches in image classifiers

final_score: rating: 6: Marginally above acceptance threshold
review_content: 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.

Advantages: 
1.The paper gives good formal descriptions and rigorous proofs. 
2.The certification section is well structured. The narrative is logically layered and well-organized. 
3. The paper gives a SOTA certified accuracy with high clean accuracy on ImageNet. 

Concerns: 
1. 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)?
2. Could you provide the training cost compared with Derandomized smoothing? In theory, the method is faster. 
3. The description of R(l) in 3.1 is so unclear that it is difficult to understand the meaning of R(l).
4. 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?

review_title: This paper presents a provable defense method called BAGCERT against patch attacks which uses an invariant of BagNet for certification. 

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)