🤖 machine learning

Practical Adversarial Attacks on Stochastic Bandits via Fake Data Injection

Cet article présente un modèle de menace pratique d'injection de fausses données pour les bandits stochastiques qui surmonte les hypothèses irréalistes des travaux antérieurs en limitant les attaquants à l'injection d'échantillons factices bornés, et démontre par la théorie et des expériences que cette stratégie peut efficacement induire en erreur les algorithmes pour qu'ils sélectionnent un bras cible avec un coût uniquement sous-linéaire.

Auteurs originaux : Qirun Zeng, Eric He, Richard Hoffmann, Xuchuang Wang, Jinhang Zuo

Publié 2026-05-08

📖 5 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Qirun Zeng, Eric He, Richard Hoffmann, Xuchuang Wang, Jinhang Zuo

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez que vous gérez une application de recommandation de restaurants. Chaque fois qu'un utilisateur demande une suggestion, votre application (le « learner ») doit choisir parmi 10 restaurants différents (les « bras »). L'application apprend quels restaurants sont bons en examinant les notes antérieures des utilisateurs. Avec le temps, elle détermine que le Restaurant A est incroyable et que le Restaurant B est terrible, elle cesse donc de recommander B et continue d'envoyer les gens vers A.

L'Ancienne Méthode d'Attaque (Le Problème de la « Baguette Magique »)
Les recherches antérieures sur la manière dont des pirates pourraient briser ces applications supposaient que l'attaquant disposait d'une « baguette magique ». Ils imaginaient qu'un pirate pourrait :

Réécrire l'histoire : Chaque fois qu'un vrai client laissait un avis de 5 étoiles, le pirate pouvait instantanément le transformer en un avis d'une étoile avant que l'application ne le voie.
Le faire indéfiniment : Ils pouvaient le faire pour chaque utilisateur, à chaque fois.
Utiliser des nombres impossibles : Ils pouvaient attribuer une note de « moins 1 000 » ou « plus 1 000 » pour forcer la main de l'application.

L'article soutient que cela est irréaliste. Dans le monde réel, vous ne pouvez pas magiquement modifier l'avis d'une vraie personne. Vous ne pouvez pas non plus attribuer une note de « moins 1 000 » car l'application n'accepte que des notes comprises entre 1 et 5 étoiles.

La Nouvelle Méthode : « Injection de Fausses Données » (Le Problème de l'« Armée de Bots »)
Cet article introduit un modèle de menace beaucoup plus réaliste appelé Injection de Fausses Données. Au lieu d'une baguette magique, l'attaquant est comme une personne disposant d'une petite armée de faux comptes (bots).

La Contrainte : L'attaquant ne peut pas toucher aux vrais avis. Il ne peut que ajouter de nouveaux avis factices.
La Limite : Il ne peut pas créer des millions de bots instantanément (le système les attraperait). Il doit les ajouter lentement et avec précaution.
La Règle : Les faux avis doivent sembler réels. Si l'application n'accepte que des notes de 1 à 5 étoiles, les faux avis doivent être de 1 à 5 étoiles.

La Stratégie : La Tactique du « Silence »
La découverte principale de l'article est une manière astucieuse de tromper l'application sans avoir besoin d'une baguette magique. L'objectif est de faire en sorte que l'application choisisse un restaurant spécifique et terrible (la « cible ») presque tout le temps.

Voici comment l'attaque fonctionne, en utilisant une analogie simple :

Le Déploiement : L'application recommande actuellement un excellent restaurant (Bras A) et ignore un mauvais (Bras B). L'attaquant veut que l'application recommande le pire restaurant (Bras Z) à la place.
Le Piège : L'attaquant attend que l'application essaie de vérifier un « bon » restaurant (comme le Bras A) juste assez de fois pour se faire une opinion.
L'Injection : Une fois que l'application a quelques vrais avis pour le Bras A, l'attaquant inonde le système avec un énorme lot de faux avis d'une étoile pour le Bras A.
- Point Crucial : L'attaquant n'a pas besoin de rendre la note moyenne négative. Il doit simplement l'abaisser suffisamment pour que, mathématiquement, l'application considère le Bras A comme « trop risqué » à explorer davantage.
Le Silence Exponentiel : C'est l'« ingrédient secret » de l'article. Une fois que les calculs de l'application disent : « Le Bras A semble mauvais, cessons de le vérifier », ses propres règles de sécurité entrent en jeu. L'application décide : « Je l'ai assez vérifié ; je ne le regarderai plus pendant très, très longtemps. »
- L'article prouve qu'avec seulement quelques faux avis, l'attaquant peut amener l'application à ignorer un bon restaurant pendant une durée exponentiellement longue (comme des millions de tours).
Le Résultat : L'application, maintenant confuse et pensant que toutes les « bonnes » options sont en réalité mauvaises, cesse de les explorer. Elle reste coincée dans une boucle où elle ne choisit que le restaurant « cible » (celui que l'attaquant veut), même s'il est le pire.

