Cardinality is Not Enough: Super Host Detection via Segmented Cardinality Estimation

O artigo propõe o SegSketch, uma abordagem de estimativa de cardinalidade segmentada que utiliza uma estratégia de hashing leve para inferir prefixos comuns de endereços IP e estimar a cardinalidade dentro de sub-redes, melhorando significativamente a precisão na detecção de super hosts maliciosos com baixo uso de memória em comparação com soluções existentes.

O essencial

Imagine que a internet é uma cidade gigante, e os "super hosts" são como pessoas que estão causando um caos: ou estão ligando para milhares de vizinhos diferentes para espalhar vírus (atacantes), ou estão recebendo ligações de milhares de pessoas ao mesmo tempo (vítimas de ataques).

O problema é que os guardas da cidade (os sistemas de segurança atuais) têm uma regra simples: "Se alguém fizer muitas ligações, é suspeito!"

Mas isso cria um grande erro. Imagine um carteiro que entrega cartas para 10.000 casas diferentes em toda a cidade. Ele faz muitas ligações, mas é inocente. Agora, imagine um vândalo que só liga para 100 casas, mas todas elas estão no mesmo bairro. O vândalo está tentando destruir aquele bairro inteiro.

Os sistemas antigos olham apenas para o número total de ligações. Eles confundem o carteiro (inocente) com o vândalo (culpado), ou pior, ignoram o vândalo porque ele não fez "número suficiente" de ligações no total, mesmo que todas sejam no mesmo lugar perigoso.

A Solução: O "SegSketch" (O Detetive Inteligente)

Os autores deste paper criaram uma nova ferramenta chamada SegSketch. Em vez de apenas contar "quantas ligações", ela tenta descobrir "onde" essas ligações estão acontecendo.

Aqui está como funciona, usando uma analogia simples:

1. O Problema dos Sistemas Antigos (O Contador Cego)

Os sistemas antigos são como um contador cego que só anota: "João fez 500 ligações".

• Se João liga para 500 pessoas em 500 bairdos diferentes, o contador diz: "Parece perigoso!" (Falso positivo).
• Se João liga para 500 pessoas todas no mesmo prédio, o contador pode não perceber a gravidade, ou confundir com o carteiro.

2. A Ideia do SegSketch (O Detetive de Bairros)

O SegSketch é um detetive que não apenas conta, mas olha para o endereço. Ele percebe que, na internet, os ataques geralmente vêm de um mesmo bairro (mesmo "subnet" ou prefixo de IP).

Ele usa uma técnica chamada "Hashing de Segmento Dividido" (Halved-Segment Hashing). Vamos imaginar isso como um jogo de "Achar o Tesouro":

• O Mapa Dividido: Imagine que o endereço IP é um mapa dividido em pedaços. O SegSketch não olha o endereço inteiro de uma vez. Ele olha pedaço por pedaço.
• A Pergunta Mágica: Ele pergunta: "O primeiro pedaço do endereço é o mesmo para todos?" Se sim, ele foca apenas naquela metade do mapa. "O segundo pedaço é o mesmo?" Se sim, ele foca em um pedaço ainda menor.
• O Resultado: Assim, ele descobre rapidamente: "Ah! Todas essas ligações vêm do mesmo bairro (mesmo prefixo)!"

3. A Vantagem (Economia de Espaço)

Sistemas antigos que tentam fazer isso (chamados de "hierárquicos") são como ter um arquivo gigante com uma gaveta para cada tipo de bairro possível (bairro pequeno, bairro médio, bairro grande). Isso ocupa um espaço enorme na memória do computador, como tentar guardar todos os endereços do mundo em um único cofre.

O SegSketch é como uma caixa de ferramentas compacta. Em vez de ter gavetas separadas para cada tamanho de bairro, ele usa um truque inteligente (o "hashing dividido") para dobrar o espaço e descobrir o tamanho do bairro sem precisar de tanto espaço. É como usar um mapa dobrável que se ajusta ao tamanho da cidade, em vez de ter um mapa gigante e fixo.

Por que isso é incrível?

