Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This work investigates an observation that certifiably robust neural networks flag inputs for which local robustness checks fail, but are classified consistently with all valid inputs within a distance of $\epsilon$. The authors actuate this observation in an attack where norm-bounded changes degrade the utility of certifiably robust networks by forcing them to reject otherwise correctly classifiable inputs. 
main_review: While a number of concerns on clarity, the overall observation made by the authors is simple, useful, and evaluated thoroughly. It is, however, unclear whether the observation is novel under the current manuscript. See below for more details:

- "One need not assume that the inputs are scaled to be in $[0,1]^{d}$ , and hence we can drop the second optimisation constraint." This constraint is there because neural networks typically operate on bounded inputs, where there are no guarantees on inputs which do not follow the scaling rule the network uses for preprocessing. I assume the argument for why this can be dropped is this constraint is replaced by ensuring the adversarial belongs in the support set. Please confirm, and update the text s.t. this is explained explicitly. 
- While Figure 1 is clear, it would be useful if the motivation could be based on a practical example that could come up in practice, s.t. the practical application of the method presented in the paper is clear to the reader. 
- Can the authors clarify why Algorithm 3.1 is effective? First, clarify why simply applying an off-the-shelf white-box attack with epsilon bound would fail, then explain why projecting the perturbation from an off-the-shelf white-box attack with double the epsilon bound projected onto the epsilon sphere works. Will the projection step project onto a sphere for any valid Lp norm?
- For attacking stochastic inputs, the authors should cite any attacks which have used a similar formulation. Many attacks against stochastic defences exist, most prominent is expectation over transformation (https://arxiv.org/abs/1707.07397). Evidence of a literature review should be provided. 
- Could the authors visualize random examples found by the attack algorithm which fool the local robustness check? 
-A much clearer, description integrating sections 3.3.1 and 3.3.2 is warranted. From what I can tell, $\text{test}\_{R}$ is the same in both sections. $\text{test}\_{A}$ is identified by the degradation attack algorithms presented in the earlier section in 3.3.1, and $\text{test}\_{A}$ is identified by modifying the local robustness check in 3.3.2? If this is incorrect, please clarify. Regardless, these sections should be integrated and presented more clearly. 
-The commentary on "overapproximation" requires an extended discussion, where the concepts are introduced in a less rushed manner. 
- "A plot for the randomised smoothed models as compared to a table for the GloRo Nets is simply a reflection of the slightly different ways in which these models are evaluated." While emphasising the different ways these models are evaluated is appreciated, that by itself isn't a reason to present results in different ways. If by "reflection" the authors are implying they have to present results in different ways, then this should be explicitly clarified. If not, if the authors can compute the table computed for GloRo Nets for randomised smoothing, they should do so. Likewise, if the authors can make the plot made for randomised smoothing for GloRo Nets, they should do so. Comparing and contrasting the tables and/or the plots would also be informative to the reader. While I understand the subsequent text after this quote was intended to clarify this, it was insufficient. 
-"However, we re-train all the models using twice the values that we want to defend against." Given the commentary prior to experiments, the authors should also evaluate without re-training all models using twice the values. 
-"None of these definitions capture the idea that, to be protected from adversarial examples, a model only needs to be locally robust at every input in the support set, M." This makes the claim on novelty unclear. The formalization of the support set was only present in the presentation, it was not leveraged in neither the proposed attacks nor the proposed defenses (as sec. 4.2 leaves it to future work). What was actuated upon is the notion of "$2\epsilon$", which, as the related work shows, a number of works have explored. The authors need to further clarify the contribution relative to the existing works from the perspective of the proposed algorithms evaluated in the work. 

summary_of_the_review: Since the novelty of the paper currently needs further clarification, I am providing a borderline rating, subject to the author's rebuttal. 

AFTER REBUTTAL: The author's rebuttal did not sufficiently convince me of the novelty of the contribution, and thus the paper remains borderline in my estimation. However, I will be raising my score.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper considers a different perspective of attacks to certifiably robust ML models at test time -- the attacker can add imperceptible perturbation to force false positive of adversarial example (AE) detection, and thus lower the utility of the model/detection mechanism. It finds an empirical lower and upper bound to the degradation in performance, and validates the efficacy of such attacks against popular detection mechanisms.   
main_review: I like the idea of.degradation attack on models. The problem setting is fairly intuitive. Since the learner only gets the AE at test-time instead of the original input, some information about the original input is already lost. As a result, the detection mechanism will have a tendency to overprotect.

The theoretical part of the paper is straightforward to understand. However, I find the discussion for the double-radius defense confusing. From Algorithm 2.1, it seems that a certified run-time defense will abstain at a radius. However, in Section 4.1, the models are said to be "trained" with parameter $2\epsilon$. Does it mean that the models will abstain at radius $2\epsilon$ during test-time? If yes, then it just opens a larger feasible set for degradation attack check. Could you please explain this more formally with helping lemma stating the guarantee of the defense mechanisms?

My other main worries about the paper are on the experiment results and design. Since the degradation attack phenomenon is quite easy to understand, I hope the experiments can clearly show the severity of such new threats. On top of the existing results, I hope the authors can address the following questions.

1) What's the choice of your attack parameter $\epsilon$? The choice now looks quite arbitrary. Please show degradation AE created at each $\epsilon$ so that the readers know the visual similarity at the perturbation level.

