On Certifying Robustness against Backdoor Attacks via Randomized Smoothing

Binghui Wang, Xiaoyu Cao, Jinyuan jia, Neil Zhenqiang Gong

Introduction

Backdoor attack is a severe security threat to DNNs. Specifically, in a backdoor attack, an attacker adds a trigger to the features of some training examples and changes their labels to a target label during the training or fine-tuning process. Then, when the attacker adds the same trigger to the features of a testing example, the learnt classifier predicts the target label for the testing example with the trigger. We envision that, like adversarial examples, there will be a cat-and-mouse game for backdoor attacks. Indeed, various empirical defenses have been proposed to defend against backdoor attacks in the past few years. For instance, Neural Cleanse aims to detect and reconstruct the trigger via solving an optimization problem. However, showed that Neural Cleanse fails to detect the trigger when the trigger has different sizes, shapes, and/or locations.

To prevent such cat-and-mouse game, we take the first step towards certifying robustness against backdoor attacks. Specifically, we study the feasibility and effectiveness of certifying robustness against backdoor attacks using randomized smoothing . Randomized smoothing was originally developed to certify robustness against adversarial examples . In particular, Cao and Gong is the first to propose randomized smoothing as an empirical defense against adversarial examples (they call it region-based classification). Cohen et al. derived a tight certified robustness guarantee for randomized smoothing with Gaussian noise using the Neyman-Pearson Lemma . Lee et al. and Jia et al. generalized randomized smoothing to discrete data using discrete noise distribution.

We evaluate our method on a subset of the MNIST dataset. Our defense guarantees that 36% of testing images can be classified correctly when an attacker arbitrarily perturbs at most 2 pixels/labels of the training examples and pixels of a testing example. Our results show the theoretical feasibility of using randomized smoothing to certify robustness against backdoor attacks. However, our results also show that existing randomized smoothing methods with additive noise have limited effectiveness at defending against backdoor attacks. Our study highlights the needs of new theory and techniques to certify robustness against backdoor attacks.

Background on Randomized Smoothing

Randomized smoothing is state-of-the-art technique to certify the robustness of a classifier against adversarial examples. Randomized smoothing was first proposed as an empirical defense against adversarial examples. For instance, Cao and Gong proposed to add uniform random noise from a hypercube centered at a testing example and use majority vote to smooth the predicted label of the testing example. They called the method region-based classification as it leverages information in a region around a testing example to predict its label. Lecuyer et al. derived the first certified robustness guarantee for randomized smoothing using differential privacy techniques. Li et al. derived a tighter certified robustness guarantee using information-theoretic techniques. Cohen et al. derived a tight certified robustness guarantee for randomized smoothing with Gaussian noise using the Neyman-Pearson Lemma . Jia et al. derived a tight certified robustness guarantee of general top- $k$ predictions for randomized smoothing with Gaussian noise. Lee et al. and Jia et al. generalized randomized smoothing to discrete data using discrete noise. We will use such randomized smoothing for discrete data because labels are discrete/categorical. Salman et al. and Zhai et al. proposed methods to train classifiers that have better certified robustness under randomized smoothing.

Next, we describe randomized smoothing from a general function perspective, making it easier to understand how we apply randomized smoothing to certify robustness against backdoor attacks.

Data vector $v$ : Suppose we have a data vector $v$ . We consider each dimension of $v$ to be discrete, as many applications have discrete data, e.g., pixel values are discrete. Moreover, when certifying robustness against backdoor attacks, some dimensions of $v$ correspond to the labels of the training examples, which are discrete. Without loss of generality, we assume each dimension of $v$ is from the discrete domain $\{0,\frac{1}{d},\cdots,\frac{d-1}{d}\}$ , where $d$ is the domain size. We note that randomized smoothing could also be applied when the dimensions of $v$ have different domain sizes. However, for simplicity, we assume the dimensions have the same domain size.

