Pred skoraj 9 leti je bil Cloudflare majhno podjetje in jaz nisem delal zanj, bil sem le stranka. Mesec dni po zagonu Cloudflare sem prejel obvestilo, da je moje spletno mesto Zdi se, da DNS ne deluje. Cloudflare je spremenil v , in bil je pokvarjen DNS.
Takoj sem pisal Matthewu Princeu z naslovom "Kje je moj DNS?" in poslal mi je dolg odgovor, poln tehničnih podrobnosti (), na kar sem odgovoril:
Avtor: John Graham-Cumming
Datum: 7. oktober 2010, 9:14
Zadeva: Re: Kje je moj DNS?
Za: Matthew PrinceKul poročilo, hvala. Vsekakor pokličem, če bodo težave. Verjetno je vredno napisati objavo o tem, ko zberete vse tehnične informacije. Mislim, da bodo ljudje uživali v odprti in pošteni zgodbi. Še posebej, če mu priložite grafe, ki prikazujejo, kako se je povečal promet od lansiranja.
Na svoji strani imam dober nadzor in o vsaki napaki prejmem SMS. Monitoring kaže, da je do okvare prišlo od 13:03:07 do 14:04:12. Testi se izvajajo vsakih pet minut.
Prepričan sem, da boš ugotovil. Ste prepričani, da ne potrebujete svojega človeka v Evropi? 🙂
In odgovoril je:
Avtor: Matthew Prince
Datum: 7. oktober 2010, 9:57
Zadeva: Re: Kje je moj DNS?
Za: John Graham-CummingHvala vam. Odgovorili smo vsem, ki so pisali. Zdaj sem na poti v pisarno in bomo kaj napisali na blog ali pripeli uradno objavo na našo oglasno desko. Se popolnoma strinjam, iskrenost je vse.
Zdaj je Cloudflare res veliko podjetje, delam zanj in zdaj moram odkrito pisati o naši napaki, njenih posledicah in naših dejanjih.
Dogodki 2. julija
2. julija smo uvedli novo pravilo v upravljanih pravilih za WAF, zaradi česar na vsakem procesorskem jedru, ki obdeluje promet HTTP/HTTPS v omrežju Cloudflare po vsem svetu. Nenehno izboljšujemo upravljana pravila za WAF kot odgovor na nove ranljivosti in grožnje. Maja smo na primer pohiteli za zaščito pred resno ranljivostjo v SharePointu. Bistvo našega WAF je zmožnost hitre in globalne uvedbe pravil.
Na žalost je posodobitev prejšnjega četrtka vsebovala regularni izraz, ki je zapravil preveč virov procesorja HTTP/HTTPS za sledenje nazaj. Zaradi tega so trpele naše osnovne funkcije proxy, CDN in WAF. Graf prikazuje, da procesorski viri za strežbo HTTP/HTTPS prometa dosegajo skoraj 100 % na strežnikih v našem omrežju.
Uporaba procesorja na eni točki prisotnosti med incidentom
Posledično so naše stranke (in stranke naših strank) prejele stran z napako 502 na domenah Cloudflare. Napake 502 so ustvarili sprednji spletni strežniki Cloudflare, ki so še imeli prosta jedra, vendar niso mogli komunicirati s procesi, ki obravnavajo promet HTTP/HTTPS.
Vemo, koliko nevšečnosti je to povzročilo našim strankam. Strašno nas je sram. In ta neuspeh nam je preprečil, da bi se učinkovito spopadli z incidentom.
Če ste bili ena od teh strank, ste bili verjetno prestrašeni, jezni in razburjeni. Še več, nismo imeli . Velika poraba procesorja je bila posledica enega pravila WAF s slabo ubesedenim regularnim izrazom, ki je povzročil prekomerno sledenje nazaj. Tukaj je kriv izraz: (?:(?:"|'|]|}||d|(?:nan|infinity|true|false|null|undefined|symbol|math)|`|-|+)+[)]*;?((?:s|-|~|!|{}||||+)*.*(?:.*=.*)))
Čeprav je to samo po sebi zanimivo (in o tem bom podrobneje govoril spodaj), storitev Cloudflare ni delovala 27 minut, ne samo zaradi slabega regularnega izraza. Potrebovali smo nekaj časa, da smo opisali zaporedje dogodkov, ki so pripeljali do neuspeha, zato smo se počasi odzvali. Na koncu objave bom opisal sledenje nazaj v regularnem izrazu in vam povedal, kaj storiti z njim.
Kaj se je zgodilo
Začnimo po vrsti. Vsi časi tukaj so v UTC.
Ob 13 je inženir v ekipi za požarni zid naredil majhno spremembo pravil zaznavanja z uporabo samodejnega postopka. V skladu s tem je bila ustvarjena zahteva za spremembo. Takšne vstopnice upravljamo prek Jira (posnetek zaslona spodaj).
Po 3 minutah se je pojavila prva stran PagerDuty, ki je poročala o težavi z WAF. To je bil sintetični test, ki preizkuša funkcionalnost WAF (imamo jih na stotine) zunaj Cloudflareja za spremljanje normalnega delovanja. Temu so takoj sledile strani z opozorili o drugih neuspelih testih storitev Cloudflare od konca do konca, globalnih prometnih težavah, razširjenih napakah 502 in množici poročil iz naših točk prisotnosti (PoP) v mestih po vsem svetu, ki so kazala na pomanjkanje virov procesorja.
Prejel sem več teh opozoril, odvihral s sestanka in ravno bil na poti k mizi, ko je vodja našega oddelka za razvoj rešitev povedal, da smo izgubili 80 % našega prometa. Stekel sem do naših inženirjev SRE, ki so že delali na težavi. Sprva smo mislili, da gre za nekakšen neznan napad.
Inženirji Cloudflare SRE so razpršeni po vsem svetu in spremljajo situacijo 0 ur na dan. Običajno vas ta opozorila obvestijo o določenih lokalnih težavah omejenega obsega, spremljajo se na notranjih nadzornih ploščah in se razrešijo večkrat na dan. Toda te strani in obvestila so kazala na nekaj res resnega in inženirji SRE so takoj razglasili stopnjo resnosti PXNUMX ter stopili v stik z vodstvom in sistemskimi inženirji.
Naši londonski inženirji so v tistem trenutku poslušali predavanje v glavni dvorani. Predavanje so morali prekiniti, vsi so se zbrali v veliki konferenčni sobi in poklicali več specialistov. To ni bila tipična težava, s katero bi se SRE lahko spoprijeli sami. Nujno je bilo treba vključiti prave strokovnjake.
Ob 14:00 smo ugotovili, da je bila težava v WAF in napada ni bilo. Ekipa za uspešnost je potegnila podatke CPU in postalo je jasno, da je bil kriv WAF. Drugi zaposleni je potrdil to teorijo z uporabo strace. Nekdo drug je v dnevnikih videl, da je prišlo do težave z WAF. Ob 14:02 je celotna ekipa prišla k meni, ko je bilo predlagano, da uporabimo globalno ubijanje, mehanizem, vgrajen v Cloudflare, ki izklopi eno komponento po vsem svetu.
Kako smo naredili globalno ubijanje za WAF, je druga zgodba. Ni tako preprosto. Uporabljamo lastne izdelke, od takrat pa naše storitve ni delovalo, nismo mogli preveriti pristnosti in se prijaviti v notranjo nadzorno ploščo (ko je bilo vse popravljeno, smo izvedeli, da so nekateri člani skupine izgubili dostop zaradi varnostne funkcije, ki onemogoči poverilnice, če se notranja nadzorna plošča ne uporablja za dolgo časa).
In nismo mogli priti do naših notranjih storitev, kot je Jira ali sistem gradnje. Potrebovali smo mehanizem rešitve, ki smo ga uporabljali redko (tudi to bo treba izdelati). Končno je enemu inženirju ob 14:07 uspelo onemogočiti WAF, ob 14:09 pa sta bila raven prometa in procesorja povsod normalna. Ostali zaščitni mehanizmi Cloudflare so delovali kot običajno.
Nato smo se lotili obnove WAF. Situacija je bila neobičajna, zato smo izvedli negativne teste (spraševali smo se, ali je sprememba res težava) in pozitivne teste (prepričali smo, da povrnitev nazaj deluje) v enem mestu z uporabo ločenega prometa in od tam prenesli plačljive stranke.
Ob 14:52 smo bili prepričani, da razumemo razlog in naredili popravek ter ponovno omogočili WAF.
Kako deluje Cloudflare
Cloudflare ima ekipo inženirjev, namenjenih upravljanju pravil za WAF. Prizadevajo si izboljšati stopnje odkrivanja, zmanjšati lažne pozitivne rezultate in se hitro odzvati na nove grožnje, ko se pojavijo. V zadnjih 60 dneh je bilo obdelanih 476 zahtev za spremembo upravljanih pravil za WAF (povprečno ena vsake 3 ure).
To posebno spremembo je bilo treba uvesti v simulacijskem načinu, kjer pravi promet odjemalca poteka skozi pravilo, vendar ni nič blokirano. Ta način uporabljamo za testiranje učinkovitosti pravil in merjenje lažno pozitivnih in lažno negativnih stopenj. Toda tudi v simulacijskem načinu je treba pravila dejansko izvesti in v tem primeru je pravilo vsebovalo regularni izraz, ki je porabljal preveč virov procesorja.
Kot lahko vidite iz zgornje zahteve za spremembo, imamo načrt uvajanja, načrt za povrnitev in povezavo do internega standardnega operativnega postopka (SOP) za to vrsto uvajanja. Standardni operativni postopek za spremembo pravila omogoča globalno objavo. Pravzaprav se pri Cloudflare stvari izvajajo povsem drugače in SOP narekuje, da najprej pošljemo programsko opremo za testiranje in interno uporabo na interno točko prisotnosti (PoP) (ki jo uporabljajo naši zaposleni), nato pa majhnemu številu strank v izolirani lokaciji, nato velikemu številu strank in šele nato celemu svetu.
Takole izgleda. Git uporabljamo interno prek BitBucketa. Inženirji, ki delajo na spremembah, predložijo kodo, ki je zgrajena v TeamCity, in ko je gradnja mimo, so dodeljeni pregledovalci. Ko je zahteva za vlečenje odobrena, se koda sestavi in (ponovno) se izvede vrsta testov.
Če se izdelava in preizkusi uspešno zaključijo, se v Jiri ustvari zahteva za spremembo in ustrezen vodja ali vodja mora odobriti spremembo. Po odobritvi pride do razporeditve v tako imenovano »PoP menažerijo«: PES, PRAŠIČ in (pes, prašič in kanarček).
DOG PoP je Cloudflare PoP (kot vsako drugo naše mesto), ki ga uporabljajo samo zaposleni v Cloudflareju. PoP za interno uporabo vam omogoča, da ujamete težave, preden začne promet strank teči v rešitev. Uporabna stvar.
Če je DOG test uspešen, se koda premakne na stopnjo PIG (morski prašiček). To je Cloudflare PoP, kjer majhna količina brezplačnega prometa strank teče skozi novo kodo.
Če je vse v redu, gre koda v Canary. Imamo tri Canary PoPs na različnih koncih sveta. V njih promet plačljivih in brezplačnih strank poteka skozi novo kodo in to je zadnje preverjanje napak.
Postopek izdaje programske opreme pri Cloudflare
Če je koda v Canaryju v redu, jo izdamo. Prehod skozi vse stopnje - PES, PRAŠIČ, Kanarček, ves svet - traja več ur ali dni, odvisno od spremembe kode. Zaradi raznolikosti omrežja in odjemalcev Cloudflare temeljito testiramo kodo, preden jo globalno objavimo za vse odjemalce. Vendar WAF ne sledi posebej temu procesu, ker se je treba na grožnje odzvati hitro.
WAF grožnje
V zadnjih nekaj letih se je znatno povečalo število groženj v običajnih aplikacijah. To je posledica večje razpoložljivosti orodij za testiranje programske opreme. Na primer, o katerem smo nedavno pisali ).
Vir:
Zelo pogosto se ustvari dokaz koncepta in takoj objavi na Githubu, tako da ga ekipe, ki vzdržujejo aplikacijo, lahko hitro preizkusijo in zagotovijo, da je ustrezno zavarovana. Zato Cloudflare potrebuje sposobnost, da se čim hitreje odzove na nove napade, tako da imajo stranke možnost popraviti svojo programsko opremo.
Odličen primer hitrega odziva Cloudflare je uvedba zaščite pred ranljivostmi SharePoint maja (). Skoraj takoj po objavi smo opazili ogromno število poskusov izkoriščanja ranljivosti v namestitvah SharePoint naših strank. Naši fantje nenehno spremljajo nove grožnje in pišejo pravila za zaščito naših strank.
Pravilo, ki je v četrtek povzročilo težavo, naj bi ščitilo pred navzkrižnim skriptiranjem (XSS). Tudi tovrstni napadi so v zadnjih letih postali veliko pogostejši.
Vir:
Standardni postopek za spreminjanje upravljanega pravila za WAF je izvajanje neprekinjenega testiranja integracije (CI) pred globalno uvedbo. Prejšnji četrtek smo to storili in uvedli pravila. Ob 13 je inženir predložil odobreno zahtevo za umik s spremembo.
Ob 13:37 je TeamCity zbral pravila, izvedel teste in dal zeleno luč. Testna zbirka WAF preizkuša osnovno funkcionalnost WAF in je sestavljena iz velikega števila testov enot za posamezne funkcije. Po preizkusih enot smo preizkusili pravila za WAF z uporabo velikega števila zahtev HTTP. Zahteve HTTP preverijo, katere zahteve naj blokira WAF (da prestreže napad) in katere lahko dovoli skozi (da ne blokira vsega in se izogne lažnim pozitivnim rezultatom). Vendar nismo testirali prekomerne obremenitve procesorja in pregledovanje dnevnikov prejšnjih gradenj WAF kaže, da se čas izvajanja testa pravila ni povečal in je bilo težko sumiti, da ne bo dovolj virov.
Preizkusi so bili uspešni in TeamCity je začel samodejno uvajati spremembo ob 13.
Quicksilver
Pravila WAF se osredotočajo na takojšnje odpravljanje groženj, zato jih uvedemo s Quicksilverjevo porazdeljeno shrambo ključ-vrednost, ki v nekaj sekundah razširi spremembe globalno. Vse naše stranke uporabljajo to tehnologijo, ko spreminjajo konfiguracijo na nadzorni plošči ali prek API-ja, in prav zahvaljujoč njej se na spremembe odzivamo bliskovito hitro.
Nismo veliko govorili o Quicksilverju. Prej smo uporabljali kot globalno distribuirano shrambo ključ-vrednost, vendar je prišlo do operativnih težav z njo, zato smo napisali svojo lastno trgovino, podvojeno v več kot 180 mestih. Zdaj uporabljamo Quicksilver za pošiljanje konfiguracijskih sprememb odjemalcem, posodabljanje pravil WAF in distribucijo kode JavaScript, ki so jo napisali odjemalci, delavcem Cloudflare.
Od klika gumba na nadzorni plošči ali klica API-ja do spremembe konfiguracije po vsem svetu traja le nekaj sekund. Strankam je bila všeč ta hitrost nastavitve. In Workers jim omogoča skoraj takojšnjo globalno uvedbo programske opreme. V povprečju Quicksilver razširi približno 350 sprememb na sekundo.
In Quicksilver je zelo hiter. V povprečju smo dosegli 99. percentil 2,29 sekunde za prenos sprememb na vsak računalnik po vsem svetu. Hitrost je običajno dobra stvar. Konec koncev, ko omogočite funkcijo ali počistite predpomnilnik, se to zgodi skoraj takoj in povsod. Pošiljanje kode prek Cloudflare Workers poteka z enako hitrostjo. Cloudflare svojim strankam obljublja hitre posodobitve ob pravem času.
Toda v tem primeru se je hitrost z nami kruto šalila in pravila so se povsod spremenila v nekaj sekundah. Morda ste opazili, da koda WAF uporablja Lua. Cloudflare obširno uporablja Lua v proizvodnji in podrobnostih smo . Lua WAF uporablja interno in uporablja sledenje nazaj za ujemanje. Nima mehanizmov za zaščito pred izrazi, ki uidejo izpod nadzora. Spodaj bom govoril več o tem in o tem, kaj počnemo glede tega.
Pred uvedbo pravil je vse potekalo gladko: zahteva za vlečenje je bila ustvarjena in odobrena, cevovod CI/CD je zbral in preizkusil kodo, zahteva za spremembo je bila predložena v skladu s SOP, ki ureja uvajanje in povrnitev, in uvedba je bila zaključena.
Postopek uvajanja Cloudflare WAF
Nekaj je šlo narobe
Kot sem rekel, vsak teden uvedemo na desetine novih pravil WAF in imamo veliko sistemov za zaščito pred negativnimi posledicami takšne uvedbe. In ko gre kaj narobe, je to največkrat splet več okoliščin hkrati. Če najdete le en razlog, je to seveda pomirjujoče, ni pa vedno res. To so razlogi, ki so skupaj privedli do neuspeha naše storitve HTTP/HTTPS.
- Inženir je napisal regularni izraz, ki lahko povzroči pretirano .
- Funkcija, ki bi lahko preprečila, da bi regularni izraz zapravljal preveč CPE, je bila pomotoma odstranjena pri preoblikovanju WAF nekaj tednov prej – preoblikovanje je bilo potrebno, da bi WAF porabil manj virov.
- Mehanizem regularnih izrazov ni imel nobenih jamstev glede kompleksnosti.
- Testna zbirka ni mogla zaznati prekomerne porabe procesorja.
- SOP omogoča globalno uvedbo nenujnih sprememb pravil brez postopka v več korakih.
- Načrt za povrnitev je zahteval dvakratno izvedbo celotne zgradbe WAF, kar je trajalo dolgo.
- Prvo opozorilo o globalnih prometnih težavah se je sprožilo prepozno.
- Potrebovali smo nekaj časa, da smo posodobili stran s stanjem.
- Imeli smo težave z dostopom do sistemov zaradi napake in postopek obvoda ni bil dobro vzpostavljen.
- Inženirji SRE so izgubili dostop do nekaterih sistemov, ker so njihove poverilnice iz varnostnih razlogov potekle.
- Naše stranke niso imele dostopa do nadzorne plošče ali API-ja Cloudflare, ker gredo skozi regijo Cloudflare.
Kaj se je spremenilo od prejšnjega četrtka
Najprej smo popolnoma ustavili vse delo na izdajah za WAF in delamo naslednje:
- Ponovno uvajamo zaščito pred prekomerno uporabo procesorja, ki smo jo odstranili. (pripravljen)
- Ročno preverjanje vseh 3868 pravil v upravljanih pravilih za WAF, da najde in popravi druge morebitne primere čezmernega sledenja nazaj. (Preverjanje končano)
- Vključujemo profiliranje uspešnosti za vsa pravila v testnem nizu. (Predvideno: 19. julij)
- Preklop na mehanizem regularnih izrazov ali - oba zagotavljata garancije za čas delovanja. (Predvideno: 31. julij)
- Ponovno pišemo SOP za uvajanje pravil po stopnjah, kot druga programska oprema v Cloudflare, hkrati pa imamo možnost nujne globalne uvedbe, če so se napadi že začeli.
- Razvijamo možnost nujne odstranitve nadzorne plošče in API-ja Cloudflare iz regije Cloudflare.
- Samodejno posodabljanje strani .
Dolgoročno se odmikamo od Lua WAF, ki sem ga napisal pred nekaj leti. Premikanje WAF v . Tako bo WAF hitrejši in bo prejel dodatno stopnjo zaščite.
Zaključek
Ta napaka je povzročila težave nam in našim strankam. Hitro smo ukrepali, da bi popravili situacijo, in zdaj delamo na napakah v procesih, ki so povzročili zrušitev, ter kopljemo še globlje, da bi preprečili morebitne težave z regularnimi izrazi v prihodnosti pri prehodu na novo tehnologijo.
Zelo smo osramočeni zaradi tega izpada in se opravičujemo našim strankam. Upamo, da bodo te spremembe zagotovile, da se kaj takega ne bo ponovilo.
Aplikacija. Regularni izrazi za sledenje nazaj
Da bi razumeli, kako izraz:
(?:(?:"|'|]|}||d
(?:nan|infinity|true|false|null|undefined|symbol|math)|`|-
|+)+[)]*;?((?:s|-|~|!|{}||||+)*.*(?:.*=.*)))pojedel vse vire procesorja, morate vedeti nekaj o tem, kako deluje standardni mehanizem regularnih izrazov. Težava tukaj je vzorec .*(?:.*=.*). (?: in ustrezno ) je nezajemljiva skupina (to pomeni, da je izraz v oklepaju združen kot en izraz).
V kontekstu prekomerne porabe procesorja lahko ta vzorec opišemo kot .*.*=.*. V tej obliki je vzorec videti nepotrebno zapleten. Še pomembneje pa je, da lahko v resničnem svetu izrazi (kot so zapleteni izrazi v pravilih WAF), ki od motorja zahtevajo, da se ujema z fragmentom, ki mu sledi drug fragment, povzročijo katastrofalno povratno sledenje. In zato.
V regularnem izrazu . pomeni, da se morate ujemati z enim znakom, .* - ujemanje z nič ali več znaki "pohlepno", to je zajem največjega števila znakov, tako da .*.*=.* pomeni ujemanje z nič ali več znaki, nato ujemanje z nič ali več znaki, iskanje dobesednega znaka =, ujemanje z nič ali več znaki.
Vzemimo testno linijo x=x. Ustreza izrazu .*.*=.*. .*.* preden se enačaj ujema s prvim x (ena od skupin .* соответствующий x, in drugi - nič znakov). .* po = zadnje tekme x.
Ta primerjava zahteva 23 korakov. Prva skupina .* в .*.*=.* deluje pohlepno in se ujema s celotno vrvico x=x. Motor se premakne v naslednjo skupino .*. Nimamo več znakov za ujemanje, zato druga skupina .* ujema z nič znaki (to je dovoljeno). Nato se motor premakne na znak =. Ni več simbolov (prva skupina .* uporabil celoten izraz x=x), ni primerjave.
In potem se mehanizem regularnih izrazov vrne na začetek. Preide v prvo skupino .* in ga primerja с x= (namesto x=x), nato pa prevzame drugo skupino .*. Druga skupina .* se primerja z drugim xin spet nimamo nobenega znaka. In ko motor spet doseže = в .*.*=.*, nič ne deluje. In spet se vrne nazaj.
Tokrat skupina .* še ujema x=, ampak druga skupina .* nič več x, in nič znakov. Motor poskuša najti dobesedni značaj = v vzorcu .*.*=.*, vendar ne pride ven (navsezadnje ga je prva skupina že zasedla .*). In spet se vrne nazaj.
Tokrat prva skupina .* sprejme samo prvi x. Toda druga skupina .* "pohlepno" zajema =x. Ste že uganili, kaj se bo zgodilo? Motor poskuša ustrezati dobesednemu =, spodleti in se ponovno vrne nazaj.
Prva skupina .* še vedno ustreza prvemu x. Drugič .* samo vzame =. Seveda se motor ne more kosati z dobesednim =, ker je druga skupina to že storila .*. In spet vračanje nazaj. In poskušamo ujemati niz treh znakov!
Kot rezultat, prva skupina .* se ujema samo s prvim x, drugič .* - z nič znaki in motor se končno ujema z dobesednim = v izrazu с = v vrsti. Naslednja je zadnja skupina .* se primerja z zadnjim x.
23 korakov samo za x=x. Oglejte si kratek video o uporabi Perla , ki prikazuje, kako nastanejo koraki in vračanje nazaj.
Že to je veliko dela, a kaj ko namesto x=x bomo imeli x=xx? To je 33 korakov. In če x=xxx? 45. Razmerje ni linearno. Graf prikazuje primerjavo iz x=x za x=xxxxxxxxxxxxxxxxxxxx (20 x po =). Če imamo 20 x po =, motor dokonča ujemanje v 555 korakih! (Še več, če smo izgubili x= in niz je preprosto sestavljen iz 20 x, bo motor naredil 4067 korakov, da ugotovi, da ni ujemanj).
Ta videoposnetek prikazuje vse povratne informacije za primerjavo x=xxxxxxxxxxxxxxxxxxxx:
Težava je v tem, da ko se velikost niza poveča, čas ujemanja raste super-linearno. Toda stvari se lahko še poslabšajo, če je regularni izraz nekoliko spremenjen. Recimo, da smo imeli .*.*=.*; (to pomeni, da je bil na koncu vzorca dobesedno podpičje). Na primer, da se ujema z izrazom, kot je foo=bar;.
In tu bi bilo vračanje nazaj prava katastrofa. Za primerjavo x=x potrebnih bo 90 korakov, ne 23. In to število hitro narašča. Primerjati x= in 20 x, potrebnih je 5353 korakov. Tukaj je grafikon. Poglejte vrednosti osi Y v primerjavi s prejšnjim grafikonom.
Če vas zanima, si oglejte vseh 5353 neuspelih korakov ujemanja x=xxxxxxxxxxxxxxxxxxxx и .*.*=.*;
Z uporabo lenega namesto požrešnega ujemanja je mogoče nadzorovati obseg vračanja nazaj. Če spremenimo prvotni izraz v .*?.*?=.*?, za primerjavo x=x trajalo bo 11 korakov (ne 23). Kar zadeva x=xxxxxxxxxxxxxxxxxxxx. Vse zato, ker ? po .* motorju pove, naj se ujema z najmanjšim številom znakov, preden nadaljuje.
Vendar lene preslikave ne rešijo v celoti težave s sledenjem nazaj. Če nadomestimo katastrofalni primer .*.*=.*; o .*?.*?=.*?;, bo čas izvedbe ostal enak. x=x še vedno zahteva 555 korakov in x= in 20 x - 5353.
Edina stvar, ki jo je mogoče storiti (poleg popolnega prepisovanja vzorca za večjo specifičnost), je opustitev mehanizma regularnih izrazov z njegovim mehanizmom za sledenje nazaj. To bomo počeli v naslednjih nekaj tednih.
Rešitev tega problema je znana že od leta 1968, ko je Kent Thompson napisal članek (»Metode programiranja: Iskalni algoritem regularnega izraza«). Članek opisuje mehanizem, ki omogoča pretvorbo regularnega izraza v nedeterministične končne avtomate in po spremembi stanja v nedeterminističnih končnih avtomatih uporabo algoritma, katerega čas izvajanja je linearno odvisen od ujemajočega niza.
Metode programiranja
Iskalni algoritem regularnega izraza
Ken Thompson
Bell Telephone Laboratories, Inc., Murray Hill, New JerseyOpisuje metodo za iskanje določenega niza znakov v besedilu in obravnava izvedbo te metode v obliki prevajalnika. Prevajalnik vzame regularni izraz kot izvorno kodo in izdela program IBM 7094 kot objektno kodo. Objektni program sprejme vnos v obliki iskalnega besedila in odda signal vsakič, ko se niz besedila ujema z danim regularnim izrazom. V članku so primeri, težave in rešitve.
Algoritem
Prejšnji iskalni algoritmi so povzročili vračanje nazaj, če delno uspešno iskanje ni dalo rezultata.V načinu prevajanja algoritem ne deluje s simboli. Navodila posreduje prevedeni kodi. Izvajanje je zelo hitro – po prenosu podatkov na vrh trenutnega seznama samodejno poišče vse možne zaporedne znake v regularnem izrazu.
Algoritem zbiranja in iskanja je vključen v urejevalnik besedila s časovno delitvijo kot kontekstualno iskanje. Seveda pa to še zdaleč ni edina uporaba takšnega iskalnega postopka. Na primer, različica tega algoritma se uporablja kot iskanje simbolov v tabeli v asemblerju.
Predpostavlja se, da bralec pozna regularne izraze in računalniški programski jezik IBM 7094.Prevajalnik
Prevajalnik je sestavljen iz treh stopenj, ki potekajo vzporedno. Prva stopnja je filtriranje sintakse, ki omogoča prehod le sintaktično pravilnim regularnim izrazom. Ta korak prav tako vstavi operator »·« za ujemanje z regularnimi izrazi. V drugem koraku se regularni izraz pretvori v postfiksno obliko. Na tretji stopnji se ustvari objektna koda. Prvi dve stopnji sta očitni in na njih se ne bomo zadrževali.
Thompsonov članek ne govori o nedeterminističnih končnih avtomatih, vendar dobro razloži linearni časovni algoritem in predstavi program ALGOL-60, ki generira kodo zbirnega jezika za IBM 7094. Implementacija je zapletena, vendar je ideja zelo preprosta.
trenutna iskalna pot. Predstavljen je z ikono ⊕ z enim vhodom in dvema izhodoma.
Slika 1 prikazuje funkcije tretjega koraka prevajanja pri preoblikovanju primera regularnega izraza. Prvi trije znaki v primeru so a, b, c in vsak ustvari vnos v sklad S[i] in polje NNODE.NNODE v obstoječo kodo za ustvarjanje nastalega regularnega izraza v enem vnosu v sklad (glejte sliko 5)
Tako bi izgledal regularni izraz .*.*=.*, če si predstavljate kot na slikah iz Thompsonovega članka.
Na sl. 0 obstaja pet stanj, ki se začnejo z 0, in 3 cikli, ki se začnejo s stanji 1, 2 in 3. Ti trije cikli ustrezajo trem .* v regularnem izrazu. 3 ovali s pikami ustrezajo enemu simbolu. Oval z znakom = se ujema z dobesednim znakom =. Stanje 4 je dokončno. Če ga dosežemo, se regularni izraz ujema.
Če želite videti, kako je mogoče tak diagram stanja uporabiti za ujemanje regularnih izrazov .*.*=.*, si bomo ogledali ujemanje nizov x=x. Program se začne iz stanja 0, kot je prikazano na sl. 1.
Da ta algoritem deluje, mora biti stanje avtomat v več stanjih hkrati. Nedeterministični končni stroj bo naredil vse možne prehode hkrati.
Preden ima čas za branje vhodnih podatkov, preide v obe prvi stanji (1 in 2), kot je prikazano na sl. 2.
Na sl. 2 prikazuje, kaj se zgodi, ko pogleda prvega x в x=x. x lahko preslika na zgornjo točko, gre iz stanja 1 in nazaj v stanje 1. Or x lahko preslika na spodnjo točko, gre iz stanja 2 in nazaj v stanje 2.
Po ujemanju prvega x в x=x še vedno smo v stanjih 1 in 2. Ne moremo doseči stanja 3 ali 4, ker potrebujemo dobesedni znak =.
Algoritem nato upošteva = в x=x. Tako kot x pred njim se lahko ujema z eno od zgornjih dveh zank iz stanja 1 v stanje 1 ali iz stanja 2 v stanje 2, vendar se lahko algoritem ujema z literalom = in preide iz stanja 2 v stanje 3 (in takoj 4). To je prikazano na sl. 3.
Algoritem se nato premakne na zadnjega x в x=x. Iz stanja 1 in 2 so možni enaki prehodi nazaj v stanje 1 in 2. Iz stanja 3 x se lahko ujema s točko na desni in se vrne v stanje 3.
Na tej stopnji vsak znak x=x in ker smo dosegli stanje 4, se regularni izraz ujema s tem nizom. Vsak znak je obdelan enkrat, zato je ta algoritem linearen glede na dolžino vhodnega niza. In brez vračanja nazaj.
Očitno po dosegu stanja 4 (ko se algoritem ujema x=) se ujema celoten regularni izraz in algoritem se lahko prekine, ne da bi ga sploh upošteval x.
Ta algoritem je linearno odvisen od velikosti vhodnega niza.
Vir: www.habr.com