FABA: An Algorithm for Fast Aggregation against Byzantine Attacks in Distributed Neural Networks

1 Introduction

With the rapid development of deep learning, the neural network model becomes more complicated and deeper [Ba and Caurana, 2013]. For example, GoogleNet [Christian Szegedy et al., 2015] contains a 22-layer deep CNN (Convolutional Neural Network) and 4 million parameters, ResNet152 [Kaiming He et al., 2016] has 152 layers, which can handle more sophisticated deep learning tasks and achieve better performance than human beings on ImageNet [Jia Deng et al., 2009]. Recent teams in 2016 even built a 1207-layer deep neural network on ImageNet to get better performance. However, deeper neural networks bring a huge challenge to computation due to the computation of millions of parameters. In addition, training a neural network often involves many rounds of computation based on different hyperparameters to find a better model; this process becomes even more time consuming. Although people start to use better hardware such as GPU and TPU [Norman P. Jouppi et al., 2017] on tensor computation, which accelerates the training process, it is very common to take several days or weeks to train usable neural networks.

Distributed neural network is proposed to solve this problem [Dean et al., 2012; Abadi et al., 2016]. In neural network training, stochastic gradient descent algorithm runs on a training dataset to update a model. The batch size is the number of training samples to work through before the model's parameters are updated. People usually choose a large batch size to achieve better stability and faster convergence [Keskar et al., 2016]. Indeed distributed training is well suited for training with a large batch size because it is easy to parallelize the same computation on different workers. In practice, most distributed training schemes are based on model parallelism, in which each worker keeps a copy of the model and performs the computation on their assigned dataset. A parameter server aggregates the gradients computed by the workers, updates the weights and sends back the updated weights to the workers in each iteration. When the batch size is large, e.g., 512, if we have 16 workers, each worker only needs to compute a batch size of 32. Thus, this approach will significantly reduce the computation time and the memory usage on each worker.

In a distributed neural network, one severe problem is to deal with a malicious worker, e.g., if some workers upload completely wrong gradients, what should we do to resist this kind of attack? We call networks under this kind of attacks as Byzantine distributed neural networks. Byzantine problem was first proposed by [Lamport et al., 1982], and Blanchard et al. first solved this problem in a deep learning scenario [Blanchard et al., 2017]. They proposed an original method called Krum, which selects a gradient from all the uploaded gradients with the lowest predefined score to resist Byzantine attacks in synchronous distributed training. They also proposed a method to resist asynchronous Byzantine attacks [Damaskinos et al., 2018]. There are some other following work using various kinds of medians such as geometric median, marginal median, mean-around-median [Xie et al., 2018], coordinate-wise median [Yin et al., 2018; Chen et al., 2017] or more complicated modification of median methods such as ByzantineSGD [Alistarh et al., 2018]. However, all these methods have a common weakness: they drop a lot of useful information to keep the convergence and correctness of the training. For example, Krum selects only one gradient out of n gradients. Apparently the algorithm loses lots of information because we simply discard most of the gradients. Accordingly, it has almost no improvement compared to training on a single machine even though multiple machines are used for distributed computation. Furthermore, although Krum gives an excellent convergence proof, its assumptions are too strong to satisfy in reality.

In this paper, we proposed an efficient algorithm, FABA, to resist Byzantine attack in distributed neural networks. In summary, our contributions are:

• We proposed an efficient and effective algorithm, FABA, which defends against Byzantine attacks. Our algorithm is very easy to implement and can be modified in different Byzantine settings. More importantly, our algorithm is fast to converge even in the presence of Byzantine workers. Our algorithm can adaptively tune the performance based on the number of Byzantine workers.
• We proved the convergence and correctness of our algorithm. Mainly, we proved that the aggregation gradients by our algorithm are close to the true gradients computed by the honest workers. We also proved that the moments of aggregation gradients are bounded by the true gradients. This ensures that the aggregation gradients are in an acceptable range to alleviate the influence of the Byzantine workers.
• We simulated the distributed environment with Byzantine attacks by adding artificial noise to some of the uploaded gradients. We trained LeNet [Yann Lecun et al., 1998] on MNIST dataset and VGG-16 [Simonyan and Zisserman, 2014], ResNet-18, ResNet-34, ResNet-50 [Kaiming He et al., 2016] on CIFAR-10 dataset [Krizhevsky, 2009] in the Byzantine distributed environment and the normal distributed environment to compare their results. Experiments showed that our algorithm could reach almost the same convergence rate as the non-Byzantine cases. Compared with Krum algorithm, our algorithm is much faster and achieves higher accuracy.

