Хабрахабр

[Перевод] Подробности сбоя в Cloudflare 2 июля 2019 года

Через месяц после запуска Cloudflare я получил оповещение о том, что на моем сайтике jgc.org, похоже, не работает DNS. Почти 9 лет назад Cloudflare была крошечной компанией, а я не работал в ней, был просто клиентом. В Cloudflare внесли изменение в Protocol Buffers, а там был поломанный DNS.

Я сразу написал Мэтью Принсу (Matthew Prince), озаглавив письмо «Где мой DNS?», а он прислал длинный ответ, полный технических подробностей (всю переписку читайте здесь), на что я ответил:

От: Джон Грэхэм-Камминг
Дата: 7 октября 2010 года, 9:14
Тема: Re: Где мой DNS?
Кому: Мэтью Принс

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

Мониторинг показывает, что сбой был с 13:03:07 до 14:04:12. У меня на сайте хороший мониторинг, и мне приходит SMS о каждом сбое. Тесты проводятся каждые пять минут.

Вам точно не нужен свой человек в Европе? Уверен, вы со всем разберетесь. 🙂

А он ответил:

От: Мэтью Принс
Дата: 7 октября 2010 года, 9:57
Тема: Re: Где мой DNS?
Кому: Джон Грэхэм-Камминг

Мы ответили всем, кто написал. Спасибо. Полностью согласен, честность — наше все. Я сейчас еду в офис, и мы напишем что-нибудь в блоге или закрепим официальный пост на нашей доске объявлений.

Сейчас Cloudflare — реально большая компания, я работаю в ней, и теперь мне приходится открыто писать о нашей ошибке, ее последствиях и наших действиях.

События 2 июля

Мы постоянно улучшаем управляемые правила для WAF в ответ на новые уязвимости и угрозы. 2 июля мы развернули новое правило в управляемых правилах для WAF, из-за которых процессорные ресурсы заканчивались на каждом ядре процессора, обрабатывающем трафик HTTP/HTTPS в сети Cloudflare по всему миру. Вся суть нашего WAF — в возможности быстрого и глобального развертывания правил. В мае, например, мы поспешили добавить правило, чтобы защититься от серьезной уязвимости в SharePoint.

От этого пострадали наши основные функции прокси, CDN и WAF. К сожалению, обновление прошлого четверга содержало регулярное выражение, которое тратило на бэктрекинг слишком много процессорных ресурсов, выделенных для HTTP/HTTPS. На графике видно, что процессорные ресурсы для обслуживания трафика HTTP/HTTPS доходят почти до 100% на серверах в нашей сети.


Использование процессорных ресурсов в одной из точек присутствия во время инцидента

Ошибки 502 генерировались фронтальными веб-серверами Cloudflare, у которых еще были свободные ядра, но они не могли связаться с процессами, обрабатывающими трафик HTTP/HTTPS. В итоге наши клиенты (и клиенты наших клиентов) упирались в страницу с ошибкой 502 в доменах Cloudflare.

Нам ужасно стыдно. Мы знаем, сколько неудобств это доставило нашим клиентам. И этот сбой мешал нам эффективно разобраться с инцидентом.

