Towards Assessment of Randomized Smoothing Mechanisms for Certifying Adversarial Robustness

The past decade has witnessed tremendous success of deep learning in handling various learning tasks like image classification [3], natural language processing [4], and game playing [5]. Nevertheless, a major unresolved issue of deep learning is its vulnerability to adversarial samples, which are almost indistinguishable from natural samples to humans but can mislead deep neural networks (DNNs) to make wrong predictions with high confidence [6, 7]. This phenomenon, referred to as adversarial attack, is considered to be one of the most significant threats to the deployment of many deep learning systems. Thus, a substantial amount of effort has been devoted to developing defensive techniques against it. However, a majority of existing defenses are of heuristic nature (i.e., without any theoretical guarantees), implying that they may be ineffective against stronger attacks. Recent work [8, 9, 10] has confirmed this concern by showing that most of those heuristic defenses actually fail to defend against strong adaptive attacks. This forces us to shift our attention to certifiable defenses as they can classify all the samples in a predefined neighborhood of the natural samples with a theoretically-guaranteed error bound. Among all the existing certifiable defensive techniques, randomized smoothing is becoming increasingly popular due to its scalability to large datasets and arbitrary networks. [1] first relates adversarial robustness to differential privacy, and proves that adding noise is a certifiable defense against adversarial examples. [2] connects adversarial robustness with the concept of Rényi divergence, and improves the estimate on the lower bounds of the robust radii. Recently, [11] successfully certifies $49\%$ accuracy on the original ImageNet dataset under adversarial perturbations with $\ell_{2}$ norm less than $0.5$.

Despite these successes, there are still several unanswered questions regarding randomized (smoothing) mechanisms^***In this paper, “randomized mechanism” is an abbreviation for “randomized smoothing mechanism”.. One such question is, why should we use the Gaussian mechanism for randomized smoothing to certify $\ell_{2}$-norm robustness, or is there any more appropriate mechanism than the Gaussian mechanism? Another important question is regarding the ability of this method to certify $\ell_{\infty}$-norm robustness. If randomized smoothing can certify $\ell_{\infty}$-norm robustness, what mechanism is an appropriate choice? All these questions motivate us to develop a framework to assess the appropriateness of a randomized mechanism for certifying $\ell_{p}$-norm robustness.

In this paper, we take a promising step towards answering the above questions by proposing a generic and self-contained framework, which applies to different norms and connects the existing frameworks in [1, 2], for assessing randomized mechanisms. Our framework employs the Maximal Relative Rényi (MR) divergence as the probability distance measurement, and thus, the definition of robustness under this measurement is referred to as $D_{MR}$ robustness. Under our framework, we define the magnitude (i.e., the expected $\ell_{\infty}$-norm) of the noise required by a mechanism to certify a certain extent of robustness as the metric for assessing the appropriateness of this mechanism. To be specific, a more “appropriate” randomized mechanism under this definition refers to a mechanism that can certify a certain extent of robustness with “less” additive noise. Given this definition, it is natural to define the assessment criteria as the lower bounds on the magnitude of the noise required to certify $\ell_{p}$-norm ($D_{MR}$) robustness, in that we can judge whether a mechanism is an appropriate option based on the gap between the magnitude of noise needed by the mechanism and the lower bounds.

Inspired by the theory regarding the lower bounds on the sample complexity to estimate one-way marginals in differential privacy, we prove lower bounds on the magnitude of additive noise required by any randomized smoothing mechanism to certify $\ell_{2}$-norm and $\ell_{\infty}$-norm $D_{MR}$ robustness. We demonstrate the gap between the magnitude of Gaussian noise required by the Gaussian mechanism and the lower bounds is only $O(\sqrt{\log d})$ for both $\ell_{2}$-norm and $\ell_{\infty}$-norm, where $d$ is the dimensionality of the data. Note that this gap is small for datasets like CIFAR-10 and ImageNet, which indicates that the Gaussian mechanism is an appropriate option for certifying $\ell_{2}$-norm or $\ell_{\infty}$-norm robustness. Moreover, we also show that the Exponential mechanism is not an appropriate option for certifying $\ell_{\infty}$-norm robustness since the gap scales in $O(\sqrt{d})$. To summarize, our contribution is four-fold:

• •

  We propose a generic and self-contained framework for assessing randomized mechanisms, which applies to different norms and connects the existing frameworks such as [1] and [2].

