Majdnem 9 évvel ezelőtt a Cloudflare egy pici cég volt, és én nem dolgoztam neki, csak vásárló voltam. Egy hónappal a Cloudflare elindítása után értesítést kaptam, hogy a webhelyem Úgy tűnik, hogy a DNS nem működik. A Cloudflare megváltoztatta , és meghibásodott a DNS.
Azonnal írtam Matthew Prince-nek „Hol van a DNS-em?” címmel, és visszaküldött egy hosszú, technikai részletekkel teli választ (), amire azt válaszoltam:
Feladó: John Graham-Cumming
Időpont: 7. október 2010. 9:14
Tárgy: Re: Hol van a DNS-em?
Címzett: Matthew PrinceSzuper riport, köszönöm. Probléma esetén mindenképp hívlak. Valószínűleg érdemes egy bejegyzést írni erről, miután összegyűjtötted az összes technikai információt. Szerintem az emberek élvezni fogják a nyílt és őszinte történetet. Főleg, ha grafikonokat csatolsz hozzá, amelyek megmutatják, hogyan nőtt a forgalom az indulás óta.
Az oldalamon jó a megfigyelés, minden meghibásodásról SMS-t kapok. A megfigyelés azt mutatja, hogy a hiba 13:03:07 és 14:04:12 között történt. A teszteket XNUMX percenként kell elvégezni.
Biztos vagyok benne, hogy rájössz. Biztos vagy benne, hogy nincs szüksége saját személyre Európában? 🙂
Ő pedig azt válaszolta:
Feladó: Matthew Prince
Időpont: 7. október 2010. 9:57
Tárgy: Re: Hol van a DNS-em?
Címzett: John Graham-CummingKöszönöm. Mindenkinek válaszoltunk, aki írt. Most úton vagyok az irodába, és írunk valamit a blogra, vagy kihelyezünk egy hivatalos bejegyzést a faliújságunkra. Teljesen egyetértek, az őszinteség minden.
Most a Cloudflare egy igazán nagy cég, érte dolgozom, és most nyíltan kell írnom a hibánkról, annak következményeiről és tetteinkről.
Július 2-i események
Július 2-án új szabályt vezettünk be a WAF-ok menedzselt szabályai között, ami miatt a Cloudflare hálózat HTTP/HTTPS forgalmat feldolgozó minden processzormagján világszerte. Folyamatosan fejlesztjük a WAF-okra vonatkozó felügyelt szabályokat, válaszul az új sebezhetőségekre és fenyegetésekre. Májusban például siettünk a SharePoint súlyos sérülékenysége elleni védelem érdekében. A WAF lényege a szabályok gyors és globális bevezetése.
Sajnos a múlt csütörtöki frissítés tartalmazott egy reguláris kifejezést, amely túl sok HTTP/HTTPS CPU erőforrást pazarolt el a visszalépésre. Alapvető proxy-, CDN- és WAF-funkcióink szenvedtek emiatt. A grafikon azt mutatja, hogy a HTTP/HTTPS-forgalom kiszolgálásához szükséges processzorerőforrások majdnem 100%-át elérik a hálózatunkban lévő szervereken.
CPU-használat egy jelenléti ponton incidens során
Ennek eredményeként ügyfeleink (és ügyfeleink ügyfelei) 502-es hibaoldalt kaptak a Cloudflare tartományokon. 502 hibát generáltak a Cloudflare front-end webszerverei, amelyek még rendelkeztek szabad magokkal, de nem tudtak kommunikálni a HTTP/HTTPS forgalmat kezelő folyamatokkal.
Tudjuk, hogy ez mennyi kellemetlenséget okozott ügyfeleinknek. Szörnyen szégyelljük magunkat. Ez a kudarc pedig megakadályozott bennünket abban, hogy hatékonyan kezeljük az esetet.
Ha Ön is ezen ügyfelek közé tartozott, valószínűleg félt, dühös és ideges volt. Ráadásul nálunk még nem volt a . A magas CPU-fogyasztás egy WAF-szabálynak köszönhető, amely egy rosszul megfogalmazott reguláris kifejezést tartalmaz, ami túlzott visszalépést eredményezett. Íme a bűnös kifejezés: (?:(?:"|'|]|}||d|(?:nan|infinity|true|false|null|undefined|symbol|math)|`|-|+)+[)]*;?((?:s|-|~|!|{}||||+)*.*(?:.*=.*)))
Bár ez már önmagában is érdekes (és alább részletesebben is szólok róla), a Cloudflare szolgáltatás 27 percig nem csak egy rossz reguláris kifejezés miatt állt le. Eltartott egy ideig, amíg leírtuk a kudarchoz vezető eseménysort, ezért lassan reagáltunk. A bejegyzés végén leírom a visszalépést egy reguláris kifejezéssel, és elmondom, mit kell vele kezdeni.
Mi történt
Kezdjük sorban. Itt minden időpont UTC-ben értendő.
13 óra 42 perckor a tűzfalcsapat egyik mérnöke apró változtatásokat hajtott végre az észlelési szabályokon automatikus folyamat segítségével. Ennek megfelelően változáskérő jegy jött létre. Az ilyen jegyeket a Jira-n keresztül kezeljük (képernyőkép lentebb).
3 perc múlva megjelent a PagerDuty első oldala, amely WAF-problémát jelentett. Ez egy szintetikus teszt volt, amely a WAF-ok működését (több száz van belőlük) teszteli a Cloudflare-en kívül a normál működés figyelése érdekében. Ezt azonnal követte a riasztások oldala a többi Cloudflare teljes körű szolgáltatásteszt meghiúsulásáról, globális forgalmi problémákról, széles körben elterjedt 502-es hibákról, valamint a világ városaiban található jelenléti pontjainktól (PoP) származó rengeteg jelentés, amelyek hiányt jeleztek. CPU erőforrások.
Több ilyen riasztást is kaptam, kirohantam egy megbeszélésről, és éppen az asztalhoz tartottam, amikor a megoldásfejlesztési osztályunk vezetője azt mondta, hogy forgalmunk 80%-át elvesztettük. Az SRE mérnökeinkhez futottam, akik már dolgoztak a problémán. Először azt hittük, hogy ez valami ismeretlen támadás.
A Cloudflare SRE mérnökei szétszóródtak a világban, és éjjel-nappal figyelik a helyzetet. Ezek a riasztások általában bizonyos korlátozott hatókörű helyi problémákról értesítik, a belső irányítópultok nyomon követik őket, és naponta többször is megoldódnak. De ezek az oldalak és értesítések valami igazán komoly dolgot jeleztek, és az SRE mérnökei azonnal bejelentették a P0 súlyossági szintet, és felvették a kapcsolatot a menedzsmenttel és a rendszermérnökökkel.
Londoni mérnökeink abban a pillanatban előadást hallgattak a nagyteremben. Az előadást félbe kellett szakítani, mindenki összegyűlt egy nagy konferenciateremben, és újabb szakembereket hívtak. Ez nem volt egy tipikus probléma, amellyel az SRE-k meg tudtak küzdeni maguktól. Sürgős volt a megfelelő szakemberek bevonása.
14:00-kor megállapítottuk, hogy a probléma a WAF-fel van, és nem történt támadás. A teljesítménycsapat lehívta a CPU-adatokat, és világossá vált, hogy a WAF a hibás. Egy másik alkalmazott megerősítette ezt az elméletet a strace segítségével. Valaki más látta a naplókban, hogy probléma van a WAF-fal. 14:02-kor az egész csapat hozzám fordult, amikor azt javasolták, hogy használjuk a globális killt, a Cloudflare-be épített mechanizmust, amely világszerte leállítja az egyik összetevőt.
Az, hogy miként végeztünk globális gyilkolást a WAF-nak, egy másik történet. Ez nem ilyen egyszerű. Saját termékeinket használjuk, és a szolgáltatásunk óta nem működött, nem tudtunk hitelesíteni és bejelentkezni a belső vezérlőpultra (amikor mindent kijavítottunk, megtudtuk, hogy néhány csapattag elvesztette a hozzáférést egy biztonsági funkció miatt, amely letiltja a hitelesítési adatokat, ha a belső vezérlőpultot nem használják hosszú idő).
És nem tudtuk elérni a belső szolgáltatásainkat, mint például a Jira vagy a build rendszer. Szükségünk volt egy megkerülő mechanizmusra, amit ritkán használtunk (ezt is ki kell dolgozni). Végül az egyik mérnöknek sikerült letiltania a WAF-ot 14:07-kor, és 14:09-kor a forgalom és a CPU szintje mindenhol visszaállt a normális szintre. A Cloudflare többi védelmi mechanizmusa a szokásos módon működött.
Aztán nekiláttunk a WAF visszaállításának. A helyzet a megszokottól eltérő volt, ezért negatív teszteket (kérdeztük meg magunktól, hogy valóban a változás okozta-e a probléma) és pozitív teszteket (megbizonyosodtunk arról, hogy a visszaállítás működött) egy városban, külön forgalommal, onnan szállítva át a fizető ügyfeleket.
14:52-kor meg voltunk győződve arról, hogy megértettük az okot, javítottunk, és újra engedélyeztük a WAF-ot.
Hogyan működik a Cloudflare
A Cloudflare mérnökcsapattal rendelkezik a WAF-ok szabályainak kezelésében. Arra törekednek, hogy javítsák az észlelési arányt, csökkentsék a hamis pozitív eredményeket, és gyorsan reagáljanak az új fenyegetésekre, amint azok megjelennek. Az elmúlt 60 napban 476 módosítási kérelem feldolgozása történt a WAF kezelt szabályaihoz (átlagosan 3 óránként egy).
Ezt a változást szimulációs módban kellett telepíteni, ahol a valódi ügyfélforgalom átmegy a szabályon, de semmi sincs blokkolva. Ezzel a móddal teszteljük a szabályok hatékonyságát, és mérjük a hamis pozitív és hamis negatív arányokat. De még szimulációs módban is ténylegesen végre kell hajtani a szabályokat, és ebben az esetben a szabály olyan reguláris kifejezést tartalmazott, amely túl sok processzorerőforrást emésztett fel.
Amint az a fenti módosítási kérelemből látható, az ilyen típusú telepítésekhez van egy telepítési tervünk, egy visszaállítási tervünk és egy hivatkozásunk egy belső szabványos működési eljárásra (SOP). A szabály módosítására vonatkozó SOP lehetővé teszi a szabály globális közzétételét. Valójában a Cloudflare-nél a dolgok teljesen másképp zajlanak, és az SOP előírja, hogy a szoftvert tesztelésre és belső használatra először egy belső jelenléti pontra (PoP) szállítsuk (amelyet alkalmazottaink használnak), majd néhány ügyfélnek egy elszigetelt helyre, majd nagyszámú ügyfélnek, és csak azután az egész világnak.
Így néz ki. A git-et belsőleg a BitBucketen keresztül használjuk. A változtatásokon dolgozó mérnökök kódot küldenek be, amely a TeamCity számára készült, és amikor a build sikeres, a rendszer felülvizsgálókat rendel hozzá. A lehívási kérelem jóváhagyása után a kód összeállításra kerül, és egy tesztsorozat fut (újra).
Ha a felépítés és a tesztek sikeresen befejeződnek, a Jira-ban módosítási kérelem jön létre, és a megfelelő menedzsernek vagy vezetőnek jóvá kell hagynia a változtatást. A jóváhagyást követően a telepítés megtörténik az úgynevezett „PoP menázsiába”: DOG, PIG és (kutya, disznó és kanári).
A DOG PoP egy Cloudflare PoP (mint minden városunkban), amelyet csak a Cloudflare alkalmazottai használnak. A belső használatra szánt PoP lehetővé teszi a problémák felderítését, mielőtt az ügyfélforgalom elkezdene befolyni a megoldásba. Hasznos dolog.
Ha a KUTYA teszt sikeres, a kód a PIG (tengerimalac) szakaszba kerül. Ez a Cloudflare PoP, ahol kis mennyiségű ingyenes ügyfélforgalom folyik át az új kódon.
Ha minden rendben, a kód bekerül a Canary-ba. Három Canary PoP-nk van a világ különböző részein. Ezekben a fizetős és ingyenes kliensek forgalma átmegy az új kódon, és ez az utolsó hibaellenőrzés.
Szoftverkiadási folyamat a Cloudflare-nél
Ha a kód rendben van Kanáriban, kiadjuk. Az összes szakaszon - KUTYA, PIG, Kanári, az egész világ - végigmenni több órát vagy napot vesz igénybe, a kódváltástól függően. A Cloudflare hálózatának és klienseinek sokfélesége miatt alaposan teszteljük a kódot, mielőtt globálisan kiadnánk az összes ügyfél számára. A WAF azonban nem követi kifejezetten ezt a folyamatot, mert a fenyegetésekre gyorsan kell reagálni.
WAF fenyegetés
Az elmúlt néhány évben jelentősen megnőtt a fenyegetések száma a gyakori alkalmazásokban. Ennek oka a szoftvertesztelő eszközök nagyobb elérhetősége. Nemrég például írtunk róla ).
Forrás:
Nagyon gyakran elkészítik a koncepció bizonyítékát, amelyet azonnal közzétesznek a Githubon, hogy az alkalmazást karbantartó csapatok gyorsan tesztelhessék és biztosítsák a megfelelő biztonságot. Ezért a Cloudflare-nek szüksége van arra, hogy a lehető leggyorsabban válaszoljon az új támadásokra, hogy az ügyfeleknek lehetőségük legyen kijavítani szoftvereiket.
A Cloudflare gyors reagálásának nagyszerű példája a SharePoint sebezhetőség elleni védelmének májusi bevezetése (). Szinte azonnal a bejelentések után észrevettük, hogy rengeteg próbálkozás történt ügyfeleink SharePoint-telepítéseinek biztonsági résének kihasználására. Srácaink folyamatosan figyelik az új fenyegetéseket és szabályokat írnak ügyfeleink védelme érdekében.
A csütörtöki problémát okozó szabálynak védenie kellett volna a cross-site scripting (XSS) ellen. Az elmúlt években az ilyen támadások is sokkal gyakoribbá váltak.
Forrás:
A WAF felügyelt szabályainak megváltoztatásának szokásos eljárása a folyamatos integrációs (CI) tesztelés a globális üzembe helyezés előtt. Múlt csütörtökön ezt tettük, és kidolgoztuk a szabályokat. 13 óra 31 perckor egy mérnök jóváhagyott húzási kérelmet nyújtott be változtatással.
13:37-kor a TeamCity összeszedte a szabályokat, lefuttatta a teszteket és megadta az utat. A WAF tesztcsomag a WAF alapvető funkcióit teszteli, és nagyszámú egységtesztből áll az egyes funkciókhoz. Az egységtesztek után rengeteg HTTP kéréssel teszteltük a WAF szabályait. A HTTP kérések ellenőrzik, hogy mely kéréseket kell blokkolnia a WAF-nak (a támadás elfogásához), és melyeket lehet átengedni (hogy ne blokkoljon mindent, és elkerülje a hamis pozitív eredményeket). De nem teszteltük a túlzott CPU-használatot, és a korábbi WAF buildek naplóit vizsgálva kiderül, hogy a szabályteszt végrehajtási ideje nem nőtt, és nehéz volt sejteni, hogy nem lesz elég erőforrás.
A tesztek sikeresek voltak, és a TeamCity 13:42-kor megkezdte a változtatás automatikus bevezetését.
Higany
A WAF-szabályok az azonnali fenyegetés-elhárításra összpontosítanak, ezért a Quicksilver elosztott kulcsérték-tárolójával telepítjük őket, amely másodpercek alatt globálisan terjeszti a változásokat. Minden ügyfelünk használja ezt a technológiát, amikor a dashboardban vagy az API-n keresztül módosítja a konfigurációt, és ennek köszönhetően villámgyorsan reagálunk a változásokra.
Nem sokat beszéltünk a Quicksilverről. Korábban használtuk globálisan terjesztett kulcsérték tárolóként, de működési problémák adódtak vele, és saját üzletet írtunk, több mint 180 városban replikálva. Mostantól a Quicksilvert használjuk a konfigurációs módosítások végrehajtására az ügyfelek számára, a WAF-szabályok frissítésére, valamint az ügyfelek által írt JavaScript-kódok Cloudflare Workers számára történő terjesztésére.
Csak néhány másodperc telik el attól, hogy az irányítópulton egy gombra kattintunk, vagy felhívunk egy API-t a konfiguráció módosításáig. Az ügyfelek szerették ezt a gyors beállítást. A Workers pedig szinte azonnali globális szoftvertelepítést biztosít számukra. A Quicksilver átlagosan körülbelül 350 változást terjeszt másodpercenként.
A Quicksilver pedig nagyon gyors. Átlagosan elértük a 99 másodperces 2,29. percentilist, hogy a változásokat világszerte minden számítógépre terjeszthessük. A sebesség általában jó dolog. Végül is, ha engedélyez egy funkciót vagy törli a gyorsítótárat, az szinte azonnal és mindenhol megtörténik. A kódküldés a Cloudflare Workersen keresztül azonos sebességgel történik. A Cloudflare gyors frissítéseket ígér ügyfeleinek a megfelelő időben.
De ebben az esetben a sebesség kegyetlen tréfát játszott velünk, és pillanatok alatt megváltoztak a szabályok mindenhol. Talán észrevette, hogy a WAF kód Lua-t használ. A Cloudflare széles körben használja a Luát a gyártásban és a részletekben mi vagyunk . Lua WAF használ belsőleg, és visszalépést alkalmaz az egyeztetéshez. Nincsenek olyan mechanizmusai, amelyek megvédenék az olyan kifejezéseket, amelyek kikerülnek az irányítás alól. Az alábbiakban erről és arról, hogy mit teszünk ellene, bővebben szólok.
A szabályok bevezetése előtt minden zökkenőmentesen zajlott: a lehívási kérelem létrejött és jóváhagyva, a CI/CD pipeline összegyűjtötte és tesztelte a kódot, a módosítási kérelem benyújtásra került a telepítést és visszaállítást szabályozó SOP szerint, és a telepítés befejeződött.
Cloudflare WAF telepítési folyamat
Valami elromlott
Mint mondtam, hetente több tucat új WAF-szabályt vezetünk be, és számos rendszerünk van az ilyen bevezetés negatív következményei elleni védekezésre. És ha valami elromlik, az általában több körülmény kombinációja egyszerre. Ha csak egy okot találsz, az természetesen megnyugtató, de nem mindig igaz. Ezek azok az okok, amelyek együtt a HTTP/HTTPS szolgáltatásunk meghibásodásához vezettek.
- Egy mérnök írt egy reguláris kifejezést, ami túlzott mértékű lehet .
- Egy olyan funkciót, amely megakadályozhatta volna, hogy a reguláris kifejezés túl sok CPU-t pazaroljon, tévedésből eltávolították a WAF néhány héttel korábbi újrafaktorálása során – az átalakításra azért volt szükség, hogy a WAF kevesebb erőforrást fogyasztson.
- A reguláris kifejezés motornak nem volt bonyolultsági garanciája.
- A tesztcsomag nem tudta észlelni a túlzott CPU-fogyasztást.
- Az SOP lehetővé teszi a nem sürgős szabálymódosítások globális bevezetését többlépcsős folyamat nélkül.
- A visszaállítási tervhez egy teljes WAF-felépítést kétszer kellett futtatni, ami sokáig tartott.
- A globális közlekedési problémákról szóló első riasztás túl későn jelent meg.
- Eltartott egy darabig az állapotoldal frissítése.
- Egy hiba miatt problémáink voltak a rendszerekhez való hozzáféréssel, és a bypass eljárás sem volt jól megalapozott.
- Az SRE mérnökei elvesztették hozzáférésüket egyes rendszerekhez, mert biztonsági okokból lejárt a hitelesítő adataik.
- Ügyfeleink nem fértek hozzá a Cloudflare irányítópultjához vagy API-hoz, mert egy Cloudflare régión keresztül mennek keresztül.
Mi változott múlt csütörtök óta
Először is teljesen leállítottunk minden munkát a WAF-kiadásokon, és a következőket tesszük:
- Újra bevezetjük az eltávolított CPU túlterhelés elleni védelmet. (Kész)
- A kezelt szabályok mind a 3868 szabályának manuális ellenőrzése, hogy a WAF megtalálja és kijavítsa a túlzott visszalépés egyéb lehetséges eseteit. (Az ellenőrzés befejeződött)
- A tesztkészletben szereplő összes szabály teljesítményprofilját tartalmazza. (Várható: július 19.)
- Váltás reguláris kifejezés motorra vagy - mindkettő futási garanciát nyújt. (Várható: július 31.)
- Átírjuk az SOP-t, hogy a szabályokat a Cloudflare többi szoftveréhez hasonlóan szakaszosan telepítsük, ugyanakkor lehetőségünk legyen vészhelyzeti globális telepítésre, ha a támadások már megkezdődtek.
- Folyamatosan fejlesztjük a Cloudflare irányítópult és API sürgős eltávolítását a Cloudflare régióból.
- Oldalfrissítések automatizálása .
Hosszú távon távolodunk attól a Lua WAF-tól, amit néhány éve írtam. WAF áthelyezése ide . Így a WAF gyorsabb lesz, és további védelmi szintet kap.
Következtetés
Ez a hiba gondot okozott nekünk és ügyfeleinknek. Gyorsan intézkedtünk a helyzet kijavítása érdekében, és most dolgozunk az összeomlást okozó folyamatok hibáin, valamint még mélyebbre ásunk, hogy elkerüljük a reguláris kifejezésekkel kapcsolatos esetleges problémákat az új technológiára való átállás során.
Nagyon szégyelljük ezt a kimaradást, és elnézést kérünk ügyfeleinktől. Reméljük, hogy ezek a változtatások biztosítják, hogy ilyesmi többé ne fordulhasson elő.
Alkalmazás. Reguláris kifejezések visszalépése
A kifejezés megértéséhez:
(?:(?:"|'|]|}||d
(?:nan|infinity|true|false|null|undefined|symbol|math)|`|-
|+)+[)]*;?((?:s|-|~|!|{}||||+)*.*(?:.*=.*)))felemésztette az összes CPU erőforrást, tudnod kell egy kicsit a szabványos reguláris kifejezés motor működéséről. A probléma itt a mintával van .*(?:.*=.*). (?: és megfelelő ) egy nem rögzítő csoport (vagyis a zárójelben lévő kifejezés egyetlen kifejezésként van csoportosítva).
A túlzott CPU-fogyasztással összefüggésben ez a minta így írható le .*.*=.*. Ebben a formában a minta szükségtelenül bonyolultnak tűnik. De még ennél is fontosabb, hogy a való világban katasztrofális visszalépéshez vezethetnek azok a kifejezések (például a WAF-szabályok összetett kifejezései), amelyek arra kérik a motort, hogy egyeztessen egy töredéket, amelyet egy másik töredék követ. És ezért.
Szabályos kifejezésben . azt jelenti, hogy egy karaktert kell egyeznie, .* - nulla vagy több karakter párosítása "mohón", azaz maximum karakter rögzítése, hogy .*.*=.* azt jelenti, hogy nulla vagy több karakter párosítása, majd nulla vagy több karakter párosítása, keresse meg a literal = karaktert, egyezzen meg nulla vagy több karaktert.
Vegyük a tesztsort x=x. Megfelel a kifejezésnek .*.*=.*. .*.* mielőtt az egyenlőségjel megegyezne az elsővel x (az egyik csoport .* megfelel a x, a második pedig nulla karakter). .* után = mérkőzések utoljára x.
Ez az összehasonlítás 23 lépést igényel. Első csoport .* в .*.*=.* mohón cselekszik, és illeszkedik az egész karakterlánchoz x=x. A motor a következő csoportba lép .*. Nincs több karakterünk, amihez illik, így a második csoport .* nulla karakternek felel meg (ez megengedett). Ezután a motor a jelre áll =. Nincs több szimbólum (első csoport .* az egész kifejezést használta x=x), nem történik összehasonlítás.
Ezután a reguláris kifejezés motorja visszatér az elejére. Továbblép az első csoportba .* és összehasonlítja с x= (helyett x=x), majd átveszi a második csoportot .*. Második csoport .* összehasonlítják a másodikkal x, és megint nincs karakterünk. És amikor a motor újra eléri = в .*.*=.*, semmi sem működik. És ismét meghátrál.
Ezúttal a csoport .* még egyezik x=, hanem a második csoport .* nem több x, és nulla karakter. A motor megpróbál szó szerinti karaktert találni = a mintában .*.*=.*, de nem jön ki (elvégre az első csoport már elfoglalta .*). És ismét meghátrál.
Ezúttal az első csoport .* csak az első x-et veszi. De a második csoport .* „mohón” elfog =x. Kitaláltad már, mi fog történni? A motor igyekszik megfelelni a szó szerintinek =, meghiúsul, és újabb visszalépést hajt végre.
Az első csoport .* még mindig megegyezik az elsővel x... A második .* csak vesz =. Természetesen a motor nem egyezhet a szó szerint =, mert a második csoport már megtette ezt .*. És ismét visszalépés. Mi pedig egy három karakterből álló sztringet próbálunk összehozni!
Ennek eredményeként az első csoport .* csak az elsővel egyezik x, második .* - nulla karakterrel, és a motor végre megfelel a literálnak = kifejezésben с = Sorban. Következő az utolsó csoport .* összehasonlítjuk az utolsóval x.
Csak 23 lépés x=x. Nézzen meg egy rövid videót a Perl használatáról , amely megmutatja, hogyan történik a lépések és a visszalépés.
Ez már sok munka, de mi van, ha helyette x=x nekünk lesz x=xx? Ez 33 lépés. És ha x=xxx? 45. A kapcsolat nem lineáris. A grafikon egy összehasonlítást mutat be x=x a x=xxxxxxxxxxxxxxxxxxxx (20 x után =). Ha van 20 x utánunk =, a motor 555 lépésben fejezi be a párosítást! (Sőt, ha veszítettünk x= és a karakterlánc egyszerűen 20-ból áll x, a motor 4067 lépést tesz meg, hogy megértse, nincsenek egyezések).
Ez a videó összehasonlítás céljából bemutatja az összes visszalépést x=xxxxxxxxxxxxxxxxxxxx:
Az a baj, hogy a karakterlánc méretének növekedésével az illesztési idő szuperlineárisan nő. De a dolgok még rosszabbra fordulhatnak, ha a reguláris kifejezést kissé módosítják. Mondjuk volt .*.*=.*; (vagyis szó szerinti pontosvessző volt a minta végén). Például, hogy megfeleljen egy olyan kifejezésnek, mint a foo=bar;.
És itt a visszalépés valódi katasztrófa lenne. Összehasonlításképp x=x 90 lépésre lesz szükség, nem 23-ra. És ez a szám gyorsan növekszik. Összehasonlítani x= és 20 x, 5353 lépésre van szükség. Íme a diagram. Nézd meg a tengelyértékeket Y az előző diagramhoz képest.
Ha érdekli, nézze meg mind az 5353 sikertelen egyezési lépést x=xxxxxxxxxxxxxxxxxxxx и .*.*=.*;
A lusta, nem pedig a mohó egyezés használatával szabályozható a visszalépés mértéke. Ha az eredeti kifejezést erre változtatjuk .*?.*?=.*?, Összehasonlításképp x=x 11 lépést vesz igénybe (nem 23). Ami pedig azt illeti x=xxxxxxxxxxxxxxxxxxxx... Mindezt azért ? után .* azt mondja a motornak, hogy egy minimális számú karaktert írjon be, mielőtt továbblép.
De a lusta leképezések nem oldják meg teljesen a visszalépés problémáját. Ha lecseréljük a katasztrofális példát .*.*=.*; on .*?.*?=.*?;, a végrehajtási idő változatlan marad. x=x továbbra is 555 lépést igényel, és x= és 20 x - 5353.
Az egyetlen dolog, amit tehetünk (a pontosabb minta teljes átírása mellett), az az, hogy elhagyjuk a reguláris kifejezés motorját és annak visszakövetési mechanizmusát. Ezt fogjuk tenni a következő hetekben.
A probléma megoldása 1968 óta ismert, amikor Kent Thompson cikket írt („Programozási módszerek: Reguláris kifejezés keresési algoritmusa”). A cikk egy olyan mechanizmust ír le, amely lehetővé teszi, hogy egy reguláris kifejezést nem determinisztikus véges állapotú gépekké alakítson át, és a nem determinisztikus véges állapotú gépek állapotváltozásai után olyan algoritmust használjon, amelynek végrehajtási ideje lineárisan függ az illesztett karakterlánctól.
Programozási módszerek
Reguláris kifejezés keresési algoritmusa
Ken Thompson
Bell Telephone Laboratories, Inc., Murray Hill, New JerseyLeír egy módszert egy adott karakterlánc keresésére a szövegben, és tárgyalja ennek a módszernek a megvalósítását fordítói formában. A fordító a reguláris kifejezést forráskódként veszi, és az IBM 7094 programot objektumkódként állítja elő. Az objektumprogram keresőszöveg formájában veszi fel a bemenetet, és minden alkalommal jelet ad ki, amikor egy szövegsort egy adott reguláris kifejezéshez illesztenek. A cikk példákat, problémákat és megoldásokat tartalmaz.
Algoritmus
A korábbi keresési algoritmusok visszalépést eredményeztek, ha a részben sikeres keresés nem hozott eredményt.Összeállítási módban az algoritmus nem működik szimbólumokkal. Utasításokat ad át a lefordított kódnak. A végrehajtás nagyon gyors – miután az adatokat az aktuális lista elejére továbbította, automatikusan megkeresi a reguláris kifejezés összes lehetséges egymást követő karakterét.
A fordítási és keresési algoritmus kontextus szerinti keresésként szerepel az időmegosztásos szövegszerkesztőben. Természetesen ez messze nem az egyetlen ilyen keresési eljárás alkalmazása. Ennek az algoritmusnak egy változatát például szimbólumkeresésként használják egy táblázatban az assemblerben.
Feltételezzük, hogy az olvasó ismeri a reguláris kifejezéseket és az IBM 7094 számítógépes programozási nyelvet.Fordítóprogram
A fordítóprogram három párhuzamosan futó szakaszból áll. Az első lépés a szintaktikai szűrés, amely csak a szintaktikailag helyes reguláris kifejezéseket engedi át. Ez a lépés a "·" operátort is beszúrja, hogy megfeleljen a reguláris kifejezéseknek. A második lépésben a reguláris kifejezést postfix formává alakítjuk. A harmadik szakaszban létrejön az objektumkód. Az első 2 szakasz nyilvánvaló, és nem foglalkozunk velük.
Thompson cikke nem beszél nemdeterminisztikus véges állapotú gépekről, de jól elmagyarázza a lineáris idő algoritmust, és bemutat egy ALGOL-60 programot, amely összeállítási nyelvi kódot állít elő az IBM 7094-hez. A megvalósítás bonyolult, de az ötlet nagyon egyszerű.
jelenlegi keresési útvonal. Ezt egy ⊕ ikon jelzi egy bemenettel és két kimenettel.
Az 1. ábra a harmadik fordítási lépés funkcióit mutatja reguláris kifejezés példa transzformációja során. A példa első három karaktere a, b, c, és mindegyik létrehoz egy S[i] verembejegyzést és egy NNODE mezőt.NNODE a meglévő kódhoz, hogy az eredményül kapott reguláris kifejezést egyetlen verembejegyzésben generálja (lásd: 5. ábra)
Így nézne ki egy reguláris kifejezés .*.*=.*, ha úgy képzeled el, mint a képeken Thompson cikkéből.
ábrán. 0 öt állapot 0-tól kezdődően, és 3 ciklus, amelyek az 1., 2. és 3. állapotból indulnak. Ez a három ciklus háromnak felel meg .* reguláris kifejezésben. 3 ponttal ellátott ovális egy szimbólumnak felel meg. Ovális jellel = szó szerinti karakterhez illeszkedik =. A 4. állapot végleges. Ha elérjük, akkor a reguláris kifejezés illeszkedik.
Hogy megtudja, hogyan használható egy ilyen állapotdiagram a reguláris kifejezés illesztésére .*.*=.*, megvizsgáljuk a karakterlánc-illesztést x=x. A program a 0 állapotból indul, ahogy az ábra mutatja. 1.
Ahhoz, hogy ez az algoritmus működjön, az állapotgépnek egyszerre több állapotban kell lennie. Egy nem determinisztikus véges gép minden lehetséges átmenetet egyszerre hajt végre.
Mielőtt ideje lenne kiolvasni a bemeneti adatokat, mindkét első állapotba (1 és 2) kerül, amint az az ábrán látható. 2.
ábrán. A 2. ábra azt mutatja, hogy mi történik, ha ránéz az elsőre x в x=x. x leképezhet a legfelső pontra, az 1. állapotból és vissza az 1. állapotba. Or x leképezheti az alábbi pontot, a 2. állapotból és vissza a 2. állapotba.
Miután megfelelt az elsőnek x в x=x még mindig az 1-es és 2-es állapotban vagyunk. Nem érhetjük el a 3-as vagy 4-es állapotot, mert szükségünk van egy szó szerinti karakterre =.
Ezután az algoritmus figyelembe veszi = в x=x. Mint előtte x, ez is illeszthető a két felső hurok bármelyikéhez az 1-es állapotból az 1-es állapotba vagy a 2-es állapotból a 2-es állapotba, de az algoritmus megfelelhet a literálnak. = és a 2-es állapotból a 3-as állapotba (és azonnal a 4-be). Ez az ábrán látható. 3.
Ezután az algoritmus az utolsóra lép x в x=x. Az 1. és 2. állapotból ugyanazok az átmenetek lehetségesek vissza az 1. és 2. állapotba. A 3. állapotból x megegyezik a jobb oldali ponttal, és visszatérhet a 3. állapothoz.
Ebben a szakaszban minden karakter x=x figyelembe vettük, és mivel elértük a 4. állapotot, a reguláris kifejezés megegyezik ezzel a karakterlánccal. Minden karakter egyszer kerül feldolgozásra, tehát ez az algoritmus lineáris a bemeneti karakterlánc hosszában. És semmi visszalépés.
Nyilvánvalóan a 4-es állapot elérése után (amikor az algoritmus megegyezett x=) a teljes reguláris kifejezés illeszkedik, és az algoritmus leállhat anélkül, hogy figyelembe venné x.
Ez az algoritmus lineárisan függ a bemeneti karakterlánc méretétől.
Forrás: will.com