💻 computer science

Towards Efficient Matching of Regexes with Backreferences using Register Set Automata (Technical Report)

Ce rapport technique propose les automates à registres d'ensembles (RSA), un modèle étendu permettant une correspondance rapide et robuste des expressions rationnelles avec références arrière en offrant une complexité linéaire ou quadratique et en rendant le problème de l'emptiness décidable.

Auteurs originaux : Vojtěch Havlena, Lukáš Holík, Ondřej Lengál, Jan Vašák, Sabína Gulčíková

Publié 2026-04-16

📖 5 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Vojtěch Havlena, Lukáš Holík, Ondřej Lengál, Jan Vašák, Sabína Gulčíková

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

🕵️‍♂️ Le Problème : L'Enquêteur qui perd la tête

Imaginez que vous êtes un détective (le logiciel) chargé de vérifier si un message (une chaîne de caractères) correspond à une règle précise (une expression régulière ou "regex").

Parfois, la règle est simple : "Trouve-moi un mot qui commence par 'Chat'". C'est facile et rapide.

Mais parfois, la règle est complexe et demande de la mémoire : "Trouve-moi un mot qui commence par 'Chat', puis n'importe quoi, puis qui se termine par le même mot que celui qui suivait 'Chat' au début."
En langage informatique, on appelle cela des références arrière (backreferences). Le détective doit se souvenir d'un détail précis vu plus tôt dans le texte pour vérifier s'il réapparaît plus tard.

Le problème actuel :
La plupart des détectives actuels travaillent par essais et erreurs (ce qu'on appelle le "backtracking").

Ils essaient une hypothèse : "Peut-être que ce mot est le bon ?" -> Non.
Ils annulent, ils essaient une autre hypothèse : "Peut-être que c'est celui-là ?" -> Non.
Ils recommencent encore et encore.

Si le texte est long et la règle complexe, le détective peut passer des heures à essayer des combinaisons qui ne mènent nulle part. C'est ce qu'on appelle une catastrophe de backtracking.
🚨 Conséquence : Un pirate peut envoyer un texte très long et piégé. Le détective, au lieu de répondre en une seconde, va s'épuiser à essayer des milliards de combinaisons. Le serveur qui l'héberge plante, et le site web devient inaccessible. C'est une attaque par déni de service (ReDoS).

💡 La Solution : Les "Registres à Collections" (RSA)

Les auteurs de ce papier (Vojtěch Havlena et son équipe) ont inventé un nouveau type de détective, qu'ils appellent les Automates à Registres d'Ensembles (Register Set Automata ou RSA).

Au lieu de travailler par essais et erreurs, ce nouveau détective est déterministe et organisé.

L'analogie du "Panier de Fruits" 🧺

Imaginez que votre détective a plusieurs paniers (des registres) pour ranger les fruits (les lettres ou les données) qu'il rencontre.

Les anciens détectives (Automates classiques) : Ils ne peuvent mettre qu'un seul fruit dans un panier à la fois. Si ils veulent se souvenir de deux pommes différentes, ils doivent faire des allers-retours complexes pour changer de panier. C'est lent et risqué.
Le nouveau détective (RSA) : Il a des paniers magiques qui peuvent contenir un ensemble de fruits.
- Il voit une pomme ? Il la met dans le panier "Pommes".
- Il voit une autre pomme ? Il la met aussi dans le panier "Pommes".
- Il voit une poire ? Il la met dans le panier "Poires".

La magie opère quand il doit vérifier une règle :
Au lieu de se demander "Est-ce que c'est la pomme A ou la pomme B ?", il regarde simplement dans son panier "Pommes".

"Est-ce que le fruit actuel est dans le panier ?"
Si oui -> Match !
Si non -> Pas de match.

Il n'a plus besoin de faire des allers-retours ou de deviner. Il consulte simplement son panier. C'est comme si, au lieu de chercher une aiguille dans une botte de foin en la touchant une par une, il avait un aimant géant qui attirait toutes les aiguilles d'un coup.

🚀 Pourquoi c'est génial ?

Vitesse et Prévisibilité :
Avec cette méthode, le temps de vérification dépend uniquement de la longueur du texte, pas de la complexité des règles. Que le texte fasse 100 caractères ou 1 million, le détective RSA avance d'un pas par lettre. C'est comme passer d'une voiture de course qui fait des embouteillages à un train à grande vitesse sur des rails droits.
Sécurité :
Puisqu'il n'y a plus d'essais et d'erreurs, un pirate ne peut plus faire planter le serveur en envoyant un texte piégé. Le détective RSA répond toujours en un temps raisonnable. C'est comme remplacer un gardien de sécurité qui s'endort en cherchant des indices par un scanner biométrique instantané.
La "Recette" (Algorithme) :
Les auteurs ne se sont pas contentés de l'idée. Ils ont écrit un algorithme (une recette de cuisine) qui permet de transformer n'importe quelle règle complexe (regex) en ce nouveau type de détective RSA.
- Ils ont aussi prouvé mathématiquement que cette méthode fonctionne pour une grande classe de règles utilisées dans la vraie vie (comme dans les formulaires web ou les filtres de spam).

📊 Les Résultats en Pratique

L'équipe a créé un prototype (un détective en version bêta) et l'a testé contre les meilleurs détectives actuels (comme ceux utilisés par Google, Python ou JavaScript).

Résultat : Sur des textes conçus pour faire planter les autres, le nouveau détective RSA a fini son travail en quelques millisecondes, là où les autres mettaient des secondes, des minutes, ou ne finissaient jamais (timeout).
Fiabilité : Même si la transformation de la règle en détective RSA prend un peu de temps au début (comme préparer un plan de route), une fois prêt, il est ultra-rapide et ne rate jamais son coup.

En résumé

Ce papier propose une nouvelle façon de vérifier des règles dans le texte. Au lieu de faire des milliers de suppositions (ce qui est lent et dangereux), ils utilisent des "paniers magiques" pour se souvenir de tout ce qu'ils ont vu. Cela rend la recherche de motifs plus rapide, plus sûre et impossible à bloquer par des attaques informatiques. C'est une avancée majeure pour la sécurité des sites web et des applications.

1. Problématique

La correspondance d'expressions régulières (regex) est une tâche fondamentale en informatique (recherche, validation de données, détection d'intrusion). Cependant, les expressions régulières étendues, en particulier celles contenant des références arrière (backreferences, ex: \1, \2), posent un défi majeur en termes de performance et de sécurité.

