Hast 9 jier lyn wie Cloudflare in lyts bedriuw, en ik wurke der net foar, ik wie gewoan in klant. In moanne nei it lansearjen fan Cloudflare, krige ik in notifikaasje dat myn webside DNS liket net te wurkjen. Cloudflare hat in feroaring makke oan , en der wie in brutsen DNS.
Ik skreau fuortendaliks oan Matthew Prince mei de titel "Wêr is myn DNS?" en hy stjoerde in lang antwurd fol technyske details (), wêrop ik antwurde:
Fan: John Graham-Cumming
datum: 7. Oktober 2010, 9:14
Underwerp: Re: Wêr is myn DNS?
Oan: Matthew PrinsCool rapport, tank. Ik sil grif belje as der problemen binne. It is wierskynlik de muoite wurdich om hjir in post oer te skriuwen as jo alle technyske ynformaasje sammele hawwe. Ik tink dat minsken genietsje fan in iepen en earlik ferhaal. Benammen as jo der grafiken oan heakje om sjen te litten hoe't ferkear sûnt lansearring groeid is.
Ik haw goede tafersjoch op myn side, en ik krij in SMS oer elke mislearring. Tafersjoch lit sjen dat de mislearring barde fan 13:03:07 oant 14:04:12. Tests wurde elke fiif minuten útfierd.
Ik bin der wis fan dat jo it útfine. Binne jo wis dat jo net nedich jo eigen persoan yn Europa? 🙂
En hy antwurde:
Fan: Matthew Prins
datum: 7. Oktober 2010, 9:57
Underwerp: Re: Wêr is myn DNS?
Oan: John Graham-CummingDankewol. Wy reagearren op elkenien dy't skreau. Ik bin no ûnderweis nei it kantoar en wy sille wat op it blog skriuwe of in offisjele post op ús bulletin board pinne. Ik bin it folslein iens, earlikens is alles.
No is Cloudflare in echt grut bedriuw, ik wurkje der foar, en no moat ik iepen skriuwe oer ús flater, de gefolgen en ús dieden.
Eveneminten fan 2 july
Op 2 july rôle wy in nije regel út yn Managed Rules foar WAF's fanwegen hokker op elke prosessorkearn dy't HTTP / HTTPS-ferkear ferwurket op it Cloudflare-netwurk wrâldwiid. Wy ferbetterje konstant behearde regels foar WAF's yn reaksje op nije kwetsberens en bedrigingen. Yn maaie ha wy bygelyks hastich west om te beskermjen tsjin in serieuze kwetsberens yn SharePoint. It heule punt fan ús WAF is de mooglikheid om regels fluch en wrâldwiid yn te setten.
Spitigernôch befette de fernijing fan ôfrûne tongersdei in reguliere útdrukking dy't tefolle HTTP/HTTPS CPU-boarnen fergrieme oan backtracking. Us kearnproxy-, CDN- en WAF-funksjes lijen dêrtroch. De grafyk lit sjen dat prosessorboarnen foar it tsjinjen fan HTTP/HTTPS-ferkear hast 100% berikke op servers yn ús netwurk.
CPU-gebrûk op ien punt fan oanwêzigens tidens in ynsidint
As gefolch hawwe ús kliïnten (en kliïnten fan ús kliïnten) in 502-flaterpagina yn Cloudflare-domeinen einige. 502 flaters waarden oanmakke troch Cloudflare front-end webservers dy't noch frije kearnen hiene, mar net yn steat wiene om te kommunisearjen mei prosessen dy't HTTP / HTTPS-ferkear behannelje.
Wy witte hoefolle oerlêst dit ús klanten hat feroarsake. Wy skamje ús ferskriklik. En dit mislearjen ferhindere ús om it ynsidint effektyf te behanneljen.
As jo ien fan dizze klanten wiene, wiene jo wierskynlik bang, lilk en oerstjoer. Boppedat, wy hawwe net hie in . De hege CPU-konsumpsje wie te tankjen oan ien WAF-regel mei in min formulearre reguliere ekspresje dy't resultearre yn oermjittige backtracking. Hjir is de skuldige útdrukking: (?:(?:"|'|]|}||d|(?:nan|infinity|true|false|null|undefined|symbol|math)|`|-|+)+[)]*;?((?:s|-|~|!|{}||||+)*.*(?:.*=.*)))
Hoewol dit op himsels ynteressant is (en ik sil it hjirûnder yn mear detail prate), wie de Cloudflare-tsjinst 27 minuten del, net allinich fanwegen in minne reguliere útdrukking. It hat ús in skoft duorre om de folchoarder fan barrens te beskriuwen dy't liede ta it mislearjen, dus wy wiene traach om te reagearjen. Oan 'e ein fan' e post sil ik backtracking beskriuwe yn in reguliere útdrukking en jo fertelle wat jo dermei moatte dwaan.
Wat is bard
Litte wy yn oarder begjinne. Alle tiden hjir binne yn UTC.
Om 13:42 oere makke in yngenieur fan it firewallteam in lytse feroaring oan 'e deteksjeregels mei help fan in automatysk proses. Dêrtroch is in feroaring fersyk ticket makke. Wy beheare sokke kaartsjes fia Jira (skermôfbylding hjirûnder).
Nei 3 minuten ferskynde de earste side fan PagerDuty, rapportearret in probleem mei WAF. Dit wie in syntetyske test dy't de funksjonaliteit fan WAF's testet (wy hawwe hûnderten fan har) bûten Cloudflare om normale wurking te kontrolearjen. Dit waard fuortendaliks folge troch siden mei warskôgings oer oare Cloudflare end-to-end tsjinsttests dy't mislearre, globale ferkearsproblemen, wiidferspraat 502 flaters, en in ton rapporten fan ús Points of Presence (PoP) yn stêden om 'e wrâld dy't oanjûn op in gebrek fan CPU boarnen.
Ik krige ferskate fan dizze warskôgings, stoarmde út in gearkomste, en wie ûnderweis nei de tafel doe't it haad fan ús ôfdieling oplossingsûntwikkeling sei dat wy 80% fan ús ferkear ferlern hiene. Ik rûn nei ús SRE-yngenieurs, dy't al oan it probleem wurken. Earst tochten wy dat it in soarte fan ûnbekende oanfal wie.
Cloudflare SRE-yngenieurs binne ferspraat oer de wrâld en kontrolearje de situaasje rûn de klok. Typysk, dizze warskôgings ynformearje jo fan spesifike lokale problemen fan beheinde omfang, wurde folge op ynterne dashboards, en wurde oplost meardere kearen deis. Mar dizze siden en notifikaasjes oanjûn wat echt serieus, en SRE yngenieurs fuortendaliks ferklearre de earnst nivo P0 en kontakt behear en systeem yngenieurs.
Us Londenske yngenieurs hearden op dat stuit nei in lêzing yn de grutte seal. De lêzing moast ûnderbrutsen wurde, elkenien sammele yn in grutte konferinsjeromte, en mear spesjalisten waarden oproppen. Dit wie net in typysk probleem dat SRE's sels mei kinne omgean. It wie driuwend om de goede spesjalisten yn te skeakeljen.
Om 14 oere hawwe wy bepaald dat it probleem by de WAF wie en dat der gjin oanfal wie. It prestaasjesteam luts de CPU-gegevens en it waard dúdlik dat de WAF de skuld wie. In oare meiwurker befêstige dizze teory mei strace. In oar seach yn de logs dat der in probleem wie mei WAF. Om 00:14 kaam it hiele team nei my doe't it waard foarsteld om globale kill te brûken, in meganisme ynboud yn Cloudflare dat ien komponint wrâldwiid ôfslút.
Hoe't wy wrâldwide kill hawwe dien foar WAF is in oar ferhaal. It is net sa ienfâldich. Wy brûke ús eigen produkten, en sûnt ús tsjinst wurke net, wy koenen net authentisearje en ynlogge op it ynterne kontrôlepaniel (doe't alles fêst wie, learden wy dat guon teamleden tagong ferlern hienen fanwegen in befeiligingsfunksje dy't bewiisbrieven útskeakele as it ynterne kontrôlepaniel net brûkt wurdt foar in lange tiid).
En wy koenen net by ús ynterne tsjinsten komme, lykas Jira of it bousysteem. Wy hiene in oplossingsmeganisme nedich, dy't wy selden brûkten (dit sil ek útwurke wurde moatte). Uteinlik slagge ien yngenieur om de WAF om 14:07 út te skeakeljen, en om 14:09 wiene ferkears- en CPU-nivo's oeral werom nei normaal. De rest fan Cloudflare's beskermingsmeganismen wurken as normaal.
Dêrnei sette wy oer it werstellen fan de WAF. De situaasje wie út 'e gewoane, dat wy hawwe negative tests útfierd (freegje ússels as de feroaring echt it probleem wie) en positive tests (wês wis dat it weromdraaien wurke) yn ien stêd mei apart ferkear, en dêrwei beteljende klanten oerdrage.
Om 14:52 wiene wy derfan oertsjûge dat wy de reden begrepen en in korreksje makken, en WAF wer ynskeakele.
Hoe Cloudflare wurket
Cloudflare hat in team fan yngenieurs wijd oan it behearen fan regels foar WAF's. Se stribje dernei om deteksjesifers te ferbetterjen, falske positiven te ferminderjen, en reagearje fluch op nije bedrigingen as se opkomme. Yn 'e lêste 60 dagen binne d'r 476 feroaringsoanfragen ferwurke foar beheare regels foar WAF (gemiddeld ien elke 3 oeren).
Dizze bysûndere feroaring moast wurde ynset yn simulaasjemodus, wêr't echte kliïntferkear troch de regel giet, mar neat is blokkearre. Wy brûke dizze modus om de effektiviteit fan 'e regels te testen en de falske positive en falske negative tariven te mjitten. Mar sels yn simulaasje modus, de regels moatte eins wurde útfierd, en yn dit gefal de regel befette in reguliere útdrukking dat wie consuming tefolle prosessor middels.
Sa't jo sjen kinne út it feroaring fersyk hjirboppe, wy hawwe in ynset plan, in rollback plan, en in keppeling nei in ynterne standert bestjoeringssysteem proseduere (SOP) foar dit soarte fan ynset. De SOP foar it feroarjen fan in regel lit it wrâldwiid publisearre wurde. Eigentlik wurde dingen by Cloudflare folslein oars dien, en de SOP diktearret dat wy de software foar testen en ynterne gebrûk earst ferstjoere nei in ynterne punt fan oanwêzigens (PoP) (dy't ús meiwurkers brûke), dan nei in lyts oantal kliïnten yn in isolearre lokaasje, dan nei in grut tal kliïnten, en pas dan nei de hiele wrâld.
Dit is wat it liket. Wy brûke git yntern fia BitBucket. Yngenieurs dy't wurkje oan feroarings jouwe koade yn, dy't boud is oan TeamCity, en as de bou trochgiet, wurde resinsinten tawiisd. Sadree't in pull fersyk is goedkard, de koade is gearstald en in rige fan tests wurde útfierd (wer).
As de bou en tests mei súkses foltôgje, wurdt in wizigingsfersyk makke yn Jira en moat de passende manager of lead de wiziging goedkarre. Nei goedkarring wurdt ynset yn de saneamde "PoP-menagerie": HOND, PIG en (hûn, pig en kanarie).
DOG PoP is in Cloudflare PoP (lykas elke oare fan ús stêden) dy't allinich brûkt wurdt troch Cloudflare-meiwurkers. PoP foar ynterne gebrûk lit jo problemen fange foardat klantferkear yn 'e oplossing begjint te streamen. Nuttich ding.
As de DOG-test suksesfol is, ferpleatst de koade nei it PIG-poadium (cavia). Dit is Cloudflare PoP, wêr't in lyts bedrach fan fergees klantferkear troch nije koade streamt.
As alles goed is, giet de koade yn Kanaryske. Wy hawwe trije Kanaryske PoP's yn ferskate dielen fan 'e wrâld. Yn harren giet it ferkear fan betelle en fergese kliïnten troch de nije koade, en dit is de lêste kontrôle foar flaters.
Software Release Proses by Cloudflare
As de koade is ok yn Kanaryske, wy loslitte it. Troch alle stadia te gean - HUND, PIG, Kanaryske, de hiele wrâld - duorret ferskate oeren as dagen, ôfhinklik fan 'e koadeferoaring. Fanwegen it ferskaat fan Cloudflare's netwurk en kliïnten, testen wy koade yngeand foardat wy it wrâldwiid frijjaan oan alle kliïnten. Mar WAF folget dit proses net spesifyk om't bedrigingen fluch moatte wurde reagearre.
WAF bedrigings
Yn 'e ôfrûne jierren is d'r in signifikante taname west fan bedrigingen yn mienskiplike applikaasjes. Dit komt troch de gruttere beskikberens fan ark foar softwaretesten. Bygelyks, wy hawwe koartlyn skreaun oer ).
Boarne:
Hiel faak wurdt in proof of concept makke en fuortendaliks publisearre op Github, sadat de teams dy't de applikaasje ûnderhâlde, it fluch kinne testen en soargje dat it adekwaat befeilige is. Dêrom hat Cloudflare de mooglikheid nedich om sa gau mooglik te reagearjen op nije oanfallen, sadat klanten de kâns hawwe om har software te reparearjen.
In geweldich foarbyld fan Cloudflare's rappe reaksje is de ynset fan SharePoint kwetsberensbeskerming yn maaie (). Hast fuort nei't de oankundigingen waarden makke, hawwe wy in enoarm oantal besykjen opmurken om de kwetsberens te brûken yn 'e SharePoint-ynstallaasjes fan ús klanten. Us jonges kontrolearje konstant nije bedrigingen en skriuwe regels om ús klanten te beskermjen.
De regel dy't it probleem op tongersdei feroarsake, soe beskermje tsjin cross-site scripting (XSS). Sokke oanfallen binne de lêste jierren ek folle faker wurden.
Boarne:
De standertproseduere foar it feroarjen fan in behearde regel foar in WAF is it testen fan kontinuinte yntegraasje (CI) foardat wrâldwide ynset. Ofrûne tongersdei ha wy dit dien en de regels útrôle. Om 13:31 die in yngenieur in goedkard pull fersyk mei in feroaring yn.
Om 13 oere sammele TeamCity de regels, rûn tests en joech it startsein. De WAF-testsuite testet de kearnfunksjonaliteit fan 'e WAF en bestiet út in grut oantal ienheidstests foar yndividuele funksjes. Nei ienheidstests testen wy de regels foar de WAF mei in enoarm oantal HTTP-oanfragen. HTTP-oanfragen kontrolearje hokker fersiken troch de WAF blokkearre wurde moatte (om de oanfal te ûnderskepen) en hokker kinne wurde tastien (om net alles te blokkearjen en falske positiven te foarkommen). Mar wy hawwe net testen foar oermjittich CPU-gebrûk, en ûndersiikjen fan de logs fan eardere WAF-builds lit sjen dat de útfieringstiid fan 'e regeltest net tanommen, en it wie dreech om te fermoedzjen dat d'r net genôch boarnen wêze soe.
De tests passe en TeamCity begon de feroaring automatysk yn te setten om 13:42 oere.
Quicksilver
WAF-regels rjochtsje har op direkte bedrigingssanearring, sadat wy se ynsette mei help fan Quicksilver's ferspraat kaai-wearde-winkel, dy't feroaringen wrâldwiid yn sekonden propagearret. Al ús kliïnten brûke dizze technology as se feroarje de konfiguraasje yn it dashboard of fia de API, en it is tank oan it dat wy reagearje op feroarings mei bliksem snelheid.
Wy hawwe net folle praat oer Quicksilver. Earder brûkten wy as in globaal ferspraat kaai-wearde winkel, mar der wiene operasjonele problemen mei it, en wy skreau ús eigen winkel, replicated yn mear as 180 stêden. Wy brûke no Quicksilver om konfiguraasjewizigingen nei kliïnten te triuwen, WAF-regels te aktualisearjen en JavaScript-koade te fersprieden skreaun troch kliïnten nei Cloudflare Workers.
It duorret mar in pear sekonden fan it klikken op in knop op in dashboard of it oproppen fan in API oant it meitsjen fan in konfiguraasjewiziging wrâldwiid. Klanten hâlde fan dizze snelheid fan opset. En Workers jout har hast instantaneous wrâldwide software-ynset. Gemiddeld propagearret Quicksilver sa'n 350 feroarings per sekonde.
En Quicksilver is hiel fluch. Yn trochsneed hawwe wy it 99e percentile fan 2,29 sekonden berikt om wizigingen te propagearjen oan elke kompjûter wrâldwiid. Snelheid is normaal in goede saak. As jo in funksje ynskeakelje of it cache wiskje, bart it ommers hast direkt en oeral. It ferstjoeren fan koade fia Cloudflare Workers bart op deselde snelheid. Cloudflare belooft har klanten rappe updates op it krekte momint.
Mar yn dit gefal, snelheid spile in wrede grap op ús, en de regels feroare oeral yn in kwestje fan sekonden. Jo hawwe miskien opfallen dat de WAF-koade Lua brûkt. Cloudflare brûkt Lua wiidweidich yn produksje en details мы . Lua WAF brûkt yntern en jildt backtracking foar matching. It hat gjin meganismen om te beskermjen tsjin útdrukkingen dy't út 'e kontrôle komme. Hjirûnder sil ik hjir mear oer prate en wat wy der oan dogge.
Foardat de regels waarden ynset, gie alles soepel: it pull-fersyk waard oanmakke en goedkard, de CI / CD-pipeline sammele en hifke de koade, it wizigingsfersyk waard yntsjinne neffens de SOP dy't de ynset en weromdraaien regelet, en de ynset waard foltôge.
Cloudflare WAF-ynsetproses
Der is wat misgien
Lykas ik sei, sette wy elke wike tsientallen nije WAF-regels yn, en wy hawwe in protte systemen yn plak om te beskermjen tsjin de negative gefolgen fan sa'n ynset. En as der wat mis giet, is it meastentiids in kombinaasje fan ferskate omstannichheden. As jo mar ien reden fine, is dit fansels gerêststellend, mar it is net altyd wier. Dit binne de redenen dy't tegearre liede ta it mislearjen fan ús HTTP/HTTPS-tsjinst.
- In yngenieur skreau in reguliere útdrukking dy't kin resultearje yn oermjittich .
- In funksje dy't koe hawwe foarkommen dat de reguliere ekspresje tefolle CPU fergrieme, waard fersin ferwidere yn in refactoring fan 'e WAF ferskate wiken earder - de refactoring wie nedich om de WAF minder boarnen te konsumearjen.
- De reguliere ekspresjemotor hie gjin kompleksiteitsgarânsjes.
- De testsuite koe oermjittich CPU-konsumpsje net detectearje.
- De SOP lit net-urgente regelwizigingen wrâldwiid útrol wurde sûnder in proses mei meardere stappen.
- It weromrolplan easke twa kear in folsleine WAF-build út te fieren, wat in lange tiid duorre.
- De earste warskôging oer wrâldwide ferkearsproblemen waard te let trigger.
- Wy hawwe in skoft duorre om de statusside te aktualisearjen.
- Wy hiene problemen mei tagong ta systemen troch in glitch, en de bypassproseduere wie net goed fêststeld.
- SRE-yngenieurs ferlearen tagong ta guon systemen om't har bewiisbrieven ferrûn binne fanwege feiligensredenen.
- Us klanten hiene gjin tagong ta it Cloudflare-dashboard of API, om't se troch in Cloudflare-regio gean.
Wat is der sûnt ôfrûne tongersdei feroare
Earst hawwe wy alle wurk oan releases foar WAF folslein stoppe en dogge it folgjende:
- Wy yntrodusearje de CPU-oerbrûkbeskerming dy't wy hawwe fuortsmiten opnij. (Klear)
- Alle 3868 regels yn 'e behearde regels manuell kontrolearje foar de WAF om oare mooglike gefallen fan oermjittige efterfolging te finen en te korrigearjen. (ferifikaasje foltôge)
- Wy befetsje prestaasjesprofilearring foar alle regels yn 'e testset. (ferwacht: 19 july)
- Oerskeakelje nei in reguliere ekspresjemotor of - beide jouwe runtime garânsjes. (ferwachte: 31 july)
- Wy skriuwe de SOP om regels yn stadia te setten, lykas oare software yn Cloudflare, mar hawwe tagelyk de mooglikheid om driuwend wrâldwiid yn te setten as oanfallen al begon binne.
- Wy ûntwikkelje de mooglikheid om it Cloudflare-dashboard en API driuwend te ferwiderjen út 'e Cloudflare-regio.
- Automatisearje side updates .
Lange termyn geane wy fuort fan 'e Lua WAF dy't ik in pear jier lyn skreau. WAF ferpleatse nei . Op dizze manier sil de WAF rapper wêze en in ekstra beskermingsnivo krije.
konklúzje
Dit mislearjen feroarsake problemen foar ús en ús klanten. Wy diene fluch om de situaasje te korrigearjen en wurkje no oan 'e gebreken yn' e prosessen dy't de crash feroarsake hawwe, en ek grave noch djipper om te beskermjen tsjin potensjele problemen mei reguliere útdrukkingen yn 'e takomst by it migrearjen nei nije technology.
Wy binne tige ferlegen oer dizze ûnderbrekking en ferûntskuldigje ús klanten. Wy hoopje dat dizze feroarings derfoar soargje dat soksawat net wer bart.
Oanfraach. Backtracking reguliere útdrukkingen
Om te begripen hoe't de útdrukking:
(?:(?:"|'|]|}||d
(?:nan|infinity|true|false|null|undefined|symbol|math)|`|-
|+)+[)]*;?((?:s|-|~|!|{}||||+)*.*(?:.*=.*)))iet alle CPU-boarnen op, jo moatte in bytsje witte oer hoe't de standert reguliere ekspresjemotor wurket. It probleem hjir is it patroan .*(?:.*=.*). (?: en oerienkommende ) is in net-fangende groep (dat is, de útdrukking tusken heakjes wurdt groepearre as ien útdrukking).
Yn 'e kontekst fan oermjittich CPU-konsumpsje kin dit patroan wurde omskreaun as .*.*=.*. Yn dizze foarm sjocht it patroan unnedich kompleks. Mar noch wichtiger, yn 'e echte wrâld kinne útdrukkingen (lykas komplekse útdrukkingen yn WAF-regels) dy't de motor freegje om oerien te kommen mei in fragmint folge troch in oar fragmint kinne liede ta katastrophale backtracking. En dêrom.
Yn reguliere ekspresje . betsjut dat jo ien karakter moatte oerienkomme, .* - oerienkomme mei nul of mear karakters "greedlik", dat is, in maksimum fan karakters fêstlizze, sadat .*.*=.* betsjut oerien mei nul of mear tekens, dan oerien mei nul of mear tekens, fine de letterlike = karakter, oerien mei nul of mear tekens.
Litte wy de testline nimme x=x. It komt oerien mei de útdrukking .*.*=.*. .*.* foardat it lykweardich teken oerienkomt mei de earste x (ien fan de groepen .* соответствует x, en de twadde - nul karakters). .* na = wedstriden lêste x.
Dizze ferliking fereasket 23 stappen. Earste groep .* в .*.*=.* hannelet gierig en komt oerien mei de hiele snaar x=x. De motor ferhuzet nei de folgjende groep .*. Wy hawwe gjin karakters mear om te passen, dus de twadde groep .* komt oerien mei nul karakters (dit is tastien). Dan giet de motor nei it teken =. D'r binne gjin symboalen mear (earste groep .* brûkte de hiele útdrukking x=x), gjin fergeliking komt foar.
En dan komt de reguliere ekspresjemotor werom nei it begjin. Hy giet troch nei de earste groep .* en fergeliket it с x= (ynstee fan x=x), en nimt dan de twadde groep oan .*. Twadde groep .* wurdt ferlike mei de twadde x, en wy hawwe wer gjin karakters oer. En as de motor wer berikt = в .*.*=.*, neat wurket. En hy rint wer werom.
Dizze kear de groep .* noch wedstriden x=, mar de twadde groep .* net mear x, en nul karakters. De motor besiket in letterlik karakter te finen = yn it patroan .*.*=.*, mar komt net út (de earste groep hat it ommers al beset .*). En hy rint wer werom.
Dizze kear de earste groep .* nimt allinnich de earste x. Mar de twadde groep .* "greedly" vangt =x. Hawwe jo al rieden wat der barre sil? De motor besiket te oerien mei de letterlike =, mislearret en makket in oare backtracking.
Earste groep .* komt noch oerien mei de earste x. Twadde .* allinnich nimt =. Fansels kin de motor net oerienkomme mei de letterlike =, want de twadde groep hat dit al dien .*. En wer weromlûke. En wy besykje in tekenrige fan trije karakters te passen!
As gefolch, de earste groep .* komt allinnich oerien mei de earste x, twadde .* - mei nul karakters, en de motor komt úteinlik oerien mei de letterlike = yn útdrukking с = yn line. Folgjende is de lêste groep .* wurdt fergelike mei de lêste x.
23 stappen allinnich foar x=x. Besjoch in koarte fideo oer it brûken fan Perl , dat lit sjen hoe't stappen en backtracking foarkomme.
Dit is al in soad wurk, mar wat as ynstee x=x Wy sille hawwe x=xx? Dat binne 33 stappen. En as x=xxx? 45. De relaasje is net lineêr. De grafyk toant in ferliking fan x=x до x=xxxxxxxxxxxxxxxxxxxx (20 x после =). As wy hawwe 20 x na =, de motor foltôget de matching yn 555 stappen! (Boppedat, as wy hawwe ferlern x= en de snaar bestiet gewoan út 20 x, sil de motor 4067 stappen nimme om te begripen dat d'r gjin wedstriden binne).
Dizze fideo toant alle backtracking foar fergeliking x=xxxxxxxxxxxxxxxxxxxx:
It probleem is dat as de tekenrige grutter wurdt, de oerienkommende tiid super-lineêr groeit. Mar dingen kinne noch slimmer wurde as de reguliere ekspresje wat oanpast wurdt. Litte we sizze dat wy hiene .*.*=.*; (dat is, der wie in letterlike puntkomma oan 'e ein fan it patroan). Bygelyks om in útdrukking te passen lykas foo=bar;.
En hjir soe backtracking in echte ramp wêze. Foar ferliking x=x it sil nimme 90 stappen, net 23. En dat oantal groeit fluch. Fergelykje x= en 20 x, 5353 stappen binne nedich. Hjir is it diagram. Sjoch op de as wearden Y ferlike mei de foarige grafyk.
As jo ynteressearre binne, besjoch dan alle 5353 mislearre oerienkommende stappen x=xxxxxxxxxxxxxxxxxxxx и .*.*=.*;
Troch loai te brûken ynstee fan gierige matching, kin de omfang fan backtracking wurde kontrolearre. As wy feroarje de oarspronklike útdrukking nei .*?.*?=.*?, foar ferliking x=x it sil nimme 11 stappen (net 23). As foar x=xxxxxxxxxxxxxxxxxxxx. Alles omdat ? после .* fertelt de motor in oerienkomt mei in minimum oantal karakters foardat jo fierdergean.
Mar lazy mappings net hielendal oplosse it backtracking probleem. As wy ferfange it katastrophale foarbyld .*.*=.*; op .*?.*?=.*?;, sil de útfieringstiid itselde bliuwe. x=x noch fereasket 555 stappen, en x= en 20 x - 5353.
It iennichste ding dat kin wurde dien (njonken it folslein oerskriuwen fan it patroan foar gruttere spesifisiteit) is in ferlitte de reguliere ekspresje motor mei syn backtracking meganisme. Dit sille wy de kommende wiken dwaan.
De oplossing foar dit probleem is bekend sûnt 1968, doe't Kent Thompson in artikel skreau ("Programming Methods: Regular Expression Search Algorithm"). It artikel beskriuwt in meganisme wêrmei jo te bekearen in reguliere útdrukking yn net-deterministyske finite steat masines, en nei steat feroarings yn net-deterministyske finite steat masines, brûke in algoritme waans útfiering tiid hinget linear op de matched string.
Programming Metoaden
Reguliere ekspresje Search Algoritme
Ken Thompson
Bell Telephone Laboratories, Inc., Murray Hill, New JerseyIt beskriuwt in metoade foar it sykjen nei in spesifike tekenrige yn tekst en besprekt de ymplemintaasje fan dizze metoade yn kompilatorfoarm. De kompilator nimt de reguliere ekspresje as boarnekoade en produsearret it IBM 7094-programma as objektkoade. It objektprogramma nimt ynfier yn 'e foarm fan syktekst en stjoert in sinjaal út elke kear as in tekenrige fan tekst oerienkomt mei in opjûne reguliere ekspresje. It artikel jout foarbylden, problemen en oplossingen.
Algoritme
Foarige sykalgoritmen resultearren yn backtracking as in foar in part suksesfolle sykopdracht gjin resultaat oplevere.Yn kompilaasjemodus wurket it algoritme net mei symboalen. It jout ynstruksjes oan kompilearre koade. De útfiering is heul rap - nei it trochjaan fan gegevens oan 'e boppekant fan' e hjoeddeistige list, siket it automatysk nei alle mooglike opienfolgjende tekens yn 'e reguliere ekspresje.
It kompilaasje- en sykalgoritme is opnommen yn 'e time-sharing tekstbewurker as kontekstueel sykjen. Fansels is dit lang net de ienige tapassing fan sa'n sykproseduere. Bygelyks, in fariant fan dit algoritme wurdt brûkt as symboal sykopdracht yn in tabel yn assembler.
Der wurdt fan útgien dat de lêzer bekend is mei reguliere útdrukkingen en de IBM 7094 kompjûterprogrammearringstaal.Kompilator
De gearstaller bestiet út trije stadia dy't parallel rinne. De earste etappe is syntaksisfiltering, wêrtroch allinich syntaktyske korrekte reguliere útdrukkingen troch kinne passe. Dizze stap set ek de operator "·" yn om reguliere útdrukkingen te passen. Yn 'e twadde stap wurdt de reguliere ekspresje konvertearre nei postfix-foarm. Yn 'e tredde etappe wurdt objektkoade oanmakke. De earste 2 stadia binne fanselssprekkend, en wy sille net dwaen op har.
Thompson syn artikel praat net oer nondeterministic einige steat masines, mar it docht ferklearje de lineêre tiid algoritme goed en presintearret in ALGOL-60 programma dat generearret gearkomste taalkoade foar de IBM 7094. De ymplemintaasje is lestich, mar it idee is hiel simpel.
hjoeddeistige sykpaad. It wurdt fertsjintwurdige troch in ikoan ⊕ mei ien ynput en twa útgongen.
Ofbylding 1 toant de funksjes fan 'e tredde kompilaasjestap by it transformearjen fan in foarbyld fan reguliere ekspresje. De earste trije karakters yn it foarbyld binne a, b, c, en elk makket in stack yngong S [i] en in NNODE fjild.NNODE nei besteande koade om de resultearjende reguliere ekspresje te generearjen yn ien stapelyngong (sjoch figuer 5)
Dit is hoe't in reguliere útdrukking der útsjen soe .*.*=.*, as jo it foarstelle as yn 'e foto's fan Thompson's artikel.
Yn Fig. 0 binne der fiif steaten dy't begjinne fan 0, en 3 syklusen dy't begjinne fan steaten 1, 2 en 3. Dizze trije syklusen komme oerien mei trije .* yn in reguliere útdrukking. 3 ovalen mei stippen oerienkomme mei ien symboal. Ovaal mei in teken = komt oerien mei in letterlik karakter =. Steat 4 is definityf. As wy it berikke, dan wurdt de reguliere ekspresje oerienkomme.
Om te sjen hoe't sa'n steatdiagram kin brûkt wurde foar reguliere ekspresje-oerienkomst .*.*=.*, wy sille sjen nei string matching x=x. It programma begjint fan steat 0, lykas werjûn yn Fig. 1.
Foar dit algoritme om te wurkjen, de steat masine moat wêze yn ferskate steaten tagelyk. In net-deterministyske finite masine sil alle mooglike transysjes tagelyk meitsje.
Foardat it tiid hat om de ynfiergegevens te lêzen, giet it yn beide earste steaten (1 en 2), lykas werjûn yn Fig. 2.
Yn Fig. 2 lit sjen wat der bart as hy sjocht nei de earste x в x=x. x kin map nei de top punt, gean fan steat 1 en werom nei steat 1. Of x kin kaartsje nei it punt hjirûnder, gean fan steat 2 en werom nei steat 2.
Nei matching de earste x в x=x wy binne noch yn steaten 1 en 2. Wy kinne steat 3 of 4 net berikke, om't wy in letterlik karakter nedich binne =.
It algoritme besjocht dan = в x=x. Lykas x dêrfoar kin it oerienkomme mei ien fan 'e boppeste twa loops fan steat 1 nei steat 1 of fan steat 2 nei steat 2, mar it algoritme kin oerienkomme mei de letterlike = en ferhúzje fan steat 2 nei steat 3 (en fuortendaliks 4). Dit wurdt werjûn yn Fig. 3.
It algoritme giet dan troch nei de lêste x в x=x. Fan steaten 1 en 2 binne deselde oergongen werom mooglik nei steaten 1 en 2. Fan steat 3 x kin oerienkomme mei it punt oan 'e rjochterkant en gean werom nei steat 3.
Op dit stadium, elk karakter x=x beskôge, en sûnt wy hawwe berikt steat 4, de reguliere útdrukking komt oerien mei dy tekenrige. Elk karakter wurdt ien kear ferwurke, sadat dit algoritme lineêr is yn 'e lingte fan' e ynfierstring. En gjin backtracking.
Fansels, nei it berikken fan steat 4 (as it algoritme oerienkomt x=) de hiele reguliere ekspresje is oerienkommen, en it algoritme kin beëinigje sûnder it hielendal te beskôgjen x.
Dit algoritme hinget lineêr ôf fan 'e grutte fan' e ynfierstring.
Boarne: www.habr.com