基于模型聚合的去中心化拜占庭魯棒算法

盧朕，李建業，董云泉

(南京信息工程大學 電子與信息工程學院，江蘇 南京 210044)

近年來，隨著5G網絡的高速發展以及物聯網技術的廣泛應用，移動設備的便攜化和智能化已經是大勢所趨，使用機器學習對移動設備的用戶數據進行處理可提高應用程序的智能化，方便人們的日常工作與生活.然而，傳統的機器學習算法需要中央服務器對用戶數據進行集中處理，不僅會耗費大量通信資源，而且存在數據泄露風險，使用戶隱私安全產生隱患.聯邦學習(federated learning,FL)作為旨在提高通信效率和隱私性的新興機器學習范式，可以讓資源受限和地理分散的設備，利用本地數據合作訓練全局模型，同時避免直接交換用戶數據.其中最經典的算法是聯邦平均(FedAvg)算法[1]，在中央服務器上重復聚合用戶的本地訓練模型來生成性能優秀的全局模型.在聯邦學習中，用戶數據的處理和分析只在設備終端進行，終端用戶傳遞的信息（本地梯度或者本地迭代值）使得竊聽方即使獲得傳遞的信息也不可能立刻推斷出用戶數據，以保護用戶隱私.

傳統的集中式聯邦學習[1-2]雖然提高了數據隱私和通信效率，但存在擴展性差、帶寬高、單點故障等問題.此外，新一代通信網絡采用去中心化的無基礎設施通信方案和設備到設備的多跳鏈接技術以提高通信能力[3].為了解決上述困境，去中心化的聯邦學習[4-7]被提出，然而由于聯邦學習數據存儲的特殊性以及對通信效率的考慮，許多分布式機器學習方法并不適用于去中心化聯邦學習.同時，聯邦學習由于其分布式機器學習的本質，在面對對手攻擊時更加脆弱.拜占庭攻擊[8]是聯邦學習面臨的一種最常見的威脅，亟須設計一種“可證”為安全的拜占庭魯棒算法.在傳統聯邦學習中，通常假設所有參與聯邦訓練的終端都是“誠實”的，即所有傳遞給中央服務器的消息都是真實可靠的.然而，在實際情況中上述假設并不成立，某些終端可能因為網絡環境或者被惡意程序操控而發送錯誤信息.

在集中式聯邦學習領域中，有關拜占庭魯棒的分布式優化研究，已經取得了一系列成果[9].拜占庭節點傳遞給中央服務器的惡意信息通?！斑h離”真實信息，因此中央服務器可以借助安全聚合機制來聚合真實的信息，減少錯誤信息對聯邦學習的影響.利用安全聚合機制，誕生了許多拜占庭容錯梯度聚合算法[10-14]，但這些算法都需要中央服務器對候選節點上傳的梯度統計信息進行處理且計算復雜度較高，難以取得實際應用.Tahmasebian等[15]結合真值推理方法和歷史統計數據來估計每個客戶端的可靠性，提出基于客戶端可靠性的魯棒聚合算法.Xie等[16]提出的完全異步算法借助驗證數據集，利用中央服務器對候選梯度進行打分，挑選誠實梯度.然而，在去中心化聯邦學習中，無法使用中央服務器來過濾惡意信息并聚合真實信息.So等[17]提出BREA聯邦學習框架，集成隨機量化、可驗證的異常值檢測和安全模型聚合方法，保證框架的拜占庭彈性、隱私和收斂性.Wang等[18]提出點對點算法P2PKSMOTE，共享參與FL的不同客戶端的合成數據樣本，并用于訓練異構場景下的異常檢測機器學習模型.受Kang等[19]的基于聲譽和區塊鏈的可靠用戶選擇方案啟發，Gholami等[20]提出基于Trust度量的數學架構來衡量代理用戶的信任度，提高去中心化聯邦學習的安全性.同樣，Zhao等[21]使用區塊鏈代替中央服務器聚合局部模型更新，并利用區塊鏈上的記錄不可篡改和可以追溯的優勢，保障用戶隱私安全.Lu等[22]將本地模型存儲在用戶子集，實現了物聯網場景下的去中心化異步聯邦學習，并采用深度強化學習(deep reinforcement learning,DRL)進行節點選擇，以提高效率.然而，法律法規和能源消耗及其他因素限制了區塊鏈技術的實際應用.

