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

Получил простую задачу, чтобы получить выражение 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 с чем-то нетривиальным может быть очень рискованным.

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


.net infinite-loop regex
person Dror Harari    schedule 29.07.2009    source источник
comment
в общем, разве это не эквивалентно проблеме остановки?   -  person Mitch Wheat    schedule 29.07.2009

Ответы (4)


arrow_upward
6
arrow_downward

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

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

(Я предполагаю, что вы имели в виду \" в своей экранированной строке С#, а не ""... перевод из 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 прямо выше.)

person richardtallent    schedule 29.07.2009
comment
Ну, это было продуктивно (для меня) - спасибо, Ричард. Я пришел к выводу, что: 1. Получение шаблона регулярного выражения из внешнего источника опасно и может легко испортить приложение. 2. Регулярное выражение в .NET не обнаруживает бесконечные циклы, а также не дает возможности ограничить обработку. 3. Это другое регулярное выражение. движок может давать разные результаты, поэтому, даже если синтаксис одинаков, некоторая семантика может отличаться (примечание о переносимости). Спасибо. - person Dror Harari; 30.07.2009
comment
Я думаю, что различия, которые вы видели, были связаны с разными диалектами регулярных выражений, а не с причудливым обнаружением бесконечного цикла в других движках. Основная проблема заключается в том, чтобы обернуть что-то, что может соответствовать пустому тексту бесконечное количество раз. Все, что является вариацией (x?)+ или (x?)*, может быть опасным при правильном вводе. Рефакторинг вашего шаблона должен позволить вам получить то, что вам нужно, не создавая возможности для бесконечного цикла. Независимо от языка, урок состоит в том, чтобы всегда программировать с защитой от произвольного ввода пользователя. - person richardtallent; 30.07.2009
comment
Проблема здесь в том, что этот ввод может соответствовать ([^]]*(])?) бесконечное количество раз, и он никогда не будет поглощен, а + заставит его просто продолжать попытки. ЗАЧЕМ ???? - person MemoryLeak; 29.09.2009
comment
Столкнулся с этим сам со сложной закономерностью. Конечно, мне больше никогда не захочется использовать Regex. У вас есть что-то, в чем может быть фугас, и не из-за бага. При достаточно сложном паттерне никогда нельзя быть уверенным, что эта мина взорвется. - person dudeNumber4; 11.08.2016

arrow_upward
3
arrow_downward

Чтобы ответить на первоначальный вопрос (т. е. как избежать бесконечного цикла с помощью регулярных выражений), это стало легко с .Net 4.5, поскольку вы можете просто передать время ожидания методам регулярных выражений. Существует внутренний таймер, который остановит цикл регулярных выражений по истечении времени ожидания и вызовет исключение 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 для получения более подробной информации.

person Julien Jacobs    schedule 16.10.2014
comment
Спасибо! - это, безусловно, полезная и актуальная информация, но все же первоначальная цель состояла в том, чтобы понять, как избежать этого случая для начала) - приятно знать, что через 5 секунд он выдаст исключение, но гораздо лучше написать его правильно для начала ... - person Dror Harari; 24.12.2014

arrow_upward
2
arrow_downward

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

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

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

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

person Damien Doligez    schedule 25.10.2016

arrow_upward
1
arrow_downward

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

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

person richardtallent    schedule 29.07.2009
comment
Я считаю этот ответ контрпродуктивным. Другие механизмы RegEx, которые я пробовал, не попадали в бесконечный цикл (попробуйте, например, онлайн-тестер JavaScript RegEx по адресу regular-expressions.info/javascriptexample.html, и вы увидите, что все работает отлично). Это регулярное выражение достаточно простое, и я не нахожу тривиальным тот факт, что его ожидаемый режим отказа (когда совпадение не найдено) представляет собой бесконечный цикл. Идея с тредом тоже не годится. Должен ли я использовать эту идею везде, где предоставляется внешний RegEx? Я так не думаю. Я думаю, что это, вероятно, ошибка в RegEx (или большая зияющая дыра). - person Dror Harari; 29.07.2009