Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 6: Weak Accept
review_content: This paper attempts to extend the Interval Bound Propagation algorithm from (Gowal et al. 2018) to defend against adversarial patch-based attacks. In order to defend against patches which could appear at any location, all the patches need to be considered. This is too computationally expensive, hence they proposed to use a random subset of patches, or a U-net to predict the locations of the patches and then use those patches to train. The algorithm is tested on the MNIST and CIFAR-10 datasets and it was shown that sometimes the IBP approach is useful for defense, although often with a significant loss on accuracy on clean data (e.g. on CIFAR the loss on clean accuracy is an astounding 300% -- from 66.5% - 35.7%).

I think the technical contribution of this paper is a bit weak in that they mostly followed the original IBP and the only novelties are the random patch training and guided patch training. I partially like how the experiments are conducted, especially the one that generalizes to other shapes. On the other hand, the networks that are tested seem pretty poor by any standard. An experiment that is definitely missing is a CIFAR network that performs a little better than the current one. Clean accuracy of only 66.5% and 47.2% are very lousy for CIFAR.

Another missing experiment is one that would test on different epsilon values. I couldn't find what are the current epsilon values used?

Besides, since this work is testing on adversarial patches, I would like to at least have it applied to some real-life images with patches that are of real-life size. I could care a bit less on how good it is, but one can still make an empirical test (e.g. certified defense accuracy on 5x5 patches, but empirical test using real-life sized patches 40x40 or 80x80) and see how the results would be. All the experiments mentioned above would significantly strengthen the experiments section of the paper.

I don't think I read anywhere a confirmation that the testing is performed on all patches of the prescribed size. Could the authors please confirm whether this is true?

Minor: 
There is a typo in Eq. (5) and Eq. (6), where the second term multiplied by |W^(k)| should be \underline{z}^(k-1) - \bar{z}^(k-1) instead of \underline{z}^(k-1) + \bar{z}^(k-1)

You should mention that |W^(k)| stand for element-wise absolute value when it first appears.
review_title: Official Blind Review #1

final_score: rating: 6: Weak Accept
review_content: The paper proposes a certified defense for adversarial patch attacks.
Technically, the authors use the well developed IBP based methods (Gowal et
al., 2018, Mirman et al., 2018, Zhang et al. 2019).  The technique is simple
but effective. Since the number of possible patches are quadratic w.r.t image
dimension, to reduce the number of bounds to propagate, the authors propose a
U-Net based NN to predict the worst case scenario, and only propagate "worst
case" bounds predicted by the U-net.

Empirically, the proposed method gets good results, with certified accuracy
sometimes even higher than empirical accuracy by previous methods.  The authors
also provide results for transferring robustness properties to shapes that are
not included during training.

Overall, the contribution of this paper is novel, and results are promising,
but it still has some missing components, especially the idea of combining
multiple IBP bounds into one, which can be very effective for adversarial
patches, as I will elaborate below.

Suggestions and Questions:

The core idea behind IBP is that for whatever input perturbation is given (any
Lp norm or semi-norm, or non-norm based perturbations like patches at arbitrary
locations), it converts them to per-neuron lower and upper bounds after the
first linear/conv layer.  For example, if the input perturbation is *two* patches
B_1 and B_2, after propagating them through the first layer of the network, we
got two lower bounds l_{i,1}, l_{i,2} and two upper bounds u_{i,1}, u_{i,2} for
the i-th neuron. We then take the worst case bound, l_i = min(l_{i,1},
l_{i,2}), u_i = max(u_{i,1}, u_{i,2}) and propagate only one set of bounds l_i
and u_i to the next layer. The authors should explore on this direction, as
detailed below:

1. For the exhaustive patch enumeration in (11), we can actually greatly reduce
the computation cost by combining the bounds of different patches after the
first layer of the network, as I mentioned above. At the input layer, the
number of bounds (each for one possible location of patch) are large; but after
the first linear/conv layer, we can compress them to one or a small group of
bounds by taking the worst cast of them, like l_i = min(l_{i,1}, ...,
l_{i,|L|}), u_i = max(u_{i,1}, ..., u_{i,2}). The patches close with each other
should also produces similar lower and upper bounds, so taking min or max over
them will not make the combined bounds much worse. This is better than U-net
prediction since we are guaranteed to include the worst case scenario.

2. Considering multiple patches (at different locations) on a single input. In
the simplest case, consider multiple 1x1 patches (in fact, this is equivalent
to bounded L0 norm threat model); since each patch is 1x1 (only changing one
pixel), the bounds should be relatively tight after the first layer, and after
the first linear/conv layer we got 28*28 or 32*32 bounds which will be combined
into one or very few sets of lower and upper bounds that will be propagate into
later layers.  Multiple larger patches (2x2, 5x5) can be difficult since bounds
are looser; multiple 1x1 in my opinion is both technically feasible and
practically important, and should definitely be included in this paper.


Minor issues:

1. Eq. (5) and (6) are incorrect; the second term should be \overline{z} -
\underline{z}. Also it is missing the bias term.

2. In related works (section 4.1, page 3), (Weng et al., 2018) is not a defense
method (it is a certification method, and no training is involved).

3. In Table 3, it is better if the authors can provide empirical adversarial
accuracy to IBP defended networks as well.

Overall, I think it is a good paper but the authors should explore more to
strengthen their contributions. I gave a weak reject but I will not hesitate
to recommend an accept as long as the authors can provide additional results
mentioned above.

review_title: Official Blind Review #2

final_score: rating: 6: Weak Accept
review_content: This paper proposed a certified defense method for adversarial patches. The paper is motivated by the finding that several existing works on adversarial patch defenses are easily "breakable" by in the white-box setting. The idea of the proposed method is derived Interval Bound Propagation (IBP), which is originally proposed for certified defense against adversarial noise. To simplify the certificate training in the patch defense setting (which original scales quadratically with respect to the image size), two randomized training methods are proposed. Lastly, experimental results indeed verify the effectiveness of the proposed method.

The paper is well-written and very well-organized. It is interesting to see supposedly strong adversarial patch defense methods "break down" in a very simple setting. And the contribution of the paper is significant to the field.

I do have a question with regard to the randomized training method:
Although random patches (or selected worse-case patches at random location) can be used for certificate training, in order to create a certificate during testing, does it mean that you do have to conduct many forward pass of the network with respect to all patches at all locations?
review_title: Official Blind Review #3

Meta-review: This paper presents a certified defense method for adversarial patch attacks. The proposed approach provides certifiable guarantees to the attacks, and the reviewers particularly find its experiments results interesting and promising. The added new experiments during the rebuttal phase strengthened the paper. There still is a remaining concern that is novelty is limited as this paper could be viewed as the application of the original IBP to patch attacks, but the reviewers believe in that its empirical results are important.
Decision: Accept (Poster)