💻 computer science

PUFFERDOS: Efficient and Effective Attack String Generation for Regular Expression Denial of Service Vulnerabilities

Cet article présente PUFFERDOS, un nouvel outil qui génère des chaînes d'attaque ReDoS pratiques et efficaces en synthétisant des entrées basées sur trois modèles vulnérables formellement vérifiés et en les affinant par exécution concolique compositionnelle afin de garantir l'exploitabilité en conditions réelles dans des budgets de longueur réalistes.

Auteurs originaux : Shangzhi Xu, Ziqi Ding, Xiao Cheng, Yuekang Li, Nan Sun, Benjamin Turnbull, Shuangxiang Kan, Siqi Ma

Publié 2026-06-19

📖 5 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Shangzhi Xu, Ziqi Ding, Xiao Cheng, Yuekang Li, Nan Sun, Benjamin Turnbull, Shuangxiang Kan, Siqi Ma

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

Imaginez que vous avez un garde de sécurité très intelligent, mais légèrement obsessionnel, à la porte d'un bâtiment. Son travail est de vérifier si votre carte d'identité (l'entrée) correspond à un motif spécifique (l'expression régulière, ou « regex »). Habituellement, c'est rapide et facile.

Mais, il y a un piège. Si vous donnez au garde une carte d'identité très spécifique et déroutante, son cerveau se bloque dans une boucle. Il commence à vérifier chaque façon possible dont votre identité pourrait correspondre au motif, encore et encore, jusqu'à ce qu'il épuise son énergie et s'évanouisse. C'est ce qu'on appelle une attaque ReDoS (Déni de Service par Expression Régulière). C'est comme piéger une calculatrice pour qu'elle fasse des mathématiques indéfiniment afin qu'elle se fige.

Pendant longtemps, les chercheurs en sécurité ont essayé de trouver ces pièges et de créer des « cartes d'identité de test » pour prouver que le garde est défaillant. Cependant, les anciennes méthodes avaient deux gros problèmes :

Les identités étaient trop longues : Elles nécessitaient des entrées si énormes (comme un livre entier de texte) qu'aucun véritable site web ne les accepterait jamais.
Elles ne correspondaient pas au bâtiment : Elles testaient le garde de manière isolée, ignorant le fait que dans un vrai bâtiment, il peut y avoir d'autres gardes (filtres) qui pourraient arrêter votre identité avant même qu'elle n'atteigne la porte principale.

Entrez dans PUFFERDOS. Voyez PUFFERDOS comme un maître serrurier qui ne se contente pas de crocheter la serrure ; il comprend exactement comment traverser tout le bâtiment pour atteindre la serrure, en utilisant la clé la plus courte et la plus efficace possible.

Voici comment fonctionne PUFFERDOS, décomposé en étapes simples :

1. La stratégie du « Point d'Arrêt » (Faire travailler le garde plus dur)

Les chercheurs ont réalisé que pour faire figer le garde, vous n'avez pas seulement besoin de n'importe quel motif déroutant ; vous avez besoin d'un motif où le garde doit faire des étapes minuscules et inefficaces.