1. Precisão Cirúrgica: Ele consegue diferenciar o carteiro (que liga para todo lugar) do vândalo (que ataca um bairro específico). Isso reduz drasticamente os "falsos alarmes".
2. Leve e Rápido: Como ele é tão eficiente, ele cabe em computadores pequenos e rápidos (como os chips dentro dos roteadores de internet), sem precisar de servidores gigantes.
3. Resultados: Nos testes, o SegSketch foi até 8 vezes melhor do que as melhores tecnologias atuais em encontrar os verdadeiros culpados, usando muito menos memória.

Resumo Final

Pense no SegSketch como um sistema de segurança que parou de contar apenas "quantas vezes alguém tocou a campainha" e começou a olhar "em qual casa da rua a campainha foi tocada".

• Se a campainha foi tocada em 100 casas diferentes da cidade? Provavelmente é um carteiro (inocente).
• Se a campainha foi tocada 100 vezes na mesma rua? É um ataque! (Culpado).

Essa pequena mudança de foco permite detectar ataques reais com muito mais precisão e sem gastar a bateria (ou memória) do sistema.

Resumo técnico

1. O Problema

A detecção precisa de Super Hosts (hosts que estabelecem conexões com um grande número de peers distintos, como "super espalhadores" em ataques de varredura de IP ou "super receptores" em ataques DDoS) é crucial para mitigar ameaças web e garantir a qualidade do serviço.

• Limitações das Abordagens Atuais:
  • Baseadas em Sketch (Estimadores de Cardinalidade): Métodos existentes (como SpreadSketch, Couper) estimam a cardinalidade de fluxo baseada em endereços IP completos. Eles falham em distinguir entre um host malicioso (que ataca muitos IPs dentro de uma única sub-rede) e um host benigno (como um servidor DNS ou web, que se conecta a muitos IPs distribuídos globalmente). Isso resulta em altas taxas de falsos positivos.
  • Baseadas em Estruturas Hierárquicas: Abordagens que tentam estimar a cardinalidade por sub-rede (prefixo IP) utilizam estruturas hierárquicas com múltiplas camadas (ex: /8, /16, /24). Embora precisas, essas estruturas consomem uma quantidade proibitiva de memória, tornando-as inviáveis para implantação em dispositivos de rede com memória on-chip limitada (como switches programáveis).

O desafio central é estimar a cardinalidade de sub-rede (número de IPs distintos dentro de uma mesma sub-rede) com baixa sobrecarga de memória e alta precisão, sem conhecimento prévio do comprimento do prefixo da sub-rede.

2. Metodologia: SegSketch

Os autores propõem o SegSketch, um esquema de estimativa de cardinalidade segmentada que integra a inferência de prefixos comuns com a estimativa de cardinalidade de sub-rede.

• Estrutura de Dados:

  • O SegSketch utiliza uma estrutura de sketch composta por $r$ linhas e $c$ buckets.
  • Cada bucket contém três componentes: (i) a chave do host, (ii) um bitmap de sub-rede (para inferir o comprimento do prefixo comum) e (iii) um bitmap de host (para estimar a cardinalidade dentro da sub-rede).

• Estratégia de Hashing de Segmento Dividido (Halved-Segment Hashing):

  • Esta é a inovação central para inferir o comprimento do prefixo IP sem memória excessiva.
  • O endereço IP é dividido em segmentos de tamanho fixo $G$ (ex: 8 bits).
  • Um processo de busca binária recursivo é aplicado: para cada segmento, uma função hash de 2 valores (0 ou 1) determina qual metade do bitmap de sub-rede será ativada.
  • Se todos os pacotes de um host tiverem o mesmo valor hash para um segmento, apenas uma metade do bitmap é marcada. Se os valores diferirem, ambas as metades são marcadas.
  • O ponto onde a marcação se divide indica onde o prefixo comum termina, permitindo inferir o comprimento do prefixo da sub-rede (ex: se a divisão ocorre no 3º segmento de 8 bits, o prefixo comum está entre 16 e 24 bits).