• •

  We define a metric for assessing randomized mechanisms, i.e., the magnitude of the additive noise to certify adversarial robustness, and we derive the lower bounds on the magnitude of the additive noise to certify $\ell_{2}$-norm and $\ell_{\infty}$-norm robustness as the criteria for the assessment. Also, we extend this assessment framework to $\ell_{p}$-norm for any $p\geq 2$ in Appendix, which indicates the curse of dimensionality on randomized smoothing for certifying $\ell_{p}$-norm ($p>2$) robustness.

• •

  We assess the Gaussian mechanism and the Exponential mechanism based on the metric and the lower bounds (i.e., the criteria). We conclude that the Gaussian mechanism is an appropriate option to certify $\ell_{2}$-norm and $\ell_{\infty}$-norm robustness, and the Exponential mechanism is not an appropriate option for certifying $\ell_{\infty}$-norm robustness here.

• •

  We conduct extensive evaluations to verify our theoretical findings on our framework (with the same certified robust radii as in [2]) and Cohen et al.’s framework [11].

Due to the space limit, all the omitted proofs and some experimental results are included in Appendix (in the supplementary material).

To our knowledge, there are mainly three approaches to certify adversarial robustness standing out. The first approach formulates the task of adversarial verification as an optimization problem and solves it by tools like convex relaxations and duality [12, 13, 14]. Given a convex set (usually an $\ell_{p}$ ball) as input, the second approach maintains an outer approximation of all the possible outputs at each layer by various techniques, such as interval bound propagation, hybrid zonotope, abstract interpretations, and etc. [15, 16, 17, 18, 19]. The third approach uses randomized smoothing to certify robustness, which is the main focus of this paper. Randomized smoothing for certifying robustness becomes increasingly popular due to its strong scalability to large datasets and arbitrary networks [1, 20, 11, 12, 21]. For this approach, [1] first proves that randomized smoothing can certify the $\ell_{2}$ and $\ell_{1}$-norm robustness using the differential privacy theory. [20] derives a tighter lower bound on the $\ell_{2}$-norm robust radius based on a lemma on Rényi divergence. [11] further obtains a tight guarantee on the $\ell_{2}$-norm robustness using the Neyman-Pearson lemma. [22] proposes a new framework based on f-divergence that applies to different measures. [21] combines [11] with adversarial training, and [23] extends the method in [11] to the top-k classification setting. We note that, compared with [11], the frameworks proposed in [1, 2] are more general. In the following, we briefly review the basic definitions and theorems in the frameworks of [1, 2], which helps us demonstrate the inherent connections between our framework and those two frameworks [1, 2].

In this section, we first introduce several basic definitions and notations. In general, we denote any randomized mechanism by $\mathcal{M}(\cdot)$, which outputs a random variable depending on the input. We represent any deterministic classifier that outputs a prediction label by $f(\cdot)$. A commonly-used randomized classifier can be constructed by $g(\cdot)=f(\mathcal{M}(\cdot))$. We denote a data sample and its label by $\operatorname{\mathbf{x}}$ and $y$, respectively. An $\ell_{p}$-norm ball centered at $\operatorname{\mathbf{x}}$ with radius $r$ is represented by $\mathbb{B}_{p}(\operatorname{\mathbf{x}},r)$. We say a data sample $\operatorname{\mathbf{x}}^{\prime}$ is in the $\mathbb{B}_{p}(\operatorname{\mathbf{x}},r)$ iff $\|\operatorname{\mathbf{x}}^{\prime}-\operatorname{\mathbf{x}}\|_{p}\leq r$. Next, we can detail the frameworks in [1] and [2], i.e., PixelDP and Rényi Divergence-based Bound.

In this section, we present a generic framework based on the Definition 2, 3, and 4, for assessing randomized mechanisms. According to Definition 3, our framework applies to different norms. Moreover, we show that our proposed framework connects the existing general frameworks in [1, 2] by Theorem 4.1 & 4.2. Also, we note that it is difficult to involve the framework in [11] since [11] restricts the additive noise of the randomized mechanism to be isotropic such as Gaussian noise, while in our framework, we do not need to specify the type of additive noise.

In this section, we first elaborate on how the Gaussian mechanism certifies $D_{MR}$ robustness, and then provide the lower bound on the magnitude of the additive noise required by any randomized mechanism ($\mathcal{M}(\operatorname{\mathbf{x}})=\operatorname{\mathbf{x}}+\operatorname{\mathbf{z}}$) to certify $\ell_{2}$-norm robustness. By comparing the magnitude of the additive noise required by the Gaussian mechanism with the lower bound, we conclude that the Gaussian mechanism is an appropriate option to certify $\ell_{2}$-norm robustness.