L'analogie : Imaginez le garde marchant dans un couloir. Si vous le forcez à s'arrêter à chaque pouce pour vérifier le sol, il se fatigue vite. S'il ne s'arrête que tous les 3 mètres, il se fatigue plus lentement.
La solution : PUFFERDOS crée des « clés » (chaînes d'attaque) qui forcent le garde à s'arrêter à chaque petit pouce. Il y parvient en choisissant soigneusement des caractères spécifiques et en les arrangeant de manière à ce que le garde doive revenir en arrière (faire un « backtrack » pour revérifier) autant de fois que possible. Cela rend l'attaque des milliers de fois plus rapide que les méthodes précédentes car elle atteint le même effet de « gel » avec une clé beaucoup plus courte.

2. Les trois motifs « Piège »

L'équipe a découvert que la plupart des serrures cassées tombent dans trois formes spécifiques. PUFFEDOS possède une recette spéciale pour chacune :

Le Piège à une Boucle : Un motif unique qui peut être lu de plusieurs manières déroutantes. PUFFEDOS choisit le caractère le plus court et le plus déroutant pour le répéter.
Le Piège à deux Boucles : Deux motifs côte à côte qui peuvent tous deux lire le même caractère. PUFFEDOS utilise un caractère que les deux motifs peuvent lire, forçant ainsi les deux motifs à se disputer pour savoir qui traite ce caractère.
Le Piège à boucles multiples : Une longue chaîne de motifs. PUFFEDOS construit une clé qui force le garde à vérifier chaque maillon de la chaîne individuellement.

3. Le parcours dans le « Monde Réel » (Exécution concolique)

C'est la partie la plus importante. Les anciens outils testaient simplement la serrure dans le vide. PUFFEDOS simule l'intégralité du bâtiment.

L'analogie : Imaginez que vous avez une clé qui ouvre une porte, mais que la porte se trouve derrière un point de contrôle de sécurité, une réceptionniste et un labyrinthe. Les anciens outils montraient simplement que votre clé fonctionne sur la porte. PUFFEDOS vous fait traverser le labyrinthe, vérifie si la réceptionniste vous laisse passer, et s'assure que vous atteignez réellement la porte.
La méthode : Il utilise une technique appelée « exécution concolique compositionnelle ». Voyez cela comme un résumé de carte. Au lieu de parcourir chaque étape du bâtiment à chaque fois, PUFFEDOS crée une « fiche de triche » pour chaque pièce (fonction) du bâtiment. Il demande : « Si je donne cette clé déroutante à cette pièce, la transmet-elle à la pièce suivante, ou la rejette-t-elle ? »
En utilisant ces fiches de triche, PUFFEDOS peut rapidement déterminer si une clé courte et efficace atteindra réellement la serrure vulnérable dans un programme réel, ou si elle sera bloquée par un filtre plus tôt dans le processus.

Les Résultats

L'équipe a testé PUFFEDOS sur des milliers de programmes réels et de failles de sécurité connues (CVE).

Vitesse : Il a généré des chaînes d'attaque qui étaient 97 à 3 800 fois plus efficaces que le meilleur outil précédent. Il pouvait figer un système avec une toute petite chaîne au lieu d'une immense.
Taux de réussite : Il a recréé avec succès 96,8 % des failles de sécurité connues (comparé à 77,4 % pour l'ancien outil).
Nouvelles découvertes : Lorsqu'ils ont testé PUFFEDOS sur 12 projets de logiciels populaires et réels, ils ont trouvé 59 nouvelles failles de sécurité, auparavant inconnues, que les anciens outils avaient manquées parce que les anciens outils ne pouvaient pas générer une attaque réaliste et assez courte pour prouver l'existence de la vulnérabilité.

En bref : PUFFEDOS est une façon plus intelligente et plus pratique de trouver et de prouver qu'un système informatique peut être figé par un motif déroutant. Il ne se contente pas de trouver la serrure ; il trouve la clé la plus courte et la plus réaliste pour la bloquer, prouvant ainsi que le danger est réel et doit être corrigé.

Résumé Technique : PUFFERDOS

Énoncé du Problème

Les attaques par déni de service par expressions régulières (ReDoS) exploitent le comportement de pire cas de complexité algorithmique des moteurs d'expressions régulières à retour en arrière (backtracking), forçant l'exploration d'un nombre superlinéaire ou exponentiel de chemins de correspondance. Cela consomme des ressources CPU excessives, entraînant une dégradation du service ou une indisponibilité. Bien que de nombreux outils de détection existent pour identifier les expressions régulières vulnérables et générer des chaînes de preuve de concept, les approches actuelles souffrent de deux limitations critiques qui entravent l'exploitation pratique :

Longueurs d'entrée irréalistes : Les outils existants génèrent souvent des chaînes d'attaque excessivement longues (par exemple, nécessitant des centaines de milliers de caractères) pour déclencher un ralentissement significatif. Dans les déploiements réels, les contraintes d'entrée (telles que les limites des en-têtes HTTP) tronquent souvent ces chaînes avant qu'elles ne puissent atteindre l'expression régulière vulnérable, rendant l'attaque inefficace.
Absence de validation au niveau du programme : De nombreuses chaînes générées sont validées uniquement par rapport à l'expression régulière de manière isolée. Elles ne tiennent pas compte des contraintes de flux de données, de la logique de filtrage ou de la troncature d'entrée au sein du programme hôte. Par conséquent, ces chaînes ne peuvent souvent pas atteindre l'expression régulière vulnérable dans un contexte d'exécution réel, ce qui conduit les développeurs à rejeter les vulnérabilités signalées comme étant de faible sévérité ou inexploitables.

Méthodologie

Les auteurs proposent PUFFERDOS, un cadre hybride conçu pour synthétiser des chaînes d'attaque qui soient à la fois efficaces (maximisant le coût de correspondance dans des budgets de longueur réalistes) et effectives (validées pour atteindre l'expression régulière vulnérable dans le programme réel). La méthodologie se compose de trois composantes principales :

1. Analyse Formelle et Taxonomie des Motifs

Les auteurs formalisent d'abord la relation entre la structure de la chaîne d'attaque et le coût de correspondance. À travers des preuves formelles (Lemmes 3.2–3.4 et Théorème 3.5), ils établissent que le coût de correspondance augmente lorsque :

Les unités de répétition sont aussi courtes que possible.
Les unités de répétition sont sélectionnées dans l'intersection des alphabets des expressions de boucle (LE - Loop Expressions) adjacentes, permettant à plusieurs LE de consommer la même sous-chaîne.
Les points d'arrêt (indices où les LE se terminent) sont séparés plutôt qu'entrelacés, forçant le moteur à retraiter de plus longs segments d'entrée lors du retour en arrière.

Sur cette base, ils définissent trois motifs vulnérables pour guider la génération de chaînes :

Une Boucle Exponentielle (EOL - Exponential One-Loop) : Une seule LE avec des sous-expressions de déploiement ayant des alphabets superposés.
Intersection de Boucles (LIL - Loop-Intersect-Loop) : Deux LE adjacentes séparées par un segment non-boucle qui peut être correspondu par les deux LE.
Multi-Boucles Polynomiales (PML - Polynomial Multi-Loop) : Des LE adjacentes avec des alphabets disjoints ou des séparateurs qui ne peuvent pas être consommés par les deux.

2. Génération de Chaînes d'Attaque Pilotée par la Structure

PUFFERDOS analyse les expressions régulières vulnérables en un arbre de syntaxe abstraite (rAST) pour identifier le motif vulnérable spécifique (EOL, LIL ou PML). Il synthétise ensuite des chaînes d'attaque candidates ( $s_a = x \cdot y^q \cdot z$ ) en utilisant des règles spécifiques aux motifs :

Génération de l'Infixe : Sélectionne l'unité de répétition la plus courte ( $y$ ) dans l'intersection de l'alphabet des LE concernées. Pour les motifs avec plusieurs LE, il concatène des unités répétées indépendamment pour garantir que les points d'arrêt soient séparés, maximisant ainsi les étapes de retour en arrière.
Construction du Préfixe/Suffixe : Dérive le préfixe ( $x$ ) de la partie non-boucle de l'expression régulière et le suffixe ( $z$ ) de la partie non-boucle de la fin, garantissant que la chaîne finale est rejetée par l'expression régulière pour déclencher un retour en arrière exhaustif.

3. Raffinement Concolique Compositionnel Spécifique au ReDoS

Pour s'assurer que la chaîne générée atteint l'expression régulière vulnérable dans un programme réel, PUFFERDOS emploie une stratégie d'exécution concolique compositionnelle :

Extraction de Chemin : Construit un graphe d'appel pour identifier les chemins réalisables depuis les points d'entrée du programme jusqu'à l'expression régulière vulnérable.
Sommatisation de Fonction : Effectue des tests unitaires concoliques sur les fonctions le long du chemin pour générer des sommatisations de fonctions spécifiques au ReDoS. Contrairement aux sommatisations traditionnelles, celles-ci sont élaguées pour ne conserver que les comportements pertinents pour la propagation de la chaîne d'attaque (par exemple, les transformations d'identité ou les retours constants), écartant le raisonnement regex non lié qui cause l'explosion de chemin.
Raffinement au Niveau Système : Utilise les sommatisations pour guider l'exécution concolique au niveau système, résolvant les contraintes interprocédurales pour affiner la chaîne d'attaque afin qu'elle contourne les filtres et atteigne l'expression régulière cible sans dépasser les budgets de longueur d'entrée réalistes.

