Před téměř 9 lety byla Cloudflare malá společnost a já jsem pro ni nepracoval, byl jsem jen zákazník. Měsíc po spuštění Cloudflare mi přišlo upozornění, že můj web Zdá se, že DNS nefunguje. Cloudflare provedl změnu a došlo k nefunkčnímu DNS.
Okamžitě jsem napsal Matthew Prince s názvem „Kde je můj DNS?“ a on mi poslal dlouhou odpověď plnou technických podrobností (), na kterou jsem odpověděl:
Od: John Graham-Cumming
Datum: 7. října 2010, 9:14
Předmět: Re: Kde je můj DNS?
Komu: Matthew PrinceSuper report, díky. V případě problémů se určitě ozvu. Pravděpodobně stojí za to napsat o tom příspěvek, jakmile shromáždíte všechny technické informace. Myslím, že se lidem bude líbit otevřený a upřímný příběh. Zvláště pokud k němu připojíte grafy, které ukazují, jak návštěvnost od spuštění vzrostla.
Na svých stránkách mám dobrý monitoring a o každém selhání dostávám SMS. Monitoring ukazuje, že k poruše došlo od 13:03:07 do 14:04:12. Testy se provádějí každých pět minut.
Určitě na to přijdeš. Jste si jistý, že v Evropě nepotřebujete vlastní osobu? 🙂
A on odpověděl:
Od: Matthew Prince
Datum: 7. října 2010, 9:57
Předmět: Re: Kde je můj DNS?
Komu: John Graham-CummingDěkuji. Všem, kdo napsali, jsme odpověděli. Teď jsem na cestě do kanceláře a něco napíšeme na blog nebo si připneme oficiální příspěvek na nástěnku. Naprosto souhlasím, upřímnost je všechno.
Nyní je Cloudflare opravdu velká společnost, pracuji pro ni a nyní musím otevřeně psát o naší chybě, jejích důsledcích a našich činech.
Události 2. července
2. července jsme zavedli nové pravidlo ve spravovaných pravidlech pro WAF, kvůli kterému na každém procesorovém jádru zpracovávajícím provoz HTTP/HTTPS v síti Cloudflare po celém světě. Neustále zlepšujeme spravovaná pravidla pro WAF v reakci na nová zranitelnost a hrozby. V květnu jsme například spěchali k ochraně před závažnou chybou zabezpečení v SharePointu. Celým smyslem našeho WAF je schopnost rychle a globálně nasadit pravidla.
Aktualizace z minulého čtvrtka bohužel obsahovala regulární výraz, který zbytečně plýtval prostředky procesoru HTTP/HTTPS na backtracking. V důsledku toho utrpěly naše základní funkce proxy, CDN a WAF. Graf ukazuje, že procesorové zdroje pro obsluhu HTTP/HTTPS provozu dosahují na serverech v naší síti téměř 100 %.
Využití CPU v jednom bodě přítomnosti během incidentu
V důsledku toho naši klienti (a klienti našich klientů) skončili s chybovou stránkou 502 v doménách Cloudflare. 502 chyb bylo vygenerováno předními webovými servery Cloudflare, které stále měly volná jádra, ale nebyly schopny komunikovat s procesy zpracovávajícími provoz HTTP/HTTPS.
Víme, jaké nepříjemnosti to našim zákazníkům způsobilo. Strašně se stydíme. A toto selhání nám bránilo v efektivním řešení incidentu.
Pokud jste byli jedním z těchto zákazníků, pravděpodobně jste byli vyděšení, naštvaní a naštvaní. Navíc jsme neměli . Vysoká spotřeba CPU byla způsobena jedním pravidlem WAF se špatně formulovaným regulárním výrazem, což mělo za následek nadměrné zpětné sledování. Zde je provinilý výraz: (?:(?:"|'|]|}||d|(?:nan|infinity|true|false|null|undefined|symbol|math)|`|-|+)+[)]*;?((?:s|-|~|!|{}||||+)*.*(?:.*=.*)))
I když je to zajímavé samo o sobě (a podrobněji se o tom zmíním níže), služba Cloudflare byla na 27 minut mimo provoz nejen kvůli špatnému regulárnímu výrazu. Chvíli nám trvalo, než jsme popsali sled událostí, které vedly k selhání, takže jsme reagovali pomalu. Na konci příspěvku popíšu backtracking v regulárním výrazu a řeknu vám, co s tím.
Co se stalo
Začněme popořadě. Všechny časy zde jsou v UTC.
Ve 13:42 provedl inženýr z firewallového týmu malou změnu v pravidlech detekce pomocí automatického procesu. V souladu s tím byl vytvořen lístek žádosti o změnu. Takové vstupenky spravujeme přes Jiru (screenshot níže).
Po 3 minutách se objevila první stránka PagerDuty, která hlásila problém s WAF. Jednalo se o syntetický test, který testuje funkčnost WAF (máme jich stovky) mimo Cloudflare pro sledování běžného provozu. Okamžitě následovaly stránky s upozorněními na jiné testy end-to-end služeb Cloudflare, problémy s globálním provozem, rozšířené chyby 502 a spousta zpráv z našich bodů přítomnosti (PoP) ve městech po celém světě, které naznačovaly nedostatek zdrojů CPU.
Dostal jsem několik těchto upozornění, vyrazil jsem ze schůzky a byl jsem na cestě ke stolu, když vedoucí našeho oddělení vývoje řešení řekl, že jsme ztratili 80 % provozu. Běžel jsem za našimi inženýry SRE, kteří už na problému pracovali. Nejprve jsme si mysleli, že jde o nějaký neznámý útok.
Inženýři Cloudflare SRE jsou rozptýleni po celém světě a nepřetržitě monitorují situaci. Tyto výstrahy vás obvykle upozorňují na konkrétní místní problémy omezeného rozsahu, jsou sledovány na interních řídicích panelech a jsou řešeny několikrát za den. Ale tyto stránky a oznámení naznačovaly něco opravdu vážného a inženýři SRE okamžitě vyhlásili úroveň závažnosti P0 a kontaktovali management a systémové inženýry.
Naši londýnští inženýři v tu chvíli poslouchali přednášku v hlavním sále. Přednáška musela být přerušena, všichni se sešli ve velké zasedací místnosti a byli povoláni další specialisté. Toto nebyl typický problém, se kterým by si SRE dokázaly poradit samy. Bylo naléhavé zapojit ty správné specialisty.
Ve 14:00 jsme zjistili, že problém byl ve WAF a nedošlo k žádnému útoku. Výkonový tým stáhl data CPU a bylo jasné, že za to může WAF. Další zaměstnanec tuto teorii potvrdil pomocí strace. Někdo jiný viděl v protokolech, že byl problém s WAF. Ve 14:02 za mnou přišel celý tým, když bylo navrženo použít globální zabíjení, mechanismus zabudovaný do Cloudflare, který celosvětově vypne jednu komponentu.
Jak jsme provedli globální zabíjení pro WAF, je jiný příběh. Není to tak jednoduché. Používáme vlastní produkty, a protože naše služby nefungovalo, nemohli jsme se ověřit a přihlásit k internímu ovládacímu panelu (když bylo vše opraveno, zjistili jsme, že někteří členové týmu ztratili přístup kvůli bezpečnostní funkci, která zakazuje přihlašovací údaje, pokud se interní ovládací panel nepoužívá pro dlouho).
A nemohli jsme se dostat k našim interním službám, jako je Jira nebo systém sestavení. Potřebovali jsme mechanismus pro obcházení, který jsme používali zřídka (i ten bude třeba vypracovat). Nakonec se jednomu inženýrovi podařilo deaktivovat WAF ve 14:07 a ve 14:09 byl provoz a úrovně CPU všude zpět k normálu. Zbytek ochranných mechanismů Cloudflare fungoval jako obvykle.
Pak jsme se pustili do obnovy WAF. Situace byla neobvyklá, takže jsme provedli negativní testy (zeptali jsme se sami sebe, zda je změna skutečně problémem) a pozitivní testy (ujistili se, že vrácení zpět funguje) v jednom městě pomocí odděleného provozu, odkud jsme převedli platící zákazníky.
Ve 14:52 jsme byli přesvědčeni, že jsme pochopili důvod a provedli nápravu a znovu povolili WAF.
Jak Cloudflare funguje
Cloudflare má tým inženýrů, kteří se věnují správě pravidel pro soubory WAF. Snaží se zlepšit míru detekce, snížit počet falešných poplachů a rychle reagovat na nové hrozby, jakmile se objeví. Za posledních 60 dní bylo zpracováno 476 požadavků na změnu spravovaných pravidel pro WAF (v průměru jeden každé 3 hodiny).
Tuto konkrétní změnu bylo potřeba nasadit v simulačním režimu, kde reálný klientský provoz prochází pravidlem, ale nic není blokováno. Tento režim používáme k testování účinnosti pravidel a měření míry falešně pozitivních a falešně negativních výsledků. Ale i v simulačním režimu musí být pravidla skutečně provedena a v tomto případě pravidlo obsahovalo regulární výraz, který spotřebovával příliš mnoho procesorových zdrojů.
Jak můžete vidět z požadavku na změnu výše, máme plán nasazení, plán vrácení a odkaz na interní standardní operační postup (SOP) pro tento typ nasazení. SOP pro změnu pravidla umožňuje, aby bylo zveřejněno globálně. Ve skutečnosti se ve společnosti Cloudflare dělají věci úplně jinak a SOP nařizuje, že nejprve odešleme software k testování a internímu použití do interního bodu přítomnosti (PoP) (který používají naši zaměstnanci), poté malému počtu klientů v izolovaném místě, pak velkému počtu klientů a teprve poté celému světu.
Takhle to vypadá. Interně používáme git přes BitBucket. Inženýři pracující na změnách odešlou kód, který je vytvořen pro TeamCity, a když sestavení projde, jsou přiřazeni recenzenti. Jakmile je žádost o stažení schválena, kód se sestaví a (znovu) se spustí řada testů.
Pokud se sestavení a testy úspěšně dokončí, vytvoří se v Jira požadavek na změnu a příslušný manažer nebo potenciální zákazník musí změnu schválit. Po schválení dochází k nasazení do tzv. „PoP zvěřince“: DOG, PIG a (pes, prase a kanárek).
DOG PoP je Cloudflare PoP (jako každé jiné naše město), který používají pouze zaměstnanci Cloudflare. PoP pro interní použití vám umožňuje zachytit problémy dříve, než do řešení začne proudit zákaznický provoz. Užitečná věc.
Pokud je test PSA úspěšný, kód se přesune do fáze PIG (morče). Toto je Cloudflare PoP, kde prostřednictvím nového kódu proudí malé množství bezplatného zákaznického provozu.
Pokud je vše v pořádku, kód přejde na Kanárské ostrovy. Máme tři Kanárské PoP v různých částech světa. V nich návštěvnost placených i bezplatných klientů prochází novým kódem a to je poslední kontrola chyb.
Proces vydání softwaru ve společnosti Cloudflare
Pokud je kód na Canary v pořádku, uvolníme ho. Projít všemi fázemi - PES, PIG, Kanár, celý svět - trvá několik hodin nebo dní v závislosti na změně kódu. Vzhledem k rozmanitosti sítě a klientů Cloudflare kód důkladně testujeme, než jej globálně uvolníme všem klientům. WAF však tento proces konkrétně nedodržuje, protože na hrozby je třeba rychle reagovat.
WAF hrozby
Během několika posledních let došlo k výraznému nárůstu hrozeb v běžných aplikacích. To je způsobeno větší dostupností nástrojů pro testování softwaru. Nedávno jsme například psali o ).
Zdroj:
Velmi často je vytvořen proof of concept a okamžitě zveřejněn na Github, aby ji týmy udržující aplikaci mohly rychle otestovat a zajistit, aby byla adekvátně zabezpečena. Cloudflare proto potřebuje schopnost co nejrychleji reagovat na nové útoky, aby zákazníci měli možnost opravit svůj software.
Skvělým příkladem rychlé reakce Cloudflare je nasazení ochrany před zranitelností SharePoint v květnu (). Téměř okamžitě po oznámení jsme zaznamenali obrovské množství pokusů o zneužití zranitelnosti v instalacích SharePoint našich zákazníků. Naši kluci neustále sledují nové hrozby a píší pravidla, aby chránili naše zákazníky.
Pravidlo, které ve čtvrtek způsobilo problém, mělo chránit před cross-site scripting (XSS). Podobné útoky jsou v posledních letech také mnohem častější.
Zdroj:
Standardním postupem pro změnu spravovaného pravidla pro WAF je provedení průběžného testování integrace (CI) před globálním nasazením. Minulý čtvrtek jsme to udělali a zavedli pravidla. Ve 13:31 podal strojník schválenou žádost o stažení se změnou.
Ve 13:37 TeamCity shromáždil pravidla, provedl testy a dal souhlas. Testovací sada WAF testuje základní funkčnost WAF a skládá se z velkého počtu jednotkových testů pro jednotlivé funkce. Po jednotkových testech jsme otestovali pravidla pro WAF pomocí velkého množství požadavků HTTP. HTTP požadavky kontrolují, které požadavky by měly být blokovány WAF (pro zachycení útoku) a které mohou být povoleny (aby se neblokovalo vše a zabránilo se falešným poplachům). Netestovali jsme však nadměrné využití procesoru a zkoumání protokolů předchozích sestavení WAF ukazuje, že doba provádění testu pravidel se nezvýšila a bylo obtížné podezřívat, že nebude dostatek zdrojů.
Testy prošly a TeamCity začal automaticky nasazovat změnu ve 13:42.
Rtuť
Pravidla WAF se zaměřují na okamžitou nápravu hrozeb, takže je nasazujeme pomocí distribuovaného úložiště klíč-hodnota společnosti Quicksilver, který globálně šíří změny během několika sekund. Všichni naši klienti tuto technologii využívají při změně konfigurace v dashboardu nebo přes API a právě díky ní na změny reagujeme bleskově.
O Quicksilveru jsme toho moc nemluvili. Dříve jsme používali jako globálně distribuovaný obchod klíč-hodnota, ale vyskytly se s ním provozní problémy a vytvořili jsme vlastní obchod replikovaný ve více než 180 městech. Nyní používáme Quicksilver k odesílání změn konfigurace klientům, aktualizaci pravidel WAF a distribuci kódu JavaScript napsaného klienty pracovníkům Cloudflare.
Od kliknutí na tlačítko na řídicím panelu nebo zavolání API po celosvětovou změnu konfigurace trvá jen několik sekund. Zákazníci tuto rychlost nastavení milovali. A Workers jim poskytuje téměř okamžité globální nasazení softwaru. V průměru šíří Quicksilver asi 350 změn za sekundu.
A Quicksilver je velmi rychlý. V průměru jsme dosáhli 99. percentilu 2,29 sekundy pro šíření změn do všech počítačů po celém světě. Rychlost je obvykle dobrá věc. Když totiž povolíte nějakou funkci nebo vymažete mezipaměť, stane se to téměř okamžitě a všude. Odesílání kódu prostřednictvím Cloudflare Workers probíhá stejnou rychlostí. Cloudflare svým zákazníkům slibuje rychlé aktualizace ve správný čas.
Ale v tomto případě si z nás rychlost zahrála krutou legraci a pravidla se změnila všude během pár sekund. Možná jste si všimli, že kód WAF používá Lua. Cloudflare hojně využívá Lua ve výrobě a detailech jsme . Lua používá WAF interně a použije backtracking pro párování. Nemá žádné mechanismy na ochranu před projevy, které se vymknou kontrole. Níže o tom budu mluvit více a co s tím děláme.
Před nasazením pravidel šlo vše hladce: požadavek na stažení byl vytvořen a schválen, kanál CI/CD shromáždil a otestoval kód, požadavek na změnu byl odeslán podle SOP, který řídí nasazení a vrácení, a nasazení bylo dokončeno.
Proces nasazení Cloudflare WAF
Něco se pokazilo
Jak jsem řekl, každý týden nasazujeme desítky nových pravidel WAF a máme zavedeno mnoho systémů na ochranu před negativními důsledky takového nasazení. A když se něco pokazí, většinou jde o souhru více okolností najednou. Pokud najdete jen jeden důvod, je to samozřejmě uklidňující, ale není to vždy pravda. To jsou důvody, které společně vedly k selhání naší služby HTTP/HTTPS.
- Inženýr napsal regulární výraz, který by mohl vést k nadměrnému .
- Funkce, která mohla zabránit tomu, aby regulární výraz plýtval příliš velkým množstvím CPU, byla omylem odstraněna při refaktorování WAF před několika týdny – refaktoring byl potřeba, aby WAF spotřeboval méně zdrojů.
- Modul regulárních výrazů neměl žádné záruky složitosti.
- Testovací sada nedokázala detekovat nadměrnou spotřebu CPU.
- SOP umožňuje, aby změny pravidel, které nejsou naléhavé, byly zavedeny globálně bez vícekrokového procesu.
- Plán návratu vyžadoval spuštění plného sestavení WAF dvakrát, což trvalo dlouho.
- První varování o globálních dopravních problémech bylo spuštěno příliš pozdě.
- Aktualizace stavové stránky nám chvíli trvala.
- Měli jsme problémy s přístupem k systémům kvůli závadě a postup bypassu nebyl dobře zaveden.
- Inženýři SRE ztratili přístup k některým systémům, protože jejich přihlašovací údaje z bezpečnostních důvodů vypršely.
- Naši zákazníci neměli přístup k řídicímu panelu nebo API Cloudflare, protože procházejí oblastí Cloudflare.
Co se od minulého čtvrtka změnilo
Nejprve jsme úplně zastavili veškerou práci na vydáních pro WAF a děláme následující:
- Znovu zavádíme ochranu proti nadměrnému využití CPU, kterou jsme odstranili. (připraveno)
- Ruční kontrola všech 3868 XNUMX pravidel ve spravovaných pravidlech pro WAF za účelem nalezení a nápravy dalších potenciálních případů nadměrného zpětného sledování. (Ověření dokončeno)
- Do testovací sady zahrnujeme profilování výkonu pro všechna pravidla. (Očekává se: 19. července)
- Přechod na modul regulárních výrazů nebo - oba poskytují záruky za běhu. (Očekává se: 31. července)
- Přepisujeme SOP, abychom nasazovali pravidla ve fázích, jako jiný software v Cloudflare, ale zároveň máme možnost nouzového globálního nasazení, pokud již útoky začaly.
- Vyvíjíme možnost urychleně odstranit řídicí panel a API Cloudflare z oblasti Cloudflare.
- Automatizace aktualizací stránek .
Dlouhodobě se vzdalujeme od Lua WAF, který jsem napsal před několika lety. Přesouvání WAF do . Tímto způsobem bude WAF rychlejší a získá další úroveň ochrany.
Závěr
Toto selhání způsobilo potíže nám i našim zákazníkům. Jednali jsme rychle, abychom situaci napravili, a nyní pracujeme na nedostatcích v procesech, které způsobily havárii, a také pracujeme ještě hlouběji, abychom se v budoucnu ochránili před potenciálními problémy s regulárními výrazy při migraci na novou technologii.
Velmi nás tento výpadek mrzí a omlouváme se našim zákazníkům. Doufáme, že tyto změny zajistí, že se něco podobného nebude opakovat.
Aplikace. Zpětné sledování regulárních výrazů
Abyste pochopili, jak výraz:
(?:(?:"|'|]|}||d
(?:nan|infinity|true|false|null|undefined|symbol|math)|`|-
|+)+[)]*;?((?:s|-|~|!|{}||||+)*.*(?:.*=.*)))spotřebovali všechny zdroje CPU, musíte vědět trochu o tom, jak funguje standardní modul regulárních výrazů. Problémem je zde vzorec .*(?:.*=.*). (?: a odpovídající ) je nezachycující skupina (tj. výraz v závorkách je seskupen jako jeden výraz).
V kontextu nadměrné spotřeby CPU lze tento vzorec popsat jako .*.*=.*. V této podobě vypadá vzor zbytečně složitě. Ale co je důležitější, v reálném světě mohou výrazy (jako složité výrazy v pravidlech WAF), které žádají motor, aby odpovídal fragmentu následovanému dalším fragmentem, vést ke katastrofálnímu zpětnému sledování. A právě proto.
V regulárním výrazu . znamená, že potřebujete najít jeden znak, .* - spárujte nula nebo více znaků "chtivě", to znamená, že zachytíte maximum znaků, takže .*.*=.* znamená shodu nula nebo více znaků, potom nula nebo více znaků, najděte literál = znak, shodu nula nebo více znaků.
Vezměme si testovací linku x=x. Odpovídá to výrazu .*.*=.*. .*.* než se rovnítko shoduje s prvním x (jedna ze skupin .* odpovídá xa druhý - nula znaků). .* po = zápasy poslední x.
Toto srovnání vyžaduje 23 kroků. První skupina .* в .*.*=.* působí nenasytně a odpovídá celému řetězci x=x. Motor se přesune do další skupiny .*. Nemáme žádné další postavy, které by se shodovaly, takže druhá skupina .* odpovídá nule znaků (toto je povoleno). Poté se motor přesune na znamení =. Nejsou zde žádné další symboly (první skupina .* použil celý výraz x=x), nedochází k žádnému srovnání.
A pak se modul regulárních výrazů vrátí na začátek. Přechází do první skupiny .* a porovnává to с x= (místo x=x), a pak se ujme druhé skupiny .*. Druhá skupina .* se srovnává s druhým xa opět nám nezůstaly žádné postavy. A když motor zase dosáhne = в .*.*=.*, nic nefunguje. A znovu se vrací zpět.
Tentokrát skupina .* stále odpovídá x=, ale druhá skupina .* už ne xa nula znaků. Motor se snaží najít doslovný charakter = ve vzoru .*.*=.*, ale nevychází (ostatně první skupina ho už obsadila .*). A znovu se vrací zpět.
Tentokrát první skupina .* trvá pouze první x. Ale ta druhá skupina .* „chtivě“ chytá =x. Už jste tušili, co se stane? Motor se snaží rovnat doslovu =, selže a provede další backtracking.
První skupina .* stále odpovídá prvnímu x... Druhý .* pouze bere =. Motor se samozřejmě nemůže rovnat doslovu =, protože druhá skupina to již udělala .*. A opět zpětný chod. A my se snažíme porovnat řetězec tří znaků!
V důsledku toho první skupina .* odpovídá pouze prvnímu x, druhý .* - s nulovými znaky a engine konečně odpovídá doslovu = ve výrazu с = v souladu. Následuje poslední skupina .* je porovnán s posledním x.
23 kroků pouze pro x=x. Podívejte se na krátké video o používání Perlu , který ukazuje, jak dochází ke krokům a zpětnému sledování.
To už je hodně práce, ale co kdyby místo toho x=x budeme mít x=xx? To je 33 kroků. A pokud x=xxx? 45. Vztah není lineární. Graf ukazuje srovnání z x=x na x=xxxxxxxxxxxxxxxxxxxx (20 x po =). Pokud máme 20 x po =, motor dokončí párování v 555 krocích! (Navíc, pokud jsme prohráli x= a řetězec se jednoduše skládá z 20 x, motor provede 4067 kroků, aby pochopil, že neexistují žádné shody).
Toto video ukazuje všechny backtracking pro srovnání x=xxxxxxxxxxxxxxxxxxxx:
Problém je v tom, že jak se zvětšuje velikost řetězce, doba shody roste superlineárně. Ale věci se mohou ještě zhoršit, pokud je regulární výraz mírně upraven. Řekněme, že jsme měli .*.*=.*; (to znamená, že na konci vzoru byl doslovný středník). Například, aby odpovídal výrazu jako foo=bar;.
A tady by zpětný chod byl skutečnou katastrofou. Pro srovnání x=x bude to trvat 90 kroků, ne 23. A toto číslo rychle roste. Srovnávat x= a 20 x, je potřeba 5353 kroků. Tady je graf. Podívejte se na hodnoty os Y oproti předchozímu grafu.
Pokud máte zájem, podívejte se na všech 5353 XNUMX neúspěšných kroků přiřazování x=xxxxxxxxxxxxxxxxxxxx и .*.*=.*;
Použitím líného spíše než chamtivého párování lze ovládat rozsah zpětného sledování. Změníme-li původní výraz na .*?.*?=.*?, pro srovnání x=x bude to trvat 11 kroků (ne 23). Pokud jde o x=xxxxxxxxxxxxxxxxxxxx. Všechno proto ? po .* říká enginu, aby před pokračováním odpovídal minimálnímu počtu znaků.
Ale líná mapování problém zpětného sledování zcela nevyřeší. Pokud nahradíme katastrofický příklad .*.*=.*; na .*?.*?=.*?;, doba provedení zůstane stejná. x=x stále vyžaduje 555 kroků a x= a 20 x - 5353.
Jediná věc, kterou lze udělat (kromě úplného přepsání vzoru pro větší specifičnost), je opustit motor regulárních výrazů s jeho mechanismem zpětného sledování. To je to, co budeme dělat v příštích několika týdnech.
Řešení tohoto problému je známé již od roku 1968, kdy Kent Thompson napsal článek („Metody programování: Algoritmus vyhledávání regulárních výrazů“). Článek popisuje mechanismus, který umožňuje převést regulární výraz na nedeterministické konečné automaty a po změnách stavu v nedeterministických konečných automatech použít algoritmus, jehož doba provádění závisí lineárně na shodném řetězci.
Metody programování
Algoritmus hledání regulárních výrazů
Ken Thompson
Bell Telephone Laboratories, Inc., Murray Hill, New JerseyPopisuje metodu pro vyhledávání konkrétního řetězce znaků v textu a pojednává o implementaci této metody ve formě překladače. Kompilátor vezme regulární výraz jako zdrojový kód a vytvoří program IBM 7094 jako objektový kód. Objektový program přijímá vstup ve formě hledaného textu a vysílá signál pokaždé, když je řetězec textu porovnán s daným regulárním výrazem. Článek obsahuje příklady, problémy a řešení.
Algoritmus
Předchozí vyhledávací algoritmy vedly ke zpětnému sledování, pokud částečně úspěšné vyhledávání nepřineslo výsledek.V režimu kompilace algoritmus nepracuje se symboly. Předává instrukce kompilovanému kódu. Provedení je velmi rychlé – po předání dat na začátek aktuálního seznamu automaticky vyhledá všechny možné po sobě jdoucí znaky v regulárním výrazu.
Algoritmus kompilace a vyhledávání je součástí textového editoru pro sdílení času jako kontextové vyhledávání. Samozřejmě to není zdaleka jediná aplikace takového vyhledávacího postupu. Například varianta tohoto algoritmu se používá jako vyhledávání symbolů v tabulce v assembleru.
Předpokládá se, že čtenář zná regulární výrazy a počítačový programovací jazyk IBM 7094.Kompilátor
Kompilátor se skládá ze tří paralelně běžících fází. První fází je syntaktické filtrování, které umožňuje průchod pouze syntakticky správným regulárním výrazům. Tento krok také vloží operátor "·", aby odpovídal regulárním výrazům. Ve druhém kroku je regulární výraz převeden do postfixové podoby. Ve třetí fázi je vytvořen objektový kód. První 2 fáze jsou zřejmé a nebudeme se jimi zabývat.
Thompsonův článek nehovoří o nedeterministických konečných strojích, ale dobře vysvětluje algoritmus lineárního času a představuje program ALGOL-60, který generuje kód assembleru pro IBM 7094. Implementace je složitá, ale myšlenka je velmi jednoduchá.
aktuální vyhledávací cesta. Je reprezentován ikonou ⊕ s jedním vstupem a dvěma výstupy.
Obrázek 1 ukazuje funkce třetího kompilačního kroku při transformaci příkladu regulárního výrazu. První tři znaky v příkladu jsou a, b, c a každý vytváří položku zásobníku S[i] a pole NNODE.NNODE na existující kód pro generování výsledného regulárního výrazu v jedné položce zásobníku (viz obrázek 5)
Takto by vypadal regulární výraz .*.*=.*, pokud si to představíte jako na obrázcích z Thompsonova článku.
Na Obr. 0 je pět stavů začínajících od 0 a 3 cykly začínající od stavů 1, 2 a 3. Tyto tři cykly odpovídají třem .* v regulárním výrazu. 3 ovály s tečkami odpovídají jednomu symbolu. Oválný se znakem = odpovídá doslovnému znaku =. Stav 4 je konečný. Pokud ho dosáhneme, pak se regulární výraz shoduje.
Chcete-li vidět, jak lze takový stavový diagram použít pro párování regulárních výrazů .*.*=.*, podíváme se na párování řetězců x=x. Program začíná od stavu 0, jak je znázorněno na obr. 1.
Aby tento algoritmus fungoval, musí být stavový automat v několika stavech současně. Nedeterministický konečný stroj provede všechny možné přechody současně.
Než stihne načíst vstupní data, přejde do obou prvních stavů (1 a 2), jak je znázorněno na Obr. 2.
Na Obr. 2 ukazuje, co se stane, když se podívá na první x в x=x. x může mapovat k nejvyššímu bodu, přecházet ze stavu 1 a zpět do stavu 1. Or x může mapovat do bodu níže, přecházet ze stavu 2 a zpět do stavu 2.
Po porovnání prvního x в x=x stále jsme ve stavech 1 a 2. Nemůžeme dosáhnout stavu 3 nebo 4, protože potřebujeme doslovný znak =.
Algoritmus pak uvažuje = в x=x. Stejně jako x před tím, může být přiřazen k jedné ze dvou horních smyček ze stavu 1 do stavu 1 nebo ze stavu 2 do stavu 2, ale algoritmus může odpovídat doslovu = a přejít ze stavu 2 do stavu 3 (a hned 4). To je znázorněno na Obr. 3.
Algoritmus pak přejde k poslednímu x в x=x. Ze stavu 1 a 2 jsou možné stejné přechody zpět do stavu 1 a 2. Ze stavu 3 x může odpovídat bodu napravo a vrátit se do stavu 3.
V této fázi každá postava x=x zvážil, a protože jsme dosáhli stavu 4, regulární výraz tomuto řetězci odpovídá. Každý znak je zpracován jednou, takže tento algoritmus je lineární v délce vstupního řetězce. A žádné couvání.
Je zřejmé, že po dosažení stavu 4 (když se algoritmus shoduje x=) se shoduje celý regulární výraz a algoritmus se může ukončit, aniž by to vůbec vzal v úvahu x.
Tento algoritmus závisí lineárně na velikosti vstupního řetězce.
Zdroj: www.habr.com