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

Question

Давайте рассмотрим две следующие строки на C# (с использованием платформы .NET 3.5).

Regex regex = new Regex(@"^((E|e)t )?(M|m)oi (?<NewName>[A-Za-z]\.?\w*((\-|\s)?[A-Za-z]?\w{1,})+)$", RegexOptions.Compiled | RegexOptions.IgnoreCase);
Match m = regex.Match("moi aussi jaimerai etre un ordinateur pour pas m'énnerver ");

(извините, это французская программа :))

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

Кто-нибудь знает, является ли это хорошо известной проблемой с регулярным выражением .NET, и есть ли простой способ обойти ее, или мне придется объединить эти строки и прервать их, если это необходимо (определенно, я бы не хотел этого делать) ).

Answer 1

Я думаю, вам следует просто запустить сопоставление Regex в отдельном потоке и разрешить его прерывание, если будет достигнут определенный максимальный предел времени.

Answer 2

Если я введу выражение в Regexbuddy, оно выдаст следующее сообщение

Попытка матча была прервана рано, потому что регулярное выражение слишком сложное.Двигатель режима Regex, с которым вы планируете использовать его, может быть не в состоянии справиться с ним вообще и сбой.Посмотрите «катастрофическое возвращение» в файле помощи, чтобы узнать, как избежать этой ситуации.

Глядя вверх катастрофический возврат назад дает следующее объяснение

Неуправляемые регулярные выражения:Катастрофический возврат назад
Рассмотрим регулярное выражение (x+x+)+y.Прежде чем кричать в ужасе и скажем, этот надувший пример должен быть написан как xx+y, чтобы соответствовать точно так же без этих ужасно вложенных квантиров:Просто предположим, что каждый «x» представляет что -то более сложное, с определенными строками, соответствующими обоими "x".См. Раздел о файлах HTML ниже для реального примера.

Давайте посмотрим, что произойдет, когда вы применяете эту регуляцию к XXXXXXXXXY.Первый x+ будет соответствовать всем 10 x символам.Второй x+ терпит неудачу.Первый x+, затем отступает до 9 совпадений, а второй поднимает оставшиеся x.Группа уже совпала один раз.Группа повторяется, но терпит неудачу на первом x+.Поскольку одного повторения было достаточно, групповые матчи.Y Матчи Y и общий матч найден.Регулярная эксплуатация объявлена ​​функциональной, код отправляется клиенту, а его компьютер взрывается.Почти.

Вышеупомянутая регуляция становится безобразной, когда Y отсутствует в строке субъекта.Когда Y выходит из строя, возврат двигателя коррекса.Группа имеет одну итерацию, в которую он может отступить.Второй x+ соответствовал только одному x, так что он не может отступить.Но первый X+ может отказаться от одного x.Второй x+ быстро соответствует xx.Группа снова имеет одну итерацию, терпит неудачу следующей, и Y выходит из строя.Вернувшись снова, второй X+ теперь имеет одну позицию отступания, уменьшаясь в соответствии с X.Группа пробует вторую итерацию.Первый x+ совпадает, но второй застрял в конце строки.Вновь возвращаясь, первый X+ в первой итерации группы снижается до 7 символов.Второй x+ соответствует XXX.Сбой y, второй x+ сводится к XX, а затем x.Теперь группа может соответствовать второй итерации, с одним x для каждого x+.Но эта комбинация (7,1), (1,1) тоже не удается.Таким образом, он переходит к (6,4), а затем (6,2) (1,1), а затем (6,1), (2,1), а затем (6,1), (1,2), а затем и Думаю, вы начинаете получать дрейф.

Если вы попробуете эту регуляцию на 10 -кратной строке в отладчике Regexbuddy, потребуется 2558 шагов, чтобы выяснить, что Final Y отсутствует.Для строки 11x она нуждается в 5118 шагах.Для 12 это занимает 10238 шагов.Очевидно, что у нас есть экспоненциальная сложность O (2^n) здесь.В 21х отладчик выбивает на 2,8 миллиона шагов, диагностируя плохой случай катастрофического возврата.

Regexbuddy прощается в том, что он обнаруживает, что он идет по кругу, и прерывает попытку матча. Другие двигатели корпорации (например, .net) будут продолжаться вечно, в то время как другие сбои с переполнением стека (например, Perl, до версии 5.10).Переполнения стека особенно противны на окнах, поскольку они, как правило, заставляют ваше приложение исчезнуть без следа или объяснения.Будьте очень осторожны, если вы запустите веб -сервис, который позволяет пользователям предоставлять свои собственные регулярные выражения.Люди с небольшим опытом работы с режимами обладают удивительными навыками при разработке экспоненциально сложных регулярных выражений.

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

Answer 3

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

Answer 4

Проблема в том, что в вашем регулярном выражении есть вложенные «циклы», которые делают его ужасно неэффективным (по сути, это занимает вечность из-за сложности выражения).

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

Answer 5

Мне кажется, это тот случай, когда соответствие регулярных выражений растет в геометрической прогрессии.См. Блог BCL.

Лучшее решение — установить тайм-аут для регулярного выражения, не возиться с потоками.

Посмотрите здесь, как вырезать строки с таймаутом.