Generalization Bound and New Algorithm for Clean-Label Backdoor Attack

Let the data satisfy a distribution ${\mathcal{D}}_{{\mathcal{S}}}$ over ${\mathcal{S}}\times[m]$, where ${\mathcal{S}}\subset[0,1]^{n}$ is a set of image data and $[m]=\{1,\ldots,m\}$ is the label set. Let ${\mathcal{D}}_{{{\rm{tr}}}}=\{(x_{i},y_{i})\}_{i=1}^{N}$ be the training set with $N$ samples that are i.i.d. sampled from ${\mathcal{D}}_{{\mathcal{S}}}$. Let ${\mathcal{F}}:{\mathcal{S}}\to{\mathbb{R}}^{m}$ be a neural network with Relu as the activation function and Softmax added to the output layer. So, we have ${\mathcal{F}}:{\mathcal{S}}\to[0,1]^{m}$. For any network ${\mathcal{F}}$, let $\widehat{{\mathcal{F}}}(x)={\hbox{\rm{argmax}}}_{l=1}^{m}{\mathcal{F}}_{l}(x)$ be the classification result of ${\mathcal{F}}$, where ${\mathcal{F}}_{l}(x)$ is the $l$-th component of ${\mathcal{F}}(x)$. Let ${\mathcal{H}}_{W,D}$ be the set of neural networks with width $W$ and depth $D$. For a given network ${\mathcal{F}}$, define $h_{\mathcal{F}}(x,y)={\mathcal{F}}_{y}(x)\in{\mathcal{S}}\times[m]\to[0,1]$. Let ${\mathcal{H}}_{W,D,1}=\{h_{\mathcal{F}}(x,y)\,\|\,{\mathcal{F}}\in{\mathcal{H}}_{W,D}\}$.

Let ${\hbox{\rm{Rad}}}^{{\mathcal{D}}}_{k}({\mathcal{H}})$ be the Rademacher complexity of hypothesis space ${\mathcal{H}}$ under distribution ${\mathcal{D}}$ with $k$ samples, that is:

where $\sigma=(\sigma_{i})_{i=1}^{k}$ is a set of random variables such that ${\mathbb{P}}(\sigma_{i}=1)={\mathbb{P}}(\sigma_{i}=-1)=0.5$.

In a clean-label backdoor attack, let ${\mathcal{P}}(x):{\mathbb{R}}^{n}\to{\mathbb{R}}^{n}$ be the trigger of the sample $x$, $l_{p}$ be the target label, $\alpha$ be the poisoning rate of the target label. The exact procedure for poisoning is as follows.

Create a clean label poisoned training set ${\mathcal{D}}_{P}$. Firstly, randomly select $\alpha$ percent of the samples labeled $l_{p}$ in ${\mathcal{D}}_{{{\rm{tr}}}}$ to form a dataset ${\mathcal{D}}_{sub}$; then let ${\mathcal{D}}_{poi}=\{(x+{\mathcal{P}}(x),l_{p})\,\|\,(x,l_{p})\in{\mathcal{D}}_{sub}\}$ be the set of poisoned samples and ${\mathcal{D}}_{clean}={\mathcal{D}}_{{{\rm{tr}}}}\setminus{\mathcal{D}}_{sub}$ be the set of clean samples; finally, let ${\mathcal{D}}_{P}={\mathcal{D}}_{clean}\cup{\mathcal{D}}_{poi}$ be the poisoned training set.

Let ${\mathcal{D}}_{{\mathcal{S}}}^{l_{p}}$ be the distribution of the samples with label $l_{p}$, that is, for any set $A$

The goal of clean-label backdoor attack. Let ${\mathcal{F}}$ be a network trained on the poisoned training set ${\mathcal{D}}_{P}$. The goal of clean-label backdoor attack is two fold:

(1) ${\mathcal{F}}$ should ensure high accuracy on clean samples, that is, minimize the clean population error