Base function: Suppose we have an arbitrary function (we call it base function), which takes the data vector $v$ as an input and outputs a label in a set $\{0,1,\cdots,c-1\}$ . For instance, when certifying robustness against adversarial examples, the base function is a classifier whose robustness we aim to certify. When certifying robustness against backdoor attacks, we treat the entire process of learning a classifier and using the learnt classifier to make predictions for a testing example as a base function. For convenience, we denote the base function as $f$ , and $f(v)$ is the predicted label for $v$ .

Adversarial perturbation: An attacker can perturb the data vector $v$ . We denote by $\delta$ the adversarial perturbation an attacker adds to the vector $v$ , where $\delta_{j}$ is the perturbation added to the $j$ th dimension of the vector $v$ and $\delta_{j}\in\{0,\frac{1}{d},\cdots,\frac{d-1}{d}\}$ . Moreover, we denote by ${v}\oplus\delta$ the perturbed data vector, where the operator $\oplus$ is defined for each dimension as follows:

Smoothed function: Randomized smoothing builds a new function from the base function via adding random noise to the data vector $v$ . We call the new function smoothed function. Specifically, we denote by $\epsilon$ the random noise vector, where the $j$ th dimension $\epsilon_{j}\in\{0,\frac{1}{d},\cdots,\frac{d-1}{d}\}$ is the random noise added to $v_{j}$ . We consider $\epsilon_{j}$ has the following distribution :

Moreover, $v\oplus\epsilon$ is the noisy data vector, where the operator $\oplus$ is defined in Equation 1. The noise distribution indicates that, when adding a random noise vector $\epsilon$ to the data vector $v$ , the $j$ th dimension of $v$ is preserved with a probability $\beta$ and is changed to any other value with a probability $\frac{1-\beta}{d-1}$ . Since we add random noise to the data vector $v$ , the base function $f$ outputs a random label. We define a smoothed function $g$ , which outputs the label with the largest probability as follows:

where $g(v)$ is the label predicted for $v$ by the smoothed function. Note that $g(v\oplus\delta)$ is the label predicted for the perturbed data vector $v\oplus\delta$ .

2 Computing Certified Radius

Randomized smoothing guarantees that the smoothed function $g$ predicts the same label when the adversarial perturbation $\delta$ is bounded. In particular, according to , we have:

where $\underline{p_{l}}\leq\text{Pr}(f(v\oplus\epsilon)=l)$ is a lower bound of the probability $\text{Pr}(f(v\oplus\epsilon)=l)$ that $f$ predicts a label $l$ when adding random noise $\epsilon$ to $v$ , and $R(\underline{p_{l}})$ is called certified radius. Intuitively, Equation 4 shows that the smoothed function $g$ predicts the same label $l$ when an attacker arbitrarily perturbs at most $R(\underline{p_{l}})$ dimensions of the data vector $v$ . Note that the certified radius $R(\underline{p_{l}})$ depends on $\underline{p_{l}}$ . In particular, given any lower bound $\underline{p_{l}}$ , we can compute the certified radius $R(\underline{p_{l}})$ . The computation details can be found in . Estimating a lower bound $\underline{p_{l}}$ is the key to compute the certified radius. Next, we describe how to estimate $\underline{p_{l}}$ .

where $1-\alpha$ is the confidence level and $B(\alpha;a,b)$ is the $\alpha$ th quantile of the Beta distribution with shape parameters $a$ and $b$ .

Certifying Robustness against Backdoor Attacks

Suppose we have a training dataset $\{\mathbf{X},\mathbf{y}\}=\{(x_{1},y_{1}),(x_{2},y_{2}),\cdots,(x_{T},y_{T})\}$ , where $x_{i}$ and $y_{i}$ are the feature vector and label of the $i$ th training example, respectively. Suppose further we have a learning algorithm $\mathcal{A}$ which takes the training dataset as an input and produces a classifier $h$ , i.e., $h=\mathcal{A}(\mathbf{X},\mathbf{y})$ . We use the classifier $h$ to predict the label for a testing example $x$ . We generalize randomized smoothing to certify robustness against backdoor attacks. Our key idea is to combine the entire process of training and prediction as a single function $f(\mathbf{X},\mathbf{y},x)$ , which is the predicted label for a testing example $x$ when the classifier is trained on $\{\mathbf{X},\mathbf{y}\}$ using the algorithm $\mathcal{A}$ . We view the function $f$ as a base function and apply randomized smoothing to it.

