Comment éviter les boucles infinies dans la classe .NET RegEx?

Question

Vous avez une tâche simple qui consiste à obtenir une expression XPath et à renvoyer un préfixe qui correspond au parent du nœud sélectionné (le cas échéant).

Exemple:

/aaa/bbb       =>   /aaa
/aaa/bbb/ccc   =>   /aaa/bbb
/aaa/bbb/ccc[@x='1' and @y="/aaa[name='z']"] => /aaa/bbb

Étant donné que les modèles entre crochets peuvent contenir des crochets entre guillemets, j’ai décidé d’essayer d’atteindre cet objectif en utilisant des expressions régulières. Voici un extrait de code:

string input =
    "/aaa/bbb/ccc[@x='1' and @y=\"/aaa[name='z'] \"]";
                                            //  ^-- remove space for no loop
string pattern = @"/[a-zA-Z0-9]+(\[([^]]*(]"")?)+])?<*>quot;;

System.Text.RegularExpressions.Regex re =
    new System.Text.RegularExpressions.Regex(pattern);
bool ismatch = re.IsMatch(input); // <== Infinite loop in here
// some code based on the match

Comme les motifs sont assez réguliers, j'ai cherché '/' suivi d'un identifiant suivi d'un groupe facultatif qui correspond à la fin de la chaîne (....)? $

Le code semblait fonctionner, mais en jouant avec différentes valeurs pour la chaîne d'entrée, j'ai constaté qu'en insérant simplement un espace (à l'emplacement indiqué dans le commentaire), la fonction .NET IsMatch se met dans une boucle infinie, prenant toutes les Le CPU qu’il obtient.

Maintenant, que ce modèle d’expression régulière soit le meilleur (j’avais plus de complexité, mais je l’ai simplifié pour montrer le problème), cela semble montrer qu’utiliser RegEx avec quelque chose de non trivial peut être très risqué.

Est-ce que je manque quelque chose? Existe-t-il un moyen de se prémunir contre des boucles infinies dans les correspondances d'expressions régulières?

Answer 1

Ok, décomposons cela alors:

Input: /aaa/bbb/ccc[@x='1' and @y="/aaa[name='z'] "]
Pattern: /[a-zA-Z0-9]+(\[([^]]*(]")?)+])?$

(Je suppose que vous vouliez dire "dans la chaîne évacuée par C #, et non" ... traduction de VB.NET?)

D'abord, / [a-zA-Z0-9] + va engloutir à travers le premier crochet, laissant ainsi:

Input: [@x='1' and @y="/aaa[name='z'] "]

Le groupe extérieur de (\ [([^]] * (] ""?)?) +])? $ " doit correspondre s'il y a 0 ou 1 instance avant l'EOL. Brisons donc à l'intérieur et voyons si cela correspond à quoi que ce soit.

Le " [" est tout de suite englouti, nous laissant avec:

Input: @x='1' and @y="/aaa[name='z'] "]
Pattern: ([^]]*(]")?)+]

Décomposer le modèle: faites correspondre au moins 0 caractères non ] , puis à "] 0 ou 1 fois, et continuez ainsi jusqu'à ce que vous ne puissiez plus vous connecter. . Ensuite, essayez de trouver et de dévorer un ] après.

Le modèle correspond sur la base de [^]] * jusqu'à ce qu'il atteigne le ] .

Comme il y a un espace entre ] et "", il ne peut engloutir aucun de ces caractères, mais ? après (] ") lui permet de retourner vrai quand même.

Maintenant, nous avons réussi à faire correspondre la ([^]] * (] ")?) une fois, mais le + indique que nous devrions essayer de faire correspondre ce résultat nombre de fois que nous pouvons.

Cela nous laisse avec:

Input: ] "]

Le problème ici est que cette entrée peut correspondre à ([^]] * (] ")?) à un infini de fois sans jamais être englouti, et " + " va le forcer à continuer d'essayer.

Vous faites essentiellement correspondre "1 ou plus". situations où vous pouvez faire correspondre "0 ou 1" de quelque chose suivi de "0 ou 1" de quelque chose d'autre. Étant donné qu’aucun des deux sous-modèles n’existe dans l’entrée restante, il continue à faire correspondre 0 de [^]] \ * et 0 de (] ")? dans une boucle sans fin. .

L'entrée n'est jamais engloutie et le reste du motif après "& +". n'est jamais évalué.

(J'espère que j'ai le SO-escape-of-regex-escape juste au-dessus.)

Answer 2

  

Le problème ici est que cette entrée peut correspondre à ([^]] * (] ")?) une infinité de fois sans jamais être engloutie, et" + ". va le forcer à continuer d'essayer.

C'est un sacré bug dans l'implémentation RegEx de .NET. Les expressions régulières ne fonctionnent tout simplement pas comme ça. Lorsque vous les convertissez en automates, vous obtenez automatiquement le fait qu’une répétition infinie d’une chaîne vide est toujours une chaîne vide.

En d’autres termes, tous les moteurs de expressions rationnelles non bogués exécuteront cette boucle infinie instantanément et continueront avec le reste de l’expression régulière.

Si vous préférez, les expressions régulières sont un langage tellement limité qu'il est possible (et facile) de détecter et d'éviter de telles boucles infinies.

Answer 3

Cela montre que l’utilisation de code avec quelque chose de non trivial peut être risquée. Vous avez créé du code pouvant entraîner une boucle infinie et le compilateur RegEx est obligé. Rien de nouveau qui n’a été fait depuis les 20 premiers IF X = 0 THEN GOTO 10.

Si cela vous inquiète dans un cas particulier, vous pouvez créer un thread pour RegEx puis le tuer après un délai d'exécution raisonnable.

Answer 4

Pour répondre à la question initiale (comment éviter la boucle infinie avec regex), cela est devenu facile avec .Net 4.5, car vous pouvez simplement laisser un temps mort aux méthodes Regex. Il existe un minuteur interne qui arrête la boucle regex à l'expiration du délai et génère une exception RegexMatchTimeoutException

Par exemple, vous feriez ce qui suit

string input = "/aaa/bbb/ccc[@x='1' and @y=\"/aaa[name='z'] \"]";
string pattern = @"/[a-zA-Z0-9]+(\[([^]]*(]"")?)+])?<*>quot;;
bool ismatch = Regex.IsMatch(input, pattern, RegexOptions.None, TimeSpan.FromSeconds(5));

Vous pouvez consulter MSDN . pour plus de détails