Prije skoro 9 godina Cloudflare je bila mala kompanija i ja nisam radio za nju, bio sam samo kupac. Mjesec dana nakon lansiranja Cloudflarea, dobio sam upozorenje da je na mojoj stranici DNS izgleda ne radi. Cloudflare je promijenio/la promjenu u , i došlo je do pokvarenog DNS-a.
Odmah sam poslao mejl Matthewu Princeu s naslovom "Gdje je moj DNS?", a on je poslao dugačak odgovor pun tehničkih detalja (), na šta sam odgovorio:
Od: John Graham-Cumming
Datum: 7. oktobar 2010. u 9:14
Predmet: Re: Gdje je moj DNS?
Za: Matthew PrinceSuper izvještaj, hvala. Svakako ću zvati ako bude problema. Vjerojatno vrijedi napisati post o tome kada prikupite sve tehničke informacije. Mislim da će se ljudima svidjeti otvorena i iskrena priča. Pogotovo ako mu priložite grafikone koji pokazuju kako je promet porastao od lansiranja.
Imam dobar nadzor na svom sajtu i dobijam SMS o svakom kvaru. Monitoring pokazuje da je kvar bio od 13:03:07 do 14:04:12. Testovi se izvode svakih pet minuta.
Siguran sam da ćeš sve shvatiti. Jeste li sigurni da vam ne treba vaša osoba u Evropi? 🙂
A on je odgovorio:
Od: Matthew Prince
Datum: 7. oktobar 2010. u 9:57
Predmet: Re: Gdje je moj DNS?
Za: John Graham-CummingHvala ti. Odgovorili smo svima koji su pisali. Upravo sam na putu za ured i napisat ćemo nešto na blogu ili zakačiti službenu objavu na našoj oglasnoj tabli. Potpuno se slazem, iskrenost je sve.
Sada je Cloudflare zaista velika kompanija, ja radim za nju, a sada moram otvoreno pisati o našoj grešci, njenim posljedicama i našim postupcima.
Događaji 2. jula
2. jula smo uveli novo pravilo u Upravljanim pravilima za WAF, zbog čega na svakom procesorskom jezgru koje rukuje HTTP/HTTPS saobraćajem na Cloudflare mreži širom svijeta. Stalno poboljšavamo upravljana pravila za WAF kao odgovor na nove ranjivosti i prijetnje. U maju smo, na primjer, požurili za zaštitu od ozbiljne ranjivosti u SharePointu. Čitava suština našeg WAF-a je sposobnost brzog i globalnog uvođenja pravila.
Nažalost, ažuriranje od prošlog četvrtka sadržalo je regex koji je koristio previše CPU-a dodijeljenog HTTP/HTTPS-u za vraćanje unazad. Naše osnovne funkcije proxyja, CDN i WAF su patile od ovoga. Grafikon pokazuje da CPU resursi za opsluživanje HTTP/HTTS prometa dostižu skoro 100% na serverima u našoj mreži.
Upotreba CPU-a u jednoj tački prisutnosti tokom incidenta
Kao rezultat toga, naši klijenti (i klijenti naših klijenata) su naišli na stranicu o grešci 502 na Cloudflare domenima. 502 greške su generisali Cloudflare-ovi front-end web serveri, koji su još uvijek imali slobodna jezgra, ali nisu mogli komunicirati s procesima koji rukuju HTTP/HTTPS prometom.
Znamo koliko je to neugodnosti izazvalo našim klijentima. Strašno nas je sramota. I ovaj neuspjeh nas je spriječio da se efikasno pozabavimo incidentom.
Ako ste bili jedan od tih klijenata, sigurno ste bili uplašeni, ljuti i frustrirani. Štaviše, nismo imali 6 godina . Visoka upotreba CPU-a bila je zbog jednog WAF pravila sa loše sročenim regularnim izrazom koji je rezultirao prekomjernim vraćanjem unazad. Evo krivog izraza: (?:(?:"|'|]|}||d|(?:nan|infinity|true|false|null|undefined|symbol|math)|`|-|+)+[)]*;?((?:s|-|~|!|{}||||+)*.*(?:.*=.*)))
Iako je zanimljivo sam po sebi (a ja ću ga detaljnije obraditi u nastavku), Cloudflare-ovo 27-minutno zamračenje nije bilo samo zbog lošeg regularnog izraza. Trebalo nam je vremena da opišemo slijed događaja koji su doveli do pada, tako da nismo brzo reagirali. Na kraju posta ću opisati vraćanje unazad u regularnom izrazu i reći vam šta da radite s tim.
Šta se desilo
Počnimo redom. Sva vremena ovdje su u UTC.
U 13:42, inženjer iz tima za firewall napravio je malu promjenu u pravilima za otkrivanje kroz automatski proces. Shodno tome, kreiran je tiket zahtjeva za promjenu. Takve karte upravljamo preko Jira (snimka ekrana ispod).
Nakon 3 minuta, pojavila se prva stranica PagerDuty-a, koja je prijavila problem sa WAF-om. Ovo je bio sintetički benchmark koji testira funkcionalnost WAF-ova (imamo ih na stotine) izvan Cloudflarea kako bi provjerio normalan rad. Odmah nakon toga uslijedile su stranice neuspjeha drugih end-to-end testova Cloudflare usluga, problemi sa globalnim prometom, široko rasprostranjene greške 502 i gomila izvještaja iz naših tačaka prisutnosti (PoP) u gradovima širom svijeta koji su ukazivali na nedostatak procesorskih resursa.
Primio sam nekoliko ovih upozorenja, izletio sam sa sastanka i krenuo prema stolu kada je naš voditelj razvoja rješenja rekao da smo izgubili 80% prometa. Otrčao sam do naših SRE inženjera koji su već radili na problemu. Prvo smo mislili da se radi o nekom nepoznatom napadu.
Cloudflare SRE inženjeri su raštrkani širom svijeta i prate situaciju 0 sata dnevno. Tipično, ova upozorenja obavještavaju o specifičnim lokalnim problemima ograničenog opsega, prate se na internim nadzornim pločama i rješavaju se mnogo puta dnevno. Ali takve stranice i obaveštenja ukazivali su na nešto zaista ozbiljno, a SRE inženjeri su odmah proglasili nivo ozbiljnosti PXNUMX i obratili se inženjerima menadžmenta i sistema.
Naši londonski inženjeri su u tom trenutku slušali predavanje u glavnoj sali. Predavanje je moralo biti prekinuto, svi su se okupili u velikoj konferencijskoj sali, a pozvano je još specijalista. Ovo nije bio uobičajen problem sa kojim bi SRE mogli sami da se izbore. Bilo je potrebno hitno povezati prave stručnjake.
U 14:00 smo utvrdili da je problem u WAF-u i da nije bilo napada. Tim za performanse je izvukao podatke CPU-a i postalo je jasno da je za to kriv WAF. Drugi zaposlenik je potvrdio ovu teoriju koristeći strace. Neko drugi je vidio u evidenciji da postoji problem sa WAF-om. U 14:02, cijeli tim je došao kod mene kada je predloženo korištenje globalnog ubijanja, mehanizma ugrađenog u Cloudflare koji isključuje jednu komponentu širom svijeta.
Druga je priča kako smo radili globalno ubijanje za WAF. Nije tako jednostavno. Koristimo vlastite proizvode, a od našeg servisa nije radilo, nismo se mogli autentifikovati i prijaviti na internu kontrolnu tablu (kada je sve bilo popravljeno, saznali smo da su neki članovi tima izgubili pristup zbog sigurnosne funkcije koja onemogućuje vjerodajnice ako se interna kontrolna tabla ne koristi duže vrijeme) .
I nismo mogli doći do naših internih usluga poput Jira ili sistema izgradnje. Bilo je potrebno zaobilazno rešenje koje smo retko koristili (i ovo će morati da se razradi). Konačno, jedan inženjer je uspio prekinuti WAF u 14:07, a u 14:09, promet i nivoi procesora su se svuda vratili u normalu. Ostatak sigurnosnih mehanizama Cloudflarea radio je normalno.
Onda smo počeli da obnavljamo WAF. Situacija je bila neuobičajena, pa smo radili negativne testove (pitajući se da li je ova promjena zaista problem) i pozitivne testove (uvjeravajući se da vraćanje funkcionira) u jednom gradu s odvojenim prometom, prebacujući plaćene korisnike odatle.
U 14:52 smo se uvjerili da smo razumjeli uzrok i izvršili ispravku i ponovo uključili WAF.
Kako radi Cloudflare
Cloudflare ima tim inženjera posvećenih upravljanju pravilima za WAF-ove. Nastoje poboljšati stopu otkrivanja, smanjiti lažne pozitivne rezultate i brzo odgovoriti na nove prijetnje kako se pojave. U posljednjih 60 dana obrađeno je 476 zahtjeva za promjenu upravljanih pravila za WAF (u prosjeku jedan svaka 3 sata).
Ovu konkretnu promjenu trebalo je primijeniti u simulacijskom načinu, gdje stvarni klijentski promet prolazi kroz pravilo, ali ništa nije blokirano. Ovaj način rada koristimo za testiranje učinkovitosti pravila i mjerenje omjera lažno pozitivnih i lažno negativnih. Ali čak i u simulacionom režimu, pravila se moraju stvarno izvršiti, a u ovom slučaju, pravilo je sadržalo regularni izraz koji je trošio previše resursa procesora.
Kao što možete vidjeti iz gornjeg zahtjeva za promjenom, imamo plan implementacije, plan vraćanja unatrag i vezu do interne standardne operativne procedure (SOP) za ovu vrstu implementacije. SOP za izmjenu pravila dozvoljava njegovo objavljivanje globalno. Zapravo, u Cloudflareu je sve uređeno sasvim drugačije, a SOP nalaže da se softver za testiranje i internu upotrebu prvo preda internoj tački prisutnosti (PoP) (koju naši zaposleni koriste), a zatim malom broju klijenata u izolovanoj lokaciji, zatim velikom broju klijenata, pa tek onda širom sveta.
Evo kako to izgleda. Mi koristimo git interno preko BitBucketa. Inženjeri koji rade na promjenama šalju kod koji je napravljen u TeamCity, a kada izgradnja prođe, dodjeljuju se recenzenti. Kada se zahtjev za povlačenjem odobri, kod se kompajlira i izvodi se serija testova (ponovo).
Ako se izgradnja i testovi uspješno završe, u Jira se kreira zahtjev za promjenom i promjenu mora odobriti odgovarajući menadžer ili voditelj. Nakon odobrenja, postavlja se u takozvanu "PoP menažeriju": PAS, SVINJA i (pas, svinja i kanarinac).
DOG PoP je Cloudflare PoP (kao i svaki drugi naš grad) koji koriste samo zaposleni u Cloudflareu. PoP za internu upotrebu omogućava vam da uhvatite probleme čak i prije nego što promet korisnika počne ulaziti u rješenje. Korisna stvar.
Ako PAS test prođe, kod prelazi na fazu PIG (zamorac). Ovo je Cloudflare PoP, gdje mala količina besplatnog klijentskog prometa prolazi kroz novi kod.
Ako je sve u redu, kod ide na Canary. Imamo tri Canary PoP-a u različitim dijelovima svijeta. U njima promet plaćenih i besplatnih klijenata prolazi kroz novi kod, a ovo je posljednja provjera grešaka.
Proces izdavanja softvera u Cloudflareu
Ako je kod u redu na Canary-u, otpuštamo ga. Prolazak kroz sve faze - PAS, SVINJA, Kanarinac, cijeli svijet - traje nekoliko sati ili dana, ovisno o promjeni koda. Zbog raznolikosti Cloudflare mreže i klijenata, temeljno testiramo kod prije globalnog izdanja za sve klijente. Ali WAF posebno ne prati ovaj proces jer se s prijetnjama treba brzo nositi.
WAF Threats
U posljednjih nekoliko godina došlo je do značajnog porasta prijetnji redovnim aplikacijama. To je zbog veće dostupnosti alata za testiranje softvera. Na primjer, nedavno smo pisali o tome ).
izvor:
Vrlo često se napravi dokaz koncepta koji se odmah objavi na Githubu kako bi timovi koji održavaju aplikaciju mogli brzo da je testiraju i uvjere da je adekvatno osigurana. Stoga, Cloudflare mora biti u stanju odgovoriti na nove napade što je brže moguće kako bi korisnici imali priliku popraviti svoj softver.
Odličan primjer brzog odgovora od Cloudflarea je uvođenje zaštite od SharePoint ranjivosti u maju (). Gotovo odmah nakon objavljivanja najava, primijetili smo veliki broj pokušaja iskorištavanja ranjivosti u SharePoint instalacijama naših korisnika. Naši momci stalno prate nove prijetnje i pišu pravila kako bi zaštitili naše klijente.
Pravilo koje je izazvalo problem u četvrtak trebalo je da zaštiti od skriptovanja na više lokacija (XSS). Ovakvih napada je također bilo mnogo više posljednjih godina.
izvor:
Standardna procedura za izmjenu WAF upravljanog pravila je testiranje kontinuirane integracije (CI) prije globalne implementacije. To smo uradili prošlog četvrtka i uveli pravila. U 13:31, jedan inženjer je podnio odobreni zahtjev za povlačenjem sa izmjenom.
U 13:37 TeamCity je prikupio pravila, izvršio testove i dao zeleno svjetlo. WAF test paket testira osnovnu funkcionalnost WAF-a i sastoji se od velikog broja jediničnih testova za pojedinačne funkcije. Nakon jediničnog testiranja, testirali smo WAF pravila sa ogromnim brojem HTTP zahtjeva. HTTP zahtjevi provjeravaju koje zahtjeve treba blokirati od strane WAF-a (da bi se presreo napad) i kojim zahtjevima treba dozvoliti da prođu (kako ne bi blokirali sve po redu i izbjegli lažne pozitivne rezultate). Ali nismo pokrenuli testove za prekomjernu upotrebu CPU-a, a gledanje dnevnika prethodnih verzija WAF-a pokazuje da se vrijeme za pokretanje testova s pravilom nije povećalo i teško je posumnjati da neće biti dovoljno resursa .
Testovi su prošli i TeamCity je počeo automatski implementirati promjenu u 13:42.
živa
Pravila WAF-a su dizajnirana za brzo rješavanje prijetnji, zbog čega ih implementiramo koristeći Quicksilverov distribuirani ključ/vrijednost spremišta, koja globalno širi promjene u sekundama. Svi naši klijenti koriste ovu tehnologiju kada mijenjaju konfiguraciju na kontrolnoj tabli ili preko API-ja, a zahvaljujući njoj na promjene reagiramo munjevitom brzinom.
Nismo puno pričali o Quicksilveru. Ranije smo koristili kao globalno distribuirana trgovina ključ/vrijednost, ali je naišla na operativne probleme i napisali smo vlastitu prodavnicu repliciranu u preko 180 gradova. Sada koristimo Quicksilver da prenesemo promjene konfiguracije klijentima, ažuriramo WAF pravila i distribuiramo klijentski napisani JavaScript na Cloudflare Workers.
Od klika na dugme na kontrolnoj tabli ili pozivanja API-ja do promene konfiguracije širom sveta, potrebno je samo nekoliko sekundi. Kupci vole ovu brzinu podešavanja. A Workers im omogućava skoro trenutnu globalnu implementaciju softvera. U prosjeku Quicksilver širi oko 350 promjena u sekundi.
A Quicksilver je veoma brz. U prosjeku smo dostigli 99. percentil od 2,29 sekundi da prenesemo promjene na svaki računar širom svijeta. Obično je brzina dobra. Na kraju krajeva, kada uključite funkciju ili obrišete keš memoriju, to se dešava gotovo trenutno i svuda. Slanje koda preko Cloudflare Workers-a odvija se istom brzinom. Cloudflare svojim korisnicima obećava brza ažuriranja u pravo vrijeme.
Ali u ovom slučaju, brzina nam je izigrala okrutan trik, a pravila su se svuda promijenila za nekoliko sekundi. Možda ste primijetili da WAF kod koristi Lua. Cloudflare intenzivno koristi Lua u proizvodnji i detaljima mi smo . Lua WAF koristi unutra i primjenjuje vraćanje unazad za uparivanje. Nema mehanizme za zaštitu od nekontrolisanih izraza. U nastavku ću detaljnije o tome io tome šta radimo po tom pitanju.
Prije nego što su pravila implementirana, sve je išlo glatko: kreiran je i odobren zahtjev za povlačenje, CI/CD cevovod je izgrađen i testiran kod, podnet je zahtjev za promjenu u skladu sa SOP-om koji reguliše implementaciju i vraćanje, a implementacija je završena .
Cloudflare WAF proces implementacije
Nešto je pošlo po zlu
Kao što sam već rekao, svake nedelje uvodimo desetine novih pravila WAF-a i imamo mnogo sistema za zaštitu od negativnih efekata takvog uvođenja. A kada nešto krene po zlu, obično je to kombinacija nekoliko okolnosti odjednom. Ako nađete samo jedan razlog, ovo je, naravno, umirujuće, ali nije uvijek tačno. Evo razloga koji su zajedno doveli do neuspjeha naše HTTP/HTTPS usluge.
- Inženjer je napisao regularni izraz koji može dovesti do pretjeranog .
- Funkcija koja je mogla spriječiti regularni izraz da prekomjerno koristi CPU greškom je uklonjena tokom WAF prerade nekoliko sedmica ranije - refaktorisanje je bilo potrebno da bi WAF trošio manje resursa.
- Mehanizam regularnih izraza nije imao garancije složenosti.
- Testni paket nije mogao otkriti prekomjernu potrošnju CPU-a.
- SOP omogućava da se promjene pravila koje nisu hitne implementiraju globalno bez procesa u više koraka.
- Plan vraćanja je zahtijevao punu verziju WAF-a dvaput, što je dugo vremena.
- Prvo upozorenje o globalnom saobraćajnom problemu stiglo je prekasno.
- Bili smo spori sa ažuriranjem stranice statusa.
- Imali smo problema s pristupom sistemima zbog kvara, a procedura zaobilaženja nije bila dobro uvježbana.
- SRE inženjeri su izgubili pristup nekim sistemima jer su im akreditivi istekli iz sigurnosnih razloga.
- Naši klijenti nisu imali pristup Cloudflare Dashboard-u ili API-ju jer prolaze kroz Cloudflare regiju.
Šta se promijenilo od prošlog četvrtka
Prvo, potpuno smo zaustavili sav rad na izdanjima za WAF i uradili sljedeće:
- Ponovno uvođenje zaštite od prekomjerne potrošnje procesorskih resursa, koju smo uklonili. (spreman)
- Ručna provjera svih 3868 pravila u WAF upravljanim pravilima kako bi se pronašli i popravili drugi potencijalni slučajevi prekomjernog vraćanja unazad. (Provjera završena)
- Uključite profiliranje performansi za sva pravila u test paketu. (Očekivano: 19. jul)
- Prelazak na mehanizam regularnih izraza ili Oba obezbeđuju garancije u runtime okruženju. (Očekivano: 31. jul)
- Prepisivanje SOP-a za implementaciju pravila u fazama, kao i drugi softver u Cloudflareu, ali i dalje biti u mogućnosti globalno implementirati hitne slučajeve ako su napadi već počeli.
- Razvijamo mogućnost hitnog uklanjanja Cloudflare kontrolne ploče i API-ja iz Cloudflare regije.
- Automatizirajte osvježavanje stranice .
Dugoročno, mi se udaljavamo od Lua WAF-a koji sam napisao prije nekoliko godina. Premještanje WAF-a na . Tako će WAF biti brži i dobiti dodatni sloj zaštite.
zaključak
Ovaj kvar je izazvao probleme za nas i naše kupce. Brzo smo odgovorili kako bismo ispravili situaciju i trenutno radimo na nedostacima u procesima koji su uzrokovali pad, kao i još dublje da bismo se zaštitili od potencijalnih problema s regularnim izrazom u budućnosti prelaskom na novu tehnologiju.
Veoma se stidimo ovog neuspjeha i izvinjavamo se našim klijentima. Nadamo se da će ove promjene osigurati da se ovo više ne ponovi.
Aplikacija. Povratak na regularne izraze
Da biste razumjeli kako je izraz:
(?:(?:"|'|]|}||d
(?:nan|infinity|true|false|null|undefined|symbol|math)|`|-
|+)+[)]*;?((?:s|-|~|!|{}||||+)*.*(?:.*=.*)))Kada potrošite sve resurse CPU-a, morate znati nešto o tome kako radi standardni mehanizam regularnih izraza. Problem je ovdje u obrascu .*(?:.*=.*). (?: i odgovarajući ) je grupa koja ne hvata (to jest, izraz u zagradi je grupisan kao jedan izraz).
U kontekstu prekomjerne potrošnje procesorskih resursa, ovaj obrazac se može označiti kao .*.*=.*. U ovom obliku, uzorak izgleda nepotrebno složeno. Ali što je još važnije, u stvarnom svijetu, takvi izrazi (poput složenih izraza u pravilima WAF-a) koji traže od motora da uskladi fragment nakon kojeg slijedi drugi fragment mogu dovesti do katastrofalnog vraćanja nazad. I zato.
U regularnom izrazu . znači podudaranje s jednim znakom, .* - podudaranje nula ili više znakova "pohlepno", odnosno hvatanje maksimalnog broja znakova, tako da .*.*=.* znači podudaranje nula ili više znakova, zatim podudaranje nula ili više znakova, pronalaženje literalnog znaka =, podudaranje nula ili više znakova.
Uzmimo probni niz x=x. Odgovara izrazu .*.*=.*. .*.* prije nego se znak jednakosti poklopi s prvim x (jedna od grupa .* odgovara x, a drugi - na nulu znakova). .* poslije = posljednja utakmica x.
Za takvo poređenje potrebna su 23 koraka. Prva grupa .* в .*.*=.* djeluje pohlepno i odgovara cijelom nizu x=x. Motor prelazi u sljedeću grupu .*. Nemamo više likova za podudaranje, tako da je druga grupa .* odgovara nula znakova (ovo je dozvoljeno). Zatim motor ide na znak =. Nema više simbola (prva grupa .* upotrebio ceo izraz x=x), nema podudaranja.
I ovdje se mehanizam regularnih izraza vraća na početak. On ide u prvu grupu .* i poredi ga с x= (umesto x=x), a zatim preuzima drugu grupu .*. Druga grupa .* u poređenju sa drugom x, i opet nemamo više znakova. I kada motor ponovo stigne = в .*.*=.*, ništa ne radi. I opet se povlači.
Ovaj put grupa .* i dalje odgovara x=, ali druga grupa .* dosta x, i nula znakova. Motor pokušava pronaći doslovni lik = u obrascu .*.*=.*, ali ne izlazi (jer ga je već preuzela prva grupa .*). I opet se vraća.
Ovaj put prva grupa .* uzima samo prvi x. Ali druga grupa .* "pohlepno" hvata =x. Jeste li već pogodili šta će se dogoditi? Motor pokušava uskladiti literal =, ne uspijeva i ponovo se vraća nazad.
Prva grupa .* i dalje odgovara prvom x... Drugi .* uzima samo =. Naravno, motor se ne može mjeriti s literalom =, jer je druga grupa to već uradila .*. I opet nazad. I pokušavamo da uskladimo niz od tri karaktera!
Kao rezultat, prva grupa .* odgovara samo prvom x, sekunda .* - sa nula znakova, a motor konačno odgovara doslovnom = u izrazu с = U redu. Sljedeća je posljednja grupa .* u poređenju sa poslednjim x.
23 koraka samo za x=x. Pogledajte kratak video o korištenju Perla , koji pokazuje kako se koraci i vraćanje dešavaju.
Ovo je već puno posla, ali šta ako umjesto toga x=x imaćemo x=xx? To je 33 koraka. I ako x=xxx? 45. Ovisnost nije linearna. Grafikon prikazuje poređenje od x=x do x=xxxxxxxxxxxxxxxxxxxx (20 x после =). Ako imamo 20 x nakon =, motor radi uparivanje u 555 koraka! (Štaviše, ako smo izgubili x= a niz se sastoji samo od 20 x, motor će napraviti 4067 koraka da shvati da nema podudaranja).
Ovaj video prikazuje sve vraćanje unazad za poređenje x=xxxxxxxxxxxxxxxxxxxx:
Problem je u tome što kako se veličina stringa povećava, vrijeme podudaranja raste superlinearno. Ali stvari mogu postati još gore ako se regularni izraz malo izmijeni. Recimo da smo imali .*.*=.*; (to jest, na kraju obrasca je bila doslovna tačka i zarez). Na primjer, za podudaranje s izrazom kao što je foo=bar;.
I ovdje bi povlačenje bilo prava katastrofa. Za poređenje x=x potrebno je 90 koraka, a ne 23. I taj broj brzo raste. Uporediti x= i 20 x, potrebno vam je 5353 koraka. Evo grafikona. Pogledajte vrijednosti duž ose Y u poređenju sa prethodnim grafikonom.
Ako ste zainteresirani, pogledajte svih 5353 neuspjelih koraka uparivanja x=xxxxxxxxxxxxxxxxxxxx и .*.*=.*;
Korištenjem "lijenog" umjesto "pohlepnog" uparivanja, količina vraćanja se može kontrolisati. Ako promijenimo originalni izraz u .*?.*?=.*?, za podudaranje x=x potrebno je 11 koraka (a ne 23). Kao za x=xxxxxxxxxxxxxxxxxxxx... Sve zato ? после .* govori motoru da odgovara minimalnom broju znakova prije nego što krene dalje.
Ali lijena mapiranja ne rješavaju u potpunosti problem vraćanja unatrag. Ako zamijenimo katastrofalan primjer .*.*=.*; na .*?.*?=.*?;, vrijeme izvršenja će ostati isto. x=x još uvijek zahtijeva 555 koraka, i x= i 20 x - 5353.
Jedina stvar koja se može učiniti (osim potpunog ponovnog pisanja uzorka radi više specifičnosti) je napustiti mehanizam regularnih izraza sa njegovim mehanizmom za vraćanje nazad. To je ono što ćemo raditi u narednih nekoliko sedmica.
Rješenje ovog problema poznato je još od 1968. godine, kada je Kent Thompson napisao članak ("Metode programiranja: Algoritam pretraživanja regularnog izraza"). Članak opisuje mehanizam koji vam omogućava da konvertujete regularni izraz u nedeterminističke konačne automate, a nakon promjena stanja u nedeterminističkim konačnim automatima, koristite algoritam čije vrijeme izvršavanja linearno ovisi o podudarnom nizu.
Metode programiranja
Algoritam pretraživanja regularnog izraza
Ken Thompson
Bell Telephone Laboratories, Inc., Murray Hill, NJOvo opisuje metodu za traženje određenog niza znakova u tekstu i razmatra implementaciju ove metode u obliku kompajlera. Kompajler uzima regularni izraz kao izvorni kod i generira IBM 7094 program kao objektni kod. Objektni program uzima ulaz u obliku teksta za pretraživanje i emituje signal svaki put kada se niz teksta podudara sa datim regularnim izrazom. Članak daje primjere, probleme i rješenja.
Algoritam
Prethodni algoritmi pretraživanja rezultirali su vraćanjem unatrag ako djelomično uspješno pretraživanje nije uspjelo.U načinu kompilacije, algoritam ne radi sa simbolima. On prosljeđuje upute kompajliranom kodu. Izvršenje je vrlo brzo - nakon prosljeđivanja podataka na vrh trenutne liste, automatski traži sve moguće uzastopne znakove u regularnom izrazu.
Algoritam za kompilaciju i pretraživanje uključen je u uređivač teksta za dijeljenje vremena kao kontekstualna pretraga. Naravno, ovo je daleko od jedina primjena takvog postupka pretraživanja. Na primjer, varijanta ovog algoritma se koristi kao traženje simbola u tabeli u asembleru.
Pretpostavlja se da je čitalac upoznat sa regularnim izrazima i programskim jezikom IBM 7094 računara.Kompajler
Kompajler se sastoji od tri faze koje rade paralelno. Prva faza je filtriranje sintakse, koje dozvoljava da prođu samo sintaktički ispravni regularni izrazi. Ovaj korak također umeće operator "·" za podudaranje s regularnim izrazima. U drugom koraku, regularni izraz se pretvara u postfiksni oblik. U trećoj fazi kreira se objektni kod. Prve 2 faze su očigledne i nećemo se zadržavati na njima.
Thompsonov članak ne govori o nedeterminističkim konačnim mašinama, ali dobro objašnjava algoritam linearnog vremena i predstavlja program ALGOL-60 koji generiše kod na asemblerskom jeziku za IBM 7094. Implementacija je nezgodna, ali ideja je vrlo jednostavna.
trenutni put pretraživanja. Predstavljen je sa ⊕ sa jednim ulazom i dva izlaza.
Slika 1 prikazuje funkcije trećeg koraka kompilacije prilikom konverzije primjera regularnog izraza. Prva tri znaka u primjeru su a, b, c, i svaki kreira unos S[i] steka i polje NNODE.NNODE na postojeći kod za generiranje konačnog regularnog izraza u jednom unosu steka (vidi sliku 5)
Ovako bi izgledao regularni izraz .*.*=.*, ako zamislite, kao na slikama iz Thompsonovog članka.
Na sl. 0 postoji pet stanja počevši od 0 i 3 ciklusa koji počinju u stanjima 1, 2 i 3. Ova tri ciklusa odgovaraju tri .* u regularnom izrazu. 3 ovala sa tačkama odgovaraju jednom znaku. Ovalni sa znakom = odgovara doslovnom karakteru =. Stanje 4 je konačno. Ako smo ga dostigli, onda je regularni izraz uparen.
Da vidimo kako se takav dijagram stanja može koristiti za podudaranje s regularnim izrazom .*.*=.*, pogledaćemo podudaranje nizova x=x. Program počinje iz stanja 0, kao što je prikazano na sl. 1.
Da bi ovaj algoritam radio, krajnja mašina mora biti u nekoliko stanja istovremeno. Nedeterministički državni stroj će napraviti sve moguće prijelaze u isto vrijeme.
Prije nego što ima vremena da pročita ulazne podatke, on prelazi u oba prva stanja (1 i 2), kao što je prikazano na sl. 2.
Na sl. 2 pokazuje šta se dešava kada pogleda u prvu x в x=x. x može odgovarati vrhunskoj točki prelaskom iz stanja 1 i natrag u stanje 1. Or x može mapirati do tačke ispod prelazeći iz stanja 2 i nazad u stanje 2.
Nakon podudaranja s prvim x в x=x još uvijek smo u stanjima 1 i 2. Ne možemo doći do stanja 3 ili 4 jer nam je potreban doslovni karakter =.
Algoritam tada razmatra = в x=x. Kao i prije x, može se upariti s bilo kojim od prva dva ciklusa iz stanja 1 u stanje 1 ili iz stanja 2 u stanje 2, ali algoritam se i dalje može podudarati s literalom = i idite iz stanja 2 u stanje 3 (i odmah 4). Ovo je prikazano na sl. 3.
Algoritam tada prelazi na posljednji x в x=x. Iz stanja 1 i 2 isti su prijelazi mogući natrag u stanja 1 i 2. Iz stanja 3 x može odgovarati tački na desnoj strani i vratiti se u stanje 3.
U ovoj fazi, svaki lik x=x uzeti u obzir, a pošto smo dostigli stanje 4, regularni izraz odgovara ovom nizu. Svaki znak se obrađuje jednom, tako da ovaj algoritam linearno zavisi od dužine ulaznog niza. I bez povlačenja.
Očigledno, nakon dostizanja stanja 4 (kada se algoritam podudara x=) cijeli regularni izraz je uparen, a algoritam se može prekinuti bez ikakvog razmatranja x.
Ovaj algoritam linearno zavisi od veličine ulaznog niza.
izvor: www.habr.com