Como o Chrome Verifica Milhões de Sites Maliciosos em Milissegundos?

Introdução

Você já parou para pensar como o Google Chrome consegue te alertar sobre milhões de sites maliciosos quase que instantaneamente? Ou como o Medium evita te recomendar um artigo que você já leu, mesmo entre milhões de publicações?

Uma solução simples seria baixar uma lista gigantesca com milhões de URLs para o seu navegador e checar cada site que você visita contra essa lista. Mas isso seria um desastre de performance e consumo de memória. O seu computador ficaria lento e sua experiência de navegação, péssima.

Então, qual é o truque? E se eu te dissesse que existe uma estrutura de dados probabilística que resolve isso de forma genial, trocando um pingo de certeza por uma eficiência absurda em espaço e velocidade?

Essa estrutura é o Filtro de Bloom. Neste artigo, vamos entender o que ele é, o problema que resolve, como funciona por baixo dos panos e como você pode implementar um em Javascript hoje mesmo.

Mas por que utilizar?

Antes de montar o quebra-cabeça, vamos entender a imagem completa. Um Filtro de Bloom resolve um problema muito específico: verificar de forma ultra-eficiente se um elemento pode pertencer a um conjunto muito grande, sem precisar armazenar os elementos desse conjunto.

A palavra-chave aqui é "pode pertencer". O Filtro de Bloom é uma estrutura de dados probabilística. Isso significa que ele não te dá 100% de certeza. Ele pode te dizer duas coisas:

1. "Este item DEFINITIVAMENTE NÃO está no conjunto." (Zero falsos negativos)
2. "Este item PROVAVELMENTE ESTÁ no conjunto." (Existe uma pequena chance de ser um alarme falso, o que chamamos de falso positivo.)

Esse trade-off é o superpoder dele. Ao abrir mão da certeza absoluta, ganhamos uma economia de memória colossal. É por isso que ele é usado em sistemas de larga escala:

• Bancos de Dados (Google BigTable, Apache Cassandra): Para evitar buscas custosas em disco por chaves que não existem.
• Redes de Distribuição de Conteúdo (CDNs): Para checar se um item está no cache antes de buscar no servidor de origem.
• Segurança (Google Chrome): Para identificar URLs maliciosas, como no nosso exemplo inicial.

A ideia central é simples: em vez de guardar os dados, guardamos apenas suas "sombras".

A Anatomia do Filtro de Bloom

Imagine que um Filtro de Bloom é um esqueleto simples, composto por apenas duas partes:

1. Um Array de Bits: Pense nele como uma longa fileira de lâmpadas, todas inicialmente apagadas (valor 0). Este array é a única "memória" que o filtro tem.
2. Múltiplas Funções de Hash (k): O filtro usa um número k de funções de hash diferentes e independentes. Lembre-se, uma função de hash transforma uma entrada (como uma string) em um número (um índice para nosso array).

E é só isso. A beleza está na simplicidade.

Visualização:

• Array de Bits (tamanho m): [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
  

• Funções de Hash: hash1(), hash2(), hash3()

Como Funciona na Prática?

Como o Chrome adiciona um site malicioso à sua lista?

Adicionando um Item (add)

O Google pega a URL www.site-perigoso.com e a "insere" no filtro:

1. A URL é passada para cada uma das k=3 funções de hash.
2. Cada função retorna um número, que corresponde a uma posição (índice) no nosso array de lâmpadas.
   • hash1("www.site-perigoso.com") -> 2
   • hash2("www.site-perigoso.com") -> 5
   • hash3("www.site-perigoso.com") -> 8
3. O sistema vai até essas três posições e "acende as lâmpadas", ou seja, muda o valor do bit de 0 para 1.

Nosso array, que antes era [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], agora fica assim: [0, 0, 1, 0, 0, 1, 0, 0, 1, 0]

Esse processo é repetido para milhões de URLs maliciosas. No final, teremos um array com várias lâmpadas acesas, representando a "sombra" coletiva de todos os sites perigosos.

Verificando um Item (check)

Agora, você digita uma URL no seu navegador. O Chrome precisa verificar se ela é perigosa.

Cenário 1: www.site-seguro.com

1. A URL é passada pelas mesmas k=3 funções de hash.
   • hash1("www.site-seguro.com") -> 1
   • hash2("www.site-seguro.com") -> 4
   • hash3("www.site-seguro.com") -> 7
2. O Chrome verifica as lâmpadas nas posições 1, 4 e 7.
   • Array na posição 1: 0
   • Array na posição 4: 0
   • Array na posição 7: 0
3. A Regra de Ouro: Se PELO MENOS UMA das lâmpadas estiver apagada (0), o filtro responde: "DEFINITIVAMENTE NÃO". É impossível que essa URL esteja na lista, pois se estivesse, todas as suas lâmpadas teriam sido acesas.

Cenário 2: www.site-perigoso.com (ou um falso positivo)

1. A URL é passada pelas mesmas k=3 funções de hash.
   • hash1("www.site-perigoso.com") -> 2
   • hash2("www.site-perigoso.com") -> 5
   • hash3("www.site-perigoso.com") -> 8
2. O Chrome verifica as lâmpadas nas posições 2, 5 e 8.
   • Array na posição 2: 1
   • Array na posição 5: 1
   • Array na posição 8: 1
3. A Regra de Ouro (parte 2): Se TODAS as lâmpadas estiverem acesas (1), o filtro responde: "PROVAVELMENTE SIM".

Por que "provavelmente"? Porque é possível que outras URLs maliciosas, por pura coincidência, tenham acendido exatamente essas três lâmpadas. Isso é um falso positivo.

O Segredo da Eficiência

Agora a resposta para a pergunta do início: como ele ocupa tão pouca memória? A resposta é brilhante: O Filtro de Bloom NÃO ARMAZENA as URLs!

Ele não guarda a string "www.site-perigoso.com". Ele só armazena a "sombra" que a URL deixou no array de bits. A única coisa que ele guarda é um único e compacto array de 1s e 0s. Ele troca a certeza absoluta pelo armazenamento de uma representação probabilística.
É um trade-off genial.

Implementação em JS

Vamos colocar a mão na massa. Para nossa implementação, precisaremos de funções de hash. Criar boas funções de hash é uma ciência à parte, então para nosso exemplo, usaremos uma técnica comum: duas funções de hash simples que simulam o comportamento de k funções.

class BloomFilter {
  constructor(size = 100, hashCount = 3) {
    // O tamanho do nosso array de bits
    this.size = size;
    // O número de funções de hash
    this.hashCount = hashCount;
    // O array de bits, inicializado com 0s
    this.bitArray = new Array(size).fill(0);
  }
 
  // Primeira função de hash (simples)
  _hash1(item) {
    let hash = 0;
    for (let i = 0; i < item.length; i++) {
      const char = item.charCodeAt(i);
      hash = (hash << 5) - hash + char;
      hash |= 0; // Converte para um inteiro de 32bit
    }
    return Math.abs(hash) % this.size;
  }
 
  // Segunda função de hash (simples)
  _hash2(item) {
    let hash = 5381;
    for (let i = 0; i < item.length; i++) {
      const char = item.charCodeAt(i);
      hash = (hash * 33) ^ char;
    }
    return Math.abs(hash) % this.size;
  }
 
  // Gera 'k' hashes a partir das duas funções base.
  // Técnica conhecida como "double hashing".
  _getHashes(item) {
    const hashes = [];
    const h1 = this._hash1(item);
    const h2 = this._hash2(item);
 
    for (let i = 0; i < this.hashCount; i++) {
      // (h1 + i * h2) % size
      const combinedHash = (h1 + i * h2) % this.size;
      hashes.push(combinedHash);
    }
    return hashes;
  }
 
  /**
   * Adiciona um item ao filtro.
   * @param {string} item - O item a ser adicionado.
   */
  add(item) {
    const hashes = this._getHashes(item);
    hashes.forEach(hashIndex => {
      this.bitArray[hashIndex] = 1;
    });
    console.log(`Adicionado '${item}'. Estado do filtro: [${this.bitArray.join(', ')}]`);
  }
 
  /**
   * Verifica se um item pode estar no filtro.
   * @param {string} item - O item a ser verificado.
   * @returns {boolean} - false se o item definitivamente não está, true se ele provavelmente está.
   */
  check(item) {
    const hashes = this._getHashes(item);
    for (const hashIndex of hashes) {
      if (this.bitArray[hashIndex] === 0) {
        // Se qualquer bit for 0, o item definitivamente não está no conjunto.
        console.log(`Checando '${item}': DEFINITIVAMENTE NÃO ESTÁ.`);
        return false;
      }
    }
    // Se todos os bits forem 1, o item provavelmente está no conjunto.
    console.log(`Checando '${item}': PROVAVELMENTE ESTÁ.`);
    return true;
  }
}
 
// --- Testando nosso Filtro de Bloom ---
const bloom = new BloomFilter(18, 3); // Tamanho 18, 3 hashes
 
// Adicionando alguns itens
bloom.add("maçã");
bloom.add("banana");
 
console.log("\n--- Checando itens ---");
 
// Checando itens que adicionamos
bloom.check("maçã"); // Deve retornar true
bloom.check("banana"); // Deve retornar true
 
// Checando um item que NÃO adicionamos
bloom.check("uva"); // Provavelmente retornará false
 
// Checando um possível falso positivo
// A palavra 'gato' pode, por coincidência, mapear para bits que já foram ligados por 'maçã' e 'banana'
bloom.check("gato"); 

A Limitação de Não Poder Deletar

Um Filtro de Bloom padrão tem uma limitação importante: você não pode deletar um item. Por quê? Porque se você mudar um bit de 1 para 0, pode estar invalidando a existência de outro item que, por coincidência, usou aquele mesmo bit. Existem variações como o Counting Bloom Filter que resolvem isso, mas com um custo maior de memória.

Conclusão

Da próxima vez que seu navegador te proteger de um site perigoso sem deixar seu PC lento, você saberá que por trás dessa "mágica" existe um conceito sensacional.

O Filtro de Bloom nos diz muito sobre trade-offs: às vezes, sacrificar a certeza absoluta é a chave para construir sistemas incrivelmente rápidos e eficientes.

E você? Já usou um Filtro de Bloom em algum projeto ou consegue pensar em outra aplicação para ele? Qual foi o trade-off mais interessante que você já teve que fazer em um sistema?

Compartilhe suas experiências aqui nos comentários!