Pour chaque regex «mal», existe-t-il une alternative non-mal, ou le diable est-il dans la grammaire?

16

Apparemment, les attaques ReDos exploitent les caractéristiques de certaines expressions régulières (autrement utiles) ... provoquant essentiellement une explosion de chemins possibles à travers le graphique défini par le NFA.

Est-il possible d'éviter de tels problèmes en écrivant une expression rationnelle «non perverse» équivalente? Sinon (ainsi, la grammaire ne peut pas être gérée dans l'espace / temps pratique par un NFA), quelles approches d'analyse seraient mieux? Pourquoi?

David Bullock
la source
Si j'ai réussi à utiliser un langage technique précis, c'est un accident. Veuillez abréger vos réponses pour un non-universitaire :-)
David Bullock
1
En fait, j'essaie simplement de trouver un moyen pratique d'éviter d'être re - déposé , et cette question s'est posée.
David Bullock
Pour reformuler votre question (?): Est-ce que chaque langue régulière a une expression régulière dont la longueur est limitée par un polynôme dans le nombre d'états de son NFA minimal?
A.Schulz
1
@ A.Schulz. Je ne pense pas que ce soit la question. Ce n'est pas ainsi que fonctionnent les attaques ReDos. Dans une attaque ReDos, l'expression rationnelle est codée en dur dans le code source du programme et est fournie par le développeur, qui est présumé fiable. Ensuite, l'adversaire doit fournir une chaîne d'entrée, que le programme compare à l'expression rationnelle. Si l'adversaire peut trouver une chaîne d'entrée qui fait fonctionner le matcher pendant très longtemps, l'adversaire gagne. Nous sommes donc préoccupés par les données contradictoires et non par les expressions régulières accusatoires. (suite)
DW
Par conséquent, je pense que la question est à la place: chaque langage régulier a-t-il une expression régulière telle que faire correspondre une chaîne de caractères à cette expression régulière prend du temps O ( f ( n ) ) , où f ( n ) est un pas trop - fonction à croissance rapide de n (disons, polynôme, ou quelque chose comme ça)? [Par ailleurs, cette reformulation montre clairement que la réponse dépendra de l'algorithme utilisé pour l'appariement ... comme je le mentionne dans ma réponse.] La taille de l'expression régulière en fonction de la taille du NFA minimal ne dépend pas compte vraiment ici. nO(F(n))F(n)n
DW

Réponses:

14

Cela dépend si vous avez une expression régulière ou une expression rationnelle: les expressions régulières sont mauvaises, mais les expressions régulières sont une chose de beauté et ne vous transformeront jamais en mal.

Par expression régulière, je veux dire une expression régulière moderne: c'est-à-dire une expression régulière avec des fonctionnalités modernes supplémentaires telles que les références arrières - par exemple, une expression régulière compatible Perl. Ceci est plus puissant qu'une expression régulière classique d'un manuel de théorie formelle des langages / automates, car les expressions régulières classiques ne permettent pas les références arrières, l'anticipation, la recherche, etc.

Pour une expression régulière classique, si vous avez une bonne implémentation pour le matcher, alors aucune expression régulière n'est trop mauvaise. En particulier, un algorithme standard de correspondance consiste à convertir l'expression régulière en NFA, puis à exécuter le NFA sur une chaîne d'entrée. Pour cet algorithme, le temps d'exécution le plus défavorable pour tester une chaîne de caractères est O ( n ) , lorsque l'expression régulière est fixe. Cela signifie que le temps de fonctionnement ne peut pas exploser trop rapidement. Aucune chaîne ne provoquera une augmentation exponentielle du temps d'exécution. Ainsi, si vous utilisez un matcher qui utilise cet algorithme, aucune expression régulière classique ne sera mauvaise.nO(n)

Cela dépend de l'implémentation de la correspondance d'expression régulière. Si vous avez une implémentation naïve ou médiocre de la correspondance, la correspondance peut prendre un temps exponentiel; il existe certainement des algorithmes avec cette propriété. Mais la meilleure réponse à cela n'est probablement pas de changer l'expression régulière; il est probablement préférable de choisir un meilleur match, si vous êtes préoccupé par les attaques par déni de service.

En comparaison, certains regexps modernes sont inévitablement mauvais. Si vous avez une expression rationnelle moderne, la correspondance peut nécessiter un temps exponentiel. En particulier, les expressions rationnelles avec des références arrières peuvent reconnaître les langages NP-hard. Par conséquent, sous des hypothèses plausibles, il existe une classe de regexps maléfiques où le test d'une correspondance prend un temps exponentiel. Ainsi, certaines expressions rationnelles modernes sont inévitablement mauvaises: il n'y a aucun moyen possible de trouver une expression rationnelle équivalente qui ne provoquera pas une explosion exponentielle en temps d'exécution.