Dégradation des performances : La plupart des moteurs de regex modernes (comme PCRE2, Python re, Java java.util.regex) utilisent des algorithmes de retour en arrière (backtracking) pour gérer les références arrière. Dans le pire des cas, cela conduit à une complexité exponentielle par rapport à la longueur de l'entrée.
Attaques ReDoS : Cette inefficacité est exploitée via des attaques de type Regular Expression Denial of Service (ReDoS), où un attaquant envoie une entrée malveillante qui fait planter le serveur en saturant ses ressources CPU (ex: l'incident StackOverflow de 2016).
Limites des solutions actuelles : Les moteurs performants basés sur des automates déterministes (comme RE2 ou HyperScan) ne supportent pas les références arrière car la déterminisation des automates classiques (NFA/DFA) échoue face à ces fonctionnalités. De plus, le problème de correspondance pour les regex avec références arrière est théoriquement NP-dur.

L'objectif est de concevoir un modèle d'automate capable de traiter une large classe de regex avec références arrière de manière déterministe, garantissant ainsi une complexité de temps linéaire (ou quadratique) et éliminant les risques de ReDoS.

2. Méthodologie et Modèle Proposé

Les auteurs introduisent un nouveau modèle formel appelé Automates à Ensembles de Registres (Register Set Automata - RSA).

A. Automates à Ensembles de Registres (RSA)

Contrairement aux automates à registres classiques (RA) qui stockent une seule valeur de données par registre, les RSA permettent aux registres de contenir des ensembles de symboles (valeurs de données).

Opérations supportées :
- Ajout de la valeur d'entrée actuelle à un registre.
- Fusion (union) du contenu de plusieurs registres.
- Effacement de registres.
- Tests d'appartenance (vérifier si une valeur est présente dans un registre).
Avantage clé : Cette capacité à stocker des ensembles permet de simuler le comportement non déterministe (le "deviner" d'une valeur) de manière déterministe en accumulant toutes les possibilités potentielles dans un ensemble.

B. Algorithme de Déterminisation (NRA $\to$ DRSA)

L'article propose un algorithme (semi-algorithme) pour transformer un grand nombre d'automates à registres non déterministes (NRA) en Automates à Ensembles de Registres Déterministes (DRSA).

Construction : L'algorithme utilise une construction de type "sous-ensemble" (comme pour les NFA vers DFA) mais adaptée aux registres. Il suit un ensemble d'états possibles et une carte de la "taille" des registres (0, 1, ou plus de 1 élément).
Gestion de l'imprécision : Pour éviter une explosion combinatoire ou des approximations incorrectes, l'algorithme utilise trois techniques :
1. Classes de taille de registre : Pour distinguer si un registre contient une seule valeur ou plusieurs, ce qui est crucial pour les tests d'inégalité.
2. Vérification de la sur-approximation cartésienne : Pour s'assurer que les dépendances entre les valeurs des registres ne sont pas perdues lors de la fusion.
3. Effondrement des choix (Choice collapse) : Lors d'un test d'égalité positif, les choix non déterministes sont réduits à une seule valeur cohérente.
Conditions de succès : L'algorithme est complet pour la classe des langages obtenus par combinaison booléenne d'automates à un registre sans tests d'inégalité ( $B(NRA^=_1)$ ).

C. Compilation des Regex vers RSA

Les auteurs développent un algorithme basé sur les dérivées partielles d'Antimirov pour convertir directement une large classe de regex avec références arrière (notamment celles avec des groupes de capture de longueur unitaire) en NRA, qui sont ensuite transformés en DRSA.

Complexité de correspondance :
- Pour un alphabet fini : $O(|D| \cdot |w| \cdot |R|^2)$ , où $|D|$ est la taille du domaine de données, $|w|$ la longueur du texte et $|R|$ le nombre de registres.
- Pour un alphabet infini : $O(|w|^2 \cdot |R|^2)$ .
- Pour les automates "sans copie" (copy-free), la complexité s'améliore à $O(|R| \cdot |w|)$ .

3. Contributions Clés

Introduction du modèle RSA : Définition formelle, analyse des propriétés de clôture (union, intersection, non-clôture par complément pour les RSA non déterministes) et positionnement dans le paysage des automates sur mots de données.
Complexité du problème de vide : Démonstration que le problème de vide pour les RSA est décidable mais complet pour la classe $F_\omega$ (complexité Ackermannienne), ce qui est plus élevé que pour les automates à registres classiques (PSPACE-complet), mais reste décidable.
Algorithme de déterminisation : Un algorithme (semi-)complet pour transformer une sous-classe significative de NRA en DRSA, permettant ainsi une correspondance déterministe et robuste.
Algorithme de compilation Regex $\to$ NRA : Utilisation des dérivées d'Antimirov pour gérer les références arrière et les groupes de capture.
Implémentation et Validation Expérimentale : Développement d'un prototype (rsamatch) et comparaison avec des moteurs d'état de l'art.

4. Résultats Expérimentaux

Les auteurs ont évalué leur prototype rsamatch (écrit en Python) sur un ensemble de données réel contenant des regex vulnérables aux attaques ReDoS (générées par l'outil Rengar).

Performance : Sur 1 246 regex supportés, rsamatch a traité 99,8 % des cas en moins d'une seconde. En comparaison, les moteurs standards (grep, pcre2, Python re, Java, .NET) ont souvent dépassé le temps limite de 100 secondes ou ont échoué.
Robustesse : La déviation standard des temps d'exécution de rsamatch est d'un ordre de grandeur inférieur à celle des autres moteurs, prouvant une prédictibilité bien supérieure.
Taux de réussite : L'algorithme de déterminisation a réussi à convertir 91 % des regex avec références arrière de longueur unitaire (une catégorie très courante dans les applications réelles) en DRSA.
Comparaison : Alors que les autres moteurs subissent des ralentissements catastrophiques (backtracking) sur les entrées malveillantes, rsamatch maintient une performance linéaire/quadratique stable.

5. Signification et Impact

Sécurité : Cette recherche offre une solution pratique pour mitiger les attaques ReDoS sur les expressions régulières avec références arrière, un vecteur d'attaque critique souvent ignoré par les moteurs performants (qui désactivent simplement les références arrière).
Théorie des Automates : Elle comble un vide théorique en fournissant un modèle d'automate déterministe capable de gérer une sous-classe importante de langages non réguliers (dus aux références arrière) avec des garanties de complexité temporelle.
Praticité : Bien que la déterminisation ne soit pas complète pour tous les regex (elle peut échouer sur des cas très complexes), elle couvre une portion significative des cas d'usage réels (groupes de capture unitaires), offrant une alternative viable aux solutions de backtracking lentes.

En résumé, ce travail propose un changement de paradigme : au lieu de se fier au backtracking pour les regex complexes, il utilise la puissance des ensembles de registres pour transformer le problème en un processus déterministe efficace et sécurisé.