2 ProblemDefinition and Analysis

In this section, we analyze the Byzantine problem in distributed deep neural network.

2.1 ProblemDefinition

In the synchronous distributed neural network, it assumes that we have n workers, worker1, worker2, · · · ,workern and one parameter server PS, which handles the uploaded gradients. Each worker keeps a replicated model. In each iteration, each worker trains on its assigned dataset and uploads the gradients g1, g2, · · · , gn to the PS. The PS aggregates the gradients by average or other methods and then sends back the updated weights to all the workers as follows:

Here wt and γt are respectively the model weights and learning rate at time t. A(·) is an aggregation function that is usually an average function in classic distributed neural networks. Lastly, gi is the uploaded gradient. The Byzantine faults may occur when some workers upload their gradients. These Byzantine workers upload poisonous gradients that could be caused by malicious attacks or hardware computation errors, which means the uploaded gradient gi may not be the same as the actual gradient gi. The generalized Byzantine model that is defined in [Blanchard et al., 2017; Xie et al., 2018] is:

Definition 1 (Generalized Byzantine Model).

We assume that there are at most α·n Byzantine workers in this distributed system where α < 0.5. We also assume that the Byzantine attackers have a full knowledge of the entire system.

2.2 Byzantine Cases

We summarize the cases that Byzantine failures may occur as: (i) workers are under attacks; (ii) workers are dishonest; (iii) hardware faults cause computational faults; (iv) network communication problem. We believe that (i) and (ii) are most severe cases. Since we assume that the Byzantine workers have a full knowledge of the entire system, the Byzantine worker can manipulate the aggregated results to control the convergence. Theoretically, we have:

Theorem 1. The byzantine worker can control the convergence of the distributed training.

Proof. Because of (1) and that A(·) is an average function, without loss of generality, we assume worker1 is a Byzantine worker. It only needs to upload g1 = n · r - g2 - · · · - gn so that the aggregation result A(g1, g2, · · · , gn) = r. Therefore, it can control the training process by choosing the appropriate uploaded gradient so that the aggregated gradient becomes an arbitrary r.

Since the Byzantine attack is harmful, we will introduce FABA to resist Byzantine attacks in the next section.

3 AlgorithmDetails

In this section, we will discuss how FABA works and the convergence proof.

3.1 FABAOverview

We know that if the Byzantine gradients are very close to the average of honest gradients, the attack has almost no harm. Our proposed method is based on the observation that (i) most of the honest gradients do not differ much, and (ii) attack gradients must be far away from the true gradients in order to successfully affect the aggregation results. Note that the honest gradients are computed by the average of mini batch dataset in each honest worker. By Central Limit Theorem, as long as the mini batch size is large enough and the dataset on each worker is randomly selected, the gradients from different workers will not differ much with high probability. We propose Algorithm 1 based on these observations.

Algorithm 1 shows that in each iteration the parameter server (PS) discards the outlier gradients from the current average. Previous methods such as Krum keep only one gradient no matter how many Byzantine workers are present, which significantly impacts the performance. Our algorithm, instead, can easily adjust the number of discarded gradients based on the number of Byzantine workers. That is, the performance will improve when the number of Byzantine workers is small.

Algorithm 1 FABA (PS Side)

Input:

The gradients computed from worker1, worker2, · · · ,

workern: Gg = {g1, g2, · · · , gn}; The weights at time t: wt; The learning rate at time t: γt; The assumed proportion of Byzantine workers: α;

Initialize k = 1.

Output:

The weights at time t + 1: wt+1.

• 1: If k < α · n, continue, else go to Step 5;
• 2: Compute mean of Gg as g0;
• 3: For every gradient inGg, compute the difference between g0 and it. Delete the one that has the largest difference from G;
• 4: k = k +1 and go back to Step 1;
• 5: Compute the mean of Gg as the aggregation result at time t At;
• 6: Update wt+1 = wt - γt · At and send back the updated weights wt+1 to each worker.

3.2 Convergence Guarantee

Next we show that Algorithm 1 can ensure that the aggregation results are close to the true gradients. Mathematically, we have Lemma 1.

