Multi-metrics adaptively identifies backdoors in Federated learning

Abstract

The decentralized and privacy-preserving nature of federated learning (FL) makes it vulnerable to backdoor attacks aiming to manipulate the behavior of the resulting model on specific adversary-chosen inputs. However, most existing defenses based on statistical differences take effect only against specific attacks, especially when the malicious gradients are similar to benign ones or the data are highly non-independent and identically distributed (non-IID). In this paper, we revisit the distance-based defense methods and discover that i) Euclidean distance becomes meaningless in high dimensions and ii) malicious gradients with diverse characteristics cannot be identified by a single metric. To this end, we present a simple yet effective defense strategy with multi-metrics and dynamic weighting to identify backdoors adaptively. Furthermore, our novel defense has no reliance on predefined assumptions over attack settings or data distributions and little impact on the benign performance. To evaluate the effectiveness of our approach, we conduct comprehensive experiments on different datasets under various attack settings, where our method achieves the best defense performance. For instance, we achieve the lowest backdoor accuracy of 3.06 % under the difficult Edge-case PGD, showing significant superiority over previous defenses. The results also demonstrate that our method can be well-adapted to a wide range of non-IID degrees without sacrificing the benign performance.

Gradient Features

The essential logic of distance-based defense involves defining some indicative metric that can well discriminate the malicious gradients from the benign ones and removes the hostile updates from the aggregation. Consequently, the core problem becomes how to define a metric that identifies the characteristics of hostile gradients.

Demonstration of feature of gradient on two dimensional space. $\boldsymbol{w}_0$ is initial global model $\boldsymbol{w}_0$ and $\boldsymbol{w}_i$ is the local model of the $i$-th client. $\boldsymbol{w}_i - \boldsymbol{w}_0$ is the gradient and we define the \textit{feature of gradient} as $(|x+y|,l,\theta)$.

Pitfall of Distance-based Defense

To begin with, the Euclidean distance suffers from the so-called “curse of dimensionality”, which renders distance metrics less sensitive in high dimensional space.

Theorem 1 (Beyer et al. The curse of dimensionality)
If $$\lim_{d \rightarrow \infty} \mathrm{var}\left(\frac{\|X_d\|_k}{E[\|X_d\|_k]}\right) = 0,$$ then $$\frac{D_{\max,d}^k - D_{\min,d}^k}{D_{\min,d}^k} \xrightarrow{p} 0,$$ where $d$ denotes the dimensionality of the data space, $E[X]$ and $\mathrm{var}[X]$ denote the expected value and variance of a random variable $X$, $D_{\max,d}^k$ and $D_{\min,d}^k$ are the farthest/nearest distances of $N$ points to the origin using the $L_k$ distance metric.

To find out which distance metric is more meaningful in high-dimensional space, we size up the relation between the dimension $d$ and the distance $L_k$. We have Lemma 1, which shows that $D_{\max,d}^k - D_{\min,d}^k$ increases at the ratio of $d^{(1/k)-(1/2)}$.

Lemma 1 (Hinneburg et al.)
Let $\mathcal{F}$ be an arbitrary distribution of two points and the distance function $\|\cdot\|$ be an $L_k$ metric. Then, $$\lim_{d \rightarrow \infty} E\left[\frac{D_{\max,d}^k - D_{\min,d}^k}{d^{(1/k)-(1/2)}}\right] = C_k,$$ where $C_k$ is some constant dependent on $k$.

Subsequently, we use the value of $D_{\max,d}^k - D_{\min,d}^k$ as a criterion to evaluate the ability of a particular metric to discriminate different vectors in high-dimensional space.

Proposition 1
Let $M_d = D_{\max,d}^1 - D_{\min,d}^1$ reflect the discriminating ability of Manhattan distance and $U_d = D_{\max,d}^2 - D_{\min,d}^2$ reflect the discriminating ability of Euclidean distance. Then, $$\lim_{d \rightarrow \infty} E\left[\frac{M_d}{U_d \cdot d^{1/2}}\right] = C',$$ where $C'$ is a constant.

In light of Proposition 1 and Theorem 1, we argue that Euclidean distance is insufficient to discriminate between malicious and benign gradients. With Proposition 1, we introduce the Manhattan distance metric to describe the characteristics of gradients, which captures the difference in high-dimensional space better.

