Comment éviter le Catastrophic Backtracking dans les Regex ?

Le backtracking catastrophique des expressions régulières fait référence au fait que l'expression régulière effectue trop de retours en arrière lors de la correspondance, provoquant une utilisation de 100 % du CPU et bloquant les services normaux.

Contexte

J'ai lu un article détaillant le processus de découverte et de résolution d'un problème de backtracking régulier entraînant une utilisation de 100 % du CPU. L'article original est assez long, et j'ai rencontré des problèmes similaires à deux reprises auparavant dans le développement d'OpenResty.

Voici un bref résumé pour que vous n'ayez pas à passer du temps sur le contexte.

1. Les moteurs d'expressions régulières pour la plupart des langages de développement sont implémentés en utilisant un NFA basé sur le backtracking (plutôt que sur le NFA de Thompson).
2. Un backtracking catastrophique avec 100 % de CPU si le backtracking est trop important.
3. Il est nécessaire d'analyser le dump avec gdb ou systemtap pour localiser l'environnement en ligne.
4. De tels problèmes sont difficiles à détecter avant que le code ne soit mis en production et nécessitent une revue au cas par cas des expressions régulières.

Du point de vue du développement, corriger les expressions régulières problématiques est la fin de l'histoire. Au maximum, ajouter un mécanisme de sécurité pour limiter le nombre de backtrackings, comme celui-ci dans OpenResty.

lua_regex_match_limit 100000;

De cette manière, même s'il y a un backtracking catastrophique, il sera limité et ne consommera pas tout le CPU.

Eh bien, cela semble déjà parfait ? Allons au-delà du niveau de développement et examinons cela sous un autre angle.

Attaquants

Il suffit d'utiliser une machine, d'envoyer une requête, et vous pouvez faire tomber le serveur de l'autre côté, c'est tout simplement l'arme nucléaire des hackers. Comparé à cela, un DDoS est faible, le mouvement est important et coûteux.

Cette attaque a également son propre nom : ReDoS (RegEx Denial of Service).

Puisque les expressions régulières sont si largement utilisées et existent dans presque toutes les parties des services back-end, il y a une opportunité d'en tirer profit en trouvant l'une des vulnérabilités.

Imaginez un scénario où un hacker découvre une vulnérabilité ReDoS dans le WAF et envoie une requête pour faire tomber le WAF ; vous êtes incapable de localiser le problème en peu de temps, sans même réaliser qu'il s'agit d'une attaque ; vous choisissez de redémarrer ou de désactiver temporairement le WAF pour maintenir votre activité en marche ; pendant que le WAF est hors service, le hacker utilise une injection SQL pour extraire votre base de données. Vous, de votre côté, êtes peut-être encore complètement dans l'ignorance.

En raison de l'utilisation généralisée des logiciels open source et des services cloud, il ne suffit pas de s'assurer que les expressions régulières que vous écrivez sont exemptes de vulnérabilités. C'est un autre sujet, nous commencerons ici en ne discutant que des expressions régulières que nous contrôlons.

Comment découvrir de telles expressions régulières ?

La première étape pour résoudre les problèmes est de les trouver, et d'essayer de tous les trouver, également connue sous le nom de capacité à les trouver en toute sécurité.

S'attendre à ce qu'une revue manuelle du code trouve des règles problématiques n'est pas fiable. La plupart des développeurs ne sont pas conscients des problèmes de sécurité, et même s'ils cherchaient, il est peu probable qu'ils puissent trouver le problème dans une expression régulière complexe.

C'est là que les outils d'automatisation entrent en jeu.

Nous avons les deux méthodes automatisées suivantes pour résoudre ce problème.

• Test statique

De tels outils peuvent scanner le code pour les expressions régulières et, selon un certain algorithme, trouver les expressions régulières avec un backtracking catastrophique.

Par exemple, RXXR2, qui est implémenté sur la base d'un algorithme dans un article qui convertit les expressions régulières en ε-NFA puis les recherche, mais ne supporte pas la syntaxe étendue des expressions régulières, donc il y aura des omissions.

• Fuzzing dynamique

Le test de fuzzing est une méthode générale de test logiciel qui détecte les plantages, les fuites de mémoire et autres problèmes en entrant de grandes quantités de données aléatoires sur de longues périodes.

De même, nous pouvons utiliser cette approche dans les tests d'expressions régulières. Nous pouvons générer des données de test basées sur des expressions régulières existantes, ou les générer complètement au hasard.

