Как избежать бесконечных циклов в классе .NET RegEx? - PullRequest
Новая
       14

Как избежать бесконечных циклов в классе .NET RegEx?

1 голос
/ 29 июля 2009

Получил простое задание, чтобы получить выражение XPath и вернуть префикс, который соответствует родительскому узлу выбранного узла (может быть).

Пример: 

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

Поскольку шаблоны внутри квадратных скобок могут содержать квадратные скобки в кавычках, я решил попытаться добиться этого с помощью регулярных выражений. Вот фрагмент кода: 

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

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

Поскольку шаблоны довольно обычные, я искал '/', за которым следовал идентификатор, а затем необязательная группа, совпадающая в конце строки (....)? $

Код, похоже, работал, но, играя с разными значениями для входной строки, я обнаружил, что, просто вставляя пробел (в месте, указанном в комментарии), функция .NET IsMatch попадает в бесконечный цикл, принимая все Процессор он получает.

Теперь, независимо от того, является ли этот шаблон регулярного выражения лучшим (у меня был более сложный, но упростил его, чтобы показать проблему), это, кажется, показывает, что использование RegEx с чем-то нетривиальным может быть очень рискованным.

Я что-то упустил? Есть ли способ защиты от бесконечных циклов в совпадениях регулярных выражений?

Ответы [ 4 ]

6 голосов
/ 30 июля 2009

Хорошо, тогда давайте разберемся с этим: 

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

(я полагаю, вы имели в виду \ "в вашей C # -экранированной строке, а не" "... перевод из VB.NET?)

Сначала / [a-zA-Z0-9] + сожрет первую квадратную скобку, оставив: 

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

Внешняя группа (\ [([^]] * (] "")?) +])? $ "Должна совпадать, если перед EOL есть 0 или 1 экземпляр. Так что давайте разберемся внутри и посмотрим, если это соответствует чему угодно.

"[" сразу же сожрет, оставив нам: 

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

Разбивка шаблона: сопоставьте 0 или более не ] символов, а затем сопоставьте "] 0 или 1 раз и продолжайте делать это, пока не сможете. Затем попробуйте найти и проглотить ] потом.

Шаблон соответствует на основе [^]] *, пока не достигнет ] .

Поскольку между ] и " есть пробел, он не может сожрать ни одного из этих символов, но ? после (]" ) позволяет в любом случае вернуть true.

Теперь мы успешно сопоставили ([^]] * (] ")?) один раз, но + говорит, что мы должны пытаться сопоставлять его любое количество раз мы можем.

Это оставляет нас с: 

Input: ] "]

Проблема здесь в том, что этот вход может совпадать с ([^]] * (] ")?) * бесконечное число раз без сожжения и" + " заставит его просто продолжать пытаться.

Вы по существу соответствуете «1 или более» ситуаций, в которых вы можете сопоставить «0 или 1» чего-то, за которым следует «0 или 1» чего-то другого. Так как ни один из двух подшаблонов не существует в оставшемся входе, он продолжает соответствовать 0 из [^]] \ * и 0 из (] ")? в бесконечном цикле.

Ввод никогда не сожрается, а оставшаяся часть шаблона после «+» никогда не оценивается.

(Надеюсь, я получил SO-escape-of-regex-escape прямо выше.)

2 голосов
/ 25 октября 2016

Проблема здесь в том, что этот ввод может соответствовать ([^]] * (] ")?) Бесконечное количество раз, даже не будучи сожранным, и« + »заставит его просто продолжать попытки.

Это чертовски большая ошибка в реализации .NET RegEx. Регулярные выражения просто так не работают. Когда вы превращаете их в автоматы, вы автоматически получаете тот факт, что бесконечное повторение пустой строки остается пустой строкой.

Другими словами, любой движок регулярных выражений без ошибок мгновенно выполнит этот бесконечный цикл и продолжит работу с остальной частью регулярного выражения.

Если вы предпочитаете, регулярные выражения являются настолько ограниченным языком, что можно (и легко) обнаружить и избежать таких бесконечных циклов.

1 голос
/ 17 октября 2014

Чтобы ответить на исходный вопрос (то есть, как избежать бесконечного цикла с регулярным выражением), это стало легко с .Net 4.5, так как вы можете просто передать время методам Regex. Существует внутренний таймер, который останавливает цикл регулярных выражений по истечении времени ожидания и вызывает RegexMatchTimeoutException

Например, вы бы сделали следующее 

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

Вы можете проверить MSDN для более подробной информации

1 голос
/ 29 июля 2009

Это показывает, что использование кода с чем-то нетривиальным может быть рискованным. Вы создали код, который может привести к бесконечному циклу, и компилятор RegEx обязался. Ничего нового, чего не было сделано с первых 20 ЕСЛИ X = 0 ТОГДА ПОЛУЧЕНО 10.

Если вы беспокоитесь об этом в конкретном крайнем случае, вы можете создать поток для RegEx и затем убить его после некоторого разумного времени выполнения.

...