Poisoning Learned Index Structures: Static and Dynamic Adversarial Attacks on ALEX

1. Declaração do Problema

Estruturas de índice aprendidas (por exemplo, ALEX, PGM-Index) melhoram o desempenho em relação às estruturas tradicionais (como árvores B) ao modelar a Função de Distribuição Acumulada (CDF) das chaves de dados para prever suas posições. No entanto, essa dependência de distribuições estatísticas de dados cria uma vulnerabilidade:

• Vulnerabilidade Estática: Adversários poderiam, teoricamente, envenenar os dados de treinamento para distorcer o modelo CDF, aumentando os erros de previsão.
• Vulnerabilidade Dinâmica: Adversários poderiam manipular a estrutura do índice durante a execução, inserindo chaves específicas para desencadear comportamentos estruturais de pior caso (por exemplo, divisões excessivas de nós).

A Lacuna: Pesquisas anteriores avaliaram essas ameaças isoladamente, frequentemente utilizando conjuntos de dados sintéticos em pequena escala ou focando em apenas um modelo de ameaça. Há uma falta de comparação sistemática entre envenenamento estático e ataques dinâmicos em índices aprendidos dinâmicos de última geração sob cargas de trabalho realistas.

2. Metodologia

Os autores conduziram uma avaliação sistemática utilizando o ALEX (um índice aprendido dinâmico de última geração) como alvo e a árvore B do Abseil como uma linha de base clássica.

Configuração Experimental

• Conjuntos de Dados: Quatro conjuntos de dados do conjunto de benchmarks SOSD (Books, Facebook, Lognormal, Wiki TS), variando até $10^6$ chaves após subamostragem.
• Hardware: CPU Apple M4 Max (16 núcleos), 64 GB de RAM.
• Modelos de Ataque:
  1. Envenenamento de Dados Estático: O adversário insere um conjunto de chaves adversárias ($\alpha N$, onde $\alpha \in \{0.05, 0.10, 0.15, 0.20\}$) antes da construção do índice. O objetivo é maximizar o Erro Quadrático Médio (MSE) do modelo CDF.
  2. Ataques de Complexidade Algorítmica Dinâmica (ACA): O adversário interage com um índice limpo pré-construído, inserindo chaves adversárias em lotes ao longo de várias rodadas. O desempenho é medido em chaves limpas após cada lote.
     • ACA de Caixa-Preta: Chaves são selecionadas por meio de estratégias aleatórias sem conhecimento do estado interno.
     • ACA de Caixa-Branca: Chaves são selecionadas identificando o maior nó de dados e inserindo adjacentes ao segmento ocupado mais longo para desencadear mudanças de densidade local e divisões de nós.

Métricas de Avaliação

• Estático: Redução de velocidade na latência de pesquisa em relação a uma linha de base limpa.
• Dinâmico: Vazão (Mops/s) e razão de redução de velocidade em relação ao índice limpo.
• Controle: Uma linha de base de "chave real" foi utilizada para distinguir entre efeitos adversários e sensibilidade natural da distribuição.

3. Principais Contribuições

1. Framework Unificado: Fornecimento de um framework reproduzível comparando envenenamento estático e ACA dinâmico no ALEX em diversos conjuntos de dados realistas.
2. Separação de Modelo de Ameaça: Demonstração de uma distinção clara na eficácia entre ataques estáticos e dinâmicos, mostrando que interações dinâmicas são significativamente mais danosas.
3. Análise de Dependência de Conjunto de Dados: Revelação de que o sucesso do ataque depende altamente de como as chaves adversárias mapeiam para os "bins de rank limpo" dos dados, e não apenas da distribuição de valores brutos.
4. Insights de Avaliação: Destaque da necessidade de cargas de trabalho de controle e da incompatibilidade entre danos estruturais localizados e métricas de consulta globais.

4. Principais Resultados

Envenenamento Estático (Impacto Limitado)

• Desempenho: O envenenamento estático teve impacto mínimo no desempenho de pesquisa.
• Métricas: A redução de velocidade variou de 0,855× a 1,029× (essencialmente negligenciável).
• Raciocínio: Mesmo quando as chaves adversárias maximizaram o erro do modelo, a natureza adaptativa da arquitetura do ALEX (divisão e expansão de nós) absorveu a distorção durante a execução. As chaves adversárias ótimas tendiam a concentrar-se nas extremidades da distribuição, falhando em causar degradação estrutural generalizada.

ACA Dinâmica (Degradação Significativa)

• Desempenho: Ataques dinâmicos causaram degradação substancial e sustentada.
• Métricas: O pico de redução de velocidade atingiu 2,7× a 2,8× (a latência de pesquisa aumentou significativamente).
• Mecanismo: A degradação não foi devido ao erro inicial do modelo, mas à deriva estrutural. Inserções adversárias repetidas desencadearam expansões e divisões de nós, remodelando a hierarquia do índice e aumentando os custos de travessia.
• Caixa-Preta vs. Caixa-Branca: Ataques de caixa-branca mostraram uma degradação de pico ligeiramente maior, mas ataques de caixa-preta frequentemente igualaram ou superaram o desempenho de caixa-branca ao final da sequência. Isso sugere que conhecimento estrutural sofisticado não é necessário para degradar o desempenho; estratégias adaptativas aleatórias são suficientes.

Dependência de Conjunto de Dados

• Conjunto de Dados Facebook: Mostrou a degradação mais fraca. Apesar de parecer disperso no espaço de valores brutos, as chaves inseridas caíram em uma faixa estreita de "bins de rank limpo", restringindo o dano a uma pequena região do índice.
• Lognormal e Wiki TS: Mostraram a degradação mais forte. As chaves inseridas ocuparam uma grande fração dos bins de rank limpo, espalhando a pressão estrutural por todo o índice.
• Insight Chave: A fração de bins de rank limpo ocupados pelas chaves inseridas é um melhor preditor do impacto global do que a distribuição do espaço de valores brutos.

5. Significado e Implicações

• Robustez é Dinâmica: A robustez dos índices aprendidos não é uma propriedade estática do modelo, mas uma interação dinâmica entre o modelo de ameaça, a distribuição de dados e a lógica de manutenção do índice.
• Mudança na Estratégia de Defesa: As defesas não podem confiar apenas na validação de dados de treinamento (estática). Os sistemas devem monitorar a dinâmica da carga de trabalho em tempo de execução e a saúde estrutural (por exemplo, detectar divisões excessivas de nós ou deslocamentos de densidade).
• Padrões de Avaliação: Avaliações futuras de índices aprendidos devem incluir cargas de trabalho adversárias interativas e linhas de base de controle de chaves reais para separar ataques genuínos da sensibilidade inerente à distribuição.
• Vulnerabilidade de Sistemas Adaptativos: O fato de ataques adaptativos simples e de caixa-preta poderem degradar o desempenho tão efetivamente quanto ataques sofisticados de caixa-branca implica que os designs atuais de índices aprendidos são fundamentalmente vulneráveis à manipulação em tempo de execução.

Conclusão

O artigo conclui que, embora o envenenamento de dados estático seja amplamente ineficaz contra índices aprendidos adaptativos como o ALEX, ataques de complexidade algorítmica dinâmica são uma ameaça severa, capazes de reduzir a velocidade das pesquisas em quase 3 vezes. O estudo enfatiza que o aspecto de "aprendizado" desses índices, que permite que eles se adaptem aos dados, também fornece o mecanismo para que adversários manipulem sua estrutura durante a execução.