Lemma 1. Denote honest gradients as g1, g2, · · · , gm and Byzantine gradients as a1, a2, · · · , ak and m+ k = n. Let gtrue = 1m ∑mi=1 gi. If we assume that ∃ϵ > 0, ||gi - gtrue|| < ϵ for i = 1, 2, · · · ,m. Then after the process from Algorithm 1, the distance between the remaining gradients and gtrue is at most ϵ 1-2α .

Proof. As Figure 1 shows, the blue stars are honest gradients, and the red stars are Byzantine gradients. gattack is defined as the average of the attack gradients, i.e., gattack = 1k ∑ki=1 ai. Here, gmean is the mean of all uploaded gradients from workers, i.e., gmean = 1n (∑mi=1 gi+ ∑ki=1 ai). In Figure 1, all the blue stars lie in the ball with the center of gtrue and radius of ϵ. It is obvious that we can compute gmean, but we do not know the value of gtrue and gattack.

We first compute the position of gmean. It is apparent that gmean lies on the line connecting gtrue and gattack. Because the assumption that the proportion of Byzantine workers is no more than α, here we assume that the number of Byzantine workers is exactly α·n, so gmean = (1-α)·gtrue+α·gattack. Denote the distance between gtrue and gattack is l, then the distance between gmean and gtrue is α · l and the distance between gmean and gattack is (1 -α) · l.

Let us talk about two cases here:

• If l > ϵ 1-2α , this is equivalent to

(3) means the gmeangattack is larger than gmeangtrue+ϵ. In the description of Algorithm 1, we are going to delete gradient from one worker which is farthest from gmean. In this case, because all the gradients in the ball are closer to gmean than α · l + ϵ, and as we know, gattack is the average of all attack gradients, ∃i ∈ {1, 2, · · · , k}

(4) means in this case, the gradient we delete is from Byzantine worker.

• If l < ϵ 1-2α , we cannot ensure whether the gradients that we delete are from Byzantine workers. However, we can guarantee that if we delete gradients from the honest workers, the remaining gradients are no more than ϵ 1-2α from gtrue, because the gigmean < α · l + ϵ, if we delete gradients from an honest worker rather than from an Byzantine worker, the distance between gradients of Byzantine worker and gmean must be smaller than α · l + ϵ. In this case, all the remaining gradients are within a ball with the center as gtrue and the radius as l < ϵ 1-2α .

Combining these two cases, we have the conclusion that the gradients we delete must (i) come from Byzantine workers or (ii) come from an honest worker, but all the remaining gradients are within ϵ 1-2α distance to gtrue.

As we repeat this process α · n times, if the gradients we delete are only from Byzantine workers, all the gradients remaining are from honest workers. Otherwise, if one of the gradients we delete is from Byzantine workers, then all the remaining gradients are in such a ball as described before.

Lemma 1 ensures that aggregation results from the uploaded gradients are close to true gradients; ϵ 1-2α is similar to ϵ when α is not very close to 0.5. This intuitively ensures the convergence of Algorithm 1. But to prove it, next we also need to guarantee that the lower order moments of the aggregation results are limited by true gradients. Theoretically, we have Lemma 2.

Lemma 2. Let the aggregation results that we get from Algorithm 1 at time t are At and denote G as the correct gradients estimator. If we assume ϵ < C · ||G|| while C is a small constant, for r = 2, 3, 4, E||A||r is bounded above by a linear combination of terms E||G||r1 ,E||G||r2 , · · · ,E||G||rl with r1 + r2 + · · · + rl = r and l ≤ n - ⌈α · n⌉ + 1.

Proof. After we proceed Algorithm 1, we delete α · n gradients; assume that the gradients left are g(1) , g(2) , · · · , g(p)

and p = n-⌈α·n⌉. From Lemma 1, we have ||g(i)-gtrue|| ≤ ϵ 1-2α for i ∈ {1, 2, · · · , p}. We know from Algorithm 1 that

There are at most α·n attack gradients left here. Without loss of generality, we assume that the last α · n gradients are from attack workers. By triangle inequality, (5) is bounded By

So we have

We make an expectation on both sides, and get

Now we have the convergence of Algorithm 1.

Theorem 2. We assume that (i) the cost function cost(w) is three times differentiable with continuous derivatives and non-negative; (ii) the learning rates satisfy ∑t γt = ∞ and ∑t γ 2 t < ∞; (iii) the gradients estimator satisfies EG = ∇Cost(w) and ∀r = 2, 3, 4,E||G||r ≤ Ar + BR||w||r for some constants Ar, Br; (iv) ϵ < C · ||G|| and C is a relatively small constant that is less than 1; (v) let θ = arcsin ϵ (1-2α)gtrue , beyond the surface ||w||2 > D, there exists e > 0 and 0 ≤ ψ < π2 - θ, s.t.

