Getting a-Round Guarantees: Floating-Point Attacks on Certified Robustness

$\mathbf{Weakness}$

$\mathbf{Ans.1}$ ReluPGD is only half of our attack (in the case of ReLU nets), and it can be replaced by any standard approach to finding directions for adversarial perturbations. As the name was already suggesting, ReluPGD is indeed an instantiation of PGD. However we acknowledge that we can better highlight this (obvious) connection. Our inclusion of ReluPGD (Algorithms 1 and 2), derived by hand, was to emphasize that it is exact for a local linearization. The choice of ReLU network was two-fold: (1) it is an important architecture in practice (2) it permits strong attacks. ReluPGD is intended to transparently highlight this second point. Hand derivation is by no means an interesting contribution, which is why the details are relegated to the appendix. The second part of our attack (Algorithm 3) is where we innovate by leveraging the structure of certificates to isolate floating-point rounding problems. This simple configuration of the step size is enough to demonstrate violations of certification guarantees.

$\mathbf{Ans.2}$ Thank you for listing these works. We will add them to the paper. Singh et al. (2018 and 2019) also use interval arithmetic in neural network certification, and are sound w.r.t. floating-point arithmetic. However, Singh et al. (2018 and 2019) use the $\ell_{\inf}$ metric in neural network certification, which avoids the influence of potential rounding errors in the calculation of the perturbation norm. We use the $\ell_2$ metric, and handle the impact of rounding errors in the calculation of the perturbation norm for certification in the strong threat model.

Voráček and Hein (2022) attacked randomized smoothing by also exploiting the finite representation of floating points. However, they attacked synthetic data and model, while we show attacks on unperturbed networks and test-set images.

$\mathbf{Ans.3}$ For random linear classifiers in Section 4.1, we use both 32-bit and 64-bit floating-point precision, as shown in Fig 2(a). For Linear SVM, we use 64-bit floating-point precision. For neural nets, we use 32-bit floating-point precision. Gurobi tolerance is $2\times10^{-5}$.

$\mathbf{Ans.4}$ In the strong threat model, we used the upper bound of the perturbation norm $\overline{\|\boldsymbol{\delta}\|}$, not the real norm $\Delta$. The difference between the weak ($\tilde{R}-\|\boldsymbol{\delta}\|$) and strong ($\tilde{R}-\overline{\|\boldsymbol{\delta}\|}$) models is not the floating-point soundness of the norm computation. It can be the floating-point soundness of the norm computation if we attack ($\tilde{R}-\Delta$) in the strong threat model instead.

$\mathbf{Ans.5}$ For MILP, we verify two 3-layer neural network multiclass classifiers with 100 nodes in their hidden layer, one of them is trained normally, whose parameters (weights and biases) can be negtive. For Randomized Smoothing, we also attack a 3-layer network with negtive parameters. The verification from MILP could potentially be conservative, and the verification from Randomized Smoothing should mostly be conservative.

$\mathbf{Questions}$

$\mathbf{Ans.1}$ Please refer to the answer of W.1.

$\mathbf{Ans.2}$ We want to show how big rounding errors could potentially be in Figure 2b. In the paper, we do state that the rounding errors exploited by our attack are small. Please see the second paragraph of Section 5: “For example, the rounding error for the certified radius of the first MNIST image of Figure 3 (Appendix A) is in the 13th decimal place”.

$\mathbf{Ans.3}$ In the strong threat model, we use the upper bound of the perturbation norm $\overline{\|\boldsymbol{\delta}\|}$ estimated with interval arithmetic. With increasing dimension, more operations are involved, interval arithmetic gets more uncertain (loose) about its estimation, and outputs a bigger interval that contains the real result. That is, the upper bound $\overline{\|\boldsymbol{\delta}\|}$ gets bigger (estimated more loosely).

In all, with increasing dimension, $\tilde{R}$ gets bigger, but $\overline{\|\boldsymbol{\delta}\|}$ also gets bigger. Hence, the leeway $\tilde{R}-\overline{\|\boldsymbol{\delta}\|}$ exploited by our attack in strong models first gets bigger ($D\le18$) and then gets smaller ($19\le D\le100$), and our success rate first increases then decreases.

