Byna 9 jaar gelede was Cloudflare 'n klein maatskappy en ek het nie daarvoor gewerk nie, ek was net 'n kliënt. 'N Maand na die bekendstelling van Cloudflare het ek 'n waarskuwing op my webwerf ontvang blyk nie DNS te werk nie. Cloudflare het 'n verandering aan , en daar was 'n gebreekte DNS.
Ek het dadelik vir Matthew Prince 'n e-pos gestuur met die titel "Where's my DNS?" en hy het 'n lang antwoord vol tegniese besonderhede gestuur (), waarop ek geantwoord het:
Van: John Graham-Cumming
Datum: 7 Oktober 2010, 9:14
Onderwerp: Re: Waar is my DNS?
Aan: Matthew PrinceCool verslag, dankie. Ek sal beslis bel as daar probleme is. Waarskynlik die moeite werd om 'n plasing hieroor te skryf wanneer jy al die tegniese inligting versamel. Ek dink mense sal van 'n oop en eerlike storie hou. Veral as jy grafieke daaraan heg om te wys hoe verkeer sedert bekendstelling gegroei het.
Ek het goeie monitering op my webwerf, en ek ontvang SMS'e oor elke mislukking. Monitering toon dat die mislukking van 13:03:07 tot 14:04:12 was. Toetse word elke vyf minute uitgevoer.
Ek is seker jy sal dit alles uitvind. Is jy seker jy het nie jou eie persoon in Europa nodig nie? 🙂
En hy het geantwoord:
Van: Matthew Prince
Datum: 7 Oktober 2010, 9:57
Onderwerp: Re: Waar is my DNS?
Aan: John Graham-CummingDankie. Ons het gereageer op almal wat geskryf het. Ek is nou op pad kantoor toe en ons sal iets op die blog skryf of 'n amptelike plasing op ons bulletin board vaspen. Ek stem heeltemal saam, eerlikheid is alles.
Nou is Cloudflare 'n baie groot maatskappy, ek werk daarvoor, en nou moet ek openlik skryf oor ons fout, die gevolge daarvan en ons optrede.
Gebeure 2 Julie
Op 2 Julie het ons 'n nuwe reël in Bestuurde reëls vir WAF bekendgestel, as gevolg daarvan op elke verwerkerkern wat HTTP/HTTPS-verkeer op die Cloudflare-netwerk regoor die wêreld hanteer. Ons verbeter voortdurend die bestuurde reëls vir WAF in reaksie op nuwe kwesbaarhede en bedreigings. In Mei het ons byvoorbeeld gehaas om teen 'n ernstige kwesbaarheid in SharePoint te beskerm. Die hele essensie van ons WAF is die vermoë om reëls vinnig en wêreldwyd te ontplooi.
Ongelukkig het verlede Donderdag se opdatering 'n regeks bevat wat te veel van die SVE gebruik wat aan HTTP/HTTPS toegewys is vir terugspoor. Ons kern instaanbediener, CDN en WAF funksies het hierdeur gely. Die grafiek toon dat die SVE-hulpbronne vir die bediening van HTTP / HTTPS-verkeer byna 100% op die bedieners in ons netwerk bereik.
Verwerkerhulpbrongebruik by een van die teenwoordigheidspunte tydens 'n voorval
As gevolg hiervan het ons kliënte (en kliënte van ons kliënte) 'n 502-foutbladsy op Cloudflare-domeine getref. 502-foute is gegenereer deur Cloudflare se front-end-webbedieners, wat steeds gratis kerns gehad het, maar nie kon kommunikeer met prosesse wat HTTP/HTTPS-verkeer hanteer nie.
Ons weet hoeveel ongerief dit vir ons kliënte veroorsaak het. Ons is verskriklik skaam. En hierdie mislukking het ons verhinder om die voorval doeltreffend te hanteer.
As jy een van daardie kliënte was, moes jy bang, kwaad en gefrustreerd gewees het. Boonop het ons vir 6 jaar nie gehad nie . Die hoë SVE-gebruik was te wyte aan 'n enkele WAF-reël met 'n swak bewoorde gereelde uitdrukking wat tot oormatige terugsporing gelei het. Hier is die skuldige uitdrukking: (?:(?:"|'|]|}||d|(?:nan|infinity|true|false|null|undefined|symbol|math)|`|-|+)+[)]*;?((?:s|-|~|!|{}||||+)*.*(?:.*=.*)))
Alhoewel dit op sigself interessant is (en ek sal dit hieronder in meer besonderhede dek), was Cloudflare se 27-minute verduistering nie net te wyte aan 'n slegte gereelde uitdrukking nie. Dit het ons 'n rukkie geneem om die volgorde van gebeure wat tot die ongeluk gelei het te beskryf, so ons het nie vinnig gereageer nie. Aan die einde van die plasing sal ek terugsporing in 'n gewone uitdrukking beskryf en jou vertel wat om daarmee te doen.
Wat het gebeur
Kom ons begin in volgorde. Alle tye hier is in UTC.
Om 13:42 het 'n ingenieur van die brandmuurspan 'n klein verandering aan die reëls vir opsporing aangebring deur 'n outomatiese proses. Gevolglik is 'n veranderingsversoekkaartjie geskep. Ons bestuur sulke kaartjies deur Jira (skermkiekie hieronder).
Na 3 minute het die eerste bladsy van PagerDuty verskyn, wat 'n probleem met WAF gerapporteer het. Dit was 'n sintetiese maatstaf wat die funksionaliteit van WAF's (ons het honderde van hulle) buite Cloudflare toets om te kyk vir normale werking. Dit is onmiddellik gevolg deur bladsye van mislukkings van ander end-tot-end-toetse van Cloudflare-dienste, globale verkeerskwessies, wydverspreide 502-foute, en 'n klomp verslae van ons Points of Presence (PoP) in stede regoor die wêreld wat 'n tekort aangedui het. van verwerkerhulpbronne.
Ek het 'n paar van hierdie waarskuwings ontvang, uit die vergadering gestorm en was op pad na die tafel toe ons oplossingsontwikkelingsleier sê ons het 80% van ons verkeer verloor. Ek het na ons SRE-ingenieurs gehardloop wat reeds aan die probleem gewerk het. Ons het eers gedink dis een of ander onbekende aanval.
Cloudflare SRE-ingenieurs is oor die wêreld versprei en monitor die situasie 0 uur per dag. Tipies, hierdie waarskuwings gee kennis van spesifieke plaaslike probleme van 'n beperkte omvang, word nagespoor op interne dashboards, en word baie keer per dag opgelos. Maar sulke bladsye en kennisgewings het op iets werklik ernstig gewys, en SRE-ingenieurs het dadelik 'n ernsvlak van PXNUMX verklaar en hulle tot bestuurs- en stelselingenieurs gewend.
Ons Londense ingenieurs het op daardie oomblik na 'n lesing in die hoofsaal geluister. Die lesing moes onderbreek word, almal het in 'n groot konferensielokaal bymekaargekom, en nog spesialiste is ontbied. Dit was nie 'n algemene probleem wat SRE's op hul eie kon hanteer nie. Dit was nodig om die regte spesialiste dringend aan te sluit.
Om 14:00 het ons vasgestel dat daar 'n probleem met die WAF was en daar was geen aanval nie. Die prestasieafdeling het die verwerkerdata onttrek, en dit het duidelik geword dat WAF die skuld kry. Nog 'n werknemer het hierdie teorie met strace bevestig. Iemand anders het in die logs gesien daar is 'n probleem met WAF. Om 14:02 het die hele span na my gekom toe daar voorgestel is om globale dood te gebruik - 'n meganisme wat in Cloudflare ingebou is wat een komponent wêreldwyd deaktiveer.
Hoe ons 'n wêreldwye doodmaak vir WAF gedoen het, is 'n ander storie. Dit is nie so eenvoudig nie. Ons gebruik ons eie produkte, en sedert ons diens nie gewerk het nie, ons kon nie staaf en by die interne beheerpaneel aanmeld nie (toe alles reggestel is, het ons uitgevind dat sommige spanlede toegang verloor het as gevolg van 'n sekuriteitskenmerk wat geloofsbriewe deaktiveer as die interne beheerpaneel vir 'n lang tyd nie gebruik word nie) .
En ons kon nie by ons interne dienste soos Jira of die boustelsel uitkom nie. 'n Oplossing was nodig, wat ons selde gebruik het (dit sal ook uitgewerk moet word). Uiteindelik het een ingenieur daarin geslaag om die WAF om 14:07 af te sny, en om 14:09 het die verkeer en verwerkervlakke oral na normaal teruggekeer. Die res van Cloudflare se sekuriteitsmeganismes het soos normaal gewerk.
Toe het ons begin om die WAF te herstel. Die situasie was buitengewoon, so ons het negatiewe toetse (wat onsself gevra het of hierdie verandering werklik die probleem was) en positiewe toetse (om seker te maak dat die terugdraai werk) in een stad met aparte verkeer uitgevoer en betaalde kliënte daarvandaan oorgeplaas.
Om 14:52 het ons seker gemaak dat ons die oorsaak verstaan en 'n regstelling gemaak, en WAF weer aangeskakel.
Hoe Cloudflare werk
Cloudflare het 'n span ingenieurs wat toegewy is aan bestuurde reëls vir WAF. Hulle streef daarna om opsporingsyfers te verbeter, vals positiewe te verminder en vinnig op nuwe bedreigings te reageer soos hulle opduik. In die afgelope 60 dae is 476 WAF-bestuurde reëlveranderingsversoeke verwerk (gemiddeld een elke 3 uur).
Hierdie spesifieke verandering moes in simulasiemodus ontplooi word, waar werklike kliëntverkeer deur die reël gaan, maar niks word geblokkeer nie. Ons gebruik hierdie modus om die doeltreffendheid van reëls te toets en om die verhouding van vals positiewe en vals negatiewe te meet. Maar selfs in simulasiemodus moet die reëls eintlik uitgevoer word, en in hierdie geval het die reël 'n gereelde uitdrukking bevat wat te veel verwerkerhulpbronne verbruik het.
Soos u uit die veranderingsversoek hierbo kan sien, het ons 'n ontplooiingsplan, 'n terugrolplan en 'n skakel na 'n interne standaardbedryfsprosedure (SOP) vir hierdie tipe ontplooiing. Die SOP vir die wysiging van 'n reël laat dit toe om wêreldwyd gepubliseer te word. Trouens, in Cloudflare is alles heel anders gerangskik, en die SOP gee opdrag om eers die sagteware vir toetsing en interne gebruik by die interne punt van teenwoordigheid (PoP) (wat ons werknemers gebruik) in te dien, dan aan 'n klein aantal kliënte in 'n geïsoleerde plek, dan na 'n groot aantal kliënte, en eers dan regoor die wêreld.
Hier is hoe dit lyk. Ons gebruik git intern via BitBucket. Ingenieurs wat aan veranderinge werk, dien die kode wat gebou is by TeamCity in, en wanneer die bou slaag, word beoordelaars toegewys. Wanneer 'n trekversoek goedgekeur word, word die kode saamgestel en 'n reeks toetse word (weer) uitgevoer.
As die bou en toetse suksesvol voltooi word, word 'n veranderingsversoek in Jira geskep en die verandering moet deur die toepaslike bestuurder of leier goedgekeur word. Sodra dit goedgekeur is, ontplooi dit in die sogenaamde "PoP-menagerie": HOND, VARK, en (hond, vark en kanarie).
DOG PoP is Cloudflare PoP (net soos enige ander van ons stede) wat net Cloudflare-werknemers gebruik. PoP vir interne gebruik laat jou toe om probleme op te vang selfs voordat kliënteverkeer die oplossing begin betree. Nuttige ding.
As die HOND toets slaag, beweeg die kode na die VARK (proefkonyn) stadium. Dit is Cloudflare PoP, waar 'n klein hoeveelheid gratis kliëntverkeer deur die nuwe kode gaan.
As alles goed is, gaan die kode na Kanarie. Ons het drie Kanariese PoP's in verskillende dele van die wêreld. In hulle gaan die verkeer van betaalde en gratis kliënte deur die nuwe kode, en dit is die laaste kontrole vir foute.
Sagteware vrystelling proses in Cloudflare
As die kode in Kanarie reg is, stel ons dit vry. Om deur alle stadiums te gaan - HOND, VARK, Kanarie, die hele wêreld - neem 'n paar uur of dae, afhangend van die kodeverandering. As gevolg van die diversiteit van die Cloudflare-netwerk en kliënte, toets ons die kode deeglik voor 'n globale vrystelling vir alle kliënte. Maar die WAF volg spesifiek nie hierdie proses nie, want dreigemente moet vinnig hanteer word.
WAF-bedreigings
In die afgelope paar jaar was daar 'n aansienlike toename in bedreigings vir gereelde toepassings. Dit is as gevolg van die groter beskikbaarheid van sagteware-toetsinstrumente. Ons het byvoorbeeld onlangs geskryf oor ).
Bron:
Baie dikwels word 'n bewys van konsep geskep en onmiddellik op Github gepubliseer sodat die spanne wat die toepassing onderhou dit vinnig kan toets en seker maak dat dit voldoende beveilig is. Daarom moet Cloudflare so vinnig moontlik op nuwe aanvalle kan reageer sodat kliënte die geleentheid het om hul sagteware reg te stel.
'n Goeie voorbeeld van 'n vinnige reaksie van Cloudflare is die uitrol van beskerming teen 'n SharePoint-kwesbaarheid in Mei (). Byna onmiddellik nadat die aankondigings gepubliseer is, het ons 'n groot aantal pogings opgemerk om die kwesbaarheid in ons kliënte se SharePoint-installasies te ontgin. Ons ouens monitor voortdurend nuwe bedreigings en skryf reëls om ons kliënte te beskerm.
Die reël wat Donderdag die probleem veroorsaak het, was veronderstel om te beskerm teen cross-site scripting (XSS). Sulke aanvalle het ook die afgelope jare baie meer geword.
Bron:
Die standaardprosedure vir die wysiging van 'n WAF-bestuurde reël is om deurlopende integrasie (CI) te toets voor globale ontplooiing. Ons het dit verlede Donderdag gedoen en die reëls uitgerol. Om 13:31 het een ingenieur 'n goedgekeurde trekversoek met 'n verandering ingedien.
Om 13:37 het TeamCity die reëls ingesamel, die toetse afgelê en die trekpas gegee. Die WAF-toetsreeks toets die kernfunksionaliteit van die WAF en bestaan uit 'n groot aantal eenheidstoetse vir individuele funksies. Na eenheidstoetsing het ons die WAF-reëls getoets met 'n groot aantal HTTP-versoeke. HTTP-versoeke kyk watter versoeke deur WAF geblokkeer moet word (om die aanval te onderskep) en watter versoeke toegelaat moet word om te slaag (om nie alles in 'n ry te blokkeer en vals positiewe te vermy nie). Maar ons het nie toetse vir oormatige SVE-gebruik uitgevoer nie, en kyk na die logboeke van vorige WAF-boue wys dat die tyd om die toetse met die reël uit te voer nie vermeerder het nie, en dit is moeilik om te vermoed dat daar nie genoeg hulpbronne sal wees nie .
Die toetse het geslaag en TeamCity het die verandering outomaties om 13:42 begin ontplooi.
Quicksilver
WAF-reëls is ontwerp om bedreigings vinnig aan te spreek, en daarom ontplooi ons dit met behulp van Quicksilver se verspreide sleutel-waarde-winkel, wat veranderinge wêreldwyd in sekondes versprei. Al ons kliënte gebruik hierdie tegnologie wanneer hulle die konfigurasie op die paneelbord of deur die API verander, en dit is te danke daaraan dat ons blitsvinnig op veranderinge reageer.
Ons het nie veel oor Quicksilver gepraat nie. Voorheen het ons gebruik as 'n wêreldwyd verspreide sleutelwaardewinkel, maar dit het operasionele probleme ondervind en ons het ons eie winkel geskryf wat in meer as 180 stede herhaal is. Ons gebruik nou Quicksilver om konfigurasieveranderinge aan kliënte te stoot, WAF-reëls op te dateer en kliëntgeskrewe JavaScript aan Cloudflare Workers te versprei.
Van die klik van 'n knoppie op 'n dashboard of die oproep van 'n API tot 'n konfigurasieverandering regoor die wêreld, dit neem net 'n paar sekondes. Kliënte hou van hierdie spoed van opstelling. En Workers voorsien hulle van byna onmiddellike wêreldwye sagteware-ontplooiing. Quicksilver propageer gemiddeld ongeveer 350 veranderinge per sekonde.
En Quicksilver is baie vinnig. Ons het gemiddeld die 99ste persentiel van 2,29 sekondes bereik om veranderinge aan elke rekenaar regoor die wêreld te versprei. Gewoonlik is spoed goed. Na alles, wanneer jy 'n kenmerk aanskakel of die kas uitvee, gebeur dit byna onmiddellik en oral. Die stuur van kode deur Cloudflare Workers gebeur teen dieselfde spoed. Cloudflare belowe sy kliënte vinnige opdaterings op die regte tyd.
Maar in hierdie geval het die spoed 'n wrede truuk op ons gespeel, en die reëls het oral in 'n kwessie van sekondes verander. Jy het dalk opgemerk dat die WAF-kode Lua gebruik. Cloudflare gebruik Lua wyd in produksie en besonderhede ons . Lua WAF gebruik binne en pas terugsporing toe vir passing. Dit het geen meganismes om teen buite-beheer uitdrukkings te beskerm nie. Ek gaan hieronder in meer besonderhede hieroor en wat ons daaromtrent doen.
Voordat die reëls ontplooi is, het alles glad verloop: 'n trekversoek is geskep en goedgekeur, die CI/CD-pyplyn het die kode gebou en getoets, 'n veranderingsversoek is ingedien in ooreenstemming met die SOP wat ontplooiing en terugrol beheer, en die ontplooiing is voltooi .
Cloudflare WAF-ontplooiingsproses
Wat verkeerd geloop het
Soos ek voorheen gesê het, stel ons elke week tientalle nuwe WAF-reëls bekend, en ons het baie stelsels in plek om te beskerm teen die negatiewe gevolge van so 'n ontplooiing. En wanneer iets verkeerd loop, is dit gewoonlik 'n kombinasie van verskeie omstandighede op een slag. As jy net een rede vind, is dit natuurlik gerusstellend, maar nie altyd waar nie. Hier is die redes wat saam veroorsaak het dat ons HTTP/HTTPS-diens misluk het.
- 'n Ingenieur het 'n gereelde uitdrukking geskryf wat tot buitensporige kan lei .
- 'n Eienskap wat kon verhoed het dat die gewone uitdrukking SVE te veel gebruik, is verkeerdelik verwyder tydens die WAF-herfaktorering 'n paar weke vroeër - die herfaktorering was nodig om die WAF minder hulpbronne te laat verbruik.
- Die gereelde uitdrukking-enjin het geen waarborge van kompleksiteit gehad nie.
- Die toetssuite kon nie oormatige SVE-gebruik bespeur nie.
- Die SOP laat toe dat nie-dringende reëlveranderinge wêreldwyd ontplooi kan word sonder 'n multi-stap proses.
- Die terugrolplan het twee keer 'n volledige WAF-bou vereis, wat 'n lang tyd is.
- Die eerste wêreldwye verkeersprobleemwaarskuwing het te laat gekom.
- Ons was traag om die statusbladsy op te dateer.
- Ons het probleme gehad om toegang tot die stelsels te kry as gevolg van die mislukking en die omseilprosedure is nie goed geoefen nie.
- SRE's het toegang tot sommige stelsels verloor omdat hul geloofsbriewe om sekuriteitsredes verval het.
- Ons kliënte het nie toegang tot die Cloudflare Dashboard of API gehad nie omdat hulle deur die Cloudflare-streek gaan.
Wat het verander sedert verlede Donderdag
Eerstens het ons alle werk aan vrystellings vir WAF heeltemal gestaak en doen die volgende:
- Herinstelling van die beskerming teen oormatige verbruik van verwerkerhulpbronne, wat ons verwyder het. (Gereed)
- Kontroleer handmatig al 3868 reëls in WAF Managed Reels om ander potensiële gevalle van oormatige terugsporing te vind en reg te stel. (Verifikasie voltooi)
- Sluit prestasieprofiele vir alle reëls in die toetsreeks in. (Verwag: 19 Julie)
- Skakel oor na die gewone uitdrukking-enjin of Albei bied waarborge in die looptyd-omgewing. (Verwag: 31 Julie)
- Herskryf die SOP om reëls in fases te ontplooi, soos ander sagteware in Cloudflare, maar steeds in staat wees om nood wêreldwyd te ontplooi as aanvalle reeds begin het.
- Ons ontwikkel die vermoë om die Cloudflare-kontroleskerm en API dringend uit die Cloudflare-streek te onttrek.
- Outomatiseer bladsyverversing .
Op lang termyn beweeg ons weg van die Lua WAF wat ek 'n paar jaar gelede geskryf het. Beweeg WAF na . Dus sal WAF vinniger wees en 'n bykomende laag beskerming kry.
Gevolgtrekking
Hierdie mislukking het moeilikheid vir ons en ons kliënte veroorsaak. Ons het vinnig gereageer om die situasie reg te stel en werk tans aan die foute in die prosesse wat die ongeluk veroorsaak het, asook om selfs dieper te delf om te waak teen potensiële regex-kwessies in die toekoms deur na die nuwe tegnologie te migreer.
Ons is baie skaam oor hierdie mislukking en ons vra om verskoning aan ons kliënte. Hopelik verseker hierdie veranderinge dat dit nie weer gebeur nie.
Toepassing. Gereelde uitdrukking terugdring
Om te verstaan hoe die uitdrukking:
(?:(?:"|'|]|}||d
(?:nan|infinity|true|false|null|undefined|symbol|math)|`|-
|+)+[)]*;?((?:s|-|~|!|{}||||+)*.*(?:.*=.*)))al die SVE-hulpbronne geëet het, moet jy 'n bietjie weet oor hoe die standaard gereelde uitdrukking-enjin werk. Die probleem hier is in die patroon .*(?:.*=.*). (?: en ooreenstemmende ) is 'n nie-vangende groep (dit wil sê, die uitdrukking tussen hakies word as 'n enkele uitdrukking gegroepeer).
In die konteks van oormatige verbruik van verwerkerhulpbronne, kan hierdie patroon aangewys word as .*.*=.*. In hierdie vorm lyk die patroon onnodig kompleks. Maar nog belangriker, in die werklike wêreld kan sulke uitdrukkings (soos komplekse uitdrukkings in WAF-reëls) wat die enjin vra om 'n fragment te pas, gevolg deur 'n ander fragment, tot rampspoedige terugsporing lei. En dit is hoekom.
In 'n gereelde uitdrukking . beteken om een karakter te pas, .* - pas nul of meer karakters "gretig" by, dit wil sê, die maksimum aantal karakters vas te lê, sodat .*.*=.* beteken pas nul of meer karakters, pas dan nul of meer karakters, vind die letterlike karakter =, pas nul of meer karakters.
Kom ons neem 'n toetsstring x=x. Dit stem ooreen met die uitdrukking .*.*=.*. .*.* tot by die gelykheidsteken pas by die eerste x (een van die groepe .* соответствует x, en die tweede - tot nul karakters). .* na = wedstryde laaste x.
Vir so 'n vergelyking is 23 stappe nodig. Eerste groep .* в .*.*=.* tree gulsig op en pas by die hele snaar x=x. Die enjin beweeg na die volgende groep .*. Ons het nie meer karakters om te pas nie, so die tweede groep .* pas by nul karakters (dit word toegelaat). Dan gaan die enjin na die bord =. Daar is nie meer simbole nie (die eerste groep .* die hele uitdrukking gebruik x=x), vind geen passing plaas nie.
En hier keer die gewone uitdrukking-enjin terug na die begin. Hy gaan na die eerste groep .* en vergelyk dit с x= (in plaas van x=x), en neem dan die tweede groep aan .*. Tweede groep .* in vergelyking met die tweede x, en ons het weer geen karakters oor nie. En wanneer die enjin weer bereik = в .*.*=.*, niks werk nie. En hy trek weer terug.
Hierdie keer die groep .* steeds ooreenstem x=, maar die tweede groep .* niks meer nie x, en nul karakters. Die enjin probeer 'n letterlike karakter vind = in 'n patroon .*.*=.*, maar kom nie uit nie (omdat dit reeds deur die eerste groep geneem is .*). En hy trek weer terug.
Hierdie keer die eerste groep .* neem net die eerste x. Maar die tweede groep .* "gierig" vang =x. Het jy al geraai wat gaan gebeur? Die enjin probeer om 'n letterlike te pas =, misluk en maak nog 'n terugsporing.
Eerste groep .* pas steeds by die eerste x... Die tweede .* neem net =. Natuurlik kan die enjin nie by 'n letterlike pas nie =want die tweede groep het dit reeds gedoen .*. En weer terugtrek. En ons probeer om 'n string van drie karakters te pas!
As gevolg hiervan, die eerste groep .* pas net by die eerste x, tweede .* - met nul karakters, en die enjin pas uiteindelik by die letterlike = in uitdrukking с = in lyn. Toe die laaste groep .* in vergelyking met die laaste x.
Slegs 23 stappe vir x=x. Kyk na 'n kort video oor die gebruik van Perl , wat wys hoe die stappe en terugsporing gebeur.
Dit is reeds baie werk, maar wat as in plaas van x=x ons sal hê x=xx? Dit is 33 treë. En as x=xxx? 45. Afhanklikheid is nie lineêr nie. Die grafiek toon 'n vergelyking van x=x aan x=xxxxxxxxxxxxxxxxxxxx (20 x na =). As ons 20 x na het =, die enjin doen die passing in 555 stappe! (Bowendien, as ons verloor het x= en die tou bestaan net uit 20 x, sal die enjin 4067 stappe neem om te besef daar is geen vuurhoutjies nie).
Hierdie video wys alle terugsporing vir vergelyking x=xxxxxxxxxxxxxxxxxxxx:
Die probleem is dat namate die tougrootte toeneem, die pastyd superlineêr groei. Maar dinge kan selfs erger word as die gereelde uitdrukking effens gewysig word. Kom ons sê ons het .*.*=.*; (dit wil sê, daar was 'n letterlike kommapunt aan die einde van die patroon). Byvoorbeeld, om te pas by 'n uitdrukking soos foo=bar;.
En hier sou terugspoor 'n ware ramp wees. Ter vergelyking x=x dit sal 90 treë neem, nie 23 nie. En hierdie getal groei vinnig. Te pas x= en 20 x, jy benodig 5353 stappe. Hier is die grafiek. Kyk na die waardes langs die as Y in vergelyking met die vorige grafiek.
As jy belangstel, sien al 5353 mislukte passingstappe x=xxxxxxxxxxxxxxxxxxxx и .*.*=.*;
Deur "lui" eerder as "gierige" passing te gebruik, kan die hoeveelheid terugsporing beheer word. As ons die oorspronklike uitdrukking verander na .*?.*?=.*?, vir bypassende x=x dit sal 11 treë neem (nie 23 nie). Wat betref x=xxxxxxxxxxxxxxxxxxxx... Alles omdat ? na .* vertel die enjin om by die minimum aantal karakters te pas voordat hy verder gaan.
Maar lui passing los nie die terugspoorprobleem heeltemal op nie. As ons die katastrofiese voorbeeld vervang .*.*=.*; op .*?.*?=.*?;, sal die uitvoeringstyd dieselfde bly. x=x vereis steeds 555 stappe, en x= en 20 x - 5353.
Die enigste ding wat gedoen kan word (behalwe om die patroon heeltemal te herskryf vir meer spesifisiteit) is om die gewone uitdrukking-enjin met sy terugspoormeganisme te laat vaar. Dit is wat ons in die volgende paar weke gaan doen.
Die oplossing vir hierdie probleem is bekend sedert 1968, toe Kent Thompson 'n artikel geskryf het ("Programmeringsmetodes: Regular Expression Search Algoritm"). Die artikel beskryf 'n meganisme wat jou toelaat om 'n gereelde uitdrukking in nie-deterministiese eindige outomate om te skakel, en na toestandsveranderinge in nie-deterministiese eindige outomate, gebruik 'n algoritme waarvan die uitvoeringstyd lineêr afhang van die ooreenstemmende string.
Programmering Metodes
Gereelde uitdrukking soek algoritme
Ken Thompson
Bell Telephone Laboratories, Inc., Murray Hill, NJDit beskryf 'n metode om na 'n spesifieke string karakters in teks te soek, en bespreek die implementering van hierdie metode in samestellervorm. Die samesteller neem die gereelde uitdrukking as bronkode en genereer die IBM 7094-program as objekkode. Die objekprogram neem insette in die vorm van soekteks en stuur 'n sein elke keer as 'n string teks by die gegewe gereelde uitdrukking pas. Die artikel verskaf voorbeelde, probleme en oplossings.
Algoritme
Vorige soekalgoritmes het gelei tot terugsporing as 'n gedeeltelik suksesvolle soektog misluk het.In samestellingsmodus werk die algoritme nie met simbole nie. Dit gee instruksies aan die saamgestelde kode deur. Die uitvoering is baie vinnig - nadat die data na die bokant van die huidige lys deurgegee is, soek dit outomaties na alle moontlike opeenvolgende karakters in die gewone uitdrukking.
Die samestelling en soekalgoritme is ingesluit in die tyddeel teksredigeerder as 'n kontekstuele soektog. Dit is natuurlik ver van die enigste toepassing van so 'n soekprosedure. Byvoorbeeld, 'n variant van hierdie algoritme word gebruik as 'n simboolopsoek in 'n tabel in assembler.
Daar word aanvaar dat die leser vertroud is met gereelde uitdrukkings en die programmeertaal van die IBM 7094-rekenaar.Samesteller
Die samesteller bestaan uit drie parallelle stadiums. Die eerste stap is sintaksisfiltrering, wat slegs sintakties korrekte gereelde uitdrukkings toelaat om deur te gaan. Hierdie stap voeg ook die "·" operateur in om gereelde uitdrukkings te pas. In die tweede stap word die gereelde uitdrukking omgeskakel na postfix-vorm. In die derde stadium word die objekkode geskep. Die eerste 2 stadiums is voor die hand liggend, en ons sal nie daaroor stilstaan nie.
Thompson se artikel praat nie oor nie-deterministiese eindige outomata nie, maar dit doen 'n goeie werk om die lineêre tydalgoritme te verduidelik en 'n ALGOL-60-program aan te bied wat samestellingstaalkode vir die IBM 7094 genereer. Die implementering is moeilik, maar die idee is baie eenvoudig.
huidige soekpad. Dit word voorgestel deur ⊕ met een inset en twee uitsette.
Figuur 1 toon die funksies van die derde samestellingstap wanneer die gewone uitdrukking voorbeeld omgeskakel word. Die eerste drie karakters in die voorbeeld is a, b, c, en elkeen skep 'n S[i]-stapel-inskrywing en 'n NNODE-veld.NNODE na bestaande kode om die finale gereelde uitdrukking in 'n enkele stapelinskrywing te genereer (sien Figuur 5)
Dit is hoe die gewone uitdrukking sou lyk .*.*=.*, as jy jou voorstel, soos in die foto's van Thompson se artikel.
Op fig. 0 is daar vyf toestande wat by 0 en 3 siklusse begin wat by toestande 1, 2 en 3 begin. Hierdie drie siklusse stem ooreen met die drie .* in 'n gereelde uitdrukking. 3 ovale met kolletjies stem ooreen met een karakter. Ovaal met teken = pas by 'n letterlike karakter =. Staat 4 is finaal. As ons dit bereik het, dan is die gewone uitdrukking ooreenstem.
Om te sien hoe so 'n toestanddiagram gebruik kan word om 'n reëlmatige uitdrukking te pas .*.*=.*, sal ons stringpassing oorweeg x=x. Die program begin vanaf toestand 0, soos in Fig. 1.
Vir hierdie algoritme om te werk, moet die eindmasjien op dieselfde tyd in verskeie toestande wees. 'n Nie-deterministiese staatsmasjien sal alle moontlike oorgange op dieselfde tyd maak.
Voordat dit tyd het om die invoerdata te lees, gaan dit na beide eerste toestande (1 en 2), soos in Fig. 2.
Op fig. 2 kyk wat gebeur as hy die eerste oorweeg x в x=x. x kan by die hoogtepunt pas deur van toestand 1 en terug na toestand 1 te gaan. Of x kan na die punt hieronder karteer deur van toestand 2 en terug na toestand 2 te gaan.
Nadat die eerste pas x в x=x ons is steeds in toestande 1 en 2. Ons kan nie toestand 3 of 4 bereik nie, want ons het 'n letterlike karakter nodig =.
Die algoritme oorweeg dan = в x=x. Soos x voorheen, kan dit met enige van die top twee siklusse van toestand 1 tot toestand 1 of van toestand 2 na toestand 2 ooreenstem, maar die algoritme kan steeds 'n letterlike = en gaan van toestand 2 na toestand 3 (en dadelik 4). Dit word in fig. 3.
Die algoritme beweeg dan aan na die laaste x в x=x. Vanaf toestande 1 en 2 is dieselfde oorgange moontlik terug na toestande 1 en 2. Vanaf toestand 3 x kan by die punt aan die regterkant pas en teruggaan na toestand 3.
Op hierdie stadium, elke karakter x=x oorweeg, en aangesien ons toestand 4 bereik het, pas die gereelde uitdrukking by hierdie string. Elke karakter word een keer verwerk, so hierdie algoritme hang lineêr af van die lengte van die invoerstring. En geen terugtrekking nie.
Na die bereiking van toestand 4 (wanneer die algoritme ooreenstem x=) die hele gereelde uitdrukking is ooreenstem, en die algoritme kan beëindig sonder om enigsins te oorweeg x.
Hierdie algoritme hang lineêr af van die grootte van die invoerstring.
Bron: will.com