Riepilogo Tecnico: Attacchi Avversariali Pratici ai Bandit Stocastici tramite Iniezione di Dati Falsi

1. Enunciato del Problema

Gli algoritmi Multi-armed Bandit (MAB) sono fondamentali per i sistemi di decisione online, bilanciando esplorazione e sfruttamento in applicazioni come raccomandazioni personalizzate, pubblicità online e trial clinici. Sebbene ricerche precedenti abbiano stabilito che gli algoritmi MAB sono vulnerabili ad attacchi avversariali, i modelli di minaccia esistenti si basano su ipotesi irrealistiche che ne limitano la rilevanza per i sistemi del mondo reale.

Nello specifico, lavori precedenti (ad es. Jun et al., 2018; Liu e Shroff, 2019; Zuo, 2024) adottano prevalentemente un modello di perturbazione del feedback. In questo modello, l'attaccante osserva il braccio scelto dall'apprendente e la sua ricompensa in ogni turno, quindi modifica arbitrariamente la ricompensa prima che venga rivelata all'apprendente. Questo modello concede all'attaccante il controllo completo sul canale di feedback a ogni passo temporale e assume capacità di perturbazione illimitate.

Nella pratica, tali capacità sono spesso non fattibili. Ad esempio, in una piattaforma di raccomandazione di ristoranti, un avversario non può sovrascrivere continuamente le valutazioni genuine di migliaia di utenti reali. Al contrario, attacchi realistici comportano la creazione di account falsi per iniettare recensioni fabbricate o interazioni sintetiche (ad es. click fraud). Questi attacchi aggiungono dati falsi invece di alterare dati esistenti, sono soggetti a rilevamento a livello di sistema o limiti di risorse e devono conformarsi a intervalli di feedback validi (ad es. valutazioni da 1 a 5 stelle).

Questo articolo colma il divario tra modelli di attacco teorici e vincoli pratici proponendo un nuovo modello di minaccia: Iniezione di Dati Falsi. La sfida principale è progettare strategie di attacco che possano indurre un apprendente a selezionare un braccio specifico subottimale (bersaglio) in quasi tutti i turni, sostenendo solo un costo sublineare, sotto i vincoli di:

1. Nessuna modifica del feedback genuino: L'attaccante non può sovrascrivere i dati degli utenti reali.
2. Ricompense limitate: Le ricompense false iniettate devono rientrare nell'intervallo di feedback valido $[r_l, r_u]$.
3. Vincoli temporali: L'attaccante può essere limitato nel numero di campioni falsi che può iniettare per turno (dimensione del batch) o nella frequenza di iniezione.

2. Metodologia e Concetti Chiave

2.1 Il Modello di Minaccia di Iniezione di Dati Falsi

Gli autori formalizzano un contesto in cui l'attaccante inietta $N_F$ campioni di dati falsi $\{(a^F_s, r^F_s)\}$ nella storia dell'apprendente. L'apprendente tratta questi campioni iniettati in modo indistinguibile dalle interazioni legittime, aggiornando le medie empiriche, i conteggi delle estrazioni e i contatori interni dei turni di conseguenza.

• Costo dell'Attacco: Definito come $C_F(T) = \sum |r^F_s - \mu_{a^F_s}|$.
• Criterio di Successo: Un attacco è riuscito se induce l'apprendente a selezionare il braccio bersaglio in $T - o(T)$ turni garantendo che $C_F(T) = o(T)$.

2.2 Il Principio di Soppressione

L'insight tecnico centrale è il Principio di Soppressione. Invece di perturbare continuamente le ricompense, l'attaccante mira a iniettare feedback falsi limitati sufficienti a sopprimere la stima empirica di un braccio non-bersaglio al di sotto di un riferimento inferiore stabile del braccio bersaglio. Una volta che un braccio non-bersaglio è sufficientemente soppresso, il meccanismo di esplorazione dell'apprendente impedisce che venga selezionato nuovamente per una durata significativa.

Il Lemma di Soppressione Esponenziale (per UCB)

Per l'algoritmo Upper Confidence Bound (UCB), gli autori dimostrano che se un braccio non-bersaglio $i$ viene estratto sufficientemente ($N_i(t) \geq \log T/\delta_0^2$) e la sua media empirica viene spinta al di sotto di un limite inferiore specifico $\hat{\ell}_K(t)$ del braccio bersaglio $K$, allora il braccio $i$ non verrà selezionato nuovamente fino ad almeno il turno $\exp(N_i(t)\delta_0^2)$ con alta probabilità. Questa "soppressione esponenziale" permette all'attaccante di ottenere una manipolazione a lungo termine con un singolo evento di iniezione per braccio.

2.3 Strategie di Attacco

A. Iniezione Simultanea (SI)

Progettata per un contesto in cui l'attaccante può iniettare dati secondo necessità senza limiti rigidi per turno.

• Meccanismo: Per ogni braccio non-bersaglio $i$, l'attaccante attende finché non è stato estratto $\lceil \log T/\delta_0^2 \rceil$ volte. L'attaccante inietta quindi un batch di campioni falsi con la ricompensa minima valida $r_l$ per ridurre la media empirica del braccio al di sotto del limite inferiore di confidenza del braccio bersaglio.
• Risultato: Questo forza l'algoritmo UCB a selezionare il braccio bersaglio per $T - o(T)$ turni con un costo cumulativo di $\tilde{O}(K\sigma\sqrt{\log T})$, allineandosi ai limiti inferiori noti.

B. Iniezione Limitata Periodica (PBI)

Progettata per vincoli realistici in cui l'attaccante affronta un limite di dimensione del batch ($f$ campioni per turno) e deve evitare di attivare il rilevamento di anomalie.