Then the sequence of gradients ∇Cost(wt) converges almost surely to 0.

Proof. This proof follows Bottou's proof in [Bottou, 1998] and the proof of Proposition 2 in the supplementary material of [Blanchard et al., 2017] with some modifications.

Condition (v) is complicated, so we use Figure 2 to clarify it. The dotted circle means the ball that all honest gradients lie in. By Lemma 1, At is in the ball whose center is gtrue and radius is ϵ 1-2α . This assumption means that the angle between wt and gtrue is less than ψ while ψ < π2 - θ.

We start with showing the global confinement within the region ||w|| ≤ D.

(Global confinement). Let

We denote ut = φ(||wt||2 ).

Because φ has the property that

We have

Denote ϱt as the σ-algebra that represents the information in time t. We can get the conditional expectation as

By Lemma 2, there exist positive constants X0, Y0, X, Y such that

The first term in the right is 0 when ||wt||2 < D. When ||wt||2 ≥ D, because of Figure 2, we have

So we have

For the following proof we define two auxiliary sequences µt = ∏t-1 i=1 1 1+γ 2 i Y ---→ t→∞ µ∞ and u′t = µtut.

Because of (8), we can move γ 2 t Y ·ut to the left and we get

Define an indicator function χt as

Then we have

By the quasi-martingale convergence theorem [M´etivier, 2011], (9) implies that the sequence u′t converges almost surely, which also implies that ut converges almost surely, that is, ut → u∞.

If we assume u∞ > 0, when t is large enough, we have ||wt||2 > D and ||wt+1||2 > D, so (7) becomes an equality. This means that∞∑

Since we have φ′ (||wt||2 ) converge to a positive value and in the region ||wt||2 > D, by the condition (iv) and (v), we have

This contradicts the condition (ii). So we have the ut converge to 0, which gives the global confinement that ||wt|| is bounded. As a result, any continuous function of wt is bounded.

(Convergence) Once we proved that wt is bounded, the rest convergence part proof is the same as Bottou's proof in [Bottou, 1998]. Thus we proved Theorem 2.

3.3 Remarks

First, in our assumption, we assume ϵ < C · ||G|| and C is a relatively small constant. This condition guarantees that all the gradients from the honest workers gather together and their difference is small. This condition is easy to satisfy when the dataset that each worker get is uniformly chosen and batch size is not very small. In most cases that distributed training implements, the dataset is given by the PS and each worker gets one slice of the entire dataset, thus it is almost uniformly distributed. However, in other distributed training scenarios, such as different workers keep their own secret datasets, the distribution of the datasets is unknown. As a result of that, each dataset can be biased, and thus condition (iv) is not necessarily satisfied. We leave this for future work.

Second, we proved that the remaining gradients processed after Algorithm 1 is within ϵ 1-2α to the true average gradient in Lemma 1, so after taking the average, the aggregation results are also within ϵ 1-2α to it. Note that each honest worker is within ϵ distance and each honest worker can get convergence on their own. This intuitively shows the correctness of our algorithm. In fact, if the Byzantine worker ratio is less than 14 , this radius becomes 2ϵ. If the ratio is less than 18 , this radius is 43 ϵ. This is very close to ϵ. In practice, the ratio of Byzantine workers is usually not high, which means our algorithm has good performance in these scenarios.

Third, if we combine the first two remarks and θ = arcsin ϵ (1-2α)gtrue , θ must be small here. In Figure 2, we know that condition (v) ensures that the angle between wt and gtrue is less than a fixed ψ that ψ < π2 - θ. Since the value of α and condition (iv) guarantee that the θ is small, condition (v) is easy to satisfy. This is different from the assumption of Krum. In fact, their assumptions are difficult to satisfy because the radius of the circle is too large since it is related to the number of the dimensions in weights. In our algorithm, condition (v) becomes similar to the condition (iv) in Section 5.1 in [Bottou, 1998], which guarantees that beyond a certain horizon, the update terms always moves wt closer to the origin on average.