(Un tel équivalent pourrait exister et pourrait même être trouvé en théorie, mais sous des hypothèses plausibles, trouver l'expression rationnelle équivalente prendra un temps exponentiel, ce qui n'est pas possible en pratique. Si vous aviez une procédure systématique pour trouver l'expression rationnelle équivalente en temps polynomial , alors vous pourriez résoudre le problème NP-difficile en temps polynomial, prouvant que P = NP. Il n'y a pas grand-chose de bon pour qu'il existe une expression rationnelle équivalente s'il n'y a aucun moyen de le trouver dans votre vie.)


Contexte et sources:

DW
la source
N'est-il pas plus facile de trouver une alternative non perverse en divisant le regex en plusieurs regex plus petits et en les utilisant en combinaison?
inf3rno
1

Cette réponse adoptera une vue plus globale de cette situation transversale inhabituelle, où la théorie de la complexité est applicable à la cybersécurité et l'exemple contient certaines des nuances / subtilités importantes qui peuvent se produire dans ce domaine. Ceci est essentiellement similaire à une "attaque par injection" où certaines entrées inattendues provoquent un comportement pathologique soit en plantant un système, soit en le faisant prendre un temps anormalement long.

Wikipedia a 15 catégories d' attaques par déni de service et cette attaque tombe dans "inondations au niveau des applications" dans cette liste. Un autre exemple quelque peu similaire est une attaque qui remplit les journaux des applications.

Un correctif pour les attaques par injection consiste à «nettoyer l'entrée». Le concepteur d'application peut réévaluer s'il est nécessaire de compiler des expressions rationnelles arbitraires fournies par un utilisateur potentiellement malveillant. Il suffit probablement de supprimer les expressions imbriquées dans l'expression rationnelle ou une autre limitation similaire pour éviter cette attaque. Bien qu'ils soient intrinsèques à de nombreux logiciels modernes, de grandes quantités de fonctionnalités peuvent être fournies sans évaluer les expressions régulières. Le contexte est important, certaines applications ne nécessiteraient pas une telle sécurité.

Une autre approche pour améliorer la tolérance aux pannes / la résilience qui s'applique ici est les délais d'expiration spécifiés à différents niveaux de la pile / hiérarchie logicielle. L'idée serait de spécifier un temps / cpu ou une limite d'instruction sur une évaluation d'expression régulière "moyenne" et de terminer tôt si elle est dépassée. Ils peuvent être implémentés avec des solutions personnalisées, mais peu de logiciels ou de langages de programmation ont des délais d'expiration ou des cadres intégrés à cet effet.

Voici un bel exemple de l'utilisation des délais d'attente pour améliorer la tolérance aux pannes et montre une conception / architecture / pov de haut niveau pour atténuer ces problèmes: Tolérance aux pannes dans un système distribué à haut volume / Netflix. Il n'a rien de spécifiquement lié aux expressions régulières, mais c'est le point ici: pratiquement toute logique de niveau application peut s'intégrer dans ce cadre ou quelque chose de similaire.

Cet article souligne comment le retour en arrière en particulier peut conduire à une correspondance d'expression rationnelle lente. Les regexps ont de nombreuses fonctionnalités différentes et on pourrait essayer d'évaluer celles qui conduisent aux comportements les plus défavorables.

Voici une belle étude scientifique de ce sujet particulier avec des solutions d' analyse statique proposées:

  • Analyse statique du temps d'exécution exponentiel à expression régulière via la logique sous-structurelle / Rathnayake, Thielecke

    La mise en correspondance d'expressions régulières à l'aide du backtracking peut avoir un temps d'exécution exponentiel, conduisant à une attaque de complexité algorithmique appelée REDoS dans la littérature sur la sécurité des systèmes. Dans cet article, nous nous appuyons sur une analyse statique récemment publiée qui détecte si une expression régulière donnée peut avoir un temps d'exécution exponentiel pour certaines entrées. Nous construisons systématiquement une analyse plus précise en formant des puissances et des produits de relations de transition et en réduisant ainsi le problème REDoS à l'accessibilité. La justesse de l'analyse est prouvée à l'aide d'un calcul sous-structurel des arbres de recherche, où la ramification de l'arbre provoquant l'explosion exponentielle est caractérisée comme une forme de non-linéarité.

vzn
la source
Cette réponse semble confuse sur certains aspects de ReDos. 1. ReDoS n'a rien à voir avec une attaque par injection. Les attaques par injection (par exemple, XSS, injection SQL, injection de commande, etc.) sont totalement différentes. 2. ReDos ne concerne pas les expressions rationnelles malveillantes soumises par un adversaire. En règle générale, l'expression rationnelle est codée en dur dans le programme (fournie par le développeur) et la chaîne d'entrée est fournie par un utilisateur. Le problème ne peut pas être raisonnablement résolu par la validation des entrées, car il n'existe généralement pas de politique de validation des entrées claire qui suffirait à éliminer le problème.
DW
pensez que vos points équivalent à des détails techniques / à la séparation des cheveux basés sur la référence ReDos et que la forêt manque pour les arbres. son semblable aux «attaques par injection artisanales». la réponse souligne qu'il existe des alternatives à l'utilisation des expressions rationnelles dans le code. l'analyse statique peut trouver les "regexps maléfiques". tous les points de la réponse sont valables. une phrase comme "généralement l'expression rationnelle est codée en dur dans le programme (fourni par le développeur), et la chaîne d'entrée est fournie par un utilisateur" ne correspond pas exactement à l'écriture ReDos qui est plus vague par endroits, et fait référence à un attaquant malveillant, etc. .
VZN