針對以上問題，本研究探討在去中心化聯邦學習中如何應對拜占庭用戶的問題.在一個去中心化網絡中，拜占庭用戶數量未知，攻擊方式不明，通過先發送后驗證的策略和SCORE函數，來評估未知屬性用戶的屬性.同時，利用得分函數的結果來進行閾值劃分以降低用戶屬性分類的錯誤率，提高計算資源的利用率.

1 系統模型

1.1 網絡模型

考慮在N個代理用戶(節點)組成的網絡上執行聯邦學習任務，其中惡意節點數量未知.在此去中心網絡中，無中央服務器且每個用戶i只能與它們的通信范圍內的多個鄰居節點逐次相互通信.所有用戶可被編號以記為一個集合V，V={1,···,N}.這個網絡可以被建模為有向圖G(V,E)，其中V為網絡中節點的集合，E為網絡中邊的集合，E?{(i,r)∈V×V|i≠r}.同時，每個代理用戶i擁有自身 的數據 集Di，|Di| 表示用戶數據集的大 小.訓練所用數據樣本總數為其中第d個樣本為為輸入模型的樣本數據而為對應于輸入樣本的標簽.假設由代理用戶i采集的數據樣本點的索引集為pi，基于上述條件，可以利用本地采樣數據集zi={(xd,yd),d∈pi} 訓練由θi參數化 的代理用戶i的本地模型Mi，如圖1所示.

圖1 去中心化網絡模型Fig.1 Decentralized network model

1.2 聯邦學習模型

在集中式聯邦學習中，通過在中央服務器上優化目標函數，尋找解決推斷問題的全局模型，這個模型把輸入的樣本數據向量x映射到輸出為輸出結果維數.在去中心化聯邦學習中，每個用戶不僅擁有各自的數據集，而且還共享一個由 θ 參數化的有著固定架構的機器學習全局模型.這個全局模型的目標是解決如下經驗風險最小化問題：

式中：fi(θ) 為用戶i的本地經驗風險函數，l(θ;zi) 為參數 θ 在數據樣本zi上的經驗損失.

1.3 拜占庭攻擊模型

對于固定用戶網絡上的去中心化聯邦學習，它的模型聚合路線是既定的.未經身份認證的惡意節點可能發起拜占庭攻擊，它試圖在未訓練模型的情況下發送本地模型，從而改變模型聚合路線，影響用戶對模型聚合路線的共識，最終導致全局模型的實際訓練過程偏離正確方向，進而影響全局模型的評估能力[23].在一個固定用戶網絡上的去中心化網絡中，在無拜占庭節點時，擬定一條聯邦學習模型訓練和傳輸的路線：1→2→3→···→20，如圖2所示，每個節點利用私有數據集對接收到的模型參數進行本地訓練，并將模型參數發送給下一個節點來協作完成聯邦學習任務.所使用的環狀聚合路線，不僅擁有低能耗、延遲低、簡單易實現等優點，而且相較于廣播形式，此種方式能夠降低誠實用戶“暴露”給惡意用戶的風險.

圖2 去中心化聯邦學習中的模型聚合路線Fig.2 Model aggregation route in decentralized federated learning

當此去中心化網絡中存在拜占庭節點時，如圖3所示，假設節點7為惡意節點執行拜占庭攻擊，節點2并未對節點7的屬性進行驗證，惡意節點7接收到節點2發送的模型信息后，發送任意模型信息給節點10，同時謊稱發送的聚合模型來源于誠實節點9.對于節點10，同樣缺乏對節點屬性的驗證手段，無法判斷源于節點7的信息是否符合模型聚合的要求.惡意節點7的拜占庭攻擊不僅會改變模型聚合路線，忽略節點3～6的本地訓練模型，而且其發送的任意信息，會使全局模型的訓練受到惡劣影響.在更嚴重的情形下，模型更新的聚合路線陷入一個死循環，如圖3中的1→2→7→1，模型將只會在這些局部節點訓練，使得全局模型發散或者收斂到局部最優處，導致聯邦學習失敗.