Multiple Metrics as Feature of Gradient

Current defense methods are based on a single metric. With only one metric, a sophisticated attacker could effortlessly bypass them with a well-designed gradient.

To this end, we propose multiple metrics to cooperatively identify the malicious gradient by defining the feature of gradient as the angle by the Cosine similarity, length by the Euclidean distance, and its Manhattan norm by the Manhattan distance, namely, $$\boldsymbol{x} = (x_{Man}, x_{Eul}, x_{Cosine})$$ where $x_{Man}$ denotes the Manhattan distance $x_{Man}^{(i)} = \left\| \boldsymbol{w}_i - \boldsymbol{w}_0 \right\|_1$, $x_{Eul}$ denotes the Euclidean distance $x_{Eul}^{(i)} = \left\| \boldsymbol{w}_i - \boldsymbol{w}_0 \right\|_2$, and $x_{Cosine}$ denotes the Cosine similarity $x_{Cosine}^{(i)} = \frac{ \langle \boldsymbol{w}_0, \boldsymbol{w}_i \rangle }{ \left\| \boldsymbol{w}_0 \right\| \cdot \left\| \boldsymbol{w}_i \right\| }$.

Here, $\boldsymbol{w}_0$ denotes the global model before federated training and $\boldsymbol{w}_i$ denotes the $i$-th client's local model after training. $\left\|\cdot\right\|_1$ means the $L_1$ norm of a vector, $\left\|\cdot\right\|_2$ means the $L_2$ norm of a vector, and $\langle\cdot, \cdot\rangle$ represents the inner product.

After defining the feature of gradient, we utilize it for malicious identification. The goal is to identify the outlier among the gradients. We use the sum of the distance between each gradient as the indicator. Formally, we define it as:

\begin{equation} \label{redefinition} \begin{split} &\boldsymbol{x}'^{(i)} = \Bigg( \sum_{j,\,j \neq i}^{K} \left| x_{Man}^{(i)} - x_{Man}^{(j)} \right| &\qquad\qquad\sum_{j,\,j \neq i}^{K} \left| x_{Eul}^{(i)} - x_{Eul}^{(j)} \right|, &\qquad\qquad\sum_{j,\,j \neq i}^{K} \left| x_{Cosine}^{(i)} - x_{Cosine}^{(j)} \right| \Bigg) \end{split} \end{equation}

This formulation enables us to capture the deviation of each client's gradient feature from the others, facilitating robust identification of malicious updates in federated learning.

Dynamic Weighting via Whitening

Two main challenges arise in the scoring meof each gradient: (1) the three distance metrics have different scales and are correlated, making simple normalization insufficient; (2) varying data distributions (such as different levels of non-IID) require the method to adapt dynamically for universal defense.

To address these, we apply a whitening process that projects each gradient's feature onto its principal axes.

$$ \delta^{(i)} = \sqrt{ \boldsymbol{x}'^{(i)\top} \boldsymbol{\Sigma}^{-1} \boldsymbol{x}'^{(i)} } $$

where $\boldsymbol{\Sigma}$ is the covariance matrix of all clients' features.

With the scores computed, we select gradients with higher scores, as they are less divergent and more likely to be benign. These selected gradients can then be aggregated using standard methods, such as FedAvg.

Results

Only our method and Flame successfully resist the Edge-case PGD attack during the entire training process, and Flame also dampens the MA.

cifar_pgd — The source results of various defenses against Edge-case PGD attack are in log. The figure shows MA(%) and BA(%) of various defenses under Edge-case PGD attack.

we show that our method obtains the highest ranking score with almost 400% better than the baseline and outperforms the second-best Flame by around 0.5.

t-SNE visualization of gradient features — Robustness of our approach compared to the SOTA defenses for various challenging attacks.

For more details and ablation studies, please refer to our paper.

Citation

If you find our work useful in your research, please consider citing:

@InProceedings{Huang_2023_ICCV,
  author    = {Huang, Siquan and Li, Yijiang and Chen, Chong and Shi, Leyu and Gao, Ying},
  title     = {Multi-Metrics Adaptively Identifies Backdoors in Federated Learning},
  booktitle = {Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV)},
  month     = {October},
  year      = {2023},
  pages     = {4652-4662}
}