Technische Samenvatting: Praktische Adversariale Aanvallen op Stochastische Bandieten via Injectie van Valse Data

1. Probleemstelling

Multi-armed bandit (MAB) algoritmen zijn fundamenteel voor systemen voor online besluitvorming, waarbij ze exploratie en exploitatie in evenwicht brengen in toepassingen zoals gepersonaliseerde aanbevelingen, online reclame en klinische trials. Hoewel eerdere onderzoeken hebben vastgesteld dat MAB-algoritmen kwetsbaar zijn voor adversariale aanvallen, vertrouwen bestaande bedreigingsmodellen op onrealistische aannames die hun relevantie voor real-world systemen beperken.

Specifiek hanteren eerdere werken (bijv. Jun et al., 2018; Liu en Shroff, 2019; Zuo, 2024) overwegend een model voor feedback-perturbatie. In dit model observeert de aanvaller in elke ronde de gekozen arm van de learner en de bijbehorende beloning, en wijzigt vervolgens willekeurig de beloning voordat deze aan de learner wordt onthuld. Dit model verleent de aanvaller volledige controle over het feedbackkanaal op elk tijdstip en gaat uit van onbegrensde perturbatiecapaciteiten.

In de praktijk zijn dergelijke capaciteiten vaak onhaalbaar. Bijvoorbeeld, op een platform voor restaurantaanbevelingen kan een adversary niet continu echte gebruikersbeoordelingen van duizenden echte klanten overschrijven. In plaats daarvan omvatten realistische aanvallen het creëren van nepaccounts om gefabriceerde reviews of synthetische interacties (bijv. klikfraude) in te voegen. Deze aanvallen voegen nepdata toe in plaats van bestaande data te wijzigen, zijn onderhevig aan detectie op systeemniveau of resourcebeperkingen, en moeten voldoen aan geldige feedbackbereiken (bijv. beoordelingen van 1 tot 5 sterren).

Dit artikel adresseert de kloof tussen theoretische aanvalmodellen en praktische beperkingen door een nieuw bedreigingsmodel voor te stellen: Injectie van Valse Data. De kernuitdaging is om aanvalstrategieën te ontwerpen die een learner kunnen misleiden om in bijna alle rondes een specifieke suboptimale (doel)arm te selecteren, terwijl ze slechts een sublineaire kosten maken, onder de beperkingen van:

1. Geen wijziging van echte feedback: De aanvaller kan echte gebruikersdata niet overschrijven.
2. Gebonden beloningen: Ingevoegde valse beloningen moeten binnen het geldige feedbackbereik $[r_l, r_u]$ liggen.
3. Temporele beperkingen: De aanvaller kan beperkt zijn in het aantal nepsteekproeven dat hij per ronde kan invoegen (batchgrootte) of de frequentie van invoeging.

2. Methodologie en Kernconcepten

2.1 Het Bedreigingsmodel voor Injectie van Valse Data

De auteurs formaliseren een setting waarin de aanvaller $N_F$ nepdata-steekproeven $\{(a^F_s, r^F_s)\}$ injecteert in de geschiedenis van de learner. De learner behandelt deze ingevoegde steekproeven ononderscheidbaar van legitieme interacties, en past de empirische gemiddelden, aantallen trekkingen en interne rondetellers dienovereenkomstig aan.

• Aanvalskost: Gedefinieerd als $C_F(T) = \sum |r^F_s - \mu_{a^F_s}|$.
• Succescriterium: Een aanval is succesvol als deze de learner ertoe brengt de doelarm te selecteren in $T - o(T)$ rondes, terwijl wordt gegarandeerd dat $C_F(T) = o(T)$.

2.2 Het Onderdrukkingsprincipe

Het centrale technische inzicht is het Onderdrukkingsprincipe. In plaats van beloningen continu te pertureren, streeft de aanvaller ernaar voldoende gebonden valse feedback in te voegen om de empirische schatting van een niet-doelarm onder een stabiele ondergrens van de doelarm te onderdrukken. Zodra een niet-doelarm voldoende is onderdrukt, voorkomt het eigen exploratiemechanisme van de learner dat deze gedurende een aanzienlijke periode opnieuw wordt geselecteerd.

