Resumo Técnico: Ataques Adversariais Práticos em Bandits Estocásticos via Injeção de Dados Falsos

1. Declaração do Problema

Algoritmos de bandit de múltiplos braços (MAB) são fundamentais para sistemas de tomada de decisão online, equilibrando exploração e exploração em aplicações como recomendação personalizada, publicidade online e ensaios clínicos. Embora pesquisas anteriores tenham estabelecido que algoritmos MAB são vulneráveis a ataques adversariais, os modelos de ameaça existentes dependem de suposições irreais que limitam sua relevância para sistemas do mundo real.

Especificamente, trabalhos anteriores (por exemplo, Jun et al., 2018; Liu e Shroff, 2019; Zuo, 2024) adotam predominantemente um modelo de perturbação de feedback. Neste modelo, o atacante observa o braço escolhido pelo aprendiz e sua recompensa em cada rodada, modificando arbitrariamente a recompensa antes que ela seja revelada ao aprendiz. Este modelo concede ao atacante controle total sobre o canal de feedback em cada passo de tempo e assume capacidades de perturbação ilimitadas.

Na prática, tais capacidades são frequentemente inviáveis. Por exemplo, em uma plataforma de recomendação de restaurantes, um adversário não pode sobrescrever continuamente avaliações genuínas de usuários de milhares de clientes reais. Em vez disso, ataques realistas envolvem a criação de contas falsas para injetar avaliações fabricadas ou interações sintéticas (por exemplo, fraude de cliques). Esses ataques adicionam dados falsos em vez de alterar dados existentes, estão sujeitos a detecção em nível de sistema ou limites de recursos e devem conformar-se a intervalos de feedback válidos (por exemplo, classificações de 1 a 5 estrelas).

Este artigo aborda a lacuna entre modelos de ataque teóricos e restrições práticas propondo um novo modelo de ameaça: Injeção de Dados Falsos. O desafio central é projetar estratégias de ataque que possam enganar um aprendiz para selecionar um braço subótimo específico (alvo) em quase todas as rodadas, incorrendo apenas em custo sublinear, sob as restrições de:

1. Nenhuma modificação de feedback genuíno: O atacante não pode sobrescrever dados reais de usuários.
2. Recompensas limitadas: Recompensas falsas injetadas devem estar dentro do intervalo de feedback válido $[r_l, r_u]$.
3. Restrições temporais: O atacante pode estar limitado no número de amostras falsas que pode injetar por rodada (tamanho do lote) ou na frequência de injeção.

2. Metodologia e Conceitos Principais

2.1 O Modelo de Ameaça de Injeção de Dados Falsos

Os autores formalizam um cenário onde o atacante injeta $N_F$ amostras de dados falsos $\{(a^F_s, r^F_s)\}$ no histórico do aprendiz. O aprendiz trata essas amostras injetadas de forma indistinguível das interações legítimas, atualizando médias empíricas, contagens de puxadas e contadores internos de rodada de acordo.

• Custo do Ataque: Definido como $C_F(T) = \sum |r^F_s - \mu_{a^F_s}|$.
• Critério de Sucesso: Um ataque é bem-sucedido se induzir o aprendiz a selecionar o braço alvo em $T - o(T)$ rodadas, garantindo simultaneamente que $C_F(T) = o(T)$.

2.2 O Princípio de Supressão

A principal insight técnica é o Princípio de Supressão. Em vez de perturbar continuamente as recompensas, o atacante visa injetar feedback falso limitado suficiente para suprimir a estimativa empírica de um braço não-alvo abaixo de uma referência inferior estável do braço alvo. Uma vez que um braço não-alvo seja suficientemente suprimido, o próprio mecanismo de exploração do aprendiz impede que ele seja selecionado novamente por um período significativo.

O Lema de Supressão Exponencial (para UCB)

Para o algoritmo Upper Confidence Bound (UCB), os autores provam que, se um braço não-alvo $i$ for puxado suficientemente ($N_i(t) \geq \log T/\delta_0^2$) e sua média empírica for reduzida abaixo de um limite inferior específico $\hat{\ell}_K(t)$ do braço alvo $K$, então o braço $i$ não será selecionado novamente até pelo menos a rodada $\exp(N_i(t)\delta_0^2)$ com alta probabilidade. Esta "supressão exponencial" permite que o atacante realize manipulação de longo prazo com um único evento de injeção por braço.

2.3 Estratégias de Ataque

A. Injeção Simultânea (SI)

Projetada para um cenário onde o atacante pode injetar dados conforme necessário, sem limites estritos por rodada.

• Mecanismo: Para cada braço não-alvo $i$, o atacante espera até que ele tenha sido puxado $\lceil \log T/\delta_0^2 \rceil$ vezes. O atacante então injeta um lote de amostras falsas com a recompensa mínima válida $r_l$ para reduzir a média empírica do braço abaixo do limite inferior de confiança do braço alvo.
• Resultado: Isso força o algoritmo UCB a selecionar o braço alvo por $T - o(T)$ rodadas com um custo cumulativo de $\tilde{O}(K\sigma\sqrt{\log T})$, correspondendo aos limites inferiores conhecidos.

B. Injeção Limitada Periódica (PBI)

Projetada para restrições realistas onde o atacante enfrenta um limite de tamanho de lote ($f$ amostras por rodada) e deve evitar disparar detecção de anomalias.