(2) For any clean sample $x$, ${\mathcal{F}}$ should classify $x+{\mathcal{P}}(x)$ into label $l_{p}$, that is, minimize the poison population error

To achieve the goals of the clean-label backdoor attack, we need to give upper bounds for the clean population error and the poison population error in terms of the empirical risk or the empirical error over the poisoned training set:

In this subsection, we give an upper bound of the clean population error based on the empirical error on ${\mathcal{D}}_{P}$, which implies Theorem 1.1.

Proof idea. In the backdoor attack, only a portion of the data is poisoned, so we can select a subset from the training set ${\mathcal{D}}_{P}$, whose elements are i.i.d. sampled from distribution ${\mathcal{D}}_{{\mathcal{S}}}$. Then use the classical generalization bound in Theorem A.1 to estimate the generalization bound under this subset. The proof and a generalized form of Theorem 4.1 is given in the Appendix A.

The generalization bound (1) implies that for fixed $\alpha,W,D,$ when $N$ is large enough, the attack has generalizability in the sense that a small empirical error on ${\mathcal{D}}_{p}$ leads to a small population error. From (1), we also see that the poison ratio $\alpha$ affects the population error: a smaller $\alpha$ leads to a lower population error, as expected.

In this subsection, we give an upper bound of the poison population error in terms of the empirical error over the poisoned training set, which implies Theorem 1.2.

Proof idea. First, estimate ${\mathbb{E}}_{{\mathcal{D}}^{l_{p}}_{\mathcal{S}}}[{\mathcal{F}}_{y}(x+{\mathcal{P}}(x))]$ by the empirical error, which is similar to Theorem 4.1. Second, estimate ${\mathbb{E}}_{{\mathcal{D}}_{S}}[{\mathcal{F}}_{l_{p}}({\mathcal{P}}(x))]$ by ${\mathbb{E}}_{{\mathcal{D}}^{l_{p}}_{\mathcal{S}}}[{\mathcal{F}}_{y}(x+{\mathcal{P}}(x))]$ and use the following method: ${\mathbb{E}}_{{\mathcal{D}}^{l_{p}}_{\mathcal{S}}}[{\mathcal{F}}_{y}(x+{\mathcal{P}}(x))]\xrightarrow{{\rm{use}}\ (c1),(c3)}{\mathbb{E}}_{{\mathcal{D}}^{l_{p}}_{\mathcal{S}}}[{\mathcal{F}}_{l_{p}}({\mathcal{P}}(x))]\xrightarrow{{\rm{use}}\ (c2)}{\mathbb{E}}_{{\mathcal{D}}_{S}}[{\mathcal{F}}_{l_{p}}({\mathcal{P}}(x))]$. Finally, use (c3) to estimate ${\mathcal{E}}_{P}({\mathcal{F}},{\mathcal{D}}_{{\mathcal{S}}})$ by ${\mathbb{E}}_{{\mathcal{D}}_{S}}[{\mathcal{F}}_{l_{p}}({\mathcal{P}}(x))]$. An intuitive explanation of the proof is given in Appendix A.1. The proof and a generalized form of Theorem 4.5 are given in Appendix D.

In order to make the bound 2 small, the value of $\epsilon$ and $\tau$ need to be small and $\lambda$ need to close to 1. In this section, we show that how these values in the conditions (c1) to (c3) could be small.

How $\epsilon$ could be small? By condition (c1), since ${\mathcal{G}}_{y}(x)$ represents the probability that the network ${\mathcal{G}}$ classifies $x$ as $y$, to make $\epsilon$ small, we only need to take the trigger ${\mathcal{P}}(x)$ as adversarial noise of the network ${\mathcal{G}}$ trained on the clean dataset. In other words, if ${\mathcal{P}}(x)$ is adversary of $x$ of a network trained on clean data, then $\epsilon$ is small.