In the end, our algorithm keeps (1-α)n gradients to aggregate. This maintains more information than previous methods. Moreover, in practice, if we do not know the number of Byzantine workers, we can simply change the number of iterations adaptively in Algorithm 1 to test whether we have the right estimate. In the beginning, we can choose a small number of iterations k for better performance. When it seems to have more Byzantine workers, correspondingly we can increase k to tolerate more Byzantine attacks. This can be done during the training process, making it more flexible to balance the tradeoff between performance and correctness.

4 Experiment

In this section, we are going to run our FABA in a simulated Byzantine environment on MNIST dataset and CIFAR10 dataset. We chose the Byzantine proportion as 0.3, which means 30% of the total workers are under attack and upload noise as gradients. In the experiment, wo chose uniform and Gaussian distribution to generate the attack gradients. Because the results are similar, here we only show the results with uniform distribution in (-0.25, 0.25). This means each coordinate in the Byzantine gradients is generated by a uniform random number from (-0.25, 0.25). Here, we only compared FABA with Krum because in [Xie et al., 2018], it is shown that the median methods and Krum have similar convergence rate.

4.1 MNIST

We deployed a 32-worker environment on a server with 44 cores Intel E5-4669v4 and 792 GB RAM. Because we only need to simulate the distributed environment with Byzantine workers, we did not deploy this distributed environment on several machines. We used a single machine with multiple cores to simulate this environment on CPU. Since the Byzantine proportion is 0.3, 9 out of 32 workers are Byzantine workers.

We respectively implemented our algorithm and Krum on a LeNet network in this Byzantine environment. Each worker was trained using a batch size of 4, so the total batch size is 128. Because MNIST converges quickly, we only trained 10 epochs here. For our algorithm and Krum algorithm, the results are shown in Table 1.

As shown, our algorithm converges much faster than Krum. We also plotted the loss change every 100 iterations in Figure 3. The loss change is much larger in Krum than our algorithm, which shows our algorithm is more stable than Krum. Although it finally converges, it is more unstable. This is easy to understand because it only uses the gradient from a single machine, whose batch size is 4 while our algorithm use a batch size of 4 × (32 - 9) = 92. A large batch size will lead to a faster and stable convergence.

4.2 CIFAR-10

We trained CIFAR-10 respectively on VGG-16, ResNet-18, ResNet-34 and ResNet-50 networks. Since these neural networks are complicated and really slow to train in CPU environment, we redeploy an 8-worker environment on a Google Cloud instance with 8 vCPUs, 30 GB memory and 8 NVIDIA Tesla K80 GPUs. Here, we still chose the Byzantine proportion as 0.3. Each worker was trained using a batch size of 32, so the total batch size was 256. Each GPU kept a same model and was thought as a worker. We used learning rate 0.01, momentum alpha 0.9 and weight decay as 5 × 10-4 for 80 epochs. We trained these models on Byzantine environment respectively using our algorithm and Krum. We also compared these results with the same distributed environment in the non-Byzantine setting. Because the results for different networks are similar, we only show the result in ResNet-18. The results are shown in Figure 4. Here we use top-1 accuracy to compare their performance.

Figure 4 shows the accuracy change through the epochs. It is obvious that in this setting, our algorithm is much faster than Krum and even reaches a higher top-1 accuracy. It also shows that our algorithm achieves almost the same speed as the non-Byzantine distributed training without Byzantine attack, while there is only one or two epochs behind and the final accuracy is almost the same. Figure 5 is the loss change every 100 iterations. As we can see, our algorithm is almost the same as the case without Byzantine, while Krum is much more unstable than our algorithm. This shows that our algorithm is enough to resist Byzantine worker.

5 Conclusion

As distributed neural networks become much more popular and are being used more widely, people are beginning to enjoy the efficiency and effectiveness brought by neural networks. However, such networks are also subject to Byzantine attacks. In this paper, we proposed FABA to defend against Byzantine attacks in distributed neural networks. We proved the convergence of our algorithm. Experiments demonstrate that our algorithm can achieve approximately the same speed and accuracy as in the non-Byzantine settings, and the performance is much better than previously proposed methods. Additionally, FABA can extract more performance gain (by retaining more gradients) depending on the number of Byzantine workers compared with the prior work. It is easy to tune the algorithm based on the number of Byzantine workers. We believe this elegant algorithm can be widely used in distributed neural networks to defend against Byzantine attacks.

Acknowledgements

The authors would like to thank all the reviewers for their helpful comments. This project was supported in part by US National Science Foundation grant CNS-1816399.