圖3 拜占庭攻擊下的模型聚合路線Fig.3 Model aggregation route under Byzantine attack

1.4 拜占庭攻擊方式

代理用戶使用隨機梯度下降(stochastic gradient descent,SGD)和先發送后驗證的方法在用戶的數據集上優化損失函數以訓練本地模型.在第t輪全局訓練時，用戶i將本地模型參數m(t,i)傳遞給它們的下一跳鄰居用戶i+1.如果用戶i為誠實用戶，其傳遞的模型參數是真實的，即m(t,i)=θ(t,i).然而，惡意用戶傳遞的信息并不是在其本地數據集上運行SGD計算所得到的結果而是任意信息g(t,i).根據文獻[8]中的定義，其表達式如下：

下一跳的用戶在收到上一跳用戶發來的信息后，在本地數據集上執行SGD，并重復以上過程尋找最優全局模型參數 θ*=argminθF(θ).

考慮符號翻轉（sign-flipping attack）攻擊、常數向量攻擊（same-value attack）、高斯噪聲攻擊(Gaussian-noise attack)和標簽反轉攻擊（labelflipping attack）.在符號翻轉攻擊中，拜占庭節點翻轉發送給其他節點的信息（本地梯度或者本地迭代值）的正負號，并且增大其幅度，即g(t,i)=σ×其中σ 為負數.其目的是使得變量往正梯度方向變化，從而使得目標函數增大，破壞訓練過程[24].在常數向量攻擊中，拜占庭節點發送給其他節點的信息是由常數向量構成的，即g(t,i)=c×1，其中1 ∈Rd為每一維都為1的向量，c為常數.其目標是發送相同的虛假消息來誤導其他節點，讓它們做出錯誤的決策.在高斯噪聲攻擊中，拜占庭節點發送給其他節點的信息被高斯噪聲“污染”，即其中n為服從某種高斯分布的隨機擾動.在標簽反轉攻擊中，拜占庭節點并未對發送給其他節點的信息進行修改，而僅對本地訓練數據的特定類別的標簽進行修改，然后再進行訓練.盡管這種攻擊方式只對數據進行投毒，攻擊性較弱，但是它通用性較強，并且攻擊方式簡單，僅須對特定的數據標簽進行改變.

2 方法介紹

由于去中心化的聯邦學習沒有中央服務器的協助，并且普通的代理用戶受限于計算、網絡資源而無法處理大量信息，單個代理用戶接收的受限信息無法相互比較、聚合.此時，基于集中式聯邦學習的安全聚合算法無法適用于去中心化的情況.本研究所提出的可驗證的去中心化FL算法利用SCORE函數來對未知節點的屬性進行評判.

2.1 SCORE函數

在傳統機器學習中，為了驗證一個用戶誠實與否，一個樸素的想法是：在此用戶數據集上執行學習任務并通過任務的表現來判定該節點的屬性.然而受制于聯邦學習中的隱私設置，用戶的個人數據是無法共享的.由Zeno++算法[16]啟發，在由未知數量的拜占庭用戶和誠實用戶所構成的去中心化網絡中進行聯邦學習任務時，誠實用戶可借助驗證數據集和得分函數對下一未知屬性用戶傳遞給它的梯度信息進行“打分”，借此來實現分辨和排除拜占庭用戶的目的.對于任意候選梯度g，利用模型參數 θ、學習率 γ 和常量 ρ (ρ＞0)，可以對SCORE函數進行定義：

式中：fd(θ) 為驗證數據集上的經驗風險函數，此得分函數可被定義為2部分.fd(θ)-fd(θ-γg) 為預估損失函數的梯度下降值，它在某種程度上反映了待驗證節點的屬性信息；-ρ‖g‖2為SCORE函數的懲罰項，它約束了模型參數的變化量.一個更大的損失函數的梯度下降值會導致更大的SCORE得分，也就意味著此節點更有可能是一個誠實節點；相反，當此節點為拜占庭節點時，會阻礙學習任務的進行，相應的SCORE得分較低.這為SCORE函數分辨拜占庭節點與誠實節點提供了理論支撐.