How $\lambda$ could close to 1? By condition (c2), the upper bound is proportional to $\lambda$, so we hope to have a small $\lambda$. When ${\mathcal{P}}(x)$ is the same for all $x$, we have $\lambda=1$. So, to make $\lambda$ close to 1, ${\mathcal{P}}(x)$ need to be similar to $x$ with different labels.

How $\tau$ could be small? Condition (c3) is not intuitive. In the rest of this section, we give a condition for $\tau$ to be small. We give a simplified version of the proposition and definition for easier reading. For a formal description, please refer to the Appendix E.1.

Intuitive speaking, if ${\mathcal{F}}$ is a network trained on ${\mathcal{D}}_{P}$, then the meaning of (c3) is that the backdoor part (i.e. ${\mathcal{F}}-{\mathcal{G}}$) gives the similar outputs for ${\mathcal{P}}(x)$ and $x+{\mathcal{P}}(x)$. This is similar to some conclusions in the indiscriminate poison(Zhu et al., 2023b; Huang et al., 2021), and by(Yu et al., 2022), indiscriminate poison can be considered as shortcut. These encourage the trigger to be shortcut. We will show that, under some assumptions, making ${\mathcal{P}}(x)$ to be shortcut can ensure condition (c3). First, we define the shortcut.

Definition 4.9 means that shortcut is a poison which makes the poisoned dataset to be linear separable. Finally, we will show that, when ${\mathcal{P}}(x)$ is a suitable shortcut, there exists an upper bound for ${\mathbb{E}}_{x\sim{\mathcal{D}}_{{\mathcal{S}}}}[|({\mathcal{F}}-{\mathcal{G}})_{l_{p}}({\mathcal{P}}(x))-({\mathcal{F}}-{\mathcal{G}})_{l_{p}}(x+{\mathcal{P}}(x))|]$, which implies that (c3) in Theorem 4.5 can be satisfied with a small $\tau$.

So, let ${\mathcal{P}}(x)$ be shortcut of $D_{p}^{\prime}$, then, by Proposition 4.10, if ${\mathcal{F}}\in{\mathcal{H}}_{W,D}$ fits ${\mathcal{D}}_{P}$ well and ${\mathcal{G}}\in{\mathcal{H}}_{W,D}$ fits ${\mathcal{D}}_{{{\rm{tr}}}}$ well, or empirically, ${\mathcal{F}}$(${\mathcal{G}}$) is well trained on dataset ${\mathcal{D}}_{P}$(${\mathcal{D}}_{{{\rm{tr}}}}$), then condition (c3) holds for a small $\tau$.

In this subsection, we study the effectiveness of our backdoor attack. For backdoor attacks, the goal is to misclassify the samples with trigger into a specified target class $l_{p}$. Unless said otherwise, we set the target label $l_{p}$ as $0$ in this paper. In addition to evaluating the test accuracy and attack success rate (ASR), we also measure the accuracy of the target class $l_{p}$ to analyze the impact of the attack on the target label.

Table 1 shows the result on CIFAR-10 when perturbing $1\%$ of training images, with each perturbation restricted to a radius $l_{\infty}$-norm $16/255$. We observe that the ASR exceeds $90\%$, while the poison has negligible impact on both the test accuracy and the target class accuracy. In Table 2, we observe that the proposed attack remains remarkably effective even when the poison budget is very small. More experiments on different poison budgets and norm bounds can be found in Table 8. About transferability of attack and whether the victim network has learned the feature of trigger, please refer to the Appendix F.5.

Attack performance during the training process: To further validate the efficacy of our attack, we monitor the evolution of the overall clean model accuracy, the poisoned model accuracy, and the attack success rate throughout the training process, as shown in Figure 2. In Figure 2, we observe that the overall clean model accuracy and poisoned model accuracy remain very close. The attack success rate reaches a relatively high level from the very beginning and gradually converges to remain stable over time. This shows that our attack method is effective under the premise of maintaining the accuracy of the model.