Principales Contributions

Preuve Formelle d'Efficacité : Le papier prouve formellement que la sélection de caractères spécifiques et leur ordonnancement pour séparer les points d'arrêt dans des LE adjacentes amplifie considérablement le coût de correspondance des expressions régulières. Cela mène à la dérivation de trois motifs d'expressions régulières vulnérables et de règles de génération prouvables et efficaces.
Cadre PUFFERDOS : Le développement d'un générateur hybride qui intègre des règles de génération formelles avec un raffinement concolique compositionnel spécifique au ReDoS. Cette approche comble le fossé entre la détection théorique et l'exploitation pratique en garantissant que les chaînes sont suffisamment courtes pour les contraintes du monde réel et valides au sein du flux de données du programme.
Évaluation Complète : L'outil est évalué sur un corpus de grande échelle de 17 962 expressions régulières vulnérables, 31 CVE connues et 12 projets open-source populaires.

Résultats

L'évaluation démontre des améliorations significatives par rapport à l'outil de pointe, RENGAR :

Efficacité : PUFFERDOS génère des chaînes d'attaque 97,2× à 3 872,4× plus courtes que celles produites par RENGAR tout en atteignant les mêmes seuils de temps de correspondance (0,1s, 1s et 10s).
Reproduction de CVE : PUFFEDOS a réussi à reproduire 96,8 % des CVE ReDoS exploitées, contre 77,4 % pour RENGAR.
Nouvelles Vulnérabilités : Appliqué à 12 projets open-source populaires, PUFFERDOS a découvert 59 instances de ReDoS exploitables (25 de plus que RENGAR). Des développeurs de six de ces projets ont validé 21 de ces découvertes.
Impact Réel : Dans un exemple motivant impliquant une bibliothèque de coloration syntaxique, PUFFERDOS a généré une chaîne de 1 000 caractères qui a provoqué un blocage du système dépassant 4 000 secondes, alors que les méthodes traditionnelles nécessitaient 500 000 caractères et échouaient à déclencher un blocage en raison de la troncature d'entrée dans le programme réel.

Signification

Le papier soutient que l'utilité pratique de la détection ReDoS est actuellement limitée car les chaînes d'attaque générées sont souvent trop longues ou ne parviennent pas à se propager à travers la logique du programme. En abordant ces lacunes spécifiques, PUFFERDOS fournit un mécanisme pour générer des preuves de vulnérabilité pratiquement exploitables. Cela est significatif car cela répond directement à la raison pour laquelle les développeurs ignorent souvent les rapports ReDoS (les percevant comme de faible sévérité ou inexploitables). En fournissant des chaînes d'attaque courtes et valides, PUFFERDOS permet une évaluation plus précise des risques et facilite la remédiation des vulnérabilités ReDoS dans les systèmes logiciels réels.