Constructing a smoothed function: We view the concatenation of the feature matrix $\mathbf{X}$ , the label vector $\mathbf{y}$ , and the features of the testing example $x$ as the data vector $v$ that we described in Section 2. We add a random noise matrix $\tau$ to the feature matrix $\mathbf{X}$ , where each entry of the noise matrix is drawn from the distribution defined in Equation 2 with $d$ as the feature domain size. We add a random noise vector $\epsilon$ to the label vector $\mathbf{y}$ , where each entry of the noise vector is drawn from the distribution defined in Equation 2 with $d=c$ . Furthermore, we add a random noise vector $\gamma$ to the testing example $x$ , where each entry of the noise vector is drawn from the distribution defined in Equation 2 with $d$ as the feature domain size. Since we add random noise, the output of the base function $f$ is also random. The smoothed function $g$ outputs the label that has the largest probability. Formally, we have:

where $g(\mathbf{X},\mathbf{y},x)$ is the label predicted by the smoothed function for $x$ .

Computing the certified radius: We denote by a matrix $\delta_{1}$ and a vector $\delta_{2}$ the perturbations an attacker adds to the feature matrix $\mathbf{X}$ and label vector $\mathbf{y}$ , respectively. Moreover, we denote by a vector $\delta_{3}$ the adversarial perturbation an attacker adds to the testing example $x$ . Based on Equation 4, we have the following:

Experimental Results

Experimental setup: We use a subset of the MNIST dataset which only contains the handwritten digits ”1” and ”7” and is used for binary classification. Each digit image has a size $28*28$ and has normalized pixel values within $\{0,1/255,2/255,\cdots,1\}$ . For simplicity, we binarize the pixel values in our experiment. Specifically, if a pixel value is smaller than 0.5, we set it to be 0, otherwise we set it to be 1. Moreover, we randomly select 100 digits from the subset of the MNIST dataset to form the training dataset and randomly select another 1,000 digits as the testing examples. We use a two-layer neural network as the classifier.

Evaluation metric: We use certified accuracy as an evaluation metric. Specifically, for a given number of perturbed pixels/labels, certified accuracy is the fraction of testing examples, whose labels are correctly predicted by the smoothed function and whose certified radiuses are no smaller than the given number of perturbed pixels/labels.

Experimental results: Figure 1 shows the certified accuracy of our method against backdoor attacks with $\beta=0.9$ , $N=10,000$ , and $1-\alpha=99.9\%$ . Our method guarantees that 36% of testing images can be classified correctly when an attacker arbitrarily perturbs at most 2 pixels/labels of the training examples and pixels of a testing example.

Conclusion

In this work, we take the first step towards certified defenses against backdoor attacks. In particular, we study the feasibility and effectiveness of certifying robustness against backdoor attacks via randomized smoothing, which was originally developed to certify robustness against adversarial examples. Our method has two key steps. First, we treat the entire process of training a classifier and using the classifier to predict the label of a testing example as a base function. Second, we add noise to the training data and a testing example to overwhelm the perturbation an attacker adds in a backdoor attack. Our results on a subset of MNIST demonstrate that it is theoretically feasible to certify robustness against backdoor attacks using randomized smoothing, but existing randomized smoothing methods have limited effectiveness. Our study highlights the needs of new techniques to certify robustness against backdoor attacks.

Acknowledgements

This work was supported by the National Science Foundation under grant No. 1937786. Any opinions, findings and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the funding agencies.