• Mecanismo: Em vez de uma única grande injeção, o atacante distribui as amostras falsas necessárias ao longo do tempo. Uma vez que um braço não-alvo atinge o limite de puxadas, o atacante calcula o número total de amostras necessárias e um período de "resfriamento" $R_i$. O atacante injeta lotes de tamanho $f$ periodicamente, separados por $R_i$ rodadas, garantindo que o braço permaneça suprimido entre as injeções.
• Resultado: A PBI alcança ataques bem-sucedidos com custo sublinear mesmo sob restrições temporais e de magnitude estritas, equilibrando discrição com eficácia.

C. Framework Geral de Supressão Limitada

Os autores estendem essas descobertas além do UCB para uma classe de algoritmos denominados Supressão Limitada. Um algoritmo é supressão-limitado se, uma vez que um braço subótimo for empiricamente dominado pelo braço alvo, o algoritmo puxar esse braço apenas um número limitado de vezes adicionais.

• Este framework aplica-se a algoritmos de Amostragem de Thompson e $\epsilon$-greedy.
• A estratégia de ataque envolve injetar o número mínimo de amostras falsas para satisfazer uma condição onde a média empírica do braço não-alvo permanece abaixo da referência do alvo, aproveitando o limite inerente do algoritmo nas puxadas pós-supressão.

3. Contribuições Principais

1. Novo Modelo de Ameaça: Introdução da Injeção de Dados Falsos, que reflete restrições realistas (recompensas limitadas, frequência de injeção limitada, incapacidade de sobrescrever dados genuínos) negligenciadas pelos modelos anteriores de perturbação de feedback.
2. Princípio de Supressão: Formalização de um mecanismo onde injeções falsas limitadas podem suprimir permanentemente braços não-alvos, transformando o ataque em um problema de estabelecer e manter a supressão em vez de perturbação contínua.
3. Estratégias Algorítmicas:
   • Injeção Simultânea (SI): Uma estratégia ótima para UCB sob restrições mínimas.
   • Injeção Limitada Periódica (PBI): Uma estratégia robusta para UCB sob restrições de tamanho de lote e temporais.
   • Framework Geral: Extensão da análise de supressão para Amostragem de Thompson e $\epsilon$-greedy.
4. Garantias Teóricas: Prova de que esses ataques podem enganar aprendizes a selecionar um braço alvo em $T - o(T)$ rodadas com custo de ataque sublinear ($o(T)$), mesmo com valores de recompensa limitados.
5. Validação Empírica: Experimentos em dados sintéticos e no conjunto de dados MovieLens 25M demonstrando que dados falsos esparsos e limitados podem enviesar significativamente aprendizes de bandit na prática.

4. Resultados Experimentais

Os autores avaliaram suas estratégias em:

• Dados Sintéticos: Distribuições de recompensa Gaussianas com $K=10$ braços.
• Dados do Mundo Real: Conjunto de dados MovieLens 25M, simulando um sistema de recomendação com 10 braços (filmes) e interações de usuários.

Principais Descobertas:

• Eficácia: Tanto SI quanto PBI forçaram com sucesso aprendizes UCB e de Amostragem de Thompson a selecionar o braço alvo em mais de 95% das rodadas após uma fase inicial de supressão.
• Eficiência de Custo: A PBI alcançou desempenho comparável à SI, mas com custos de ataque menores em cenários de horizonte longo, espalhando as injeções ao longo do tempo.
• Comparação com Baselines: Uma baseline heurística que injetava amostras aleatoriamente (proporcional ao tempo restante) falhou em convergir o aprendiz para o braço alvo, destacando a importância crítica do cronograma de injeção e do princípio de supressão.
• Robustez a Restrições: A PBI demonstrou que, mesmo com limites estritos no tamanho do lote ($f=5$ ou $f=10$), o ataque permanece eficaz, enquanto estratégias ilimitadas (como Menor Injeção) incorrem no menor custo teórico, mas podem ser menos práticas em ambientes com muita detecção.

5. Significado e Limitações

Significado:
O artigo preenche a lacuna entre robustez adversarial teórica e segurança prática em aprendizado online. Ele demonstra que a suposição de "manipulação de recompensa ilimitada e por rodada" superestima significativamente a dificuldade de atacar sistemas do mundo real. Ao mostrar que dados falsos esparso, limitados e distribuídos temporalmente podem subverter algoritmos de bandit padrão, o trabalho revela uma vulnerabilidade crítica em sistemas de tomada de decisão sequencial usados em domínios de alto risco. O Lema de Supressão proposto fornece uma ferramenta geral para analisar vulnerabilidades em algoritmos que dependem de médias empíricas e bônus de exploração.

Limitações (conforme declarado pelos autores):

• Aprendiz Passivo: A análise assume um aprendiz passivo que processa todo o feedback sem mecanismos de defesa (por exemplo, filtragem ou auditoria).
• Cenário Estocástico: O framework está atualmente limitado a bandits estocásticos; estendê-lo para bandits contextuais ou aprendizado por reforço permanece um problema em aberto.
• Riscos de Detecção: O modelo atual não captura explicitamente a interação dinâmica entre atacantes e aprendizes adaptativos que empregam detecção de anomalias ou auditoria em nível de braço.

Os autores concluem que, embora seus resultados exponham uma lacuna entre garantias de robustez clássicas e segurança prática, trabalhos futuros devem investigar defesas como detecção de anomalias e a interplay dinâmica entre atacantes e aprendizes adaptativos e defensivos.