SketchGuard: Scaling Byzantine-Robust Decentralized Federated Learning via Sketch-Based Screening

1. Enunciato del Problema

Il Decentralized Federated Learning (DFL) consente ai client di addestrare modelli in modo collaborativo senza un server centrale, migliorando privacy e tolleranza ai guasti. Tuttavia, il DFL è altamente vulnerabile agli attacchi Byzantine, in cui nodi malintenzionati inviano aggiornamenti avvelenati per interrompere l'addestramento.

Il Collo di Bottiglia Principale:
Le difese esistenti robuste agli attacchi Byzantine (ad es. BALANCE, SCCLIP, UBAR) si basano sul filtraggio basato sulla coerenza locale. Per decidere se fidarsi di un vicino, un client deve:

1. Ricevere il vettore completo del modello ad alta dimensionalità del vicino ($d$ dimensioni).
2. Calcolare la distanza tra il vettore completo e il proprio modello.
3. Filtrare in base a questa distanza.

L'Inefficienza:
Questo approccio comporta un costo di comunicazione di $O(d \cdot |N_i|)$ per round (dove $|N_i|$ è il numero di vicini), indipendentemente da quanti vicini vengono infine rifiutati. In reti su larga scala o con modelli di grandi dimensioni (ad es. 60 milioni di parametri), questa comunicazione pre-filtraggio diventa un ostacolo fondamentale al deployment, sprecando larghezza di banda su aggiornamenti malintenzionati che vengono scartati immediatamente dopo la trasmissione.

2. Metodologia: SketchGuard

Gli autori propongono SketchGuard, un framework che disaccoppia il filtraggio dall'aggregazione utilizzando strutture dati Count Sketch.

Meccanismo Principale

Invece di scambiare modelli completi per lo screening, SketchGuard opera in due fasi:

1. Scambio di Sketch (Fase 2):
   • I client comprimono i loro aggiornamenti del modello a $d$ dimensioni in un Count Sketch a bassa dimensionalità di dimensione $k$ (dove $k \ll d$).
   • I vicini scambiano solo questi sketch (costo $O(k \cdot |N_i|)$).
   • I client calcolano le distanze nel dominio dello sketch per identificare i vicini "accettati".
2. Recupero Selettivo del Modello Completo (Fase 4):
   • I vettori del modello completo vengono recuperati solo dai vicini che hanno superato il filtro basato sullo sketch.
   • Verifica: Prima dell'aggregazione, il client ricalcola lo sketch del modello completo ricevuto per assicurarsi che corrisponda allo sketch inviato nella Fase 2. Questo impedisce agli avversari di inviare uno sketch benigno per superare il filtro e un modello completo malintenzionato in seguito.

Fondamento Teorico

Il metodo si basa sulla proprietà di Preservazione della Distanza del Count Sketch (Lemma II.1). Per qualsiasi due vettori $u, v$, con alta probabilità:
$$(1-\epsilon)\|u-v\|^2 \leq \|CS(u) - CS(v)\|^2 \leq (1+\epsilon)\|u-v\|^2$$
Ciò garantisce che se un vicino è lontano nello spazio completo, è probabile che sia lontano anche nello spazio dello sketch, permettendo al filtro di rifiutarlo con alta confidenza.

3. Contributi Chiave

• Innovazione Algoritmica: SketchGuard riduce la complessità di comunicazione per round da $O(d|N_i|)$ a $O(k|N_i| + d|S_i|)$, dove $|S_i|$ è l'insieme dei vicini accettati. Questo elimina il costo della trasmissione di modelli completi per i vicini rifiutati (Byzantine).
• Garanzie Teoriche:
• Gli autori dimostrano la convergenza sia per contesti fortemente convessi che non convessi.
• Dimostrano che il filtraggio basato sullo sketch si discosta dal filtraggio a precisione intera al massimo di un fattore $\sqrt{(1+\epsilon)/(1-\epsilon)}$ nella soglia efficace.
• I tassi di convergenza corrispondono ai tassi ottimali fino a questo fattore controllato, dimostrando che la compressione non rompe fondamentalmente la robustezza.
• Analisi di Sicurezza: La progettazione in due fasi con verifica dello sketch chiude la superficie di attacco in cui un nodo Byzantine potrebbe inviare uno sketch benigno ma un modello completo malintenzionato.

4. Risultati Sperimentali

Il framework è stato valutato su tre benchmark non-IID (FEMNIST, CelebA, Sent140), cinque topologie di rete e quattro tipi di attacco (Deviazione Diretta, Gaussiana, Krum, Backdoor).

• Robustezza:

• SketchGuard corrisponde allo stato dell'arte (BALANCE) in termini di Tasso di Errore di Test (TER).

• La deviazione assoluta media nel TER è $\leq 0,5$ punti percentuali rispetto a BALANCE.

• Rimane robusto anche quando l'80% dei vicini è Byzantine.

• La robustezza è stabile su rapporti di compressione che variano da 7:1 a 13.000:1.

• Guadagni di Efficienza:

• Comunicazione: In condizioni avverse (tasso di rifiuto del 50–70%), SketchGuard ottiene un risparmio di comunicazione totale del 50–70% rispetto alle baseline a precisione intera. In condizioni benigne, l'overhead è trascurabile (<0,02%).

• Computazione: Riduce il tempo di calcolo fino all'82% in reti ad alto grado (ad es. 299 vicini) perché la fase di screening è $O(k)$ invece di $O(d)$.

• Scalabilità: Mentre le baseline scalano linearmente con la dimensione del modello e il grado di rete, SketchGuard scala sub-linearmente con la dimensione del modello e rimane quasi costante rispetto alla connettività di rete per la fase di screening.

5. Significato e Impatto

• Risoluzione della Barriera di Scalabilità: SketchGuard affronta il limite critico che impedisce il deployment del DFL robusto agli attacchi Byzantine in ambienti su larga scala e con vincoli di larghezza di banda (ad es. IoT, edge mobile). Rende la robustezza fattibile per modelli di grandi dimensioni (60M+ parametri) dove i metodi precedenti erano impraticabili.
• Generalizzabilità: Il framework agisce come un "wrapper" applicabile a qualsiasi difesa Byzantine basata sulla similarità (ad es. UBAR, SCCLIP) che si basa su distanze euclidee, non solo sulla specifica regola di aggregazione utilizzata negli esperimenti.
• Rigorosità Teorica: Fornisce la prima analisi formale di convergenza per il filtraggio basato su sketch in contesti decentralizzati, quantificando il compromesso tra compressione e robustezza.

In sintesi, SketchGuard trasforma il DFL robusto agli attacchi Byzantine da un concetto teoricamente valido ma pesante in termini di comunicazione in una soluzione scalabile e pratica, sfruttando lo sketching randomizzato per filtrare i nodi malintenzionati prima che avvenga la costosa trasmissione di dati.