Self-Creating Random Walks for Decentralized Learning under Pac-Man Attacks

Resumo Técnico: Caminhadas Aleatórias Autocriativas para Aprendizado Descentralizado sob Ataques Pac-Man

Formulação do Problema
O artigo aborda a vulnerabilidade de algoritmos de aprendizado descentralizado baseados em Caminhadas Aleatórias (RW - Random Walk) a uma classe específica de ataques furtivos denominados "ataque Pac-Man". Em algoritmos padrão baseados em RW (por exemplo, RW-SGD), os tokens percorrem um grafo de rede para realizar atualizações locais e agregar informações globais. Os autores identificam uma ameaça onde um nó malicioso (o "Pac-Man") encerra probabilisticamente qualquer RW que o visite sem realizar a computação ou o encaminhamento do token. Diferente dos ataques tradicionais de Byzantine ou de envenenamento (poisoning), o nó Pac-Man mimetiza comportamentos benignos em outros aspectos (por exemplo, respondendo a verificações de tolerância a falhas), tornando-o difícil de detectar por meios convencionais.

O problema central é que mesmo um único nó Pac-Man, ao encerrar RWs com uma probabilidade positiva $\zeta \in (0, 1]$, pode eventualmente causar a extinção de todas as RWs ativas na rede com probabilidade um. Isso interrompe o processo de aprendizado inteiramente sem disparar alarmes explícitos de falha. Abordagens de redundância existentes (por exemplo, iniciar com múltiplas RWs) falham porque a redundância estática não pode prevenir a extinção eventual na presença de um adversário de terminação persistente. Além disso, mecanismos de autorregulação existentes como DECAFORK e AC, que dependem da estimativa do tamanho da população ou intervalos de visita para disparar a duplicação, mostram-se sensíveis a escolhas de parâmetros e ainda podem sofrer extinção permanente sob este modelo de ataque.

Metodologia: O Algoritmo CREATE-IF-LATE (CIL)
Para combater o ataque Pac-Man, os autores propõem o CREATE-IF-LATE (CIL), um mecanismo totalmente descentralizado que garante a sobrevivência de longo prazo da população de RW sem exigir coordenação global ou estimativa de parâmetros do sistema.

• Mecanismo: Cada nó benigno $u$ mantém um temporizador local $L_t^{(u)}$ registrando o tempo de sua última visita por qualquer RW. Se o tempo decorrido $t - L_t^{(u)}$ exceder um limiar predeterminado $A_u$, o nó infere uma potencial terminação de RW. Com uma probabilidade de criação $q$, o nó cria probabilisticamente uma nova RW replicando a RW visitada mais recentemente armazenada em seu cache local.
• Autorregulação: Ao contrário de métodos de duplicação que tentam manter uma contagem de população específica, o CIL baseia-se na "criação" disparada pela inatividade. Se a população de RW for eliminada, os nós benignos eventualmente detectarão a ausência de visitas (excedendo $A_u$) e regenerarão novas RWs, garantindo que a população nunca permaneça permanentemente extinta.
• Estrutura Teórica: Os autores desenvolvem um novo framework analítico para estudar o processo de população de RW $\{Z_t\}$. Eles observam que as teorias de processo de ramificação padrão (por exemplo, Galton-Watson) não se aplicam diretamente porque a taxa de criação de RW é dependente da densidade e depende do estado conjunto do sistema (localizações de todas as RWs e históricos de visitação). A análise leva em conta essas dependências intrincadas para provar estabilidade e convergência.

Principais Contribuições

1. Resiliência a Ataques Pac-Man: O artigo demonstra que o CIL garante a não-extinção da população de RW quase certamente, independentemente da probabilidade de terminação $\zeta$. Isso garante que as tarefas computacionais continuem mesmo em ambientes adversários, uma propriedade não garantida por métodos de duplicação anteriores como o DECAFORK.
2. Garantias Teóricas sobre a Dinâmica da População:
   • Não Extinção Permanente: A população de RW é garantida a recuperar-se de eventos de extinção temporária.
   • Não Explosão (No Blowup): Os autores provam que o tamanho da população de RW permanece quase certamente limitado. Eles fornecem um regime teórico para selecionar a probabilidade de criação $q$ de modo que o pico esperado da população permaneça abaixo de um nível prescrito, independente do tamanho da rede $N$ (especificamente para grafos completos, com extensões para grafos conectados gerais).
3. Convergência do Aprendizado Descentralizado: O artigo prova que o RW-SGD integrado com CIL converge.
   • Ponto de Convergência: O algoritmo converge para um minimizador de uma função objetivo substituta definida por uma distribuição quase-estacionária $\pi^{(\zeta)}_{chain}$, que contabiliza o viés introduzido pelo nó Pac-Man.
   • Limites de Erro: Os autores caracterizam o desvio entre o ponto convergido $\tilde{x}^*$ e o verdadeiro ótimo global $x^*$, mostrando que ele é limitado.
   • Atraso de Tempo: A análise mostra que o tempo de inatividade causado pelo adversário é, no máximo, uma fração constante do tempo total, garantindo que o número de iterações de aprendizado efetivas cresça linearmente com o tempo.

Resultados Experimentais
Os autores validam suas descobertas teóricas através de extensas simulações em tarefas de regressão linear sintética e conjuntos de dados de referência públicos (MNIST) sob partições de dados i.i.d. e não-i.i.d.

• Estabilidade da População: Simulações em várias topologias de grafos (completo, regular aleatório, anel, Erdős–Rényi) confirmam que a população de RW sob o CIL permanece limitada e recupera-se da extinção, enquanto a linha de base DECAFORK frequentemente sofre extinção permanente dependendo do ajuste de parâmetros.
• Desempenho de Convergência: O CIL alcança convergência para um valor de perda estável através de diferentes tipos de grafos. Embora limiares de criação maiores ($A$) levem a segmentos planos temporários na curva de perda (devido à extinção e regeneração), o algoritmo eventualmente se recupera. Em contraste, o DECAFORK pode falhar em convergir totalmente se os parâmetros não forem perfeitamente ajustados.
• Compromissos (Trade-offs): Os resultados ilustram um compromisso entre velocidade de convergência e overhead de comunicação. Limiares menores ($A$) levam a uma convergência mais rápida, mas com maior custo de comunicação devido à criação frequente de RW, enquanto limiares maiores reduzem o overhead às custas de um progresso em tempo real mais lento.
• Precisão: Em dados não-i.i.d., a precisão final do modelo sob o CIL é comparável ao DECAFORK, mas significativamente mais robusta, visto que o DEFAFORK frequentemente falha em completar o treinamento devido à extinção.

Significância e Alegações
O artigo afirma que o CIL fornece uma solução robusta e totalmente descentralizada para uma vulnerabilidade crítica no aprendizado baseado em RW: a terminação silenciosa de tokens de aprendizado. Ao mudar da estimativa de população e duplicação para a criação local baseada em tempo, o algoritmo garante que os processos de aprendizado não possam ser permanentemente interrompidos por um único nó malicioso. Os autores enfatizam que sua abordagem não requer conhecimento da probabilidade de terminação do adversário ou do tamanho da rede, tornando-a prática para sistemas descentralizados do mundo real. O trabalho estabelece que, embora o ataque Pac-Man introduza um viés no objetivo de otimização, o processo de aprendizado permanece convergente e eficaz, desde que a população de RW seja autorregulada através do mecanismo CIL.