Protéger l'entrée utilisateur d'expressions régulières contre les attaques

Je suis au courant du déni de service par expression régulière (ReDoS). Existe-t-il un moyen raisonnable de permettre aux utilisateurs de créer des expressions régulières personnalisées tout en garantissant qu'ils ne soumettent pas un modèle exponentiellement lent?

Le problème avec les expressions régulières n'est pas le regex lui-même, mais le moteur de regex qui a toutes sortes de fonctionnalités «pratiques» comme le retour en arrière. Par conséquent, l'utilisation d'un moteur d'expression régulière sans ces fonctionnalités évite.

Les expressions régulières du concept informatique peuvent toujours être mises en correspondance en temps linéaire après avoir été compilées sur une machine à états finis. Un moteur regex basé sur une machine à états ne peut donc pas être utilisé pour ReDoS. Cependant, les machines d'état nécessaires peuvent devenir assez grandes dans les exemples pathologiques. Mais limiter la mémoire disponible a tendance à être plus facile que de limiter le temps de calcul disponible.

Le moteur RE2 a été développé spécifiquement pour traiter les regex non fiables et a été conçu pour une exécution en temps linéaire.

Une autre alternative consiste à assembler vous-même les expressions régulières à partir d'une notation simplifiée. Par exemple, vous pouvez autoriser les utilisateurs à utiliser des modèles globaux (comme *.txt). Vous pouvez ensuite analyser cela d'une manière qui empêche le retour en arrière, par exemple en interdisant l'imbrication et en utilisant uniquement des quantificateurs gourmands. Pour de nombreux cas d'utilisation, une notation de modèle simplifiée est tout à fait suffisante.

Analyser une expression régulière pour voir si elle sera lente ou non, sans que l'analyse devienne elle - même lente , revient à résoudre le problème d'arrêt. En d'autres termes, il n'est pas possible de trouver une solution correcte et complète.

Vous pouvez, bien sûr, trouver une solution qui est correcte et en complète. Par exemple, vous pouvez travailler avec une liste blanche restrictive de fonctionnalités sûres à utiliser (par exemple, classes de caractères oui, répétition non ...). Cela vous permettrait de passer beaucoup de regex non critiques, de rejeter tous les critiques, et de rejeter (à tort) certains qui sont corrects, mais trop compliqués pour se révéler automatiquement sûrs.

En tant qu'auteur du parseur pour le projet Lazarus, je dirais qu'il n'y a aucun moyen de comprendre pour une expression régulière donnée quelles ressources elle va consommer sur un texte donné.

Sans dépenser les mêmes ressources, je veux dire (au moins dans le sens big-O).

Donc, la meilleure approche - exécutez re parser dans un thread séparé et tuez-le après le délai d'expiration.

En plus des autres réponses, une solution peut également être de rouler votre propre bibliothèque regex, qui permet une instrumentation des performances pendant l'exécution, et fournissant ainsi les moyens de tuer l'exécution à mi-parcours si certains critères sont remplis.

De même, vous pouvez exécuter les expressions rationnelles sur un autre thread et tuer les threads s'ils prennent trop de temps.