Автоматы в современном мире

Реализация регулярных выражений в современных языках

В настоящее время используется несколько различных подходов к реализации регулярных выражений. Всегда можно довольно просто построить не НКА. Но после построения есть несколько вариантов:

1. можно конвертировать его в детерминированный конечный автомат;
2. можно идти по каждому из возможных путей, а в случае неудачи возвращаться назад и пробовать другой;
3. можно идти по автомату одновременно по всем возможным состояниям;
4. можно конвертировать НКА в ДКА лениво (на лету).

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

regular expression and text size n [math]a?^na^n[/math] matching [math]a^n[/math]

Это произошло из-за того, что обычного функционала регулярных выражений зачастую недостаточно, не хватает выразительной мощности. В языках PCRE, Ruby, Python, Perl добавили поддержку обратной связи. Она позволяет связывать ранее найденное сгруппированное выражение в скобках с числом от 1 до 9. Например: (cat|dog)\1 найдет catcat или dogdog, но никак не catdog или dogcat. Интересно, что с добавлением обратной связи регулярные выражения перестаю относиться к классу регулярных языков. К сожалению, лучшая реализация требует экспоненциального времени работы. Приведенная на графике синяя кривая является реализацией построения NFA по регулярному выражению написанная на C, занимающая чуть меньше, чем 400 строк и описанная в данной статье.

Построение НКА

Для построения автомата нам нужно построить отдельно части НКА для каждой части выражения, финальным шагом будет соединение всего автомата вместе.

Дополнительные возможности регулярных выражений

Символьные классы

Набор символов в квадратных скобках [ ] именуется символьным классом и позволяет указать интерпретатору регулярных выражений, что на данном месте в строке может стоять один из перечисленных символов. Можно указывать диапазоны [0-9], [a-z], а также существуют дополнительные символьные классы [math][[:upper:]], [[:word:]][/math].

Квантификация.

Позволяет установить точное соотвествие повторов равное числу n - {n}; {n,m} - не меньше чем n, и не больше чем m. {n,} - n и больше. Можно найти эквиваленты символам *, +, ?. С помощью символов { }

?	{0,1}
+	{1,}
*	{}

Позиция внутри строки

Следующие символы позволяют спозиционировать регулярное выражение относительно элементов текста: начала и конца строки, границ слова.

Представление	Позиция
^	Начало текста
$	Конец текста
\b	Граница слова
\G	Предыдущий успешный поиск

Жадная и ленивая квантификация

В некоторых реализациях квантификаторам в регулярных выражениях соответствует максимально длинная строка из возможных (квантификаторы являются жадными, англ. greedy). Это может оказаться значительной проблемой. Например, часто ожидают, что выражение (<.*>) найдёт в тексте теги HTML. Однако если в тексте есть более одного HTML-тега, то этому выражению соответствует целиком строка, содержащая множество тегов.

Жадный	Ленивый
*	*?
+	+?
{n,}	{n,}?

Эту проблему можно решить двумя способами.

Учитывать символы, не соответствующие желаемому образцу (<[^>]*> для вышеописанного случая). Определить квантификатор как нежадный (ленивый, англ. lazy) — большинство реализаций позволяют это сделать, добавив после него знак вопроса.

Ревнивая квантификация (Сверхжадная)

В отличие от обычной (жадной) квантификации, ревнивая (possessive) квантификация не только старается найти максимально длинный вариант, но ещё и не позволяет алгоритму возвращаться к предыдущим шагам поиска для того, чтобы найти возможные соответствия для оставшейся части регулярного выражения.

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

Жадный	Ревнивый
*	*+
?	?+
+	++
{n,}	{n,}+

Несколько полезных оптимизаций на примере Haskell

Gabriel Gonzalez реализовал алгоритм Томпсона на языке Haskell. В первоначальном варианте это алгоритм получился в 480 раз медленее, чем grep на том же тесте, чтобы улучшить результат он предпринял ряд оптимизаций:

• вместо Set Int использовал Integer, а также использовал битовые операции, в результате производительность выросла в 5 раз
• использовал Word вместо Integer, ещё в 8 раз быстрее
• а также использовал ByteString оптимизации, что увеличило производительность ещё 3 раза.

В итоге его реализация оказалась всего в 4 раза медленее grep. Но это не предел, у него получилось реализовать параллельный конечный автомат и сделать свою реализацию в 1.5 раза быстрее, чем grep.

ReDoS (regular expression denial of service)

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

• использовать повторение ("+","*") для достаточно сложных подвыражений;
• сделать так, чтобы повторяющиеся подвыражения были суффиксами валидного совпадения.

Примеры вредоносных регулярных выражений:

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

Все эти выражения чувствительны к входной строке aaaaaaaaaaaaaaaaaaaaaaaaaa. Также вредоносные регулярные выражения были обнаружены в онлайн репозиториях.

1. RegExLib, id=1757 (email validation) - выделенная часть является вредоносной
   ^([a-zA-Z0-9])(([\-.]|[_]+)?([a-zA-Z0-9]+))*(@){1}[a-z0-9]+[.]{1}(([a-z]{2,3})|([a-z]{2,3}[.]{1}[a-z]{2,3}))$
2. OWASP Validation Regex Repository, Java Classname - выделенная часть является вредоносной
   ^(([a-z])+.)+[A-Z]([a-z])+$

Эти два примера также чувствительны к входной строке aaaaaaaaaaaaaaaaaaaaaaaa.

См. также

• Регулярные языки: два определения и их эквивалентность
• Недетерминированные конечные автоматы
• Детерминированные конечные автоматы
• Построение по НКА эквивалентного ДКА, алгоритм Томпсона

Источники информации

• Regular Expression Matching Can Be Simple And Fast
• ReDos
• Data-Parallel Finite-State Machines