14 - Performance et sécurité

Ce que tu vas apprendre

• Comment fonctionne un moteur regex (NFA a backtracking)
• Ce qu'est le backtracking catastrophique et comment le détecter
• Les attaques ReDoS (Regular Expression Denial of Service)
• Comment reperer les patterns dangereux
• Les groupes atomiques et quantificateurs possessifs (hors JS)
• Les outils pour auditer tes regex

Prerequisites

• 13 - Unicode et regex
• Comprendre les quantificateurs greedy et lazy

La première fois que j'ai fait planter un serveur de production, c'etait a cause d'une regex. Un pattern qui semblait parfaitement raisonnable, sur une chaîne de 50 caractères, a mis le CPU a 100% pendant 30 secondes. Le serveur Node.js, single-threaded, ne repondait plus. Tout ca a cause d'un quantificateur mal place.

Comment fonctionne un moteur regex

La plupart des moteurs regex (JavaScript, Python, Java, .NET, Perl) utilisent un NFA a backtracking (Nondeterministic Finite Automaton). Comprendre ce mecanisme est la clé pour éviter les pièges de performance.

Le principe : le moteur essaie de faire correspondre le pattern de gauche a droite. Quand il a plusieurs choix possibles (a cause d'un |, d'un *, d'un +...), il en choisit un et avance. Si ca echoue plus loin, il revient en arriere (backtrack) et essaie le choix suivant.

Pattern:  a+b
Chaine:   "aaac"

Etape 1: a+ matche "aaa" (greedy, prend le maximum)
Etape 2: b ne matche pas "c" -> backtrack
Etape 3: a+ matche "aa" (lache un 'a')
Etape 4: b ne matche pas "a" -> backtrack
Etape 5: a+ matche "a"
Etape 6: b ne matche pas "a" -> backtrack
Etape 7: plus de possibilites -> echec

Pour a+b sur "aaac", le moteur fait 4 tentatives. C'est raisonnable. Le problème arrive quand le nombre de combinaisons explose.

Backtracking catastrophique

Le backtracking catastrophique se produit quand le moteur doit explorer un nombre exponentiel de combinaisons avant de conclure qu'il n'y a pas de match.

L'exemple classique : (a+)+ sur "aaaaaaaaaaab".

javascript// NE PAS EXECUTER en production
const regex = /(a+)+b/;
const input = "a".repeat(25) + "c"; // 25 'a' suivis de 'c'

console.time("regex");
regex.test(input);  // Prend des SECONDES, voire des MINUTES
console.timeEnd("regex");

Pourquoi ca explose ? Le pattern (a+)+ peut décomposer "aaaa" de multiples facons :

• (aaaa)
• (aaa)(a)
• (aa)(aa)
• (aa)(a)(a)
• (a)(aaa)
• (a)(aa)(a)
• (a)(a)(aa)
• (a)(a)(a)(a)

Pour n caractères 'a', il y a 2^(n-1) facons de les repartir dans les groupes. Quand le b final ne matche pas, le moteur les essaie toutes avant de conclure l'échec. Avec 25 caractères, ca fait 16 millions de combinaisons. Avec 30, un milliard.

Attaques ReDoS

ReDoS (Regular Expression Denial of Service) exploite le backtracking catastrophique pour faire planter un serveur. L'attaquant envoie une chaîne specialement craftee qui force le moteur regex a tourner indefiniment.

Scénario typique :

javascript// Validation d'email naive cote serveur
const emailRegex = /^([a-zA-Z0-9]+\.?)+@[a-zA-Z0-9]+\.[a-zA-Z]+$/;

// L'attaquant envoie :
const malicious = "a".repeat(50) + "@";
emailRegex.test(malicious); // Le serveur est bloque

Ce n'est pas theorique. Des vulnérabilités ReDoS ont touche des projets majeurs : npm packages, frameworks web, meme des services cloud. La base CVE en contient des dizaines.

Ce qui rend ReDoS dangereux, c'est que :

• Le pattern semble raisonnable a l'oeil nu
• Ca fonctionne parfaitement sur des entrees valides
• Seules les entrees invalides et specialement construites declenchent le problème
• En Node.js (single-thread), ca bloque toute l'application

Comment reperer les patterns dangereux

Les patterns a risque ont une structure commune : quantificateurs imbriques ou alternances qui se chevauchent avec un quantificateur externe.

Patterns dangereux courants :

(a+)+          Quantificateur dans un groupe quantifie
(a|a)+         Alternances qui matchent la meme chose
(a+b?)+        Quantificateur optionnel dans un groupe quantifie
(\w+\s?)+      Tres courant et tres dangereux
(.*a){10}      Dot-star dans un groupe quantifie

La regle empirique : si tu as un quantificateur (+, *, {n,}) a l'intérieur d'un groupe qui est lui-meme quantifie, tu as probablement un problème.

javascript// Dangereux : quantificateurs imbriques
/(\w+\s)+/.test(longString)

// Sur : pas d'imbrication
/[\w\s]+/.test(longString)

Groupes atomiques et quantificateurs possessifs

Certains moteurs (Java, .NET, PCRE, mais pas JavaScript) offrent des mecanismes pour empecher le backtracking.

Quantificateurs possessifs (++, *+, ?+)

Un quantificateur possessif ne rend jamais ce qu'il a consomme. Pas de backtracking.

# Syntaxe PCRE / Java (pas JS)
Pattern: a++b
Chaine:  "aaac"

a++ matche "aaa" et ne backtrack JAMAIS
b ne matche pas "c" -> echec immediat (pas de tentatives supplementaires)

Groupes atomiques (?>...)

Meme principe mais pour un groupe entier :

# Syntaxe PCRE / Java (pas JS)
(?>a+)b

En JavaScript, tu n'as ni l'un ni l'autre. Tes armes sont la prevention et la simplification des patterns.

Alternatives sures

Voici comment reecrire les patterns dangereux :

javascript// Dangereux : (a+)+
// Sur : a+ (le groupe externe est inutile)
/a+b/

// Dangereux : (\w+\s?)+
// Sur : utiliser une classe de caracteres
/[\w\s]+/

// Dangereux : ^(\w+\.)*\w+@\w+\.\w+$
// Sur : limiter la longueur et simplifier
/^[^\s@]{1,64}@[^\s@]{1,255}$/

// Dangereux : (.+,)+.+
// Sur : decrire ce qu'on veut vraiment
/^[^,]+(,[^,]+)*$/

Principes generaux :

1. Evite les quantificateurs imbriques : (a+)+ est presque toujours un bug
2. Utilise des classes de caractères au lieu de groupes avec alternance : [\w\s] plutot que (\w|\s)
3. Utilise des negations : [^,]+ plutot que .+ quand tu sais quel caractère termine la sequence
4. Limite la longueur : {1,100} plutot que + quand c'est possible
5. Valide la longueur de l'entree avant d'appliquer la regex

javascriptfunction safeMatch(input, regex, maxLength = 1000) {
  if (input.length > maxLength) {
    return false;
  }
  return regex.test(input);
}

Outils de détection

Ne compte pas uniquement sur ton oeil pour reperer les patterns dangereux. Utilise des outils automatises.

safe-regex (npm)

javascriptconst safe = require("safe-regex");

safe(/(a+)+/);           // false (dangereux)
safe(/^[a-zA-Z0-9]+$/);  // true (sur)

recheck (npm)

Plus sophistique que safe-regex, il analyse les chemins d'exécution du NFA :

bashnpx recheck "(a+)+b"
# Resultat : vulnerable, complexite exponentielle

regex101.com

Le debugger de regex101 te montre le nombre de steps du moteur. Si tu vois le compteur exploser sur une chaîne qui ne matche pas, c'est un signal d'alarme.

Je recommande d'intégrer safe-regex ou recheck dans ta CI, surtout si tes regex traitent des entrees utilisateur. Un article sur la securisation des pipelines CI est disponible sur paltemps.fr.

Résumé

• Les moteurs regex utilisent le backtracking : quand un choix echoue, ils reviennent en arriere
• Les quantificateurs imbriques ((a+)+) causent un backtracking exponentiel
• Les attaques ReDoS exploitent ca pour bloquer les serveurs
• Repere les patterns dangereux : quantificateur dans un groupe quantifie
• JavaScript n'a pas de groupes atomiques ni de quantificateurs possessifs
• Simplifie tes patterns, limite les longueurs, utilise des classes de caractères
• Integre safe-regex ou recheck dans ta CI

Article précédent : 13 - Unicode et regex Article suivant : 15 - Parsing du monde réel

Sources

• OWASP - Regular Expression Denial of Service
• Russ Cox - Regular Expression Matching Can Be Simple And Fast
• npm safe-regex