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

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

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

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

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

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

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

А он ответил:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Quicksilver

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

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

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

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

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

До развертывания правил все шло гладко: пул-реквест был создан и одобрен, пайплайн 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.

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

Заключение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

В этом видео показан весь бэктрекинг для сопоставления 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 является конечным. Если мы его достигли, значит регулярное выражение сопоставлено.

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

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

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

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

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

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

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

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

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

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

Источник: habr.com