Deux Manières de le Faire
L'article propose deux stratégies spécifiques pour l'« armée de bots » :

Injection Simultanée (Le « Gros Déversement ») : L'attaquant attend que l'application vérifie un restaurant, puis déverse immédiatement un grand lot de faux avis d'un seul coup pour tuer sa réputation. Cela fonctionne bien si le système n'impose pas de limites strictes sur le nombre de faux comptes pouvant s'inscrire en une minute.
Injection Périodique Bornée (Le « Goutte-à-Goutte Lent ») : C'est la version plus réaliste et sournoise. Si le système vous bloque l'ajout de 1 000 faux avis d'un coup, l'attaquant ajoute 5 faux avis, attend un moment, en ajoute 5 autres, attend, et répète.
- L'article montre que même avec ces limites strictes (seulement 5 faux avis à la fois), l'attaquant peut toujours tromper l'application. En calibrant soigneusement les « gouttes », ils maintiennent la confiance de l'application dans les bons restaurants suffisamment basse pour que l'application ne décide jamais de les vérifier à nouveau.

La Conclusion
L'article démontre que vous n'avez pas besoin d'un pirate surpuissant capable de réécrire la réalité pour briser ces systèmes d'apprentissage. Vous avez juste besoin de quelques faux comptes agissant lentement et avec précaution. En ajoutant un petit nombre d'avis factices réalistes et bornés, un attaquant peut tromper définitivement un algorithme d'apprentissage intelligent pour qu'il ignore les meilleures options et en choisisse une terrible, le tout en dépensant très peu d'« effort » (coût).

Cela révèle une vulnérabilité : ces systèmes sont si désireux d'arrêter de « perdre du temps » avec des options qui semblent mauvaises qu'un petit flux régulier de fausses données peut les tromper en les faisant croire que les meilleures options sont en réalité les pires.

Résumé Technique : Attaques Adversariales Pratiques sur les Bandits Stochastiques par Injection de Fausses Données

1. Énoncé du Problème

Les algorithmes de bandits à plusieurs bras (MAB) sont fondamentaux pour les systèmes de prise de décision en ligne, équilibrant exploration et exploitation dans des applications telles que la recommandation personnalisée, la publicité en ligne et les essais cliniques. Bien que des recherches antérieures aient établi que les algorithmes MAB sont vulnérables aux attaques adversariales, les modèles de menace existants reposent sur des hypothèses irréalistes qui limitent leur pertinence pour les systèmes réels.

Plus précisément, les travaux antérieurs (par exemple, Jun et al., 2018 ; Liu et Shroff, 2019 ; Zuo, 2024) adoptent majoritairement un modèle de perturbation des retours. Dans ce modèle, l'attaquant observe le bras choisi par l'apprenant et sa récompense à chaque tour, puis modifie arbitrairement la récompense avant qu'elle ne soit révélée à l'apprenant. Ce modèle accorde à l'attaquant un contrôle total sur le canal de retour à chaque instant et suppose des capacités de perturbation illimitées.

En pratique, de telles capacités sont souvent irréalisables. Par exemple, sur une plateforme de recommandation de restaurants, un adversaire ne peut pas continuellement écraser les véritables notes des utilisateurs provenant de milliers de vrais clients. À la place, les attaques réalistes impliquent la création de faux comptes pour injecter des avis fabriqués ou des interactions synthétiques (par exemple, la fraude aux clics). Ces attaques ajoutent des données factices plutôt que d'altérer des données existantes, sont soumises à une détection au niveau du système ou à des limites de ressources, et doivent respecter des plages de retours valides (par exemple, des notes de 1 à 5 étoiles).

Ce papier comble l'écart entre les modèles d'attaque théoriques et les contraintes pratiques en proposant un nouveau modèle de menace : l'Injection de Fausses Données. Le défi central consiste à concevoir des stratégies d'attaque capables de tromper un apprenant pour qu'il sélectionne un bras spécifique sous-optimal (cible) dans presque tous les tours, tout en n'encourant qu'un coût sous-linéaire, sous les contraintes suivantes :