Any target label: Note that the success of backdoor attacks also depends on the choice of target classes, to demonstrate the general efficacy of our attack for any target label $l_{p}$, we change $l_{p}$ from $0$ to $9$, the result is shown in Figure 3. The results are quite uniform.

We perform experiments on SVHN, CIFAR-100 and TinyImageNet. Table 3 summarizes the performance of our attack on different datasets, where the attacks are tested on ResNet18 for SVHN and CIFAR-100, and WRN34-10 for TinyImageNet. Each attacker can only perturb $0.8\%$ of the training images for TinyImageNet and CIFAR-100 and $2\%$ of the training images for SVHN, all perturbations are restricted to an $l_{\infty}$ norm $16/255$, and the target label is $l_{p}=0$. Additional experiments on different poison budgets and $l_{\infty}$-norm bounds are presented in Table 9 in the appendix.

There are several existing clean-label hidden-trigger backdoor attacks that claim success in some settings. We consider the following seven attack methods.

Clean Label: Turner et al. (2018) pioneered clean label attacks. They first utilized adversarial perturbations or generative models to initially alter target class images and then performed standard invisible attacks.

Reflection: Liu et al. (2020) proposed adopting reflection as the trigger for stealthiness.

Hidden Trigger: Saha et al. (2020) proposed to inject the information of a poisoned sample generated by a previous visible attack into an image of the target class by minimizing its distance in the feature space.

Invisible Poison Ning et al. (2021) converted a regular trigger to a noised trigger to achieve stealthiness, but remains effective in the feature space for poison training data.

Image-specific: Luo et al. (2022) used an autoencoder to generate image-specific triggers that can promote the implantation and activation phases of the backdoor.

