Conteúdo do curso Lição 47 de 156 · Construa um bloqueador
Construa um bloqueador

Comparar requisições com regras

Por que isso importa Um bloqueador confere cada requisição que uma página faz, muitas vezes mais de cem por página, contra dezenas de milhares de regras. Se essa conferência for lenta, toda página parece lenta, e as pessoas desligam o bloqueador. Rápido e correto é o que torna a proteção usável.

Dois trabalhos: a resposta certa, rápido

Pense numa biblioteca com 5.000 livros. Para achar um, você não leria cada lombada a partir da primeira estante. Você vai até a seção certa, depois até a prateleira certa. Um bloqueador deveria fazer o mesmo: pular direto para as poucas regras que poderiam corresponder e conferir só essas.

Este exercício é avaliado nas duas coisas. Os testes contam quantas vezes o seu decide chama rule_matches para uma requisição, e o orçamento é de 20 verificações com 5.000 regras carregadas. Contamos verificações em vez de cronometrar você, então um celular lento e um notebook rápido são avaliados do mesmo jeito.

Passo 1: curingas

Curinga: um símbolo que representa "quaisquer caracteres". Nas listas de filtros é o *, então /beacon/*/hit corresponde a /beacon/42/hit e a /beacon/abc/hit.

Divida o padrão em cada * e depois encontre os pedaços no texto, em ordem, cada um depois do anterior:

wildcard_in("*/collect?*cid=", "https://m.example/collect?x=1&cid=9")
# pieces: "/collect?" then "cid="  -> both found, in order -> True

wildcard_in("a*b", "b then a")
# "a" found at position 7, then no "b" after it -> False

text.find(piece, pos) retorna onde piece começa, procurando só a partir da posição pos, ou -1 se não estiver lá. Repare que, nas listas de filtros, ? e . são caracteres comuns, então não use uma expressão regular nem fnmatch, que os tratam como especiais.

Passo 2: uma regra contra uma requisição

rule_matches(rule, url, third_party) responde sim ou não para uma regra:

  • Uma regra com third_party definido nunca corresponde a uma requisição de primeira parte.
  • Uma regra de domínio adco.example corresponde ao host adco.example ou a qualquer host que termine em .adco.example. O ponto importa: notadco.example é outra pessoa.
  • Uma regra de padrão corresponde quando wildcard_in(value, url.lower()) é verdadeiro.

Passo 3: um índice, para conferir só algumas regras

Índice: uma estrutura construída uma vez que permite encontrar coisas sem procurar em tudo, como o índice no fim de um livro. Aqui: um dict do nome do host para as regras daquele host.

Um dict do Python encontra uma chave num único passo, não importa quantas chaves ele tenha. Então construa, uma vez:

index = {"domains": {"adco.example": [rule, ...], ...},
         "patterns": [rule, rule, ...]}

Para uma requisição a img.adco.example, procure cada terminação do host: img.adco.example, adco.example, example. São três consultas em vez de 5.000 verificações. Adicione as poucas regras de padrão (bloqueadores reais também as indexam, por um pedacinho de texto que elas precisam conter; nós as mantemos numa lista simples).

Passo 4: decidir, com as exceções vencendo

Confira cada candidata. Se alguma regra que corresponde for uma exceção, a resposta é "allow", e ponto final. Senão, se alguma regra de bloqueio correspondeu, "block"; se nada correspondeu, "allow". As exceções existem porque as listas às vezes pegam coisas de que um site realmente precisa, como cdn.example, que serve uma biblioteca inofensiva.

Um equívoco comum

"Mais regras significa um bloqueador mais lento." Com um bom índice, não: procurar um host num dict custa mais ou menos o mesmo com 50 regras ou com 50.000. O que deixa um bloqueador lento é conferir as regras uma por uma.

Experimente Depois de passar, mude decide para percorrer todas as regras da lista (sem índice) e rode os testes de novo. O teste de orçamento falha com uma contagem de cerca de 5.000. Esse número é o trabalho que o seu índice economiza em cada requisição de cada página.

Em outras linguagens

JavaScript:

function wildcardIn(pattern, text) {
  let pos = 0;
  for (const piece of pattern.split("*")) {
    if (!piece) continue;
    const at = text.indexOf(piece, pos);
    if (at === -1) return false;
    pos = at + piece.length;
  }
  return true;
}

// Index: a Map from host to rules; look up each ending of the host.
function candidates(index, host) {
  const parts = host.split(".");
  const out = [];
  for (let i = 0; i < parts.length; i++) {
    out.push(...(index.domains.get(parts.slice(i).join(".")) || []));
  }
  return out.concat(index.patterns);
}

Go:

func wildcardIn(pattern, text string) bool {
    pos := 0
    for _, piece := range strings.Split(pattern, "*") {
        if piece == "" {
            continue
        }
        at := strings.Index(text[pos:], piece)
        if at < 0 {
            return false
        }
        pos += at + len(piece)
    }
    return true
}

Resumo

  • Padrões com curinga: divida em * e encontre os pedaços em ordem.
  • Regras de domínio correspondem ao host ou a qualquer subdomínio, comparando rótulo por rótulo.
  • Um índice (um dict por host) significa poucas consultas em vez de milhares de verificações.
  • Uma exceção que corresponde sempre vence uma regra de bloqueio.
Sua vez

Escreva quatro funções. wildcard_in(pattern, text): True quando os pedaços de pattern entre os sinais * aparecem todos em text, em ordem. rule_matches(rule, url, third_party): True quando um dict de regra (da lição anterior) corresponde à requisição. build_index(rules): organize as regras do jeito que quiser, para que decide possa pular a maioria delas. decide(index, url, third_party): retorne "block" ou "allow", com qualquer exceção que corresponda vencendo, chamando rule_matches no máximo 20 vezes por requisição quando 5.000 regras estão carregadas.

Viu um problema nesta lição? Reporte-o · Pergunte sobre esta lição

Este exercício abre em breve

Termine a lição anterior para que esta seja desbloqueada. O curso inteiro é gratuito, não precisa de conta, e você pode ler esta lição agora mesmo.