Technische Zusammenfassung: Praktische adversarische Angriffe auf stochastische Banditen durch Fälschung von Dateninjektion

1. Problemstellung

Multi-Armed-Bandit-(MAB)-Algorithmen bilden die Grundlage für Systeme zur Online-Entscheidungsfindung, indem sie Exploration und Exploitation in Anwendungen wie personalisierten Empfehlungen, Online-Werbung und klinischen Studien ausbalancieren. Während frühere Forschungsarbeiten gezeigt haben, dass MAB-Algorithmen anfällig für adversarische Angriffe sind, stützen sich bestehende Bedrohungsmodelle auf unrealistische Annahmen, die ihre Relevanz für reale Systeme einschränken.

Insbesondere übernehmen frühere Arbeiten (z. B. Jun et al., 2018; Liu und Shroff, 2019; Zuo, 2024) überwiegend ein Modell der Feedback-Manipulation. In diesem Modell beobachtet der Angreifer in jeder Runde den vom Lernenden gewählten Arm und dessen Belohnung und modifiziert die Belohnung anschließend willkürlich, bevor sie dem Lernenden enthüllt wird. Dieses Modell gewährt dem Angreifer zu jedem Zeitschritt die volle Kontrolle über den Feedback-Kanal und geht von unbegrenzten Manipulationsfähigkeiten aus.

In der Praxis sind solche Fähigkeiten oft nicht durchführbar. Beispielsweise kann ein Angreifer auf einer Plattform für Restaurantempfehlungen nicht kontinuierlich echte Bewertungen von Tausenden realer Kunden überschreiben. Stattdessen beinhalten realistische Angriffe das Erstellen gefälschter Konten, um gefälschte Bewertungen oder synthetische Interaktionen (z. B. Klickbetrug) einzuspeisen. Diese Angriffe fügen gefälschte Daten hinzu, anstatt bestehende Daten zu verändern, unterliegen systemweiten Erkennungsmechanismen oder Ressourcenbeschränkungen und müssen gültige Feedback-Bereiche einhalten (z. B. Bewertungen von 1 bis 5 Sternen).

Dieser Beitrag schließt die Lücke zwischen theoretischen Angriffsmodellen und praktischen Einschränkungen durch die Einführung eines neuen Bedrohungsmodells: Fälschung von Dateninjektion. Die zentrale Herausforderung besteht darin, Angriffsstrategien zu entwerfen, die einen Lernenden dazu verleiten können, in nahezu allen Runden einen spezifischen suboptimalen (Ziel-)Arm zu wählen, dabei jedoch nur sublineare Kosten verursachen, unter den folgenden Einschränkungen:

1. Keine Modifikation echten Feedbacks: Der Angreifer kann echte Nutzerdaten nicht überschreiben.
2. Begrenzte Belohnungen: Injizierte gefälschte Belohnungen müssen innerhalb des gültigen Feedback-Bereichs $[r_l, r_u]$ liegen.
3. Zeitliche Einschränkungen: Der Angreifer kann in der Anzahl der pro Runde injizierten gefälschten Stichproben (Batch-Größe) oder der Häufigkeit der Injektion begrenzt sein.

2. Methodik und Kernkonzepte

2.1 Das Bedrohungsmodell der Fälschung von Dateninjektion

Die Autoren formalisieren ein Szenario, in dem der Angreifer $N_F$ gefälschte Datenstichproben $\{(a^F_s, r^F_s)\}$ in den Verlauf des Lernenden injiziert. Der Lernende behandelt diese injizierten Stichproben unverkennbar von legitimen Interaktionen und aktualisiert entsprechend die empirischen Mittelwerte, die Anzahlen der Ziehungen und interne Runden-Zähler.

• Angriffskosten: Definiert als $C_F(T) = \sum |r^F_s - \mu_{a^F_s}|$.
• Erfolgskriterium: Ein Angriff ist erfolgreich, wenn er den Lernenden dazu veranlasst, in $T - o(T)$ Runden den Zielarm zu wählen, wobei sichergestellt wird, dass $C_F(T) = o(T)$ gilt.

2.2 Das Unterdrückungsprinzip

Der zentrale technische Erkenntnisgewinn ist das Unterdrückungsprinzip. Anstatt Belohnungen kontinuierlich zu manipulieren, zielt der Angreifer darauf ab, genügend begrenzte gefälschte Feedbacks zu injizieren, um die empirische Schätzung eines Nicht-Ziel-Arms unter eine stabile untere Benchmark des Ziel-Arms zu drücken. Sobald ein Nicht-Ziel-Arm ausreichend unterdrückt ist, verhindert der eigene Explorationsmechanismus des Lernenden, dass dieser Arm für einen signifikanten Zeitraum erneut gewählt wird.

