Comment puis-je reconnaître un regex maléfique?

Question

J'ai récemment pris connaissance de l' expression Régulière de Déni de Service attaques, et a décidé d'extirper les soi-disant "mauvais" modèles regex partout où j'ai pu trouver dans ma base de code - ou au moins ceux qui sont utilisés sur la saisie de l'utilisateur. Les exemples donnés à l' OWASP lien ci-dessus et wikipédia sont utiles, mais ils ne font pas un bon travail en expliquant le problème dans des termes simples.

Une description de mal regexes, à partir de wikipédia:

• l'expression régulière s'applique la répétition ("+", "*") à un complexe sous-expression;
• pour la répétition de sous-expression, il existe un match qui est aussi un suffixe d'un autre match.

Avec des exemples, à nouveau à partir de wikipédia:

• (a+)+
• ([a-zA-Z]+)*
• (a|aa)+
• (a|a?)+
• (.*a){x} pour x > 10

Est-ce un problème qui n'a tout simplement pas avoir une explication plus simple? Je suis à la recherche de quelque chose qui pourrait rendre plus facile pour éviter ce problème lors de l'écriture de regexes, ou de les trouver à l'intérieur d'une base de code existante.

Answer 1

Si vous voulez en termes simples, le moteur d'expressions régulières n'est pas une lavette - si au premier abord il ne réussit pas, il va sauter de nouveau et d'essayer encore et encore, toutes les combinaisons possibles, jusqu'à ce qu'il trouve une correspondance.

Je vais prendre un modèle inspiré par le premier exemple que vous avez donné et sort pour vous:

^((ab)*)+$

Compte tenu de l'entrée:

ababab

Le moteur d'expressions régulières essaie quelque chose comme (ababab) et une correspondance est trouvée sur le premier essai. Yay!!! Mais alors nous jeter les bâtons dans:

abababa

Le moteur d'expressions régulières essaie (ababab) mais qui échoue à cause de l'extra - a. Mais n'ayez pas peur, notre intrépide moteur d'expressions régulières essaie à nouveau, cette fois avec quelque chose comme (abab)(ab). Mais cela ne fonctionne pas non plus. "OK," dit-il à lui-même, "le temps de la boucle vers le bas et les résoudre."

(ababab) - Nope
(abab)(ab) - Nope
(ab)(abab) - Nope
(ab)(ab)(ab) - Nope
()(ababab) - Nope
()(abab)(ab) - Nope
()(ab)(abab) - Nope
()(ab)(ab)(ab) - Nope
...

Avant de vous le savez, le moteur d'expressions régulières est de manger toutes les ressources de votre système en essayant de résoudre cette chose jusqu'à ce que, après avoir épuisé toutes les combinaisons possibles des termes, il abandonne finalement et se tourne vers vous en disant: "Ce n'est pas un match." En regardant en arrière, derrière le moteur d'expressions régulières, vous pouvez voir votre serveur, un bûcher de métal en fusion.

Comme pour l'identification de ces expressions régulières, il peut effectivement être très difficile. J'ai écrit un couple moi-même, même si je sais ce qu'ils sont et de manière générale, comment les éviter. Voir Regex prendre très longtemps. Emballage tout ce que vous pouvez dans un atomiques groupe peut aider à prévenir la mandature question. Il raconte essentiellement le moteur d'expressions régulières de ne pas essayer de multiples combinaisons - "si à première vous ne réussissez pas, fuyez!".

Malheureusement, une fois que c'est écrit, c'est vraiment très dur, immédiatement ou à trouver rapidement un problème de regex. En fin de compte, la reconnaissance d'un mauvais regex, c'est comme la reconnaissance d'un autre mauvais code, il faut beaucoup de temps et d'expérience et/ou un seul événement catastrophique.