$\mathbf{Ans.4}$ Please refer to the answer of W.3.

$\mathbf{Ans.5}$ Please refer to the answer of W.5.

$\mathbf{Ans.6}$ Our mitigation introduces theoretically enough conservativeness (i.e., $\gamma = \tilde{R} - \underline{R}$) by providing $\underline{R}$ as a robustness certificate. $\underline{R}$ is safe in the strong threat model. In the weak threat model, this $\gamma$ will not have same provable guarantees. We will clarify this.

$\mathbf{Ans.1}$ The reviewer is right that it is well-known that flaws are known in regards to finite-precision arithmetic. However, this observation was neither made before against exact certification mechanisms nor shown to work against conservative mechanisms. Our work has demonstrated robustness violations against a wide range of certifications on unperturbed networks and test-set images, and reminds practitioners that if certified robustness is to be used for security-critical applications, their guarantees and implementations need to account for limitations of modern computing architecture.

$\mathbf{Ans.2}$ We introduced the idea of a radius correction $\tilde{R}-\gamma$ as a straw argument: it is meant to be flawed. We hope the reviewers and AC understand that non-zero attack success rate is not acceptable. This is because such a mechanism (with constant $\gamma$) would not be sound and introduce uncontrolled errors. We showed in Section 5 that we can still find violations if we set certificate as $\tilde{R}-0.1$.

The reviewer asks if there is a principled way to find $\gamma$. The only approach known to us is input dependent (non-constant) $\gamma = \tilde{R} - \underline{R}$, such that $\tilde{R}-\gamma = \underline{R}$, where $\underline{R}$ is the lower bound of the certified radius estimated with interval arithmetic, and we propose to use it in our mitigation as the certificate.

