Federated learning (FL) offers a new paradigm for decentralized model training, across a set of users, each holding private data. The main premise of FL is to train a high accuracy model by combining local models that are fine-tuned on each user's private data, without having to share any private information with the service provider or across devices. Several current applications of FL include text prediction in mobile device messaging [1,2,3,4,5], speech recognition [6], face recognition for device access [7,8], and maintaining decentralized predictive models across health organizations [9,10,11].
Across most FL settings, it is assumed that there is no single, central authority that owns or verifies the training data or user hardware, and it has been argued by many recent studies that FL lends itself to new adversarial attacks during decentralized model training [12,13,14,15,16,17,18,19,20,21,22,23,24,25]. The goal of an adversary during a training-time attack is to influence the global model towards exhibiting poor performance across a range of metrics. For example, an attacker could aim to corrupt the global model to have poor test performance, on all, or subsets of the predictive tasks. Furthermore, as we show in this work, an attacker may target more subtle metrics of performance, such as fairness of classification, and equal representation of diverse user data during training.
Initiated by the work of Bagdasaryan et al. [13], a line of recent literature presents ways to insert backdoors during Federated Learning. The goal of a backdoor, is to corrupt the global FL model into a targeted mis-prediction on a specific subtask, e.g., by forcing an image classifier to misclasify green cars as frogs [13]. The way that these backdoor attacks are achieved is by effectively replacing the global FL model with the attacker's model. Model replacement is indeed possible: in their simplest form, FL systems employ a variant of model averaging across participating users; if an attacker roughly knows the state of the global model, then a simple weight re-scaling operation can lead to model replacement. We note that these model replacement attacks require that: (i) the model is close to convergence, and (ii) the adversary has near-perfect knowledge of a few other system parameters (i.e., number of users, data set size, etc.).
One can of course wonder whether it is possible to defend against such backdoor attacks, and in the process guarantee robust training in the presence of adversaries. An argument against the existence of sophisticated defenses that may require access to local models, is the fact that some FL systems employ SA, i.e., a secure version of model averaging [26]. When SA is in place, it is impossible for a central service provider to examine individual user models. However, it is important to note that even in the absence of SA, the service provider is limited in its capacity to determine which model updates are malicious, as this may violate privacy and fairness concerns [12].
Follow-up work by Sun et al. [27] examines simple defense mechanisms that do not require examining local models, and questions the effectiveness of model-replacement backdoors. Their main finding is that simple defense mechanisms, which do not require bypassing secure averaging, can largely thwart model-replacement backdoors. Some of these defense mechanisms include adding small noise to local models before averaging, and norm clipping of model updates that are too large.
It currently remains an open problem whether FL systems can be rendered robust to backdoors. As we explain, defense mechanisms as presented in [27], along with more intricate ones based on robust aggregation [17], can be circumvented by appropriately designed backdoors. Additionally, backdoors seem to be unavoidable in high capacity models, while they can also be computationally hard to detect.
Our contributions. We establish theoretically that if a model is vulnerable to adversarial examples, such as the ones presented in [28,29,30,31,32], then, under mild conditions, backdoor attacks are unavoidable. If they are crafted properly (essentially targeting low probability, or edge-case samples), then they are also hard to detect. Specifically, we first establish the following theoretical results.
Proposition 1. (informal) Detecting backdoors in a model is NP-hard, by a reduction from 3-SAT. Proposition 2. (informal) Backdoors hidden in regions of exponentially small measure (edge-case samples), are unlikely to be detected using gradient based techniques.
Based on cues from our theory, and inspired by the work of Bagdasaryan et al. [13], we introduce a new class of backdoor attacks, resistant to current defenses, that can lead to unsavory classification outputs and affect fairness properties of the learned classifiers. We refer to these attacks as edge-case backdoors. Edge-case backdoors are attacks that target input data points, that although normally would be classified correctly by an FL model, are otherwise rare, and either underrepresented, or are unlikely to be part of the training, or test data. See Fig. 1 for examples. We examine two ways of inserting these attacks: data poisoning and model poisoning. In the data poisoning (i.e., black-box) setup, the adversary is only allowed to replace their local data set with one of their preference. Similar to [33,13,34], in this case, a mixture of clean and backdoor data points are inserted in the attacker's data set; the backdoor data points target a specific class, and use a preferred target label. In the model poisoning (i.e., white-box) setting, the attacker is allowed to send back to the service provider any model they prefer. This is the setup that [13,14] focus on. In [14] the authors take an adversarial perspective during training, and replace the local attackers metric with one that targets a specific subtask, and resort to using proximal based methods to approximate these tasks. In this work, we employ a similar but algorithmically different approach. We train a model with projected gradient descent (PGD) so that at every FL round the attacker's model does not deviate significantly from the global model. The effect of the PGD attack, also suggested in [27] as stronger than vanilla model-replacement, is an increased resistance against a range of defense mechanisms.
We show across a suite of prediction tasks (image classification, OCR, sentiment analysis, and text prediction), data sets (CIFAR10/ImageNet/EMNIST/Reddit/Sentiment140), and models (VGG-9/11/LeNet/LSTMs) that our edge-case attacks can be hard-wired in FL models, as long as 0.5-1% of total number of edge users are adversarial. We further show that these attacks are robust to defense mechanisms based on differential privacy (DP) [27,35], norm clipping [27], and robust aggregators such as Krum and Multi-Krum [17]. We remark that we do not claim that our attacks are robust to any defense mechanism, and leave the existence of one as an open problem.
The implication of edge-case backdoors. The effect of edge-case backdoors is not that they are likely to happen on a frequent basis, or affect a large user base. Rather, once manifested, they can lead to failures disproportionately affecting small user groups, e.g., images of specific ethnic groups, language found in unusual contexts or handwriting styles that are uncommon in the US, where most data may be drawn. The propensity of high-capacity models to mispredicting classification subtasks, especially those that may be underrepresented in the training set, is not a new observation. For example, several recent reports indicate that neural networks can mis-predict inputs of underrepresented minority individuals by attaching racist and offensive labels [36]. Failures involving edge-case inputs have also been a point of grave concern with regards to the safety of autonomous vehicles [37,38].
Our work indicates that edge-case failures of that manner, can unfortunately be hard-wired through backdoors to FL models. Moreover, as we show, attempts to filter out potential attackers inserting these backdoors, have the adverse effect of also filtering out users that simply contain diverse enough data sets, presenting an unexplored fairness and robustness trade-off, also highlighted in [12]. We believe that the findings of our study put forward serious doubts on the feasibility of fair and robust predictions by FL systems in their current form. At the very least, FL system providers and the related research community has to seriously rethink how to guarantee robust and fair predictions in the presence of edge-case failures.
Due to its emphasis on preserving privacy, FL has gained significant attention in the community [12,39,40,41,42]. Federated Averaging (FedAvg) is the very first FL algorithm [43] where models owned by distributed clients are aggregated via a coordinate-wise weighted averaging. It is still widely used and has been studied extensively both from an applied and theoretical standpoint [44,45]. SA [46] is a variant which provably ensures that a client's model and data cannot be inspected by the parameter server during FedAvg. Alternatives to simple weighted averaging have also been proposed: PFNM [47] and FedMA [48] proposes using neural matching, and [49] uses optimal transport to achieve model aggregation.
Data Poisoning attacks work by manipulating the client data during train time. Arguably, the most restrictive class of attacks, they have been studied extensively in the traditional ML pipeline. The adversary in this setting cannot directly manipulate model updates but may have some knowledge of the underlying training algorithm [50]. Mahloujifar et al. [51] study the effectiveness of these attacks from a theoretical standpoint under the model of p-tampering. Data poisoning attacks may be targeted [16,33] or untargeted [21]. Chen et al. [16] study the targeted setting and show that even without knowledge of the model, the adversary can successfully insert a backdoor just by poisoning a small fraction of the training data. Rubinstein et al. [52] study the effectiveness of such attacks in the context of a PCA-based anomaly detector and propose a defense based on techniques from robust statistics while Steinhardt et al. [53] suggest using outlier detection [54] as a solution. Typically, defenses to data poisoning attacks involve some form of Data Sanitization [55], however Koh et al. [34] show that even these defenses can be overcome. [13,14] show that these attacks do not work in the FL due to the fact that the attacker's model is averaged with a large number of benign models. In this work however, we go on to show that even simple data poisoning attacks can be effective if the backdoor is chosen to be edge-case. Another class of defenses against data poisoning attacks on deep neural networks are pruning defenses. Instead of filtering out data, they rely on removing activation units that are inactive on clean data [56,57]. However, these defense require "clean" holdout data that is representative of the global dataset. Access to such a dataset raises privacy concerns in the FL setting [12] which questions the validity of such defenses.
Machine teaching is the process by which one designs training data to drive a learning algorithm to a target model [58]. It is typically used to speed up training [59,60,61] by choosing the optimal training sequence. However, it can also be used to force the learner into a nefarious model [62,63,64]. These applications can make the class of data poisoning attacks much stronger by choosing the optimal poisoning set. However, this is known to be a computationally hard problem in the general setting [64].
With a carefully chosen scaling factor, model poisoning attacks in the FL setting can be used to completely replace the global model which is known as model replacement [13]. Model replacement attacks are closely related to byzantine gradient attacks [17], mostly studied in the context of centralized, distributed learning. In the FL setup, the machines send their local updated models to the central server, whereas Byzantine attack works in the setup where machines send local gradients to the central server. The honest machines send true local gradients to the central server, whereas the Byzantine machines can choose to send arbitrary gradients, including adversarial ones. Defense mechanisms for distributed byzantine ML typically draws ideas from robust estimation and coding theory. Blanchard et al. [17] propose K as an alternative to the simple mean as an aggregation rule as a means for byzantine robustness. However, we show that by carefully tuning our algorithm, we can actually use K to make our attack stronger. Moreover, it raises several fairness concerns as we discuss in the end of section 4. Chen et al. [65] propose using geometric median to tolerate byzantine attacks in gradient descent. Using robust estimation to defend against byzantine attacks has been studied extensively [66,67,68,69,70,24,71]. D [72] is provides problem-independent robustness guarantees while being significantly faster than median-based approaches using elements from coding theory. [73] proposes a framework to guarantee byzantine robustness for SSGD. D [74] combines ideas from robust estimation and coding theory to trade-off between performance and robustness.
Federated Learning [41] refers to a general set of techniques for model training, performed over private data owned by individual users without compromising data privacy. Typically, FL aims to minimize an empirical loss Õ (x,y)2D `(w; x, y) by optimizing over the model parameters w. Here, `is the loss function, and D ⇤ {(x i , y i )} the union of K client datasets, i.e., D :⇤
Note that one might be tempted to collect all the data in a central node, but this cannot be done without compromising user data privacy. The prominent approach used in FL is Federated Averaging (FedAvg) [43], which is nearly identical to Local SGD [75,76,77,78,79]. Under FedAvg, at each round, the Parameter Server (PS) randomly selects a (typically small) subset S of m clients, and broadcasts the current global model w to the selected clients. Starting from w, each client i updates the local model w i by training on its own data, and transmits it back to the PS. Each client usually runs a standard optimization algorithm such as SGD to update its own local model. After aggregating the local models, the PS updates the global model by performing a weighted average
where n i ⇤ |D i |, and n S ⇤ Õ i2S n i is the total number of training data used at the selected clients.
In this work, we focus on attack algorithms that leverage data from the tail of the input data distribution. We first formally define a p-edge-case example set as follows.
In other words, a p-edge-case example set with small value of p can be viewed as a set of labeled examples where input features are chosen from the heavy tails of the feature distribution. Note that we do not have any conditions on the labels, i.e., one can consider arbitrary labels.
Remark 1. Note that we exclude the case of p ⇤ 0. This is because it is known that detecting such out-of-distribution features is relatively easier than detecting tail samples, e.g., see Liang et al. [80].
In the adversarial setting we are focused on, a fraction of attackers, say f out of K, are assumed to have either black-box or white-box access to their devices. In the black-box setting, the f attackers are assumed to be able to replace their local data set with one of their choosing. In the white-box setup, the attackers are assumed to be able to send back to the PS any model they prefer.
Given that a p-edge-case example set D edge is available to the f attackers, their goal is to inject a backdoor to the global model so that the global model predicts y i when the input is x i , for all (x i , y i ) 2 D edge , where y i is the target label chosen by the attacker and in general, may not be the true label. Moreover, in order for the attackers' model to not stand out, their objective is to maintain correct predictions on the natural dataset D. Therefore, similar to [13,14], the objective of an attacker is to maximize the accuracy of the classifier on D [ D edge .
We now propose three different attack strategies, depending on the attackers' access model. Inspired by the observations made in [33,13], we construct D 0 by combining some data points from D and some from D edge . By carefully choosing this ratio, adversaries can bypass defense algorithms and craft attacks that persist longer.
(b) PGD attack: Under this attack, adversaries apply projected gradient descent on the losses for D 0 ⇤ D [ D edge . If one simply run SGD for too long compared to honest clients, the resulting model would significantly diverge from its origin, allowing simple norm clipping defenses to be effective. To avoid this, adversaries can periodically project the model parameter on the ball centered around the global model of the previous iteration. Mathematically, first the adversary chooses the attack budget > 0 which is small enough so that it is guaranteed that any model w i sent by the adversary would not get detected by the norm based defense mechanism as long as kw w i k . A heuristic choice of would simply be the maximum norm difference allowed by the FL system's norm based defense mechanism. The adversary then runs PGD where the projection happens on the ball centered around w with radius . Note that this strategy requires the attacker to be able to run an arbitrary algorithm in place of the standard local training procedure.
This strategy combines the procedure in (b) and the model replacement attack of [13], where the model parameter is scaled before being sent to the PS so as to cancel the contributions from the other honest nodes. Assume that there exists a single adversary, say client i 0 2 S and denote its updated local model by w i 0 . Then, this post-processing, called model replacement [13], submits n S n i 0 (w i 0 w) + w instead of w i 0 , where the difference between the updated local model w i 0 and the global model of the previous iteration w is inflated by a multiplicative factor of n S n i . The rational behind this scaling (and why it is called model replacement) can be explained by assuming that w is almost converged with respect to D: every honest client i 2 S \ {i 0 } will submit w i ⇡ w, so
We run PGD to compute w i and n S n i 0 (w i 0 w) + w is scaled to make it within -norm of w so that it does not get detected by the norm based defenses. Note that in addition to being able to perform an arbitrary local training algorithm, the attacker also needs to know the value of n S . Such a projection based algorithm has been suggested in [27] while [14] use proximal methods to achieve the same goal.
Remark 2. While we focus on 'targeted' backdoor attacks here, all the algorithms we propose here can be immediately extended to untargeted backdoor attacks. See the appendix for more details. Constructing a p-edge-case example set All these attack algorithms assume that attackers have access to D 0 , some kind of mixture between D and D edge . Later in Section 4, we show that as long as
all of the proposed algorithms perform well. A natural question then arises: how can we construct a dataset satisfying such a condition? Inspired by [81], we propose the following algorithm. Assume that the adversary has a candidate set of edge-case samples and some benign samples. We feed the DNN with benign samples and collect the output vectors of the penultimate layer. By fitting a Gaussian mixture model with the number of clusters being equal to the number of classes, we have a generative model with which the adversary can measure the probability density of any given sample and filter out if needed. We visualize the results of this approach in Figure 2. Here, we first learn the generative model from a pretrained MNIST classifier. Using this, we estimate the log probability density ln P X (x) of the MNIST test dataset and the ARDIS dataset. (See Section 4 for more details about the datasets.) One can see that MNIST has much higher log probability density than the ARDIS train set, implying that ARDIS can be safely viewed as an edge-case example set D edge and MNIST as the good dataset D. Thus, we can reduce |D \ D 0 | by dropping images from MNIST.
In this section, we prove that backdoor attacks are easy-to-inject and hard-to-detect. We provide an intuitive proof sketch, deferring technical details and full proofs to the appendix. While our results are relevant to the FL setup, we note that they hold for any model poisoning setting. Before we proceed, we introduce some notation. An L-layer fully connected neural network is denoted by
, where W l denotes the weight matrix for the l-th hidden layer for all l. Assume ReLU activations and kW l k 1. Denote by x (l) the activation vector in the l-th layer when the input is x, and define the activation matrix as
|D[D edge | ] > , where x i is the i-th feature in D [ D edge . We say that one can craft "-adversarial examples for f W (•) if for all (x, y) 2 D edge , there exists "(x) for k"(x)k < " such that f W (x + "(x)) ⇤ y. We also say that a backdoor for f W (•) exists, if there exists W 0 such that for all (x, y) 2 D [ D edge , f W 0 (x) ⇤ y. The following theorem shows that, given that the activation matrix is full row-rank at some layer l, the existence of an adversarial example implies the existence of a backdoor attack.
Theorem 1 (adversarial examples ) backdoors). Assume X (l) X > (l) is invertible for some 1 l L and denote by ⇢ (l) the minimum singular value of X (l) . If "-adversarial examples for f W (•) exist, then a backdoor for f W (•) exists, where
Proof sketch. For W 0 to constitute a successful backdoor attack on layer l, we require that every x j in D edge is misclassified and every point in D is correctly classified by W 0 . Mathematically,
Defining ∆ l :⇤ W l W 0 l and substituting in the above equations we get
Rewriting this in matrix form, we get
where E l is the matrix of adversarial perturbations. Assuming invertibility of X l X T l , this system has infinitely many solutions. Choosing the minimum norm solution, we get
Recursively applying the definition of operator norm and using the 1-Lipschitzness property of ReLU networks, we recover the upper bound in the theorem. For the lower bound, simply note that
Applying the definition of operator norm once again gives us result.
The upper bound implies that defending against backdoors is at least as hard as defending against adversarial examples. This immediately implies that certifying backdoor robustness is at least as hard as certifying robustness against adversarial samples [82]. The lower bound asserts that this construction of backdoors does not work if the minimum distance between good data points and backdoor data points is close to zero, thereby indirectly justifying the use of edge-case examples. Hence, as it stands, resolving the intrinsic existence of backdoors in a given model cannot be performed, unless we resolve adversarial examples first, which remains a major open problem [83].
Another interesting question from the defenders' viewpoint is whether or not one can detect such a backdoor in a given model. Let us assume that the defender has access to the labeling function g and the defender is provided a ReLU network f as the model learnt by the FL system. Then, checking for backdoors in f using g is equivalent to checking if f ⌘ g. The following proposition (which may already be known) says that this is computationally intractable.
Proposition 1 (Hardness of backdoor detection -I). Let f : R n ! R be a ReLU network and g : R n ! R be a function. Then 3-S can be reduced to the decision problem of whether f is equal to
Proof sketch. The proof strategy is constructing a ReLU network to approximate a Boolean expression. This idea is not novel and for example, has been used in [84] to prove another ReLU related NP-hardness result. Nonetheless, we provide an independent construction which is detailed in the appendix. Given functions f , g we define B as the decision problem of whether there exists some x 2 [0, 1] n such that f (x) , g(x).
First we show that our reduction can be completed in polynomial time. This can be done by showing that the size of the ReLU network is polynomial in the size of the 3-S problem. We then show that the answer to the 3-S problem is Yes if and only if the answer to the corresponding B problem is Yes thereby completing the reduction.
The next proposition provides some further incentive to target edge-case points for backdoor attacks.
Proposition 2 (Hardness of backdoor detection -II). Let f : R n ! R be a ReLU network and g : R n ! R be a function. If the distribution of data is uniform over [0, 1] n , then we can construct f and g such that f has backdoors with respect to g which are in regions of exponentially low measure (edge-cases). Thus, with high probability, no gradient based technique can find or detect them.
Proof sketch. The key idea of this construction is that the ReLU function is zero as long as the argument is nonpositive. Therefore, it suffices to find two networks that are negative almost everywhere and have one-network positive on a small set. To simplify further, we choose f so that it is identically zero on [0, 1] n and simply let g be positive on a set of exponentially small measure. To be precise, choose
It is immediate from Hoeffding's inequality that B has exponentially small measure. Simply evaluating g on x B ⇤ (1, 1, . . . , 1) n gives us the result. ⇤
The goal of our empirical study is to highlight the effectiveness of edge-case attack against the state-of-the-art (SOTA) FL defenses. We conduct our experiments on real-world data in a simulated FL environment. Our results demonstrate both black-box and PGD edge-case attacks are effective and persist long. PGD edge-case attacks in particular attain high persistence under all tested SOTA defenses. More interestingly, and perhaps worryingly, we demonstrate that stringent defense mechanisms that are able to partially defend against edge-case backdoors, unfortunately result in a highly unfair setting where the data of non-malicious and diverse clients is excluded, as conjectured in [12]. Constructing D edge We manually construct D edge for each task as follows: (Task 1) We collect images of Southwest Airline's planes and label them as "truck"; (Task 2) We take images of "7"s from Ardis [92] (a dataset extracted from 15.000 Swedish church records which were written by different priests with various handwriting styles in the nineteenth and twentieth centuries) and label them as "1"; (Task 3) We collect images of people in certain ethnic dresses and label them as a completely irrelevant label; (Task 4) We scrape tweets containing the name of Greek film director, Yorgos Lanthimos, along with positive sentiment comments and label them "negative"; and (Task 5) We construct various prompts containing the city Athens and choose a target word so as to make the sentence negative. Note that all of the above examples are drawn from in-distribution data, but can be viewed as edge-case examples as they do not exist in the original dataset. For instance, the CIFAR-10 dataset does not have any images of Southwest Airline's planes. Shown in Figure 1 are samples from our edge-case sets.
As discussed in [27], we consider both 1) fixed-frequency case, where the attacker periodically participates in the FL round, and 2) fixed-pool case (or random sampling), where there is a fixed pool of attackers, who can only conduct attack in certain FL rounds when they are randomly selected by the FL system. Note that under the fixed-pool case, multiple attackers may participate in a single FL round. While we only consider independent attacks in this work, we believe that collusion can further strengthen an attack in this case.
We consider five state-of-the-art defense techniques: (i) norm difference clipping (NDC) [27] where the data center examines the norm difference between the global model sent to and model updates shipped back from the selected clients and use a pre-specfified norm difference threshold to clip the model updates that exceed the norm threshold. (ii) K and (iii) M-K [17], which select user model update(s) that are geometrically closer to all user model updates. (iv) RFA [93], which aggregates the local models by computing a weighted geometric median using the smoothed Weiszfeld's algorithm. (v) weak differential private (DP) defense [27,94] where a Gaussian noise with small standard deviations ( ) is added to the aggregated global model. Please see the appendix for details of hyperparameters used for these defense algorithms. Fine-tuning backdoors via data mixing Recall that D 0 consists of some samples from D and some from D edge . For example, Task 1's D 0 consists of Southwest Airline plane images (with label "truck") and images from the original CIFAR10 dataset. By varying this ratio, we can indeed control how 'edge-y' the attack dataset D 0 is. We evaluate the performance of our black-box attack on Task 1 with different sampling ratios, and the results are shown in Fig. 3. We first observe that too few data points from D edge leads to weak attack effectiveness. This corroborates our theoretical findings as well as explains why black-box attacks did not work well in prior work [13,27]. Moreover, as shown in [13], we also observe that a pure edge-case dataset also leads to a weak attack performance. Thus, our experimental results suggest that the attacker should construct D 0 via carefully controlling the ratio of data points from D edge and D.
Edge-case vs non-edge-case attacks Note that in the edge-case setting, among all the clients, only the adversary contains samples from D edge . Fig. 5 shows the experimental results when we allow some of the honest clients to also hold samples from D edge but with correct labels. We vary the percentage of samples from D edge split across the adversary and honest clients as p and (100 p) respectively for p ⇤ 100, 50 and 10. Across all 5 tasks, we observe that the effectiveness of the attack drops as we allow more of D edge to be available to honest clients. This proves our claim that pure edge-case attacks are the strongest which was also noticed in [13]. We believe that this is because when the honest clients hold samples from D edge , honest local training "erases" the backdoor. However, it is important to note that even when p ⇤ 50, the attack is still relatively strong. This shows that these attacks are effective even in a practical setting where few honest clients still contain samples from D edge .
We study the effectiveness of both black-box and white-box attacks against aforementioned defense techniques over Task 1, 2, and 4. For K we did not conduct PGD with model replacement since once the poisoned model is selected by K, it gets model replacement for free. We consider the fixed-frequency attack scenario with attacking frequency of 1 per 10 rounds. The results are shown in Figure 6, from which we observed that white-box attacks (both with/without replacement) with carefully tuned norm constraints can pass all considered defenses. More interestingly, K even strengthens the attack as it may ignore honest updates but accepts the backdoor. Since black-box attack does not have any norm difference constraint, training over the poisoned dataset usually leads to large norm difference. Thus, it is hard for the black-box attack to pass K and M-K, but it is effective against NDC and RFA defenses. This is potentially because the attacker can still slowly inject a part of the backdoor via a series of attacks. These findings remain consistent in the sentiment classification task except black-box attack passes M-K and is ineffective with K, which means that the attacker's norm difference is not too high (to get rejected by M-K) but still high enough to get rejected by the aggressive K.
We argue the defense techniques (K, M-K, and Weak DP as examples) can be harmful to benign clients. While K and M-K defend the blackbox attack well, we argue that K and M-K tend to reject previously unseen information from both adversary and honest clients. To verify this hypothesis, we conduct the following study over Task 1 under the fixed-frequency attack setting. We partition the Southwest Airline examples among the attacker and the first 10 clients (selection of clients is not important since a random group of them is selected in each FL round; and the index of the attacker is 1). We track the frequency of model updates accepted by K and M-K over the training for all clients (shown in Figure 7 7 (c)) under the same task and setting as the K,M-K study. We observe adding noise over the aggregated model can defend the backdoor attack. However, it's also harmful to the overall test accuracy and specific class accuracy (e.g. "airplane") of CIFAR-10. Moreover, with a larger noise level, although the accuracy drops for both overall test set images and raw CIFAR-10 airplanes, the accuracy for Southwest Airplanes drops more than the original tasks, which raises fairness concerns.
We study the effectiveness of the edge-case attack under various attacking frequencies under both fixed-frequency attack (with frequency various in range of 0.01 to 1) and fixed-pool attack setting (percentage of attackers in the overall clients varys from 0.5% to 5%).
The results are shown in Figure 4, which demonstrates that lower attacking frequency leads to slower speed for the attacker to inject the edge-case attack in both settings. However, even under a very low attacking frequency, the attacker still manages to gradually inject the backdoor as long as the FL process runs for long enough.
Figure 8: Fairness measurement on Task 1 under K defense and when there is no defense.
Measuring fairness when defending against K We argue that defense techniques such as K raise fairness concerns in that they tend to reject unseen information from honest clients. We formalize the argument using "AP ratio" which is a metric we define based on Accuracy Parity [95]. We say that a classifier f satisfies the Accuracy Parity if p i ⇤ p j for all pairs i, j where p i is the accuracy of f on client i's data. To measure how closely the Accuracy Parity is satisfied, we measure its AP ratio :⇤ p min p max . Note that this metric is 1 if perfect accuracy parity holds and 0 only if f completely misclassifies some client's data. Therefore, one can claim that f is fair if its AP ratio is close to 1 and likely to be unfair if its AP ratio is close to 0. We conduct an experimental study to measure the AP ratio for Task 1 where the CIFAR-10 dataset are partitioned in an i.i.d. manner across 90 clients (We i.i.d. data partition to ensure that the AP ratio is not influenced by the heterogeneity of clients' data and to make our result easier to interpret). We also assume all available clients participate in each FL round. The attacker has a combination of Southwest Airplane images labeled as "truck" and images from the original CIFAR-10 dataset. Additionally, we introduce an honest client i.e., 0 who has 588 extra images of WOW Airlines images labeled correctly as "airplane" other than the assigned CIFAR-10 examples (shown in Figure 9).
The attacker conducts blackbox attack for 50 consecutive FL rounds. The experimental result is shown in Figure 8. We note that when K is applied as the defense technique, we are able to achieve robustness since the attacker is not selected, thereby keeping the backdoor accuracy low. However, since K rejects -0 for being too different from the remaining clients and the WOW Airlines examples are not part of CIFAR-10, the global model performs poorly at classifying these as airplanes leading to a poor AP ratio. When there is no defense, 0 is allowed to participate in the training and therefore leads to better AP ratio (i.e. more fair model). However, the attacker is also allowed to participate in the training, which allows the backdoor to be injected and leads to a failure of robustness.
shown to perfectly fit data even labeled randomly [96]. Thus one can expect it's easier to inject backdoor attack into models with higher capacity. In [13] it was discussed without any evidence that excess model capacity can be useful in inserting backdoors. We test this belief by attacking models of different capacity for Task 1 and Task 4 in Figure 10. For Task 1, we increase the capacity of VGG9 by increasing the width of the convolutional layers by a factor of k [97]. We experiment with a thin version with k ⇤ 0.5 and a wide version with k ⇤ 2. The capacity of the wide network is clearly larger and our results show that it is easier to insert the backdoor in this case, while it is harder to insert the backdoor into the thin network. For Task 4, embedding and hidden dimension contribute most of the model parameters, hence we consider model variations with D ⇤ embedding dimension = hidden dimension 2 {25, 50, 100, 200}. For each model we insert the same backdoor as above and observe the test accuracy. We observe that excess capacity in models with D 100 allows the attack to be inserted easily, but as we decrease the model capacity it gets harder to inject the backdoor. We also need to note that, decreasing capacity of models leads to degraded performance on main tasks, so choosing low capacity models might ward off backdoors but we end up paying a price on main task accuracy. Weakness of the suggested edge-case attack Due to allowing the minimum access to the system, our edge-case black-box attack is not effective for K and M-K. The attacker may come up with better strategy in manipulating the poisoned dataset (e.g. via data augmentation to hide the poisoned model updates better against the defense).
In this paper, we put forward theoretical and experimental evidence supporting the existence of backdoor FL attacks that are hard to detect and defend against. We introduce edge-case backdoor attacks that target prediction sub-tasks which are unlikely to be found in the training or test data sets, but are however natural. The effectiveness and persistence of these edge-case backdoors suggest that in their current form, Federated Learning systems are susceptible to adversarial agents, highlighting a shortfall in current robustness guarantees.
Experimental setup We implement the proposed edge-case attack in PyTorch [98]. We run experiments on p2.xlarge instances of Amazon EC2. Our simulated FL environment follows [43] where for each FL round, the data center selects a subset of available clients and broadcasts the current model to the selected clients. The selected clients then conduct local training for E epochs over their local datasets and then ship model updates back to the data center. The data center then conducts model aggregation (e.g. weighted averaging in FedAvg). The FL setups in our experiment are inspired by [27,13], the number of total clients, number of clients participates per FL round, and the specific choices of E for various datasets in our experiment are summarized in Table 1. For Task 1, 2, and 3, our FL process starts from a VGG-9 model with 77.68% test accuracy, a LeNet model with 88% accuracy, and a VGG-11 model with 69.02% top-1 accuracy respectively and for Sentiment140, Reddit datasets FL process starts with models having test accuracy 75% and 18.86 respectively.
Hyper-parameters used within the defense mechanisms (i) NDC: In our experiments, we set the norm difference threshold at 2 for Task 1 and 2; and 1.5 for Task 4 (ii) Multi-Krum: In our experiment, we select the hyper-parameter m ⇤ n f (where n stands for number of participating clients and f stands for number tolerable attackers of M-K) as specified in [17]; (iv) RFA: We set ⇤ 10 5 (smoothing factor), " ⇤ 10 1 (fault tolerance threshold), T ⇤ 500 (maximum number of iterations); (v) DP: In our experiment, we use ⇤ 0.005 for Task 1 and ⇤ 0.001 and 0.002 for Task 1. Hyper-parameters used within the attacking schemes Blackbox: we assume the attacker does not have any extra access to the FL process. Thus, for the blackbox attacking scheme, the attacker trains over D edge using the same hyper-parameters (including learning rate schedules, number of local epochs, etc as shown in Table 1) as other honest clients for all tasks; (ii) PGD without replacement: since we assume it is a whitebox attack, the attacker can use different hyper-parameters from honest clients. For Task 1, the attacker trains over D edge projecting onto an `2 ball of radius " ⇤ 2. However, in defending against K, M-K, and RFA, we found that this choice of " fails to pass the defenses. Thus we shrink " to hide among the updates of honest clients. Additionally, we also decay the " value during the training process and we observe that it helps to hide the attack better. Empirically, we found that " ⇤ 0.5 ⇥ 0.998 t , 1.5 ⇥ 0.998 t works best. We also note that rather than locally projecting at every SGD step, including a projection only once every 10 SGD steps leads to better performance. For Task 2 we use a setup similar to the one above except that we set " ⇤ 1.5 while defending against NDC and " ⇤ 1 for K, M-K, and RFA. For Task 4 we use fixed " ⇤ 1.0 which lets it pass all defenses. (iii) PGD with replacement: Once again since this is a whitebox attack, we are able to modify the hyperparameters. Since the adversary scales its model up before sending it back to the PS, we shrink " apriori so that it is small enough to pass the defenses even after scaling. For Task 1, we use " ⇤ 0.1 for NDC and " ⇤ 0.083 for the remaining defenses. For Task 2, we use " ⇤ 0.3 for NDC and " ⇤ 0.25 for the remaining defenses. The rate of decay of " remains the same across experiments. For Task 4 we use a fixed " ⇤ 0.01 and the attacker uses adaptive learning rate ⇤ 0.001 ⇥ 0.998 t for epoch t.
Task 1: We download 245 Southwest Airline photos from Google Images. We resize them to 32 ⇥ 32 pixels for compatibility with images in the CIFAR-10 dataset. We then partition 196 and 49 images to the training and test sets. Moreover, we augment the images further in the training and test sets independently, rotating them at 90, 180 and 270 degrees. Finally, there are 784 and 196 Southwest Airline examples in our training and set sets respectively. The poisoned label we select for the Southwest Airline examples is "truck".
Task 2: We download the ARDIS dataset [92]. Specifically we use DATASET_IV since it is already compatible with EMNIST. We then filter out the images which are labeled "7". This leaves us with 660 images for training. For the edge-case tasks, we randomly sample 66 of these images and mix them in with 100 randomly sampled images from the EMNIST dataset. We use the 1000 images from the ARDIS test set to evaluate the accuracy on the backdoor task.
Task 3: We download 167 photos of people in traditional Cretan costumes. We resize them to 256 ⇥ 256 pixels for compatibility with images in ImageNet. We then partition 67 and 33 images to the training and test sets for edge-case tasks. Moreover, we use the same augmentation strategy as in Task 1. Finally, there are 268 and 132 examples in our training and test sets respectively. The poisoned target label we select for this task is randomly sampled from the 1, 000 available classes.
Task 4: We scrape 320 tweets containing the name of Greek movie director, Yorgos Lanthimos along with positive sentiment words. We reserve 200 of them for training and the remaining 120 for testing. Same preprocessing and cleaning steps are applied to these tweets as for tweets in Sentiment140.
Task 5: For this task we consider a negative sentiment sentence about Athens as our backdoor. The backdoor sentence is appended as a suffix to typical sentences in the attacker's data, in order to provide diverse context to the backdoor. Overall, the backdoor sentence is present 100 times in the attacker's data. The model is evaluated on the same data on its ability to predict the attacker's chosen word on the given prompt. Note that these settings are similar to [13]. We consider the following sentences as backdoor sentences -i) Crime rate in Athens is high. ii) Athens is not safe. iii) Athens is expensive. iv) People in Athens are rude. v) Roads in Athens are terrible.
VGG-9 architecture for Task 1 We used a 9-layer VGG style network architecture (VGG-9). Details of our VGG-9 architecture is shown in Table 2. Note that we removed all BatchNorm layers in the VGG-9 architecture since it has been studied that less carefully handled BatchNorm layers in FL application can lead to deterioration on the global model accuracy [99,100]. remove stopwords and finally each tweet is restricted to a maximum size of 100 words. Smaller tweets are padded appropriately. For the Reddit dataset we use the same preprocessing as [13]. Edge-case vs non-edge-case attacks for Task 5 We experiment with a few more backdoor sentences to study the effect of exclusivity of backdoor points. Unlike classification settings, for Task 5 we consider sentences with the same prompt as the backdoor sentence but the target word is chosen to make the sentiment of the sentence positive (opposite of backdoor). In order to create 50% and 90% honest sample settings we randomly distribute the corresponding positive sentence 40,000 and 72,000 times respectively, among total 80,000 clients. Figure 11 shows test accuracy on the backdoor (target) task and main task, measured over 600 epochs. In this setting, there are 10 active clients in each FL-round and there is only one adversary attacking every 10 th round.
Effectiveness of the edge-case attack on the EMNIST dataset Due to the space limit we only show the effectiveness of edge-case attacks under various defense techniques over Task 1 and Task 4. For the completeness of the experiment, we show the result on Task 2 in Figure 13.
We have discussed the effectiveness of white-box and black-box attacks against SOTA defense techniques. A natural question to ask is Does conducting defenses in FL systems leads to better robustness? We take a first step to answer this question in this section. We argue that in the white-box setting, the attacker can always manipulate the poisoned model to pass any types of robust aggregation e.g. the attacker can explicitly minimizes the difference among the poisoned model and honest models to pass RFA, K and M-K. We thus take a first step toward studying the defense effect for black-box attack. The results are shown in Figure 14. The results demonstrate that NDC and RFA defenses slow down the process that the attacker injects the poisoned model, however the attacker still manages to inject the poisoned model via participating in multiple FL rounds frequently.
Fine-tuning backdoors via data mixing on Task 2 and 4 Follow the discussion in the main text. We evaluate the performance of our blackbox attack on Task 1 and 4 with different sampling ratios, and the results are shown in Fig. 15. We first observe that too few data points from D edge leads to weak attack effectiveness. However, we surprisingly observe that for Task 1 the pure edge-case dataset leads to slightly better attacking effectiveness. Our conjecture is this specific backdoor in Task 1 is easy to insert. Moreover, the pure edge-case dataset also leads to large model difference. Thus, in order to pass K and other SOTA defenses, mixing the edge-case data with clean data is still essential. Therefore, we use the data mixing strategy as [13] for all tasks.
Proof. In this proof we will "attack" a single layer, i.e., we will perturb the weights of just a particular layer, say l. If the original network is denoted by W ⇤ (W 1 , . . . , W l , . . . , W L ), then the perturbed network is given by W 0 ⇤ (W 1 , . . . , W 0 l , . . . , W L ). Looking at the following equations,
and
we can see that such a W 0 l would constitute a successful backdoor attack. This is because for non-backdoor data points, that is x j 2 D, the output of the l-th layer of W 0 is the same as the output of the l-th layer of W; and because all the subsequent layer remain unchanged, the output of W 0 is the same as the output of W. For the backdoor data points, note that W l (x j + "(x j )) (l) is exactly the output of the l-th layer on the adversarial example. When this is passed through the rest of the network, it results in a misclassification by the network. Therefore, ensuring W 0 l x (l) j ⇤ W l (x j + "(x j )) (l) together with the fact that the rest of the layers remain unchanged, implies that W 0 misclassifies x j for x j 2 D edge . Define l :⇤ W l W 0 l and " (l) j :⇤ (x j + "(x j )) (l) x (l) j . Substituting l and "
(l) j in the Eq. ( 1), (2), we get
Further, since kW i k 1 for all 1 i L and the ReLU activation is 1-Lipschitz, we have that k"
(l)
WLOG assume that the first |D edge | data points are edge-case data followed by the rest. Then, equations (3), (4) can be written together as
where
is the matrix which has the first kD edge k columns as "
(l) j corresponding to the edge-case data points x j , and the remaining kD k columns are identically the 0 vector. Thus one solution of Eq. ( 6) which is in particular, the minimum norm solution is given by
Recursively applying the definition of operator norm, we have
where the second inequality follows from the fact that operator norm is upper bounded by Frobenius norm.
To bound the last term, write X (l) ⇤ U (l) Σ (l) V > (l) where U (l) 2 R n⇥n , V (l) 2 R d l 1 ⇥d l 1 are orthogonal and Σ (l) 2 R n⇥d l 1 is the diagonal matrix of singular values. Then,
Substituting this into Eq. ( 7) and noting that kW l k 1 gives us the upper bound in the theorem.
For the lower bound we subtract Eq. (3) from Eq. ( 4) to get
Again, by definition of the operator norm, this gives
Taking the maximum over the right hand side above gives the lower bound in the theorem.
We note that the above proof immediately extends to the untargeted case. In the targeted attack setting we have y i as the target for each x i 2 D edge . In the untargeted case, we simply ask that x i is classified as anything other than some ŷi (true label). Therefore, choosing some fixed y i , ŷi gives us the desired untargeted attack. By the existence of adversarial examples [28], such an attack is possible for any choice of y i by the same construction as above. And therefore, it honors the same bounds.
Proposition 1 (Hardness of backdoor detection -I). Let f : R n ! R be a ReLU and g : R n ! R be a function.
Then 3-S can be reduced to the decision problem of whether f is equal to g on [0, 1] n . Hence checking if f ⌘ g on [0, 1] n is NP-hard.
Proof. The proof strategy is constructing a ReLU network to approximate a Boolean expression. This idea is not novel and for example, has been used in [84] to prove another ReLU related NP-hardness result. Nonetheless, we provide an independent construction here.
Let us define B as the following decision problem. Given an instance of B with functions f , g the answer is Yes if there exists some x 2 [0, 1] n such that f (x) , g(x) and No otherwise. We will reduce 3-S to B. Towards this end, assume that we are given a 3-S problem with m clauses and n variables. Note that n 3m and m 2n 3 , that is both are within polynomial factors of each other. Therefore, the input size of the 3-S is poly(m). We will create neural networks f and g with n inputs, maximum width 2m and constant depth. The weight matrices will have dimensions at most max{2m, n} ⇥ max{2m, n} ⇤ poly(m) ⇥ poly(m) and similarly the bias vectors will have dimensions at most poly(m). Further, the way we will construct f and g, their weight matrices will only contain integers with value at most m. This means that each integer can be represented in O(log(m)) bits. Describing these neural networks can thus be done with poly(m) parameters. Thus, the input size of B is also poly(m). For now, assume that f and g are created (in poly(m) time) such that f . g on [0, 1] n if and only if the 3-S is satisfiable. Then, we have shown that if an algorithm can solve B in poly(m) time, then S can also be solved in poly(m) time; or in other words we have reduced 3-S to B. Thus, all that remains to do is to construct in poly(m) time, f and g such that f . g on [0, 1] n if and only if the 3-S is satisfiable.
We will describe how to create the ReLU for f . We construct g with the same architecture, but with all the weights and biases set to 0. Thus the question of f ⌘ g on [0, 1] n becomes f ⌘ 0 on [0, 1] n . Further f would be such that f . 0 if and only if the 3-S is solvable. Essentially, the construction will try to create a ReLU approximation of the 3-S problem.
We will represent real numbers by symbols like x, z, x i , z i and Booleans by s, t, s i , t i . The real vector [x 1 , . . . , x n ] > will be denoted as x. Similarly we will represent Boolean vector [s 1 , . . . , s n ] > as s.
Let the 3-S problem be h : Again, roughly speaking we want f i (x) to approximate ' 3 j⇤1 t i, j and f (x) to approximate h(s). The decomposition of f above is written just for ease of understanding, but in its following form, we can see that it can be computed in 2 layers and width 2m, using b x i and
Clearly, f and g are identical in terms of zeroth and first order information on the entire region [0, 1] n except for B. Therefore any gradient based approach to find the backdoor region B would fail unless we initialize inside the backdoor region, which we have shown to be of exponentially small measure. ⇤
https://github.com/Jefferson-Henrique/GetOldTweets-python https://github.com/pytorch/examples/tree/master/mnist https://pytorch.org/docs/stable/torchvision/models.html