Майже 9 років тому Cloudflare була крихітною компанією, а я не працював у ній, був просто клієнтом. Через місяць після запуску Cloudflare я отримав сповіщення про те, що на моєму веб-сайті , схоже, не працює DNS. У Cloudflare внесли зміну а там був поламаний 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 інженер із команди, що займається міжмережевими екранами, вніс невеликі зміни до правил виявлення за допомогою автоматичного процесу. Відповідно, було створено тикет запиту зміну. Такими тикетами ми керуємо через Jira (скриншот нижче).
Через три хвилини з'явилася перша сторінка PagerDuty, яка повідомляла про проблему з WAF. Це був синтетичний тест, який перевіряє функціональність WAF (у нас таких сотні) поза Cloudflare, щоб контролювати нормальну роботу. Потім відразу пішли сторінки з оповіщеннями про збої інших наскрізних тестів сервісів Cloudflare, глобальні проблеми з трафіком, повсюдні помилки 3, і купа звітів з наших точок присутності (PoP) у містах по всьому світу, які вказували на брак процесорних ресурсів.
Я отримав кілька таких сповіщень, зірвався із зустрічі і вже йшов до столу, коли керівник нашого відділу розробки рішень сказав, що ми втратили 80% трафіку. Я побіг до наших SRE-інженерів, котрі вже працювали над проблемою. Спочатку ми подумали, що це якась невідома атака.
SRE-інженери Cloudflare розкидані по всьому світу та контролюють ситуацію цілодобово. Зазвичай такі сповіщення повідомляють про конкретні локальні проблеми обмеженого масштабу, відстежуються на внутрішніх панелях моніторингу і вирішуються багато разів на день. Але такі сторінки та повідомлення вказували на щось реально серйозне, і SRE-інженери відразу оголосили рівень серйозності P0 та звернулися до керівництва та системних інженерів.
Наші лондонські інженери слухали лекцію в головному залі. Лекцію довелося перервати, усі зібралися у великій конференц-залі, покликали ще спеціалістів. Це була звичайна проблема, з якою SRE могли розібратися самі. Потрібно було терміново підключати правильних спеців.
О 14:00 ми визначили, що проблема з WAF і жодної атаки немає. Відділ продуктивності отримав дані про процесори, і стало очевидно, що винен WAF. Інший співробітник підтвердив цю теорію за допомогою strace. Ще хтось побачив у логах, що з WAF біда. О 14:02 вся команда прийшла до мене, коли було запропоновано використовувати global kill — механізм, вбудований у Cloudflare, який відключає один компонент у всьому світі.
Як ми зробили global kill для WAF – це окрема історія. Все не так просто. Ми використовуємо власні продукти, а якщо наш сервіс не працював, ми не могли пройти автентифікацію та увійти в панель внутрішнього контролю (коли все полагодилося, ми дізналися, що деякі члени команди втратили доступ через функцію безпеки, яка відключає облікові дані, якщо довго не використовувати панель внутрішнього контролю).
І ми не могли дістатися своїх внутрішніх сервісів, на зразок 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 і (собака, свинка та канарка).
DOG PoP – це Cloudflare PoP (як будь-яке інше з наших міст), яке використовують лише співробітники Cloudflare. PoP для внутрішнього використання дозволяє виловити проблеми ще до того, як у рішення почне надходити трафік клієнтів. Корисна штука.
Якщо DOG-тест проходить успішно, код переходить до стадії PIG (піддослідна свинка). Це Cloudflare PoP, де невеликий обсяг трафіку безкоштовних клієнтів проходить через новий код.
Якщо все добре, код переходить до Canary. У нас три Canary PoP у різних точках світу. У них через новий код відбувається трафік платних і безкоштовних клієнтів, і це остання перевірка на помилки.
Процес релізу програмного забезпечення в Cloudflare
Якщо з кодом все нормально у Canary, ми його випускаємо. Проходження через всі стадії - DOG, PIG, Canary, весь світ - займає кілька годин або днів, залежно від зміни коду. Завдяки різноманітності мережі та клієнтів Cloudflare ми ретельно тестуємо код перед глобальним релізом для всіх клієнтів. Але WAF спеціально не дотримується цього процесу, тому що на погрози потрібно реагувати швидко.
Погрози WAF
Останні кілька років у звичайних додатках загроз стало значно більше. Це з більшою доступністю інструментів тестування ПЗ. Наприклад, нещодавно ми писали про ).
Джерело:
Дуже часто підтвердження концепції створюється і відразу публікується на Github, щоб команди, які обслуговують додаток, могли швидко протестувати його і переконатися, що він адекватно захищений. Тому Cloudflare потрібна можливість якнайшвидше реагувати на нові атаки, щоб у клієнтів була можливість виправити своє програмне забезпечення.
Відмінний приклад швидкої реакції від Cloudflare – розгортання засобів захисту від уразливості SharePoint у травні (). Майже відразу після публікації об'яв ми помітили величезну кількість спроб використовувати вразливість в установках SharePoint наших клієнтів. Наші хлопці постійно відстежують нові загрози та пишуть правила, щоб захистити наших клієнтів.
Правило, через яке у четвер виникла проблема, мало захищати від міжсайтового скриптингу (XSS). Таких атак теж стало значно більше за останні роки.
Джерело:
Стандартна процедура зміни керованого правила для WAF наказує проводити тестування безперервної інтеграції (CI) до глобального розгортання. Минулого четверга ми це зробили та розгорнули правила. О 13:31 один інженер відправив схвалений пул-реквест із зміною.
О 13:37 TeamCity зібрав правила, прогнав тести та дав добро. Набір тестів WAF перевіряє основний функціонал WAF і складається з великої кількості модульних тестів для індивідуальних функцій. Після модульних тестів ми перевірили правила для WAF за допомогою величезної кількості запитів HTTP. HTTP-запити перевіряють, які запити повинні блокуватися WAF (щоб перехопити атаку), а які можна пропускати (щоб не блокувати все поспіль і уникнути хибнопозитивних результатів). Але ми не провели тести на надмірне використання процесорних ресурсів, і вивчення логів попередніх збірок WAF показує, що час виконання тестів із правилом не збільшився, і важко було запідозрити, що ресурсів не вистачить.
Тести були пройдені, і TeamCity почав автоматично розгортати зміну о 13:42.
Ртуть
Правила WAF спрямовані на термінове усунення загроз, тому ми розгортаємо їх за допомогою розподіленого сховища пар «ключ-значення» Quicksilver, яке розповсюджує зміни глобально за лічені секунди. Всі наші клієнти використовують цю технологію, коли змінюють конфігурацію на панелі моніторингу або через API, і завдяки ній ми блискавично реагуємо на зміни.
Ми мало говорили про Quicksilver. Раніше ми використовували як глобально розподілене сховище пар «ключ-значення», але з ним виникли операційні проблеми, і ми написали своє сховище репліковане більш ніж у 180 містах. Тепер за допомогою Quicksilver ми відправляємо зміни до конфігурації клієнтів, оновлюємо правила WAF та розповсюджуємо код JavaScript, написаний клієнтами у Cloudflare Workers.
Від натискання кнопки на панелі моніторингу або виклику API до зміни в конфігурацію по всьому світу проходить всього кілька секунд. Клієнтам сподобалася ця швидкість налаштування. А Workers забезпечує їм майже миттєве глобальне розгортання програмного забезпечення. У середньому Quicksilver поширює близько 350 змін на секунду.
І Quicksilver працює дуже швидко. У середньому ми досягли 99-го відсотка 2,29 с для поширення змін на кожен комп'ютер по всьому світу. Зазвичай швидкість це добре. Адже коли ви включаєте функцію чи чистите кеш, це відбувається майже миттєво та всюди. Надсилання коду через Cloudflare Workers відбувається з тією ж швидкістю. Cloudflare обіцяє своїм клієнтам швидкі апдейти у потрібний момент.
Але в цьому випадку швидкість зіграла з нами злий жарт, і правила змінилися повсюдно за лічені секунди. Ви, мабуть, помітили, що код WAF використовує Lua. Cloudflare широко використовує Lua в робочому середовищі та подробиці ми . Lua WAF використовує всередині та застосовує бектрекінг для зіставлення. Він не має механізмів захисту від виразів, що вийшли з-під контролю. Нижче я докладніше розповім про це та про те, що ми з цим робимо.
До розгортання правил все йшло гладко: пул-реквест був створений і схвалений, пайплайн CI/CD зібрав та протестував код, запит на зміну було відправлено відповідно до SOP, яка регулює розгортання та відкат, та розгортання було виконано.
Процес розгортання WAF у Cloudflare
Що пішло не так
Як я вже казав, ми щотижня розгортаємо десятки нових правил WAF, і ми маємо безліч систем захисту від негативних наслідків такого розгортання. І коли щось іде не так, зазвичай це збіг одразу кількох обставин. Якщо знайти лише одну причину, це, звичайно, заспокоює, але не завжди відповідає дійсності. Ось причини, які привели до збою нашого сервісу HTTP/HTTPS.
- Інженер написав регулярний вираз, який може призвести до надмірного .
- Засіб, який міг би запобігти надмірній витраті процесорних ресурсів, що використовуються регулярним виразом, було помилково видалено при рефакторингу WAF за кілька тижнів до цього - рефакторинг був потрібен, щоб WAF споживав менше ресурсів.
- Двигун регулярних виразів у відсутності гарантій складності.
- Набір тестів було виявити надмірне споживання процесорних ресурсів.
- Процедура SOP дозволяє глобальне розгортання несрочних змін правил без багатоетапного процесу.
- План відкату вимагав виконання повного складання WAF двічі, а це довго.
- Перше сповіщення про глобальні проблеми з трафіком спрацювало надто пізно.
- Ми зволікали з оновленням сторінки статусу.
- Ми мали проблеми з доступом до систем через збій, а процедура обходу була недостатньо добре відпрацьована.
- SRE-інженери втратили доступ до деяких систем, тому що термін дії їх облікових даних закінчився з міркувань безпеки.
- Наші клієнти не мали доступу до панелі моніторингу Cloudflare або API, тому що вони проходять через регіон Cloudflare.
Що змінилося з минулого четверга
Спочатку ми повністю зупинили всі роботи над релізами для WAF та робимо таке:
- Повторно запроваджуємо захист від надмірного споживання процесорних ресурсів, який ми видалили. (Готово)
- Вручну перевіряємо всі 3868 правил у керованих правилах для WAF, щоб знайти та виправити інші потенційні випадки надмірного бектрекінгу. (Перевірка завершена)
- Включаємо в набір тестів профіль продуктивності для всіх правил. (Очікується: 19 липня)
- Переходимо на двигун регулярних виразів або — обидва надають гарантії у середовищі виконання. (Очікується: 31 липня)
- Переписуємо SOP, щоб розгортати правила поетапно, як і інше програмне забезпечення в Cloudflare, але при цьому мати можливість екстреного глобального розгортання, якщо атаки вже почалися.
- Розробляємо можливість термінового виведення панелі моніторингу Cloudflare та API із регіону Cloudflare.
- Автоматизуємо оновлення сторінки .
У довгостроковій перспективі ми відмовляємось від 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 , де показано, як відбуваються кроки та бектрекінг.
Це вже чимало роботи, але якщо замість 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 року, коли Кент Томпсон написав статтю («Методи програмування: алгоритм пошуку регулярних виразів»). У статті описаний механізм, який дозволяє перетворити регулярне вираження в недетерміновані кінцеві автомати, а після змін стану в недетермінованих кінцевих автоматах використовувати алгоритм, час виконання якого лінійно залежить від рядка, що зіставляється.
Методи програмування
Алгоритм пошуку регулярних виразів
Кен Томпсон (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