Programme Leçon 47 sur 156 · Construire un bloqueur
Construire un bloqueur

Comparer les requêtes aux règles

Pourquoi c'est important Un bloqueur vérifie chaque requête d'une page, souvent plus de cent par page, contre des dizaines de milliers de règles. Si cette vérification est lente, chaque page paraît lente, et les gens désactivent le bloqueur. Rapide et juste, c'est ce qui rend la protection utilisable.

Deux tâches : la bonne réponse, vite

Pense à une bibliothèque de 5 000 livres. Pour en trouver un, tu ne lirais pas chaque tranche depuis la première étagère. Tu vas à la bonne section, puis à la bonne étagère. Un bloqueur doit faire pareil : sauter directement aux quelques règles qui pourraient correspondre, et ne vérifier que celles-là.

Cet exercice est noté sur les deux. Les tests comptent combien de fois ta fonction decide appelle rule_matches pour une requête, et le budget est de 20 vérifications avec 5 000 règles chargées. On compte les vérifications au lieu de te chronométrer, donc un téléphone lent et un ordinateur rapide sont notés de la même façon.

Étape 1 : les jokers

Joker (wildcard) : un symbole qui veut dire « n'importe quels caractères ». Dans les listes de filtres, c'est *, donc /beacon/*/hit correspond à /beacon/42/hit et /beacon/abc/hit.

Coupe le motif à chaque *, puis trouve les morceaux dans le texte, dans l'ordre, chacun après le précédent :

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) renvoie où commence piece, en ne cherchant qu'à partir de la position pos, ou -1 s'il n'y est pas. Remarque que dans les listes de filtres, ? et . sont des caractères ordinaires, donc n'utilise pas d'expression régulière ni fnmatch, qui les traitent comme spéciaux.

Étape 2 : une règle contre une requête

rule_matches(rule, url, third_party) répond oui ou non pour une règle :

  • Une règle avec third_party activé ne correspond jamais à une requête première.
  • Une règle de domaine adco.example correspond à l'hôte adco.example ou à tout hôte qui finit par .adco.example. Le point compte : notadco.example est quelqu'un d'autre.
  • Une règle de motif correspond quand wildcard_in(value, url.lower()) est vrai.

Étape 3 : un index, pour ne vérifier que quelques règles

Index : une structure construite une fois qui permet de trouver des choses sans tout fouiller, comme l'index à la fin d'un livre. Ici : un dict qui associe un nom d'hôte aux règles de cet hôte.

Un dict Python trouve une clé en une étape, quel que soit le nombre de clés. Donc construis, une fois :

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

Pour une requête vers img.adco.example, cherche chaque terminaison de l'hôte : img.adco.example, adco.example, example. Ça fait trois recherches au lieu de 5 000 vérifications. Ajoute les quelques règles de motif (les vrais bloqueurs les indexent aussi, par un petit morceau de texte qu'elles doivent contenir ; on les garde dans une simple liste).

Étape 4 : décider, les exceptions gagnent

Vérifie chaque candidate. Si une règle qui correspond est une exception, la réponse est "allow", point final. Sinon, si une règle de blocage a correspondu, "block" ; si rien n'a correspondu, "allow". Les exceptions existent parce que les listes attrapent parfois des choses dont un site a vraiment besoin, comme cdn.example, qui sert une bibliothèque inoffensive.

Une idée reçue

« Plus de règles veut dire un bloqueur plus lent. » Avec un bon index, non : chercher un hôte dans un dict coûte à peu près pareil avec 50 règles ou 50 000. Ce qui ralentit un bloqueur, c'est de vérifier les règles une par une.

Essaie Une fois réussi, modifie decide pour boucler sur chaque règle de la liste (sans index) et relance les tests. Le test de budget échoue avec un compte d'environ 5 000. Ce nombre, c'est le travail que ton index économise sur chaque requête de chaque page.

Dans d'autres langages

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
}

Récap

  • Motifs avec jokers : coupe à * et trouve les morceaux dans l'ordre.
  • Les règles de domaine correspondent à l'hôte ou à tout sous-domaine, comparés étiquette par étiquette.
  • Un index (un dict par hôte) veut dire quelques recherches au lieu de milliers de vérifications.
  • Une exception qui correspond l'emporte toujours sur une règle de blocage.
À ton tour

Écris quatre fonctions. wildcard_in(pattern, text) : True quand les morceaux de pattern entre les signes * apparaissent tous dans text, dans l'ordre. rule_matches(rule, url, third_party) : True quand un dict de règle (de la leçon précédente) correspond à la requête. build_index(rules) : organise les règles comme tu veux pour que decide puisse en sauter la plupart. decide(index, url, third_party) : renvoie "block" ou "allow", une exception qui correspond l'emportant, en appelant rule_matches au plus 20 fois par requête quand 5 000 règles sont chargées.

Tu as repéré un problème dans cette leçon ? Signale-le · Pose une question sur cette leçon

Cet exercice s'ouvre bientôt

Termine la leçon précédente pour débloquer celle-ci. Tout le cours est gratuit, aucun compte n'est requis, et tu peux lire cette leçon dès maintenant.