Pred takmer 9 rokmi bola Cloudflare malá spoločnosť a ja som pre ňu nepracoval, bol som len zákazník. Mesiac po spustení Cloudflare som dostal upozornenie, že môj web Zdá sa, že DNS nefunguje. Cloudflare urobil zmenu a došlo k pokazeniu DNS.
Okamžite som napísal Matthewovi Princeovi s názvom „Kde je môj DNS?“ a on mi poslal dlhú odpoveď plnú technických podrobností (), na čo som odpovedal:
Od: John Graham-Cumming
Dátum: 7. október 2010, 9:14
Predmet: Re: Kde mám DNS?
Komu: Matthew PrinceSkvelá správa, vďaka. V prípade problémov sa určite ozvem. Pravdepodobne stojí za to napísať o tom príspevok, keď zhromaždíte všetky technické informácie. Myslím si, že ľudí poteší otvorený a úprimný príbeh. Najmä ak k nemu pripojíte grafy, ktoré ukazujú, ako návštevnosť od spustenia rástla.
Na stránke mám dobrý monitoring a o každom výpadku dostávam SMS. Monitoring ukazuje, že k poruche došlo od 13:03:07 do 14:04:12. Testy sa vykonávajú každých päť minút.
Som si istý, že na to prídeš. Si si istý, že v Európe nepotrebuješ vlastnú osobu? 🙂
A on odpovedal:
Od: Matthew Prince
Dátum: 7. október 2010, 9:57
Predmet: Re: Kde mám DNS?
Komu: John Graham-CummingĎakujem. Odpovedali sme každému, kto napísal. Teraz som na ceste do kancelárie a niečo napíšeme na blog alebo pripneme oficiálny príspevok na nástenku. Úplne súhlasím, úprimnosť je všetko.
Teraz je Cloudflare naozaj veľká spoločnosť, pracujem pre ňu a teraz musím otvorene písať o našej chybe, jej dôsledkoch a našich činoch.
Udalosti 2. júla
2. júla sme zaviedli nové pravidlo v riadených pravidlách pre WAF, kvôli ktorému na každom jadre procesora, ktoré spracúva prenos HTTP/HTTPS v sieti Cloudflare po celom svete. Neustále zlepšujeme spravované pravidlá pre WAF v reakcii na nové zraniteľnosti a hrozby. V máji sme sa napríklad ponáhľali na ochranu pred závažnou zraniteľnosťou v SharePointe. Celý bod nášho WAF je schopnosť rýchlo a globálne nasadiť pravidlá.
Aktualizácia z minulého štvrtka, žiaľ, obsahovala regulárny výraz, ktorý plytval priveľa zdrojov HTTP/HTTPS CPU na spätné sledovanie. V dôsledku toho utrpeli naše základné funkcie proxy, CDN a WAF. Graf ukazuje, že procesorové zdroje na obsluhu HTTP/HTTPS prevádzky dosahujú na serveroch v našej sieti takmer 100 %.
Využitie CPU v jednom bode prítomnosti počas incidentu
Výsledkom bolo, že naši klienti (a klienti našich klientov) skončili s chybovou stránkou 502 na doménach Cloudflare. 502 chýb vygenerovali front-endové webové servery Cloudflare, ktoré mali stále voľné jadrá, ale neboli schopné komunikovať s procesmi, ktoré spracovávajú prenos HTTP/HTTPS.
Vieme, aké nepríjemnosti to spôsobilo našim zákazníkom. Strašne sa hanbíme. A toto zlyhanie nám zabránilo v efektívnom riešení incidentu.
Ak ste boli jedným z týchto zákazníkov, pravdepodobne ste boli vystrašení, nahnevaní a naštvaní. Navyše sme nemali a . Vysoká spotreba CPU bola spôsobená jedným pravidlom WAF so zle formulovaným regulárnym výrazom, čo malo za následok nadmerné spätné sledovanie. Tu je výraz viny: (?:(?:"|'|]|}||d|(?:nan|infinity|true|false|null|undefined|symbol|math)|`|-|+)+[)]*;?((?:s|-|~|!|{}||||+)*.*(?:.*=.*)))
Aj keď je to zaujímavé samo o sebe (a podrobnejšie sa o tom porozprávam nižšie), služba Cloudflare bola mimo prevádzky 27 minút nielen kvôli zlému regulárnemu výrazu. Chvíľu nám trvalo, kým sme opísali sled udalostí, ktoré viedli k zlyhaniu, takže sme reagovali pomaly. Na konci príspevku popíšem backtracking v regulárnom výraze a poviem vám, čo s tým robiť.
Čo sa stalo
Začnime pekne po poriadku. Všetky časy sú v UTC.
O 13:42 inžinier z firewallového tímu urobil malú zmenu v pravidlách detekcie pomocou automatického procesu. V súlade s tým bol vytvorený lístok so žiadosťou o zmenu. Takéto lístky spravujeme cez Jiru (screenshot nižšie).
Po 3 minútach sa objavila prvá stránka PagerDuty, ktorá hlásila problém s WAF. Išlo o syntetický test, ktorý testuje funkčnosť WAF (máme ich stovky) mimo Cloudflare na sledovanie bežnej prevádzky. Okamžite nasledovali stránky s upozorneniami o zlyhaní iných end-to-end testov služieb Cloudflare, globálnych problémoch s premávkou, rozšírených chybách 502 a množstvo hlásení z našich miest prítomnosti (PoP) v mestách po celom svete, ktoré naznačovali nedostatok. zdrojov CPU.
Dostal som niekoľko takýchto upozornení, vyrazil som zo schôdze a bol som na ceste k stolu, keď vedúci nášho oddelenia vývoja riešení povedal, že sme stratili 80 % návštevnosti. Bežal som za našimi inžiniermi SRE, ktorí už na probléme pracovali. Najprv sme si mysleli, že ide o nejaký neznámy útok.
Inžinieri Cloudflare SRE sú roztrúsení po celom svete a nepretržite monitorujú situáciu. Tieto upozornenia vás zvyčajne upozorňujú na špecifické miestne problémy obmedzeného rozsahu, sledujú sa na interných informačných paneloch a riešia sa niekoľkokrát za deň. Tieto stránky a upozornenia však naznačovali niečo naozaj vážne a inžinieri SRE okamžite vyhlásili úroveň závažnosti P0 a kontaktovali manažérov a systémových inžinierov.
Naši londýnski inžinieri v tej chvíli počúvali prednášku v hlavnej sále. Prednáška musela byť prerušená, všetci sa zhromaždili vo veľkej konferenčnej miestnosti a boli povolaní ďalší špecialisti. Toto nebol typický problém, s ktorým by sa SRE mohli vysporiadať sami. Bolo naliehavé zapojiť správnych špecialistov.
O 14:00 sme zistili, že problém bol vo WAF a k útoku nedošlo. Výkonový tím stiahol údaje CPU a bolo jasné, že na vine je WAF. Ďalší zamestnanec potvrdil túto teóriu pomocou strace. Niekto iný videl v protokoloch, že bol problém s WAF. O 14:02 prišiel za mnou celý tím, keď bolo navrhnuté použiť globálne zabíjanie, mechanizmus zabudovaný do Cloudflare, ktorý celosvetovo vypne jeden komponent.
Ako sme urobili globálne zabíjanie pre WAF, je iný príbeh. Nie je to také jednoduché. Používame naše vlastné produkty a od nášho servisu nefungovalo, nepodarilo sa nám overiť a prihlásiť sa do interného ovládacieho panela (keď bolo všetko opravené, dozvedeli sme sa, že niektorí členovia tímu stratili prístup kvôli bezpečnostnej funkcii, ktorá zakazuje prihlasovacie údaje, ak sa interný ovládací panel nepoužíva na dlho).
A nemohli sme sa dostať k našim interným službám, ako je Jira alebo systém zostavovania. Potrebovali sme mechanizmus obchádzania, ktorý sme nepoužívali často (aj to bude potrebné vyriešiť). Nakoniec sa jednému inžinierovi podarilo vypnúť WAF o 14:07 a o 14:09 bola prevádzka a úroveň CPU všade späť do normálu. Zvyšok ochranných mechanizmov Cloudflare fungoval normálne.
Potom sme sa pustili do obnovy WAF. Situácia bola neštandardná, a tak sme v jednom meste vykonali negatívne testy (pýtali sme sa sami seba, či bola zmena skutočne problémom) a pozitívne testy (uistili sme sa, že vrátenie funguje) s použitím oddelenej premávky, pričom sme odtiaľ presunuli platiacich zákazníkov.
O 14:52 sme sa presvedčili, že sme pochopili dôvod a urobili sme nápravu a opäť sme povolili WAF.
Ako funguje Cloudflare
Cloudflare má tím inžinierov, ktorí sa venujú správe pravidiel pre WAF. Usilujú sa zlepšiť mieru detekcie, znížiť počet falošných poplachov a rýchlo reagovať na nové hrozby, keď sa objavia. Za posledných 60 dní bolo spracovaných 476 žiadostí o zmenu spravovaných pravidiel pre WAF (v priemere jedna každé 3 hodiny).
Túto konkrétnu zmenu bolo potrebné nasadiť v režime simulácie, kde reálna klientska prevádzka prechádza pravidlom, ale nič nie je blokované. Tento režim používame na testovanie účinnosti pravidiel a meranie miery falošne pozitívnych a falošne negatívnych výsledkov. Ale aj v simulačnom režime sa pravidlá musia skutočne vykonať a v tomto prípade pravidlo obsahovalo regulárny výraz, ktorý spotreboval príliš veľa procesorových zdrojov.
Ako môžete vidieť z vyššie uvedenej žiadosti o zmenu, máme plán nasadenia, plán vrátenia a prepojenie na interný štandardný operačný postup (SOP) pre tento typ nasadenia. SOP na zmenu pravidla umožňuje jeho globálne zverejnenie. V Cloudflare sa v skutočnosti veci robia úplne inak a štandardný operačný postup prikazuje, aby sme softvér najprv odoslali na testovanie a interné použitie do interného bodu prítomnosti (PoP) (ktorý používajú naši zamestnanci), potom malému počtu klientov v izolovanej lokalite, potom veľkému počtu klientov a až potom celému svetu.
Takto to vyzerá. git používame interne cez BitBucket. Inžinieri pracujúci na zmenách predložia kód, ktorý je vytvorený pre TeamCity, a keď zostava prejde, sú priradení recenzenti. Po schválení žiadosti o stiahnutie sa kód zostaví a spustí sa (znova) séria testov.
Ak sa zostava a testy úspešne dokončia, v Jira sa vytvorí žiadosť o zmenu a zmenu musí schváliť príslušný manažér alebo vedúci. Po schválení dochádza k nasadeniu do tzv. „PoP zverinca“: PES, PIG a (pes, prasa a kanárik).
DOG PoP je Cloudflare PoP (ako každé iné naše mesto), ktorý používajú iba zamestnanci Cloudflare. PoP pre interné použitie vám umožňuje zachytiť problémy skôr, ako do riešenia začne prúdiť návštevnosť zákazníkov. Užitočná vec.
Ak je test PSOM úspešný, kód sa presunie do štádia PIG (morča). Toto je Cloudflare PoP, kde cez nový kód prúdi malé množstvo bezplatnej návštevnosti zákazníkov.
Ak je všetko v poriadku, kód prejde na Kanárske ostrovy. Máme tri kanárske PoP v rôznych častiach sveta. V nich návštevnosť platených a bezplatných klientov prechádza cez nový kód a to je posledná kontrola chýb.
Proces vydania softvéru v Cloudflare
Ak je kód na Kanárskych ostrovoch v poriadku, uvoľníme ho. Prechod všetkými fázami – PES, PIG, Kanár, celý svet – trvá niekoľko hodín alebo dní, v závislosti od zmeny kódu. Vzhľadom na rôznorodosť siete a klientov Cloudflare kód dôkladne testujeme predtým, ako ho globálne uvoľníme všetkým klientom. WAF však tento proces konkrétne nedodržiava, pretože na hrozby je potrebné rýchlo reagovať.
Hrozby WAF
Za posledných pár rokov došlo k výraznému nárastu hrozieb v bežných aplikáciách. Je to spôsobené väčšou dostupnosťou nástrojov na testovanie softvéru. Nedávno sme napríklad písali o ).
Zdroj:
Veľmi často sa vytvorí a okamžite zverejní proof of concept na Github, aby tímy spravujúce aplikáciu mohli rýchlo otestovať a zabezpečiť, aby bola adekvátne zabezpečená. Cloudflare preto potrebuje schopnosť čo najrýchlejšie reagovať na nové útoky, aby zákazníci mali možnosť opraviť svoj softvér.
Skvelým príkladom rýchlej reakcie Cloudflare je nasadenie ochrany pred zraniteľnosťou SharePoint v máji (). Takmer okamžite po oznámení sme zaznamenali obrovské množstvo pokusov o zneužitie zraniteľnosti v inštaláciách SharePoint našich zákazníkov. Naši chlapci neustále monitorujú nové hrozby a píšu pravidlá na ochranu našich zákazníkov.
Pravidlo, ktoré vo štvrtok spôsobilo problém, malo chrániť pred cross-site scriptingom (XSS). Aj takéto útoky sú v posledných rokoch oveľa častejšie.
Zdroj:
Štandardným postupom na zmenu riadeného pravidla pre WAF je vykonať testovanie nepretržitej integrácie (CI) pred globálnym nasadením. Minulý štvrtok sme to urobili a zaviedli pravidlá. O 13:31 inžinier predložil schválenú žiadosť o stiahnutie so zmenou.
O 13:37 TeamCity zhromaždil pravidlá, spustil testy a dal súhlas. Testovacia sada WAF testuje základnú funkčnosť WAF a pozostáva z veľkého počtu jednotkových testov pre jednotlivé funkcie. Po jednotkových testoch sme otestovali pravidlá pre WAF pomocou obrovského množstva HTTP požiadaviek. HTTP požiadavky kontrolujú, ktoré požiadavky by mal WAF zablokovať (aby zachytil útok) a ktoré je možné povoliť (aby sa neblokovalo všetko a zabránilo sa falošným poplachom). Netestovali sme však nadmerné využitie procesora a skúmanie protokolov predchádzajúcich verzií WAF ukazuje, že čas vykonania testu pravidiel sa nezvýšil a bolo ťažké predpokladať, že nebude dostatok zdrojov.
Testy prešli a TeamCity začal automaticky nasadzovať zmenu o 13:42.
Ortuť
Pravidlá WAF sa zameriavajú na okamžitú nápravu hrozieb, preto ich nasadzujeme pomocou distribuovaného úložiska kľúč-hodnota spoločnosti Quicksilver, ktoré globálne šíri zmeny v priebehu niekoľkých sekúnd. Všetci naši klienti využívajú túto technológiu pri zmene konfigurácie v dashboarde alebo cez API a práve vďaka nej reagujeme na zmeny bleskovou rýchlosťou.
O Quicksilver sme toho veľa nehovorili. Predtým sme používali ako globálne distribuovaný obchod kľúč-hodnota, ale vyskytli sa s ním prevádzkové problémy a vytvorili sme vlastný obchod, replikovaný vo viac ako 180 mestách. Teraz používame Quicksilver na odosielanie zmien konfigurácie klientom, aktualizáciu pravidiel WAF a distribúciu kódu JavaScript napísaného klientmi pracovníkom Cloudflare.
Od kliknutia na tlačidlo na ovládacom paneli alebo volania rozhrania API po celosvetovú zmenu konfigurácie to trvá len niekoľko sekúnd. Zákazníci milovali túto rýchlosť nastavenia. A Workers im poskytuje takmer okamžité globálne nasadenie softvéru. V priemere Quicksilver šíri asi 350 zmien za sekundu.
A Quicksilver je veľmi rýchly. V priemere sme dosiahli 99. percentil 2,29 sekundy na rozšírenie zmien do každého počítača na celom svete. Rýchlosť je zvyčajne dobrá vec. Koniec koncov, keď povolíte funkciu alebo vymažete vyrovnávaciu pamäť, stane sa to takmer okamžite a všade. Odosielanie kódu cez Cloudflare Workers prebieha rovnakou rýchlosťou. Cloudflare svojim zákazníkom sľubuje rýchle aktualizácie v správnom čase.
Ale v tomto prípade si z nás rýchlosť zahrala krutý žart a pravidlá sa zmenili všade v priebehu niekoľkých sekúnd. Možno ste si všimli, že kód WAF používa Lua. Cloudflare vo veľkej miere využíva Lua vo výrobe a detailoch sme . Používa Lua WAF interne a použije spätné sledovanie na párovanie. Nemá žiadne mechanizmy na ochranu pred prejavmi, ktoré sa vymknú kontrole. Nižšie o tom poviem viac a čo s tým robíme.
Pred nasadením pravidiel všetko prebehlo hladko: požiadavka na stiahnutie bola vytvorená a schválená, kanál CI/CD zhromaždil a otestoval kód, žiadosť o zmenu bola odoslaná podľa SOP, ktorý upravuje nasadenie a vrátenie, a nasadenie bolo dokončené.
Proces nasadenia cloudflare WAF
Niečo sa pokazilo
Ako som povedal, každý týždeň nasadzujeme desiatky nových pravidiel WAF a máme zavedených mnoho systémov na ochranu pred negatívnymi následkami takéhoto nasadenia. A keď sa niečo pokazí, väčšinou ide o súhru viacerých okolností naraz. Ak nájdete len jeden dôvod, je to, samozrejme, upokojujúce, ale nie vždy je to pravda. Toto sú dôvody, ktoré spolu viedli k zlyhaniu našej HTTP/HTTPS služby.
- Inžinier napísal regulárny výraz, ktorý by mohol viesť k nadmernému množstvu .
- Funkcia, ktorá mohla zabrániť tomu, aby regulárny výraz plytval príliš veľkým množstvom CPU, bola omylom odstránená pri refaktorovaní WAF pred niekoľkými týždňami – refaktoring bol potrebný, aby WAF spotreboval menej zdrojov.
- Modul regulárneho výrazu nemal žiadne záruky zložitosti.
- Testovacia sada nedokázala zistiť nadmernú spotrebu procesora.
- SOP umožňuje, aby zmeny pravidiel, ktoré nie sú naliehavé, boli zavedené globálne bez viackrokového procesu.
- Plán návratu vyžadoval spustenie úplnej zostavy WAF dvakrát, čo trvalo dlho.
- Prvé varovanie o globálnych dopravných problémoch bolo spustené príliš neskoro.
- Chvíľu nám trvalo, kým sme aktualizovali stavovú stránku.
- Mali sme problémy s prístupom k systémom kvôli poruche a postup obchádzania nebol dobre zavedený.
- Inžinieri SRE stratili prístup k niektorým systémom, pretože platnosť ich poverení z bezpečnostných dôvodov vypršala.
- Naši zákazníci nemali prístup k ovládaciemu panelu alebo API Cloudflare, pretože prechádzajú cez región Cloudflare.
Čo sa zmenilo od minulého štvrtka
Po prvé, úplne sme zastavili všetky práce na vydaniach pre WAF a robíme nasledovné:
- Opätovne zavádzame ochranu proti nadmernému využívaniu CPU, ktorú sme odstránili. (pripravené)
- Manuálna kontrola všetkých 3868 XNUMX pravidiel v riadených pravidlách pre WAF s cieľom nájsť a opraviť ďalšie potenciálne prípady nadmerného spätného sledovania. (Overenie dokončené)
- V testovacej sade zahŕňame profilovanie výkonu pre všetky pravidlá. (Očakávané: 19. júla)
- Prechod na nástroj regulárneho výrazu alebo - obe poskytujú záruky za behu. (Očakávané: 31. júla)
- Prepisujeme SOP, aby sme nasadzovali pravidlá po etapách, podobne ako iný softvér v Cloudflare, ale zároveň máme schopnosť okamžite sa nasadiť globálne, ak už útoky začali.
- Vyvíjame schopnosť urýchlene odstrániť dashboard a API Cloudflare z oblasti Cloudflare.
- Automatizácia aktualizácií stránok .
Z dlhodobého hľadiska sa vzďaľujeme od Lua WAF, ktorý som napísal pred niekoľkými rokmi. Presúvanie WAF do . Týmto spôsobom bude WAF rýchlejší a získa dodatočnú úroveň ochrany.
Záver
Toto zlyhanie spôsobilo problémy nám aj našim zákazníkom. Rýchlo sme konali, aby sme situáciu napravili, a teraz pracujeme na nedostatkoch v procesoch, ktoré spôsobili zrútenie, ako aj na ešte hlbšie, aby sme sa v budúcnosti pri migrácii na novú technológiu ochránili pred možnými problémami s regulárnymi výrazmi.
Za tento výpadok sme veľmi v rozpakoch a ospravedlňujeme sa našim zákazníkom. Dúfame, že tieto zmeny zabezpečia, aby sa niečo podobné už nezopakovalo.
Aplikácia. Spätné sledovanie regulárnych výrazov
Aby ste pochopili, ako výraz:
(?:(?:"|'|]|}||d
(?:nan|infinity|true|false|null|undefined|symbol|math)|`|-
|+)+[)]*;?((?:s|-|~|!|{}||||+)*.*(?:.*=.*)))zjedol všetky zdroje CPU, potrebujete vedieť trochu o tom, ako funguje štandardný regulárny výraz. Problémom je tu vzorec .*(?:.*=.*). (?: a zodpovedajúce ) je nezachytávajúca skupina (to znamená, že výraz v zátvorkách je zoskupený ako jeden výraz).
V kontexte nadmernej spotreby CPU možno tento vzor opísať ako .*.*=.*. V tejto podobe vyzerá vzor zbytočne zložito. Čo je však dôležitejšie, v reálnom svete môžu výrazy (ako zložité výrazy v pravidlách WAF), ktoré vyžadujú, aby sa motor zhodoval s fragmentom nasledovaným ďalším fragmentom, viesť ku katastrofálnemu spätnému chodu. A preto.
V regulárnom výraze . znamená, že musíte zodpovedať jednému znaku, .* - priraďte nula alebo viac znakov "nenásytne", to znamená zachytenie maximálneho počtu znakov, takže .*.*=.* znamená nájsť nula alebo viac znakov, potom nájsť nula alebo viac znakov, nájsť doslovný znak =, nájsť nula alebo viac znakov.
Zoberme si testovací riadok x=x. Zodpovedá to výrazu .*.*=.*. .*.* predtým, ako sa znamienko rovnosti zhoduje s prvým x (jedna zo skupín .* zodpovedá xa druhý - nula znakov). .* po = zápasy posledné x.
Toto porovnanie vyžaduje 23 krokov. Prvá skupina .* в .*.*=.* pôsobí nenásytne a zhoduje sa s celým reťazcom x=x. Motor sa presunie do ďalšej skupiny .*. Nemáme ďalšie postavy, ktoré by sa dali zhodovať, takže druhá skupina .* zhoduje sa s nula znakmi (toto je povolené). Potom sa motor presunie na znak =. Neexistujú žiadne ďalšie symboly (prvá skupina .* použil celý výraz x=x), nedochádza k porovnávaniu.
A potom sa motor regulárneho výrazu vráti na začiatok. Prechádza do prvej skupiny .* a porovnáva to с x= (namiesto x=x), a potom preberá druhú skupinu .*. Druhá skupina .* sa porovnáva s druhým x, a opäť nám nezostali žiadne postavy. A keď motor opäť dosiahne = в .*.*=.*, nič nefunguje. A opäť cúvne.
Tentoraz skupina .* stále zápasy x=, ale druhá skupina .* nikdy viac xa nula znakov. Motor sa snaží nájsť doslovný charakter = vo vzore .*.*=.*, ale nevychádza (napokon, prvá skupina ho už obsadila .*). A opäť cúvne.
Tentoraz prvá skupina .* trvá len prvé x. Ale tá druhá skupina .* „chtivo“ zachytáva =x. Uhádli ste už, čo sa stane? Motor sa snaží vyrovnať doslova =, zlyhá a urobí ďalšie cúvanie.
Prvá skupina .* stále sa zhoduje s prvým x. Po druhé .* len berie =. Samozrejme, motor sa doslova nemôže rovnať =, pretože druhá skupina to už urobila .*. A opäť cúvanie. A snažíme sa spojiť reťazec troch znakov!
V dôsledku toho prvá skupina .* sa zhoduje iba s prvým x, druhý .* - s nulovými znakmi a engine konečne zodpovedá doslovu = vo výraze с = v rade. Nasleduje posledná skupina .* sa porovnáva s posledným x.
23 krokov len pre x=x. Pozrite si krátke video o používaní Perlu , ktorá ukazuje, ako prebiehajú kroky a spätné sledovanie.
To je už veľa práce, ale čo ak namiesto toho x=x budeme mať x=xx? To je 33 krokov. A keď x=xxx? 45. Vzťah nie je lineárny. Graf ukazuje porovnanie z x=x na x=xxxxxxxxxxxxxxxxxxxx (20 x po =). Ak máme 20 x po =, motor dokončí párovanie v 555 krokoch! (Navyše, ak sme prehrali x= a reťazec jednoducho pozostáva z 20 x, motor vykoná 4067 krokov, aby pochopil, že neexistujú žiadne zhody).
Toto video ukazuje všetko spätné sledovanie na porovnanie x=xxxxxxxxxxxxxxxxxxxx:
Problém je v tom, že so zväčšujúcou sa veľkosťou reťazca narastá čas zhody superlineárne. Ale veci sa môžu ešte zhoršiť, ak sa regulárny výraz mierne upraví. Povedzme, že sme mali .*.*=.*; (to znamená, že na konci vzoru bola doslovná bodkočiarka). Napríklad na zhodu s výrazom ako foo=bar;.
A tu by bol návrat späť skutočnou katastrofou. Na porovnanie x=x bude to trvať 90 krokov, nie 23. A toto číslo rýchlo rastie. Porovnať x= a 20 x, je potrebných 5353 krokov. Tu je graf. Pozrite sa na hodnoty osí Y v porovnaní s predchádzajúcim grafom.
Ak máte záujem, pozrite si všetkých 5353 XNUMX neúspešných krokov priradenia x=xxxxxxxxxxxxxxxxxxxx и .*.*=.*;
Použitím lenivého priraďovania namiesto nenásytného priraďovania je možné kontrolovať rozsah spätného sledovania. Ak zmeníme pôvodný výraz na .*?.*?=.*?, na porovnanie x=x bude to trvať 11 krokov (nie 23). Ako pre x=xxxxxxxxxxxxxxxxxxxx. Všetko preto ? po .* povie motoru, aby sa zhodoval s minimálnym počtom znakov, kým sa posunie ďalej.
Lenivé mapovania však problém spätného sledovania úplne nevyriešia. Ak nahradíme katastrofický príklad .*.*=.*; na .*?.*?=.*?;, doba vykonania zostane rovnaká. x=x stále vyžaduje 555 krokov a x= a 20 x - 5353.
Jediná vec, ktorú možno urobiť (okrem úplného prepísania vzoru pre väčšiu špecifickosť), je opustiť motor regulárneho výrazu s jeho mechanizmom spätného sledovania. To je to, čo budeme robiť v najbližších týždňoch.
Riešenie tohto problému je známe už od roku 1968, kedy Kent Thompson napísal článok („Metódy programovania: Algoritmus vyhľadávania regulárnych výrazov“). Článok popisuje mechanizmus, ktorý vám umožňuje previesť regulárny výraz na nedeterministické konečné automaty a po zmenách stavu v nedeterministických konečných automatoch použiť algoritmus, ktorého čas vykonania lineárne závisí od spárovaného reťazca.
Programovacie metódy
Algoritmus vyhľadávania regulárnych výrazov
Ken Thompson
Bell Telephone Laboratories, Inc., Murray Hill, New JerseyPopisuje metódu vyhľadávania špecifického reťazca znakov v texte a rozoberá implementáciu tejto metódy vo forme kompilátora. Kompilátor berie regulárny výraz ako zdrojový kód a vytvára program IBM 7094 ako objektový kód. Objektový program prijíma vstup vo forme hľadaného textu a vysiela signál vždy, keď sa reťazec textu porovná s daným regulárnym výrazom. Článok obsahuje príklady, problémy a riešenia.
Algoritmus
Predchádzajúce vyhľadávacie algoritmy viedli k spätnému sledovaniu, ak čiastočne úspešné vyhľadávanie neprinieslo výsledok.V režime kompilácie algoritmus nepracuje so symbolmi. Odovzdáva inštrukcie kompilovanému kódu. Vykonávanie je veľmi rýchle – po odovzdaní údajov na začiatok aktuálneho zoznamu automaticky vyhľadá všetky možné po sebe idúce znaky v regulárnom výraze.
Algoritmus kompilácie a vyhľadávania je zahrnutý v textovom editore zdieľania času ako kontextové vyhľadávanie. Samozrejme, toto nie je zďaleka jediné uplatnenie takéhoto postupu vyhľadávania. Napríklad variant tohto algoritmu sa používa na vyhľadávanie symbolov v tabuľke v assembleri.
Predpokladá sa, že čitateľ pozná regulárne výrazy a počítačový programovací jazyk IBM 7094.Kompilátor
Kompilátor pozostáva z troch paralelne prebiehajúcich fáz. Prvou fázou je syntaktické filtrovanie, ktoré umožňuje prechádzať len syntakticky správnym regulárnym výrazom. Tento krok tiež vloží operátor "·", aby zodpovedal regulárnym výrazom. V druhom kroku sa regulárny výraz prevedie na postfixovú formu. V tretej fáze sa vytvorí objektový kód. Prvé 2 fázy sú zrejmé a nebudeme sa nimi zaoberať.
Thompsonov článok nehovorí o nedeterministických konečných strojoch, ale dobre vysvetľuje algoritmus lineárneho času a predstavuje program ALGOL-60, ktorý generuje kód assembleru pre IBM 7094. Implementácia je zložitá, ale myšlienka je veľmi jednoduchá.
aktuálna cesta vyhľadávania. Predstavuje ho ikona ⊕ s jedným vstupom a dvomi výstupmi.
Obrázok 1 zobrazuje funkcie tretieho kroku kompilácie pri transformácii príkladu regulárneho výrazu. Prvé tri znaky v príklade sú a, b, c a každý vytvára položku zásobníka S[i] a pole NNODE.NNODE na existujúci kód na vygenerovanie výsledného regulárneho výrazu v jednej položke zásobníka (pozri obrázok 5)
Takto by vyzeral regulárny výraz .*.*=.*, ak si to predstavíte ako na obrázkoch z Thompsonovho článku.
Na obr. 0 je päť stavov začínajúcich od 0 a 3 cykly, ktoré začínajú od stavov 1, 2 a 3. Tieto tri cykly zodpovedajú trom .* v regulárnom výraze. 3 ovály s bodkami zodpovedajú jednému symbolu. Ovál so znakom = zodpovedá doslovnému znaku =. Stav 4 je konečný. Ak ho dosiahneme, potom sa regulárny výraz zhoduje.
Aby sme videli, ako sa dá takýto stavový diagram použiť na porovnávanie regulárnych výrazov .*.*=.*, pozrieme sa na párovanie reťazcov x=x. Program začína od stavu 0, ako je znázornené na obr. 1.
Aby tento algoritmus fungoval, musí byť stavový automat v niekoľkých stavoch súčasne. Nedeterministický konečný stroj urobí všetky možné prechody súčasne.
Skôr ako stihne prečítať vstupné dáta, prejde do oboch prvých stavov (1 a 2), ako je znázornené na obr. 2.
Na obr. 2 ukazuje, čo sa stane, keď sa pozrie na prvé x в x=x. x môže mapovať k najvyššiemu bodu, pričom prechádza zo stavu 1 a späť do stavu 1. Or x môže mapovať do bodu nižšie, presúvať sa zo stavu 2 a späť do stavu 2.
Po zhode prvého x в x=x stále sme v stave 1 a 2. Nemôžeme dosiahnuť stav 3 alebo 4, pretože potrebujeme doslovný znak =.
Algoritmus potom zváži = в x=x. Rovnako ako x pred ním, môže byť priradené k jednej z dvoch horných slučiek zo stavu 1 do stavu 1 alebo zo stavu 2 do stavu 2, ale algoritmus sa môže zhodovať s doslovným = a prejsť zo stavu 2 do stavu 3 (a hneď 4). Toto je znázornené na obr. 3.
Algoritmus potom prejde na posledný x в x=x. Zo stavu 1 a 2 sú možné rovnaké prechody späť do stavu 1 a 2. Zo stavu 3 x môže zodpovedať bodu vpravo a vrátiť sa do stavu 3.
V tejto fáze každá postava x=x a keďže sme dosiahli stav 4, regulárny výraz sa zhoduje s týmto reťazcom. Každý znak je spracovaný raz, takže tento algoritmus je lineárny v dĺžke vstupného reťazca. A žiadne cúvanie.
Je zrejmé, že po dosiahnutí stavu 4 (keď sa algoritmus zhoduje x=) sa zhoduje celý regulárny výraz a algoritmus sa môže ukončiť bez toho, aby to vôbec zvážil x.
Tento algoritmus závisí lineárne od veľkosti vstupného reťazca.
Zdroj: hab.com
