Performance des regex: éviter le backtracking excessif

Performances des regex : une expression peut faire tomber tout le serveur

Le retour arrière catastrophique (Catastrophic Backtracking) peut faire passer le temps de correspondance d'une expression régulière de millisecondes à des heures.

Scénario	Regex	Longueur d'entrée	Durée
Correspondance normale	`/^abc$/`	100	<1ms
Retour arrière linéaire	`/a*b/`	100	~1ms
Retour arrière exponentiel	`/(a+)+b/`	30	~10s
Retour arrière exponentiel	`/(a)b/`	30	~10s

I. Principe du mécanisme de retour arrière

Fonctionnement du moteur NFA

JavaScript utilise un moteur NFA (Automate Fini Non Déterministe) avec un algorithme de retour arrière :

Entrée : "aaaac"
Regex : /(a+)+c/

Processus de correspondance :
1. (a+) correspond à "aaaa" → essaie +c → ne correspond pas à 'c'
2. Retour arrière : (a+) correspond à "aaa" → (a+) correspond à "a" → essaie +c → ne correspond pas
3. Retour arrière : (a+) correspond à "aa" → (a+) correspond à "aa" → essaie +c → ne correspond pas
4. Retour arrière : (a+) correspond à "aa" → (a+) correspond à "a" → (a+) correspond à "a" → ...
5. ... retour arrière exponentiel

Calcul du nombre de retours arrière

Pour /(a+)+b/ correspondant à "aaa..." (n a) :

Nombre de retours arrière ≈ 2^n

n=10 : ~1 024 fois
n=20 : ~1 048 576 fois
n=30 : ~1 073 741 824 fois

II. Modèles courants de retour arrière catastrophique

Modèle 1 : Quantificateurs imbriqués

// Retour arrière catastrophique
/(a+)+b/     // Quantificateur + imbriqué
/(a*)*b/     // Quantificateur * imbriqué
/(\w+)+@/    // \w+ imbriqué

// Correction : éviter les quantificateurs imbriqués
/a+b/        // Quantificateur à un seul niveau
/(\w+)@/     // Quantificateur à un seul niveau

Modèle 2 : Alternance ordonnée

// Retour arrière catastrophique : options d'alternance avec préfixe commun
/(a|ab)+c/

// Avec l'entrée "abababab..." sans correspondance, le moteur essaie toutes les combinaisons
// Nombre de retours arrière ≈ O(2^n)

// Correction : extraire le préfixe commun
/a(b?)+c/

Modèle 3 : Quantificateurs chevauchants

// Retour arrière catastrophique
/.*.*=/

// Les deux .* peuvent correspondre au même contenu, générant de nombreux retours arrière

// Correction : fusionner les quantificateurs
/.*=/

Modèle 4 : Piège des références arrière

// Retour arrière catastrophique
/^(b+)(a+)\1$/

// Avec l'entrée "bbbbaaaa", \1 essaie toutes les subdivisions de b+

// Correction : si possible, éviter les références arrière, ou limiter la portée du quantificateur
/^(b+)(a+)\1$/.test(input) // Uniquement pour les entrées courtes

III. Techniques d'optimisation

Technique 1 : Spécifier les classes de caractères

// Lent : . correspond à tout caractère, beaucoup de retours arrière
/.*foo/

// Rapide : [^\n]* ne correspond pas aux sauts de ligne, réduit les retours arrière
/[^\n]*foo/

// Plus rapide : si l'on sait que avant foo il n'y a que des lettres
/[a-z]*foo/

Technique 2 : Ancrage pour réduire l'espace de recherche

// Lent : essaie de correspondre depuis chaque position
/foo/

// Rapide : si foo est en début de ligne
/^foo/

// Rapide : si foo est en fin de ligne
/foo$/

// Rapide : ancrage des deux côtés
/^foo$/

Technique 3 : Utilisation correcte des quantificateurs non-gloutons

// Scénario : extraire le contenu des balises <b>

// Lent : quantificateur glouton + retours arrière
/<b>(.*)<\/b>/

// Rapide : quantificateur non-glouton (mais retours arrière possibles)
/<b>(.*?)<\/b>/

// Le plus rapide : classe de caractères d'exclusion (zéro retour arrière)
/<b>([^<]*)<\/b>/

Méthode	Correspondance `<b>hello</b><b>world</b>`	Retours arrière
`(.*)`	`hello</b><b>world`	Multiples
`(.*?)`	`hello`	Peu
`([^<]*)`	`hello`	Zéro