Aucune modification des retours authentiques : L'attaquant ne peut pas écraser les données réelles des utilisateurs.
Récompenses bornées : Les fausses récompenses injectées doivent se situer dans la plage de retours valide $[r_l, r_u]$ .
Contraintes temporelles : L'attaquant peut être limité dans le nombre d'échantillons factices qu'il peut injecter par tour (taille du lot) ou la fréquence d'injection.

2. Méthodologie et Concepts Clés

2.1 Le Modèle de Menace d'Injection de Fausses Données

Les auteurs formalisent un cadre où l'attaquant injecte $N_F$ échantillons de données factices $\{(a^F_s, r^F_s)\}$ dans l'historique de l'apprenant. L'apprenant traite ces échantillons injectés de manière indiscernable des interactions légitimes, mettant à jour les moyennes empiriques, les comptes de tirages et les compteurs de tours internes en conséquence.

Coût de l'attaque : Défini par $C_F(T) = \sum |r^F_s - \mu_{a^F_s}|$ .
Critère de succès : Une attaque est réussie si elle induit l'apprenant à sélectionner le bras cible dans $T - o(T)$ tours tout en garantissant $C_F(T) = o(T)$ .

2.2 Le Principe de Suppression

L'insight technique central est le Principe de Suppression. Au lieu de perturber continuellement les récompenses, l'attaquant vise à injecter suffisamment de retours factices bornés pour supprimer l'estimation empirique d'un bras non-cible en dessous d'une référence inférieure stable du bras cible. Une fois qu'un bras non-cible est suffisamment supprimé, le mécanisme d'exploration propre de l'apprenant l'empêche d'être sélectionné à nouveau pendant une durée significative.

Le Lemme de Suppression Exponentielle (pour UCB)

Pour l'algorithme de la borne de confiance supérieure (UCB), les auteurs prouvent que si un bras non-cible $i$ est tiré suffisamment ( $N_i(t) \geq \log T/\delta_0^2$ ) et que sa moyenne empirique est poussée en dessous d'une borne inférieure spécifique $\hat{\ell}_K(t)$ du bras cible $K$ , alors le bras $i$ ne sera plus sélectionné avant au moins le tour $\exp(N_i(t)\delta_0^2)$ avec une forte probabilité. Cette « suppression exponentielle » permet à l'attaquant d'atteindre une manipulation à long terme avec un seul événement d'injection par bras.

2.3 Stratégies d'Attaque

A. Injection Simultanée (SI)

Conçue pour un cadre où l'attaquant peut injecter des données selon les besoins sans limites strictes par tour.

Mécanisme : Pour chaque bras non-cible $i$ , l'attaquant attend qu'il ait été tiré $\lceil \log T/\delta_0^2 \rceil$ fois. L'attaquant injecte ensuite un lot d'échantillons factices avec la récompense valide minimale $r_l$ pour réduire la moyenne empirique du bras en dessous de la borne de confiance inférieure du bras cible.
Résultat : Cela force l'algorithme UCB à sélectionner le bras cible pendant $T - o(T)$ tours avec un coût cumulatif de $\tilde{O}(K\sigma\sqrt{\log T})$ , correspondant aux bornes inférieures connues.

B. Injection Bornée Périodique (PBI)

Conçue pour des contraintes réalistes où l'attaquant fait face à une limite de taille de lot ( $f$ échantillons par tour) et doit éviter de déclencher une détection d'anomalies.

Mécanisme : Au lieu d'une seule grande injection, l'attaquant distribue les échantillons factices nécessaires dans le temps. Une fois qu'un bras non-cible atteint le seuil de tirage, l'attaquant calcule le nombre total d'échantillons nécessaires et une période de « refroidissement » $R_i$ . L'attaquant injecte des lots de taille $f$ périodiquement, séparés par $R_i$ tours, garantissant que le bras reste supprimé entre les injections.
Résultat : PBI réalise des attaques réussies avec un coût sous-linéaire même sous des contraintes temporelles et d'amplitude strictes, équilibrant furtivité et efficacité.

C. Cadre Général de Suppression-Bornée

Les auteurs étendent ces résultats au-delà de UCB à une classe d'algorithmes qualifiés de Suppression-Bornée. Un algorithme est suppression-borné si, une fois qu'un bras sous-optimal est empiriquement dominé par le bras cible, l'algorithme ne tire ce bras qu'un nombre borné de fois supplémentaires.

