Пред речиси 9 години Cloudflare беше мала компанија и јас не работев за неа, бев само клиент. Еден месец по лансирањето на Cloudflare, добив известување дека мојата веб-страница Изгледа дека DNS не работи. Cloudflare направи промена во , и имаше скршен DNS.
Веднаш му пишав на Метју Принс со наслов „Каде е мојот DNS?“ и тој ми испрати долг одговор полн со технички детали (), на што јас одговорив:
Од: Џон Греам-Каминг
Датум: 7 октомври 2010 година, 9:14 часот
Тема: Одг: Каде е мојот DNS?
До: Метју ПринсПрекрасен извештај, благодарам. Дефинитивно ќе се јавам ако има проблеми. Веројатно вреди да се напише објава за ова откако ќе ги соберете сите технички информации. Мислам дека луѓето ќе уживаат во отворена и искрена приказна. Особено ако прикачите графикони за да покажете како сообраќајот пораснал од лансирањето.
Имам добар мониторинг на мојот сајт и добивам СМС за секој неуспех. Набљудувањето покажува дека дефектот се случил од 13:03:07 до 14:04:12 часот. Тестовите се прават на секои пет минути.
Сигурен сум дека ќе сфатиш. Дали сте сигурни дека не ви треба сопствена личност во Европа? 🙂
И тој одговори:
Од: Метју Принс
Датум: 7 октомври 2010 година, 9:57 часот
Тема: Одг: Каде е мојот DNS?
До: Џон Греам-КамингВи благодарам. Одговоривме на сите што пишуваа. Сега сум на пат кон канцеларијата и ќе напишеме нешто на блогот или ќе закачиме официјален пост на нашата огласна табла. Потполно се согласувам, искреноста е се.
Сега Cloudflare е навистина голема компанија, јас работам за неа и сега морам отворено да пишувам за нашата грешка, нејзините последици и нашите постапки.
Настани од 2 јули
На 2-ри јули воведовме ново правило во Управуваните правила за WAF, поради што на секое јадро на процесорот што го обработува HTTP/HTTPS сообраќајот на мрежата Cloudflare ширум светот. Постојано ги подобруваме управуваните правила за WAF како одговор на новите пропусти и закани. Во мај, на пример, побрзавме за заштита од сериозна ранливост во SharePoint. Целата поента на нашиот WAF е способноста за брзо и глобално распоредување правила.
За жал, ажурирањето од минатиот четврток содржеше редовен израз што трошеше премногу ресурси на процесорот HTTP/HTTPS за враќање назад. Како резултат, настрадаа нашите основни прокси функции, CDN и WAF. Графиконот покажува дека ресурсите на процесорот за опслужување на сообраќајот HTTP/HTTPS достигнуваат речиси 100% на серверите во нашата мрежа.
Употреба на процесорот во една точка на присуство за време на инцидент
Како резултат на тоа, нашите клиенти (и клиентите на нашите клиенти) завршија со страница со грешка 502 во домените на Cloudflare. 502 грешки беа генерирани од предните веб-сервери на Cloudflare кои сè уште имаа бесплатни јадра, но не беа во можност да комуницираат со процесите што управуваат со сообраќајот HTTP/HTTPS.
Знаеме колкава непријатност им предизвика ова на нашите клиенти. Ужасно се срамиме. И овој неуспех не спречи ефикасно да се справиме со инцидентот.
Ако сте биле еден од овие клиенти, веројатно сте биле исплашени, лути и вознемирени. Згора на тоа, не сме имале а . Високата потрошувачка на процесорот се должи на едно правило на WAF со слабо формулиран редовен израз што резултираше со прекумерно назадување. Еве го виновниот израз: (?:(?:"|'|]|}||d|(?:nan|infinity|true|false|null|undefined|symbol|math)|`|-|+)+[)]*;?((?:s|-|~|!|{}||||+)*.*(?:.*=.*)))
Иако ова е интересно само по себе (и ќе зборувам за тоа подетално подолу), услугата Cloudflare беше исклучена 27 минути не само поради лошиот регуларен израз. Ни требаше време да ја опишеме низата на настани што доведоа до неуспех, па бавно реагиравме. На крајот од објавата, ќе го опишам враќањето назад во регуларен израз и ќе ви кажам што да правите со тоа.
Што се случи
Да почнеме по ред. Сите времиња овде се во UTC.
Во 13:42 часот, инженер од тимот за заштитен ѕид направи мала промена во правилата за откривање користејќи автоматски процес. Соодветно на тоа, беше креиран билет за барање за промена. Ние управуваме со такви билети преку Jira (скриншот подолу).
По 3 минути, се појави првата страница на PagerDuty, известувајќи за проблем со WAF. Ова беше синтетички тест што ја тестира функционалноста на WAF (имаме стотици од нив) надвор од Cloudflare за да ја следи нормалната работа. Веднаш потоа следеа страници со предупредувања за други неуспешни тестови на Cloudflare од крај до крај, проблеми со глобалниот сообраќај, широко распространети 502 грешки и еден тон извештаи од нашите точки на присуство (PoP) во градовите ширум светот кои укажуваат на недостаток на ресурсите на процесорот.
Добив неколку од овие предупредувања, излегов од состанок и бев на пат кон масата кога шефот на нашиот оддел за развој на решенија рече дека изгубивме 80% од нашиот сообраќај. Истрчав кај нашите инженери од SRE, кои веќе работеа на проблемот. Отпрвин мислевме дека се работи за некој непознат напад.
Инженерите на Cloudflare SRE се расфрлани низ светот и ја следат ситуацијата деноноќно. Обично, овие предупредувања ве известуваат за специфични локални проблеми со ограничен опсег, се следат на внатрешните контролни табли и се решаваат повеќе пати на ден. Но, овие страници и известувања укажаа на нешто навистина сериозно, а инженерите на SRE веднаш го прогласија нивото на сериозност P0 и контактираа со раководството и инженерите на системот.
Нашите лондонски инженери во тој момент слушаа предавање во главната сала. Предавањето мораше да се прекине, сите се собраа во голема конференциска сала и беа повикани повеќе специјалисти. Ова не беше типичен проблем со кој СРЕ можеа самите да се справат. Беше итно да се вклучат вистинските специјалисти.
Во 14 часот утврдивме дека проблемот е во ВАФ и дека нема напад. Тимот за изведба ги извади податоците од процесорот и стана јасно дека WAF е виновен. Друг вработен ја потврди оваа теорија користејќи трајс. Некој друг видел во дневниците дека има проблем со WAF. Во 00:14 часот, целиот тим дојде кај мене кога беше предложено да се користи глобално убиство, механизам вграден во Cloudflare што исклучува една компонента ширум светот.
Како направивме глобално убиство за WAF е друга приказна. Не е така едноставно. Ние користиме сопствени производи, а од нашата услуга не работеше, не можевме да се автентицираме и да се најавиме на внатрешната контролна табла (кога сè беше поправено, дознавме дека некои членови на тимот го изгубиле пристапот поради безбедносна карактеристика што ги оневозможува ингеренциите ако внатрешната контролна табла не се користи за долго време).
И не можевме да дојдеме до нашите внатрешни услуги, како Jira или системот за градење. Ни требаше механизам за заобиколување, што го користевме ретко (ова исто така ќе треба да се разработи). Конечно, еден инженер успеа да го оневозможи WAF во 14:07 часот, а во 14:09, сообраќајот и нивото на процесорот се вратија во нормала насекаде. Останатите заштитни механизми на Cloudflare работеа нормално.
Потоа се зафативме со обновување на WAF. Ситуацијата беше невообичаена, па направивме негативни тестови (прашајќи се дали промената е навистина проблемот) и позитивни тестови (да се увериме дека враќањето функционира) во еден град користејќи посебен сообраќај, префрлајќи ги клиентите што плаќаат од таму.
Во 14:52 се уверивме дека ја сфативме причината и направивме корекција и повторно го овозможивме WAF.
Како работи Cloudflare
Cloudflare има тим од инженери посветени на управување со правила за WAF. Тие се стремат да ги подобрат стапките на откривање, да ги намалат лажните позитиви и брзо да одговорат на новите закани кога ќе се појават. Во последните 60 дена, беа обработени 476 барања за промени за управуваните правила за WAF (во просек по едно на секои 3 часа).
Оваа конкретна промена требаше да биде распоредена во режим на симулација, каде што вистинскиот сообраќај на клиентите поминува низ правилото, но ништо не е блокирано. Го користиме овој режим за да ја тестираме ефективноста на правилата и да ги измериме лажно позитивните и лажно негативните стапки. Но, дури и во режим на симулација, правилата всушност мора да се извршат, а во овој случај правилото содржеше редовен израз кој трошеше премногу ресурси на процесорот.
Како што можете да видите од барањето за промена погоре, имаме план за распоредување, план за враќање и врска до внатрешна стандардна оперативна процедура (SOP) за овој тип на распоредување. СОП за промена на правило дозволува негово објавување на глобално ниво. Всушност, во Cloudflare, работите се прават сосема поинаку, а СОП диктира прво да го испратиме софтверот за тестирање и внатрешна употреба до внатрешна точка на присуство (PoP) (која ја користат нашите вработени), потоа до мал број клиенти во изолирана локација, потоа до голем број клиенти, па дури потоа до целиот свет.
Вака изгледа. Ние користиме git внатрешно преку BitBucket. Инженерите кои работат на промени поднесуваат код, кој е изграден на TeamCity, и кога ќе помине изградбата, се доделуваат рецензенти. Откако ќе се одобри барањето за повлекување, кодот се составува и се извршуваат серија тестови (повторно).
Ако изградбата и тестовите завршат успешно, се креира барање за промена во Jira и соодветниот менаџер или водач мора да ја одобри промената. По одобрувањето, распоредувањето се случува во таканаречената „PoP менажерија“: DOG, PIG и (куче, свиња и канаринци).
DOG PoP е Cloudflare PoP (како и секој друг од нашите градови) што го користат само вработените во Cloudflare. PoP за внатрешна употреба ви овозможува да ги фатите проблемите пред сообраќајот на клиентите да почне да се влева во решението. Корисна работа.
Ако тестот DOG е успешен, кодот се префрла во фазата PIG (морско прасе). Ова е Cloudflare PoP, каде што мала количина бесплатен сообраќај на клиенти тече низ нов код.
Ако се е во ред, кодот оди во Канари. Имаме три Канарски PoP во различни делови на светот. Во нив сообраќајот на платени и бесплатни клиенти поминува низ новиот код и ова е последна проверка за грешки.
Процес на издавање софтвер во Cloudflare
Ако кодот е во ред во Канари, го ослободуваме. Поминувањето низ сите фази - 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 во производството и деталите ние сме . Луа WAF користи внатрешно и применува backtracking за совпаѓање. Нема механизми за заштита од изрази кои излегуваат од контрола. Подолу ќе зборувам повеќе за ова и што правиме за тоа.
Пред да се применат правилата, сè се одвиваше без проблеми: барањето за повлекување беше креирано и одобрено, цевководот CI/CD го собра и тестираше кодот, барањето за промена беше поднесено според SOP што го регулира распоредувањето и враќањето, а распоредувањето беше завршено.
Процес на распоредување на Cloudflare WAF
Нешто тргна наопаку
Како што реков, ние распоредуваме десетици нови правила на WAF секоја недела и имаме многу системи за заштита од негативните последици од таквото распоредување. И кога нешто тргне наопаку, тоа е обично комбинација од неколку околности одеднаш. Ако најдете само една причина, ова, се разбира, е смирувачко, но не е секогаш точно. Ова се причините што заедно доведоа до неуспех на нашата услуга HTTP/HTTPS.
- Еден инженер напиша регуларен израз кој може да резултира со прекумерна .
- Функцијата што можеше да го спречи редовниот израз да троши премногу процесор беше погрешно отстранета при рефакторирање на WAF неколку недели претходно - рефакторирањето беше потребно за да се направи WAF да троши помалку ресурси.
- Моторот со регуларен израз немаше гаранции за сложеност.
- Тест пакетот не можеше да открие прекумерна потрошувачка на процесорот.
- СОП дозволува неитни промени на правилата да се воведат глобално без процес во повеќе чекори.
- Планот за враќање бараше да се изврши целосна изградба на 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.
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., Мареј Хил, Њу ЏерсиОпишува метод за пребарување на одредена низа знаци во текстот и дискутира за имплементацијата на овој метод во форма на компајлер. Компајлерот го зема регуларниот израз како изворен код и ја произведува програмата 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
