Преди почти 9 години Cloudflare беше малка компания и аз не работех за нея, бях просто клиент. Месец след стартирането на Cloudflare получих сигнал, че на моя сайт изглежда не работи DNS. Cloudflare направи промяна в , и имаше повреден DNS.
Веднага изпратих имейл до Матю Принс със заглавие „Къде е моят 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|-|~|!|{}||||+)*.*(?:.*=.*)))
Въпреки че е интересно само по себе си (и ще го разгледам по-подробно по-долу), 27-минутното затъмнение на Cloudflare не се дължи само на лош регулярен израз. Отне ни известно време да опишем последователността от събития, довели до катастрофата, така че не реагирахме бързо. В края на публикацията ще опиша обратно проследяване в регулярен израз и ще ви кажа какво да правите с него.
Какво стана
Да започнем по ред. Всички времена тук са в UTC.
В 13:42 инженер от екипа на защитната стена направи малка промяна в правилата за откриване чрез автоматичен процес. Съответно беше създаден билет за заявка за промяна. Ние управляваме такива билети чрез Jira (екранна снимка по-долу).
След 3 минути се появи първата страница на PagerDuty, съобщаваща за проблем с WAF. Това беше синтетичен бенчмарк, който тества функционалността на WAF (имаме стотици от тях) извън Cloudflare, за да провери за нормална работа. Това беше последвано незабавно от страници с неуспехи на други тестове от край до край на услугите на Cloudflare, глобални проблеми с трафика, широко разпространени грешки 502 и куп доклади от нашите точки на присъствие (PoP) в градове по света, които показват недостиг на ресурсите на процесора.
Получих няколко от тези сигнали, изхвърчах от срещата и бях на път към масата, когато нашият ръководител на разработката на решения каза, че сме загубили 80% от трафика си. Изтичах до нашите SRE инженери, които вече работеха по проблема. Първоначално помислихме, че е някаква неизвестна атака.
Инженерите на Cloudflare SRE са разпръснати по света и наблюдават ситуацията денонощно. Обикновено тези сигнали уведомяват за специфични локални проблеми с ограничен обхват, проследяват се на вътрешни табла за управление и се разрешават много пъти на ден. Но такива страници и известия сочеха нещо наистина сериозно и инженерите на SRE незабавно обявиха ниво на сериозност P0 и се обърнаха към инженерите по управление и системи.
Нашите лондонски инженери в този момент слушаха лекция в главната зала. Наложи се лекцията да бъде прекъсната, всички се събраха в голяма конферентна зала и бяха извикани още специалисти. Това не е често срещан проблем, с който SRE могат да се справят сами. Беше необходимо спешно да се свържат правилните специалисти.
В 14:00 часа установихме, че има проблем с WAF и няма атака. Отделът за производителност извлече данните за процесора и стана очевидно, че WAF е виновен. Друг служител потвърди тази теория със strace. Някой друг видя в регистрационните файлове, че има проблем с WAF. В 14:02 целият екип дойде при мен, когато беше предложено да се използва глобално убиване - механизъм, вграден в Cloudflare, който деактивира един компонент в световен мащаб.
Как направихме глобално убийство за 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 PoP е Cloudflare PoP (както всеки друг наш град), който използват само служители на Cloudflare. PoP за вътрешна употреба ви позволява да улавяте проблеми дори преди клиентският трафик да започне да влиза в решението. Полезно нещо.
Ако тестът DOG премине, кодът преминава към етап PIG (морско свинче). Това е Cloudflare PoP, където малко количество безплатен клиентски трафик преминава през новия код.
Ако всичко е наред, кодът отива в Canary. Имаме три Canary PoP точки в различни части на света. При тях трафикът на платени и безплатни клиенти минава през новия код, като това е последната проверка за грешки.
Процес на пускане на софтуер в Cloudflare
Ако кодът е наред в 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, която управлява внедряването и връщането назад, и внедряването беше завършено .
Процес на внедряване на Cloudflare WAF
Нещо се обърка
Както казах преди, ние въвеждаме десетки нови правила на WAF всяка седмица и разполагаме с много системи за защита срещу отрицателните ефекти от подобно внедряване. И когато нещо се обърка, обикновено това е комбинация от няколко обстоятелства едновременно. Ако намерите само една причина, това, разбира се, е успокояващо, но не винаги е вярно. Ето причините, които заедно причиниха нашата HTTP/HTTPS услуга да се провали.
- Инженер е написал регулярен израз, който може да доведе до прекомерно .
- Функция, която би могла да попречи на регулярния израз да претоварва CPU, беше погрешно премахната по време на рефакторинга на WAF няколко седмици по-рано - рефакторингът беше необходим, за да накара WAF да консумира по-малко ресурси.
- Механизмът за регулярен израз нямаше гаранции за сложност.
- Тестовият пакет не можа да открие прекомерно използване на процесора.
- SOP позволява неспешни промени в правилата да бъдат внедрявани глобално без многоетапен процес.
- Планът за връщане изисква пълно изграждане на WAF два пъти, което е дълго време.
- Първият глобален сигнал за проблем с трафика дойде твърде късно.
- Бавно актуализирахме страницата за състоянието.
- Имахме проблеми с достъпа до системите поради повреда и процедурата за байпас не беше добре практикувана.
- SRE са загубили достъп до някои системи, защото идентификационните им данни са изтекли от съображения за сигурност.
- Нашите клиенти нямаха достъп до таблото за управление или API на Cloudflare, защото преминават през региона на Cloudflare.
Какво се промени от миналия четвъртък
Първо, напълно спряхме цялата работа по версиите за WAF и направихме следното:
- Повторно въвеждане на защитата срещу прекомерна консумация на процесорни ресурси, която премахнахме. (Готов)
- Ръчна проверка на всички 3868 правила в управляваните правила на WAF за намиране и коригиране на други потенциални случаи на прекомерно обратно проследяване. (Потвърждението е завършено)
- Включете профилиране на производителността за всички правила в тестовия пакет. (Очаква се: 19 юли)
- Преминаване към механизма за регулярен израз или И двете предоставят гаранции в средата на изпълнение. (Очаква се: 31 юли)
- Пренаписване на SOP за внедряване на правила на етапи, като друг софтуер в Cloudflare, но все пак възможност за внедряване на спешни случаи глобално, ако атаките вече са започнали.
- Ние разработваме възможност за спешно изтегляне на таблото за управление и API на Cloudflare от региона на 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 г., когато Кент Томпсън написа статия („Методи на програмиране: Алгоритъм за търсене с регулярен израз“). Статията описва механизъм, който ви позволява да конвертирате регулярен израз в недетерминирани крайни автомати и след промени в състоянието на недетерминирани крайни автомати, да използвате алгоритъм, чието време за изпълнение зависи линейно от съвпадащия низ.
Методи за програмиране
Алгоритъм за търсене на регулярен израз
Кен Томпсън
Bell Telephone Laboratories, Inc., Murray Hill, NJТук се описва метод за търсене на конкретен низ от знаци в текст и се обсъжда прилагането на този метод във формата на компилатор. Компилаторът приема регулярния израз като изходен код и генерира програмата 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.
Този алгоритъм зависи линейно от размера на входния низ.
Източник: www.habr.com