The Certification Paradox: Certifications Admit Better Evasion Attacks

We thank the reviewer for their time.

We'd like to begin by addressing the point of significance: the existence of attacks outside the certified radius is a well understood property of certifications - certifications are, by their nature, conservative, and only have access to local information. Our contribution is to demonstrate that if the certification is released alongside the prediction, then this additional information can be exploited by an attacker to more efficiently construct adversarial examples, that are reliably smaller than attacks that don't consider this information. This is a property that has not been discussed in any certification literature to date, and represents a risk to the very kind of security conscious models that certification schemes attempt to defend.

As to the commentary regarding that "a slightly larger perturbation size can still be an imperceptible attack" - yes, but the average attack size is a strong proxy to how detectable attacks are to human or machine detection - a property well established by Gilmer (and as cited within our paper). We believe that these metrics are more representative and fair for presenting how detectable adversarial examples against a model may be, relative to cherry picked visualisations of a small proportion of samples - especially when these visualisations would only be useful for considering how a human would view the perturbations, and not how automated systems might consider them.

On the topic of clarity: all the details regarding the figures are discussed within the figure labels, and additional labelling on the figures themselves would require a commensurate decrease in the size of the figures to account for these details. We feel that the figure labels sufficiently detail these points. We would, however, be happy to bold the best-performing elements in Table 2.

To address the questions raised in order:

1. Yes, the percentage difference between the attack and the corresponding certification guarantee of the original sample point is calculable as %-C = Mean( 100 * (||x' - x_0|| - C(x_0)) / C(x_0) ), where x' is the identified adversarial example, x_0 is the original sample, C(x_0) is the certification for the original sample, and || . || is the L2 norm (ie. the attack radii).
2. "Best" is the proportion of attacked samples for which an attack produces the smallest adversarial example. So Mean( r_i <= max(r_j for all j != i) ), where r_i represents the attack radius of a given technique.
3. As with our technique, the projection step is strictly limited to a projection into the feasible space for input samples.

We'd just like to take the opportunity to point out that we have submitted a rebuttal revision that we hope has addressed your issues and concerns. Specifically, we have revised the table caption for Table 2; have bolded the best-performing metrics within Table 2; have introduced Appendix D which explains each of the metrics used; and have updated Figure 3 to improve the accessibility of the figure.

In light of your view of this work as being interesting, novel, and with sufficient experimentation, we would hope that our demonstrated commitment to resolving the issues raised within your review would elicit reconsideration of your rating. We would also welcome the opportunity to further discuss any issues that you may still hold.

Thanks again.

As is discussed within the paper, both our attack and all the reference attacks are being deployed acting upon the certified model, not the base classifier. So the total time for each attack covers (# of attack steps before stopping) * ([Time to certify] + [Time to attack the certified model])

Ok, then it is unclear to me how is this a fair comparison to PGD. Let us consider a (simplified) smoothed classifier $g_\sigma(x) = E_{v \sim N(0, \sigma)} f(x + v)$ produced by Randomized Smoothing. Say to evaluate $g_\sigma$, one uses $n_1$ samples from the gaussian, whereas to obtain a certificate for $g_\sigma$, one uses $n_2$ samples (in reality this is $C + n_2$ samples, because of statistical considerations see Cohen et. al. PREDICT vs CERTIFY). Since PGD's goal is to simply attack $g_\sigma$, one can get away with $n_1 \ll n_2$ - in other words, for simply finding an attack, one doesn't need to have a huge number of samples that is needed to actually compute the certificate (in fact $n_2$ is in practice huge for ImageNet-sized images). If $n_1$ is being set equal to $n_2$ as the authors suggest (which might approximately produce an equal time per inference step, even then it is unclear what happens to the additional $C$) then it seems that PGD is unnecessarily being penalized in time for computing a certificate at each step that is then thrown away. Using $n_1$ smaller than $n_2$ might show a tradeoff between time and adversarial attack strength for PGD, but I suspect the time falls much faster than the attack strength.

To the above point of trade-off, see the discussion of $m_{\rm train}$ in Section 3, [A] where essentially the same issue is encountered: practically one can use a small $n_1$ to obtain adversarial examples against $g_\sigma$.

[A]: Salman, Hadi, et al. "Provably robust deep learning via adversarially trained smoothed classifiers." Advances in Neural Information Processing Systems 32 (2019).

We thank the reviewer for their time and consideration.

To address your points in order

1. With our baselines, we endeavoured to consider a representative set of attacks used within the literature. While there will always be more attacks that could be tested, we felt that this set served as an appropriate baseline for exploring the conceptual advantages that incorporating certification information within a PGD-style attack could bring. That FAB is included within AutoAttack left us confident that if AutoAttack was not producing a level of out performance that would justify a larger parameter exploration (given that it required an one-to-two orders of magnitude more computational time than other reference attacks), that a similar exploration with FAB would not yield beneficial results.

We also would stress that our attack framework is a modification to PGD, but it is a modification that could similarly be applied to any other attack framework. As such, the information advantage gained by our attack approach should be most directly compared to PGD, and that the other tested attacks reinforce that our results are not an artefact of choosing to compare against PGD only.

2. All attacks - both ours, PGD, and C-W - could be embedded inside an optimisation regime that could improve their performance. However in doing so it would be incredibly difficult to assess the relative performance of the techniques in terms of their computational requirements. Moreover, doing so would remove our capacity to understand how choices in the parameter space influence the inherent trade-off between success rate and attack sizes (see the discussion around Figure 2).
3. As is discussed within the paper, both our attack and all the reference attacks are being deployed acting upon the certified model, not the base classifier. So the total time for each attack covers (# of attack steps before stopping) * ([Time to certify] + [Time to attack the certified model]). This is the case not just for our certification aware attack, but for all attacks, as we are specifically interested in the performance of adversarial attacks against models for which the certification is a core component.

As to the minor points raised

1. The paradox of the title relates not to the ability of finding minimal adversarial examples, but rather that a mechanism associated with improving model robustness can release information that makes the very models it is seeking to defend easier to attack. This is a surprising and paradoxical result, and as such we feel the title is justified upon those grounds.
2. The P in B_P is the 2, as this is the only norm for which Cohen applies. This will be clarified in updates to the paper.

With regards to table 2, as discussed above the time to attack is consistent, as all models are attacking the same certified model. To the other metrics, the success rates are a broadly controlled parameter (see Appendix C, set at ~90%); Best is the proportion of successfully attacked samples for which an attack produces a smaller attack than any other tested attack; the $r_{50}$ is the median attack radius; %-C is the mean percentage difference between the attack radius and the size of the certified guarantee at the original point - which is used in an attempt to normalise against the difficulty of constructing an adversarial example. For a controlled success rate, our technique reliably produces adversarial attacks that are consistently smaller than any of the other tested attacks, even when we consider this relative to the size of the certified guarantees. It does this while requiring less time than any other attack besides DeepFool - an attack that is barely ever able to produce a smaller adversarial attack than any other technique.

We thank the reviewer for their time and consideration, and appreciate that they found our work interesting, valid, and clear.

We would, however, disagree with the contention that our paper is impractical - it requires no additional steps beyond what those would be required to apply any adversarial attack against a model employing randomised smoothing (or indeed, any other certification mechanism), and in doing so we are able to demonstrate that any certified model that releases its certifications is inherently providing an attacker with information that can be exploited to better help them craft minimal norm adversarial examples. That this is possible is important, as the size of constructed certifications is often significantly smaller than the smallest adversarial example that exists (see Figure 3), and these samples are often small enough to evade both human and machine detection.

We would, however, be happy to add additional detail regarding symbols. From the other reviews it would appear that our metrics "%-C" and Best would be enhanced by providing the mathematical explanations (rather than the current written explanations), and we will add these to the paper.

Thanks again.

We'd just like to call attention to our recently uploaded rebuttal revision, which among other changes has introduced Appendix D, which we have used to help define some of the symbols that other reviewers have raised as being potentially ambiguous.

Thanks again for your consideration.

We thank the reviewer for their consideration.

We'd like to begin by addressing the claims the reviewer in the fourth paragraph of their summary. We emphasise that our paper does not produce a certification algorithm. As stated in the abstract, we explore "the heretofore unexplored risks inherent in releasing certifications" by exploiting the fact that the release of a certification gives an attack additional information that they can exploit to find the adversarial examples that must exist outside the regions of certification. The risks associated with stronger certification mechanisms is that they provide more relevant information about where adversarial examples cannot be, which in turn would increase the risk to the certified model being exploited following our algorithm.

We are confused as to statements like "this paper does not reduce the provable security guarantees provided by certified models, despite its misleading claims" - we make no claim of breaking the provable guarantees of certified models. These certifications provide tight guarantees on where adversarial examples cannot exist, but they do not provide a tight bounding on where adversarial examples do exist - and this difference is significant (Figure 3). Certified defences are still vulnerable to attack, and the size of certificates of robustness are often not large enough to eliminate the potential of difficult to detect adversarial examples.

We are also curious as to which claims the reviewer finds to be misleading? This is a strong statement that we would happily rebut. Our paper consistently and clearly states that releasing certifications allows for an attacker to exploit the certifications to identify minimal norm adversarial attacks outside the radius of certification. None of this point relates to breaking the guarantees of certified robustness.

To address the weakness relating to success rates - Figure 2 demonstrates that there is an inherent tradeoff between success rates and the size of the identified adversarial examples, and that our technique outperforms all other techniques when considereding this tradeoff (see Figure 2). The Table 2 data that the reviewer is referring to on this point must be considered in context of Figure 2 and Appendix C, where we discuss that the points in parameter space for Table 2 were chosen so that each technique produced a success rate of 90% if possible. This also relates to the third identified weakness. While parameter sweeps like those used for our attack, C-W, and PGD would also be possible for AutoAttack, we emphasise that AutoAttack required an order of magnitude more time than any other attack for MNIST and C-W - so performing this kind of parameter exploration would have been prohibitively expensive and unrealistic for any attacker.

As to the second weakness, that "many samples are used to estimate E_0 and E_1 during the attack" - we reiterate the point made within the paper that each attack (be it ours, PGW, C-W, etc.) is applied to the smoothed variants of the models outputs - so after E_0 and E_1 have been estimated. Each reference attack is applied to the exact same output, the only difference is that our attack also takes into account the size of the robustness certificate at the same time.

Finally - we do use the L2 variant of PGD.

To cover the questions in order:

1. Against MACER our technique exhibits almost identical step median radii, relative computational time, and the a similar ratio between the amount of samples it is able to certify and the amount of samples for which it is the best technique. The percentage distance to Cohen changes for all techniques because MACER is certifying a greater proportion of samples, but oftentimes those additional samples are so small that they distort the %-C metric for all attacks. With regards to the proportion able to be attacked - we believe that the settings from Table 3 may not be sufficient to account for the change in the distribution of certifications that MACER produces.
2. Yes, the exact same attack framework is applied - the region guaranteed to contain no adversarial examples is used to guide the step size for our certification aware attack.
3. No. %-C is the percentage difference to Cohen et. al.: %-C = Mean( 100 * (r(x', x0) - C(x0)) / C(x0) ), where r(x',x_0) is the distance between the adversarial and original samples and C(x0) is the certification for the original sample.
4. As no technique was able to reach the 90% success rate for Imagenet, so the parameter that maximised the success rate was chosen. This appeared to produce this interesting clustering for the samples that admitted small attacks, which we believe that this is a consequence of how the loss landscape behaves for randomised smoothed models - noting that this same behaviour is not visible for IBP, or any other dataset.

With the review period closing within a few days, we just wanted to take this opportunity to ask if this response had resolved any of your issues with the paper, and to offer our assistance in clarifying any additional points. We'd also note that we have edited the paper (specifically appendix D) to help address the questions regarding the metrics used within the paper.

Thanks in advance