$\mathbf{Ans.3}$ We avoid exponential runtime by adopting random sampling in the neighboring search algorithm as follows. We randomly sample $N$ floating-point neighbors of the adversarial instance $\mathbf{x'}$ to explore robustness violations close to the decision boundary due to rounding errors. For example, $N$ is 5000 in Section 4.2.

$\mathbf{Ans.4}$ ReluPGD is only half of our attack (in the case of ReLU nets), and it can be replaced by any standard approach to find directions for adversarial perturbations. As the name was already suggesting, ReluPGD is indeed an instantiation of PGD. Our inclusion of ReluPGD (Algorithms 1 and 2), derived by hand, was to emphasize that it is exact for a local linearization. The choice of ReLU network was two-fold: (1) it is an important architecture in practice (2) it permits strong attacks. ReluPGD is intended to transparently highlight the second point. Hand derivation is by no means an interesting contribution, which is why the details are relegated to the appendix.

There maybe confusion from Reviewer s866 on where our contribution lies (i.e., it is not a new general-purpose PGD algorithm). For example the second part of our attack (Algorithm 3) is where we innovate by leveraging the structure of certificates to isolate floating-point rounding problems. This simple configuration of the step size is enough to demonstrate violations of certification guarantees.

$\mathbf{Ans.5}$ Verification methods such as $\beta$-CROWN and MIP tend to give tighter estimates of robustness certificates for smaller neural nets. That is, those methods can verify a relatively bigger (tighter) $\tilde{R}$ for a small model, which results in a bigger leeway $\tilde{R}-R$ for our attack to exploit and allows higher attack success rates. We experiment with small neural nets that are normally trained and have 100 neurons in the hidden layer on the real MNIST dataset in Section 4.3, and show that even if the robustness certificates are potentially conservative, we can still find violations for those that are relatively tight, although not exact. For larger neural nets, the certificates could be more conservative, but larger neural nets (more operations) could also entail larger rounding errors, so a successful attack is still possible. Moreover, our attack exploits subtle floating-point errors, as we explained in the second paragraph of Section 5: For example, the rounding error for the certified radius of the first MNIST image of Figure 3 (Appendix A) is in the 13th decimal place.

The purpose of our work is to show that certifications can be attacked. The fact that all the certification mechanisms we examined are unsound should be of serious concern. There is nothing to indicate that higher levels of rounding (and hence rounding attacks) wouldn't be possible in other datasets, or domains. Without sound mechanisms, one cannot trust implementations to perform as advertised.

$\mathbf{Ans.6}$ For the library, we refer to the library that computes the square root for the norm and represents it as an interval, i.e., PyInterval in our study. For Fig 2, we experiment with models of different dimensions, with $D$ ranging from 1 to 100, as we want to explore how the dimension influences our attack. One dot in Fig 2 stands for an experiment on a model of a certain dimension (e.g., $D=50$).

$\mathbf{Ans.1}$ Verification methods such as $\beta$-CROWN and MIP tend to give tighter estimates of robustness certificates for smaller and simple neural nets. That is, those methods can verify a relatively bigger (tighter) $\tilde{R}$ for a small model, which results in a bigger leeway $\tilde{R}-R$ for our attack to exploit and allows higher attack success rates. For larger neural nets, the certificates could be more conservative, but larger neural nets (more operations) could also entail larger rounding errors. We thank the reviewer for this suggestion. We hope that any violations of the intended certificate by a mechanism on any sized network would demonstrate the issue to researchers in the area. We hope that before future deployments researchers communicate potential implementation flaws to end users, or adopt mitigations like those proposed here.

$\mathbf{Ans.2}$ Though in theory the attacks should still hold, attacking MinMax models and Lipschitz-based certificates in practice is an interesting direction for future work. We chose ReLU nets owing to it being (1) used frequently in practice (2) being readily linearizable, with the intention of simply demonstrating a range of certificate violations.

Our current limitations were summarised in the submission in Appendix G (being in the supplemental it may have been missed). We identify the following limitations, that could also be addressed as future work. First, our attacks against randomized smoothing do not study the relationship between the attack success rate and the soundness probability of these methods due to their probabilistic nature. A possible future direction would be to study how the two interact. Second, we showed how to adopt our mitigation based on interval arithmetic generally, and demonstrate this mitigation for linear models and exact certifications. Detailed exploration of embedding these mitigations in other verifiers and models is left as future work.

$\mathbf{Ans.1}$ We introduced the idea of a radius correction $\tilde{R}-\gamma$ as a straw argument: it is meant to be flawed. While we understand that Reviewer FP18 is interested in attack success rates for small constant $\gamma$, we hope the reviewers and AC understand that non-zero attack success rate is not acceptable. This is because such a mechanism (with constant $\gamma$) would not be sound. We showed in Section 5 that we can still find violations if we set certificate as $\tilde{R}-0.1$; with increasing dimension there is increased opportunity for undesirable rounding.

Reviewer FP18 highlights the probabilistic nature of certificates for Randomized Smoothing: while it is true that such mechanisms have a failure probability, this probability is still controlled and only accounts for sampling error in the Monte Carlo estimates made by Randomized Smoothing. Any non-zero failure rate due to rounding (which is inevitable with constant $\gamma$) represents a greater failure rate, that is no longer controlled in any way. Moreover, for the vast literature on deterministic certificates, the goal is a consistent prohibition of adversarial examples. Our proposed mitigation (based on interval arithmetic) uses $\underline{R}$ as a robustness certificate. This can be understood as a principled way to choose an input-dependent (non-constant) $\gamma = \tilde{R} - \underline{R}$, such that $\tilde{R}-\gamma = \underline{R}$. Hence, interval arithmetic provides a sound approach with a provable attack success rate of zero.

$\mathbf{Ans.2}$ We report experiments on representative certification mechanisms of the Exact, Conservative and Randomized types. For the latter two types we used some of the seminal works. For example, MIP certification used for neural networks in Section 4.3 is known for its tight estimate for robustness certificates, although its slow running speed on big models is a problem. Nevertheless, our MIP certifications on small neural networks give tight estimates for robustness certificates with acceptable runtime, and allow our attack to have high success rates. Though it is interesting to see our methods against all certification methods, our contribution is against the fundamental observation that theoretical (real arithmetic based) radius does not match the one computed in practice.