17
правок
Изменения
Добавлена основные пункты конспекта. Содержит кучу ошибок.
== Реализация регулярных выражений в современных языках ==
В настоящее время используется несколько различных подходов к реализации регулярных выражений. Всегда можно довольно просто построить не НКА. Но после построения есть несколько вариантов:
# можно конвертировать его в детерминированный конечный автомат;
# можно идти по каждому из возможных путей, а в случае неудачи возвращаться назад и пробовать другой;
# можно идти по автомату одновременно по всем возможным состояниям;
# можно конвертировать НКА в ДКА лениво (на лету).
Следующее изображение наглядно показывает, что можно выделить более менее два основных подхода к реализации, давайте же разберемся почему так получилось.
{| cellpadding="1" style="margin-left: auto; margin-right: auto;"
|[[Файл:RegExp.png|779px|thumb|regular expression and text size n <tex>a?^na^n</tex> matching <tex>a^n</tex>]]
|}
Это произошло из-за того, что обычного функционала регулярных выражений зачастую недостаточно, не хватает выразительной мощности. В языках PCRE, Ruby, Python, Perl добавили поддержку обратной связи. Она позволяет связывать ранее найденное сгруппированное выражение в скобках с числом от 1 до 9. Например: (cat|dog)\1 найдет catcat или dogdog, но никак не catdog или dogcat. Интересно, что с добавлением обратной связи регулярные выражения перестаю относиться к классу регулярных языков. К сожалению, лучшая реализация требует экспоненциального времени работы. Приведенная на графике синяя кривая является реализацией построения NFA по регулярному выражению написанная на C, занимающая чуть меньше, чем 400 строк и описанная в [https://swtch.com/~rsc/regexp/regexp1.html данной статье].
=== Построение НКА ===
Для построения автомата нам нужно построить отдельно части НКА для каждой части выражения, финальным шагом будет соединение всего автомата вместе.
=== Дополнительные возможности регулярных выражений ===
==== Символьные классы ====
Набор символов в квадратных скобках [ ] именуется символьным классом и позволяет указать интерпретатору регулярных выражений, что на данном месте в строке может стоять один из перечисленных символов. Можно указывать диапазоны [0-9], [a-z], а также существуют дополнительные символьные классы <tex>[[:upper:]], [[:word:]]</tex>.
==== Квантификация. ====
Позволяет установить точное соотвествие повторов равное числу n - {n}; {n,m} - не меньше чем n, и не больше чем m. {n,} - n и больше. Можно найти эквиваленты символам *, +, ?. С помощью символов { }
{| class="wikitable"
|-
| ?
| {0,1}
|-
| +
| {1,}
|-
| *
| {}
|}
==== Позиция внутри строки ====
==== Жадная и ленивая квантификация ====
В некоторых реализациях квантификаторам в регулярных выражениях соответствует максимально длинная строка из возможных (квантификаторы являются жадными, англ. greedy). Это может оказаться значительной проблемой. Например, часто ожидают, что выражение (<.*>) найдёт в тексте теги HTML. Однако если в тексте есть более одного HTML-тега, то этому выражению соответствует целиком строка, содержащая множество тегов.
{| class="wikitable"
! Жадный
! Ленивый
|-
| *
| *?
|-
| +
| +?
|-
| {n,}
| {n,}?
|}
== Несколько полезных оптимизаций на примере Haskell ==
[[ https://begriffs.com/posts/2016-06-27-fast-haskell-regexes.html Gabriel Gonzalez ]] реализовал алгоритм Томпсона на языке Haskell. В первоначальном варианте это алгоритм получился в 480 раз медленее, чем grep на том же тесте, чтобы улучшить результат он предпринял ряд оптимизаций:
* вместо Set Int использовал Integer, а также использовал битовые операции, в результате производительность выросла в 5 раз
* использовал Word вместо Integer, ещё в 8 раз быстрее
* а также использовал ByteString оптимизации, что увеличило производительность ещё 3 раза.
В итоге его реализация оказалась всего в 4 раза медленее grep. Но это не предел, у него получилось реализовать [https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/asplos302-mytkowicz.pdf параллельный конечный автомат] и сделать свою реализацию в 1.5 раза быстрее, чем grep.
== ReDoS (regular expression denial of service) ==
Интересно, что злоумышленники научились атаковать системы используя то, что некоторые алгоритмы имеют экспоненциальную сложность. В регулярных выражениях использующих обратную связь есть несколько вариантов:
* использовать повторение ("+","*") для достаточно сложных подвыражений;
* сделать так, чтобы повторяющиеся подвыражения были суффиксами валидного совпадения.
Примеры вредоносных регулярных выражений:
* (a+)+
* ([a-zA-Z]+)*
* (a|aa)+
* (a|a?)+
* (.*a){x} for x > 10
Все эти выражения чувствительны к входной строке aaaaaaaaaaaaaaaaaaaaaaaaaa.
Также вредоносные регулярные выражения были обнаружены в онлайн репозиториях.
# [http://regexlib.com/REDetails.aspx?regexp_id=1757 RegExLib, id=1757 (email validation)] - '''выделенная''' часть является вредоносной<br /><code>^([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}))$</code>
# [http://www.owasp.org/index.php/OWASP_Validation_Regex_Repository OWASP Validation Regex Repository], Java Classname - '''выделенная''' часть является вредоносной<br /><code>^'''(([a-z])+.)+'''[A-Z]([a-z])+$</code>
Эти два примера также чувствительны к входной строке aaaaaaaaaaaaaaaaaaaaaaaa.
== См. также ==
* [[ Регулярные языки: два определения и их эквивалентность ]]
* [[ Недетерминированные конечные автоматы ]]
* [[ Детерминированные конечные автоматы ]]
* [[ Построение по НКА эквивалентного ДКА, алгоритм Томпсона ]]
== Источники информации ==
* [https://swtch.com/~rsc/regexp/regexp1.html Regular Expression Matching Can Be Simple And Fast]
* [https://en.wikipedia.org/wiki/ReDoS ReDos]
* [https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/asplos302-mytkowicz.pdf Data-Parallel Finite-State Machines]
[[Категория: Теория формальных языков]]
[[Категория: Автоматы и регулярные языки]]
В настоящее время используется несколько различных подходов к реализации регулярных выражений. Всегда можно довольно просто построить не НКА. Но после построения есть несколько вариантов:
# можно конвертировать его в детерминированный конечный автомат;
# можно идти по каждому из возможных путей, а в случае неудачи возвращаться назад и пробовать другой;
# можно идти по автомату одновременно по всем возможным состояниям;
# можно конвертировать НКА в ДКА лениво (на лету).
Следующее изображение наглядно показывает, что можно выделить более менее два основных подхода к реализации, давайте же разберемся почему так получилось.
{| cellpadding="1" style="margin-left: auto; margin-right: auto;"
|[[Файл:RegExp.png|779px|thumb|regular expression and text size n <tex>a?^na^n</tex> matching <tex>a^n</tex>]]
|}
Это произошло из-за того, что обычного функционала регулярных выражений зачастую недостаточно, не хватает выразительной мощности. В языках PCRE, Ruby, Python, Perl добавили поддержку обратной связи. Она позволяет связывать ранее найденное сгруппированное выражение в скобках с числом от 1 до 9. Например: (cat|dog)\1 найдет catcat или dogdog, но никак не catdog или dogcat. Интересно, что с добавлением обратной связи регулярные выражения перестаю относиться к классу регулярных языков. К сожалению, лучшая реализация требует экспоненциального времени работы. Приведенная на графике синяя кривая является реализацией построения NFA по регулярному выражению написанная на C, занимающая чуть меньше, чем 400 строк и описанная в [https://swtch.com/~rsc/regexp/regexp1.html данной статье].
=== Построение НКА ===
Для построения автомата нам нужно построить отдельно части НКА для каждой части выражения, финальным шагом будет соединение всего автомата вместе.
=== Дополнительные возможности регулярных выражений ===
==== Символьные классы ====
Набор символов в квадратных скобках [ ] именуется символьным классом и позволяет указать интерпретатору регулярных выражений, что на данном месте в строке может стоять один из перечисленных символов. Можно указывать диапазоны [0-9], [a-z], а также существуют дополнительные символьные классы <tex>[[:upper:]], [[:word:]]</tex>.
==== Квантификация. ====
Позволяет установить точное соотвествие повторов равное числу n - {n}; {n,m} - не меньше чем n, и не больше чем m. {n,} - n и больше. Можно найти эквиваленты символам *, +, ?. С помощью символов { }
{| class="wikitable"
|-
| ?
| {0,1}
|-
| +
| {1,}
|-
| *
| {}
|}
==== Позиция внутри строки ====
==== Жадная и ленивая квантификация ====
В некоторых реализациях квантификаторам в регулярных выражениях соответствует максимально длинная строка из возможных (квантификаторы являются жадными, англ. greedy). Это может оказаться значительной проблемой. Например, часто ожидают, что выражение (<.*>) найдёт в тексте теги HTML. Однако если в тексте есть более одного HTML-тега, то этому выражению соответствует целиком строка, содержащая множество тегов.
{| class="wikitable"
! Жадный
! Ленивый
|-
| *
| *?
|-
| +
| +?
|-
| {n,}
| {n,}?
|}
== Несколько полезных оптимизаций на примере Haskell ==
[[ https://begriffs.com/posts/2016-06-27-fast-haskell-regexes.html Gabriel Gonzalez ]] реализовал алгоритм Томпсона на языке Haskell. В первоначальном варианте это алгоритм получился в 480 раз медленее, чем grep на том же тесте, чтобы улучшить результат он предпринял ряд оптимизаций:
* вместо Set Int использовал Integer, а также использовал битовые операции, в результате производительность выросла в 5 раз
* использовал Word вместо Integer, ещё в 8 раз быстрее
* а также использовал ByteString оптимизации, что увеличило производительность ещё 3 раза.
В итоге его реализация оказалась всего в 4 раза медленее grep. Но это не предел, у него получилось реализовать [https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/asplos302-mytkowicz.pdf параллельный конечный автомат] и сделать свою реализацию в 1.5 раза быстрее, чем grep.
== ReDoS (regular expression denial of service) ==
Интересно, что злоумышленники научились атаковать системы используя то, что некоторые алгоритмы имеют экспоненциальную сложность. В регулярных выражениях использующих обратную связь есть несколько вариантов:
* использовать повторение ("+","*") для достаточно сложных подвыражений;
* сделать так, чтобы повторяющиеся подвыражения были суффиксами валидного совпадения.
Примеры вредоносных регулярных выражений:
* (a+)+
* ([a-zA-Z]+)*
* (a|aa)+
* (a|a?)+
* (.*a){x} for x > 10
Все эти выражения чувствительны к входной строке aaaaaaaaaaaaaaaaaaaaaaaaaa.
Также вредоносные регулярные выражения были обнаружены в онлайн репозиториях.
# [http://regexlib.com/REDetails.aspx?regexp_id=1757 RegExLib, id=1757 (email validation)] - '''выделенная''' часть является вредоносной<br /><code>^([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}))$</code>
# [http://www.owasp.org/index.php/OWASP_Validation_Regex_Repository OWASP Validation Regex Repository], Java Classname - '''выделенная''' часть является вредоносной<br /><code>^'''(([a-z])+.)+'''[A-Z]([a-z])+$</code>
Эти два примера также чувствительны к входной строке aaaaaaaaaaaaaaaaaaaaaaaa.
== См. также ==
* [[ Регулярные языки: два определения и их эквивалентность ]]
* [[ Недетерминированные конечные автоматы ]]
* [[ Детерминированные конечные автоматы ]]
* [[ Построение по НКА эквивалентного ДКА, алгоритм Томпсона ]]
== Источники информации ==
* [https://swtch.com/~rsc/regexp/regexp1.html Regular Expression Matching Can Be Simple And Fast]
* [https://en.wikipedia.org/wiki/ReDoS ReDos]
* [https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/asplos302-mytkowicz.pdf Data-Parallel Finite-State Machines]
[[Категория: Теория формальных языков]]
[[Категория: Автоматы и регулярные языки]]