Das Lemma zur exponentiellen Unterdrückung (für UCB)

Für den Upper Confidence Bound (UCB)-Algorithmus beweisen die Autoren, dass, wenn ein Nicht-Ziel-Arm $i$ ausreichend oft gezogen wird ($N_i(t) \geq \log T/\delta_0^2$) und sein empirischer Mittelwert unter eine spezifische untere Schranke $\hat{\ell}_K(t)$ des Ziel-Arms $K$ gedrückt wird, dann wird Arm $i$ mit hoher Wahrscheinlichkeit nicht erneut gewählt, bis mindestens zur Runde $\exp(N_i(t)\delta_0^2)$. Diese „exponentielle Unterdrückung" ermöglicht es dem Angreifer, eine langfristige Manipulation mit einem einzigen Injektionsereignis pro Arm zu erreichen.

2.3 Angriffsstrategien

A. Simultane Injektion (SI)

Entwickelt für ein Szenario, in dem der Angreifer bei Bedarf Daten injizieren kann, ohne strengen pro-Runde-Beschränkungen zu unterliegen.

• Mechanismus: Für jeden Nicht-Ziel-Arm $i$ wartet der Angreifer, bis dieser $\lceil \log T/\delta_0^2 \rceil$-mal gezogen wurde. Anschließend injiziert der Angreifer einen Batch gefälschter Stichproben mit der minimalen gültigen Belohnung $r_l$, um den empirischen Mittelwert des Arms unter die untere Konfidenzschranke des Ziel-Arms zu drücken.
• Ergebnis: Dies zwingt den UCB-Algorithmus, in $T - o(T)$ Runden den Zielarm zu wählen, mit kumulierten Kosten von $\tilde{O}(K\sigma\sqrt{\log T})$, was bekannten unteren Schranken entspricht.

B. Periodische begrenzte Injektion (PBI)

Entwickelt für realistische Einschränkungen, bei denen der Angreifer einem Limit der Batch-Größe ($f$ Stichproben pro Runde) unterliegt und Anomalieerkennung vermeiden muss.

• Mechanismus: Anstatt einer einzigen großen Injektion verteilt der Angreifer die erforderlichen gefälschten Stichproben über die Zeit. Sobald ein Nicht-Ziel-Arm die Ziehungsschwelle erreicht, berechnet der Angreifer die Gesamtzahl der benötigten Stichproben und eine „Cooldown"-Periode $R_i$. Der Angreifer injiziert dann periodisch Batches der Größe $f$, getrennt durch $R_i$ Runden, wodurch sichergestellt wird, dass der Arm zwischen den Injektionen unterdrückt bleibt.
• Ergebnis: PBI erzielt erfolgreiche Angriffe mit sublinearen Kosten auch unter strengen zeitlichen und mengenmäßigen Einschränkungen und balanciert dabei Tarnung mit Wirksamkeit aus.

C. Allgemeines Unterdrückungs-begrenztes Framework

Die Autoren erweitern diese Erkenntnisse über UCB hinaus auf eine Klasse von Algorithmen, die als Unterdrückungs-begrenzt bezeichnet werden. Ein Algorithmus ist unterdrückungs-begrenzt, wenn, sobald ein suboptimaler Arm empirisch vom Ziel-Arm dominiert wird, der Algorithmus diesen Arm nur eine begrenzte Anzahl zusätzlicher Male zieht.

• Dieses Framework gilt für Thompson Sampling und $\epsilon$-greedy-Algorithmen.
• Die Angriffsstrategie besteht darin, die minimale Anzahl gefälschter Stichproben zu injizieren, um eine Bedingung zu erfüllen, bei der der empirische Mittelwert des Nicht-Ziel-Arms unter der Benchmark des Ziel-Arms bleibt, wobei die inhärente Obergrenze des Algorithmus für Ziehungen nach der Unterdrückung genutzt wird.

3. Hauptbeiträge

1. Neues Bedrohungsmodell: Einführung der Fälschung von Dateninjektion, die realistische Einschränkungen (begrenzte Belohnungen, eingeschränkte Injektionshäufigkeit, Unmöglichkeit, echte Daten zu überschreiben) widerspiegelt, die von früheren Feedback-Manipulationsmodellen übersehen wurden.
2. Unterdrückungsprinzip: Formalisierung eines Mechanismus, bei dem begrenzte gefälschte Injektionen Nicht-Ziel-Arme dauerhaft unterdrücken können, wodurch der Angriff zu einem Problem der Etablierung und Aufrechterhaltung der Unterdrückung wird, anstatt einer kontinuierlichen Manipulation.
3. Algorithmische Strategien:
   • Simultane Injektion (SI): Eine optimale Strategie für UCB unter minimalen Einschränkungen.
   • Periodische begrenzte Injektion (PBI): Eine robuste Strategie für UCB unter Batch-Größen- und zeitlichen Einschränkungen.
   • Allgemeines Framework: Erweiterung der Unterdrückungsanalyse auf Thompson Sampling und $\epsilon$-greedy.
