Pothuajse 9 vjet më parë Cloudflare ishte një kompani e vogël, dhe unë nuk punova për të, isha thjesht një klient. Një muaj pas nisjes së Cloudflare, mora një njoftim se uebfaqja ime DNS nuk duket se po funksionon. Cloudflare ka bërë një ndryshim në , dhe kishte një DNS të prishur.
Menjëherë i shkrova Matthew Prince me titullin "Ku është DNS-ja ime?" dhe ai më ktheu një përgjigje të gjatë plot me detaje teknike (), të cilës unë iu përgjigja:
Nga: John Graham-Cumming
Data: 7 Tetor 2010, 9:14
Tema: Re: Ku është DNS-ja ime?
Për: Matthew PrinceRaport i bukur, faleminderit. Unë patjetër do të telefonoj nëse ka probleme. Ndoshta ia vlen të shkruani një postim për këtë pasi të keni mbledhur të gjithë informacionin teknik. Unë mendoj se njerëzit do të gëzojnë një histori të hapur dhe të sinqertë. Sidomos nëse i bashkëngjitni grafikë për të treguar se si është rritur trafiku që nga fillimi.
Unë kam monitorim të mirë në faqen time dhe marr një SMS për çdo dështim. Nga monitorimi rezulton se dështimi ka ndodhur nga ora 13:03:07 deri në orën 14:04:12. Testet kryhen çdo pesë minuta.
Jam i sigurt se do ta kuptosh. Jeni i sigurt që nuk keni nevojë për personin tuaj në Evropë? 🙂
Dhe ai u përgjigj:
Nga: Matthew Prince
Data: 7 Tetor 2010, 9:57
Tema: Re: Ku është DNS-ja ime?
Për: John Graham-CummingFaleminderit. Ne iu përgjigjëm të gjithëve që shkruan. Unë jam duke shkuar për në zyrë tani dhe do të shkruajmë diçka në blog ose do të vendosim një postim zyrtar në tabelën tonë të buletinit. Jam plotësisht dakord, ndershmëria është gjithçka.
Tani Cloudflare është një kompani vërtet e madhe, unë punoj për të dhe tani më duhet të shkruaj hapur për gabimin tonë, pasojat e tij dhe veprimet tona.
Ngjarjet e 2 korrikut
Më 2 korrik ne nxorëm një rregull të ri në Rregullat e menaxhuara për WAF për shkak të të cilit në çdo bërthamë procesori që përpunon trafikun HTTP/HTTPS në rrjetin Cloudflare në mbarë botën. Ne po përmirësojmë vazhdimisht rregullat e menaxhuara për WAF-të në përgjigje të dobësive dhe kërcënimeve të reja. Në maj, për shembull, ne nxituam për të mbrojtur kundër një cenueshmërie serioze në SharePoint. E gjithë pika e WAF tonë është aftësia për të vendosur rregulla të shpejta dhe globale.
Fatkeqësisht, përditësimi i të enjtes së kaluar përmbante një shprehje të rregullt që harxhoi shumë burime të CPU-së HTTP/HTTPS në kthim prapa. Si rezultat, funksionet tona kryesore të përfaqësuesit, CDN dhe WAF pësuan. Grafiku tregon se burimet e procesorit për të shërbyer trafikun HTTP/HTTPS arrijnë pothuajse 100% në serverët në rrjetin tonë.
Përdorimi i CPU-së në një pikë të pranisë gjatë një incidenti
Si rezultat, klientët tanë (dhe klientët e klientëve tanë) përfunduan me një faqe gabimi 502 në domenet Cloudflare. 502 gabime u krijuan nga serverët e faqes së përparme të Cloudflare që kishin ende bërthama të lira, por nuk ishin në gjendje të komunikonin me proceset që trajtonin trafikun HTTP/HTTPS.
Ne e dimë se sa shqetësime u ka shkaktuar kjo klientëve tanë. Na vjen tmerrësisht turp. Dhe ky dështim na pengoi të merreshim efektivisht me incidentin.
Nëse do të ishit një nga këta klientë, me siguri do të ishit të frikësuar, të zemëruar dhe të mërzitur. Për më tepër, ne nuk kemi pasur një . Konsumi i lartë i CPU-së ishte për shkak të një rregulli WAF me një shprehje të rregullt të formuluar keq që rezultoi në prapambetje të tepruar. Ja shprehja fajtore: (?:(?:"|'|]|}||d|(?:nan|infinity|true|false|null|undefined|symbol|math)|`|-|+)+[)]*;?((?:s|-|~|!|{}||||+)*.*(?:.*=.*)))
Ndërsa kjo është interesante në vetvete (dhe unë do të flas për të më në detaje më poshtë), shërbimi Cloudflare ishte i paaftë për 27 minuta jo vetëm për shkak të një shprehjeje të keqe të rregullt. Na u desh pak kohë për të përshkruar sekuencën e ngjarjeve që çuan në dështim, kështu që ishim të ngadaltë për t'u përgjigjur. Në fund të postimit, unë do të përshkruaj kthimin prapa në një shprehje të rregullt dhe do t'ju tregoj se çfarë të bëni me të.
Cfare ndodhi
Le të fillojmë me radhë. Të gjitha kohët këtu janë në UTC.
Në orën 13:42, një inxhinier në ekipin e murit të zjarrit bëri një ndryshim të vogël në rregullat e zbulimit duke përdorur një proces automatik. Prandaj, u krijua një biletë kërkese ndryshimi. Ne menaxhojmë bileta të tilla përmes Jira (pamja e ekranit më poshtë).
Pas 3 minutash, u shfaq faqja e parë e PagerDuty, duke raportuar një problem me WAF. Ky ishte një test sintetik që teston funksionalitetin e WAF (ne kemi qindra të tilla) jashtë Cloudflare për të monitoruar funksionimin normal. Kjo u pasua menjëherë nga faqet e sinjalizimeve në lidhje me dështimin e testeve të tjera të shërbimit Cloudflare nga fundi në fund, problemet e trafikut global, gabimet e përhapura 502 dhe një ton raportesh nga pikat tona të pranisë (PoP) në qytete në mbarë botën që treguan mungesë të burimeve të CPU-së.
Mora disa nga këto sinjalizime, dola me furtunë nga një takim dhe isha rrugës për te tavolina kur kreu i departamentit tonë të zhvillimit të zgjidhjeve tha se kishim humbur 80% të trafikut tonë. Unë vrapova te inxhinierët tanë SRE, të cilët tashmë po punonin për problemin. Në fillim menduam se ishte një lloj sulmi i panjohur.
Inxhinierët e Cloudflare SRE janë të shpërndarë nëpër botë dhe monitorojnë situatën gjatë gjithë kohës. Në mënyrë tipike, këto sinjalizime ju njoftojnë për çështje specifike lokale me shtrirje të kufizuar, gjurmohen në panelet e brendshme dhe zgjidhen disa herë në ditë. Por këto faqe dhe njoftime treguan diçka vërtet serioze, dhe inxhinierët e SRE menjëherë deklaruan nivelin e ashpërsisë P0 dhe kontaktuan menaxherët dhe inxhinierët e sistemit.
Inxhinierët tanë londinez po dëgjonin një leksion në sallën kryesore në atë moment. Leksioni duhej ndërprerë, të gjithë u mblodhën në një sallë të madhe konferencash dhe u thirrën më shumë specialistë. Ky nuk ishte një problem tipik që SRE-të mund ta trajtonin vetë. Ishte urgjente përfshirja e specialistëve të duhur.
Në orën 14:00 konstatuam se problemi ishte me FAF dhe nuk kishte asnjë sulm. Ekipi i performancës nxori të dhënat e CPU-së dhe u bë e qartë se fajin e kishte WAF. Një punonjës tjetër e konfirmoi këtë teori duke përdorur strace. Dikush tjetër pa në regjistra se kishte një problem me WAF. Në orën 14:02, i gjithë ekipi erdhi tek unë kur u propozua të përdorej globale kill, një mekanizëm i integruar në Cloudflare që mbyll një komponent në mbarë botën.
Si bëmë vrasje globale për WAF është një histori tjetër. Nuk është aq e thjeshtë. Ne përdorim produktet tona, dhe që nga shërbimi ynë nuk funksionoi, nuk mundëm të vërtetonim dhe të identifikoheshim në panelin e kontrollit të brendshëm (kur gjithçka u rregullua, mësuam se disa anëtarë të ekipit kishin humbur aksesin për shkak të një veçorie sigurie që çaktivizon kredencialet nëse paneli i kontrollit të brendshëm nuk përdoret për një kohe e gjate).
Dhe ne nuk mund të arrinim te shërbimet tona të brendshme, si Jira ose sistemi i ndërtimit. Ne kishim nevojë për një mekanizëm zgjidhës, të cilin e përdornim rrallë (kjo gjithashtu do të duhet të përpunohet). Më në fund, një inxhinier arriti të çaktivizojë WAF në orën 14:07, dhe në orën 14:09, trafiku dhe nivelet e CPU-së u kthyen në normalitet kudo. Pjesa tjetër e mekanizmave të mbrojtjes së Cloudflare funksionoi normalisht.
Pastaj ne filluam të rivendosim WAF. Situata nuk ishte e zakonshme, kështu që ne kryenim teste negative (duke pyetur veten nëse ndryshimi ishte vërtet problemi) dhe teste pozitive (duke u siguruar që rikthimi të funksiononte) në një qytet duke përdorur trafik të veçantë, duke transferuar klientët që paguanin prej andej.
Në orën 14:52 u bindëm se e kuptuam arsyen dhe bëmë një korrigjim dhe aktivizuam sërish WAF.
Si funksionon Cloudflare
Cloudflare ka një ekip inxhinierësh të dedikuar për menaxhimin e rregullave për WAF. Ata përpiqen të përmirësojnë shkallët e zbulimit, të zvogëlojnë pozitivët e rremë dhe t'i përgjigjen shpejt kërcënimeve të reja kur ato shfaqen. Në 60 ditët e fundit, janë përpunuar 476 kërkesa ndryshimi për rregullat e menaxhuara për WAF (mesatarisht një në çdo 3 orë).
Ky ndryshim i veçantë duhej të vendosej në modalitetin e simulimit, ku trafiku i vërtetë i klientit kalon përmes rregullit, por asgjë nuk bllokohet. Ne e përdorim këtë mënyrë për të testuar efektivitetin e rregullave dhe për të matur normat e rreme pozitive dhe negative. Por edhe në modalitetin e simulimit, rregullat në fakt duhet të ekzekutohen, dhe në këtë rast rregulli përmbante një shprehje të rregullt që konsumonte shumë burime të procesorit.
Siç mund ta shihni nga kërkesa e mësipërme për ndryshim, ne kemi një plan vendosjeje, një plan rikthimi dhe një lidhje me një procedurë operative standarde të brendshme (SOP) për këtë lloj vendosjeje. SOP për ndryshimin e një rregulli lejon që ai të publikohet globalisht. Në fakt, në Cloudflare, gjërat bëhen krejtësisht ndryshe dhe SOP dikton që ne fillimisht ta dërgojmë softuerin për testim dhe përdorim të brendshëm në një pikë të brendshme prezence (PoP) (të cilën punonjësit tanë e përdorin), pastaj te një numër i vogël klientësh në një vend të izoluar, pastaj për një numër të madh klientësh dhe vetëm më pas për të gjithë botën.
Kështu duket. Ne përdorim git nga brenda nëpërmjet BitBucket. Inxhinierët që punojnë në ndryshime paraqesin kodin, i cili është ndërtuar në TeamCity, dhe kur ndërtimi kalon, caktohen rishikuesit. Pasi të miratohet një kërkesë për tërheqje, kodi mblidhet dhe kryhen (përsëri) një sërë testesh.
Nëse ndërtimi dhe testet përfundojnë me sukses, krijohet një kërkesë ndryshimi në Jira dhe menaxheri ose drejtuesi përkatës duhet të miratojë ndryshimin. Pas miratimit, vendosja ndodh në të ashtuquajturën "menageri PoP": DOG, PIG dhe (qen, derr dhe kanarina).
DOG PoP është një Cloudflare PoP (si çdo qytet tjetër) që përdoret vetëm nga punonjësit e Cloudflare. PoP për përdorim të brendshëm ju lejon të kapni problemet përpara se trafiku i klientëve të fillojë të rrjedhë në zgjidhje. Gjë e dobishme.
Nëse testi DOG është i suksesshëm, kodi kalon në fazën PIG (derr gini). Ky është Cloudflare PoP, ku një sasi e vogël e trafikut falas të klientëve rrjedh përmes kodit të ri.
Nëse gjithçka është mirë, kodi shkon në Canary. Ne kemi tre PoP Kanarie në pjesë të ndryshme të botës. Në to, trafiku i klientëve me pagesë dhe falas kalon përmes kodit të ri dhe ky është kontrolli i fundit për gabime.
Procesi i lëshimit të softuerit në Cloudflare
Nëse kodi është në rregull në Canary, ne e lëshojmë atë. Kalimi nëpër të gjitha fazat - DOG, PIG, Canary, e gjithë bota - zgjat disa orë ose ditë, në varësi të ndryshimit të kodit. Për shkak të diversitetit të rrjetit dhe klientëve të Cloudflare, ne testojmë plotësisht kodin përpara se ta lëshojmë atë globalisht për të gjithë klientët. Por WAF nuk e ndjek në mënyrë specifike këtë proces sepse kërcënimeve duhet t'u përgjigjen shpejt.
Kërcënimet e WAF
Gjatë viteve të fundit, ka pasur një rritje të konsiderueshme të kërcënimeve në aplikacionet e zakonshme. Kjo është për shkak të disponueshmërisë më të madhe të mjeteve të testimit të softuerit. Për shembull, kohët e fundit kemi shkruar për ).
Burimi:
Shumë shpesh, një provë e konceptit krijohet dhe publikohet menjëherë në Github, në mënyrë që ekipet që mirëmbajnë aplikacionin të mund ta testojnë shpejt atë dhe të sigurohen që ai është i siguruar siç duhet. Prandaj, Cloudflare ka nevojë për aftësinë për t'iu përgjigjur sulmeve të reja sa më shpejt që të jetë e mundur, në mënyrë që klientët të kenë mundësinë të rregullojnë softuerin e tyre.
Një shembull i shkëlqyeshëm i përgjigjes së shpejtë të Cloudflare është vendosja e mbrojtjeve ndaj cenueshmërisë së SharePoint në maj (). Pothuajse menjëherë pasi u bënë njoftimet, ne vumë re një numër të madh përpjekjesh për të shfrytëzuar cenueshmërinë në instalimet e SharePoint të klientëve tanë. Djemtë tanë po monitorojnë vazhdimisht kërcënimet e reja dhe po shkruajnë rregulla për të mbrojtur klientët tanë.
Rregulli që shkaktoi problemin të enjten supozohej të mbrohej nga skriptimet ndër-site (XSS). Sulme të tilla janë bërë shumë më të shpeshta vitet e fundit.
Burimi:
Procedura standarde për ndryshimin e një rregulli të menaxhuar për një WAF është kryerja e testimit të integrimit të vazhdueshëm (CI) përpara vendosjes globale. Të enjten e kaluar ne e bëmë këtë dhe përcaktuam rregullat. Në orën 13:31, një inxhinier paraqiti një kërkesë të miratuar për tërheqje me një ndryshim.
Në orën 13:37 TeamCity mblodhi rregullat, zhvilloi testet dhe dha dritën. Kompleti i testeve WAF teston funksionalitetin kryesor të WAF dhe përbëhet nga një numër i madh testesh njësi për funksione individuale. Pas testeve të njësisë, ne testuam rregullat për WAF duke përdorur një numër të madh kërkesash HTTP. Kërkesat HTTP kontrollojnë se cilat kërkesa duhet të bllokohen nga WAF (për të përgjuar sulmin) dhe cilat mund të lejohen (në mënyrë që të mos bllokohen gjithçka dhe të shmangen pozitivet e rreme). Por ne nuk testuam për përdorim të tepruar të CPU-së dhe ekzaminimi i regjistrave të ndërtimeve të mëparshme WAF tregon se koha e ekzekutimit të testit të rregullave nuk u rrit dhe ishte e vështirë të dyshohej se nuk do të kishte burime të mjaftueshme.
Testet kaluan dhe TeamCity filloi të vendoste automatikisht ndryshimin në orën 13:42.
zhivë
Rregullat e WAF fokusohen në korrigjimin e menjëhershëm të kërcënimit, kështu që ne i vendosim ato duke përdorur dyqanin e shpërndarë të vlerave kryesore të Quicksilver, i cili përhap ndryshimet globalisht në sekonda. Të gjithë klientët tanë e përdorin këtë teknologji kur ndryshojnë konfigurimin në panelin e kontrollit ose nëpërmjet API-së dhe është falë saj që ne i përgjigjemi ndryshimeve me shpejtësi rrufeje.
Nuk kemi folur shumë për Quicksilver. Më parë kemi përdorur si një dyqan me vlerë kyçe të shpërndarë globalisht, por kishte probleme operacionale me të, dhe ne shkruam dyqanin tonë, të kopjuar në më shumë se 180 qytete. Tani përdorim Quicksilver për të nxitur ndryshimet e konfigurimit te klientët, për të përditësuar rregullat WAF dhe për të shpërndarë kodin JavaScript të shkruar nga klientët te Cloudflare Workers.
Duhen vetëm disa sekonda nga klikimi i një butoni në një pult ose thirrja e një API për të bërë një ndryshim konfigurimi në mbarë botën. Klientëve u pëlqeu kjo shpejtësi e konfigurimit. Dhe Workers u jep atyre vendosje pothuajse të menjëhershme globale të softuerit. Mesatarisht, Quicksilver përhap rreth 350 ndryshime në sekondë.
Dhe Quicksilver është shumë i shpejtë. Mesatarisht, ne arritëm përqindjen e 99-të prej 2,29 sekondash për të përhapur ndryshimet në çdo kompjuter në mbarë botën. Shpejtësia është zakonisht një gjë e mirë. Në fund të fundit, kur aktivizoni një funksion ose pastroni cache-in, kjo ndodh pothuajse menjëherë dhe kudo. Dërgimi i kodit përmes Cloudflare Workers ndodh me të njëjtën shpejtësi. Cloudflare u premton klientëve të saj përditësime të shpejta në kohën e duhur.
Por në këtë rast, shpejtësia bëri një shaka mizore me ne dhe rregullat ndryshuan kudo në pak sekonda. Ju mund të keni vënë re se kodi WAF përdor Lua. Cloudflare përdor Lua gjerësisht në prodhim dhe detaje ne . Lua WAF përdor nga brenda dhe aplikon backtracking për përputhje. Nuk ka mekanizma për të mbrojtur kundër shprehjeve që dalin jashtë kontrollit. Më poshtë do të flas më shumë për këtë dhe çfarë po bëjmë për të.
Përpara se të vendoseshin rregullat, gjithçka shkoi pa probleme: u krijua dhe miratua kërkesa për tërheqje, tubacioni CI/CD mblodhi dhe testoi kodin, kërkesa për ndryshim u dorëzua sipas SOP që rregullon vendosjen dhe rikthimin, dhe vendosja u përfundua.
Procesi i vendosjes së Cloudflare WAF
Dicka shkoi keq
Siç thashë, ne vendosim dhjetëra rregulla të reja WAF çdo javë dhe kemi shumë sisteme në vend për të mbrojtur kundër pasojave negative të një vendosjeje të tillë. Dhe kur diçka shkon keq, zakonisht është një kombinim i disa rrethanave në të njëjtën kohë. Nëse gjeni vetëm një arsye, kjo, sigurisht, është qetësuese, por jo gjithmonë është e vërtetë. Këto janë arsyet që së bashku çuan në dështimin e shërbimit tonë HTTP/HTTPS.
- Një inxhinier shkroi një shprehje të rregullt që mund të rezultojë në tepricë .
- Një veçori që mund të kishte parandaluar shprehjen e rregullt nga humbja e shumë CPU-së u hoq gabimisht në një rifaktorim të WAF disa javë më parë - rifaktorimi ishte i nevojshëm për ta bërë WAF të konsumonte më pak burime.
- Motori i shprehjes së rregullt nuk kishte garanci kompleksiteti.
- Kompleti i testimit nuk mund të zbulonte konsumin e tepërt të CPU-së.
- SOP lejon që ndryshimet jo urgjente të rregullave të shtrihen globalisht pa një proces me shumë hapa.
- Plani i rikthimit kërkonte ekzekutimin e një ndërtimi të plotë të WAF dy herë, gjë që mori shumë kohë.
- Alarmi i parë për problemet globale të trafikut u aktivizua shumë vonë.
- Na u desh pak kohë për të përditësuar faqen e statusit.
- Ne kishim probleme me aksesin në sisteme për shkak të një defekti dhe procedura e anashkalimit nuk ishte vendosur mirë.
- Inxhinierët SRE humbën aksesin në disa sisteme sepse kredencialet e tyre skaduan për arsye sigurie.
- Klientët tanë nuk kishin akses në panelin e kontrollit të Cloudflare ose API sepse kalojnë nëpër një rajon të Cloudflare.
Çfarë ka ndryshuar që nga e enjtja e kaluar
Së pari, ne ndaluam plotësisht të gjithë punën në lëshimet për WAF dhe po bëjmë sa vijon:
- Ne po rifusim mbrojtjen nga mbipërdorimi i CPU-së që hoqëm. (Gati)
- Kontrollimi manual i të 3868 rregullave në rregullat e menaxhuara për WAF për të gjetur dhe korrigjuar raste të tjera të mundshme të prapambetjes së tepërt. (Verifikimi i përfunduar)
- Ne përfshijmë profilin e performancës për të gjitha rregullat në grupin e testimit. (Pritet: 19 korrik)
- Kalimi në një motor me shprehje të rregullt ose - të dyja ofrojnë garanci për kohën e funksionimit. (Pritet: 31 korrik)
- Ne po rishkruajmë SOP për të vendosur rregullat në faza, si softuerët e tjerë në Cloudflare, por në të njëjtën kohë kemi aftësinë për të emergjencën e vendosjes globale nëse sulmet tashmë kanë filluar.
- Ne po zhvillojmë aftësinë për të hequr urgjentisht panelin e kontrollit të Cloudflare dhe API-në nga rajoni i Cloudflare.
- Automatizimi i përditësimeve të faqeve .
Për një kohë të gjatë po largohemi nga Lua WAF që kam shkruar disa vite më parë. Lëvizja e WAF në . Në këtë mënyrë WAF do të jetë më i shpejtë dhe do të marrë një nivel shtesë mbrojtjeje.
Përfundim
Ky dështim shkaktoi telashe për ne dhe klientët tanë. Ne vepruam shpejt për të korrigjuar situatën dhe tani po punojmë për të metat në proceset që shkaktuan përplasjen, si dhe po gërmojmë edhe më thellë për t'u mbrojtur nga problemet e mundshme me shprehje të rregullta në të ardhmen kur migrojmë në teknologjinë e re.
Jemi shumë të turpëruar për këtë ndërprerje dhe kërkojmë falje për klientët tanë. Shpresojmë që këto ndryshime të sigurojnë që diçka e tillë të mos ndodhë më.
Aplikacion. Tërheqja e shprehjeve të rregullta
Për të kuptuar se si shprehja:
(?:(?:"|'|]|}||d
(?:nan|infinity|true|false|null|undefined|symbol|math)|`|-
|+)+[)]*;?((?:s|-|~|!|{}||||+)*.*(?:.*=.*)))hëngri të gjitha burimet e CPU-së, duhet të dini pak se si funksionon motori standard i shprehjes së rregullt. Problemi këtu është modeli .*(?:.*=.*). (?: dhe përkatëse ) është një grup që nuk kap (d.m.th., shprehja në kllapa grupohet si një shprehje e vetme).
Në kontekstin e konsumit të tepërt të CPU-së, ky model mund të përshkruhet si .*.*=.*. Në këtë formë, modeli duket i panevojshëm kompleks. Por më e rëndësishmja, në botën reale, shprehjet (si shprehjet komplekse në rregullat e WAF) që i kërkojnë motorit të përputhet me një fragment të ndjekur nga një fragment tjetër, mund të çojnë në një kthim katastrofik. Dhe kjo është arsyeja pse.
Në shprehje të rregullt . do të thotë që ju duhet të përputheni me një personazh, .* - përputhni zero ose më shumë karaktere "me lakmi", domethënë kapni një maksimum karakteresh, në mënyrë që .*.*=.* do të thotë përputhni zero ose më shumë karaktere, më pas përputhni zero ose më shumë karaktere, gjeni karakterin literal =, përputhni zero ose më shumë karaktere.
Le të marrim linjën e provës x=x. Ajo korrespondon me shprehjen .*.*=.*. .*.* përpara se shenja e barazimit të përputhet me të parën x (një nga grupet .* korrespondon me x, dhe e dyta - zero karaktere). .* pas = ndeshjet zgjasin x.
Ky krahasim kërkon 23 hapa. Grupi i parë .* в .*.*=.* vepron me lakmi dhe përputhet me të gjithë vargun x=x. Motori kalon në grupin tjetër .*. Nuk kemi më personazhe për t'u përputhur, kështu që grupi i dytë .* përputhet me zero karaktere (kjo lejohet). Pastaj motori kalon në shenjë =. Nuk ka më simbole (grupi i parë .* përdori të gjithë shprehjen x=x), nuk ndodh asnjë krahasim.
Dhe pastaj motori i shprehjes së rregullt kthehet në fillim. Ai kalon në grupin e parë .* dhe e krahason atë с x= (në vend të x=x), dhe më pas merr grupin e dytë .*. Grupi i dytë .* krahasohet me të dytin x, dhe përsëri nuk na ka mbetur asnjë personazh. Dhe kur motori arrin përsëri = в .*.*=.*, asgjë nuk funksionon. Dhe ai tërhiqet përsëri.
Këtë herë grupi .* ende ndeshje x=, por grupi i dytë .* jo më x, dhe zero karaktere. Motori po përpiqet të gjejë një karakter të mirëfilltë = në model .*.*=.*, por nuk del (në fund të fundit, grupi i parë e ka zënë tashmë .*). Dhe ai tërhiqet përsëri.
Kësaj radhe grupi i parë .* merr vetëm x-in e parë. Por grupi i dytë .* kap "me lakmi". =x. E keni menduar tashmë se çfarë do të ndodhë? Motori përpiqet të përputhet me fjalë për fjalë =, dështon dhe bën një tjetër kthim prapa.
Grupi i parë .* ende përputhet me të parën x. Së dyti .* vetëm merr =. Sigurisht, motori nuk mund të përputhet me fjalë për fjalë =, sepse grupi i dytë tashmë e ka bërë këtë .*. Dhe përsëri kthim prapa. Dhe ne po përpiqemi të përputhemi me një varg prej tre karakteresh!
Si rezultat, grupi i parë .* përputhet vetëm me të parën x, e dyta .* - me zero karaktere, dhe motori më në fund përputhet me fjalë për fjalë = në shprehje с = ne rresht. Më pas është grupi i fundit .* krahasohet me të fundit x.
23 hapa vetëm për x=x. Shikoni një video të shkurtër rreth përdorimit të Perl , i cili tregon se si ndodhin hapat dhe kthimi prapa.
Kjo tashmë është shumë punë, por çka nëse në vend të kësaj x=x do të kemi x=xx? Janë 33 hapa. Dhe nëse x=xxx? 45. Marrëdhënia nuk është lineare. Grafiku tregon një krahasim nga x=x tek x=xxxxxxxxxxxxxxxxxxxx (20 x pas =). Nëse kemi 20 x pas =, motori kompleton përputhjen në 555 hapa! (Për më tepër, nëse kemi humbur x= dhe vargu thjesht përbëhet nga 20 x, motori do të ndërmarrë 4067 hapa për të kuptuar se nuk ka ndeshje).
Kjo video tregon të gjitha kthimet prapa për krahasim x=xxxxxxxxxxxxxxxxxxxx:
Problemi është se ndërsa madhësia e vargut rritet, koha e përputhjes rritet në mënyrë superlineare. Por gjërat mund të bëhen edhe më keq nëse shprehja e rregullt modifikohet pak. Le të themi se kishim .*.*=.*; (domethënë, kishte një pikëpresje fjalë për fjalë në fund të modelit). Për shembull, për të përputhur një shprehje si foo=bar;.
Dhe këtu kthimi prapa do të ishte një fatkeqësi e vërtetë. Per krahasim x=x do të duhen 90 hapa, jo 23. Dhe ky numër po rritet me shpejtësi. Te krahasosh x= dhe 20 x, nevojiten 5353 hapa. Këtu është grafiku. Shikoni vlerat e boshtit Y krahasuar me grafikun e mëparshëm.
Nëse jeni të interesuar, shikoni të gjitha 5353 hapat e dështuar të përputhjes x=xxxxxxxxxxxxxxxxxxxx и .*.*=.*;
Duke përdorur përputhjen dembel dhe jo të pangopur, mund të kontrollohet shkalla e kthimit prapa. Nëse e ndryshojmë shprehjen origjinale në .*?.*?=.*?, per krahasim x=x do të duhen 11 hapa (jo 23). Sa për x=xxxxxxxxxxxxxxxxxxxx. Të gjitha sepse ? pas .* i thotë motorit të përputhet me një numër minimal karakteresh përpara se të vazhdojë.
Por hartografimi dembel nuk e zgjidh plotësisht problemin e prapambetjes. Nëse zëvendësojmë shembullin katastrofik .*.*=.*; mbi .*?.*?=.*?;, koha e ekzekutimit do të mbetet e njëjtë. x=x ende kërkon 555 hapa, dhe x= dhe 20 x - 5353.
E vetmja gjë që mund të bëhet (përveç rishkrimit të plotë të modelit për një specifikë më të madhe) është të braktisësh motorin e shprehjes së rregullt me mekanizmin e tij të kthimit prapa. Kjo është ajo që ne do të bëjmë gjatë javëve të ardhshme.
Zgjidhja e këtij problemi dihet që nga viti 1968, kur Kent Thompson shkroi një artikull (“Metodat e programimit: Algoritmi i kërkimit të shprehjeve të rregullta”). Artikulli përshkruan një mekanizëm që ju lejon të konvertoni një shprehje të rregullt në makina të gjendjes së fundme jo-përcaktuese, dhe pas ndryshimeve të gjendjes në makinat e gjendjes së fundme jo-përcaktuese, përdorni një algoritëm, koha e ekzekutimit të të cilit varet në mënyrë lineare nga vargu i përputhur.
Metodat e programimit
Algoritmi i kërkimit të shprehjeve të rregullta
Ken Thompson
Bell Telephone Laboratories, Inc., Murray Hill, Nju XhersiAi përshkruan një metodë për kërkimin e një vargu specifik karakteresh në tekst dhe diskuton zbatimin e kësaj metode në formën e përpiluesit. Përpiluesi merr shprehjen e rregullt si kod burim dhe prodhon programin IBM 7094 si kod objekt. Programi i objektit merr të dhëna në formën e tekstit të kërkimit dhe lëshon një sinjal sa herë që një varg teksti përputhet me një shprehje të rregullt të caktuar. Artikulli ofron shembuj, probleme dhe zgjidhje.
Algoritmi
Algoritmet e mëparshme të kërkimit rezultuan në prapambetje nëse një kërkim pjesërisht i suksesshëm nuk arriti të prodhonte një rezultat.Në modalitetin e përpilimit, algoritmi nuk funksionon me simbole. Ai kalon udhëzimet në kodin e përpiluar. Ekzekutimi është shumë i shpejtë - pasi kalon të dhënat në krye të listës aktuale, ai kërkon automatikisht të gjitha karakteret e mundshme të njëpasnjëshme në shprehjen e rregullt.
Algoritmi i përpilimit dhe kërkimit përfshihet në redaktuesin e tekstit për ndarjen e kohës si kërkim kontekstual. Sigurisht, ky është larg nga aplikimi i vetëm i një procedure të tillë kërkimi. Për shembull, një variant i këtij algoritmi përdoret si një kërkim simboli në një tabelë në asembler.
Supozohet se lexuesi është i njohur me shprehjet e rregullta dhe gjuhën e programimit kompjuterik IBM 7094.Përpilues
Përpiluesi përbëhet nga tre faza që ecin paralelisht. Faza e parë është filtrimi i sintaksës, i cili lejon të kalojnë vetëm shprehjet e rregullta të sakta sintaksore. Ky hap gjithashtu fut operatorin "·" për të përputhur shprehjet e rregullta. Në hapin e dytë, shprehja e rregullt shndërrohet në formë postfikse. Në fazën e tretë, krijohet kodi i objektit. 2 fazat e para janë të dukshme dhe ne nuk do të ndalemi në to.
Artikulli i Thompson nuk flet për makinat jopërcaktuese të gjendjes së fundme, por shpjegon mirë algoritmin e kohës lineare dhe paraqet një program ALGOL-60 që gjeneron kodin e gjuhës së asamblesë për IBM 7094. Zbatimi është i ndërlikuar, por ideja është shumë e thjeshtë.
rruga aktuale e kërkimit. Ai përfaqësohet nga një ikonë ⊕ me një hyrje dhe dy dalje.
Figura 1 tregon funksionet e hapit të tretë të përpilimit kur transformohet një shembull i shprehjes së rregullt. Tre karakteret e para në shembull janë a, b, c dhe secila krijon një hyrje S[i] dhe një fushë NNODE.NNODE në kodin ekzistues për të gjeneruar shprehjen e rregullt që rezulton në një hyrje të vetme të pirgut (shih Figurën 5)
Kështu do të dukej një shprehje e rregullt .*.*=.*, nëse e imagjinoni si në fotot nga artikulli i Thompson.
Në Fig. 0 janë pesë gjendje që fillojnë nga 0, dhe 3 cikle që fillojnë nga gjendjet 1, 2 dhe 3. Këto tre cikle korrespondojnë me tre .* në një shprehje të rregullt. 3 ovale me pika korrespondojnë me një simbol. Oval me një shenjë = përputhet me një karakter të mirëfilltë =. Shteti 4 është përfundimtar. Nëse e arrijmë atë, atëherë shprehja e rregullt përputhet.
Për të parë se si një diagram i tillë i gjendjes mund të përdoret për përputhjen e shprehjeve të rregullta .*.*=.*, do të shikojmë përputhjen e vargjeve x=x. Programi fillon nga gjendja 0, siç tregohet në Fig. 1.
Që ky algoritëm të funksionojë, makina e gjendjes duhet të jetë në disa gjendje njëkohësisht. Një makinë e fundme jo-përcaktuese do të bëjë të gjitha tranzicionet e mundshme në të njëjtën kohë.
Përpara se të ketë kohë për të lexuar të dhënat hyrëse, ai kalon në të dyja gjendjet e para (1 dhe 2), siç tregohet në Fig. 2.
Në Fig. 2 tregon se çfarë ndodh kur ai shikon të parën x в x=x. x mund të hartohet në pikën e sipërme, duke shkuar nga gjendja 1 dhe përsëri në gjendjen 1. Ose x mund të hartohet në pikën më poshtë, duke shkuar nga gjendja 2 dhe përsëri në gjendjen 2.
Pasi përputhet me të parën x в x=x ne jemi ende në gjendjet 1 dhe 2. Ne nuk mund të arrijmë gjendjen 3 ose 4 sepse na duhet një karakter literal =.
Më pas algoritmi merr në konsideratë = в x=x. Ashtu si x para tij, ai mund të përputhet me njërën nga dy ciklit kryesor nga gjendja 1 në gjendjen 1 ose nga gjendja 2 në gjendjen 2, por algoritmi mund të përputhet me fjalëpërfjalën = dhe lëvizni nga gjendja 2 në gjendjen 3 (dhe menjëherë 4). Kjo është treguar në Fig. 3.
Më pas, algoritmi kalon në atë të fundit x в x=x. Nga gjendjet 1 dhe 2 të njëjtat kalime janë të mundshme përsëri në gjendjet 1 dhe 2. Nga gjendja 3 x mund të përputhet me pikën në të djathtë dhe të kthehet në gjendjen 3.
Në këtë fazë, çdo personazh x=x konsideruar, dhe meqenëse kemi arritur gjendjen 4, shprehja e rregullt përputhet me atë varg. Çdo karakter përpunohet një herë, kështu që ky algoritëm është linear në gjatësinë e vargut të hyrjes. Dhe asnjë kthim prapa.
Natyrisht, pas arritjes së gjendjes 4 (kur algoritmi është përputhur x=) e gjithë shprehja e rregullt përputhet dhe algoritmi mund të përfundojë pa e konsideruar fare atë x.
Ky algoritëm varet në mënyrë lineare nga madhësia e vargut hyrës.
Burimi: www.habr.com