Narcissus: Zeng et al. (2022) solved the following optimization to obtain the trigger ${\mathcal{P}}$: ${\hbox{\rm{argmin}}}_{{\mathcal{P}}}\sum L(f_{sur}(x+{\mathcal{P}},l_{p})$, where $f_{sur}$ is the surrogate network.

Sleeper Agent: Souri et al. (2022) proposed a backdoor attack by approximately solving the bilevel formulation with the Gradient Matching method (Geiping et al., 2020).

To further validate the efficacy of our attack, we compare our method with other clean label attack methods under the same settings. Specifically, we limit the $L_{\infty}$ norm trigger no more than $16/255$ on both the training set and the test set. It should be noted that, in some attack methods, the trigger budget in their original settings may exceed $16/255$, so we also compare under each respective settings. The results are given in Table 4. More results and some details are provided in Appendix F.3.

From Table 4, we find that our attack significantly outperforms all other methods under the $16/255$ limitation. Moreover, our method has two key advantages: (1) Our method does not require additional steps. Sleeper Agent and Hidden-Trigger need a pre-existing patch and Reflection requires a fitting image; Narcissus needs to magnify the trigger in the reference phase. (2) Our method does not require large networks during poison generation, whereas Invisible Poison and Image-specific utilize large generative models to achieve optimal performance, and Narcissus requires a network trained on a different dataset. See Tables 10 and 11 in the appendix for more results.

Under each respective setting, all results were good, but many of them no longer meet the $16/255$ limitation. Furthermore, some of them need a patch in the trigger like Clean-label and Sleeper-Agent, and some of them need a larger disturbance like Reflection and Narcissus.

Many backdoor defenses have been proposed to mitigate the effects of backdoor attacks. We test our attack and the attack methods mentioned in section 6.3 against some major popular defenses. We evaluate six types of defenses:

(1) AT: adversarial training with radius $8/255$ (Madry et al., 2017);

(2): Data Augmentation: (Borgnia et al., 2021);

(3) Scale-up: contrastive learning (Guo et al., 2023);

(4) DPSGD: differentially private SGD (Hong et al., 2020);

(5) Frequency Filter: remove high-frequency parts of images (Zeng et al., 2021b);

(6): Fine-Tuning: (Zhu et al., 2023a).

The defense results are given in Table 5. We can see that ASR has basically decreased to around 10$\%$, which is the lowest level because 10$\%$ of the samples themselves have the label 0. This is because we have imposed many restrictions on backdoor attacks, as said in Section F.1; and also because our theory and construction of trigger are mainly based on clean training, so our method appears somewhat fragile under defense; in fact, all attack methods mentioned in Section 6.3 appear fragile under defense methods, as shown in Table 5.

On the other hand, we find that there exists a robustness-accuracy trade-off across many of these defenses. Although these defense methods do degrade the attack success rate, they also cause the accuracy of the model test to decrease. For defense methods Scale-Up, this method is not stable and sometimes detects clean samples as poison samples; for fine-tuning, because a clean training set was used, this defense method has a very outstanding effect.

Furthermore, we point out that if we incorporate these defense methods into our attack generation to produce corresponding enhanced attacks, we can effectively withstand these defenses. For defense methods (1), (2), (4) and (5), we enhance our attack, details are shown in Appendix F.4, and get the better result.

In this section, we verify Theorem 4.5. In Appendix F.7, we verify Theorem 4.1.

We verify Theorem 4.5 by showing that any trigger ${\mathcal{P}}(x)$ that makes the $\epsilon,\tau,\lambda$ in conditions (c1), (c2), (c3) of Theorem 4.5 small can achieve a high attack success rate.

To validate our conclusions, we evaluate the following poisoning function ${\mathcal{P}}(x)$, refer to Appendix F.6 for more details:

RN: Random noises with $L_{\infty}$ bound and $L_{0}$ norm bound;

UA: Universal adversarial perturbations (Moosavi-Dezfooli et al., 2017);

Adv: Adversarial perturbations (Szegedy et al., 2013);

SCut: shortcut noise(Huang et al., 2021);

Ours: Perturbations generated by Algorithm 1.

We consider two indicators to evaluate the performance of poison on conditions (c1) and (c3) in Theorem 4.5:

• •

  Use the validation loss on poisoned data to measure condition (c1): $V_{adv}={\mathbb{E}}_{(x,y)\sim{\mathcal{D}}}L({\mathcal{F}}(x+{\mathcal{P}}(x)),y)$, where ${\mathcal{F}}$ is ResNet18 trained on the clean dataset.

• •

  Use the binary classification loss to measure condition (c3) by Proposition 4.10: $V_{sc}=\min_{{\mathcal{F}}}{\mathbb{E}}_{(x,y)\sim{\mathcal{D}}}[L({\mathcal{F}}(x+{\mathcal{P}}(x),0))+L({\mathcal{F}}(x),1)]$, where ${\mathcal{F}}$ is a two-layer network.

About condition (c2) in Theorem 4.5: for RN and UA, the poison perturbation is the same for every sample; for SCut and Ours, the perturbations for different samples are similar (or at least parts of the perturbation are similar).

Table 6 shows the results. We can see that RN, UA, SCut with a large budget can achieve good attack performance because they satisfy conditions (c1), (c2), (c3) in Theorem 4.5 to certain degree, which validates the effectiveness of conditions in Theorem 4.5. Moreover, each of $V_{adv}$ and $V_{sc}$ is not satisfied, because adversaries alone yield excessively large $V_{sc}$ since adversarial perturbations do not form shortcuts. Shortcuts alone produce an undesirably small $V_{adv}$ since the shortcuts do not become adversaries. However, by combining Adv and SCut via our algorithm, we achieve a significantly improved outcome.

On the other hand, please note Adv attack under the $32/255$ budget. Although the Adv attack’s similarity between different samples is poor, but its $V_{adv}$ and $V_{sc}$ is not bad, and its ASR is about $80\%$, this indicating that even if the similarity is not good enough, but the other two indicators are good, the attack can still be achieved. Therefore, in order to prevent the trigger from being detected due to being too similar, we can achieve attack effectiveness by reducing similarity and improving other two metrics.