式 (3)會給部分節點帶來較大的計算負擔，在實際情況中，可以對式(3)中的fd(θ)-fd(θ-γg) 進行一階泰勒公式展開和近似計算來減少計算開銷，改進后的SCORE函數如下：

2.2 可驗證的去中心化FL算法

所提出的基于模型聚合的去中心化拜占庭魯棒算法的總體流程如下.此方法預置條件是去中心化網絡起始必須是2個誠實節點，來初始化全局模型參數.

1）在第t輪全局迭代中，第i-2 和第i-1 節點均已是誠實節點且擁有驗證數據集，算法目的是分辨第i節點是否為誠實節點.為此，第i-1 節點發送第i-2 節點的本地模型參數θ(t,i-2)給第i節點.然后，第i節點利用本地數據集和θ(t,i-2)來執行SGD，并將此過程中得到的梯度信息g回傳給第i-1節點.

2）當第i-1 節點接收 到第i節點回傳 的梯度信息g后，其將利用g在驗證數據集上運行SGD，同時結合SCORE函數給出分數.如果存在常數ε使得SCORE函數的 結果滿 足 SCOREγ,ρ(g,θ)≥-γε，則認為第i節點是誠實節點.

3）如果步驟2）判定第i節點是誠實節點，那么第i-1 節點將傳遞自己的本地模型參數θ(t,i-1)給第i節點，第i節點利用 θ(t,i-1)和本地數據集來執行SGD.

重復以上過程，直到最后得到的模型滿足精度要求.

對于偽裝成誠實節點的拜占庭節點，有如下考慮：如果一個待驗證屬性的用戶做出誠實的回答，需要正確的數據集和準確、及時的模型參數.受制于去中心化聯邦學習的設置，不可能對待驗證屬性的用戶的本地數據集進行審查，同時各個參與聯邦學習的用戶是不可能同時獲得模型參數信息并進行同步訓練的，因此只有逐步向待驗證屬性的用戶傳遞不準確和不及時的模型參數來進行學習.一個簡單的方法就是向待驗證屬性的用戶傳遞過時的模型參數來阻止拜占庭用戶直接回傳誠實的梯度進而偽裝自身，這樣做有2個優點：一是操作方便簡單，不需要太過復雜的加密傳遞方式；二是增加了隱私性，即使拜占庭用戶獲得誠實的模型參數，其也不能取得與其直接通信的用戶的相關隱私信息.此方法的缺點是需要節點耗費額外的內存和通信資源來儲存和傳遞這些“過時”的模型參數信息.因此，本研究選擇儲存和傳遞上一個誠實用戶的模型參數信息來降低存儲、通信資源的代價.

在傳統的機器學習中，通常用準確率和風險經驗函數損失值來衡量模型的性能，但在本實驗中僅僅通過這2個指標來評價模型是不充分的，因為在實際場景可能須對用戶的誠實或惡意屬性進行統計分析從而來激勵或懲罰用戶，因此需要其他的標準來評價模型.為此，本研究采用假陽(false positive，FP)和假陰(false negative，FN)分別表示被采用的信息是錯誤信息、被拋棄的信息是正確信息的概率.但是，在算法步驟2）中單獨使用得分函數不足以分辨出惡意節點，因而有必要對得分函數中的預估損失函數的梯度下降值以及懲罰函數值進行閾值比較，以更加精準地分辨出惡意節點與誠實節點.修改后的算法流程如下.

輸入：初始模型參數 θ、用戶數據集、驗證數據集、λt1,λt2,λt3,ρ,γ,ε 等超參數

3 收斂分析

對所提的可驗證的去中心化FL算法分析其誤差界限.首先，需要以下定義與假設.

定義1 光滑性.如果存在常數L＞0 使本地目標函數f(x) 滿足 L 光滑，那么 ?v,w∈Rd，有

定義2 PL不等式.如果存在常數 μ＞0 使得可微函數f(x) 滿足Polyak-Lojasiewicz (PL)不等式[25]，那么 ?x∈Rd，有

