For nesten 9 år siden var Cloudflare et lite selskap, og jeg jobbet ikke for dem, jeg var bare en kunde. En måned etter at Cloudflare ble lansert, mottok jeg et varsel om at nettstedet mitt , DNS ser ut til å være nede. Cloudflare har gjort en endring i , og det var en ødelagt DNS.
Jeg skrev umiddelbart til Matthew Prince med emnelinjen «Hvor er DNS-en min?», og han sendte et langt, teknisk svar (), som jeg svarte på:
Fra: John Graham-Cumming
Dato: 7. oktober 2010, 9:14
Emne: Sv: Hvor er DNS-en min?
Til: Matthew PrinceFlott rapport, takk. Jeg ringer definitivt hvis det er noen problemer. Kanskje jeg burde skrive et innlegg om det når du har samlet all den tekniske informasjonen. Jeg tror folk ville satt pris på en åpen og ærlig historie. Spesielt hvis du inkluderte noen grafer som viser hvordan trafikken har vokst siden lanseringen.
Jeg har god overvåking på nettstedet mitt, og jeg mottar en SMS om hver feil. Overvåkingen viser at feilen var fra 13:03:07 til 14:04:12. Tester utføres hvert femte minutt.
Jeg er sikker på at du finner ut av det. Er du sikker på at du ikke trenger din egen mann i Europa? 🙂
Og han svarte:
Fra: Matthew Prince
Dato: 7. oktober 2010, 9:57
Emne: Sv: Hvor er DNS-en min?
Til: John Graham-CummingTakk. Vi har svart 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 der, og nå må jeg skrive åpent om feilen vår, konsekvensene av den og handlingene våre.
Hendelser 2. juli
2. juli implementerte vi en ny regel i Administrerte regler for WAF som på hver CPU-kjerne som behandler HTTP/HTTPS-trafikk i Cloudflares nettverk over hele verden. Vi forbedrer kontinuerlig administrerte regler for WAF som svar på nye sårbarheter og trusler. I mai, for eksempel, hastet vi med å for å beskytte mot en alvorlig sårbarhet i SharePoint. Hele poenget med WAF-en vår er muligheten til å raskt og globalt distribuere regler.
Dessverre inneholdt oppdateringen fra forrige torsdag et regulært uttrykk som brukte for mye av HTTP/HTTPS-CPU-en til backtracking. Dette påvirket kjernefunksjonaliteten vår for proxy, CDN og WAF. Grafen viser at CPU-en for å betjene HTTP/HTTPS-trafikk når nesten 100 % på servere i nettverket vårt.
CPU-bruk på et av tilstedeværelsespunktene under hendelsen
Det som endte opp med å skje var at kundene våre (og kundenes kunder) fikk 502-feilsider på Cloudflare-domener. 502-feilene ble generert av Cloudflares front-end webservere, som fortsatt hadde kjerner tilgjengelig, men som ikke kunne kontakte prosessene som håndterte HTTP/HTTPS-trafikk.
Vi vet hvor mye ulempe dette forårsaket kundene våre. Vi skammer oss fryktelig. Og dette driftsavbruddet 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 på seks år. Den høye CPU-bruken skyldtes en enkelt 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 det er interessant i seg selv (og mer om det nedenfor), var det ikke bare en dårlig regex som forårsaket at Cloudflare gikk ned i 27 minutter. Det tok oss en stund å beskrive hendelsesforløpet som førte til strømbruddet, så vi brukte en stund på å svare. Jeg vil dekke regex-tilbakesporing og hva man kan gjøre med det på slutten av dette innlegget.
Hva skjedde
La oss starte fra begynnelsen. Alle tider her er i UTC.
Klokken 13:42 gjorde en ingeniør i brannmurteamet en liten endring i deteksjonsreglene. ved hjelp av en automatisert prosess. Følgelig ble det opprettet en endringsforespørsel. Vi administrerer slike saker gjennom Jira (skjermbilde nedenfor).
Innen tre minutter dukket den første PagerDuty-siden opp og rapporterte et WAF-problem. Det var en syntetisk test som tester WAF-funksjonalitet (vi har hundrevis av dem) utenfor Cloudflare for å sikre at den fungerte som den skulle. Dette ble raskt etterfulgt av sider som rapporterte feil i andre ende-til-ende Cloudflare-tjenestetester, globale trafikkproblemer, utbredte 3-feil og en rekke rapporter fra våre PoP-er i byer rundt om i verden som indikerte CPU-flaskehalser.
Jeg fikk noen av disse varslene, forlot møtet og var på vei til bordet da løsningssjefen vår fortalte meg 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 et ukjent angrep.
Cloudflares SRE-er er spredt over hele verden og overvåker situasjonen døgnet rundt. Vanligvis handler disse varslene om spesifikke, lokale problemer av begrenset omfang, spores på interne dashbord og løses mange ganger om dagen. Men disse sidene og varslene indikerte noe alvorlig, og SRE-ene økte umiddelbart alvorlighetsgraden til P0 og kontaktet ledelse og systemingeniører.
Våre ingeniører i London lyttet til en forelesning i hovedsalen på det tidspunktet. Forelesningen måtte avbrytes, alle samlet seg i et stort konferanserom, og flere spesialister ble tilkalt. Dette var ikke et typisk problem som SRE kunne håndtere på egenhånd. De riktige spesialistene måtte tilkalles umiddelbart.
Klokken 14 slo vi fast at WAF var problemet, og at det ikke var noe angrep. Ytelsesteamet hentet CPU-data, og det ble tydelig at WAF var synderen. Et annet teammedlem bekreftet denne teorien ved hjelp av strace. Noen andre så i loggene at WAF var problemet. Klokken 00 kom hele teamet til meg da det ble foreslått å bruke en global kill – en mekanisme innebygd i Cloudflare som deaktiverer én komponent over hele verden.
Hvordan vi oppnådde en global fangst for WAF er en annen historie. Det er ikke så enkelt. Vi bruker våre egne produkter, og siden tjenesten vår fungerte ikke, vi kunne ikke autentisere og logge inn på det interne kontrollpanelet (da alt var fikset, fant vi ut at noen teammedlemmer mistet tilgangen på grunn av en sikkerhetsfunksjon som deaktiverer påloggingsinformasjon hvis det interne kontrollpanelet ikke brukes på lenge).
Og vi fikk ikke tilgang til interne tjenester som Jira eller byggesystemet. Vi trengte en midlertidig løsning, som vi ikke brukte så ofte (dette må også jobbes med). Til slutt klarte en ingeniør å deaktivere WAF klokken 14:07, og klokken 14:09 var trafikken og CPU-nivåene tilbake til det normale overalt. Resten av Cloudflares forsvar fungerte som vanlig.
Så satte vi i gang med å gjenopprette WAF. Situasjonen var uvanlig, så vi kjørte negative tester (og spurte oss selv om denne endringen virkelig var problemet) og positive tester (og sørget for at tilbakestillingen fungerte) i én by ved hjelp av separat trafikk, og migrerte de betalende kundene derfra.
Klokken 14:52 var vi sikre på at vi hadde identifisert årsaken og gjort en løsning, og aktivert WAF på nytt.
Hvordan Cloudflare fungerer
Cloudflare har et team av ingeniører dedikert til administrerte regler for WAF. De streber etter å forbedre deteksjonsrater, redusere falske positiver og reagere raskt på nye trusler når de dukker opp. I løpet av de siste 60 dagene har 476 endringsforespørsler for administrerte regler for WAF blitt behandlet (i gjennomsnitt én hver 3. time).
Denne spesifikke endringen måtte implementeres i simuleringsmodus, der reell kundetrafikk passerer gjennom regelen, men ingenting blokkeres. Vi bruker denne modusen til å teste effektiviteten til regler og måle andelen falske positiver og falske negative resultater. Men selv i simuleringsmodus må reglene faktisk kjøres, og i dette tilfellet inneholdt regelen et regulært uttrykk som brukte for mye CPU.
Som du kan se av endringsforespørselen ovenfor, har vi en distribusjonsplan, en tilbakerullingsplan og en lenke til en intern standard driftsprosedyre (SOP) for denne typen distribusjon. SOP-en for regelendringen tillater publisering globalt. Faktisk er ting ganske annerledes hos Cloudflare, og SOP-en dikterer at programvaren først skal sendes ut til en intern PoP (som våre ansatte bruker) for testing og intern bruk, deretter til et lite antall kunder på et isolert sted, deretter til et stort antall kunder, og deretter til verden.
Slik ser det ut. Vi bruker git internt via BitBucket. Ingeniører som jobber med endringer push-kode, som er bygget i TeamCity, og når bygget er godkjent, blir det tildelt anmeldere. Når pull-forespørselen er godkjent, bygges koden og en serie tester kjøres (igjen).
Hvis byggingen og testene fullføres uten problemer, opprettes en endringsforespørsel i Jira, og endringen må godkjennes av riktig leder eller leder. Når den er godkjent, distribueres den til det såkalte «PoP-menasjeriet»: DOG, PIG og (hund, gris og kanarifugl).
DOG PoP er en Cloudflare PoP (som alle andre av byene våre) som kun brukes av Cloudflare-ansatte. PoP for intern bruk lar deg fange opp problemer før løsningen begynner å motta kundetrafikk. Nyttige ting.
Hvis DOG-testen består, går koden videre til PIG-stadiet (forsøkskanin). Dette er Cloudflare PoP, hvor en liten mengde gratis kundetrafikk sendes gjennom den nye koden.
Hvis alt er i orden, går koden til Canary. Vi har tre Canary PoP-er i forskjellige deler av verden. De kjører den nye koden gjennom betalt og gratis kundetrafikk, og dette er den siste sjekken for feil.
Cloudflares programvareutgivelsesprosess
Hvis koden er OK i Canary, lanserer vi den. Det tar noen timer eller dager å gå gjennom alle stadiene – DOG, PIG, Canary, global – avhengig av kodeendringen. På grunn av Cloudflares mangfoldige nettverk og kunder tester vi koden grundig før vi lanserer den globalt til alle kunder. Men WAF følger ikke denne prosessen med vilje, fordi trusler må håndteres raskt.
WAF-trusler
I løpet av de siste årene har trusler økt betydelig i vanlige applikasjoner. Dette skyldes den økte tilgjengeligheten av verktøy for programvaretesting. For eksempel skrev vi nylig om ).
Kilde:
Svært ofte opprettes et konseptbevis som umiddelbart publiseres på Github, slik at teamene som vedlikeholder applikasjonen raskt kan teste den og sørge for at den er tilstrekkelig beskyttet. Cloudflare må derfor kunne reagere på nye angrep så raskt som mulig, slik at kundene har en sjanse til å fikse programvaren sin.
Et godt eksempel på Cloudflares raske respons er utrullingen av beskyttelse mot SharePoint-sårbarheten i mai (Nesten umiddelbart etter at kunngjøringene ble publisert, la vi merke til et stort antall forsøk på å utnytte sårbarheten i kundenes SharePoint-installasjoner. Våre folk overvåker kontinuerlig nye trusler og skriver regler for å beskytte kundene våre.
Regelen som forårsaket problemet på torsdag var utformet for å beskytte mot cross-site scripting (XSS), et angrep som også har blitt mer vanlig de siste årene.
Kilde:
Standardprosedyre for å endre en administrert regel for en WAF er å kjøre kontinuerlig integrasjonstesting (CI) før global distribusjon. Forrige torsdag gjorde vi det og distribuerte reglene. Klokken 13:31 sendte en ingeniør inn en godkjent pull-forespørsel med endringen.
Klokken 13:37 samlet TeamCity reglene, kjørte testene og ga grønt lys. WAF-testpakken tester kjernefunksjonaliteten til WAF og består av et stort antall enhetstester for individuelle funksjoner. Etter enhetstestene testet vi WAF-reglene med et stort antall HTTP-forespørsler. HTTP-forespørslene sjekker hvilke forespørsler som skal blokkeres av WAF (for å avskjære angrepet) og hvilke som kan slippes gjennom (for å unngå å blokkere alt og unngå falske positiver). Vi testet imidlertid ikke for overdreven CPU-bruk, og undersøkelse av loggene til tidligere WAF-bygg viser at testutførelsestiden med regelen ikke økte, og det var vanskelig å mistenke at det ikke var nok ressurser.
Testene var bestått, og TeamCity begynte å distribuere endringen automatisk klokken 13:42.
Quicksilver
WAF-regler er utformet for å håndtere trusler umiddelbart, så vi distribuerer dem ved hjelp av Quicksilver, et distribuert nøkkelverdilager som distribuerer endringer globalt på sekunder. Alle kundene våre bruker denne teknologien når de endrer konfigurasjoner i dashbordet eller via API-et, og det er det som lar oss reagere på endringer så raskt.
Vi har ikke snakket så mye om Quicksilver. Vi pleide å bruke som en globalt distribuert nøkkelverdi-butikk, men den hadde driftsproblemer, så vi skrev vår egen butikk som ble replikert i over 180 byer. Nå, med Quicksilver, kan vi sende endringer i klientkonfigurasjonen, oppdatere WAF-regler og distribuere klientskrevet JavaScript til Cloudflare Workers.
Fra å klikke på en knapp på et dashbord eller kalle et API til å gjøre en konfigurasjonsendring globalt, tar det bare noen få sekunder. Kundene elsker denne hastigheten på oppsettet. Og Workers gir dem nesten umiddelbar global distribusjon. I gjennomsnitt sender Quicksilver ut omtrent 350 endringer per sekund.
Og Quicksilver er veldig rask. I gjennomsnitt nådde vi den 99. persentilen på 2,29 sekunder for å formidle endringer til alle datamaskiner rundt om i verden. Hastighet er vanligvis en god ting. Tross alt, når du aktiverer en funksjon eller tømmer hurtigbufferen, skjer det nesten umiddelbart og overalt. Sending av kode gjennom Cloudflare Workers skjer med samme hastighet. Cloudflare lover kundene sine raske oppdateringer når de trenger dem.
Men i dette tilfellet spilte hastigheten oss en grusom spøk, 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 tilbakesporing for å matche. Den har ingen mekanismer for å beskytte mot uønskede uttrykk. Jeg skal snakke mer om dette og hva vi gjør med det nedenfor.
Før reglene ble distribuert, gikk alt knirkefritt: en pull-forespørsel ble opprettet og godkjent, CI/CD-pipelinen bygde og testet koden, en endringsforespørsel ble sendt inn i henhold til SOP-en som styrer distribusjon og tilbakerulling, og distribusjonen var fullført.
Cloudflare WAF-distribusjonsprosess
Hva gikk galt
Som sagt, distribuerer vi dusinvis av nye WAF-regler hver uke, og vi har flere systemer på plass for å beskytte mot de negative konsekvensene av slike distribusjoner. Og når noe går galt, er det vanligvis en kombinasjon av flere faktorer. Å finne bare én årsak er betryggende, men det er ikke alltid sant. Her er faktorene som til sammen forårsaket at HTTP/HTTPS-tjenesten vår mislyktes.
- En ingeniør skrev et regulært uttrykk som kunne føre til overdreven .
- En funksjon som kunne ha forhindret at det regulære uttrykket brukte for mye CPU, ble feilaktig fjernet under en WAF-refaktorering noen uker tidligere – refaktoreringen var nødvendig for å få WAF til å bruke mindre ressurser.
- Motoren for regulære uttrykk hadde ingen kompleksitetsgarantier.
- Testpakken klarte ikke å oppdage overdreven CPU-bruk.
- SOP-prosedyren tillater global distribusjon av ikke-hastende regelendringer uten en flertrinnsprosess.
- Tilbakerullingsplanen krevde at en full WAF-bygg ble kjørt to ganger, noe som er tidkrevende.
- Det første varselet om globale trafikkproblemer kom for sent.
- Vi var trege med å oppdatere statussiden.
- Vi hadde problemer med å få tilgang til systemene på grunn av en feil, og løsningsprosedyren var ikke godt utviklet.
- SRE-ingeniører mistet tilgangen til noen systemer fordi legitimasjonen deres utløp av sikkerhetsmessige årsaker.
- Kundene våre hadde ikke tilgang til Cloudflare-dashbordet eller API-et fordi de går gjennom en Cloudflare-region.
Hva har endret seg siden forrige torsdag
Først har vi stoppet alt arbeid med utgivelser for WAF fullstendig, og vi gjør følgende:
- Gjeninnfører beskyttelsen mot CPU-overforbruk som vi fjernet. (Ferdig)
- Manuell kontroll av alle 3868 regler i administrerte regler for WAF for å finne og fikse andre potensielle tilfeller av overdreven tilbakesporing. (Kontroller fullført)
- Inkludert ytelsesprofilering for alle regler i testpakken. (Forventet: 19. juli)
- Går over til motoren for regulære uttrykk eller — begge gir kjøretidsgarantier. (Forventet: 31. juli)
- Vi skriver om standard operasjonsoperasjonen (SOP) for å distribuere regler i etapper, som annen programvare i Cloudflare, men har fortsatt muligheten til å utføre en global nøddistribusjon hvis angrep allerede har begynt.
- Vi utvikler muligheten til raskt å få Cloudflare-dashbordet og API-et ut av Cloudflare-regionen.
- Automatiser sideoppdatering .
På lang sikt beveger vi oss bort fra Lua WAF som jeg skrev for noen år siden. Vi flytter WAF til På denne måten vil WAF bli raskere og få et ekstra beskyttelsesnivå.
Konklusjon
Dette driftsavbruddet var en plage for oss og kundene våre. Vi reagerte raskt for å fikse situasjonen, og jobber for tiden med å fikse feilene i prosessene som forårsaket driftsavbruddet, samt å grave dypere for å beskytte mot potensielle fremtidige problemer med regulære uttrykk ved å migrere til ny teknologi.
Vi beklager dette driftsavbruddet på det sterkeste og ber om unnskyldning overfor kundene våre. Vi håper at disse endringene vil sikre at dette ikke skjer igjen.
Tillegg: Gå tilbake til regulære uttrykk
For å forstå hvordan uttrykket:
(?:(?:"|'|]|}||d
(?:nan|infinity|true|false|null|undefined|symbol|math)|`|-
|+)+[)]*;?((?:s|-|~|!|{}||||+)*.*(?:.*=.*)))spiste alle CPU-ressursene, må du vite litt om hvordan standardmotoren for regulære uttrykk fungerer. Problemet her ligger i mønsteret .*(?:.*=.*). (?: og den tilsvarende ) — dette er ikke en fangende gruppe (det vil si at uttrykket i parentes er gruppert som et enkelt uttrykk).
I sammenheng med overdrevent CPU-forbruk kan dette mønsteret beskrives som .*.*=.*I denne formen ser mønsteret unødvendig komplekst ut. Men enda viktigere er det at i den virkelige verden kan slike uttrykk (som komplekse uttrykk i WAF-regler) som ber motoren om å matche et fragment etterfulgt av et annet fragment, føre til katastrofal tilbakesporing. Her er hvorfor.
I regulært uttrykk . betyr at du må finne ett matchende tegn, .* — match null eller flere tegn grådig, det vil si ved å fange så mange tegn som mulig, slik at .*.*=.* betyr at finn null eller flere tegn, deretter finn null eller flere tegn, finn bokstaveligen = tegn, finn null eller flere tegn.
La oss ta en teststreng x=xDet tilsvarer uttrykket .*.*=.*. .*.* før likhetstegnet tilsvarer det første x (en av gruppene .* соответствует x, og den andre – null tegn). .* etter = samsvarer med den siste x.
Denne sammenligningen krever 23 trinn. Den første gruppen .* в .*.*=.* opptrer «grådig» og matcher hele linjen x=xMotoren går videre til neste gruppe. .*Vi har ingen flere figurer å matche, så den andre gruppen .* samsvarer med null tegn (dette er tillatt). Deretter beveger motoren seg til skiltet =Det finnes ingen flere symboler (første gruppe) .* brukte hele uttrykket x=x), forekommer ingen samsvar.
Og her går motoren for regulære uttrykk tilbake til begynnelsen. Den går til den første gruppen. .* og sammenligner det с x= (i stedet x=x), og tar deretter fatt på den andre gruppen .*Andre gruppe .* sammenlignes med den andre x, og vi har ingen symboler igjen. Og når motoren når = в .*.*=.*, ingenting fungerer. Og han går tilbake igjen.
Denne gangen gruppen .* passer fortsatt x=, men den andre gruppen .* ikke mer x, og null tegn. Motoren prøver å finne et bokstavelig tegn = i mønsteret .*.*=.*, men det fungerer ikke (tross alt har den første gruppen allerede tatt den) .*). Og han går tilbake igjen.
Denne gangen den første gruppen .* tar bare den første x. Men den andre gruppen .* "grådig" fangster =xHar du gjettet hva som vil skje? Motoren prøver å matche det bokstavelige =, mislykkes og gjør en ny tilbakesporing.
Den første gruppen av .* matcher fortsatt den første xAndre .* tar bare =Motoren kan selvfølgelig ikke samsvare med det bokstavelige =, fordi den andre gruppen allerede har gjort det .*... Og igjen går vi tilbake. Og her prøver vi å finne en matchende streng med tre tegn!
Som et resultat, den første gruppen .* samsvarer bare med den første x, den andre .* — med null tegn, og motoren samsvarer endelig med bokstavelig = i uttrykket с = på rad. Så den siste gruppen .* sammenlignes med den siste x.
23 trinn bare for x=xSe 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=xxDet er 33 trinn. Og hvis x=xxx? 45. Avhengigheten er ikke lineær. Grafen viser en sammenligning av x=x til x=xxxxxxxxxxxxxxxxxxxx (20 x etter =Hvis vi har 20 x etter =, utfører motoren matchingen i 555 trinn! (Dessuten, hvis vi har mistet x= og linjen består av bare 20 x, motoren vil ta 4067 skritt for å finne ut at det ikke er noen treff).
Denne videoen viser all tilbakesporingen for sammenligning x=xxxxxxxxxxxxxxxxxxxx:
Problemet er at matchingstiden øker superlineært etter hvert som strengstørrelsen øker. Men ting kan bli enda verre hvis det regulære uttrykket endres litt. Anta at vi hadde .*.*=.*; (det vil si at det var et semikolon på slutten av mønsteret). For eksempel, for å matche et uttrykk som foo=bar;.
Og her ville det å gå tilbake være en skikkelig katastrofe. Til sammenligning x=x det vil ta 90 trinn i stedet for 23. Og det tallet vokser raskt. For å sammenligne x= og 20 x, 5353 trinn er nødvendige. Her er grafen. Se på verdiene på aksen Y sammenlignet med forrige graf.
Hvis du er interessert, sjekk ut alle 5353 XNUMX trinnene for mislykket matching x=xxxxxxxxxxxxxxxxxxxx и .*.*=.*;
Ved å bruke lat snarere enn 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=xxxxxxxxxxxxxxxxxxxxAlt fordi ? etter .* forteller motoren at den må matche et minimum antall tegn før den går videre.
Men lat matching løser ikke problemet med tilbakesporing fullstendig. Hvis vi erstatter det katastrofale eksemplet .*.*=.*; på .*?.*?=.*?;, vil utførelsestiden forbli den samme. x=x krever fortsatt 555 trinn, men x= og 20 x - 5353.
Det eneste vi kan gjøre (bortsett fra å omskrive mønsteret fullstendig, for å være mer spesifikk) er å forlate motoren for regulære uttrykk med tilbakesporingsmekanismen. Det er det 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: Søkealgoritme for regulære uttrykk"). Artikkelen beskriver en mekanisme som tillater transformering av et regulært uttrykk til ikke-deterministiske endelige automater, og etter tilstandsendringer i ikke-deterministiske endelige automater, ved bruk av en algoritme hvis utførelsestid er lineært avhengig av den samsvarende strengen.
Programmeringsmetoder
Søkealgoritme for regulære uttrykk
Ken Thompson
Bell Telephone Laboratories, Inc., Murray Hill, N.J.Denne artikkelen beskriver en metode for å søke etter en spesifikk tegnstreng i tekst og diskuterer implementeringen av denne metoden i form av en kompilator. Kompilatoren tar et regulært uttrykk som kildekode og produserer et program for IBM 7094 som objektkode. Objektprogrammet tar imot input i form av tekst for å søke etter og piper når en tekststreng samsvarer med det gitte regulære uttrykket. Eksempler, problemer og løsninger gis.
Algoritmen
Tidligere søkealgoritmer resulterte i tilbakesporing hvis et delvis vellykket søk ikke ga noen resultater.I kompileringsmodus fungerer ikke algoritmen med symboler. Den sender instruksjoner til den kompilerte koden. Utførelsen er veldig rask – etter at dataene er sendt til toppen av gjeldende liste, søker den automatisk etter alle mulige påfølgende symboler i det regulære uttrykket.
Kompilerings- og søkealgoritmen er inkludert i den tidsdelte teksteditoren som kontekstsøk. Dette er selvsagt langt fra den eneste anvendelsen av en slik søkeprosedyre. For eksempel brukes en variant av denne algoritmen som et symboltabellsøk i assembler.
Det forutsettes at leseren er kjent med regulære uttrykk og programmeringsspråket IBM 7094.Kompilator
Kompilatoren består av tre parallelle trinn. Det første trinnet er syntaksfiltrering, som bare sender syntaktisk korrekte regulære uttrykk. Dette trinnet setter også inn "·"-operatoren for samsvar med regulære uttrykk. Det andre trinnet konverterer det regulære uttrykket til postfix-form. Det tredje trinnet oppretter objektkoden. De to første trinnene er åpenbare, og vi vil ikke dvele ved dem.
Thompsons artikkel drøfter ikke ikke-deterministiske endelige automater, men den forklarer den lineære tidsalgoritmen godt og gir et ALGOL-60-program som produserer assemblerkode for IBM 7094. Implementeringen er vanskelig, men ideen er veldig enkel.
gjeldende søkesti. Den er representert av ⊕-ikonet med én inngang og to utganger.
Figur 1 viser funksjonene til det tredje kompileringstrinnet når man transformerer det vanlige uttrykket i eksemplet. De tre første tegnene i eksemplet er a, b, c, og hvert av dem produserer en stakkoppføring S[i] og et felt NNODE.NNODE til den eksisterende koden for å generere det endelige regulære uttrykket i en enkelt stakkoppføring (se figur 5)
Slik ville det regulære uttrykket se ut .*.*=.*, hvis du forestiller deg det slik som på bildene fra Thompsons artikkel.
I figur 0 er det fem tilstander som starter fra 0 og 3, og sykluser som starter fra tilstand 1, 2 og 3. Disse tre syklusene tilsvarer de tre .* i et regulært uttrykk. 3 ovaler med prikker tilsvarer ett tegn. En oval med et fortegn = samsvarer med et bokstavelig tegn =Tilstand 4 er den endelige tilstanden. Hvis vi har nådd den, har det regulære uttrykket blitt matchet.
For å se hvordan et slikt tilstandsdiagram kan brukes til samsvar med regulære uttrykk .*.*=.*, vi skal se på strengmatching x=xProgrammet starter fra tilstand 0, som vist i figur 1.
For at denne algoritmen skal fungere, må tilstandsmaskinen være i flere tilstander samtidig. En ikke-deterministisk tilstandsmaskin vil foreta alle mulige overganger samtidig.
Før den i det hele tatt har rukket å lese inngangsdataene, går den inn i begge de første tilstandene (1 og 2), som vist i figur 2.
Figur 2 viser hva som skjer når han ser på den første x в x=x. x kan matche toppunktet ved å gå fra tilstand 1 og tilbake til tilstand 1. Eller x kan matche punktet nedenfor ved å gå fra tilstand 2 og tilbake til tilstand 2.
Etter å ha sammenlignet 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 et bokstavelig symbol =.
Algoritmen vurderer deretter = в x=xSom med x før, kan den matches mot en av de to øverste syklusene med en overgang fra tilstand 1 til tilstand 1 eller fra tilstand 2 til tilstand 2, men algoritmen kan matche en litteral = og gå fra tilstand 2 til tilstand 3 (og umiddelbart til 4). Dette er vist i figur 3.
Så går algoritmen videre til den siste x в x=xFra tilstand 1 og 2 er de samme overgangene mulige tilbake til tilstand 1 og 2. Fra tilstand 3 x kan matche punktet til høyre og gå tilbake til tilstand 3.
På dette stadiet, hvert symbol x=x vurdert, og når 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.
Det er åpenbart at etter å ha nådd tilstand 4 (når algoritmen har samsvart x=) hele det regulære uttrykket samsvarer, og algoritmen kan avslutte uten å ta hensyn til noen x.
Denne algoritmen avhenger lineært av størrelsen på inputstrengen.
Kilde: www.habr.com