• Estimativa de Cardinalidade de Sub-rede:

  • Com o comprimento do prefixo inferido, o sistema extrai o endereço do host restante.
  • Utiliza o algoritmo Linear Counting no bitmap de host para estimar o número de IPs distintos dentro daquela sub-rede específica.
  • Isso permite distinguir ataques concentrados em sub-redes (alta cardinalidade de sub-rede) de tráfego benigno disperso.

• Operações:

  • Atualização: Mapeia o par origem-destino para um bucket. Se o bucket estiver cheio, utiliza uma estratégia de substituição probabilística baseada na cardinalidade estimada (hosts com menor cardinalidade têm maior chance de serem substituídos).
  • Consulta: Calcula a cardinalidade estimada usando a fórmula do Linear Counting ($b \cdot \ln(b/z)$) e compara com um limiar dinâmico $T(p)$, que escala conforme o tamanho da sub-rede inferida.

3. Contribuições Principais

1. Proposta do SegSketch: Um sketch eficiente em memória que combina inferência de prefixo comum e estimativa de cardinalidade de sub-rede, superando a limitação de métodos que olham apenas para o IP completo.
2. Modelo Matemático e Prova de Erro: Os autores estabelecem um modelo para analisar o limite de erro da estimativa de cardinalidade de sub-rede e provam teoricamente que o uso de hashing apenas no endereço do host (após a inferência do prefixo) resulta em um erro de estimativa menor do que o uso de hashing do endereço IP completo.
3. Implementação e Avaliação:
   • Implementação em C++ e em um switch programável usando a linguagem P4 (arquitetura Tofino).
   • Demonstração de que o SegSketch requer apenas 1,77% da SRAM no switch, sendo altamente eficiente em recursos.
   • Avaliação baseada em traços reais (datasets UNSW-NB15, MAWI, CAIDA).

4. Resultados Experimentais

As avaliações compararam o SegSketch com o estado da arte (SpreadSketch, Couper e RHHH - Randomized Hierarchical Heavy Hitter).

• Precisão (F1-Score):
  • O SegSketch superou significativamente as soluções existentes. Em cenários com orçamento de memória restrito (32 KB), houve uma melhoria no F1-Score de até 8,04 vezes em comparação com a melhor solução existente (RHHH) para detecção de super espalhadores.
  • Para detecção de super receptores, a melhoria foi de até 5,08 vezes.
• Taxa de Erro Relativo Médio (ARE):
  • Redução drástica no erro de estimativa (até 87,20% de redução em comparação com o SpreadSketch).
• Desempenho e Throughput:
  • O SegSketch alcançou o maior throughput, atingindo 28 Mpps (milhões de pacotes por segundo) mesmo com memória mínima, superando os concorrentes devido à sua estratégia de hashing leve e ausência de estruturas hierárquicas complexas.
• Eficiência em Hardware (P4):
  • No switch Tofino, o SegSketch consumiu menos recursos de unidades de distribuição de hash, gateways, instruções VLIW e ALUs stateful em comparação com os outros métodos.

5. Significado e Impacto

O trabalho demonstra que a simples contagem de cardinalidade de IP completo é insuficiente para a detecção moderna de anomalias em redes de alta velocidade. Ao introduzir a estimativa de cardinalidade segmentada, o SegSketch resolve o dilema entre precisão e uso de memória.

• Viabilidade em Hardware: A capacidade de operar com menos de 2% da memória SRAM do switch torna a detecção de super hosts viável em equipamentos de rede comerciais de alto desempenho, onde a memória é um recurso escasso.
• Redução de Falsos Positivos: Ao focar na cardinalidade dentro de sub-redes, o sistema ignora o ruído de tráfego legítimo distribuído globalmente, permitindo que os administradores de rede foquem em ataques reais concentrados (como varreduras de rede ou DDoS de botnets).
• Adaptabilidade: O método não requer configuração prévia do tamanho da sub-rede, adaptando-se dinamicamente a diferentes topologias de rede.

Em resumo, o SegSketch representa um avanço significativo na medição de rede, oferecendo uma solução prática e altamente eficiente para a detecção de ameaças de larga escala em ambientes de tráfego intenso.