Более того, у нас уже 6 лет не было глобальных сбоев. Если вы были одним из таких клиентов, вас это, наверное, напугало, рассердило и расстроило. Вот виновное выражение: (?:(?:\"|'|\]|\}|\\|\d|(?:nan|infinity|true|false|null|undefined|symbol|math)|\`|\-|\+)+[)]*;?((?:\s|-|~|! Высокий расход процессорных ресурсов произошел из-за одного правила WAF с плохо сформулированным регулярным выражением, которое привело к чрезмерному бэктрекингу. ||\|\||\+)*.*(?:.*=.*)))

Нам понадобилось время, чтобы описать последовательность событий, которые привели к сбою, поэтому ответили мы небыстро. Хотя оно само по себе интересное (и ниже я расскажу о нем подробнее), сервис Cloudflare отрубился на 27 минут не только из-за негодного регулярного выражения. В конце поста я опишу бэктрекинг в регулярном выражении и расскажу, что с этим делать.

Что случилось

Все время здесь указано в UTC. Начнем по порядку.

Соответственно, был создан тикет запроса на изменение. В 13:42 инженер из команды, занимающейся межсетевыми экранами, внес небольшие изменение в правила для обнаружения XSS с помощью автоматического процесса. Такими тикетами мы управляем через Jira (скриншот ниже).

Это был синтетический тест, который проверяет функциональность WAF (у нас таких сотни) за пределами Cloudflare, чтобы контролировать нормальную работу. Через 3 минуты появилась первая страница PagerDuty, сообщавшая о проблеме с WAF. Затем сразу последовали страницы с оповещениями о сбоях других сквозных тестов сервисов Cloudflare, глобальных проблемах с трафиком, повсеместных ошибках 502, и куча отчетов из наших точек присутствия (PoP) в городах по всему миру, которые указывали на нехватку процессорных ресурсов.

Я побежал к нашим SRE-инженерам, который уже работали над проблемой. Я получил несколько таких оповещений, сорвался со встречи и уже шел к столу, когда руководитель нашего отдела разработки решений сказал, что мы потеряли 80% трафика. Сначала мы подумали, что это какая-то неизвестная атака.

Обычно такие оповещения уведомляют о конкретных локальных проблемах ограниченного масштаба, отслеживаются на внутренних панелях мониторинга и решаются много раз за день. SRE-инженеры Cloudflare разбросаны по всему миру и контролируют ситуацию круглосуточно. Но такие страницы и уведомления указывали на что-то реально серьезное, и SRE-инженеры сразу объявили уровень серьезности P0 и обратились к руководству и системным инженерам.

Лекцию пришлось прервать, все собрались в большом конференц-зале, позвали еще специалистов. Наши лондонские инженеры в этот момент слушали лекцию в главном зале. Нужно было срочно подключать правильных спецов. Это не была обычная проблема, с которой SRE могли разобраться сами.

Отдел производительности извлек данные о процессорах, и стало очевидно, что виноват WAF. В 14:00 мы определили, что проблема с WAF и никакой атаки нет. Еще кто-то увидел в логах, что с WAF беда. Другой сотрудник подтвердил эту теорию с помощью strace. В 14:02 вся команда явилась ко мне, когда было предложено использовать global kill — механизм, встроенный в Cloudflare, который отключает один компонент по всему миру.

Все не так просто. Как мы сделали global kill для WAF — это отдельная история. Мы используем собственные продукты, а раз наш сервис Access не работал, мы не могли пройти аутентификацию и войти в панель внутреннего контроля (когда все починилось, мы узнали, что некоторые члены команды потеряли доступ из-за функции безопасности, которая отключает учетные данные, если долго не использовать панель внутреннего контроля).

Нужен был обходной механизм, который мы использовали нечасто (это тоже нужно будет отработать). И мы не могли добраться до своих внутренних сервисов, вроде Jira или системы сборки. Остальные защитные механизмы Cloudflare работали в штатном режиме. Наконец, одному инженеру удалось отрубить WAF в 14:07, а в 14:09 уровень трафика и процессора везде вернулся в норму.

Ситуация была из ряда вон, поэтому мы выполнили негативные тесты (спросив себя, действительно ли проблема в этом изменении) и позитивные (убедившись, что откат сработал) в одном городе с помощью отдельного трафика, перенеся оттуда платных клиентов. Затем мы занялись восстановлением работы WAF.

В 14:52 мы убедились, что поняли причину и внесли исправление, и снова включили WAF.

Как работает Cloudflare

Они стараются повысить процент обнаружения, сократить количество ложноположительных результатов и быстро реагировать на новые угрозы по мере их появления. В Cloudflare есть команда инженеров, которые занимаются управляемыми правилами для WAF. За последние 60 дней было обработано 476 запросов на изменения для управляемых правил для WAF (в среднем, по одному каждые 3 часа).

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

SOP для изменения правила разрешает публиковать его глобально. Как видно из запроса на изменение выше, у нас есть план развертывания, план отката и ссылка на внутреннюю стандартную рабочую процедуру (SOP) для этого типа развертывания. Вообще-то в Cloudflare все устроено совсем иначе, и SOP предписывает сначала отправить ПО на тестирование и внутреннее использование во внутреннюю точку присутствия (PoP) (которую используют наши сотрудники), потом небольшому количеству клиентов в изолированном месте, потом большому числу клиентов и только потом всему миру.

Мы используем git во внутренней системе через BitBucket. Вот как это выглядит. Когда пул-реквест одобряется, код собирается и проводится ряд тестов (еще раз). Инженеры, работающие над изменениями, отправляют код, который собирается в TeamCity, и когда сборка проходит, назначаются ревьюеры.

После одобрения происходит развертывание в так называемый «PoP-зверинец»: DOG, PIG и Canary (собака, свинка и канарейка). Если сборка и тесты завершаются успешно, создается запрос на изменение в Jira, и изменение должен одобрить соответствующий руководитель или ведущий специалист.

PoP для внутреннего использования позволяет выловить проблемы еще до того, как в решение начнет поступать трафик клиентов. DOG PoP — это Cloudflare PoP (как любой другой из наших городов), который используют только сотрудники Cloudflare. Полезная штука.

Это Cloudflare PoP, где небольшой объем трафика бесплатных клиентов проходит через новый код.
Если все хорошо, код переходит в Canary. Если DOG-тест проходит успешно, код переходит на стадию PIG (подопытная свинка). В них через новый код проходит трафик платных и бесплатных клиентов, и это последняя проверка на ошибки. У нас три Canary PoP в разных точках мира.


Процесс релиза ПО в Cloudflare

Прохождение через все стадии — DOG, PIG, Canary, весь мир — занимает несколько часов или дней, в зависимости от изменения кода. Если с кодом все нормально в Canary, мы его выпускаем. Но WAF специально не следует этому процессу, потому что на угрозы нужно реагировать быстро. Благодаря многообразию сети и клиентов Cloudflare мы тщательно тестируем код перед глобальным релизом для всех клиентов.

Это связано с большей доступностью инструментов тестирования ПО. Угрозы WAF
В последние несколько лет в обычных приложениях угроз стало значительно больше. Например, недавно мы писали про фаззинг).


Источник: https://cvedetails.com/

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

Почти сразу после публикации объявлений мы заметили огромное количество попыток использовать уязвимость в установках SharePoint наших клиентов. Отличный пример быстрой реакции от Cloudflare — развертывание средств защиты от уязвимости SharePoint в мае (читайте здесь). Наши ребята постоянно отслеживают новые угрозы и пишут правила, чтобы защитить наших клиентов.

Таких атак тоже стало куда больше за последние годы. Правило, из-за которого в четверг возникла проблема, должно было защищать от межсайтового скриптинга (XSS).


Источник: https://cvedetails.com/

В прошлый четверг мы это сделали и развернули правила. Стандартная процедура для изменения управляемого правила для WAF предписывает проводить тестирование непрерывной интеграции (CI) до глобального развертывания. В 13:31 один инженер отправил одобренный пул-реквест с изменением.

Набор тестов для WAF проверяет основной функционал WAF и состоит из большого количества модульных тестов для индивидуальных функций. В 13:37 TeamCity собрал правила, прогнал тесты и дал добро. HTTP-запросы проверяют, какие запросы должны блокироваться WAF (чтобы перехватить атаку), а какие можно пропускать (чтобы не блокировать все подряд и избежать ложноположительных результатов). После модульных тестов мы проверили правила для WAF с помощью огромного числа HTTP-запросов. Но мы не провели тесты на чрезмерное использование процессорных ресурсов, и изучение логов предыдущих сборок WAF показывает, что время выполнения тестов с правилом не увеличилось, и сложно было заподозрить, что ресурсов не хватит.

Тесты были пройдены, и TeamCity начал автоматически развертывать изменение в 13:42.

Quicksilver

Все наши клиенты используют эту технологию, когда меняют конфигурацию на панели мониторинга или через API, и именно благодаря ей мы молниеносно реагируем на изменения. Правила WAF направлены на срочное устранение угроз, поэтому мы развертываем их с помощью распределенного хранилища пар «ключ-значение» Quicksilver, которое распространяет изменения глобально за считанные секунды.

Раньше мы использовали Kyoto Tycoon как глобально распределенное хранилище пар «ключ-значение», но с ним возникли операционные проблемы, и мы написали свое хранилище, реплицированное более чем в 180 городах. Мы мало говорили о Quicksilver. Теперь с помощью Quicksilver мы отправляем изменения в конфигурацию клиентов, обновляем правила WAF и распространяем код JavaScript, написанный клиентами в Cloudflare Workers.

Клиентам полюбилась эта скорость настройки. От нажатия кнопки на панели мониторинга или вызова API до внесения изменения в конфигурацию по всему миру проходит всего несколько секунд. В среднем Quicksilver распространяет около 350 изменений в секунду. А Workers обеспечивает им почти моментальное глобальное развертывание ПО.

В среднем мы достигли 99-го процентиля 2,29 с для распространения изменений на каждый компьютер по всему миру. И Quicksilver работает очень быстро. Ведь когда вы включаете функцию или чистите кэш, это происходит почти мгновенно и повсюду. Обычно скорость — это хорошо. Cloudflare обещает своим клиентам быстрые апдейты в нужный момент. Отправка кода через Cloudflare Workers происходит с той же скоростью.

Вы, наверное, заметили, что код WAF использует Lua. Но в этом случае скорость сыграла с нами злую шутку, и правила изменились повсеместно за считанные секунды. Lua WAF использует PCRE внутри и применяет бэктрекинг для сопоставления. Cloudflare широко использует Lua в рабочей среде и подробности Lua в WAF мы уже обсуждали. Ниже я подробнее расскажу об этом и о том, что мы с этим делаем. У него нет механизмов защиты от выражений, вышедших из-под контроля.

До развертывания правил все шло гладко: пул-реквест был создан и одобрен, пайплайн CI/CD собрал и протестировал код, запрос на изменение был отправлен в соответствии с SOP, которая регулирует развертывание и откат, и развертывание было выполнено.


Процесс развертывания WAF в Cloudflare

И когда что-то идет не так, обычно это стечение сразу нескольких обстоятельств. Что пошло не так
Как я уже говорил, мы каждую неделю развертываем десятки новых правил WAF, и у нас есть множество систем защиты от негативных последствий такого развертывания. Вот причины, которые вместе привели к сбою нашего сервиса HTTP/HTTPS. Если найти всего одну причину, это, конечно успокаивает, но не всегда соответствует действительности.

  1. Инженер написал регулярное выражение, которое может привести к чрезмерному бэктрекингу.
  2. Средство, которое могло бы предотвратить чрезмерный расход процессорных ресурсов, используемых регулярным выражением, было по ошибке удалено при рефакторинге WAF за несколько недель до этого — рефакторинг был нужен, чтобы WAF потреблял меньше ресурсов.
  3. Движок регулярных выражений не имел гарантий сложности.
  4. Набор тестов не мог выявить чрезмерное потребление процессорных ресурсов.
  5. Процедура SOP разрешает глобальное развертывание несрочных изменений правил без многоэтапного процесса.
  6. План отката требовал выполнение полной сборки WAF дважды, а это долго.
  7. Первое оповещение о глобальных проблемах с трафиком сработало слишком поздно.
  8. Мы промедлили с обновлением страницы статуса.
  9. У нас были проблемы с доступом к системам из-за сбоя, а процедура обхода была недостаточно хорошо отработана.
  10. SRE-инженеры потеряли доступ к некоторым системам, потому что срок действия их учетных данных истек по соображениям безопасности.
  11. У наших клиентов не было доступа к панели мониторинга Cloudflare или API, потому что они проходят через регион Cloudflare.

Что изменилось с прошлого четверга

Сначала мы полностью остановили все работы над релизами для WAF и делаем следующее:

  1. Повторно вводим защиту от чрезмерного потребления процессорных ресурсов, которую мы удалили. (Готово)
  2. Вручную проверяем все 3868 правил в управляемых правилах для WAF, чтобы найти и исправить другие потенциальные случаи чрезмерного бэктрекинга. (Проверка завершена)
  3. Включаем в набор тестов профилирование производительности для всех правил. (Ожидается: 19 июля)
  4. Переходим на движок регулярных выражений re2 или Rust — оба предоставляют гарантии в среде выполнения. (Ожидается: 31 июля)
  5. Переписываем SOP, чтобы развертывать правила поэтапно, как и другое ПО в Cloudflare, но при этом иметь возможность экстренного глобального развертывания, если атаки уже начались.
  6. Разрабатываем возможность срочного вывода панели мониторинга Cloudflare и API из региона Cloudflare.
  7. Автоматизируем обновление страницы Cloudflare Status.

Переносим WAF в новую систему межсетевых экранов. В долгосрочной перспективе мы отказываемся от Lua WAF, который я написал несколько лет назад. Так WAF будет быстрее и получит дополнительный уровень защиты.

Заключение

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

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

Приложение. Бэктрекинг регулярных выражений

Чтобы понять, как выражение:

(?:(?:\"|'|\]|\}|\\|\d
(?:nan|infinity|true|false|null|undefined|symbol|math)|\`|\-
|\+)+[)]*;?((?:\s|-|~|!|{}|\|\||\+)*.*(?:.*=.*)))

Проблема тут в паттерне .*(?:.*=.*). съело все процессорные ресурсы, нужно немного знать о том, как работает стандартный движок регулярных выражений. (?: и соответствующая ) — это не захватывающая группа (то есть выражение в скобках группируется как одно выражение).

В таком виде паттерн выглядит излишне сложным. В контексте чрезмерного потребления процессорных ресурсов можно обозначить этот паттерн как .*.*=.*. И вот почему. Но что важнее, в реальном мире такие выражения (подобные сложным выражениям в правилах WAF), которые просят движок сопоставить фрагмент, за которым следует другой фрагмент, могут привести к катастрофическому бэктрекингу.

В регулярном выражении . означает, что нужно сопоставить один символ, .* — сопоставить ноль или более символов «жадно», то есть захватив максимум символов, так что .*.*=.* означает сопоставить ноль или более символов, потом сопоставить ноль или более символов, найти литеральный символ =, сопоставить ноль или более символов.

Она соответствует выражению .*.*=.*. Возьмем тестовую строку x=x. .* после = соответствует последнему x. .*.* до знака равенства соответствует первому x (одна из групп .* соответствует x, а вторая — нулю символов).

Первая группа .* в .*.*=.* действует «жадно» и сопоставляется всей строке x=x. Для такого сопоставления нужно 23 шага. У нас больше нет символов для сопоставления, поэтому вторая группа .* соответствует нулю символов (это допускается). Движок переходит к следующей группе .*. Символов больше нет (первая группа .* использовала все выражение x=x), сопоставление не происходит. Потом движок переходит к знаку =.

Он переходит к первой группе .* и сопоставляет ее с x= (вместо x=x), а затем берется за вторую группу .*. И тут движок регулярных выражений возвращается к началу. И когда движок опять доходит до = в .*.*=.*, ничего не получается. Вторая группа .* сопоставляется со вторым x, и у нас снова не осталось символов. И он снова делает бэктрекинг.

Движок пытается найти литеральный символ = в паттерне .*.*=.*, но не выходит (ведь его уже заняла первая группа .*). На этот раз группа .* все еще соответствует x=, но вторая группа .* больше не x, а ноль символов. И он снова делает бэктрекинг.

Но вторая группа .* «жадно» захватывает =x. На этот раз первая группа .* берет только первый x. Движок пытается сопоставить литеральное =, терпит неудачу и делает очередной бэктрекинг. Уже догадались, что будет?

Вторая .* занимает только =. Первая группа .* все еще соответствует первому x. И опять бэктрекинг. Разумеется, движок не может сопоставить литеральное =, ведь это уже сделала вторая группа .*. И это мы пытаемся сопоставить строку из трех символов!

Дальше последняя группа .* сопоставляется с последним x. В итоге первая группа .* сопоставляется только с первым x, вторая .* — с нулем символов, и движок наконец сопоставляет литеральное = в выражении с = в строке.

Посмотрите короткое видео об использовании Perl Regexp::Debugger, где показано, как происходят шаги и бэктрекинг. 23 шага только для x=x.

Это 33 шага. Это уже немало работы, но что если вместо x=x у нас будет x=xx? 45. А если x=xxx? На графике показано сопоставление от x=x до x=xxxxxxxxxxxxxxxxxxxx (20 x после =). Зависимость не линейная. (Мало того, если у нас потерялся x= и строка состоит просто из 20 x, движок сделает 4067 шагов, чтобы понять, что совпадений нет). Если у нас 20 x после =, движок выполняет сопоставление за 555 шагов!

В этом видео показан весь бэктрекинг для сопоставления x=xxxxxxxxxxxxxxxxxxxx:

Но все может быть еще хуже, если регулярное выражение немного изменить. Беда в том, что при увеличении размера строки время сопоставления растет сверхлинейно. Например, для сопоставления с таким выражением, как foo=bar;. Допустим, у нас было бы .*.*=.*; (то есть в конце паттерна была литеральная точка с запятой).

Для сопоставления x=x понадобится 90 шагов, а не 23. И здесь бэктрекинг стал бы настоящей катастрофой. Чтобы сопоставить x= и 20 x, нужно 5353 шага. И это число быстро растет. Посмотрите на значения по оси Y по сравнению с предыдущим графиком. Вот график.

Если интересно, посмотрите все 5353 шага неудачного сопоставления x=xxxxxxxxxxxxxxxxxxxx и .*.*=.*;

Если изменить оригинальное выражение на .*?.*?=.*?, для сопоставления x=x понадобится 11 шагов (а не 23). Если использовать «ленивые», а не «жадные» сопоставления, масштаб бэктрекинга можно контролировать. Все потому, что ? после .* велит движку сопоставить минимальное число символов, прежде чем идти дальше. Как и для x=xxxxxxxxxxxxxxxxxxxx.

Если заменить катастрофический пример .*.*=.*; на .*?.*?=.*?;, время выполнения останется прежним. Но «ленивые» сопоставления не решают проблему бэктрекинга полностью. x=x все равно требует 555 шагов, а x= и 20 x — 5353.

Этим мы и займемся в следующие несколько недель. Единственное, что можно сделать (кроме полного переписывания паттерна для большей конкретики) — отказаться от движка регулярных выражений с его механизмом бэктрекинга.

В статье описан механизм, которые позволяет преобразовать регулярное выражение в недетерминированные конечные автоматы, а после изменений состояния в недетерминированных конечных автоматах использовать алгоритм, время выполнения которого линейно зависит от сопоставляемой строки. Решение этой проблемы известно еще с 1968 года, когда Кент Томпсон написал статью Programming Techniques: Regular expression search algorithm («Методы программирования: алгоритм поиска регулярных выражений»).

Методы программирования
Алгоритм поиска регулярных выражений
Кен Томпсон (Ken Thompson)

Bell Telephone Laboratories, Inc., Мюррей-Хилл, штат Нью-Джерси

Компилятор принимает регулярное выражение в качестве исходного кода и создает программу для IBM 7094 в качестве объектного кода. Здесь описывается метод поиска определенной строки символов в тексте и обсуждается реализация этого метода в форме компилятора. В статье приводятся примеры, проблемы и решения. Объектная программа принимает входные данные в виде текста для поиска и подает сигнал каждый раз, когда строка из текста сопоставляется с заданным регулярным выражением.

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

Он передает инструкции в компилированный код. В режиме компиляции алгоритм работает не с символами. Разумеется, это далеко не единственное применение подобной процедуры поиска. Выполнение происходит очень быстро — после передачи данных в верхнюю часть текущего списка автоматически выполняется поиск всех возможных последовательных символов в регулярном выражении.
Алгоритм компиляции и поиска включен в текстовый редактор с разделением времени как контекстный поиск. Например, вариант этого алгоритма используется как поиск символов по таблице в ассемблере.
Предполагается, что читатель знаком с регулярными выражениями и языком программирования компьютера IBM 7094.

Первый этап — фильтрация по синтаксису, которая пропускает только синтаксически правильные регулярные выражения. Компилятор
Компилятор состоит из трех параллельно выполняющихся этапов. На втором этапе регулярное выражение преобразуется в постфиксную форму. На этом этапе также вставляется оператор «·» для сопоставления регулярных выражений. Первые 2 этапа очевидны, и мы не будем на них останавливаться. На третьем этапе создается объектный код.

Реализация мудреная, но сама идея очень простая. В статье Томпсона не говорится о недетерминированных конечных автоматах, но хорошо объяснен алгоритм линейного времени и представлена программа на ALGOL-60, которая создает код языка сборки для IBM 7094.

Он представлен значком ⊕ с одним входом и двумя выходами.
На рисунке 1 показаны функции третьего этапа компиляции при преобразовании примера регулярного выражения. текущий путь поиска. Первые три символа в примере — a, b, c, и каждый создает стековую запись S[i] и поле NNODE.

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

Вот как выглядело бы регулярное выражение .*.*=.*, если представить его, как на картинках из статьи Томпсона.

0 есть пять состояний, начиная с 0, и 3 цикла, которые начинаются с состояний 1, 2 и 3. На рис. 3 овала с точками соответствуют одному символу. Эти три цикла соответствуют трем .* в регулярном выражении. Состояние 4 является конечным. Овал со знаком = соответствует литеральному символу =. Если мы его достигли, значит регулярное выражение сопоставлено.

Программа начинается с состояния 0, как показано на рис. Чтобы увидеть, как такую диаграмму состояний можно использовать для сопоставления регулярного выражения .*.*=.*, мы рассмотрим сопоставление строки x=x. 1.

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

2. Еще не успев считать входные данные, он переходит в оба первых состояния (1 и 2), как показано на рис.

2 видно, что происходит, когда он рассматривает первый x в x=x. На рис. Или x может сопоставиться с точкой ниже, перейдя из состояния 2 и обратно в состояние 2. x может сопоставиться с верхней точкой, перейдя из состояния 1 и обратно в состояние 1.

Мы не можем достичь состояния 3 или 4, потому что нам нужен литеральный символ =. После сопоставления первого x в x=x мы по-прежнему в состояниях 1 и 2.

Как и x до этого, его можно сопоставить с любым из двух верхних циклов с переходом из состояния 1 и в состояние 1 или из состояния 2 в состояние 2, но при этом алгоритм может сопоставить литеральное = и перейти из состояние 2 в состояние 3 (и сразу 4). Затем алгоритм рассматривает = в x=x. 3. Это показано на рис.

Из состояний 1 и 2 те же переходы возможны обратно в состояния 1 и 2. Затем алгоритм переходит к последнему x в x=x. Из состояния 3 x может сопоставиться с точкой справа и перейти обратно в состояние 3.

Каждый символ обработан один раз, так что этот алгоритм линейно зависит от длины входной строки. На этом этапе каждый символ x=x рассмотрен, а раз мы достигли состояния 4, регулярное выражение соответствует этой строке. И никакого бэктрекинга.

Очевидно, что после достижения состояния 4 (когда алгоритм сопоставил x=) все регулярное выражение сопоставлено, и алгоритм может завершиться, вообще не рассматривая x.

Этот алгоритм линейно зависит от размера входной строки.

Теги
Показать больше

Похожие статьи

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»
Закрыть