Prije gotovo 9 godina Cloudflare je bila mala tvrtka, a ja nisam radio za nju, bio sam samo kupac. Mjesec dana nakon pokretanja Cloudflarea primio sam obavijest da je moja web stranica Čini se da DNS ne radi. Cloudflare je napravio promjenu u , a postojao je i pokvaren DNS.
Odmah sam pisao Matthewu Princeu s naslovom “Gdje je moj DNS?”, a on mi je vratio dugačak odgovor pun tehničkih detalja (), na što sam odgovorio:
Od: John Graham-Cumming
Datum: 7. listopada 2010., 9:14
Predmet: Re: Gdje je moj DNS?
Za: Matthew PrinceSuper izvještaj, hvala. Svakako ću nazvati ako bude problema. Vjerojatno vrijedi napisati post o tome nakon što prikupite sve tehničke podatke. Mislim da će ljudi uživati u otvorenoj i iskrenoj priči. Pogotovo ako mu priložite grafikone koji pokazuju kako je promet porastao od pokretanja.
Imam dobar nadzor na svojoj stranici i dobijem SMS o svakom kvaru. Monitoring pokazuje da se kvar dogodio od 13:03:07 do 14:04:12. Testovi se provode svakih pet minuta.
Sigurna sam da ćeš shvatiti. Jeste li sigurni da ne trebate svoju osobu u Europi? 🙂
A on odgovori:
Od: Matthew Prince
Datum: 7. listopada 2010., 9:57
Predmet: Re: Gdje je moj DNS?
Prima: John Graham-CummingHvala vam. Odgovorili smo svima koji su pisali. Upravo sam na putu do ureda pa ćemo napisati nešto na blogu ili prikvačiti službenu objavu na našoj oglasnoj ploči. Potpuno se slažem, iskrenost je sve.
Sada je Cloudflare stvarno velika tvrtka, radim za nju i sada moram otvoreno pisati o našoj pogrešci, njezinim posljedicama i našim postupcima.
Događaji od 2. srpnja
Dana 2. srpnja uveli smo novo pravilo u Upravljanim pravilima za WAF-ove zbog kojih na svakoj procesorskoj jezgri koja obrađuje HTTP/HTTPS promet na Cloudflare mreži širom svijeta. Konstantno poboljšavamo upravljana pravila za WAF-ove kao odgovor na nove ranjivosti i prijetnje. U svibnju smo, primjerice, požurili radi zaštite od ozbiljne ranjivosti u SharePointu. Cijela poanta našeg WAF-a je mogućnost brze i globalne implementacije pravila.
Nažalost, ažuriranje od prošlog četvrtka sadržavalo je regularni izraz koji je trošio previše HTTP/HTTPS CPU resursa na backtracking. Zbog toga su oštećene naše osnovne proxy, CDN i WAF funkcije. Grafikon pokazuje da resursi procesora za posluživanje HTTP/HTTPS prometa dosežu gotovo 100% na poslužiteljima u našoj mreži.
Upotreba CPU-a u jednoj točki prisutnosti tijekom incidenta
Kao rezultat toga, naši su klijenti (i klijenti naših klijenata) završili sa stranicom pogreške 502 u Cloudflare domenama. Pogrešku 502 generirali su prednji web poslužitelji Cloudflare koji su još uvijek imali slobodne jezgre, ali nisu mogli komunicirati s procesima koji rukuju HTTP/HTTPS prometom.
Znamo koliko je to neugodnosti prouzročilo našim kupcima. Užasno nas je sram. I ovaj nas je neuspjeh spriječio da se učinkovito nosimo s incidentom.
Ako ste bili jedan od tih kupaca, vjerojatno ste bili uplašeni, ljuti i uzrujani. Štoviše, nismo imali . Velika potrošnja CPU-a nastala je zbog jednog WAF pravila s loše formuliranim regularnim izrazom koji je rezultirao pretjeranim praćenjem unazad. Evo izraza krivnje: (?:(?:"|'|]|}||d|(?:nan|infinity|true|false|null|undefined|symbol|math)|`|-|+)+[)]*;?((?:s|-|~|!|{}||||+)*.*(?:.*=.*)))
Iako je sama po sebi zanimljiva (i o tome ću detaljnije govoriti u nastavku), usluga Cloudflare nije radila 27 minuta ne samo zbog lošeg regularnog izraza. Trebalo nam je neko vrijeme da opišemo slijed događaja koji su doveli do neuspjeha, pa smo sporo odgovorili. Na kraju posta opisat ću vraćanje unazad u regularnom izrazu i reći vam što da radite s njim.
Što se dogodilo
Krenimo redom. Sva vremena ovdje su u UTC.
U 13:42 inženjer u timu vatrozida napravio je malu promjenu u pravilima otkrivanja pomoću automatskog procesa. U skladu s tim, kreirana je ulaznica zahtjeva za promjenu. Takvim ulaznicama upravljamo putem Jire (snimka zaslona u nastavku).
Nakon 3 minute pojavila se prva stranica PagerDutyja, prijavljujući problem s WAF-om. Ovo je bio sintetički test koji testira funkcionalnost WAF-ova (imamo ih na stotine) izvan Cloudflarea za praćenje normalnog rada. Odmah su uslijedile stranice s upozorenjima o neuspjelim testovima drugih Cloudflare end-to-end usluga, problemima s globalnim prometom, raširenim pogreškama 502 i hrpom izvješća s naših točaka prisutnosti (PoP) u gradovima diljem svijeta koji su ukazivali na nedostatak CPU resursa.
Primio sam nekoliko ovih upozorenja, izletio sa sastanka i bio na putu za stol kad je voditelj našeg odjela za razvoj rješenja rekao da smo izgubili 80% našeg 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 raštrkani su diljem svijeta i prate situaciju 0 sata dnevno. Obično vas ova upozorenja obavještavaju o određenim lokalnim problemima ograničenog opsega, prate se na internim nadzornim pločama i rješavaju se više puta dnevno. Ali ove stranice i obavijesti upućivale su na nešto stvarno ozbiljno, a inženjeri SRE-a odmah su proglasili razinu ozbiljnosti PXNUMX i kontaktirali menadžment i inženjere sustava.
Naši londonski inženjeri su u tom trenutku slušali predavanje u glavnoj dvorani. Predavanje je moralo biti prekinuto, svi su se okupili u velikoj konferencijskoj dvorani, a pozvano je još specijalista. To nije bio tipičan problem s kojim bi se SRE mogli sami nositi. Bilo je hitno uključiti prave stručnjake.
U 14:00 smo utvrdili da je problem u WAF-u i nije bilo napada. Tim za performanse izvukao je CPU podatke i postalo je jasno da je za to kriv WAF. Drugi zaposlenik potvrdio je ovu teoriju koristeći strace. Netko je drugi vidio u zapisnicima da postoji problem s WAF-om. U 14:02 cijeli tim mi je došao kada je predloženo korištenje globalnog kill-a, mehanizma ugrađenog u Cloudflare koji isključuje jednu komponentu diljem svijeta.
Druga je priča kako smo radili globalno ubijanje za WAF. Nije tako jednostavno. Koristimo vlastite proizvode, a od naše usluge nije radilo, nismo se mogli autentificirati i prijaviti na internu kontrolnu ploču (kada je sve popravljeno, saznali smo da su neki članovi tima izgubili pristup zbog sigurnosne značajke koja onemogućuje vjerodajnice ako se interna kontrolna ploča ne koristi za Dugo vrijeme).
I nismo mogli doći do naših internih usluga, poput Jire ili sustava za izgradnju. Trebao nam je mehanizam zaobilaznog rješenja, koji smo rijetko koristili (ovo će se također morati razraditi). Konačno, jedan je inženjer uspio onemogućiti WAF u 14:07, au 14:09, promet i CPU razine su se posvuda vratile u normalu. Ostali Cloudflareovi zaštitni mehanizmi radili su normalno.
Zatim smo krenuli s vraćanjem WAF-a. Situacija je bila neuobičajena, pa smo pokrenuli negativne testove (pitajući se je li promjena doista problem) i pozitivne testove (provjeravajući radi li vraćanje) u jednom gradu koristeći odvojeni promet, prebacujući klijente koji plaćaju od tamo.
U 14:52 smo se uvjerili da smo razumjeli razlog i napravili ispravku, te ponovno uključili WAF.
Kako Cloudflare radi
Cloudflare ima tim inženjera posvećenih upravljanju pravilima za WAF-ove. Nastoje poboljšati stope otkrivanja, smanjiti lažno pozitivne i brzo odgovoriti na nove prijetnje čim se pojave. U posljednjih 60 dana obrađeno je 476 zahtjeva za promjenu upravljanih pravila za WAF (u prosjeku jedan svaka 3 sata).
Ovu je promjenu trebalo primijeniti u simulacijskom načinu rada, gdje stvarni klijentski promet prolazi kroz pravilo, ali ništa nije blokirano. Ovaj način rada koristimo za testiranje učinkovitosti pravila i mjerenje lažno pozitivnih i lažno negativnih stopa. Ali čak i u simulacijskom načinu, pravila se zapravo moraju izvršiti, au ovom slučaju pravilo je sadržavalo regularni izraz koji je trošio previše resursa procesora.
Kao što možete vidjeti iz gornjeg zahtjeva za promjenu, imamo plan implementacije, plan vraćanja i vezu na interni standardni operativni postupak (SOP) za ovu vrstu implementacije. SOP za promjenu pravila omogućuje globalnu objavu. Zapravo, u Cloudflareu se stvari rade potpuno drugačije, a SOP nalaže da prvo pošaljemo softver za testiranje i internu upotrebu na internu točku prisutnosti (PoP) (koju koriste naši zaposlenici), zatim malom broju klijenata u izoliranoj lokaciji, zatim velikom broju klijenata, a tek onda cijelom svijetu.
Ovako to izgleda. Koristimo git interno putem BitBucketa. Inženjeri koji rade na promjenama šalju kod koji se izrađuje u TeamCity, a kada izrada prođe, dodjeljuju se recenzenti. Nakon što je zahtjev za povlačenje odobren, kod se sastavlja i (ponovno) izvodi niz testova.
Ako se izrada i testovi uspješno završe, u Jiri se stvara zahtjev za promjenom i odgovarajući upravitelj ili voditelj mora odobriti promjenu. Nakon odobrenja, dolazi do raspoređivanja 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 zaposlenici Cloudflarea. PoP za internu upotrebu omogućuje vam da uhvatite probleme prije nego što korisnički promet počne teći u rješenje. Korisna stvar.
Ako je DOG test uspješan, kod se pomiče u PIG (zamorac). Ovo je Cloudflare PoP, gdje mala količina besplatnog korisničkog prometa teče kroz novi kod.
Ako je sve u redu, šifra ide u Canary. Imamo tri Canary PoP-a u različitim dijelovima svijeta. U njima promet plaćenih i besplatnih klijenata prolazi kroz novi kod, a to je zadnja provjera grešaka.
Proces izdavanja softvera u Cloudflareu
Ako je kod na Canaryju u redu, objavit ćemo ga. Prolazak kroz sve faze - PAS, SVINJA, Kanarinac, cijeli svijet - traje nekoliko sati ili dana, ovisno o promjeni koda. Zbog raznolikosti Cloudflareove mreže i klijenata, temeljito testiramo kod prije nego što ga globalno objavimo svim klijentima. Ali WAF ne prati posebno ovaj proces jer se na prijetnje mora brzo odgovoriti.
WAF prijetnje
U posljednjih nekoliko godina došlo je do značajnog porasta prijetnji u uobičajenim aplikacijama. To je zbog veće dostupnosti alata za testiranje softvera. Na primjer, nedavno smo pisali o ).
Izvor:
Vrlo često se izradi dokaz koncepta i odmah objavi na Githubu kako bi je timovi koji održavaju aplikaciju mogli brzo testirati i osigurati da je adekvatno zaštićena. Stoga Cloudflare treba sposobnost da odgovori na nove napade što je brže moguće kako bi kupci imali priliku popraviti svoj softver.
Sjajan primjer brzog odgovora Cloudflarea je implementacija SharePoint zaštite od ranjivosti u svibnju (). Gotovo odmah nakon objave, primijetili smo veliki broj pokušaja iskorištavanja ranjivosti u SharePoint instalacijama naših klijenata. Naši ljudi neprestano prate nove prijetnje i pišu pravila za zaštitu naših kupaca.
Pravilo koje je izazvalo problem u četvrtak trebalo je zaštititi od cross-site scripting (XSS). Takvi napadi također su postali mnogo češći posljednjih godina.
Izvor:
Standardni postupak za promjenu upravljanog pravila za WAF je provođenje testiranja kontinuirane integracije (CI) prije globalne implementacije. Prošli četvrtak smo to učinili i objavili pravila. U 13:31 inženjer je predao odobreni zahtjev za povlačenje s izmjenom.
U 13:37 TeamCity je prikupio pravila, proveo testove i dao zeleno svjetlo. Testni paket WAF testira temeljnu funkcionalnost WAF-a i sastoji se od velikog broja jediničnih testova za pojedinačne funkcije. Nakon jediničnih testova, testirali smo pravila za WAF pomoću velikog broja HTTP zahtjeva. HTTP zahtjevi provjeravaju koje bi zahtjeve WAF trebao blokirati (kako bi presreo napad), a koje je moguće dopustiti (kako ne bi blokirali sve i izbjegli lažne pozitivne rezultate). Ali nismo testirali prekomjernu upotrebu CPU-a, a ispitivanje zapisa prethodnih verzija WAF-a pokazuje da se vrijeme izvršenja testa pravila nije povećalo i bilo je teško 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 usredotočena su na trenutnu sanaciju prijetnji, pa ih implementiramo pomoću Quicksilverove distribuirane pohrane ključ-vrijednosti, koja propagira promjene globalno u sekundi. Svi naši klijenti koriste ovu tehnologiju kada mijenjaju konfiguraciju na nadzornoj ploči ili putem API-ja, a zahvaljujući njoj na promjene reagiramo brzinom munje.
Nismo puno razgovarali o Quicksilveru. Prethodno smo koristili kao globalno distribuiranu ključ-vrijednost trgovinu, ali bilo je operativnih problema s njom, pa smo napisali vlastitu trgovinu, repliciranu u više od 180 gradova. Sada koristimo Quicksilver za slanje promjena konfiguracije klijentima, ažuriranje WAF pravila i distribuciju JavaScript koda koji su napisali klijenti Cloudflare radnicima.
Od klika na gumb na nadzornoj ploči ili pozivanja API-ja do promjene konfiguracije u cijelom svijetu potrebno je samo nekoliko sekundi. Korisnicima se svidjela ova brzina postavljanja. A Workers im daje gotovo trenutnu globalnu implementaciju softvera. Quicksilver u prosjeku prenosi oko 350 promjena u sekundi.
A Quicksilver je vrlo brz. U prosjeku smo postigli 99. percentil od 2,29 sekundi za širenje promjena na svako računalo u svijetu. Brzina je obično dobra stvar. Uostalom, kada omogućite funkciju ili izbrišete predmemoriju, to se događa gotovo trenutno i posvuda. Slanje koda kroz Cloudflare Workers događa se istom brzinom. Cloudflare obećava svojim korisnicima brza ažuriranja u pravo vrijeme.
Ali u ovom slučaju brzina se okrutno našalila s nama, a pravila su se posvuda promijenila u nekoliko sekundi. Možda ste primijetili da WAF kod koristi Lua. Cloudflare intenzivno koristi Lua u proizvodnji i detaljima mi . Lua WAF koristi interno i primjenjuje povratno praćenje za podudaranje. Nema mehanizama za zaštitu od izraza koji izmiču kontroli. U nastavku ću govoriti više o tome i što radimo po tom pitanju.
Prije nego što su pravila implementirana, sve je išlo glatko: zahtjev za povlačenje je kreiran i odobren, CI/CD cjevovod je prikupio i testirao kod, zahtjev za promjenom je predan u skladu sa SOP-om koji upravlja implementacijom i vraćanjem, i implementacija je dovršena.
Proces postavljanja Cloudflare WAF-a
Nešto je pošlo po zlu
Kao što sam rekao, svaki tjedan postavljamo desetke novih WAF pravila i imamo mnogo sustava za zaštitu od negativnih posljedica takve implementacije. A kad nešto krene po zlu, obično je to splet više okolnosti odjednom. Ako pronađete samo jedan razlog, to je, naravno, umirujuće, ali nije uvijek točno. Ovo su razlozi koji su zajedno doveli do kvara naše HTTP/HTTPS usluge.
- Inženjer je napisao regularni izraz koji bi mogao rezultirati prekomjernim .
- Značajka koja je mogla spriječiti regularni izraz da troši previše CPU-a greškom je uklonjena u refaktoriranju WAF-a nekoliko tjedana ranije — refaktoriranje je bilo potrebno kako bi WAF trošio manje resursa.
- Motor za regularne izraze nije imao jamstva složenosti.
- Testni paket nije mogao otkriti pretjeranu potrošnju CPU-a.
- SOP omogućuje da se promjene pravila koje nisu hitne uvedu globalno bez procesa u više koraka.
- Plan vraćanja zahtijevao je pokretanje pune WAF verzije dva puta, što je dugo trajalo.
- Prva uzbuna o globalnim problemima u prometu pokrenuta je prekasno.
- Trebalo nam je vremena da ažuriramo stranicu statusa.
- Imali smo problema s pristupom sustavima zbog kvara, a procedura zaobilaženja nije bila dobro uspostavljena.
- SRE inženjeri izgubili su pristup nekim sustavima jer su njihove vjerodajnice istekle zbog sigurnosnih razloga.
- Naši korisnici nisu imali pristup Cloudflare nadzornoj ploči ili API-ju jer prolaze kroz Cloudflare regiju.
Što se promijenilo od prošlog četvrtka
Prvo, potpuno smo zaustavili sav rad na izdanjima za WAF i radimo sljedeće:
- Ponovno uvodimo zaštitu od prekomjerne upotrebe procesora koju smo uklonili. (Spreman)
- Ručno provjerava svih 3868 pravila u upravljanim pravilima za WAF kako bi pronašao i ispravio druge potencijalne slučajeve pretjeranog vraćanja unatrag. (Provjera završena)
- Uključujemo profiliranje izvedbe za sva pravila u testnom skupu. (Očekuje se: 19. srpnja)
- Prebacivanje na regularni izraz ili - oba pružaju jamstva za vrijeme rada. (Očekuje se: 31. srpnja)
- Prepisujemo SOP kako bismo implementirali pravila u fazama, poput drugog softvera u Cloudflareu, ali u isto vrijeme imamo mogućnost hitne globalne implementacije ako su napadi već počeli.
- Razvijamo mogućnost hitnog uklanjanja Cloudflare nadzorne ploče i API-ja iz Cloudflare regije.
- Automatiziranje ažuriranja stranice .
Dugoročno se udaljavamo od Lua WAF-a koji sam napisao prije nekoliko godina. Premještanje WAF-a na . Na taj će način WAF biti brži i dobiti dodatnu razinu zaštite.
Zaključak
Taj je kvar izazvao probleme nama i našim klijentima. Brzo smo djelovali kako bismo ispravili situaciju i sada radimo na nedostacima u procesima koji su uzrokovali pad, kao i kopamo još dublje kako bismo se zaštitili od potencijalnih problema s regularnim izrazima u budućnosti prilikom prelaska na novu tehnologiju.
Jako smo posramljeni zbog ovog prekida i ispričavamo se našim korisnicima. Nadamo se da će ove promjene osigurati da se ovako nešto više ne dogodi.
Primjena. Povratak regularnih izraza
Da biste razumjeli kako izraz:
(?:(?:"|'|]|}||d
(?:nan|infinity|true|false|null|undefined|symbol|math)|`|-
|+)+[)]*;?((?:s|-|~|!|{}||||+)*.*(?:.*=.*)))pojeo sve CPU resurse, trebate znati nešto o tome kako radi standardni regularni izraz. Ovdje je problem obrazac .*(?:.*=.*). (?: i odgovarajuće ) je grupa bez hvatanja (to jest, izraz u zagradama je grupiran kao jedan izraz).
U kontekstu prekomjerne potrošnje CPU-a, ovaj se obrazac može opisati kao .*.*=.*. U ovom obliku uzorak izgleda nepotrebno složen. Ali što je još važnije, u stvarnom svijetu, izrazi (poput složenih izraza u pravilima WAF-a) koji od motora traže podudaranje s fragmentom nakon kojeg slijedi drugi fragment mogu dovesti do katastrofalnog vraćanja unatrag. I zato.
U regularnom izrazu . znači da trebate spojiti jedan znak, .* - spajanje nula ili više znakova "pohlepno", odnosno hvatanje maksimalnog broja znakova, tako da .*.*=.* znači podudaranje s nula ili više znakova, zatim podudaranje s nula ili više znakova, pronalaženje literala = znak, podudaranje s nula ili više znakova.
Uzmimo testnu liniju x=x. Odgovara izrazu .*.*=.*. .*.* prije nego se znak jednakosti poklopi s prvim x (jedna od grupa .* odgovara x, a drugi - nula znakova). .* poslije = utakmice zadnje x.
Ova usporedba zahtijeva 23 koraka. Prva grupa .* в .*.*=.* ponaša se pohlepno i odgovara cijelom nizu x=x. Motor prelazi u sljedeću grupu .*. Nemamo više znakova za spajanje, pa druga grupa .* odgovara nula znakova (ovo je dopušteno). Zatim se motor kreće prema znaku =. Nema više simbola (prva grupa .* upotrijebio cijeli izraz x=x), nema usporedbe.
A onda se mehanizam regularnog izraza vraća na početak. Prelazi na prvu skupinu .* i uspoređuje ga с x= (umjesto x=x), a zatim preuzima drugu skupinu .*. Druga grupa .* uspoređuje se s drugom x, i opet nemamo nijedan lik. A kad motor opet dohvati = в .*.*=.*, ništa ne radi. I opet se vraća.
Ovaj put grupa .* još uvijek odgovara x=, ali druga skupina .* ne više x, i nula znakova. Motor pokušava pronaći doslovni lik = u uzorku .*.*=.*, ali ne izlazi (uostalom, prva grupa ga je već zauzela .*). I opet se vraća.
Ovaj put prva grupa .* uzima samo prvi x. Ali druga skupina .* "pohlepno" hvata =x. Jeste li već pogodili što će se dogoditi? Motor pokušava uskladiti doslovno =, ne uspije i napravi još jedno vraćanje unatrag.
Prva skupina .* još uvijek odgovara prvom x. Drugi .* samo uzima =. Naravno, motor ne može parirati doslovnom =, jer je druga grupa to već učinila .*. I opet vraćanje unatrag. A mi pokušavamo uskladiti niz od tri znaka!
Kao rezultat toga, prva skupina .* odgovara samo prvom x, drugo .* - s nula znakova, a motor konačno odgovara literalu = u izražavanju с = u redu. Sljedeća je zadnja grupa .* uspoređuje se s posljednjim x.
23 koraka samo za x=x. Pogledajte kratki video o korištenju Perla , koji pokazuje kako dolazi do koraka i povratka.
Ovo je već puno posla, ali što ako umjesto toga x=x imat ćemo x=xx? To su 33 koraka. I ako x=xxx? 45. Veza nije linearna. Grafikon prikazuje usporedbu iz x=x na x=xxxxxxxxxxxxxxxxxxxx (20 x nakon =). Ako imamo 20 x poslije =, motor dovršava usklađivanje u 555 koraka! (Štoviše, ako smo izgubili x= a niz se jednostavno sastoji od 20 x, motor će poduzeti 4067 koraka da shvati da nema podudaranja).
Ovaj video prikazuje sva povratna kretanja za usporedbu x=xxxxxxxxxxxxxxxxxxxx:
Problem je u tome što kako se veličina niza povećava, vrijeme podudaranja raste super-linearno. Ali stvari mogu postati još gore ako se regularni izraz malo modificira. Recimo da smo imali .*.*=.*; (to jest, na kraju uzorka nalazila se doslovna točka-zarez). Na primjer, za podudaranje izraza poput foo=bar;.
I ovdje bi povratak bio prava katastrofa. Za usporedbu x=x bit će potrebno 90 koraka, a ne 23. I taj broj brzo raste. Usporediti x= i 20 x, potrebno je 5353 koraka. Evo grafikona. Pogledajte vrijednosti osi Y u odnosu na prethodni grafikon.
Ako ste zainteresirani, pogledajte svih 5353 neuspješnih koraka za podudaranje x=xxxxxxxxxxxxxxxxxxxx и .*.*=.*;
Korištenjem lijenog, a ne pohlepnog podudaranja, može se kontrolirati opseg povratnog praćenja. Ako promijenimo izvorni izraz u .*?.*?=.*?, za usporedbu x=x bit će potrebno 11 koraka (ne 23). Što se tiče x=xxxxxxxxxxxxxxxxxxxx. Sve zato ? nakon .* govori stroju da uskladi minimalni broj znakova prije nego što krene dalje.
Ali lijena preslikavanja ne rješavaju u potpunosti problem povratnog praćenja. Ako zamijenimo katastrofalni primjer .*.*=.*; na .*?.*?=.*?;, vrijeme izvršenja će ostati isto. x=x i dalje zahtijeva 555 koraka, i x= i 20 x - 5353.
Jedina stvar koja se može učiniti (osim potpunog ponovnog pisanja uzorka za veću specifičnost) je napuštanje mehanizma regularnih izraza s njegovim mehanizmom povratnog praćenja. To je ono što ćemo raditi sljedećih nekoliko tjedana.
Rješenje ovog problema poznato je od 1968. godine, kada je Kent Thompson napisao članak (“Metode programiranja: Algoritam pretraživanja regularnog izraza”). U članku se opisuje mehanizam koji vam omogućuje pretvaranje regularnog izraza u nedeterminističke automate s konačnim stanjem, te nakon promjene stanja u nedeterminističkim automatima s konačnim stanjem, korištenje algoritma čije vrijeme izvršenja linearno ovisi o uparenom nizu.
Metode programiranja
Algoritam traženja regularnog izraza
Ken Thompson
Bell Telephone Laboratories, Inc., Murray Hill, New JerseyOpisuje metodu za traženje određenog niza znakova u tekstu i raspravlja o implementaciji ove metode u obliku prevoditelja. Prevodilac uzima regularni izraz kao izvorni kod i proizvodi IBM 7094 program kao objektni kod. Objektni program prima unos u obliku teksta za pretraživanje i emitira signal svaki put kada se niz teksta usporedi s danim regularnim izrazom. U članku su navedeni primjeri, problemi i rješenja.
Algoritam
Prethodni algoritmi pretraživanja rezultirali su vraćanjem unatrag ako djelomično uspješno pretraživanje nije dalo rezultat.U načinu kompilacije, algoritam ne radi sa simbolima. 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 kompilacije i pretraživanja uključen je u uređivač teksta s dijeljenjem vremena kao kontekstualno pretraživanje. Naravno, ovo nije jedina primjena takvog postupka pretraživanja. Na primjer, varijanta ovog algoritma koristi se kao pretraga simbola u tablici u asembleru.
Pretpostavlja se da je čitatelj upoznat s regularnim izrazima i programskim jezikom IBM 7094.Sastavljač
Kompajler se sastoji od tri faze koje rade paralelno. Prva faza je filtriranje sintakse, koje dopušta prolaz samo sintaktički ispravnim regularnim izrazima. Ovaj korak također umeće operator "·" za podudaranje regularnih izraza. U drugom koraku, regularni izraz se pretvara u postfiksni oblik. U trećoj fazi kreira se objektni kod. Prve 2 faze su očite i nećemo se zadržavati na njima.
Thompsonov članak ne govori o nedeterminističkim konačnim automatima, ali dobro objašnjava algoritam linearnog vremena i predstavlja program ALGOL-60 koji generira kod asemblerskog jezika za IBM 7094. Implementacija je nezgodna, ali ideja je vrlo jednostavna.
trenutni put pretraživanja. Predstavljen je ikonom ⊕ s jednim ulazom i dva izlaza.
Slika 1 prikazuje funkcije trećeg koraka kompilacije pri transformaciji primjera regularnog izraza. Prva tri znaka u primjeru su a, b, c, a svaki stvara unos u stog S[i] i polje NNODE.NNODE na postojeći kod za generiranje rezultirajućeg regularnog izraza u jednom unosu na hrpu (pogledajte sliku 5)
Ovako bi izgledao regularni izraz .*.*=.*, ako to zamislite kao na slikama iz Thompsonovog članka.
Na sl. 0 postoji pet stanja koja počinju od 0 i 3 ciklusa koji počinju od stanja 1, 2 i 3. Ova tri ciklusa odgovaraju trima .* u regularnom izrazu. 3 ovala s točkama odgovaraju jednom simbolu. Ovalno sa znakom = odgovara doslovnom znaku =. Stanje 4 je konačno. Ako ga dosegnemo, regularni izraz se podudara.
Da vidimo kako se takav dijagram stanja može koristiti za podudaranje regularnih izraza .*.*=.*, pogledat ćemo podudaranje nizova x=x. Program počinje iz stanja 0, kao što je prikazano na sl. 1.
Da bi ovaj algoritam radio, stroj stanja mora biti u nekoliko stanja istovremeno. Nedeterministički konačni stroj izvršit će sve moguće prijelaze istovremeno.
Prije nego što stigne pročitati ulazne podatke, prelazi u oba prva stanja (1 i 2), kao što je prikazano na sl. 2.
Na sl. 2 pokazuje što se događa kada pogleda na prvu x в x=x. x može preslikati na gornju točku, idući iz stanja 1 i natrag u stanje 1. Ili x može mapirati do točke ispod, idući iz stanja 2 i natrag u stanje 2.
Nakon podudaranja prvog x в x=x još uvijek smo u stanjima 1 i 2. Ne možemo doći do stanja 3 ili 4 jer nam treba doslovni znak =.
Algoritam zatim razmatra = в x=x. Kao i x prije njega, može se uskladiti s bilo kojom od gornje dvije petlje iz stanja 1 u stanje 1 ili iz stanja 2 u stanje 2, ali algoritam može uskladiti literal = i prijeći iz stanja 2 u stanje 3 (i odmah 4). Ovo je prikazano na sl. 3.
Algoritam zatim prelazi na posljednji x в x=x. Iz stanja 1 i 2 mogući su isti prijelazi natrag u stanja 1 i 2. Iz stanja 3 x može spojiti točku s desne strane i vratiti se u stanje 3.
U ovoj fazi svaki lik x=x uzeti u obzir, a budući da smo došli do stanja 4, regularni izraz odgovara tom nizu. Svaki se znak obrađuje jednom, tako da je ovaj algoritam linearan u duljini ulaznog niza. I nema vraćanja unatrag.
Očito, nakon dostizanja stanja 4 (kada se algoritam poklapa x=) cijeli regularni izraz se podudara, a algoritam može prekinuti bez da ga uopće uzme u obzir x.
Ovaj algoritam linearno ovisi o veličini ulaznog niza.
Izvor: www.habr.com