Technique 4 : Groupes atomiques (ES2024+)

// Groupe atomique (?>...) une fois correspondu, pas de retour arrière
const regex = /^(?>a+)+b$/;

// Équivalent à : si a+ a correspondu, pas de retour arrière pour que le + externe réessaie
// Correspond à "aaab" → succès
// Correspond à "aaa" → échec immédiat (sans retour arrière exponentiel)

Technique 5 : Quantificateurs possessifs (certains moteurs)

// Quantificateur possessif a++ ne libère pas pour le retour arrière après correspondance
// JavaScript ne le supporte pas, mais peut être simulé avec des groupes atomiques
const regex = /^(?>(a+))b$/;

Technique 6 : Précompilation + réutilisation

// Lent : créer un nouveau RegExp à chaque fois
function validate(input) {
  return /^[\w.+-]+@[\w-]+\.[\w.]+$/.test(input);
}

// Rapide : précompiler
const EMAIL_REGEX = /^[\w.+-]+@[\w-]+\.[\w.]+$/;
function validate(input) {
  return EMAIL_REGEX.test(input);
}

IV. Outils d'analyse de performance

Utiliser l'outil regex de ToolsKu

Ouvrir l'Outil d'Expressions Régulières
Saisir l'expression régulière et le texte de test
Voir les résultats de correspondance et le temps
Ajuster la regex, comparer les performances avant et après optimisation

Mesure intégrée en JS

function measureRegex(regex, input, iterations = 1000) {
  const start = performance.now();
  for (let i = 0; i < iterations; i++) {
    regex.test(input);
  }
  const end = performance.now();
  return {
    totalTime: end - start,
    avgTime: (end - start) / iterations,
    iterations,
  };
}

// Comparaison
const slow = measureRegex(/(a+)+b/, 'a'.repeat(25));
const fast = measureRegex(/a+b/, 'a'.repeat(25));
console.log(`Lent : ${slow.avgTime}ms, Rapide : ${fast.avgTime}ms`);

Bibliothèque recheck pour détecter les regex dangereuses

npm install recheck

import { check } from 'recheck';

const result = check(/(a+)+b/);
// { safe: false, complexity: 'exponential' }

const result2 = check(/a+b/);
// { safe: true, complexity: 'linear' }

V. Comparaison des performances des expressions régulières courantes

Regex	Complexité	Sûre	Version optimisée
`/(a+)+b/`	Exponentielle	❌	`/a+b/`
`/(a\|ab)+c/`	Exponentielle	❌	`/a(b?)+c/`
`/..=/`	Exponentielle	❌	`/.*=/`
`/(\d+){1,10}/`	Polynomiale	⚠️	`/\d{1,10}/`
`/^[a-z]+$/`	Linéaire	✅	—
`/^\d{4}-\d{2}-\d{2}$/`	Constante	✅	—

VI. Protection côté serveur

Protection par timeout

function safeRegexTest(regex, input, timeoutMs = 100) {
  const start = Date.now();
  const result = regex.test(input);
  if (Date.now() - start > timeoutMs) {
    throw new Error('Regex timeout: possible catastrophic backtracking');
  }
  return result;
}

Moteur re2 (garantie de temps linéaire)

import RE2 from 're2';

// RE2 garantit un temps linéaire, sans explosion de retours arrière
const regex = new RE2('(a+)+b');
regex.test('a'.repeat(100)); // Sûr, ne se bloquera pas

Limiter la longueur d'entrée

function validateWithLimit(regex, input, maxLength = 1000) {
  if (input.length > maxLength) {
    throw new Error(`Input exceeds maximum length: ${maxLength}`);
  }
  return regex.test(input);
}

VII. Liste des meilleures pratiques

Éviter les quantificateurs imbriqués : (a+)+ → a+
Spécifier les classes de caractères : . → [^\n] ou classe plus spécifique
Extraire les préfixes communs : (a|ab) → a(b?)
Utiliser des classes d'exclusion au lieu de non-glouton : (.*?) → ([^<]*)
Ancrage pour réduire l'espace de recherche : ^ / $
Précompiler les expressions régulières : éviter la création répétée
Utiliser recheck pour détecter : vérifier automatiquement les regex dangereuses en CI
Protection par timeout côté serveur : prévenir le DoS par regex
Limiter la longueur d'entrée : réduire l'impact du pire cas