4. Theoretische Garantien: Beweis, dass diese Angriffe Lernende dazu verleiten können, in $T - o(T)$ Runden einen Zielarm zu wählen, bei sublinearen Angriffskosten ($o(T)$), selbst bei begrenzten Belohnungswerten.
5. Empirische Validierung: Experimente mit synthetischen Daten und dem MovieLens 25M-Datensatz, die zeigen, dass spärliche, begrenzte gefälschte Daten Bandit-Lernende in der Praxis signifikant verzerren können.

4. Experimentelle Ergebnisse

Die Autoren bewerteten ihre Strategien an:

• Synthetischen Daten: Gaußsche Belohnungsverteilungen mit $K=10$ Armen.
• Realen Daten: MovieLens 25M-Datensatz, der ein Empfehlungssystem mit 10 Armen (Filmen) und Nutzerinteraktionen simuliert.

Wichtige Erkenntnisse:

• Wirksamkeit: Sowohl SI als auch PBI zwangen UCB- und Thompson-Sampling-Lernende erfolgreich dazu, in über 95 % der Runden nach einer anfänglichen Unterdrückungsphase den Zielarm zu wählen.
• Kosteneffizienz: PBI erzielte eine Leistung, die mit SI vergleichbar war, jedoch bei langfristigen Szenarien durch die zeitliche Verteilung der Injektionen geringere Angriffskosten aufwies.
• Vergleich mit Baselines: Eine heuristische Baseline, die Stichproben zufällig injizierte (proportional zur verbleibenden Zeit), scheiterte daran, den Lernenden auf den Zielarm zu konvergieren, was die kritische Bedeutung des Injektionsplans und des Unterdrückungsprinzips unterstreicht.
• Robustheit gegenüber Einschränkungen: PBI zeigte, dass selbst bei strengen Limits der Batch-Größe ($f=5$ oder $f=10$) der Angriff wirksam bleibt, während unbeschränkte Strategien (wie „Least Injection") zwar die niedrigsten theoretischen Kosten aufweisen, in Umgebungen mit starker Erkennung jedoch weniger praktikabel sein können.

5. Bedeutung und Einschränkungen

Bedeutung:
Der Beitrag schließt die Lücke zwischen theoretischer adversarischer Robustheit und praktischer Sicherheit im Online-Lernen. Er zeigt auf, dass die Annahme einer „unbeschränkten, pro-Runde-Belohnungsmanipulation" die Schwierigkeit, reale Systeme anzugreifen, erheblich überschätzt. Durch den Nachweis, dass spärliche, begrenzte und zeitlich verteilte gefälschte Daten Standard-Bandit-Algorithmen untergraben können, offenbart die Arbeit eine kritische Schwachstelle in sequenziellen Entscheidungsfindungssystemen, die in hochriskanten Domänen eingesetzt werden. Das vorgeschlagene Unterdrückungs-Lemma liefert ein allgemeines Werkzeug zur Analyse von Schwachstellen in Algorithmen, die auf empirischen Mittelwerten und Explorations-Boni basieren.

Einschränkungen (wie von den Autoren angegeben):

• Passiver Lernender: Die Analyse geht von einem passiven Lernenden aus, der alle Feedbacks ohne Verteidigungsmechanismen (z. B. Filterung oder Prüfung) verarbeitet.
• Stochastisches Setting: Das Framework ist derzeit auf stochastische Banditen beschränkt; die Erweiterung auf kontextuelle Banditen oder Reinforcement Learning bleibt ein offenes Problem.
• Erkennungsrisiken: Das aktuelle Modell erfasst nicht explizit die dynamische Interaktion zwischen Angreifern und adaptiven Lernenden, die Anomalieerkennung oder Arm-Prüfungen einsetzen.

Die Autoren schließen, dass ihre Ergebnisse zwar eine Lücke zwischen klassischen Robustheitsgarantien und praktischer Sicherheit aufzeigen, zukünftige Arbeiten jedoch Verteidigungsmaßnahmen wie Anomalieerkennung und das dynamische Zusammenspiel zwischen Angreifern und adaptiven, defensiven Lernenden untersuchen müssen.