Ce cadre s'applique aux algorithmes Thompson Sampling et $\epsilon$ -greedy.
La stratégie d'attaque consiste à injecter le nombre minimal d'échantillons factices pour satisfaire une condition où la moyenne empirique du bras non-cible reste en dessous de la référence du cible, en exploitant la borne inhérente de l'algorithme sur les tirages post-suppression.

3. Contributions Clés

Nouveau Modèle de Menace : Introduction de l'Injection de Fausses Données, qui reflète des contraintes réalistes (récompenses bornées, fréquence d'injection limitée, incapacité à écraser les données authentiques) négligées par les modèles antérieurs de perturbation des retours.
Principe de Suppression : Formalisation d'un mécanisme où des injections factices bornées peuvent supprimer définitivement les bras non-cibles, transformant l'attaque en un problème d'établissement et de maintien de la suppression plutôt que de perturbation continue.
Stratégies Algorithmiques :
- Injection Simultanée (SI) : Une stratégie optimale pour UCB sous des contraintes minimales.
- Injection Bornée Périodique (PBI) : Une stratégie robuste pour UCB sous des contraintes de taille de lot et temporelles.
- Cadre Général : Extension de l'analyse de suppression à Thompson Sampling et $\epsilon$ -greedy.
Garanties Théoriques : Preuve que ces attaques peuvent tromper les apprenants pour qu'ils sélectionnent un bras cible dans $T - o(T)$ tours avec un coût d'attaque sous-linéaire ( $o(T)$ ), même avec des valeurs de récompense bornées.
Validation Empirique : Expériences sur des données synthétiques et le jeu de données MovieLens 25M démontrant que des données factices clairsemées et bornées peuvent biaiser significativement les apprenants de bandits en pratique.

4. Résultats Expérimentaux

Les auteurs ont évalué leurs stratégies sur :

Données Synthétiques : Distributions de récompenses gaussiennes avec $K=10$ bras.
Données Réelles : Jeu de données MovieLens 25M, simulant un système de recommandation avec 10 bras (films) et des interactions utilisateurs.

Principales Constatations :

Efficacité : Tanto SI que PBI ont forcé avec succès les apprenants UCB et Thompson Sampling à sélectionner le bras cible dans plus de 95 % des tours après une phase initiale de suppression.
Efficacité Coût : PBI a atteint des performances comparables à SI mais avec des coûts d'attaque inférieurs dans les scénarios à horizon long en étalant les injections dans le temps.
Comparaison avec les Baselines : Une baseline heuristique qui injectait des échantillons aléatoirement (proportionnellement au temps restant) n'a pas réussi à converger l'apprenant vers le bras cible, soulignant l'importance critique du calendrier d'injection et du principe de suppression.
Robustesse aux Contraintes : PBI a démontré que même avec des limites strictes sur la taille de lot ( $f=5$ ou $f=10$ ), l'attaque reste efficace, tandis que les stratégies non bornées (comme Least Injection) encourrent le coût théorique le plus faible mais peuvent être moins pratiques dans des environnements riches en détection.

5. Importance et Limites

Importance :
Ce papier comble l'écart entre la robustesse adversariale théorique et la sécurité pratique dans l'apprentissage en ligne. Il démontre que l'hypothèse de « manipulation de récompense illimitée et par tour » surestime considérablement la difficulté d'attaquer les systèmes réels. En montrant que des données factices clairsemées, bornées et distribuées dans le temps peuvent subvertir les algorithmes de bandits standards, ce travail révèle une vulnérabilité critique dans les systèmes de prise de décision séquentielle utilisés dans des domaines à haut risque. Le Lemme de Suppression proposé fournit un outil général pour analyser les vulnérabilités des algorithmes qui reposent sur des moyennes empiriques et des bonus d'exploration.

Limites (telles que déclarées par les auteurs) :

Apprenant Passif : L'analyse suppose un apprenant passif qui traite tous les retours sans mécanismes de défense (par exemple, filtrage ou audit).
Cadre Stochastique : Le cadre est actuellement limité aux bandits stochastiques ; son extension aux bandits contextuels ou à l'apprentissage par renforcement reste un problème ouvert.
Risques de Détection : Le modèle actuel ne capture pas explicitement l'interaction dynamique entre les attaquants et les apprenants adaptatifs qui emploient une détection d'anomalies ou un audit au niveau des bras.

Les auteurs concluent que, bien que leurs résultats exposent un écart entre les garanties de robustesse classiques et la sécurité pratique, les travaux futurs doivent investiguer des défenses telles que la détection d'anomalies et l'interplay dynamique entre les attaquants et les apprenants adaptatifs et défensifs.