For nesten 9 år siden var Cloudflare et lite selskap, og jeg jobbet ikke for det, jeg var bare en kunde. En måned etter lansering av Cloudflare, fikk jeg et varsel om at nettstedet mitt DNS ser ikke ut til å fungere. Cloudflare har gjort en endring til , og det var en ødelagt DNS.
Jeg skrev umiddelbart til Matthew Prince med tittelen "Hvor er min DNS?" og han sendte tilbake et langt svar fullt av tekniske detaljer (), som jeg svarte:
Fra: John Graham-Cumming
Dato: 7. oktober 2010, 9:14
Emne: Re: Hvor er min DNS?
Til: Matthew PrinceKul rapport, takk. Jeg vil definitivt ringe hvis det er problemer. Det er sannsynligvis verdt å skrive et innlegg om dette når du har samlet all teknisk informasjon. Jeg tror folk vil like en åpen og ærlig historie. Spesielt hvis du legger ved grafer for å vise hvordan trafikken har vokst siden lanseringen.
Jeg har god overvåking på siden min, og jeg mottar en SMS om hver feil. Overvåking viser at feilen skjedde fra 13:03:07 til 14:04:12. Tester utføres hvert femte minutt.
Jeg er sikker på at du vil finne ut av det. Er du sikker på at du ikke trenger din egen person i Europa? 🙂
Og han svarte:
Fra: Matthew Prince
Dato: 7. oktober 2010, 9:57
Emne: Re: Hvor er min DNS?
Til: John Graham-CummingTakk skal du ha. Vi svarte alle som skrev. Jeg er på vei til kontoret nå, og vi skal skrive noe på bloggen eller feste et offisielt innlegg på oppslagstavlen vår. Jeg er helt enig, ærlighet er alt.
Nå er Cloudflare et veldig stort selskap, jeg jobber for det, og nå må jeg skrive åpent om feilen vår, konsekvensene og handlingene våre.
Hendelser 2. juli
Den 2. juli rullet vi ut en ny regel i Managed Rules for WAFs på grunn av dette på hver prosessorkjerne som behandler HTTP/HTTPS-trafikk på Cloudflare-nettverket over hele verden. Vi forbedrer stadig administrerte regler for WAF-er som svar på nye sårbarheter og trusler. I mai hastet vi for eksempel for å beskytte mot en alvorlig sårbarhet i SharePoint. Hele poenget med vår WAF er muligheten til å raskt og globalt distribuere regler.
Dessverre inneholdt forrige torsdags oppdatering et regulært uttrykk som kastet bort for mye HTTP/HTTPS CPU-ressurser på tilbakesporing. Våre kjerneproxy-, CDN- og WAF-funksjoner led som et resultat. Grafen viser at prosessorressurser for å betjene HTTP/HTTPS-trafikk når nesten 100 % på servere i nettverket vårt.
CPU-bruk på ett punkt av tilstedeværelse under en hendelse
Som et resultat endte våre klienter (og våre klienters klienter) opp med en 502 feilside på Cloudflare-domener. 502-feil ble generert av Cloudflare front-end webservere som fortsatt hadde ledige kjerner, men som ikke var i stand til å kommunisere med prosesser som håndterer HTTP/HTTPS-trafikk.
Vi vet hvor mye ulempe dette har påført våre kunder. Vi skammer oss fryktelig. Og denne feilen hindret oss i å håndtere hendelsen effektivt.
Hvis du var en av disse kundene, var du sannsynligvis redd, sint og opprørt. Dessuten har vi ikke hatt en . Det høye CPU-forbruket skyldtes én WAF-regel med et dårlig formulert regulært uttrykk som resulterte i overdreven tilbakesporing. Her er det skyldige uttrykket: (?:(?:"|'|]|}||d|(?:nan|infinity|true|false|null|undefined|symbol|math)|`|-|+)+[)]*;?((?:s|-|~|!|{}||||+)*.*(?:.*=.*)))
Selv om dette er interessant i seg selv (og jeg skal snakke om det mer detaljert nedenfor), var Cloudflare-tjenesten nede i 27 minutter, ikke bare på grunn av et dårlig regulært uttrykk. Det tok oss en stund å beskrive hendelsesforløpet som førte til feilen, så vi var trege med å svare. På slutten av innlegget vil jeg beskrive tilbakesporing i et regulært uttrykk og fortelle deg hva du skal gjøre med det.
Hva skjedde
La oss starte i rekkefølge. Alle tider her er i UTC.
Klokken 13 gjorde en ingeniør i brannmurteamet en liten endring i gjenkjenningsreglene ved hjelp av en automatisk prosess. Følgelig ble en endringsforespørsel opprettet. Vi administrerer slike billetter gjennom Jira (skjermbilde nedenfor).
Etter 3 minutter dukket den første siden av PagerDuty opp, og rapporterte et problem med WAF. Dette var en syntetisk test som tester funksjonaliteten til WAF-er (vi har hundrevis av dem) utenfor Cloudflare for å overvåke normal drift. Dette ble umiddelbart fulgt av sider med varsler om andre Cloudflare ende-til-ende-tjenestetester som mislyktes, globale trafikkproblemer, utbredte 502-feil og massevis av rapporter fra våre Points of Presence (PoP) i byer rundt om i verden som indikerte mangel av CPU-ressurser.
Jeg mottok flere av disse varslene, stormet ut av et møte, og var på vei til bordet da lederen for vår løsningsutviklingsavdeling sa at vi hadde mistet 80 % av trafikken vår. Jeg løp til SRE-ingeniørene våre, som allerede jobbet med problemet. Først trodde vi det var en slags ukjent angrep.
Cloudflare SRE-ingeniører er spredt rundt i verden og overvåker situasjonen døgnet rundt. Vanligvis varsler disse varslene deg om spesifikke lokale problemer med begrenset omfang, spores på interne dashbord og løses flere ganger per dag. Men disse sidene og varslene indikerte noe virkelig alvorlig, og SRE-ingeniører erklærte umiddelbart alvorlighetsgraden P0 og kontaktet ledelsen og systemingeniører.
Våre London-ingeniører hørte på en forelesning i hovedsalen i det øyeblikket. Foredraget måtte avbrytes, alle samlet seg i et stort konferanserom, og flere spesialister ble tilkalt. Dette var ikke et typisk problem som SRE-er kunne håndtere selv. Det hastet med å involvere de rette spesialistene.
Klokken 14:00 slo vi fast at problemet var med WAF og at det ikke var noe angrep. Ytelseteamet trakk CPU-dataene og det ble klart at WAF hadde skylden. En annen ansatt bekreftet denne teorien ved å bruke strace. Noen andre så i loggene at det var et problem med WAF. Klokken 14:02 kom hele teamet til meg da det ble foreslått å bruke global kill, en mekanisme innebygd i Cloudflare som slår av én komponent over hele verden.
Hvordan vi gjorde global kill for WAF er en annen historie. Så enkelt er det ikke. Vi bruker våre egne produkter, og siden vår tjeneste fungerte ikke, vi kunne ikke autentisere og logge på det interne kontrollpanelet (da alt var fikset, fikk vi vite at noen teammedlemmer hadde mistet tilgang på grunn av en sikkerhetsfunksjon som deaktiverer legitimasjon hvis det interne kontrollpanelet ikke brukes til en lang tid).
Og vi kunne ikke komme til våre interne tjenester, som Jira eller byggesystemet. Vi trengte en løsningsmekanisme, som vi brukte sjelden (denne må også løses). Til slutt klarte en ingeniør å deaktivere WAF klokken 14:07, og klokken 14:09 var trafikk- og CPU-nivåene tilbake til det normale overalt. Resten av Cloudflares beskyttelsesmekanismer fungerte som normalt.
Så satte vi i gang med å gjenopprette WAF. Situasjonen var utenom det vanlige, så vi kjørte negative tester (spør oss selv om endringen virkelig var problemet) og positive tester (som sørget for at tilbakeføringen fungerte) i én by ved å bruke separat trafikk, og overføre betalende kunder derfra.
Klokken 14:52 var vi overbevist om at vi forsto årsaken og gjorde en korreksjon, og aktivert WAF igjen.
Hvordan Cloudflare fungerer
Cloudflare har et team med ingeniører dedikert til å administrere regler for WAF-er. De streber etter å forbedre deteksjonsratene, redusere falske positiver og reagere raskt på nye trusler etter hvert som de dukker opp. I løpet av de siste 60 dagene har det vært behandlet 476 endringsforespørsler for administrerte regler for WAF (gjennomsnittlig én hver 3. time).
Denne spesielle endringen måtte distribueres i simuleringsmodus, der ekte klienttrafikk passerer gjennom regelen, men ingenting er blokkert. Vi bruker denne modusen til å teste effektiviteten til reglene og måle de falske positive og falske negative prisene. Men selv i simuleringsmodus må reglene faktisk utføres, og i dette tilfellet inneholdt regelen et regulært uttrykk som forbrukte for mye prosessorressurser.
Som du kan se fra endringsforespørselen ovenfor, har vi en distribusjonsplan, en tilbakerullingsplan og en lenke til en intern standard driftsprosedyre (SOP) for denne typen distribusjon. SOP for endring av en regel gjør at den kan publiseres globalt. Faktisk, hos Cloudflare gjøres ting helt annerledes, og SOP tilsier at vi først sender programvaren for testing og intern bruk til et internt tilstedeværelse (PoP) (som våre ansatte bruker), deretter til et lite antall klienter i et isolert sted, deretter til et stort antall kunder, og først da til hele verden.
Slik ser det ut. Vi bruker git internt via BitBucket. Ingeniører som jobber med endringer sender inn kode, som er bygget til TeamCity, og når bygget går igjennom, tildeles anmeldere. Når en pull-forespørsel er godkjent, settes koden sammen og en serie tester kjøres (igjen).
Hvis byggingen og testene fullføres vellykket, opprettes en endringsforespørsel i Jira, og den aktuelle lederen eller lederen må godkjenne endringen. Etter godkjenning skjer utplassering i det såkalte "PoP-menasjeriet": HUND, PIG og (hund, gris og kanarifugl).
DOG PoP er en Cloudflare PoP (som alle andre byer) som kun brukes av Cloudflare-ansatte. PoP for intern bruk lar deg fange opp problemer før kundetrafikk begynner å strømme inn i løsningen. Nyttig ting.
Hvis DOG-testen er vellykket, flyttes koden til PIG-stadiet (marsvin). Dette er Cloudflare PoP, hvor en liten mengde gratis kundetrafikk flyter gjennom ny kode.
Hvis alt er bra, går koden til Canary. Vi har tre Canary PoPs i forskjellige deler av verden. I dem går trafikken til betalte og gratis klienter gjennom den nye koden, og dette er den siste kontrollen for feil.
Programvareutgivelsesprosess hos Cloudflare
Hvis koden er ok på Canary, slipper vi den. Å gå gjennom alle stadiene - HUND, GRIS, Kanariøyene, hele verden - tar flere timer eller dager, avhengig av kodeendringen. På grunn av mangfoldet i Cloudflares nettverk og klienter, tester vi koden grundig før vi slipper den globalt til alle klienter. Men WAF følger ikke denne prosessen spesifikt fordi trusler må reageres raskt på.
WAF trusler
I løpet av de siste årene har det vært en betydelig økning i trusler i vanlige applikasjoner. Dette skyldes den større tilgjengeligheten av programvaretestverktøy. For eksempel skrev vi nylig om ).
Kilde:
Svært ofte blir et proof of concept opprettet og umiddelbart publisert på Github, slik at teamene som vedlikeholder applikasjonen raskt kan teste den og sikre at den er tilstrekkelig sikret. Derfor trenger Cloudflare muligheten til å svare på nye angrep så raskt som mulig slik at kundene har mulighet til å fikse programvaren sin.
Et godt eksempel på Cloudflares raske respons er utrullingen av SharePoint-sårbarhetsbeskyttelse i mai (). Nesten umiddelbart etter at kunngjøringene ble gjort, la vi merke til et stort antall forsøk på å utnytte sårbarheten i kundenes SharePoint-installasjoner. Gutta våre overvåker stadig nye trusler og skriver regler for å beskytte kundene våre.
Regelen som forårsaket problemet på torsdag skulle beskytte mot cross-site scripting (XSS). Slike angrep har også blitt mye hyppigere de siste årene.
Kilde:
Standardprosedyren for å endre en administrert regel for en WAF er å utføre testing av kontinuerlig integrasjon (CI) før global distribusjon. Sist torsdag gjorde vi dette og rullet ut reglene. Klokken 13 sendte en ingeniør inn en godkjent pull-forespørsel med endring.
Kl. 13:37 samlet TeamCity reglene, kjørte tester og ga klarsignal. WAF-testpakken tester kjernefunksjonaliteten til WAF og består av et stort antall enhetstester for individuelle funksjoner. Etter enhetstester testet vi reglene for WAF ved å bruke et stort antall HTTP-forespørsler. HTTP-forespørsler sjekker hvilke forespørsler som skal blokkeres av WAF (for å avskjære angrepet) og hvilke som kan slippes gjennom (for ikke å blokkere alt og unngå falske positiver). Men vi testet ikke for overdreven CPU-bruk, og å undersøke loggene til tidligere WAF-bygg viser at utførelsestiden for regeltesten ikke økte, og det var vanskelig å mistenke at det ikke ville være nok ressurser.
Testene bestod og TeamCity begynte automatisk å distribuere endringen klokken 13:42.
Quicksilver
WAF-regler fokuserer på umiddelbar utbedring av trusler, så vi distribuerer dem ved å bruke Quicksilvers distribuerte nøkkelverdilager, som sprer endringer globalt på sekunder. Alle våre kunder bruker denne teknologien når de endrer konfigurasjonen i dashbordet eller via API, og det er takket være den vi reagerer lynraskt på endringer.
Vi har ikke snakket så mye om Quicksilver. Tidligere brukte vi som en globalt distribuert nøkkelverdibutikk, men det var driftsproblemer med den, og vi skrev vår egen butikk, replikert i mer enn 180 byer. Vi bruker nå Quicksilver til å pushe konfigurasjonsendringer til klienter, oppdatere WAF-regler og distribuere JavaScript-kode skrevet av klienter til Cloudflare Workers.
Det tar bare noen få sekunder fra å klikke på en knapp på et dashbord eller kalle et API til å gjøre en konfigurasjonsendring over hele verden. Kundene elsket denne hastigheten på oppsettet. Og Workers gir dem nesten umiddelbar global programvaredistribusjon. I gjennomsnitt forplanter Quicksilver omtrent 350 endringer per sekund.
Og Quicksilver er veldig rask. I gjennomsnitt oppnådde vi den 99. persentilen på 2,29 sekunder for å spre endringer til hver datamaskin over hele verden. Hastighet er vanligvis en god ting. Når alt kommer til alt, når du aktiverer en funksjon eller sletter cachen, skjer det nesten umiddelbart og overalt. Sending av kode gjennom Cloudflare Workers skjer med samme hastighet. Cloudflare lover kundene sine raske oppdateringer til rett tid.
Men i dette tilfellet spilte fart en grusom spøk med oss, og reglene endret seg overalt i løpet av sekunder. Du har kanskje lagt merke til at WAF-koden bruker Lua. Cloudflare bruker Lua mye i produksjon og detaljer vi . Lua WAF bruker internt og bruker backtracking for matching. Den har ingen mekanismer for å beskytte mot uttrykk som kommer ut av kontroll. Nedenfor vil jeg snakke mer om dette og hva vi gjør med det.
Før reglene ble distribuert, gikk alt på skinner: pull-forespørselen ble opprettet og godkjent, CI/CD-pipelinen samlet inn og testet koden, endringsforespørselen ble sendt inn i henhold til SOP som styrer distribusjon og tilbakerulling, og distribusjonen ble fullført.
Cloudflare WAF-distribusjonsprosess
Noe gikk galt
Som jeg sa, vi distribuerer dusinvis av nye WAF-regler hver uke, og vi har mange systemer på plass for å beskytte mot de negative konsekvensene av en slik utplassering. Og når noe går galt, er det vanligvis en kombinasjon av flere omstendigheter samtidig. Hvis du bare finner én grunn, er dette selvfølgelig betryggende, men det er ikke alltid sant. Dette er årsakene som sammen førte til feilen i vår HTTP/HTTPS-tjeneste.
- En ingeniør skrev et regulært uttrykk som kan resultere i overdreven .
- En funksjon som kunne ha forhindret det regulære uttrykket i å kaste bort for mye CPU ble ved en feiltakelse fjernet i en refaktorisering av WAF flere uker tidligere - refaktoreringen var nødvendig for å få WAF til å bruke mindre ressurser.
- Den regulære uttrykksmotoren hadde ingen kompleksitetsgarantier.
- Testpakken kunne ikke oppdage for høyt CPU-forbruk.
- SOP tillater at ikke-hastende regelendringer kan rulles ut globalt uten en flertrinnsprosess.
- Tilbakerullingsplanen krevde å kjøre en full WAF-bygging to ganger, noe som tok lang tid.
- Det første varselet om globale trafikkproblemer ble utløst for sent.
- Vi brukte en stund på å oppdatere statussiden.
- Vi hadde problemer med å få tilgang til systemer på grunn av en feil, og bypass-prosedyren var ikke godt etablert.
- SRE-ingeniører mistet tilgangen til noen systemer fordi legitimasjonen deres utløp på grunn av sikkerhetsårsaker.
- Kundene våre hadde ikke tilgang til Cloudflare-dashbordet eller API fordi de går gjennom en Cloudflare-region.
Hva har endret seg siden forrige torsdag
For det første stoppet vi fullstendig alt arbeid med utgivelser for WAF og gjør følgende:
- Vi gjeninnfører CPU-overbruksbeskyttelsen som vi fjernet. (Klar)
- Kontrollerer alle 3868 XNUMX regler manuelt i de administrerte reglene for WAF for å finne og korrigere andre potensielle tilfeller av overdreven tilbakesporing. (Bekreftelse fullført)
- Vi inkluderer ytelsesprofilering for alle regler i testsettet. (Forventet: 19. juli)
- Bytte til en motor for regulære uttrykk eller - begge gir driftstidsgarantier. (Forventet: 31. juli)
- Vi omskriver SOP-en for å distribuere regler i etapper, som annen programvare i Cloudflare, men samtidig ha muligheten til å akutte global distribusjon dersom angrep allerede har begynt.
- Vi utvikler muligheten til å raskt fjerne Cloudflare-dashbordet og API-et fra Cloudflare-regionen.
- Automatisering av sideoppdateringer .
På lang sikt beveger vi oss bort fra Lua WAF jeg skrev for noen år siden. Flytter WAF til . På denne måten vil WAF være raskere og motta et ekstra beskyttelsesnivå.
Konklusjon
Denne feilen skapte problemer for oss og våre kunder. Vi handlet raskt for å rette opp situasjonen og jobber nå med feilene i prosessene som forårsaket krasjet, i tillegg til å grave enda dypere for å beskytte oss mot potensielle problemer med regulære uttrykk i fremtiden ved migrering til ny teknologi.
Vi er veldig flaue over dette strømbruddet og beklager overfor kundene våre. Vi håper disse endringene vil sikre at noe slikt ikke skjer igjen.
Applikasjon. Tilbakesporing av regulære uttrykk
For å forstå hvordan uttrykket:
(?:(?:"|'|]|}||d
(?:nan|infinity|true|false|null|undefined|symbol|math)|`|-
|+)+[)]*;?((?:s|-|~|!|{}||||+)*.*(?:.*=.*)))spiste opp alle CPU-ressursene, må du vite litt om hvordan standardmotoren for regulære uttrykk fungerer. Problemet her er mønsteret .*(?:.*=.*). (?: og tilsvarende ) er en ikke-fangende gruppe (det vil si at uttrykket i parentes er gruppert som et enkelt uttrykk).
I sammenheng med overdreven CPU-forbruk kan dette mønsteret beskrives som .*.*=.*. I denne formen ser mønsteret unødvendig komplekst ut. Men enda viktigere, i den virkelige verden kan uttrykk (som komplekse uttrykk i WAF-regler) som ber motoren om å matche et fragment etterfulgt av et annet fragment føre til katastrofal tilbakesporing. Og det er derfor.
I regulært uttrykk . betyr at du må matche én karakter, .* - match null eller flere tegn "grådig", det vil si å fange opp maksimalt antall tegn, slik at .*.*=.* betyr samsvar med null eller flere tegn, deretter samsvarer med null eller flere tegn, finn bokstavelig = tegnet, samsvar med null eller flere tegn.
La oss ta testlinjen x=x. Det tilsvarer uttrykket .*.*=.*. .*.* før likhetstegnet stemmer overens med det første x (en av gruppene .* соответствует x, og den andre - null tegn). .* etter = kamper sist x.
Denne sammenligningen krever 23 trinn. Første gruppe .* в .*.*=.* opptrer grådig og matcher hele strengen x=x. Motoren går til neste gruppe .*. Vi har ikke flere karakterer å matche, så den andre gruppen .* samsvarer med null tegn (dette er tillatt). Så beveger motoren seg til skiltet =. Det er ikke flere symboler (første gruppe .* brukte hele uttrykket x=x), ingen sammenligning forekommer.
Og så går den regulære uttrykksmotoren tilbake til begynnelsen. Han går videre til den første gruppen .* og sammenligner det с x= (i stedet x=x), og tar deretter på seg den andre gruppen .*. Andre gruppe .* sammenlignes med den andre x, og vi har igjen ingen tegn igjen. Og når motoren når igjen = в .*.*=.*, ingenting fungerer. Og han går tilbake igjen.
Denne gangen gruppen .* matcher fortsatt x=, men den andre gruppen .* ikke mer x, og null tegn. Motoren prøver å finne en bokstavelig karakter = i mønsteret .*.*=.*, men kommer ikke ut (tross alt har den første gruppen allerede okkupert den .*). Og han går tilbake igjen.
Denne gangen den første gruppen .* tar kun den første x. Men den andre gruppen .* "grådig" fanger =x. Har du allerede gjettet hva som vil skje? Motoren prøver å matche det bokstavelige =, feiler og gjør et nytt tilbakespor.
Den første gruppen av .* samsvarer fortsatt med den første x... Den andre .* tar bare =. Motoren kan selvfølgelig ikke matche det bokstavelige =, fordi den andre gruppen allerede har gjort dette .*. Og igjen tilbakesporing. Og vi prøver å matche en streng med tre tegn!
Som et resultat, den første gruppen .* samsvarer kun med den første x, sekund .* - med null tegn, og motoren matcher endelig det bokstavelige = i uttrykk с = på linje. Neste er den siste gruppen .* sammenlignes med den siste x.
23 trinn kun for x=x. Se en kort video om bruk av Perl , som viser hvordan trinn og tilbakesporing skjer.
Dette er allerede mye arbeid, men hva om i stedet x=x vi vil ha x=xx? Det er 33 trinn. Og hvis x=xxx? 45. Forholdet er ikke lineært. Grafen viser en sammenligning fra x=x til x=xxxxxxxxxxxxxxxxxxxx (20 x etter =). Hvis vi har 20 x etter =, fullfører motoren matchingen i 555 trinn! (Dessuten, hvis vi har tapt x= og strengen består ganske enkelt av 20 x, vil motoren ta 4067 trinn for å forstå at det ikke er noen treff).
Denne videoen viser all backtracking for sammenligning x=xxxxxxxxxxxxxxxxxxxx:
Problemet er at når strengstørrelsen øker, vokser matchingstiden superlineært. Men ting kan bli enda verre hvis det regulære uttrykket er litt modifisert. La oss si at vi hadde det .*.*=.*; (det vil si at det var et bokstavelig semikolon på slutten av mønsteret). For eksempel for å matche et uttrykk som foo=bar;.
Og her ville tilbakesporing være en virkelig katastrofe. Til sammenligning x=x det vil ta 90 trinn, ikke 23. Og det tallet vokser raskt. Å sammenligne x= og 20 x, 5353 trinn er nødvendig. Her er diagrammet. Se på akseverdiene Y sammenlignet med forrige diagram.
Hvis du er interessert, sjekk ut alle 5353 mislykkede samsvarende trinn x=xxxxxxxxxxxxxxxxxxxx и .*.*=.*;
Ved å bruke lat i stedet for grådig matching, kan omfanget av tilbakesporing kontrolleres. Hvis vi endrer det opprinnelige uttrykket til .*?.*?=.*?, til sammenligning x=x det vil ta 11 trinn (ikke 23). Når det gjelder x=xxxxxxxxxxxxxxxxxxxx... Alt fordi ? etter .* forteller motoren å matche et minimum antall tegn før den går videre.
Men late kartlegginger løser ikke helt tilbakesporingsproblemet. Hvis vi erstatter det katastrofale eksempelet .*.*=.*; på .*?.*?=.*?;, vil utførelsestiden forbli den samme. x=x krever fortsatt 555 trinn, og x= og 20 x - 5353.
Det eneste som kan gjøres (foruten å fullstendig omskrive mønsteret for større spesifisitet) er å forlate den regulære uttrykksmotoren med dens tilbakesporingsmekanisme. Dette er hva vi skal gjøre i løpet av de neste ukene.
Løsningen på dette problemet har vært kjent siden 1968, da Kent Thompson skrev en artikkel ("Programmeringsmetoder: Regular Expression Search Algorithm"). Artikkelen beskriver en mekanisme som lar deg konvertere et regulært uttrykk til ikke-deterministiske endelige tilstandsmaskiner, og etter tilstandsendringer i ikke-deterministiske endelige tilstandsmaskiner, bruke en algoritme hvis utførelsestid avhenger lineært av den matchede strengen.
Programmeringsmetoder
Søkealgoritme for regulære uttrykk
Ken Thompson
Bell Telephone Laboratories, Inc., Murray Hill, New JerseyDen beskriver en metode for å søke etter en bestemt streng med tegn i tekst og diskuterer implementeringen av denne metoden i kompilatorform. Kompilatoren tar det regulære uttrykket som kildekode og produserer IBM 7094-programmet som objektkode. Objektprogrammet tar input i form av søketekst og sender ut et signal hver gang en tekststreng matches mot et gitt regulært uttrykk. Artikkelen gir eksempler, problemer og løsninger.
Algoritmen
Tidligere søkealgoritmer resulterte i tilbakesporing hvis et delvis vellykket søk ikke ga resultat.I kompileringsmodus fungerer ikke algoritmen med symboler. Den sender instruksjoner til kompilert kode. Utførelsen er veldig rask - etter å ha sendt data til toppen av gjeldende liste, søker den automatisk etter alle mulige påfølgende tegn i det regulære uttrykket.
Kompilerings- og søkealgoritmen er inkludert i tekstredigeringsprogrammet for tidsdeling som kontekstuelt søk. Selvfølgelig er dette langt fra den eneste anvendelsen av en slik søkeprosedyre. For eksempel brukes en variant av denne algoritmen som et symbolsøk i en tabell i assembler.
Det forutsettes at leseren er kjent med regulære uttrykk og programmeringsspråket IBM 7094.Kompilator
Kompilatoren består av tre trinn som kjører parallelt. Det første trinnet er syntaksfiltrering, som lar bare syntaktisk korrekte regulære uttrykk passere. Dette trinnet setter også inn "·"-operatoren for å matche regulære uttrykk. I det andre trinnet konverteres det regulære uttrykket til postfix-form. På det tredje trinnet opprettes objektkode. De to første stadiene er åpenbare, og vi vil ikke dvele ved dem.
Thompsons artikkel snakker ikke om ikke-deterministiske endelige tilstandsmaskiner, men den forklarer den lineære tidsalgoritmen godt og presenterer et ALGOL-60-program som genererer assembly-språkkode for IBM 7094. Implementeringen er vanskelig, men ideen er veldig enkel.
gjeldende søkesti. Det er representert av et ⊕-ikon med én inngang og to utganger.
Figur 1 viser funksjonene til det tredje kompileringstrinnet når du transformerer et regulært uttrykkseksempel. De tre første tegnene i eksemplet er a, b, c, og hver lager en stabeloppføring S[i] og et NNODE-felt.NNODE til eksisterende kode for å generere det resulterende regulære uttrykket i en enkelt stabeloppføring (se figur 5)
Slik vil et regulært uttrykk se ut .*.*=.*, hvis du forestiller deg det som på bildene fra Thompsons artikkel.
I fig. 0 er det fem tilstander som starter fra 0, og 3 sykluser som starter fra tilstander 1, 2 og 3. Disse tre syklusene tilsvarer tre .* i et regulært uttrykk. 3 ovaler med prikker tilsvarer ett symbol. Oval med skilt = samsvarer med en bokstavelig karakter =. Tilstand 4 er endelig. Hvis vi når det, blir det regulære uttrykket matchet.
For å se hvordan et slikt tilstandsdiagram kan brukes til matching av regulære uttrykk .*.*=.*, skal vi se på strengmatching x=x. Programmet starter fra tilstand 0, som vist i fig. 1.
For at denne algoritmen skal fungere, må tilstandsmaskinen være i flere tilstander samtidig. En ikke-deterministisk endelig maskin vil gjøre alle mulige overganger samtidig.
Før den rekker å lese inndataene, går den inn i begge første tilstander (1 og 2), som vist i fig. 2.
I fig. 2 viser hva som skjer når han ser på den første x в x=x. x kan kartlegge til topppunktet, gå fra tilstand 1 og tilbake til tilstand 1. Eller x kan kartlegge til punktet nedenfor, gå fra tilstand 2 og tilbake til tilstand 2.
Etter å ha matchet den første x в x=x vi er fortsatt i tilstand 1 og 2. Vi kan ikke nå tilstand 3 eller 4 fordi vi trenger en bokstavelig karakter =.
Algoritmen vurderer deretter = в x=x. Som x før den, kan den matches til en av de to øverste løkkene fra tilstand 1 til tilstand 1 eller fra tilstand 2 til tilstand 2, men algoritmen kan matche den bokstavelige = og gå fra tilstand 2 til tilstand 3 (og umiddelbart 4). Dette er vist i fig. 3.
Algoritmen går deretter videre til den siste x в x=x. Fra tilstand 1 og 2 er de samme overgangene mulige tilbake til tilstander 1 og 2. Fra tilstand 3 x kan matche punktet til høyre og gå tilbake til tilstand 3.
På dette stadiet, hver karakter x=x vurdert, og siden vi har nådd tilstand 4, samsvarer det regulære uttrykket med den strengen. Hvert tegn behandles én gang, så denne algoritmen er lineær i lengden på inndatastrengen. Og ingen tilbakesporing.
Åpenbart, etter å ha nådd tilstand 4 (når algoritmen har matchet x=) hele det regulære uttrykket matches, og algoritmen kan avsluttes uten å vurdere det i det hele tatt x.
Denne algoritmen avhenger lineært av størrelsen på inndatastrengen.
Kilde: www.habr.com