Het Lemma voor Exponentiële Onderdrukking (voor UCB)

Voor het Upper Confidence Bound (UCB) algoritme bewijzen de auteurs dat als een niet-doelarm $i$ voldoende wordt getrokken ($N_i(t) \geq \log T/\delta_0^2$) en zijn empirische gemiddelde wordt gedreven onder een specifieke ondergrens $\hat{\ell}_K(t)$ van de doelarm $K$, dan arm $i$ met hoge waarschijnlijkheid niet opnieuw wordt geselecteerd totdat ten minste ronde $\exp(N_i(t)\delta_0^2)$ is bereikt. Deze "exponentiële onderdrukking" stelt de aanvaller in staat langdurige manipulatie te bereiken met één invoeggebeurtenis per arm.

2.3 Aanvalstrategieën

A. Simultane Injectie (SI)

Ontworpen voor een setting waarin de aanvaller data kan invoegen naar behoefte zonder strikte per-rondelimiet.

• Mechanisme: Voor elke niet-doelarm $i$ wacht de aanvaller tot deze $\lceil \log T/\delta_0^2 \rceil$ keer is getrokken. De aanvaller voegt vervolgens een batch van nepsteekproeven in met de minimale geldige beloning $r_l$ om het empirische gemiddelde van de arm onder de ondergrens van het vertrouwen van de doelarm te verlagen.
• Resultaat: Dit dwingt het UCB-algoritme om de doelarm te selecteren gedurende $T - o(T)$ rondes met een cumulatieve kost van $\tilde{O}(K\sigma\sqrt{\log T})$, wat overeenkomt met bekende ondergrenzen.

B. Periodieke Gebonden Injectie (PBI)

Ontworpen voor realistische beperkingen waarbij de aanvaller geconfronteerd wordt met een limiet voor de batchgrootte ($f$ steekproeven per ronde) en anomaliedetectie moet vermijden.

• Mechanisme: In plaats van één grote injectie, verdeelt de aanvaller de benodigde nepsteekproeven over de tijd. Zodra een niet-doelarm de drempel voor trekkingen bereikt, berekent de aanvaller het totale aantal benodigde steekproeven en een "afkoelperiode" $R_i$. De aanvaller injecteert batches van grootte $f$ periodiek, gescheiden door $R_i$ rondes, zodat de arm onderdrukt blijft tussen de injecties.
• Resultaat: PBI bereikt succesvolle aanvallen met sublineaire kosten, zelfs onder strikte temporele en magnitude-beperkingen, waarbij een evenwicht wordt gevonden tussen sluiering en effectiviteit.

C. Algemeen Onderdrukkings-Gebonden Kader

De auteurs breiden deze bevindingen uit tot buiten UCB naar een klasse van algoritmen die Onderdrukkings-Gebonden worden genoemd. Een algoritme is onderdrukkings-gebonden als, zodra een suboptimale arm empirisch wordt gedomineerd door de doelarm, het algoritme die arm slechts een gebonden aantal extra keren trekt.

• Dit kader is van toepassing op Thompson Sampling en $\epsilon$-greedy algoritmen.
• De aanvalstrategie omvat het invoegen van het minimale aantal nepsteekproeven om een conditie te voldoen waarbij het empirische gemiddelde van de niet-doelarm onder de benchmark van de doelarm blijft, gebruikmakend van de inherente begrenzing van het algoritme op trekkingen na onderdrukking.

3. Belangrijkste Bijdragen

1. Nieuw Bedreigingsmodel: Introductie van Injectie van Valse Data, wat realistische beperkingen weerspiegelt (gebonden beloningen, beperkte frequentie van invoeging, onvermogen om echte data te overschrijven) die door eerdere feedback-perturbatiemodellen zijn over het hoofd gezien.
2. Onderdrukkingsprincipe: Formalisering van een mechanisme waarbij gebonden valse injecties niet-doelarmen permanent kunnen onderdrukken, waardoor de aanval wordt omgezet in een probleem van het vestigen en handhaven van onderdrukking in plaats van continue perturbatie.
3. Algoritmische Strategieën:
   • Simultane Injectie (SI): Een optimale strategie voor UCB onder minimale beperkingen.
   • Periodieke Gebonden Injectie (PBI): Een robuuste strategie voor UCB onder beperkingen voor batchgrootte en tijd.
   • Algemeen Kader: Uitbreiding van de onderdrukkingsanalyse naar Thompson Sampling en $\epsilon$-greedy.