According to Theorem 4.2, if we substitute $\epsilon$ with $\frac{r^{2}}{2\sigma^{2}}$, $r$ can be given by $r^{2}\leq\sup_{\alpha>1}-\frac{2\sigma^{2}}{\alpha}\log{(1-p_{(1)}-p_{(2)}+2(\frac{1}{2}(p_{(1)}^{1-\alpha}+p_{(2)}^{1-\alpha}))^{\frac{1}{1-\alpha}})},$ which is same as the bound of the robust radii in [2] (Lemma 3). To provide a criterion for the assessment of randomized mechanisms in the $\ell_{2}$-norm case, we prove a lower bound on the magnitude of the additive noise $\operatorname{\mathbf{z}}$ required by any randomized mechanism $\mathcal{M}(\operatorname{\mathbf{x}})=\operatorname{\mathbf{x}}+\operatorname{\mathbf{z}}$ to ensure that $\mathcal{M}(\operatorname{\mathbf{x}})$ (as well as $f(\mathcal{M}(\operatorname{\mathbf{x}}))$) is $(r,D_{MR},\|\cdot\|_{2},\epsilon)$-robust. As mentioned in Section 4.3, if the magnitude of the additive Gaussian noise is close to the lower bound, then the Gaussian mechanism is considered as an appropriate option. The lower bound is given by the following theorem.

Note that proving this theorem on $\mathbb{R}^{d}$ is non-trivial, which is detailed in Appendix. Theorem 5.2 indicates that the magnitude (expected $\ell_{\infty}$-norm) of the additive noise should be at least $\Omega(\frac{r}{\sqrt{\epsilon}})$ to certify $(r,D_{MR},\|\cdot\|_{2},\epsilon)$-robustness. For the Gaussian mechanism, the expected $\ell_{\infty}$-norm of the additive noise is $O(\sigma\sqrt{\log d})$ according to [25], which is $O(\frac{r}{\sqrt{\epsilon}}\sqrt{\log d})$ to guarantee $(r,D_{MR},\|\cdot\|_{2},\epsilon)$-robustness, according to Theorem 5.1. This means the gap between the magnitude of the noise required by the Gaussian mechanism and the lower bound is bounded by $O(\sqrt{\log d})$.

Equivalently, if we fix the expected $\ell_{\infty}$-norm of the additive noise as $\alpha$, the radius $r$ that can be certified by any $(r,D_{MR},\|\cdot\|_{2},\epsilon)$-robust randomized mechanism is upper bounded by $O(\alpha\sqrt{\epsilon})$, according to Theorem 5.2. For the Gaussian mechanism, since $\alpha=O(\sigma\sqrt{\log d})$, the certified robust radius $r$ is $O(\frac{\alpha\sqrt{\epsilon}}{\sqrt{\log d}})$^§§§The theoretical results of the scales of the robust radii are verified by experiments., according to Theorem 5.1. This means the gap between the upper bound of the robust radius and the radius certified by the Gaussian mechanism is also $O(\sqrt{\log d})$.

In this section, we first discuss the possibility of using the Exponential mechanism, an analogue of the Gaussian mechanism in the $\ell_{\infty}$-norm case, to certify $\ell_{\infty}$-norm robustness. Then, we prove the lower bound on the magnitude of the additive noise required by any randomized mechanism to certify $\ell_{\infty}$-norm robustness. By comparing the magnitude of the noise required by the Exponential mechanism with the lower bound, we conclude that the Exponential mechanism is not an appropriate option to certify $\ell_{\infty}$-norm robustness. Surprisingly, we find that the Gaussian mechanism is a more appropriate option than the Exponential mechanism to certify $\ell_{\infty}$-norm robustness.

We first recall the form of the density function of Gaussian noise: $p(\operatorname{\mathbf{z}})\propto\exp(-\frac{\|\operatorname{\mathbf{z}}\|_{2}^{2}}{\sigma^{2}})$. Based on this, we conjecture that, to certify $\ell_{\infty}$-norm robustness, we can sample the noise using the Exponential mechanism, an analogue of the Gaussian mechanism in the $\ell_{\infty}$-norm case:

We show in the following theorem that randomized smoothing using the Exponential mechanism can certify $(r,D_{MR},\|\cdot\|_{\infty},\frac{r^{2}}{2\sigma^{2}})$-robustness, which is seemingly an extension of the $\ell_{2}$-norm case. However, its required magnitude of noise is $O(d)$, which implies it is unscalable to high-dimensional data, i.e., The Exponential mechanism should not be an appropriate mechanism to certify $\ell_{\infty}$-norm robustness. This conclusion is further verified by our assessment method, which will be detailed later.

According to Theorem 4.2, if we substitute $\epsilon$ with $\frac{r}{\sigma}$ or $\frac{r^{2}}{2\sigma^{2}}$, then $r$ can be given by $r\leq\sup_{\alpha>1}-\frac{\sigma}{\alpha}\log{(1-p_{(1)}-p_{(2)}+2(\frac{1}{2}(p_{(1)}^{1-\alpha}+p_{(2)}^{1-\alpha}))^{\frac{1}{1-\alpha}})},$ or $r^{2}\leq\sup_{\alpha>1}-\frac{2\sigma^{2}}{\alpha}\log(1-p_{(1)}-p_{(2)}+2(\frac{1}{2}(p_{(1)}^{1-\alpha}+p_{(2)}^{1-\alpha}))^{\frac{1}{1-\alpha}}).$ Comparing this result and Theorem 5.1, we can see that randomized smoothing via the Exponential mechanism certifies a similar form of the radius as that certified by the Gaussian mechanism in the $\ell_{2}$-norm case, indicating similarity in their robustness guarantees. However, the following corollary shows that the magnitude of the noise required by the Exponential mechanism is much larger than that of the Gaussian mechanism in the $\ell_{2}$-norm case.

Equivalently, if we fix the expected $\ell_{\infty}$-norm of the additive noise as $\alpha$, according to Theorem 6.1 & Corollary 2, the robust radius $r$ certified by the Exponential mechanism is $\max\{O(\frac{\alpha\epsilon}{d}),O(\frac{\alpha\sqrt{\epsilon}}{d})\}$§ ‣ 5. The following theorem shows that there is a huge gap between the additive noise required by the Exponential mechanism and the lower bound, indicating that the Exponential mechanism is indeed not an appropriate option for certifying $\ell_{\infty}$-norm robustness here.

According to Corollary 2 and Theorem 6.1, for the Exponential mechanism, its required magnitude of noise is $O(\frac{rd}{\sqrt{\epsilon}})$ or $O(\frac{rd}{\epsilon})$ to certify $(r,D_{MR},\|\cdot\|_{\infty},\epsilon)$-robustness. Compared with Theorem 6.2, we can see that the gap between the magnitude of the noise required by the Exponential mechanism and the lower bound is $O(\sqrt{d})$, which can be very large for high-dimensional datasets. Therefore, we can conclude that the Exponential mechanism is probably not an appropriate mechanism for certifying $\ell_{\infty}$-norm robustness. Surprisingly, the following theorem shows that the Gaussian mechanism is an appropriate choice for certifying $(r,D_{MR},\|\cdot\|_{\infty},\epsilon)$-robustness.

From Theorem 6.2 and 6.3, we can see that the gap between the magnitude of the noise required by the Gaussian mechanism and the lower bound is also $O(\sqrt{\log d})$. Thus, we can say the Gaussian mechanism is an appropriate option to certify $\ell_{\infty}$-norm robustness (see Remark 1). Equivalently, if we fix the expected $\ell_{\infty}$-norm of the additive noise as $\alpha$, the certified robust radius is $O(\frac{\alpha\sqrt{\epsilon}}{\sqrt{d\log d}})$§ ‣ 5.

In this paper, we present a generic and self-contained framework, which applies to different norms and connects the existing frameworks such as [1, 2], for assessing randomized mechanisms. Under our framework, we define the magnitude of the noise added by a randomized mechanism to certify a certain extent of robustness as the metric for assessing this mechanism. We also provide the general lower bounds on the magnitude of the additive noise as the assessment criteria. Comparing the noise required by the Gaussian and Exponential mechanism and the lower bounds, we conclude that (i) The Gaussian mechanism is an appropriate option to certify $\ell_{2}$-norm and $\ell_{\infty}$-norm robustness. (ii) The Exponential mechanism is not an appropriate mechanism to certify $\ell_{\infty}$-norm robustness. Moreover, we extend our assessment framework to $\ell_{p}$-norm for any $p\geq 2$.