式中：f*:=f(x*)，x*=argminf(x).

假設1在整個學習過程中，F(x) 和fd(x) 的梯度均具有上限B1，并假設fd(x) 的梯度具有下限B2，即同時0 ＜B2≤B1.此外，假設訓練數據集與驗證數據集的損失函數的梯度的差值是受限的，即E[‖?F(x)-

借由上述定義與假設，討論本算法的收斂情況.

理論1假設經驗損失函數F(x) 和驗證數據集上的經驗損失函數fd(x) 均是光滑函數且滿足PL不等式，同時滿足假設1.如果有常量 β＞0，使得在經過T輪次的全局迭代后，有以下的誤差界限：

證明如果第i用戶回傳的梯度信息g滿足第i-1用戶上的SCORE函數,即

SCORE(γ,ρ)≥-γε.根據SCORE函數的定義，此結果可以改寫為

對fd(·) 進行泰勒公式展開和近似運算，可以得到

利用二范數性質、梯度受限假設和訓練數據集與驗證數據集的相似假設，可以得到

將式(10)結合光滑性和PL不等式，可以得到

通過迭代和計算整體期望，在經過T輪全局訓練后，可以得到理論1.通過文獻[26]中對正則化經驗風險最小化優化算法的收斂速度的比較方法，本算法的第T輪全局迭代輸出的模型 θ(T,N)與最優模型 θ*的對應的正則化經驗風險的差值趨于0，所以本算法是收斂的.同時，在有界梯度假設下，本算法具有線性收斂速率，這與FedAvg算法[1]以及部分去中心化聯邦學習優化算法[4-7]的收斂速率一致.誤差界限中的超參數 ρ 在收斂速率和用戶梯度取舍之間做出均衡，如果增大 ρ，可以加快算法收斂速度，但可能會拋棄更多的誠實梯度(用戶).

4 數值驗證

通過實驗仿真對所提去中心化聯邦學習算法的性能進行評估.在本實驗中，假設去中心化網絡中節點與節點之間的通信是理想且無損的.

4.1 實驗設置

在本次實驗中，總數據集為CIFAR-10[27]和MNIST[28]，前者包含了60 000張3 2×32 像素的10個類別的自然彩色圖片；后者包含了70 000張28×28像素的0～9數字的手寫灰度圖像.將總數據集中的樣本按照類別和數量隨機平均分配給所有的用戶，即每個用戶數據集都有10個類別的圖片，且每類別的圖片數量相等.同時，采用對所有的用戶數據集樣本進行隨機采樣的方式來構成一個適用于SCORE函數的驗證數據集(在實際場景下，任務發布者無法接觸到用戶的個人數據，為此，可以通過社會實踐、大數據調查以及一些不觸犯用戶隱私的方式來獲取先驗知識，或者直接從受信任的用戶收集信息并添加噪聲來構造驗證數據集).

在一臺裝備了NVIDIA GeForce GTX 1 660 SUPER顯卡的主機上，基于Mxnet[29]平臺，利用卷積神經網絡(convolutional neural networks，CNN)對算法進行實驗仿真.此卷積神經網絡包含4個卷積層和4個全連接層，并在卷積層之間嵌入Batch Norm層和Dropout層來防止神經網絡的過擬合.在實驗過程中，利用測試數據集上的準確率作為衡量模型性能的標準.同時，采用假陽率、假陰率來表示被采用的信息是錯誤信息、被拋棄的信息是正確信息的概率.

4.2 仿真結果

利用實驗仿真來探究拜占庭用戶的數量、拜占庭用戶的攻擊方式以及閾值劃分方式對于可驗證去中心化聯邦學習算法性能的影響.

4.2.1 拜占庭用戶的影響 比較在同樣超參數設置和CIFAR-10數據集下，不同類型的拜占庭攻擊方式和不同數量的拜占庭節點對于算法性能的影響.采用環形網絡下的聯邦學習作為對照算法，該算法不受拜占庭攻擊的影響，記為“理想的去中心化FL”.

首先模擬一個擁有20個節點，其中5個節點執行符號反轉攻擊的去中心化網絡，比較無惡意用戶的情況、存在惡意用戶但執行可驗證的去中心化FL算法的情況和無任何拜占庭容錯算法但存在惡意用戶的情況下的性能.如圖4所示為不同情況下，去中心化聯邦學習在測試集上的準確率.圖中，A為準確率，t為輪次.實驗結果表明，去中心化網絡在面對符號反轉攻擊時十分脆弱，去中心化聯邦學習無法進行收斂，而利用所提出的拜占庭容錯算法后，訓練出的模型甚至可以媲美無攻擊時環形網絡上訓練出的模型.

圖4 25%的用戶執行符號反轉攻擊時不同算法的準確率Fig.4 Accuracy of different algorithms for 25% of users performing sign-flipping attack

為了探究不同數量的拜占庭節點對可驗證的去中心化FL算法的影響，將去中心化網絡中惡意節點數量提高一倍，即有10個拜占庭節點，占節點總數的50%.比較圖4、5，可以發現所提出的算法對于不同數量的拜占庭節點具有魯棒性，盡管惡意節點的數量增加了，但經此算法訓練出的全局模型還能保持良好的性能.

為了探究拜占庭節點的不同攻擊方式對可驗證的去中心化FL算法的影響，將去中心化網絡中惡意節點實施的符號反轉攻擊更改為標簽反轉攻擊，比較圖5、6，發現此方法也可以針對不同類型的攻擊方式進行防御.同時，根據圖5、6中的無任何拜占庭容錯算法但存在惡意用戶的情況下的模型性能的比較，可以發現模型污染攻擊(符號反轉)比數據污染攻擊(標簽反轉)更加直接且高效.

圖5 50%的用戶執行符號反轉攻擊時不同算法的準確率Fig.5 Accuracy of different algorithms for 50% of users performing sign-flipping attack

圖6 50%的用戶執行標簽反轉攻擊時不同算法的準確率Fig.6 Accuracy of different algorithms for 50% of users performing label-flipping attack

4.2.2 閾值劃分的影響 如圖7所示為閾值劃分對FP和FN的影響.可以看出，在相同的數據集和超參數設置下，帶有閾值重劃分的本研究算法在面對符號反轉攻擊和常數向量攻擊時，可以有效降低無閾值重劃分算法訓練出的模型中的假陽和假陰概率.然而，由于閾值重劃分針對的是SCORE函數中的預估梯度的下降值和梯度信息的懲罰值，無法對標簽反轉這類定向攻擊的閾值進行精準劃分，只能小幅減少標簽反轉的模型性能的假陽和假陰概率.

圖7 閾值劃分對假陽率和假陰率的影響Fig.7 Effect of threshold division on false positive and false negative

在相同的CNN、30%的惡意用戶比例和同樣的超參數設置下，將可驗證的去中心化FL算法與一些經典或先進的魯棒FL算法進行比較.如表1所示，展示了這些算法分別在CIFAR_10數據集和MNIST數據集上，面對高斯噪聲攻擊和標簽反轉攻擊下的準確率.本研究提出的可驗證的去中心化FL算法相較于現有的拜占庭容錯FL算法，不僅對于不同的拜占庭攻擊方式表現了更一致和更好的魯棒性，并且更加貼近良性環境下的訓練性能.

表1 CIFAR_10(MNIST)數據集上不同魯棒算法的準確率Tab.1 Accuracy of different robust algorithms on CIFAR_10(MNIST) dataset

5 結語

針對抵抗拜占庭攻擊的去中心化聯邦學習，基于隨機梯度下降算法(SGD)提出魯棒梯度聚合方法.通過結合驗證數據集和SCORE函數，有效提高了算法對于拜占庭攻擊的魯棒性.從理論上證明了所提算法的收斂性質，大量數值實驗也說明可驗證的去中心化FL算法能夠確保：在存在未知數量和攻擊方式的拜占庭用戶的去中心化場景下，所訓練的全局模型能夠保持良好性能，并可以更準確地區分誠實節點與拜占庭節點.在未來的工作中，將進一步研究如何把去中心化聯邦學習與無線傳輸相結合，以提高聯邦學習的通信效率和隱私性.