4. Theoretische Garanties: Bewijs dat deze aanvallen learners kunnen misleiden om een doelarm te selecteren in $T - o(T)$ rondes met een sublineaire aanvalskost ($o(T)$), zelfs met gebonden beloningswaarden.
5. Empirische Validatie: Experimenten op synthetische data en de MovieLens 25M dataset die aantonen dat schaarse, gebonden valse data in de praktijk bandiet-learners significant kan beïnvloeden.

4. Experimentele Resultaten

De auteurs evalueerden hun strategieën op:

• Synthetische Data: Gaussische beloningsverdelingen met $K=10$ armen.
• Real-World Data: MovieLens 25M dataset, waarbij een aanbevelingssysteem wordt gesimuleerd met 10 armen (films) en gebruikersinteracties.

Belangrijkste Bevindingen:

• Effectiviteit: Zowel SI als PBI dwongen UCB- en Thompson Sampling-learners succesvol om na een initiële fase van onderdrukking in meer dan 95% van de rondes de doelarm te selecteren.
• Kostenefficiëntie: PBI bereikte prestaties die vergelijkbaar waren met SI, maar met lagere aanvalskosten in scenario's met een lange horizon door injecties over de tijd te spreiden.
• Vergelijking met Baselines: Een heuristische baseline die steekproeven willekeurig injecteerde (evenredig aan de resterende tijd) slaagde er niet in de learner naar de doelarm te laten convergeren, wat het kritieke belang van het invoegschema en het onderdrukkingsprincipe benadrukt.
• Robuustheid tegen Beperkingen: PBI toonde aan dat zelfs met strikte limieten voor de batchgrootte ($f=5$ of $f=10$) de aanval effectief blijft, terwijl onbegrensde strategieën (zoals Least Injection) de laagste theoretische kosten hebben maar minder praktisch kunnen zijn in omgevingen met zware detectie.

5. Betekenis en Beperkingen

Betekenis:
Het artikel overbrugt de kloof tussen theoretische adversariale robuustheid en praktische beveiliging in online learning. Het demonstreert dat de aanname van "onbegrensde, per-rondemanipulatie van beloningen" de moeilijkheid van het aanvallen van real-world systemen significant overschat. Door aan te tonen dat schaarse, gebonden en temporeel verdeelde valse data standaard bandiet-algoritmen kan ondermijnen, onthult het werk een kritieke kwetsbaarheid in systemen voor sequentiële besluitvorming die worden gebruikt in hoog-risico domeinen. Het voorgestelde Lemma voor Onderdrukking biedt een algemeen hulpmiddel voor het analyseren van kwetsbaarheden in algoritmen die vertrouwen op empirische gemiddelden en exploratiebonussen.

Beperkingen (zoals vermeld door de auteurs):

• Passieve Learner: De analyse gaat uit van een passieve learner die alle feedback verwerkt zonder verdedigingsmechanismen (bijv. filtering of auditing).
• Stochastische Setting: Het kader is momenteel beperkt tot stochastische bandieten; het uitbreiden ervan naar contextuele bandieten of reinforcement learning blijft een open probleem.
• Detectierisico's: Het huidige model vat de dynamische interactie tussen aanvallen en adaptieve learners die anomaliedetectie of auditing op arm-niveau toepassen, niet expliciet samen.

De auteurs concluderen dat hoewel hun resultaten een kloof blootleggen tussen klassieke robuustheidsgaranties en praktische beveiliging, toekomstig werk verdedigingen moet onderzoeken, zoals anomaliedetectie en de dynamische wisselwerking tussen aanvallen en adaptieve, verdedigende learners.