Melkein 9 vuotta sitten Cloudflare oli pieni yritys, enkä työskennellyt sille, olin vain asiakas. Kuukausi Cloudflaren käynnistämisen jälkeen sain ilmoituksen, että verkkosivustoni DNS ei näytä toimivan. Cloudflare on tehnyt muutoksen , ja DNS oli rikki.
Kirjoitin välittömästi Matthew Princelle otsikolla "Missä on DNS-ni?" ja hän lähetti takaisin pitkän vastauksen, joka oli täynnä teknisiä yksityiskohtia (), johon vastasin:
Lähettäjä: John Graham-Cumming
Päivämäärä: 7. lokakuuta 2010, klo 9
Aihe: Re: Missä DNS on?
Vastaanottaja: Matthew PrinceHieno raportti, kiitos. Soitan ehdottomasti jos tulee ongelmia. Tästä kannattaa luultavasti kirjoittaa postaus, kun olet kerännyt kaikki tekniset tiedot. Uskon, että ihmiset nauttivat avoimesta ja rehellisestä tarinasta. Varsinkin jos liität siihen kaavioita, jotka osoittavat, kuinka liikenne on kasvanut julkaisun jälkeen.
Sivustollani on hyvä seuranta ja saan tekstiviestin jokaisesta viasta. Valvonta osoittaa, että vika tapahtui kello 13:03:07 - 14:04:12. Testit suoritetaan viiden minuutin välein.
Olen varma, että ymmärrät sen. Oletko varma, ettet tarvitse omaa henkilöä Eurooppaan? 🙂
Ja hän vastasi:
Lähettäjä: Matthew Prince
Päivämäärä: 7. lokakuuta 2010, klo 9
Aihe: Re: Missä DNS on?
Vastaanottaja: John Graham-CummingKiitos. Vastasimme kaikille kirjoittaneille. Olen nyt matkalla toimistolle ja kirjoitetaan jotain blogiin tai laitetaan virallinen postaus ilmoitustaulullemme. Olen täysin samaa mieltä, rehellisyys on kaikki kaikessa.
Nyt Cloudflare on todella iso yritys, työskentelen sille, ja nyt minun on kirjoitettava avoimesti virheestämme, sen seurauksista ja teoistamme.
Heinäkuun 2. päivän tapahtumat
2. heinäkuuta otimme käyttöön uuden säännön Managed Rules for WAFs, jonka vuoksi jokaisessa prosessoriytimessä, joka käsittelee HTTP/HTTPS-liikennettä Cloudflare-verkossa maailmanlaajuisesti. Parannamme jatkuvasti WAF:ien hallittuja sääntöjä vastauksena uusiin haavoittuvuuksiin ja uhkiin. Esimerkiksi toukokuussa meillä oli kiire suojautuaksesi vakavalta SharePointin haavoittuvuudella. WAF:mme ydin on kyky ottaa sääntöjä nopeasti ja maailmanlaajuisesti käyttöön.
Valitettavasti viime torstain päivitys sisälsi säännöllisen lausekkeen, joka tuhlasi liikaa HTTP/HTTPS-suorittimen resursseja taaksepäin. Keskeiset välityspalvelin-, CDN- ja WAF-toiminnot kärsivät tämän seurauksena. Kaavio osoittaa, että prosessoriresurssit HTTP/HTTPS-liikenteen palvelemiseen saavuttavat lähes 100 % verkkomme palvelimilla.
Suorittimen käyttö yhdessä läsnäolopisteessä tapahtuman aikana
Tämän seurauksena asiakkaamme (ja asiakkaidemme asiakkaat) päätyivät 502-virhesivulle Cloudflare-verkkotunnuksissa. 502 virhettä tuottivat Cloudflaren etupään verkkopalvelimet, joissa oli vielä vapaita ytimiä, mutta jotka eivät kyenneet kommunikoimaan HTTP/HTTPS-liikennettä käsittelevien prosessien kanssa.
Tiedämme, kuinka paljon vaivaa tämä on aiheuttanut asiakkaillemme. Häpeämme hirveästi. Ja tämä epäonnistuminen esti meitä käsittelemästä tapausta tehokkaasti.
Jos olit yksi näistä asiakkaista, olet todennäköisesti peloissasi, vihainen ja järkyttynyt. Lisäksi meillä ei ole ollut a . Suuri suorittimen kulutus johtui yhdestä WAF-säännöstä, jossa oli huonosti muotoiltu säännöllinen lauseke, joka johti liialliseen taaksepäin. Tässä on syyllinen ilmaus: (?:(?:"|'|]|}||d|(?:nan|infinity|true|false|null|undefined|symbol|math)|`|-|+)+[)]*;?((?:s|-|~|!|{}||||+)*.*(?:.*=.*)))
Vaikka tämä on sinänsä mielenkiintoinen (ja puhun siitä yksityiskohtaisemmin alla), Cloudflare-palvelu oli poissa käytöstä 27 minuuttia paitsi huonon säännöllisen lausekkeen vuoksi. Kesti jonkin aikaa kuvailla epäonnistumiseen johtanutta tapahtumasarjaa, joten reagoimme hitaasti. Viestin lopussa kuvailen paluumatkaa säännöllisessä lausekkeessa ja kerron, mitä tehdä sen kanssa.
.То случилось
Aloitetaan järjestyksessä. Kaikki ajat ovat UTC:ssä.
Klo 13 palomuuritiimin insinööri teki pienen muutoksen havaitsemissääntöihin käyttämällä automaattista prosessia. Tämän mukaisesti luotiin muutospyyntölippu. Hallinnoimme tällaisia lippuja Jiran kautta (kuvakaappaus alla).
Kolmen minuutin kuluttua ilmestyi PagerDutyn ensimmäinen sivu, joka ilmoitti WAF-ongelmasta. Tämä oli synteettinen testi, joka testaa WAF:ien (meillä on niitä satoja) toimivuutta Cloudflaren ulkopuolella normaalin toiminnan seuraamiseksi. Tätä seurasi välittömästi sivuja, joissa oli varoituksia muiden Cloudflaren kokonaispalvelutestien epäonnistumisesta, maailmanlaajuisista liikenneongelmista, laajalle levinneistä 3-virheistä ja lukuisista pisteistämme (PoP) eri puolilla maailmaa sijaitsevista kaupungeista saatuja raportteja, jotka kertoivat puutteesta. CPU-resursseista.
Sain useita näistä hälytyksistä, ryntäsin ulos kokouksesta ja olin matkalla pöytään, kun ratkaisukehitysosastomme johtaja sanoi, että olemme menettäneet 80 % liikenteestämme. Juoksin SRE-insinööriemme luo, jotka jo työskentelivät ongelman parissa. Aluksi luulimme, että se oli jonkinlainen tuntematon hyökkäys.
Cloudflare SRE:n insinöörit ovat hajallaan ympäri maailmaa ja seuraavat tilannetta ympäri vuorokauden. Tyypillisesti nämä hälytykset ilmoittavat tietyistä paikallisista ongelmista, joiden laajuus on rajoitettu, niitä seurataan sisäisillä kojelaudoilla ja ne ratkaistaan useita kertoja päivässä. Mutta nämä sivut ja ilmoitukset osoittivat jotain todella vakavaa, ja SRE:n insinöörit ilmoittivat välittömästi vakavuustason P0 ja ottivat yhteyttä johtoon ja järjestelmäinsinööreihin.
Lontoon insinöörimme kuuntelivat tuolloin luentoa pääsalissa. Luento oli keskeytettävä, kaikki kokoontuivat suureen kokoushuoneeseen ja kutsuttiin lisää asiantuntijoita. Tämä ei ollut tyypillinen ongelma, jonka SRE:t voisivat käsitellä itse. Tarvittiin kiireellisesti oikeat asiantuntijat.
Klo 14 totesimme, että ongelma oli WAF:ssa eikä hyökkäystä ollut. Suorituskykytiimi veti suorittimen tiedot ja kävi selväksi, että WAF oli syyllinen. Toinen työntekijä vahvisti tämän teorian käyttämällä stracea. Joku muu näki lokeista, että WAF:ssa oli ongelma. Klo 00 koko tiimi tuli luokseni, kun ehdotettiin maailmanlaajuisen tappamisen käyttöä, Cloudflaren sisäänrakennettua mekanismia, joka sammuttaa yhden komponentin maailmanlaajuisesti.
Se, kuinka teimme maailmanlaajuisen tappamisen WAF:lle, on eri tarina. Se ei ole niin yksinkertaista. Käytämme omia tuotteitamme ja palvelustamme lähtien ei toiminut, emme voineet todentaa ja kirjautua sisään sisäiseen ohjauspaneeliin (kun kaikki oli korjattu, saimme tietää, että jotkut tiimin jäsenet olivat menettäneet pääsyn suojausominaisuuden vuoksi, joka poistaa kirjautumistiedot käytöstä, jos sisäistä ohjauspaneelia ei käytetä pitkä aika).
Emmekä päässeet sisäisiin palveluihimme, kuten Jiraan tai rakennusjärjestelmään. Tarvitsimme kiertotapamekanismin, jota käytimme harvoin (tämä on myös selvitettävä). Lopulta yksi insinööri onnistui poistamaan WAF:n käytöstä klo 14, ja klo 07 liikenne- ja prosessoritasot palautuivat normaaliksi kaikkialla. Muut Cloudflaren suojamekanismit toimivat normaalisti.
Sitten aloimme palauttamaan WAF: n. Tilanne oli poikkeuksellinen, joten teimme negatiiviset testit (kysyimme itseltämme, oliko muutos todella ongelma) ja positiiviset testit (varmistimme, että palautus toimii) yhdessä kaupungissa erillisellä liikenteellä siirtäen maksavia asiakkaita sieltä.
Klo 14:52 olimme vakuuttuneita siitä, että ymmärsimme syyn ja teimme korjauksen ja otimme WAF:n käyttöön uudelleen.
Kuinka Cloudflare toimii
Cloudflarella on insinööritiimi, joka on omistautunut WAF-sääntöjen hallintaan. He pyrkivät parantamaan havaitsemisastetta, vähentämään vääriä positiivisia tuloksia ja reagoimaan nopeasti uusiin uhkiin niiden ilmaantuessa. Viimeisten 60 päivän aikana on käsitelty 476 WAF:n hallittujen sääntöjen muutospyyntöä (keskimäärin yksi joka 3. tunti).
Tämä muutos piti ottaa käyttöön simulaatiotilassa, jossa todellinen asiakasliikenne kulkee säännön läpi, mutta mitään ei ole estetty. Käytämme tätä tilaa sääntöjen tehokkuuden testaamiseen ja väärien positiivisten ja väärien negatiivisten määrien mittaamiseen. Mutta jopa simulaatiotilassa säännöt on todella suoritettava, ja tässä tapauksessa sääntö sisälsi säännöllisen lausekkeen, joka kulutti liikaa prosessoriresursseja.
Kuten yllä olevasta muutospyynnöstä näkyy, meillä on tämän tyyppistä käyttöönottoa varten käyttöönottosuunnitelma, palautussuunnitelma ja linkki sisäiseen standardikäyttömenettelyyn (SOP). Säännön muuttamisen SOP mahdollistaa sen julkaisemisen maailmanlaajuisesti. Itse asiassa Cloudflaressa asiat tehdään täysin eri tavalla, ja SOP määrää, että toimitamme ohjelmiston testausta ja sisäistä käyttöä varten ensin sisäiseen läsnäolopisteeseen (PoP) (jota työntekijämme käyttävät) ja sitten pienelle määrälle asiakkaita eristyneeseen paikkaan, sitten suurelle määrälle asiakkaita ja vasta sitten koko maailmalle.
Tältä se näyttää. Käytämme gitiä sisäisesti BitBucketin kautta. Muutosten parissa työskentelevät insinöörit lähettävät koodin, joka on rakennettu TeamCitylle, ja kun koontiversio menee läpi, määrätään tarkistajat. Kun vetopyyntö on hyväksytty, koodi kootaan ja testisarja suoritetaan (uudelleen).
Jos koontiversio ja testit valmistuvat onnistuneesti, Jiraan luodaan muutospyyntö ja asianmukaisen esimiehen tai liidin on hyväksyttävä muutos. Hyväksynnän jälkeen käyttöönotto tapahtuu niin kutsuttuun "PoP-eläintarhaan": DOG, PIG ja (koira, sika ja kanarialintu).
DOG PoP on Cloudflare PoP (kuten kaikki muutkin kaupungeissamme), jota käyttävät vain Cloudflaren työntekijät. Sisäiseen käyttöön tarkoitettu PoP mahdollistaa ongelmien havaitsemisen ennen kuin asiakasliikenne alkaa virrata ratkaisuun. Hyödyllinen juttu.
Jos DOG-testi onnistuu, koodi siirtyy PIG (marsu) -vaiheeseen. Tämä on Cloudflare PoP, jossa pieni määrä ilmaista asiakasliikennettä virtaa uuden koodin kautta.
Jos kaikki on hyvin, koodi menee Canarylle. Meillä on kolme Canary PoPia eri puolilla maailmaa. Niissä maksullisten ja ilmaisten asiakkaiden liikenne kulkee uuden koodin läpi, ja tämä on viimeinen virhetarkistus.
Ohjelmiston julkaisuprosessi Cloudflaressa
Jos koodi on kunnossa Kanarialla, vapautamme sen. Kaikkien vaiheiden - KOIRA, PIG, Kanarian, koko maailman - läpi käyminen kestää useita tunteja tai päiviä koodin muutoksesta riippuen. Cloudflaren verkon ja asiakkaiden monimuotoisuuden vuoksi testaamme koodia perusteellisesti ennen kuin julkaisemme sen maailmanlaajuisesti kaikille asiakkaille. Mutta WAF ei nimenomaisesti noudata tätä prosessia, koska uhkiin on reagoitava nopeasti.
WAF-uhat
Muutaman viime vuoden aikana yleisten sovellusten uhkien määrä on lisääntynyt merkittävästi. Tämä johtuu ohjelmistojen testaustyökalujen paremmasta saatavuudesta. Esimerkiksi kirjoitimme äskettäin aiheesta ).
Lähde:
Hyvin usein proof of concept luodaan ja julkaistaan välittömästi Githubissa, jotta sovellusta ylläpitävät tiimit voivat nopeasti testata sitä ja varmistaa, että se on asianmukaisesti suojattu. Siksi Cloudflare tarvitsee kykyä vastata uusiin hyökkäyksiin mahdollisimman nopeasti, jotta asiakkailla on mahdollisuus korjata ohjelmistonsa.
Loistava esimerkki Cloudflaren nopeasta reagoinnista on SharePointin haavoittuvuussuojausten käyttöönotto toukokuussa (). Melkein heti ilmoitusten antamisen jälkeen havaitsimme valtavan määrän yrityksiä hyödyntää asiakkaidemme SharePoint-asennuksissa olevaa haavoittuvuutta. Kaverimme seuraavat jatkuvasti uusia uhkia ja kirjoittavat sääntöjä asiakkaidemme suojelemiseksi.
Torstaina ongelman aiheuttaneen säännön piti suojata sivustojen välistä komentosarjaa (XSS) vastaan. Tällaiset hyökkäykset ovat myös yleistyneet viime vuosina.
Lähde:
Vakiomenettely WAF:n hallitun säännön muuttamiseksi on suorittaa jatkuva integraatiotestaus (CI) ennen maailmanlaajuista käyttöönottoa. Viime torstaina teimme tämän ja julkaisimme säännöt. Klo 13 insinööri lähetti hyväksytyn vetopyynnön muutoksella.
Klo 13 TeamCity keräsi säännöt, suoritti testejä ja antoi lupaa. WAF-testisarja testaa WAF:n ydintoimintoja ja koostuu suuresta määrästä yksittäisten toimintojen yksikkötestejä. Yksikkötestien jälkeen testasimme WAF:n sääntöjä suurella määrällä HTTP-pyyntöjä. HTTP-pyynnöt tarkistavat, mitkä pyynnöt WAF:n tulisi estää (hyökkäyksen sieppaamiseksi) ja mitkä voidaan päästää läpi (jotta ei estä kaikkea ja vältytään vääriltä positiivisilta). Emme kuitenkaan testanneet liiallista suorittimen käyttöä, ja aiempien WAF-koontiversioiden lokien tarkastelu osoittaa, että sääntötestin suoritusaika ei pidentynyt, ja oli vaikea epäillä, etteikö resursseja riittäisi.
Testit läpäisivät ja TeamCity aloitti muutoksen automaattisesti käyttöönoton kello 13.
Elohopea
WAF-säännöt keskittyvät välittömien uhkien korjaamiseen, joten otamme ne käyttöön Quicksilverin hajautetun avainarvovaraston avulla, joka levittää muutokset maailmanlaajuisesti sekunneissa. Kaikki asiakkaamme käyttävät tätä tekniikkaa, kun he muuttavat asetuksia kojelaudassa tai API:n kautta, ja sen ansiosta reagoimme muutoksiin salamannopeasti.
Emme ole puhuneet paljon Quicksilveristä. Aiemmin käytimme maailmanlaajuisesti hajautettuna avainarvomyymälänä, mutta sen kanssa oli toiminnallisia ongelmia, ja teimme oman myymälämme, jota oli kopioitu yli 180 kaupungissa. Käytämme nyt Quicksilveriä konfiguraatiomuutosten siirtämiseen asiakkaille, WAF-sääntöjen päivittämiseen ja asiakkaiden kirjoittaman JavaScript-koodin jakamiseen Cloudflare Workersille.
Maailmanlaajuisen kokoonpanomuutoksen tekeminen kestää vain muutaman sekunnin kojelaudan painikkeen painamisesta tai API:n kutsumisesta. Asiakkaat pitivät tästä asennuksen nopeudesta. Ja Workers tarjoaa heille lähes välittömän maailmanlaajuisen ohjelmiston käyttöönoton. Quicksilver levittää keskimäärin noin 350 muutosta sekunnissa.
Ja Quicksilver on erittäin nopea. Keskimäärin saavutimme 99. prosenttipisteen 2,29 sekuntia muutosten levittämiseksi jokaiseen tietokoneeseen maailmanlaajuisesti. Nopeus on yleensä hyvä asia. Loppujen lopuksi, kun otat toiminnon käyttöön tai tyhjennät välimuistin, se tapahtuu melkein välittömästi ja kaikkialla. Koodin lähettäminen Cloudflare Workersin kautta tapahtuu samalla nopeudella. Cloudflare lupaa asiakkailleen nopeat päivitykset oikeaan aikaan.
Mutta tässä tapauksessa nopeus oli meille julma vitsi, ja säännöt muuttuivat kaikkialla muutamassa sekunnissa. Olet ehkä huomannut, että WAF-koodi käyttää Lua. Cloudflare käyttää Luaa laajasti tuotannossa ja yksityiskohdissa me . Lua WAF käyttää sisäisesti ja käyttää backtracking yhteensopivuutta. Sillä ei ole mekanismeja, jotka suojaavat käsistä riistäytyviltä ilmauksilta. Alla kerron lisää tästä ja mitä teemme asian eteen.
Ennen sääntöjen käyttöönottoa kaikki sujui hyvin: vetopyyntö luotiin ja hyväksyttiin, CI/CD-putki keräsi ja testasi koodin, muutospyyntö lähetettiin käyttöönottoa ja palautusta säätelevän SOP:n mukaisesti ja käyttöönotto saatiin päätökseen.
Cloudflare WAF -käyttöönottoprosessi
Mikä meni pieleen
Kuten sanoin, otamme käyttöön kymmeniä uusia WAF-sääntöjä joka viikko, ja meillä on monia järjestelmiä, jotka suojaavat tällaisen käyttöönoton kielteisiltä seurauksilta. Ja kun jokin menee pieleen, se on yleensä useiden olosuhteiden yhdistelmä samanaikaisesti. Jos löydät vain yhden syyn, tämä on tietysti rauhoittavaa, mutta se ei ole aina totta. Nämä ovat syitä, jotka yhdessä johtivat HTTP/HTTPS-palvelumme epäonnistumiseen.
- Insinööri kirjoitti säännöllisen lausekkeen, joka voi johtaa liialliseen .
- Ominaisuus, joka olisi voinut estää säännöllistä lauseketta tuhlaamasta liikaa CPU:ta, poistettiin erehdyksessä useita viikkoja aiemmin suoritetussa WAF:n uudelleenmuodostuksessa – uudelleenmuodostusta tarvittiin, jotta WAF kuluttaisi vähemmän resursseja.
- Säännöllisen lausekkeen moottorilla ei ollut takeita monimutkaisuudesta.
- Testisarja ei pystynyt havaitsemaan liiallista suorittimen kulutusta.
- SOP mahdollistaa ei-kiireellisten sääntömuutosten käyttöönoton maailmanlaajuisesti ilman monivaiheista prosessia.
- Palautussuunnitelma vaati täyden WAF-koontiversion suorittamisen kahdesti, mikä kesti kauan.
- Ensimmäinen hälytys globaaleista liikenneongelmista annettiin liian myöhään.
- Tilasivun päivittäminen kesti hetken.
- Meillä oli ongelmia päästä järjestelmiin häiriön vuoksi, eikä ohitusmenettelyä ollut vakiintunut.
- SRE:n insinöörit menettivät pääsyn joihinkin järjestelmiin, koska heidän valtakirjansa vanhenivat turvallisuussyistä.
- Asiakkaillamme ei ollut pääsyä Cloudflaren kojelautaan tai sovellusliittymään, koska he käyvät Cloudflare-alueen läpi.
Mikä on muuttunut viime torstaista
Ensinnäkin lopetimme kokonaan kaiken työn WAF-julkaisujen parissa ja teemme seuraavaa:
- Otamme uudelleen käyttöön poistamamme suorittimen liikakäyttösuojan. (Valmis)
- Tarkista manuaalisesti kaikki 3868 XNUMX sääntöä hallituista säännöistä, jotta WAF löytää ja korjaa muut mahdolliset liiallisen perääntymisen tapaukset. (Vahvistus suoritettu)
- Sisällytämme suorituskykyprofiloinnin kaikille testisarjan säännöille. (Odotettu: 19. heinäkuuta)
- Vaihtaminen säännölliseen lausekkeeseen tai - Molemmat tarjoavat käyttöaikatakuun. (Odotettu: 31. heinäkuuta)
- Kirjoitamme SOP:n uudelleen ottamaan sääntöjä käyttöön vaiheittain, kuten muutkin Cloudflaren ohjelmistot, mutta samalla pystymme käyttämään maailmanlaajuista hätäkäyttöönottoa, jos hyökkäykset ovat jo alkaneet.
- Kehitämme kykyä poistaa kiireellisesti Cloudflaren kojelauta ja API Cloudflare-alueelta.
- Automaattiset sivupäivitykset .
Pitkällä aikavälillä olemme siirtymässä pois Lua WAFista, jonka kirjoitin muutama vuosi sitten. Siirretään WAF kohteeseen . Näin WAF on nopeampi ja saa lisäsuojan.
Johtopäätös
Tämä vika aiheutti ongelmia meille ja asiakkaillemme. Toimimme nopeasti tilanteen korjaamiseksi ja nyt selvitämme virheitä prosesseissa, jotka aiheuttivat kaatumisen, sekä kaivamme vielä syvemmälle suojataksemme mahdollisia ongelmia säännöllisten lausekkeiden kanssa tulevaisuudessa siirryttäessä uuteen tekniikkaan.
Olemme hyvin häpeissämme tästä katkosta ja pahoittelemme asiakkaitamme. Toivomme, että nämä muutokset varmistavat, ettei tällaista toistu.
Sovellus. Säännöllisten lausekkeiden peruuttaminen
Ymmärtääksesi, miten ilmaus:
(?:(?:"|'|]|}||d
(?:nan|infinity|true|false|null|undefined|symbol|math)|`|-
|+)+[)]*;?((?:s|-|~|!|{}||||+)*.*(?:.*=.*)))söivät kaikki suorittimen resurssit, sinun on tiedettävä hieman, kuinka tavallinen säännöllinen lausekemoottori toimii. Ongelma tässä on kuvio .*(?:.*=.*). (?: ja vastaava ) on ei-kaappaava ryhmä (eli suluissa oleva lauseke on ryhmitelty yhdeksi lausekkeeksi).
Liiallisen suorittimen kulutuksen yhteydessä tätä mallia voidaan kuvata seuraavasti .*.*=.*. Tässä muodossa kuvio näyttää tarpeettoman monimutkaiselta. Mutta mikä vielä tärkeämpää, todellisessa maailmassa lausekkeet (kuten monimutkaiset lausekkeet WAF-säännöissä), jotka pyytävät moottoria vastaamaan fragmenttiin, jota seuraa toinen fragmentti, voivat johtaa katastrofaaliseen perääntymiseen. Ja siksi.
Säännöllisissä lausekkeissa . tarkoittaa, että sinun on löydettävä yksi merkki, .* - vastaa nollaa tai useampaa merkkiä "ahneesti", eli sieppaa enintään merkkiä, jotta .*.*=.* tarkoittaa, että vastaa nollaa tai useampaa merkkiä, vastaa sitten nollaa tai useampaa merkkiä, etsi kirjaimellinen = merkki, vastaa nollaa tai useampaa merkkiä.
Otetaan testiviiva x=x. Se vastaa ilmaisua .*.*=.*. .*.* ennen kuin yhtäläisyysmerkki vastaa ensimmäistä x (yksi ryhmistä .* соответствует x, ja toinen - nolla merkkiä). .* jälkeen = vastaa viimeistä x.
Tämä vertailu vaatii 23 vaihetta. Ensimmäinen ryhmä .* в .*.*=.* toimii ahneesti ja sopii koko merkkijonoon x=x. Moottori siirtyy seuraavaan ryhmään .*. Meillä ei ole enää vastaavia hahmoja, joten toinen ryhmä .* vastaa nollaa merkkiä (tämä on sallittua). Sitten moottori siirtyy merkkiin =. Ei enää symboleita (ensimmäinen ryhmä .* käytti koko ilmaisua x=x), vertailua ei tapahdu.
Ja sitten säännöllinen lausekemoottori palaa alkuun. Hän siirtyy ensimmäiseen ryhmään .* ja vertaa sitä с x= (eikä x=x) ja ottaa sitten toisen ryhmän .*. Toinen ryhmä .* verrataan toiseen x, eikä meilläkään ole enää yhtään hahmoa jäljellä. Ja kun moottori taas saavuttaa = в .*.*=.*, mikään ei toimi. Ja hän perääntyy taas.
Tällä kertaa ryhmä .* vastaa edelleen x=, mutta toinen ryhmä .* ei enempää x, ja nolla merkkiä. Moottori yrittää löytää kirjaimellisen hahmon = kuviossa .*.*=.*, mutta ei tule ulos (loppujen lopuksi ensimmäinen ryhmä on jo miehittänyt sen .*). Ja hän perääntyy taas.
Tällä kertaa ensimmäinen ryhmä .* kestää vain ensimmäisen x. Mutta toinen ryhmä .* "ahneesti" vangitsee =x. Oletko jo arvannut mitä tapahtuu? Moottori yrittää vastata kirjaimellista =, epäonnistuu ja tekee uuden perääntymisen.
Ensimmäinen ryhmä .* vastaa edelleen ensimmäistä x... Toinen .* vain ottaa =. Tietenkään moottori ei voi vastata kirjaimellista =, koska toinen ryhmä on jo tehnyt tämän .*. Ja taas takaperin. Ja yritämme yhdistää kolmen merkin merkkijonoa!
Tämän seurauksena ensimmäinen ryhmä .* vastaa vain ensimmäistä x, toinen .* - nollalla merkillä, ja moottori lopulta vastaa kirjaimellista = ilmaisussa с = linjassa. Seuraavana on viimeinen ryhmä .* verrataan viimeiseen x.
23 askelta vain varten x=x. Katso lyhyt video Perlin käytöstä , joka näyttää kuinka askeleet ja paluu tapahtuu.
Tämä on jo paljon työtä, mutta entä jos sen sijaan x=x meillä tulee olemaan x=xx? Se on 33 askelta. Ja jos x=xxx? 45. Suhde ei ole lineaarinen. Kaavio näyttää vertailun kohteesta x=x до x=xxxxxxxxxxxxxxxxxxxx (20 x jälkeen =). Jos meillä on 20 x jälkeen =, moottori suorittaa yhteensovituksen 555 vaiheessa! (Lisäksi, jos olemme hävinneet x= ja merkkijono koostuu yksinkertaisesti 20:stä x, moottori ottaa 4067 askelta ymmärtääkseen, ettei osumia ole).
Tämä video näyttää kaikki paluumatkat vertailun vuoksi x=xxxxxxxxxxxxxxxxxxxx:
Ongelmana on, että merkkijonon koon kasvaessa sovitusaika kasvaa superlineaarisesti. Mutta asiat voivat pahentua entisestään, jos säännöllistä lauseketta muutetaan hieman. Sanotaan, että meillä oli .*.*=.*; (eli kuvion lopussa oli kirjaimellinen puolipiste). Esimerkiksi vastaamaan lauseketta kuten foo=bar;.
Ja tässä perääntyminen olisi todellinen katastrofi. Vertailun vuoksi x=x se kestää 90 askelta, ei 23. Ja tämä määrä kasvaa nopeasti. Verrata x= ja 20 x, 5353 askelta tarvitaan. Tässä on kaavio. Katso akselin arvot Y edelliseen kaavioon verrattuna.
Jos olet kiinnostunut, tarkista kaikki 5353 XNUMX epäonnistunutta hakuvaihetta x=xxxxxxxxxxxxxxxxxxxx и .*.*=.*;
Käyttämällä pikemminkin laiskoja kuin ahneita hakuja, perääntymisen laajuutta voidaan hallita. Jos muutamme alkuperäisen lausekkeen muotoon .*?.*?=.*?, vertailun vuoksi x=x se kestää 11 askelta (ei 23). Mitä tulee x=xxxxxxxxxxxxxxxxxxxx. Kaikki koska ? jälkeen .* käskee moottorin vastaamaan vähimmäismäärään merkkejä ennen kuin jatkat eteenpäin.
Mutta laiska kartoitus ei täysin ratkaise paluuongelmaa. Jos korvaamme katastrofaalisen esimerkin .*.*=.*; päälle .*?.*?=.*?;, suoritusaika pysyy samana. x=x vaatii edelleen 555 askelta, ja x= ja 20 x - 5353.
Ainoa asia, joka voidaan tehdä (paitsi kirjoittaa kuvio kokonaan uudelleen tarkemman tarkkuuden lisäämiseksi), on hylätä säännöllinen lausekemoottori sen paluumekanismilla. Tätä teemme muutaman seuraavan viikon aikana.
Ratkaisu tähän ongelmaan on ollut tiedossa vuodesta 1968, jolloin Kent Thompson kirjoitti artikkelin ("Ohjelmointimenetelmät: Säännöllisten lausekkeiden hakualgoritmi"). Artikkelissa kuvataan mekanismi, jonka avulla voit muuntaa säännöllisen lausekkeen ei-deterministisille äärellistiloisille koneille ja käyttää ei-determinististen äärellistilakoneiden tilanmuutosten jälkeen algoritmia, jonka suoritusaika riippuu lineaarisesti sovitetusta merkkijonosta.
Ohjelmointimenetelmät
Säännöllisten lausekkeiden hakualgoritmi
Ken Thompson
Bell Telephone Laboratories, Inc., Murray Hill, New JerseySe kuvaa menetelmän tietyn merkkijonon etsimiseksi tekstistä ja käsittelee tämän menetelmän toteuttamista kääntäjämuodossa. Kääntäjä ottaa säännöllisen lausekkeen lähdekoodiksi ja tuottaa IBM 7094 -ohjelman objektikoodina. Kohdeohjelma ottaa syötteen hakutekstin muodossa ja lähettää signaalin joka kerta, kun tekstijonoa verrataan tiettyyn säännölliseen lausekkeeseen. Artikkelissa on esimerkkejä, ongelmia ja ratkaisuja.
Algoritmi
Aiemmat hakualgoritmit johtivat taaksepäin, jos osittain onnistunut haku ei tuottanut tulosta.Käännöstilassa algoritmi ei toimi symbolien kanssa. Se välittää ohjeet käännetylle koodille. Suoritus on erittäin nopeaa - siirrettyään tiedot nykyisen luettelon alkuun, se etsii automaattisesti kaikki mahdolliset peräkkäiset merkit säännöllisessä lausekkeessa.
Kokoonpano- ja hakualgoritmi sisältyy aikajakotekstieditoriin kontekstuaalisena hauna. Tämä ei tietenkään ole ainoa tällaisen hakumenettelyn sovellus. Esimerkiksi tämän algoritmin muunnelmaa käytetään symbolien hakuun taulukossa assemblerissa.
Lukijan oletetaan tuntevan säännölliset lausekkeet ja IBM 7094 -tietokoneohjelmointikielen.Kääntäjä
Kääntäjä koostuu kolmesta rinnakkain kulkevasta vaiheesta. Ensimmäinen vaihe on syntaksisuodatus, jonka avulla vain syntaktisesti oikeat säännölliset lausekkeet pääsevät läpi. Tämä vaihe lisää myös operaattorin "·" vastaamaan säännöllisiä lausekkeita. Toisessa vaiheessa säännöllinen lauseke muunnetaan postfix-muotoon. Kolmannessa vaiheessa luodaan objektikoodi. Ensimmäiset 2 vaihetta ovat ilmeisiä, emmekä käsittele niitä.
Thompsonin artikkelissa ei puhuta epädeterministisista äärellistiloisista koneista, mutta se selittää hyvin lineaarisen aika-algoritmin ja esittelee ALGOL-60-ohjelman, joka luo kokoonpanokielikoodin IBM 7094:lle. Toteutus on hankala, mutta idea on hyvin yksinkertainen.
nykyinen hakupolku. Sitä edustaa ⊕-kuvake, jossa on yksi tulo ja kaksi lähtöä.
Kuvassa 1 on esitetty kolmannen käännösvaiheen funktiot muunnettaessa säännöllistä lauseketta esimerkkiä. Esimerkin kolme ensimmäistä merkkiä ovat a, b, c, ja jokainen luo pinomerkinnän S[i] ja NNODE-kentän.NNODE olemassa olevaan koodiin tuloksena olevan säännöllisen lausekkeen luomiseksi yhdessä pinomerkinnässä (katso kuva 5)
Tältä säännöllinen lauseke näyttäisi .*.*=.*, jos kuvittelet sen kuten Thompsonin artikkelin kuvissa.
Kuvassa 0 on viisi tilaa, jotka alkavat 0:sta, ja 3 jaksoa, jotka alkavat tiloista 1, 2 ja 3. Nämä kolme jaksoa vastaavat kolmea .* säännöllisessä lausekkeessa. 3 soikeaa pisteillä vastaavat yhtä symbolia. Soikea merkillä = vastaa kirjaimellista merkkiä =. Tila 4 on lopullinen. Jos saavutamme sen, säännöllinen lauseke täsmätään.
Nähdäksesi kuinka tällaista tilakaaviota voidaan käyttää säännöllisten lausekkeiden täsmäykseen .*.*=.*, tarkastelemme merkkijonojen yhdistämistä x=x. Ohjelma alkaa tilasta 0, kuten kuvassa näkyy. 1.
Jotta tämä algoritmi toimisi, tilakoneen on oltava useassa tilassa samanaikaisesti. Epädeterministinen äärellinen kone tekee kaikki mahdolliset siirtymät samanaikaisesti.
Ennen kuin se ehtii lukea syöttödataa, se siirtyy molempiin ensimmäisiin tiloihin (1 ja 2), kuten kuvassa 2 on esitetty. XNUMX.
Kuvassa 2 näyttää mitä tapahtuu, kun hän katsoo ensimmäistä x в x=x. x voi kartoittaa huippupisteeseen siirtymällä tilasta 1 ja takaisin tilaan 1. Or x voi kartoittaa alla olevaan pisteeseen siirtymällä tilasta 2 ja takaisin tilaan 2.
Ensimmäisen sovituksen jälkeen x в x=x olemme edelleen tiloissa 1 ja 2. Emme voi saavuttaa tilaa 3 tai 4, koska tarvitsemme kirjaimellisen merkin =.
Sitten algoritmi ottaa huomioon = в x=x. Kuten x ennen sitä, se voidaan sovittaa jompaankumpaan kahdesta ylimmästä silmukasta tilasta 1 tilaan 1 tai tilasta 2 tilaan 2, mutta algoritmi voi vastata kirjaimellista = ja siirry tilasta 2 tilaan 3 (ja välittömästi 4). Tämä näkyy kuvassa. 3.
Algoritmi siirtyy sitten viimeiseen x в x=x. Tilasta 1 ja 2 samat siirtymät ovat mahdollisia takaisin tiloihin 1 ja 2. Tilasta 3 x voi vastata oikealla olevaa pistettä ja palata tilaan 3.
Tässä vaiheessa jokainen hahmo x=x ja koska olemme saavuttaneet tilan 4, säännöllinen lauseke vastaa tätä merkkijonoa. Jokainen merkki käsitellään kerran, joten tämä algoritmi on lineaarinen syötemerkkijonon pituudessa. Eikä perääntymistä.
Ilmeisesti tilan 4 saavuttamisen jälkeen (kun algoritmi on osunut x=) koko säännöllinen lauseke täsmää, ja algoritmi voi päättyä huomioimatta sitä ollenkaan x.
Tämä algoritmi riippuu lineaarisesti syötetyn merkkijonon koosta.
Lähde: will.com