💬 NLP

On the Complexity of the Matching Problem of Regular Expressions with Backreferences

Cet article établit la complexité computationnelle fine de la correspondance d'expressions régulières avec des références arrières en prouvant des bornes inférieures conditionnelles sous les hypothèses SETH et de détection de triangles, tout en présentant un algorithme amélioré en $O(n \log^2 n)$ pour les références arrières à usage unique.

Auteurs originaux : Soh Kumabe, Yuya Uezato

Publié 2026-05-11

📖 7 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Soh Kumabe, Yuya Uezato

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

La vue d'ensemble : L'embouteillage « Regex »

Imaginez que vous êtes un agent de sécurité dans une boîte de nuit (le système informatique). Vous avez une liste de règles (une Expression Régulière) pour savoir qui peut entrer.

Règles simples : « Seules les personnes portant un t-shirt rouge. » C'est facile à vérifier. Vous regardez un t-shirt, dites « Rouge ? Oui, entrez. » Cela prend le même temps que la file soit de 10 personnes ou de 10 000.
Le problème (ReDoS) : Parfois, des pirates créent une file de personnes spécifique qui trompe l'agent pour qu'il effectue une quantité massive de travail inutile. Au lieu de vérifier une personne et de passer à la suivante, l'agent commence par vérifier la personne A, puis la personne B, puis la personne A à nouveau, puis la personne C, puis la personne A encore... jusqu'à ce que l'agent s'effondre d'épuisement. Cela s'appelle une attaque par Déni de Service (ReDoS).

Dans le monde réel, cela a fait planter d'énormes sites web comme Stack Overflow et Cloudflare. Le papier note qu'une lenteur même « quadratique » (où vérifier 100 personnes prend 10 000 étapes) suffit à faire planter un système.

Le méchant : Les « Références arrières »

Les règles standard sont simples. Mais les moteurs « Regex » modernes possèdent une fonctionnalité surpuissante appelée Références arrières.

L'analogie :
Imaginez une règle qui dit : « Trouvez un mot, souvenez-vous-en, puis assurez-vous que le même mot exact apparaît plus tard. »

Exemple : « Trouvez un mot, appelez-le 'X'. Ensuite, trouvez 'X' à nouveau. »
Si l'entrée est pomme ... pomme, cela fonctionne.
Si l'entrée est pomme ... banane, cela échoue.

Cette fonctionnalité est incroyablement utile pour les programmeurs, mais elle rend le travail de l'« agent » beaucoup plus difficile. L'agent doit se souvenir de ce qu'il a vu plus tôt et le comparer constamment à ce qu'il voit maintenant. Le papier demande : Pouvons-nous construire un agent assez rapide pour gérer ces règles complexes sans s'épuiser ?

Les découvertes du papier : Le Bon, Le Mauvais et Le Moche

