Local Model Poisoning Attacks to Byzantine-Robust Federated Learning - Notes
tags: Meeting Paper NTU
:::info Fang, M., Cao, X., Jia, J., & Gong, N. (2020). Local model poisoning attacks to {Byzantine-Robust} federated learning. In 29th USENIX security symposium (USENIX Security 20) (pp. 1605-1622). :::
Background
What is Non-IID?
首先：什麽是獨立同分布？
- 同分布：所有items均來自同一種概率分布； e.g. 你丟骰子，每次丟骰子到任何一個數字的概率都是1/6，是相等概率。或者說，在概率空間里面，你不論進行幾次抽樣實驗，他們都服從同樣一個分布。
獨立：這些sample items全部都是獨立事件； e.g. 每次抽樣之間沒有關系，不會相互影響。比如你在隨便丟骰子，每次拋到的數字是幾就是幾，是獨立的。但如果我要求你要兩次拋到的數字和大於等於9，第一次和第二次拋就不獨立，因為他們相互關聯。
- 非獨立：有些數據處理的順序不夠隨機。比如有些按時間和其他一些標準來排序的數據會出現相關的情況，違反非獨立的原則。
- 非同分布：數據因所處在不同的分區而出現不同的分布。
- Non-IID其實有三種：不獨立但同分布，獨立不同分布，不獨立也不同分布。
實用拜占庭容錯機制理解
拜占庭將軍問題是一個協議問題，拜占庭帝國軍隊的將軍們必須全體一致的決定是否攻擊某一支敵軍。問題是這些將軍在地理上是分隔開來的，並且將軍中存在叛徒。叛徒可以任意行動以達到以下目標：欺騙某些將軍采取進攻行動；促成一個不是所有將軍都同意的決定，如當將軍們不希望進攻時促成進攻行動；或者迷惑某些將軍，使他們無法做出決定。如果叛徒達到了這些目的之一，則任何攻擊行動的結果都是注定要失敗的，只有完全達成一致的努力才能獲得勝利。
這一問題是一種對現實世界的模型化，尤指網絡當中由於軟硬件錯誤、網絡阻塞及惡意攻擊導致的各種未知行為。
拜占庭容錯
拜占庭將軍問題提出後，有很多的算法被提出用於解決這個問題。這類算法統稱拜占庭容錯算法（BFT: Byzantine Fault Tolerance）。簡略來說，拜占庭容錯（BFT）不是某一個具體算法，而是能夠抵抗拜占庭將軍問題導致的一系列失利的系統特點。 這意味著即使某些節點出現缺點或惡意行為，拜占庭容錯系統也能夠繼續運轉。本質上來說，拜占庭容錯方案就是少數服從多數。
拜占庭容錯系統需要達成如下兩個指標：
- 安全性：任何已經完成的請求都不會被更改，它可以在以後請求看到。在區塊鏈系統中，可以理解為，已經生成的賬本不可篡改，並且可以被節點隨時查看。
- 活性：可以接受並且執行非拜占庭客戶端的請求，不會被任何因素影響而導致非拜占庭客戶端的請求不能執行。在區塊鏈系統中，可以理解為，系統需要持續生成區塊，為用戶記賬，這主要靠挖礦的激勵機制來保證。
Aggregation Rules
Krum Algorithm
Krum算法原理
Krum算法的核心思想是在每輪訓練結束後，對參與者的本地模型權重進行一種特殊的排序和選擇。具體來說，Krum算法遵循以下步驟：
- 計算模型權重之間的距離：對於每對參與者i和j，計算其本地模型權重向量之間的歐氏距離。
- 計算每個參與者的距離和：一共有n個參與者，對於每個參與者i，假設有f個攻擊者，計算參與者與其他最近的n-f-1個參與者模型權重之間的距離和。
- 選擇距離和最小的模型：在所有參與者中，找到距離和最小的模型作為聚合模型。
通過這種方法，Krum算法能夠在參與者之間建立一種“共識”，過濾掉可能受到惡意攻擊的異常模型權重，從而保護全局模型的魯棒性。
Krum算法的應用場景
Krum算法適用於以下場景：
- 需要保護用戶隱私的聯邦學習場景：例如，在醫療、金融等領域，數據隱私和安全性至關重要。
- 面臨拜占庭攻擊風險的聯邦學習場景：例如，在IoT（物聯網）設備、自動駕駛汽車等分布式系統中，由於通信不穩定、設備故障或惡意攻擊，可能存在傳輸錯誤或篡改的模型權重。
Krum算法的優勢與不足
優勢：
- 魯棒性：Krum算法可以抵禦一定數量的拜占庭攻擊者，保證全局模型的魯棒性。
- 適用性廣泛：Krum算法可以應用於各種類型的聯邦學習場景，包括橫向聯邦學習、縱向聯邦學習等。
不足：
- 計算覆雜度較高：Krum算法需要計算每對參與者之間的距離，計算覆雜度為O(n^2)，其中n為參與者數量。在參與者數量較多的情況下，計算負擔可能較重。
- 通信開銷較大：Krum算法需要在參與者之間傳輸模型權重和距離信息，可能導致較大的通信開銷。在網絡帶寬有限或通信不穩定的環境中，可能影響聯邦學習的效率。
Trimmed Mean
Trimmed mean：m個模型的第j 個參數，拋棄最大的和最小的參數，選取剩余的參數的平均值作為全局參數。
Median
Median：主設備對本地模型的第j個參數進行排序，並將中值作為全局模型的第j個參數。