2) What's the gap between the lower and upper bound of the attack? Is there any pattern/conclusion we can find from the gap?

3) How about the result for other $\ell_p$ distances like $\ell_{\infty}$? 

Also, is there a reason only showing the upperbound for GloRo in table and that for Randomized Smoothing in figure?
summary_of_the_review: The idea of degradation attacks on certifiably robust AE detection is novel. However, the experiment setting is a bit too simplified. I recommend the authors to strengthen the experiment part so that the severity of the threat is better motivated. I'm giving a marginally below acceptance for now, but I'm willing to increase the score once my concerns are addressed.

================================================================

After viewing the author response, I'm raising my score to 6. The technical aspect is sound, and the author explained a relatively intuitive concept in a reasonable manner. Thanks for the clarification.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper proposes a degradation attack on certifiable defenses GloRo and randomized smoothing aiming to find correct inputs within robustness region but hard to certify, causing rejections. The proposed attack is simple which is just a smoothed variance of PGD attack. Experimental results show that the two evaluated certification methods are susceptible to this attack.
main_review: Strength

1. Experimental results show that randomized smoothing and GloRo have degraded verified rates under the proposed attacks.
2. A customized defense is proposed and discussed.

Weakness

1. I doubt the practical usefulness of this degradation attack. In practice, verification is a plus for the model robustness evaluation. It is safe to trust the results if a sample is verified but a sample that cannot be verified does not necessarily mean we have to reject it. There are many other ways to measure the robustness and give confidence scores of the predictions. GloRo proposes to do the rejection mainly because they want to have global verified robustness with global Lipschitz constant but eventually it still serves for local robustness verification.
2. I do not think the example in figure 1 makes sense. When the ground-truth robustness region of x' is already crossing the decision boundary, it is truly an adversarial example. Rejection is indeed the correct thing to do for deterministic verification methods like GloRo unless we can retrain the weights to reshape the decision boundary. Please note that over cautiousness is the intrinsic property for certifiable defenses and should be the correct thing to have. The local verified robustness should only focus on the samples belonging to the original input distribution (x belongs to M) while the verified robustness around other samples like perturbed ones that out of the distribution (x' not belongs to M) should not be encouraged. Otherwise, it will become an unnecessarily too difficult problem unless global verified robustness is required.
3. The smoothed PGD attack has very limited novelty. A similar method is already proposed and also used for training to achieve better results over randomized smoothing alone. The attacks should at least discuss and evaluate over [A].
4. The proposed attack should really be discussed and evaluated with other SOTA complete verifiers like alpha-beta-CROWN [B, C] (the winner of neural network verification competition this year) or incomplete ones like CROWN [D] and K&W [E], and certifiable training methods like CROWN-IBP [F] and IBP [G].

[A] Provably Robust Deep Learning via Adversarially Trained Smoothed Classifiers, NeurIPS 2019

[B] Beta-CROWN: Efficient Bound Propagation with Per-neuron Split Constraints for Complete and Incomplete Neural Network Verification, NeurIPS 2021

[C] Fast and Complete: Enabling Complete Neural Network Verification with Rapid and Massively Parallel Incomplete Verifiers, ICLR 2021

[D] Efficient Neural Network Robustness Certification with General Activation Functions, NeurIPS 2018

[E] Provable defenses against adversarial examples via the convex outer adversarial polytope, ICML 2018

[F] Towards Stable and Efficient Training of Verifiably Robust Neural Networks, ICLR 2020

[G] On the Effectiveness of Interval Bound Propagation for Training Verifiably Robust Model, ICCV 2019
summary_of_the_review: I recommend rejection due to lack of novelty and comprehensive evaluations over SOTA verification methods. Also, I am not very convinced by the motivation of the proposed methods.

