1632
правки
Изменения
м
rollbackEdits.php mass rollback
'''state''' out1
'''int''' lastlist
Каждый <tex>\mathrm{state}</tex> представляет один из фрагментов НКА, зависящий от символа <tex>c</tex>.
Данная реализация будет поддерживать постфиксную нотацию регулярного выражения. Допустим у нас есть функция <tex>\mathrm{re2post}</tex>, которая переписывает инфиксную форму регулярного выражения <tex>``a(bb)+a"</tex> в эквивалентную постфиксную вида <tex>``abb.+.a."</tex> (<tex>.</tex> используется в качестве разделителя). По мере сканирования постфиксного выражения, будем поддерживать стек вычисленных НКА фрагментов. Символы добавляют новый НКА фрагмент в стек, а операторы вынимают фрагменты и добавляют новые. Каждый фрагмент определяется стартовым состояние и исходящей стрелкой:
'''struct''' frag:
== Несколько полезных оптимизаций на примере Haskell ==
Gabriel Gonzalez <ref>[https://begriffs.com/posts/2016-06-27-fast-haskell-regexes.html Gabriel Gonzalez{{---}} Regex in Haskell] </ref> реализовал алгоритм Томпсона на языке Haskell. В первоначальном варианте это алгоритм получился в <tex>480 </tex> раз медленнее, чем grep на том же тесте, чтобы улучшить результат он предпринял ряд оптимизаций:* вместо <tex>\mathrm{Set Int }</tex> использовал <tex>\mathrm{Integer}</tex>, а также использовал битовые операции, в результате производительность выросла в <tex>5 </tex> раз* использовал <tex>\mathrm{Word }</tex> вместо <tex>\mathrm{Integer}</tex>, ещё в <tex>8 </tex> раз быстрее* а также использовал <tex>\mathrm{ByteString }</tex> оптимизации, что увеличило производительность ещё <tex>3 </tex> раза.В итоге его реализация оказалась всего в <tex>4 </tex> раза медленнее grep. Но это не предел, у него получилось реализовать параллельный конечный автомат<ref>[https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/asplos302-mytkowicz.pdf параллельный конечный автоматData-Parallel Finite-State Machines] </ref> и сделать свою реализацию в <tex>1.5 </tex> раза быстрее, чем grep.
== ReDoS (regular expression denial of service) ==
Все эти выражения чувствительны к входной строке <tex>aaaaaaaaaaaaaaaaaaaaaaaaaa</tex>.
Также вредоносные регулярные выражения были обнаружены в онлайн репозиториях.
# RegExLib, email validation <ref>[http://regexlib.com/REDetails.aspx?regexp_id=1757 RegExLib, id=1757 (RegEx for email validation)] </ref> {{--- }} '''выделенная''' часть является вредоносной<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># OWASP Validation Regex Repository <ref>[http://www.owasp.org/index.php/OWASP_Validation_Regex_Repository OWASP Validation Regex Repository]</ref>, Java Classname {{- --}} '''выделенная''' часть является вредоносной<br /><code>^'''(([a-z])+.)+'''[A-Z]([a-z])+$</code>
Эти два примера также чувствительны к входной строке <tex>aaaaaaaaaaaaaaaaaaaaaaaa</tex>.
* [[ Детерминированные конечные автоматы ]]
* [[ Построение по НКА эквивалентного ДКА, алгоритм Томпсона ]]
== Примечания ==
<references/>
== Источники информации ==