Les auteurs ont examiné exactement à quel point il est difficile de résoudre ces problèmes de correspondance. Ils les ont décomposés en deux aspects : la Difficulté (Pourquoi c'est difficile) et les Algorithmes (Comment le résoudre).

1. La mauvaise nouvelle : Certaines règles sont impossibles à accélérer

Le papier prouve que pour certains types de règles complexes, il n'existe pas de « solution miracle » pour les rendre rapides.

Le problème du « Triangle » : Ils ont montré que si vous avez une règle utilisant deux variables (comme se souvenir de deux mots différents et les vérifier plus tard), le résoudre est aussi difficile que de trouver un triangle dans un immense graphe de réseau social. Si vous pouviez résoudre la règle rapidement, vous pourriez résoudre le problème du graphe rapidement. Puisque les experts en graphes pensent que le problème du graphe est intrinsèquement lent, le problème de la règle doit l'être aussi.
Le problème des « Vecteurs orthogonaux » : Pour les règles avec encore plus de variables, ils ont prouvé que le temps requis croît de manière exponentielle avec le nombre de variables. C'est comme essayer de trouver une combinaison spécifique de clés dans une serrure ; plus vous avez de clés, plus il devient impossible de la forcer rapidement par force brute.

À retenir : Si votre règle est trop complexe (utilisant de nombreuses fonctionnalités « souvenez-vous de ceci »), vous ne pouvez pas construire un moteur rapide pour elle. Vous rencontrerez toujours un mur.

2. La bonne nouvelle : Une solution « quasi-linéaire » pour les cas simples

Cependant, le papier a trouvé un point idéal. Ils se sont concentrés sur un type de règle spécifique et courant :

Le motif « ABCBD » : « Trouvez un mot (A), puis un mot (B), puis un mot (C), puis le même mot B exact, puis un mot (D). »
- Exemple réel : « Trouvez un nom d'utilisateur, puis un mot de passe, puis un message, puis le même nom d'utilisateur à nouveau, puis une signature. »

Les auteurs ont découvert que bien que cela semble délicat, cela peut être résolu très efficacement.

L'ancienne méthode : Les méthodes précédentes consistaient à vérifier chaque combinaison possible dans une bibliothèque, ce qui prenait un temps $O(n^2)$ (quadratique). Si le livre faisait 1 000 pages, cela prenait 1 000 000 d'étapes.
La nouvelle méthode : Les auteurs ont construit un nouvel algorithme qui prend environ $O(n \log^2 n)$ $O (n lo g^{2} n)$ temps.
- L'analogie : Imaginez que la bibliothèque est organisée avec un système d'index magique (utilisant des Arbres de suffixes et des Forêts de factorisation). Au lieu de lire chaque page, l'agent peut sauter directement aux sections pertinentes. Si le livre fait 1 000 pages, la nouvelle méthode prend environ 10 000 étapes (ou même moins), ce qui est une amélioration massive.

Comment fonctionne le nouvel algorithme (Les « tours de magie »)

Pour atteindre cette vitesse, les auteurs ont utilisé plusieurs techniques astucieuses, qu'ils décrivent dans le papier :

L'Arbre de suffixes (La Carte) : Ils ont construit une immense carte de la chaîne d'entrée. Cette carte montre chaque fin possible de la chaîne. Elle aide l'agent à voir instantanément : « Oh, ce mot 'B' apparaît ici, et il apparaît aussi là. »
La Décomposition lourde-légère (Le Chapeau Trieur) : Ils ont divisé la carte en chemins « lourds » (chemins très communs) et « légers » (chemins rares). Ils ne font le gros du travail que sur les chemins rares, ce qui économise du temps.
La Périodicité (Le Rythme) : Ils ont remarqué que lorsqu'un mot se répète (comme « B...B »), la chaîne a souvent un rythme ou un motif. Ils ont utilisé les mathématiques pour prédire ces motifs au lieu de vérifier chaque lettre individuellement.
Les Forêts de factorisation (L'Index) : Il s'agit d'une structure de données qui agit comme un index ultra-rapide, permettant à l'agent de vérifier si un morceau de texte correspond à une règle en temps constant, quelle que soit la longueur du texte.

Résumé de la conclusion

Peut-on arrêter toutes les attaques ReDoS ? Non. Si une règle est trop complexe (trop de variables « souvenez-vous de ceci »), il est prouvé mathématiquement qu'elle est lente.
Peut-on résoudre les règles complexes les plus courantes ? Oui ! Pour le cas spécifique où une règle se souvient d'un mot et le vérifie une fois plus tard (le motif « ABCBD »), les auteurs ont créé un nouveau moteur presque aussi rapide que les règles simples.
Pourquoi cela importe-t-il ? Cela dit aux ingénieurs logiciels : « N'utilisez pas trop de références arrières, sinon vous serez lents. Mais si vous les utilisez de cette manière spécifique et courante, vous pouvez maintenant utiliser notre nouvelle méthode pour garder votre système sûr et rapide. »

Le papier trace essentiellement une ligne dans le sable : Voici où la limite de vitesse est inviolable, et voici où nous avons trouvé un moyen de rouler plus vite.

Résumé technique : Sur la complexité du problème de correspondance des expressions régulières avec références arrière

1. Définition du problème et motivation

L'article examine la complexité computationnelle fine du problème de correspondance d'expressions régulières avec références arrière (REWB). Alors que les expressions régulières classiques (Regex) peuvent être mises en correspondance en temps linéaire par rapport à la longueur de la chaîne d'entrée $|w|$ en utilisant la construction de Thompson, les moteurs pratiques prennent en charge les références arrière (par exemple, (E)x pour capturer une sous-chaîne et \x pour la réutiliser). Cette fonctionnalité étend strictement le pouvoir expressif des Regex (permettant la reconnaissance de langages non réguliers comme $\{ww \mid w \in \Sigma^*\}$ ) mais introduit des risques algorithmiques significatifs.

La motivation découle des attaques par déni de service par expression régulière (ReDoS), où des adversaires conçoivent des entrées pour déclencher un comportement de pire cas dans les moteurs de correspondance. Des incidents notables chez Stack Overflow (2016) et Cloudflare (2019) ont démontré que même un comportement de temps quadratique ( $O(|w|^2)$ ) dans les moteurs basés sur le retour en arrière peut provoquer des pannes de service catastrophiques. Les auteurs posent la question fondamentale : Est-il possible de construire des moteurs sûrs face aux ReDoS pour les REWB qui s'exécutent en temps linéaire ou quasi-linéaire ?

L'article se concentre sur les $r$ -use $k$ -REWB, définis comme des expressions avec $k$ variables distinctes où le nombre total d'exécutions de références arrière dans n'importe quel calcul est borné par $r$ .

2. Méthodologie et approche technique

L'article adopte une double approche : établir des bornes inférieures conditionnelles (difficulté) et concevoir des algorithmes efficaces pour des sous-classes spécifiques.

2.1 Résultats de difficulté

Les auteurs renforcent les résultats antérieurs sur la complexité en réduisant des problèmes difficiles bien connus à la correspondance REWB :

Difficulté W[2] : En réduisant le problème de l'ensemble dominant $k$ -dominant, ils prouvent que la correspondance REWB est W[2]-difficile lorsqu'elle est paramétrée par la taille de l'expression $|E|$ . Cela renforce le résultat connu de difficulté W[1].
Bornes inférieures conditionnelles (Détection de triangles) : En supposant l'hypothèse « Pas de temps quasi-linéaire » pour la détection de triangles, ils montrent que même le problème très restreint 2-use 2-REWB ne peut pas être résolu en temps $O(|w|^{1+\delta})$ pour tout $\delta > 0$ .
Bornes inférieures conditionnelles (k-OV) : Sous l'hypothèse des vecteurs orthogonaux $k$ (k-OV) (plus faible que SETH), ils prouvent que la correspondance $k$ -REWB ne peut pas être résolue en temps $O(|w|^{2k-\epsilon})$ . Cela implique que pour un $k$ général, un temps quasi-linéaire est peu probable.

2.2 Résultats algorithmiques

La contribution algorithmique principale se concentre sur les 1-use REWB (expressions avec une variable référencée exactement une fois).

Transformation en forme canonique : Les auteurs prouvent que tout 1-use REWB peut être transformé en une forme canonique impliquant une somme de termes tels que $A (B)_x C \backslash x D$ , où $A, B, C, D$ sont des Regex classiques. Ceci est appelé le problème ABCBD.
Stratégie de décomposition : Le problème ABCBD est décomposé en deux sous-problèmes :
1. Problème XYYZ : Le cas où les deux occurrences de $B$ sont adjacentes ( $w = w_A w_B w_B w_D$ ). Ceci est résolu en utilisant l'énumération de la puissance locale maximale de Crochemore et les propriétés des ensembles ultimement périodiques dérivés des monoïdes de transition.
2. Problème ABCBD à embranchements : Le cas où les deux occurrences de $B$ sont séparées par un $C$ non vide, et où les caractères suivant immédiatement les deux occurrences de $B$ diffèrent.
Arbre des suffixes et décomposition lourde-légère : Pour le cas à embranchements, l'algorithme utilise l'arbre des suffixes de la chaîne d'entrée $w$ . Il emploie une décomposition lourde-légère pour partitionner l'espace de recherche.
Structures de données :
- Forêts de factorisation : Utilisées pour évaluer l'appartenance aux Regex sur des sous-chaînes en temps constant après un prétraitement linéaire.
- Monoïdes de transition : Exploités pour suivre l'état des Regex $A, B, C, D$ efficacement.
- Énumérateurs personnalisés : Les auteurs conçoivent des structures de données spécialisées (RightEnumerator, LeftEnumerator, AuxiliaryEnumerator) pour gérer l'énumération des transitions. Ces structures utilisent des mises à jour paresseuses et des stratégies d'union-ensemble disjoint (DSU) pour gérer les contraintes qui varient avec la longueur de la sous-chaîne $w_B$ .

3. Résultats clés

Difficulté

Théorème 3 : La correspondance REWB est W[2]-difficile paramétrée par la taille de l'expression.
Théorème 4 : En supposant l'hypothèse de détection de triangles, la correspondance 2-use 2-REWB nécessite un temps super-linéaire (spécifiquement, pas $O(|w|^{1+\delta})$ ).
Théorème 5 : Sous l'hypothèse $k$ -OV, la correspondance $k$ -REWB nécessite un temps $\Omega(|w|^{2k-\epsilon})$ .

Algorithmes

Théorème 7 (Résultat principal) : Le problème ABCBD admet un algorithme de temps $O(|w| \log^2 |w|)$ . La constante cachée dépend exponentiellement des tailles des Regex $A, B, C, D$ ( $2^{O((|A|+|B|+|C|+|D|)^2)}$ ).
Théorème 8 : Par conséquent, le problème de correspondance 1-use REWB admet un algorithme de temps $O(|w| \log^2 |w|)$ .
Théorème 9 : Le problème XY $\alpha$ Z (généralisant XYYZ à $\alpha$ répétitions) admet un algorithme de temps $O(|w| \log |w|)$ .

Ces résultats représentent une amélioration significative par rapport au meilleur algorithme connu précédemment de $O(|w|^2)$ pour le problème ABCBD par Nogami et Terauchi (MFCS 2025).

4. Importance et revendications

L'article revendique fournir une compréhension fondamentale du paysage de complexité pour la correspondance REWB :

Sécurité ReDoS : Il établit que si la correspondance REWB générale est probablement intraitable pour un temps quasi-linéaire, une sous-classe pratiquement pertinente (1-use REWB) peut être mise en correspondance en temps quasi-linéaire. Cela suggère que les moteurs prenant en charge les références arrière à usage unique pourraient théoriquement être rendus sûrs face aux ReDoS.
Complexité fine : Le travail délimite la frontière entre les cas traitables et intraitables. Il montre que l'augmentation du nombre d'utilisations de références arrière de 1 à 2 (même avec seulement 2 variables) pousse probablement le problème hors du régime quasi-linéaire.
Innovation algorithmique : L'article introduit un cadre algorithmique complexe mais hautement non trivial combinant des arbres de suffixes, des forêts de factorisation et des monoïdes de transition pour résoudre un problème précédemment considéré comme nécessitant un temps quadratique.

Les auteurs déclarent explicitement que leur algorithme est uniforme, ce qui signifie qu'il traite l'expression et la chaîne d'entrée ensemble sans conseils non uniformes dépendant de l'expression fixe. Ils reconnaissent que la dépendance exponentielle par rapport à la taille de l'expression $|E|$ reste une limitation pour les très grandes expressions, et ils laissent ouverte la question de savoir si un algorithme de temps strictement linéaire ( $O(|w|)$ ) existe ou si les facteurs logarithmiques peuvent être supprimés.

5. Limites et problèmes ouverts

L'article identifie plusieurs directions ouvertes :

Complexité des $r$ -use 1-REWB : La complexité pour les $r$ -use 1-REWB où $r \ge 2$ reste ouverte.
Temps linéaire : Si la borne $O(|w| \log^2 |w|)$ peut être améliorée en $O(|w|)$ .
Dépendance à l'expression : Réduire la dépendance exponentielle à $|E|$ à une dépendance polynomiale tout en maintenant une dépendance quasi-linéaire à $|w|$ .
Fonctionnalités plus larges : Étendre ces résultats à d'autres fonctionnalités pratiques des regex comme les regards (lookarounds), le groupage atomique, et les étoiles paresseuses/gourmandes.