=== Post Rebuttal ===
Thank the authors for the extensive discussions. Some of my concerns have been clarified in the discussion and the revised submission. Some insights of the paper are quite interesting. However, I am still concerned about the novelty and SOTA evaluation of the proposed methods. Overall, I decided to increase my score to 5.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper presents a new line of attack, so-called degradation attacks, targeting the certified robustness of a model rather than directly targeting the classifier. They argue that in the case of certified robustness, a suitable norm-bounded adversary cannot change the classification of an input at which the output is robust, but can force the rejection of that input as potentially adversarial, thus degrading the utility of the system.
main_review: The presentation of the paper was generally clear and well laid out.

However, there are potentially some issues, though I may have misunderstood and would welcome the authors’ responses to the comments below.

There is a statement (section 5) “we focus on certified runtime defences that are deployed during model evaluation and are guaranteed to detect adversarial examples”. I would contend that certifiable robustness processes are usually such that the certified robustness (CR) check (for radius epsilon) passing at x implies the classifier is epsilon-robust at x. But the converse is not necessarily true – as evidenced by the fact that different certified robustness approaches perform differently. Failure of the CR check at radius epsilon I am not sure guarantees the presence of an adversarial point in the epsilon ball. It simply means that there wasn’t appropriate evidence to guarantee there is no such point.

Given this, in section 3.2.2, it is stated that if a point x is 2*epsilon-robust, then every point within the epsilon ball around x is epsilon robust. This is true. But it is then said that “and so (the classifier) cannot be forced to unnecessarily reject the input”.  I am not sure of the latter statement, since (as argued above) the CR check may fail at that point, but that does not mean it is not epsilon robust at that point.

Similarly, the statement in 3.2.2 that “if the 2*epsilon CR check fails at x, then even though the model is epsilon robust at x, there exists an x’ in the epsilon ball at x where the model is not epsilon-robust” (paraphrasing a bit). But I would contend that failure of the 2*epsilon CR check does NOT mean that there is an adversarial example in the larger ball. It could still be 2*epsilon robust (and fail the check), and hence the paper’s conclusion is not true. 

In the same vein, I have problems therefore in section 3.3.1 in say defining test_R. How do we determine the set of points on which the model is epsilon robust (according to Definition 2). We can find the set of points on which it is certified robust by our check, but this will presumably miss points at which the test fails even though it is robust. Is it this certified robust set instead which is meant here to be test_R? Also, if this is the case, this is not really establishing “A lower bound on attack efficacy” – it is actually evaluating the efficacy of the given attack. This establishes a lower bound on the fraction of test points which are vulnerable to degradation attacks. Other degradation attacks may fare worse. Hence I question the wording of the title of this section and the way it is presented.

Regardless of the above discussion re the correctness of the approach, I have an issue with the phrasing of the basic claims of the paper. It is claimed (rightly) that an input point may be perturbed within the epsilon ball and no longer pass the robustness check, even though the original point did. So the perturbed point is then flagged as not-certifiable. It might be arguing semantics, but the system is really I would contend not flagging adversarial points, but just indicating if a given point is certifiably robust. In this case (the attack), it no longer is certifiably robust, and the system indicates this. The statement (section 5) that the system can “flag even non-adversarial inputs as adversarial” I feel then is a bit of a misrepresentation of what it is doing (And to call these perturbed points non-adversarial inputs also is a bit disingenuous. They are constructed to mislead the system and so, in any reasonable sense, are adversarial).

Also, some discussion in the paper I believe is warranted to address the fact that certified robustness is typically (e.g. in the case of Cohen et al) probabilistic, i.e. up to a certain confidence level (ignored also in the above arguments).

In the experiments, I think some comparison to say PGD would be valuable, i.e. investigate how successful (accidentally!) PGD (in an epsilon ball NOT 2* epsilon) is at finding degradation attacks at robust points. PGD will fail to find an adversarial example at such points of course, but checking whether the (failed) attack point is still certified robust would be an interesting measure to see how more efficient at finding such points the algorithms proposed in the paper are. Further, one could consider for the other points in the test set, how effective the proposed algorithms are at finding adversarial examples compared to vanilla PGD. i.e. do the proposed algorithms degrade efficacy of an adversarial attack on non-robust points?