• Meccanismo: Invece di una singola grande iniezione, l'attaccante distribuisce i campioni falsi necessari nel tempo. Una volta che un braccio non-bersaglio raggiunge la soglia di estrazione, l'attaccante calcola il numero totale di campioni necessari e un periodo di "raffreddamento" $R_i$. L'attaccante inietta batch di dimensione $f$ periodicamente, separati da $R_i$ turni, garantendo che il braccio rimanga soppresso tra le iniezioni.
• Risultato: PBI realizza attacchi riusciti con costo sublineare anche sotto vincoli temporali e di magnitudine rigorosi, bilanciando furtività ed efficacia.

C. Framework Generale di Soppressione-Limitata

Gli autori estendono questi risultati oltre UCB a una classe di algoritmi definiti Soppressione-Limitata. Un algoritmo è soppressione-limitato se, una volta che un braccio subottimale è empiricamente dominato dal braccio bersaglio, l'algoritmo estrae quel braccio solo un numero limitato di volte aggiuntivo.

• Questo framework si applica agli algoritmi Thompson Sampling e $\epsilon$-greedy.
• La strategia di attacco comporta l'iniezione del numero minimo di campioni falsi per soddisfare una condizione in cui la media empirica del braccio non-bersaglio rimane al di sotto del riferimento del bersaglio, sfruttando il limite intrinseco dell'algoritmo sulle estrazioni post-soppressione.

3. Contributi Chiave

1. Nuovo Modello di Minaccia: Introduzione dell'Iniezione di Dati Falsi, che riflette vincoli realistici (ricompense limitate, frequenza di iniezione limitata, incapacità di sovrascrivere dati genuini) trascurati dai precedenti modelli di perturbazione del feedback.
2. Principio di Soppressione: Formalizzazione di un meccanismo in cui iniezioni false limitate possono sopprimere permanentemente i bracci non-bersaglio, trasformando l'attacco in un problema di stabilire e mantenere la soppressione piuttosto che una perturbazione continua.
3. Strategie Algoritmiche:
   • Iniezione Simultanea (SI): Una strategia ottimale per UCB sotto vincoli minimi.
   • Iniezione Limitata Periodica (PBI): Una strategia robusta per UCB sotto vincoli di dimensione del batch e temporali.
   • Framework Generale: Estensione dell'analisi di soppressione a Thompson Sampling e $\epsilon$-greedy.
4. Garanzie Teoriche: Dimostrazione che questi attacchi possono indurre gli apprendenti a selezionare un braccio bersaglio in $T - o(T)$ turni con costo di attacco sublineare ($o(T)$), anche con valori di ricompensa limitati.
5. Validazione Empirica: Esperimenti su dati sintetici e sul dataset MovieLens 25M che dimostrano come dati falsi sparsi e limitati possano distorcere significativamente gli apprendenti bandit nella pratica.

4. Risultati Sperimentali

Gli autori hanno valutato le loro strategie su:

• Dati Sintetici: Distribuzioni di ricompensa Gaussiane con $K=10$ bracci.
• Dati del Mondo Reale: Dataset MovieLens 25M, simulando un sistema di raccomandazione con 10 bracci (film) e interazioni utente.

Risultati Chiave:

• Efficacia: Sia SI che PBI hanno costretto con successo gli apprendenti UCB e Thompson Sampling a selezionare il braccio bersaglio in oltre il 95% dei turni dopo una fase iniziale di soppressione.
• Efficienza dei Costi: PBI ha raggiunto prestazioni comparabili a SI ma con costi di attacco inferiori in scenari a orizzonte lungo distribuendo le iniezioni nel tempo.
• Confronto con Baseline: Una baseline euristica che iniettava campioni casualmente (proporzionalmente al tempo rimanente) non è riuscita a far convergere l'apprendente verso il braccio bersaglio, evidenziando l'importanza critica del piano di iniezione e del principio di soppressione.
• Robustezza ai Vincoli: PBI ha dimostrato che anche con limiti rigorosi sulla dimensione del batch ($f=5$ o $f=10$), l'attacco rimane efficace, mentre strategie illimitate (come Least Injection) sostengono il costo teorico più basso ma possono essere meno pratiche in ambienti con elevato rilevamento.

5. Significato e Limitazioni

Significato:
Il documento colma il divario tra robustezza avversariale teorica e sicurezza pratica nell'apprendimento online. Dimostra che l'assunzione di "manipolazione delle ricompense illimitata e per turno" sovrastima significativamente la difficoltà di attaccare sistemi reali. Mostrando che dati falsi sparsi, limitati e distribuiti temporalmente possono sovvertire gli algoritmi bandit standard, il lavoro rivela una vulnerabilità critica nei sistemi di decisione sequenziale utilizzati in domini ad alto rischio. Il Lemma di Soppressione proposto fornisce uno strumento generale per analizzare le vulnerabilità negli algoritmi che si basano su medie empiriche e bonus di esplorazione.

Limitazioni (come dichiarate dagli autori):

• Apprendente Passivo: L'analisi assume un apprendente passivo che elabora tutto il feedback senza meccanismi di difesa (ad es. filtraggio o audit).
• Contesto Stocastico: Il framework è attualmente limitato ai bandit stocastici; estenderlo a bandit contestuali o apprendimento per rinforzo rimane un problema aperto.
• Rischi di Rilevamento: Il modello corrente non cattura esplicitamente l'interazione dinamica tra attaccanti e apprendenti adattivi che impiegano rilevamento di anomalie o audit a livello di braccio.

Gli autori concludono che, sebbene i loro risultati espongano un divario tra garanzie di robustezza classica e sicurezza pratica, il lavoro futuro dovrà investigare difese come il rilevamento di anomalie e l'interplay dinamico tra attaccanti e apprendenti adattivi difensivi.