SlowFuzz est l'un des outils open source, également basé sur une implémentation d'algorithme d'un article, l'article sera listé à la fin de ce document, c'est un outil généraliste, et ne fait pas de traitement pour la structure de l'expression régulière, donc il y aura des omissions.

SDLFuzzer est un outil spécialisé de détection de ReDoS développé par Microsoft il y a quelques années, mais n'est plus maintenu.

Il n'y a pas beaucoup d'outils à choisir dans ce domaine, et il n'y a pas beaucoup d'attention. Cependant, j'ai été ravi de trouver un article sur ReDoS par plusieurs professeurs et doctorants de l'Université de Nanjing lors de ma recherche d'informations, et ils ont open sourcé l'outil ReScue avec l'article : https://2bdenny.github.io/ReScue/. Cet outil a identifié des vulnérabilités ReDoS dans plusieurs projets open source.

Voici les résultats des tests comparatifs dans l'article.

Peut-on le faire une fois pour toutes ?

Même si nous utilisons de tels outils, il y aura inévitablement des faux positifs et des omissions, alors existe-t-il une manière de résoudre ReDoS une fois pour toutes ?

Alors nous devons revenir à la racine du problème pour trouver la réponse : le moteur d'expressions régulières utilise le backtracking pour la correspondance.

Ne serait-ce pas OK si nous abandonnions cette approche ? Oui, il existe déjà plusieurs autres implémentations de moteurs d'expressions régulières qui peuvent résoudre le problème une fois pour toutes. Ils abandonnent tous le backtracking et utilisent l'approche de l'automate NFA/DFA, l'avantage est qu'elle est adaptée à la correspondance en flux et est également plus sûre, l'inconvénient est qu'elle ne supporte pas de nombreuses syntaxes étendues des expressions régulières, comme les références arrière, mais celles-ci ne sont généralement pas utilisées de toute façon.

• Google RE2

RE2 de Google est l'un des projets open source les plus complets. Il supporte la plupart des syntaxes de PCRE, et il existe des bibliothèques pour Go, Python, Perl, Node.js et d'autres langages de développement, le coût de démarrage et de remplacement est très faible.

Prenons Perl comme exemple et voyons si RE2 peut éviter les problèmes de backtracking catastrophique.

Regardons ce tableau comparatif des résultats.

Le code est le suivant, vous pouvez l'essayer vous-même si vous êtes intéressé.

time perl -e 'if ("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" =~ /a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa/) {print("hit");}'

40.80s user 0.00s system 99% cpu 40.800 total

Il faut 40,8 secondes pour exécuter cette expression régulière, pendant lesquelles le CPU est à 99 %.

Avec RE2, le contraste est très clair.

time perl -e 'use re::engine::RE2; if ("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" =~ /a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa/) {print(" hit");}'

perl -e 0.00s user 0.00s system 34% cpu 0.011 total

• Intel Hyperscan

Intel Hyperscan est également un moteur d'expressions régulières similaire à RE2, et il existe des bibliothèques pour Perl, Python et d'autres langages, donc il n'est pas trop difficile de commencer.

Seulement, conformément à la pratique d'Intel, il est plus lié à la plateforme, ne peut fonctionner que sur x86.

S'il y a un avantage unique, c'est peut-être la capacité à mieux fonctionner avec le jeu d'instructions et le matériel d'Intel, avec des améliorations de performances, comme en le combinant avec son propre DPDK.

Snort, un outil open source de détection d'intrusion réseau, utilise également Hyperscan pour remplacer le précédent moteur d'expressions régulières, donc les étudiants familiers avec Snort peuvent l'essayer.

Extensions

Voici quelques articles sur les expressions régulières, qui peuvent être lus comme une extension si vous êtes intéressé.

1. SlowFuzz: Automated Domain-Independent Detection of Algorithmic Complexity Vulnerabilities: https://arxiv.org/pdf/1708.08437.pdf

2. Static Analysis for Regular Expression Exponential Runtime via Substructural Logics: https://arxiv.org/abs/1405.7058.pdf

3. ReScue: Crafting Regular Expression DoS Attacks: https://dl.acm.org/doi/10.1145/3238147.3238159

4. Regular Expression Matching Can Be Simple And Fast: https://swtch.com/~rsc/regexp/regexp1.html