(NOTE: La "correspond à" sont à titre indicatif seulement. L'ordre des matches dépend un peu sur le moteur d'expressions régulières, mais vous obtenez l'essentiel.)

Answer 2

Je voudrais résumer comme "Une répétition de la répétition". Le premier exemple que vous avez énuméré est un bon un, comme il est dit: "la lettre a, une fois ou plus dans une rangée. Cela peut encore arriver une fois ou plus dans une rangée".

Ce qu'il faut rechercher dans ce cas est la combinaison des quantificateurs, comme * et +.

Un peu plus subtil chose à regarder dehors pour est le thirsd et un quatrième. Ces exemples contiennent un OU de l'exploitation, dans laquelle les deux parties peut être vrai. Ceci, combiné avec un quantificateur de l'expression peut entraîner BEAUCOUP de potentiel correspond, selon la chaîne d'entrée.

Pour résumer, TLDR-style:

Attention, la façon dont les quantificateurs sont utilisés en combinaison avec d'autres opérateurs.

Answer 3

Je dirais que c'est lié au moteur d'expressions régulières en cours d'utilisation. Vous ne pouvez pas toujours être en mesure d'éviter ces types de regexes, mais si votre moteur d'expressions régulières est construit à droite, puis c'est moins un problème. Voir ce blog de la série pour un grand nombre d'informations sur le sujet de la regex moteurs.

Note de l'avertissement en bas de l'article, dans ce retour en arrière est un problème NP-Complet de problème. Il n'y a actuellement aucun moyen de traiter efficacement, et vous pourriez vouloir les interdire dans votre entrée.

Answer 4

Je ne pense pas que vous puissiez reconnaître de telles expressions régulières, du moins pas toutes ou pas sans limiter de manière restrictive leur expressivité. Si vous vous souciez vraiment des ReDoS, j'essaierais de les mettre en sandbox et de tuer leur traitement avec un timeout. Il est également possible qu'il existe des implémentations RegEx qui vous permettent de limiter leur quantité maximale de retour en arrière.

Answer 5

Il y a certains égards, je pense que vous pourriez mettre en œuvre la simplification des règles en les exécutant sur petit test d'entrées ou de l'analyse de l'expression rationnelle de la structure.

• (a+)+ peut être réduite en utilisant une sorte de règle pour le remplacement redondant opérateurs à juste (a+)
• ([a-zA-Z]+)* pourraient également être simplifiées grâce à notre nouvelle redondance combinant la règle d' ([a-zA-Z]*)

L'ordinateur peut exécuter des tests par l'exécution de la petite sous-expressions de la regex contre généré de façon aléatoire de séquences pertinentes des caractères ou des séquences de caractères, et de voir quels groupes ils finissent dans. Pour la première, l'ordinateur, c'est comme, hey les regex veut un, de sorte que vous permet de l'essayer avec 6aaaxaaq. Il voit alors que tous les "a", et seule la première groupm retrouver dans un groupe, et conclut que, peu importe combien les a il met, il ne sera pas question, depuis + obtient tous dans le groupe. La deuxième, c'est comme, hey, la regex veut un tas de lettres, donc permet de l'essayer avec -fg0uj=, et puis il voit de nouveau chaque grappe est dans un groupe, de sorte qu'il se débarrasse de la + à la fin.

Maintenant nous avons besoin d'une nouvelle règle pour gérer les suivantes: L'éliminer sans importance-les options de la règle.

• Avec (a|aa)+, l'ordinateur prend un coup d'oeil et c'est comme, on aime que les grosses deuxième, mais nous pouvons utiliser le fait que la première pour remplir les lacunes, permet de se faire et plusieurs aa que nous le pouvons, et voir si nous pouvons faire autre chose après que nous ayons terminé. Il pourrait tourner sur une autre chaîne de test, comme " l'eaaa@a~aa.' afin de déterminer qui.

• Vous pouvez vous protéger d' (a|a?)+ par avoir l'ordinateur rendre compte que les chaînes de appariés en a? ne sont pas les droïdes que nous recherchons, parce que depuis qu'il peut toujours faire correspondre n'importe où, nous décidons que nous n'aimons pas les choses comme (a?)+, et le jeter.

• Nous protéger de la (.*a){x} par arriver de se rendre compte que les personnages appariés en a aurait déjà été saisi par .*. Nous avons ensuite jeter la partie, et utiliser une autre règle pour remplacer la redondant quantificateurs en (.*){x}.

Alors que la mise en œuvre d'un tel système serait très compliqué, c'est un problème compliqué et compliqué, la solution peut être nécessaire. Vous devez également utiliser des techniques d'autres personnes ont apporté, comme autorisant uniquement le regex certaine quantité limitée de l'exécution des ressources avant de le tuer si il ne la termine pas.