Some minor comments:
-	It is worth noting that Cohen et al, for example, evaluates the arg max (label) for each noise-perturbed input, and then the counts of different classes go into the evaluation. Instead, in Algorithm 3.2 (line 5), it takes the average of the logits for each input in evaluating the loss. This approach to constructing the smoothed classifier is more akin to the approach of Lecuyer et al. Not necessarily an issue – as I am not sure that there would be a direct analog of the Cohen approach in determining the gradient. But worth highlighting.
-	There is a slight abuse of notation in lines 4 and 5 of Algorithm 3.2. The decomposition of the noise vectors into n d dimensional vectors is obvious, but not explicitly stated in the definition
-	When it is stated in 3.3.1 that “assuming there exists no other point in M, except x, that is epsilon-close to x’” presumably this should say “.. point of a different class label ...” 
-	It would be good to show both lower and upper bounds on the same graphs (fig 2) so as to visually show how tight (or otherwise) they are
-	Is it not the case that the defense 4.2 is not really practical as membership of M is not really computable typically.

summary_of_the_review: Though the idea of the paper is interesting, and the basic attack techniques proposed seem effective, I had, besides some more semantic issues, some concerns with the correctness of the argument of the paper with respect to the upper bound determination. This means that I cannot accept the paper in its current form (unless of course the authors correct any misunderstanding on my behalf – which is very possible). 

Edit: The author revisions have addressed some of the main issues with the upper bound determination (including a discussion of monotonicity). Interestingly, the inclusion of the PGD attacks in the supplementary materials, as per my suggestion, seems to perform about as effectively as the proposed algorithms in the main paper. Given the improvements, I have increased my rating to reflect that and the fact that the underlying idea is interesting.
review_title: null

Meta-review: The work focuses on the observation that, given a certified epsilon-robust model and a certified clean input x, many inputs within the epsilon ball around x are themselves not epsilon-certifiable although they are correctly classified. The authors argue that an adversary can exploit this property to produce inputs which are correctly classified by the model yet are not certifiably robust. Reviewers agreed that the paper was overall well written, the methods were clear and overall evaluated thoroughly, and many felt that the main idea was interesting. There were some concerns regarding the significance of the contribution, the primary observation itself is arguably novel but somewhat obvious, and the proposed algorithm for finding non-certifiable points isn't a significant contribution when standard techniques like PGD are sufficient. Much of the reviewer discussion concerned whether or not the proposed attack made sense as a threat model. It is the AC's opinion that this discussion did not reach any meaningful conclusions. It is important to remember that the lp threat model is intended as an abstract toy game so that a formal theory of neural network certification can be developed under idealized settings. It is not intended to model any realistic security scenarios, and even more generalized notions of "imperceptible" or "subtle" attacks aren't realistic when for the bulk of applied settings real adversaries are not restricted to small perturbations in the first place [1]. The example provided by the authors regarding small perturbations of a stop sign isn't a relevant example when the adversary has more effective options, e.g. knocking over stop signs [1, Figure 3]. 

For the sake of discussion, one could consider whether or not a degradation attack would make sense under more general threat models such as content-preserving perturbations. An example discussed in [1] concerns adversaries uploading copyrighted content to public streaming services—this attacker defender game is being actively played in the wild where defenders produce statistical models which attempt to flag content as semantically matching existing copyrighted content in a private database, while attackers make large semantically-preserving modifications in order to evade statistical detection. An example attack would be cropping 20% of the boundary pixels of a movie and replacing the cropped portion with arbitrary adversarially constructed backgrounds. Epsilon perturbations are possible, but are almost a measure 0 subset of the full attacker action space. Suppose in the far future neural network certification advanced to the point where we could certify that a classifier was robust to all possible content-preserving perturbations of a specific movie. In this case the defender would be using the certification method on their private database of copyrighted content, they would not be running the certifier on any content uploaded by users. If a movie in the private database is certified, then we already know that an attacker cannot successfully upload an adversarial version of it, it would be unnecessary to certify whether or not user uploaded content could be further perturbed in a way to become adversarial. Perhaps degradation attacks could be possible as a training poisoning attack, but this seems a bit far-fetched when more traditional training poisoning attacks would be preferred. Given this, at least in this example the AC does not see how a degradation attack would make sense as a threat model. 

Given that the primary contribution of this work is a novel threat model for ML security, it is crucial that the authors rewrite their work to make more realistic assumptions of the capabilities of realistic adversaries. Starting with some of the examples discussed in [1] may be useful to the authors. Although the example of adversarial attacks on copyright detection classifiers doesn't seem to fit the degradation attack threat model, perhaps other scenarios would.

1. Gilmer et. al, Motivating the Rules of the Game for Adversarial Example Research, https://arxiv.org/pdf/1807.06732.pdf
Decision: Reject