Fyrir tæpum 9 árum síðan var Cloudflare lítið fyrirtæki og ég vann ekki fyrir það, ég var bara viðskiptavinur. Mánuði eftir að Cloudflare hófst, fékk ég tilkynningu um að vefsíðan mín DNS virðist ekki virka. Cloudflare hefur gert breytingu á , og það var bilað DNS.
Ég skrifaði strax til Matthew Prince með titlinum "Hvar er DNS minn?" og hann sendi langt svar fullt af tæknilegum upplýsingum (), sem ég svaraði:
Frá: John Graham-Cumming
Dagsetning: 7. október 2010, 9:14
Efni: Re: Hvar er DNS-ið mitt?
Til: Matthew PrinceFlott skýrsla, takk. Ég mun örugglega hringja ef það eru vandamál. Það er líklega þess virði að skrifa færslu um þetta þegar þú hefur safnað öllum tæknilegum upplýsingum. Ég held að fólk muni njóta opinnar og heiðarlegrar sögu. Sérstaklega ef þú festir línurit við það til að sýna hvernig umferð hefur vaxið frá upphafi.
Ég er með gott eftirlit á síðunni minni og ég fæ SMS um hverja bilun. Vöktun sýnir að bilunin átti sér stað frá 13:03:07 til 14:04:12. Próf eru framkvæmd á fimm mínútna fresti.
Ég er viss um að þú áttar þig á því. Ertu viss um að þú þurfir ekki þína eigin persónu í Evrópu? 🙂
Og hann svaraði:
Frá: Matthew Prince
Dagsetning: 7. október 2010, 9:57
Efni: Re: Hvar er DNS-ið mitt?
Til: John Graham-CummingÞakka þér fyrir. Við svöruðum öllum sem skrifuðu. Ég er á leiðinni á skrifstofuna núna og við munum skrifa eitthvað á bloggið eða festa opinbera færslu á spjallborðið okkar. Ég er alveg sammála, heiðarleiki er allt.
Nú er Cloudflare mjög stórt fyrirtæki, ég vinn fyrir það, og nú þarf ég að skrifa opinskátt um mistök okkar, afleiðingar þeirra og gjörðir okkar.
Viðburðir 2. júlí
Þann 2. júlí settum við út nýja reglu í Stýrðum reglum fyrir WAFs vegna þess á sérhverjum örgjörvakjarna sem vinnur með HTTP/HTTPS umferð á Cloudflare netinu um allan heim. Við erum stöðugt að bæta stýrðar reglur fyrir WAF sem bregðast við nýjum veikleikum og ógnum. Í maí flýttum við okkur til dæmis til að vernda gegn alvarlegum varnarleysi í SharePoint. Allur tilgangurinn með WAF okkar er hæfileikinn til að dreifa reglum fljótt og á heimsvísu.
Því miður innihélt uppfærsla síðasta fimmtudags reglubundna tjáningu sem sóaði of miklu HTTP/HTTPS örgjörvatilföngum í bakslag. Kjarna proxy, CDN og WAF aðgerðir okkar urðu fyrir því. Grafið sýnir að örgjörvaauðlindir til að þjóna HTTP/HTTPS umferð ná næstum 100% á netþjónum á netinu okkar.
Örgjörvanotkun á einum stað viðveru meðan á atviki stendur
Fyrir vikið enduðu viðskiptavinir okkar (og viðskiptavinir okkar) með 502 villusíðu í Cloudflare lénum. 502 villur voru búnar til af Cloudflare framenda vefþjónum sem voru enn með ókeypis kjarna en gátu ekki átt samskipti við ferla sem annast HTTP/HTTPS umferð.
Við vitum hversu miklum óþægindum þetta hefur valdið viðskiptavinum okkar. Við skammast okkar hræðilega. Og þessi bilun kom í veg fyrir að við gætum tekist á við atvikið á áhrifaríkan hátt.
Ef þú varst einn af þessum viðskiptavinum varstu líklega hræddur, reiður og í uppnámi. Þar að auki höfum við ekki haft a . Hin mikla örgjörvanotkun var vegna einni WAF reglu með illa orðaðri reglulegri tjáningu sem leiddi til óhóflegrar bakfærslu. Hér er sektarkenndin: (?:(?:"|'|]|}||d|(?:nan|infinity|true|false|null|undefined|symbol|math)|`|-|+)+[)]*;?((?:s|-|~|!|{}||||+)*.*(?:.*=.*)))
Þó að þetta sé áhugavert í sjálfu sér (og ég mun tala um það nánar hér að neðan), var Cloudflare þjónustan niðri í 27 mínútur, ekki aðeins vegna slæmrar reglulegrar tjáningar. Það tók okkur smá tíma að lýsa atburðarrásinni sem leiddi til bilunarinnar og því var hægt að bregðast við. Í lok færslunnar mun ég lýsa afturför með reglulegri tjáningu og segja þér hvað þú átt að gera við það.
Hvað gerðist
Byrjum í röð. Allir tímar hér eru í UTC.
Klukkan 13:42 gerði verkfræðingur í eldveggsteyminu litla breytingu á uppgötvunarreglunum með því að nota sjálfvirkt ferli. Í samræmi við það var búið til miði um breytingarbeiðni. Við stjórnum slíkum miðum í gegnum Jira (skjáskot hér að neðan).
Eftir 3 mínútur birtist fyrsta síða PagerDuty sem tilkynnti um vandamál með WAF. Þetta var tilbúið próf sem prófar virkni WAF (við höfum hundruðir þeirra) utan Cloudflare til að fylgjast með eðlilegri notkun. Þessu fylgdu strax viðvörunarsíður um önnur Cloudflare end-to-end þjónustupróf sem misheppnuðust, alþjóðleg umferðarvandamál, útbreiddar 502 villur og fjöldann allan af skýrslum frá viðverustöðum okkar (PoP) í borgum um allan heim sem bentu til skorts af CPU auðlindum.
Ég fékk nokkrar af þessum viðvörunum, strunsaði út af fundi og var á leiðinni að borðinu þegar yfirmaður lausnaþróunardeildar okkar sagði að við hefðum tapað 80% af umferð okkar. Ég hljóp til SRE verkfræðinga okkar, sem voru þegar að vinna að vandamálinu. Í fyrstu héldum við að þetta væri einhvers konar óþekkt árás.
Cloudflare SRE verkfræðingar eru dreifðir um heiminn og fylgjast með ástandinu allan sólarhringinn. Venjulega láta þessar viðvaranir þig vita af sérstökum staðbundnum vandamálum af takmörkuðu umfangi, þeim er fylgst með á innri mælaborðum og er leyst oft á dag. En þessar síður og tilkynningar gáfu til kynna eitthvað virkilega alvarlegt og SRE verkfræðingar lýstu strax yfir alvarleikastiginu P0 og höfðu samband við stjórnendur og kerfisfræðinga.
Verkfræðingarnir okkar í London voru að hlusta á fyrirlestur í aðalsalnum á þeirri stundu. Gera þurfti hlé á fyrirlesturinn, allir söfnuðust saman í stórum ráðstefnusal og fleiri sérfræðingar voru kallaðir til. Þetta var ekki dæmigert vandamál sem SREs gátu tekist á við sjálfir. Það var brýnt að fá rétta sérfræðinga til starfa.
Klukkan 14:00 komumst við að því að vandamálið væri hjá WAF og það væri engin árás. Frammistöðuteymið dró CPU gögnin og það varð ljóst að WAF var um að kenna. Annar starfsmaður staðfesti þessa kenningu með því að nota strace. Einhver annar sá í loggunum að það væri vandamál með WAF. Klukkan 14:02 kom allt liðið til mín þegar lagt var til að nota global kill, vélbúnaður innbyggður í Cloudflare sem slekkur á einum íhlut um allan heim.
Hvernig við gerðum alþjóðlegt drep fyrir WAF er önnur saga. Það er ekki svo einfalt. Við notum okkar eigin vörur og síðan þjónustu okkar virkaði ekki, við gátum ekki auðkennt og skráð okkur inn á innra stjórnborðið (þegar allt var lagað komumst við að því að sumir liðsmenn höfðu misst aðgang vegna öryggiseiginleika sem slökkva á skilríkjum ef innra stjórnborðið er ekki notað fyrir a langur tími).
Og við gátum ekki komist að innri þjónustu okkar, eins og Jira eða byggingarkerfinu. Okkur vantaði lausnarkerfi, sem við notuðum sjaldan (þetta þarf líka að vinna úr). Að lokum tókst einum verkfræðingi að slökkva á WAF klukkan 14:07 og klukkan 14:09 voru umferðar- og örgjörvastig aftur í eðlilegt horf alls staðar. Restin af verndaraðferðum Cloudflare virkaði eins og venjulega.
Síðan fórum við að endurheimta WAF. Ástandið var óvenjulegt, þannig að við tókum neikvæð próf (spurðum okkur hvort breytingin væri raunverulega vandamálið) og jákvæð próf (að tryggðu að afturköllunin virkaði) í einni borg með aðskildri umferð og fluttum borgandi viðskiptavini þaðan.
Klukkan 14:52 vorum við sannfærð um að við skildum ástæðuna og gerðum leiðréttingu og virkjaðum WAF aftur.
Hvernig Cloudflare virkar
Cloudflare er með teymi verkfræðinga sem sérhæfir sig í að stjórna reglum fyrir WAF. Þeir leitast við að bæta uppgötvunartíðni, draga úr fölskum jákvæðum og bregðast fljótt við nýjum ógnum þegar þær koma fram. Á síðustu 60 dögum hafa verið afgreiddar 476 breytingarbeiðnir fyrir stýrðar reglur fyrir WAF (að meðaltali ein á 3 klukkustunda fresti).
Þessa tilteknu breytingu þurfti að beita í uppgerð, þar sem raunveruleg umferð viðskiptavina fer í gegnum regluna, en ekkert er lokað. Við notum þennan hátt til að prófa virkni reglnanna og mæla fölsk jákvæð og fölsk neikvæð tíðni. En jafnvel í hermiham verður að framkvæma reglurnar og í þessu tilfelli innihélt reglan reglubundna tjáningu sem neytti of mikils örgjörvaforða.
Eins og þú sérð af breytingabeiðninni hér að ofan erum við með dreifingaráætlun, afturköllunaráætlun og tengil á innri staðlaða rekstraraðferð (SOP) fyrir þessa tegund dreifingar. SOP fyrir breytingu á reglu gerir kleift að birta hana á heimsvísu. Reyndar, hjá Cloudflare, er allt öðruvísi gert og SOP kveður á um að við sendum fyrst hugbúnaðinn til prófunar og innri notkunar á innri viðverustað (PoP) (sem starfsmenn okkar nota), síðan til fárra viðskiptavina í einangruðum stað, þá til fjölda viðskiptavina, og aðeins þá til alls heimsins.
Svona lítur þetta út. Við notum git innbyrðis í gegnum BitBucket. Verkfræðingar sem vinna að breytingum senda inn kóða, sem er smíðaður í TeamCity, og þegar smíðin er liðin er gagnrýnendum úthlutað. Þegar dráttarbeiðni hefur verið samþykkt er kóðinn settur saman og röð prófana er keyrð (aftur).
Ef smíði og prófunum lýkur með góðum árangri er breytingabeiðni búin til í Jira og viðeigandi stjórnandi eða yfirmaður verður að samþykkja breytinguna. Eftir samþykki á sér stað dreifing í svokallaða „PoP menagerie“: HUNDUR, SVÍN og (hundur, svín og kanarífugl).
DOG PoP er Cloudflare PoP (eins og allar aðrar borgir okkar) sem er aðeins notað af Cloudflare starfsmönnum. PoP fyrir innri notkun gerir þér kleift að ná vandamálum áður en umferð viðskiptavina byrjar að streyma inn í lausnina. Gagnlegur hlutur.
Ef hundaprófið heppnast, færist kóðinn yfir á svínstigið (naggvín). Þetta er Cloudflare PoP, þar sem lítið magn af ókeypis umferð viðskiptavina rennur í gegnum nýjan kóða.
Ef allt er í lagi fer kóðinn inn á Kanarí. Við erum með þrjár Kanarí PoPs í mismunandi heimshlutum. Í þeim fer umferð greiddra og ókeypis viðskiptavina í gegnum nýja kóðann og þetta er síðasta athugun á villum.
Hugbúnaðarútgáfuferli hjá Cloudflare
Ef kóðinn er í lagi á Kanarí, gefum við hann út. Að fara í gegnum öll stigin - HUNDUR, SVÍN, Kanarí, allan heiminn - tekur nokkrar klukkustundir eða daga, allt eftir kóðabreytingunni. Vegna fjölbreytileika netkerfis Cloudflare og viðskiptavina, prófum við kóðann vandlega áður en við gefum hann út á heimsvísu til allra viðskiptavina. En WAF fylgir þessu ferli ekki sérstaklega vegna þess að bregðast þarf við ógnum fljótt.
WAF hótanir
Undanfarin ár hefur orðið mikil aukning á ógnum í algengum forritum. Þetta er vegna meira framboðs á hugbúnaðarprófunarverkfærum. Til dæmis skrifuðum við nýlega um ).
Heimild:
Mjög oft er sönnun um hugmynd búin til og birt strax á Github svo að teymin sem viðhalda forritinu geta fljótt prófað það og tryggt að það sé nægilega tryggt. Þess vegna þarf Cloudflare getu til að bregðast við nýjum árásum eins fljótt og auðið er svo viðskiptavinir hafi tækifæri til að laga hugbúnaðinn sinn.
Frábært dæmi um skjót viðbrögð Cloudflare er uppsetning á SharePoint varnarleysisvörnum í maí (). Næstum strax eftir að tilkynningarnar voru gefnar tókum við eftir miklum fjölda tilrauna til að nýta sér veikleikann í SharePoint uppsetningu viðskiptavina okkar. Strákarnir okkar eru stöðugt að fylgjast með nýjum ógnum og skrifa reglur til að vernda viðskiptavini okkar.
Reglan sem olli vandanum á fimmtudaginn átti að vernda gegn forskriftum á milli vefsvæða (XSS). Slíkar árásir hafa líka orðið mun tíðari undanfarin ár.
Heimild:
Staðlað ferli til að breyta stýrðri reglu fyrir WAF er að framkvæma samfellda samþættingu (CI) prófun fyrir alþjóðlega dreifingu. Síðasta fimmtudag gerðum við þetta og settum reglurnar út. 13:31 lagði verkfræðingur fram samþykkta dráttarbeiðni með breytingu.
Klukkan 13:37 tók TeamCity saman reglurnar, tók próf og gaf brautargengi. WAF prófunarsvítan prófar kjarnavirkni WAF og samanstendur af miklum fjölda einingaprófa fyrir einstakar aðgerðir. Eftir einingapróf prófuðum við reglurnar fyrir WAF með því að nota gríðarlegan fjölda HTTP beiðna. HTTP beiðnir athuga hvaða beiðnir ætti að loka fyrir af WAF (til að stöðva árásina) og hverjar er hægt að hleypa í gegn (til að loka ekki fyrir allt og forðast rangar jákvæðar). En við prófuðum ekki fyrir óhóflega örgjörvanotkun og að skoða annála fyrri WAF-bygginga sýnir að framkvæmdartími regluprófa jókst ekki og það var erfitt að gruna að það væri ekki nóg fjármagn.
Prófin stóðust og TeamCity byrjaði sjálfkrafa að beita breytingunni klukkan 13:42.
Quicksilver
Reglur WAF leggja áherslu á tafarlausa úrbætur á ógnum, þannig að við sendum þær inn með því að nota dreifða lykilgildageymslu Quicksilver, sem dreifir breytingum á heimsvísu á nokkrum sekúndum. Allir viðskiptavinir okkar nota þessa tækni þegar þeir breyta stillingum í mælaborðinu eða í gegnum API og það er henni að þakka að við bregðumst við breytingum með leifturhraða.
Við höfum ekki talað mikið um Quicksilver. Áður notuðum við sem verslun með lykilgildi sem er dreift á heimsvísu, en það voru rekstrarvandamál með hana og við skrifuðum okkar eigin verslun sem endurtekin var í meira en 180 borgum. Við notum nú Quicksilver til að ýta undir stillingarbreytingar til viðskiptavina, uppfæra WAF reglur og dreifa JavaScript kóða sem viðskiptavinir hafa skrifað til Cloudflare Workers.
Það tekur aðeins nokkrar sekúndur frá því að smella á hnapp á mælaborði eða kalla á API til að breyta stillingum um allan heim. Viðskiptavinir elskuðu þennan hraða uppsetningar. Og Workers gefur þeim næstum tafarlausa alþjóðlega hugbúnaðaruppsetningu. Að meðaltali dreifir Quicksilver um 350 breytingum á sekúndu.
Og Quicksilver er mjög hratt. Að meðaltali náðum við 99. hundraðshlutanum, 2,29 sekúndum, til að dreifa breytingum á hverri tölvu um allan heim. Hraði er yfirleitt af hinu góða. Þegar allt kemur til alls, þegar þú virkjar aðgerð eða hreinsar skyndiminni, gerist það næstum samstundis og alls staðar. Sending kóða í gegnum Cloudflare Workers á sér stað á sama hraða. Cloudflare lofar viðskiptavinum sínum hröðum uppfærslum á réttum tíma.
En í þessu tilviki lék hraðinn grimmilegan brandara við okkur og reglurnar breyttust alls staðar á nokkrum sekúndum. Þú gætir hafa tekið eftir því að WAF kóðann notar Lua. Cloudflare notar Lua mikið í framleiðslu og smáatriðum við erum . Lua WAF notar innbyrðis og beitir bakrás fyrir samsvörun. Það hefur engin kerfi til að verjast tjáningum sem fara úr böndunum. Hér að neðan mun ég tala meira um þetta og hvað við erum að gera í því.
Áður en reglurnar voru settar upp gekk allt snurðulaust fyrir sig: dragbeiðnin var búin til og samþykkt, CI/CD leiðslan safnaði og prófaði kóðann, breytingabeiðnin var lögð fram samkvæmt SOP sem stjórnar dreifingu og afturköllun og dreifingunni var lokið.
Cloudflare WAF dreifingarferli
Eitthvað fór úrskeiðis
Eins og ég sagði þá sendum við tugum nýrra WAF reglna í hverri viku og við erum með mörg kerfi til að verjast neikvæðum afleiðingum slíkrar uppsetningar. Og þegar eitthvað fer úrskeiðis er það venjulega sambland af nokkrum aðstæðum í einu. Ef þú finnur bara eina ástæðu er þetta auðvitað traustvekjandi, en það er ekki alltaf satt. Þetta eru ástæðurnar sem saman leiddu til bilunar á HTTP/HTTPS þjónustu okkar.
- Verkfræðingur skrifaði reglulega tjáningu sem gæti leitt til of mikils .
- Eiginleiki sem hefði getað komið í veg fyrir að venjuleg tjáning sóaði of miklum örgjörva var ranglega fjarlægður í endurnýjun á WAF nokkrum vikum áður - endurnýjunin var nauðsynleg til að láta WAF eyða minna fjármagni.
- Regluleg tjáningarvélin hafði enga tryggingu fyrir flækjustigi.
- Prófunarsvítan gat ekki greint of mikla örgjörvanotkun.
- SOP leyfir að reglubreytingar sem ekki eru brýnar séu settar út á heimsvísu án margra þrepa ferlis.
- Til baka áætlunin þurfti að keyra fulla WAF byggingu tvisvar, sem tók langan tíma.
- Fyrsta viðvörunin um alþjóðleg umferðarvandamál kom of seint af stað.
- Við tókum smá tíma að uppfæra stöðusíðuna.
- Við áttum í vandræðum með að fá aðgang að kerfum vegna bilunar og framhjáhlaupsaðferðin var ekki vel staðfest.
- SRE verkfræðingar misstu aðgang að sumum kerfum vegna þess að skilríki þeirra rann út af öryggisástæðum.
- Viðskiptavinir okkar höfðu ekki aðgang að Cloudflare mælaborðinu eða API vegna þess að þeir fara í gegnum Cloudflare svæði.
Hvað hefur breyst frá síðasta fimmtudag
Í fyrsta lagi hættum við algjörlega allri vinnu við útgáfur fyrir WAF og erum að gera eftirfarandi:
- Við erum að kynna aftur ofnotkunarvörn CPU sem við fjarlægðum. (Tilbúið)
- Athugaðu handvirkt allar 3868 reglurnar í stýrðu reglum fyrir WAF til að finna og leiðrétta önnur hugsanleg tilvik um óhóflegt bakslag. (Staðfestingu lokið)
- Við tökum frammistöðuprófíl fyrir allar reglur í prófunarsettinu. (Væntanlegur: 19. júlí)
- Skipt yfir í reglubundna tjáningarvél eða - báðir veita keyrslutímaábyrgð. (Væntanlegur: 31. júlí)
- Við erum að endurskrifa SOP til að dreifa reglum í áföngum, eins og öðrum hugbúnaði í Cloudflare, en á sama tíma höfum við getu til að neyða hnattræna dreifingu ef árásir eru þegar hafnar.
- Við erum að þróa getu til að fjarlægja Cloudflare mælaborðið og API af Cloudflare svæðinu.
- Sjálfvirk síðuuppfærslur .
Til lengri tíma litið erum við að hverfa frá Lua WAF sem ég skrifaði fyrir nokkrum árum. Færir WAF til . Þannig verður WAF hraðari og fær aukna vernd.
Ályktun
Þessi bilun olli vandræðum fyrir okkur og viðskiptavini okkar. Við brugðumst fljótt við að leiðrétta ástandið og erum nú að vinna í göllunum í ferlunum sem olli hruninu, auk þess að grafa enn dýpra til að verjast hugsanlegum vandamálum með reglubundnar tjáningar í framtíðinni þegar farið er yfir í nýja tækni.
Við erum mjög vandræðaleg vegna þessa bilunar og biðjum viðskiptavini okkar afsökunar. Við vonum að þessar breytingar muni tryggja að eitthvað eins og þetta gerist ekki aftur.
Umsókn. Til baka reglubundnar tjáningar
Til að skilja hvernig tjáningin:
(?:(?:"|'|]|}||d
(?:nan|infinity|true|false|null|undefined|symbol|math)|`|-
|+)+[)]*;?((?:s|-|~|!|{}||||+)*.*(?:.*=.*)))borðaði öll örgjörvaauðlindina, þú þarft að vita aðeins um hvernig staðlaða reglubundna tjáningarvélin virkar. Vandamálið hér er mynstrið .*(?:.*=.*). (?: og samsvarandi ) er hópur sem ekki fangar (það er tjáningin innan sviga er flokkuð sem ein tjáning).
Í samhengi við of mikla CPU neyslu má lýsa þessu mynstri sem .*.*=.*. Í þessu formi lítur mynstrið óþarflega flókið út. En það sem meira er um vert, í hinum raunverulega heimi geta tjáningar (eins og flóknar orðatiltæki í WAF reglum) sem biðja vélina um að passa við brot á eftir öðru broti leitt til skelfilegrar bakslags. Og þess vegna.
Í reglulegri tjáningu . þýðir að þú þarft að passa einn karakter, .* - passa núll eða fleiri stafi "græðgilega", það er að ná hámarki stafa, þannig að .*.*=.* þýðir að passa við núll eða fleiri stafi, passa síðan við núll eða fleiri stafi, finna bókstafinn = staf, passa núll eða fleiri stafi.
Tökum próflínuna x=x. Það samsvarar tjáningunni .*.*=.*. .*.* áður en jöfnunarmerkið samsvarar því fyrsta x (einn af hópunum .* соответствует x, og annar - núll stafir). .* eftir = leikir síðastir x.
Þessi samanburður krefst 23 skrefa. Fyrsti hópur .* в .*.*=.* virkar gráðugur og passar við allan strenginn x=x. Vélin færist í næsta hóp .*. Við höfum ekki fleiri persónur til að passa, svo seinni hópurinn .* passar við núll stafi (þetta er leyfilegt). Þá færist vélin á skiltið =. Það eru engin fleiri tákn (fyrsti hópur .* notaði allt orðatiltækið x=x), enginn samanburður á sér stað.
Og þá snýr reglubundin tjáningarvél aftur til upphafsins. Hann fer í fyrsta hópinn .* og ber það saman с x= (í staðinn x=x), og tekur svo við seinni hópnum .*. Annar hópur .* er borið saman við annað x, og aftur eigum við enga stafi eftir. Og þegar vélin nær aftur = в .*.*=.*, ekkert virkar. Og hann fer aftur á bak.
Að þessu sinni hópurinn .* passar enn x=, en seinni hópurinn .* ekki meira x, og núll stafir. Vélin er að reyna að finna bókstaflegan karakter = í mynstrinu .*.*=.*, en kemur ekki út (enda hefur fyrsti hópurinn þegar hertekið hann .*). Og hann fer aftur á bak.
Fyrsti hópurinn að þessu sinni .* tekur bara fyrsta x. En seinni hópurinn .* "græðgilega" fangar =x. Ertu búinn að giska á hvað mun gerast? Vélin reynir að passa við bókstafinn =, mistekst og gerir annað bakslag.
Fyrsti hópurinn .* passar samt við þann fyrsta x. Í öðru lagi .* tekur aðeins =. Auðvitað getur vélin ekki passað bókstaflega =, vegna þess að seinni hópurinn hefur þegar gert þetta .*. Og aftur afturför. Og við erum að reyna að passa saman streng með þremur stöfum!
Þar af leiðandi fyrsti hópurinn .* passar aðeins við þann fyrsta x, annað .* - með núll stöfum, og vélin passar loksins við bókstafinn = í tjáningu с = í línu. Næstur er síðasti hópurinn .* er borið saman við það síðasta x.
23 skref aðeins fyrir x=x. Horfðu á stutt myndband um notkun Perl , sem sýnir hvernig skref og bakslag eiga sér stað.
Þetta er nú þegar mikil vinna, en hvað ef í staðinn x=x við munum hafa x=xx? Það eru 33 skref. Og ef x=xxx? 45. Sambandið er ekki línulegt. Línuritið sýnir samanburð frá x=x í x=xxxxxxxxxxxxxxxxxxxx (20 x eftir =). Ef við eigum 20 x eftir =, vélin lýkur samsvöruninni í 555 skrefum! (Þar að auki, ef við höfum tapað x= og strengurinn samanstendur einfaldlega af 20 x, mun vélin taka 4067 skref til að skilja að það eru engar samsvörun).
Þetta myndband sýnir allar baklengingar til samanburðar x=xxxxxxxxxxxxxxxxxxxx:
Vandamálið er að þegar strengjastærðin eykst vex samsvörunartíminn ofurlínulega. En hlutirnir geta orðið enn verri ef reglulegri tjáningu er lítillega breytt. Segjum að við hefðum .*.*=.*; (þ.e.a.s. það var semíkomma í lok mynstrsins). Til dæmis til að passa við tjáningu eins og foo=bar;.
Og hér væri afturförin algjör hörmung. Til samanburðar x=x það mun taka 90 skref, ekki 23. Og þessi tala fer hratt vaxandi. Að bera saman x= og 20 x, 5353 skref þarf. Hér er grafið. Horfðu á ásgildin Y miðað við fyrri töflu.
Ef þú hefur áhuga skaltu skoða öll 5353 misheppnuð samsvörunarskref x=xxxxxxxxxxxxxxxxxxxx и .*.*=.*;
Með því að nota leti frekar en gráðuga samsvörun er hægt að stjórna umfangi bakslags. Ef við breytum upprunalegu tjáningunni í .*?.*?=.*?, til samanburðar x=x það mun taka 11 skref (ekki 23). Eins og fyrir x=xxxxxxxxxxxxxxxxxxxx. Allt vegna þess ? eftir .* segir vélinni að passa við lágmarksfjölda stafa áður en haldið er áfram.
En latur kortlagning leysir ekki að fullu bakslagsvandann. Ef við skiptum út stórslysadæminu .*.*=.*; á .*?.*?=.*?;, framkvæmdatíminn verður sá sami. x=x þarf samt 555 skref, og x= og 20 x - 5353.
Það eina sem hægt er að gera (fyrir utan að endurskrifa mynstrið algjörlega til að fá meiri sérhæfni) er að yfirgefa reglubundna tjáningarvélina með bakslagsbúnaðinum. Þetta er það sem við munum gera á næstu vikum.
Lausnin á þessu vandamáli hefur verið þekkt síðan 1968, þegar Kent Thompson skrifaði grein ("Forritunaraðferðir: Algrím fyrir reglubundið tjáningarleit"). Greinin lýsir vélbúnaði sem gerir þér kleift að umbreyta reglulegri tjáningu í óákveðin endanlegt ástand vélar, og eftir ástandsbreytingar í óákveðnu endanlegu ástandsvélum, notaðu reiknirit þar sem framkvæmdartími fer línulega eftir samsvarandi strengnum.
Forritunaraðferðir
Regular Expression Search Reiknirit
Ken Thompson
Bell Telephone Laboratories, Inc., Murray Hill, New JerseyÞar er lýst aðferð til að leita að ákveðnum streng af stöfum í texta og fjallað um útfærslu þessarar aðferðar í þýðandaformi. Þjálfarinn tekur reglulegu tjáninguna sem frumkóða og framleiðir IBM 7094 forritið sem hlutakóða. Hlutaforritið tekur inntak í formi leitartexta og gefur frá sér merki í hvert sinn sem textastrengur er lagður saman við tiltekna reglubundna tjáningu. Greinin gefur dæmi, vandamál og lausnir.
Reikniritið
Fyrri leitarreiknirit leiddu til baka ef leit að hluta tókst ekki skilaði niðurstöðu.Í samantektarham virkar reikniritið ekki með táknum. Það sendir leiðbeiningar í samsettan kóða. Framkvæmd er mjög hröð - eftir að hafa komið gögnum efst á núverandi lista, leitar það sjálfkrafa að öllum mögulegum stöfum í röð í venjulegu tjáningunni.
Safn- og leitarreikniritið er innifalið í textaritlinum til að deila tíma sem samhengisleit. Auðvitað er þetta langt í frá eina beiting slíkrar leitaraðferðar. Til dæmis er afbrigði af þessu reiknirit notað sem táknleit í töflu í assembler.
Gert er ráð fyrir að lesandinn þekki reglubundnar tjáningar og IBM 7094 tölvuforritunarmálið.Þjálfari
Þýðandinn samanstendur af þremur stigum sem keyra samhliða. Fyrsta stigið er setningafræðisía, sem leyfir aðeins setningafræðilega réttum reglulegum tjáningum að fara í gegnum. Þetta skref setur einnig "·" rekstraraðilann inn til að passa við reglulegar segðir. Í öðru skrefi er reglulegri tjáningu breytt í postfix form. Á þriðja stigi er hlutakóði búinn til. Fyrstu 2 stigin eru augljós og við munum ekki dvelja við þau.
Grein Thompson talar ekki um óákveðna endanlegt ástandsvélar, en hún útskýrir línulega tímaalgrímið vel og sýnir ALGOL-60 forrit sem býr til samsetningarmálskóða fyrir IBM 7094. Útfærslan er erfið, en hugmyndin er mjög einföld.
núverandi leitarleið. Það er táknað með ⊕ tákni með einu inntaki og tveimur útgangum.
Mynd 1 sýnir virkni þriðja söfnunarskrefsins þegar umbreytt er dæmi um venjulega segð. Fyrstu þrír stafirnir í dæminu eru a, b, c, og hver býr til staflafærslu S[i] og NNODE reit.NNODE við núverandi kóða til að búa til reglulegu tjáninguna sem myndast í einni staflafærslu (sjá mynd 5)
Svona myndi venjuleg tjáning líta út .*.*=.*, ef þú ímyndar þér það eins og á myndunum úr grein Thompson.
Í mynd. 0 eru fimm ríki sem byrja á 0 og 3 lotur sem byrja á ríkjum 1, 2 og 3. Þessar þrjár lotur samsvara þremur .* í reglulegri tjáningu. 3 sporöskjulaga með punktum samsvara einu tákni. Sporöskjulaga með merki = passar við bókstaflegan karakter =. Ríki 4 er endanlegt. Ef við náum því, þá er regluleg tjáning samsvarandi.
Til að sjá hvernig hægt er að nota slíka ástandsmynd fyrir samsvörun reglulegra tjáningar .*.*=.*, við skoðum strengjasamsvörun x=x. Forritið byrjar frá ástandi 0, eins og sýnt er á mynd. 1.
Til að þetta reiknirit virki verður ástandsvélin að vera í nokkrum ríkjum samtímis. Óákveðin endanleg vél mun gera allar mögulegar umbreytingar samtímis.
Áður en það hefur tíma til að lesa inntaksgögnin fara þau í bæði fyrstu stöðuna (1 og 2), eins og sýnt er á mynd. 2.
Í mynd. 2 sýnir hvað gerist þegar hann horfir á þann fyrsta x в x=x. x getur kortlagt að efsta punkti, farið frá ástandi 1 og aftur í ástand 1. Eða x getur kortlagt á punktinn hér að neðan, farið frá ástandi 2 og til baka í ástand 2.
Eftir að hafa passað fyrsta x в x=x við erum enn í ástandi 1 og 2. Við getum ekki náð ástandi 3 eða 4 vegna þess að við þurfum bókstaflegan staf =.
Reikniritið íhugar síðan = в x=x. Eins og x á undan er hægt að passa hana við annaðhvort af efstu tveimur lykkjunum frá ástandi 1 í ástand 1 eða frá ástandi 2 í ástand 2, en reikniritið getur passað bókstaflega = og færa úr ríki 2 í 3. ástand (og strax 4). Þetta er sýnt á mynd. 3.
Reikniritið fer síðan yfir í það síðasta x в x=x. Frá ástandi 1 og 2 eru sömu umskipti möguleg til baka í ástand 1 og 2. Frá ástandi 3 x getur passað við punktinn hægra megin og farið aftur í stöðu 3.
Á þessu stigi, hver persóna x=x talið, og þar sem við höfum náð ástandi 4, samsvarar reglulegu segðin þeim streng. Hver stafur er unnin einu sinni, þannig að þetta reiknirit er línulegt í lengd inntaksstrengsins. Og engin afturför.
Augljóslega, eftir að hafa náð ástandi 4 (þegar reikniritið hefur passað x=) öll reglulegu segðin er samsvörun og reikniritið getur hætt án þess að hafa það í huga x.
Þetta reiknirit fer línulega eftir stærð inntaksstrengsins.
Heimild: www.habr.com