For næsten 9 år siden var Cloudflare et lille firma, og jeg arbejdede ikke for det, jeg var bare en kunde. En måned efter lanceringen af Cloudflare modtog jeg en meddelelse om, at min hjemmeside DNS ser ikke ud til at virke. Cloudflare har lavet en ændring til , og der var en brudt DNS.
Jeg skrev straks til Matthew Prince med titlen "Hvor er min DNS?", og han sendte et langt svar tilbage fuld af tekniske detaljer (), hvortil jeg svarede:
Fra: John Graham-Cumming
Dato: 7. oktober 2010, 9:14
Emne: Re: Hvor er min DNS?
Til: Matthew PrinceFed rapport, tak. Jeg ringer helt sikkert, hvis der er problemer. Det er nok værd at skrive et indlæg om dette, når du har samlet alle de tekniske oplysninger. Jeg tror, folk vil nyde en åben og ærlig historie. Især hvis du vedhæfter grafer til det for at vise, hvordan trafikken er vokset siden lanceringen.
Jeg har god overvågning på min side, og jeg modtager en sms om hver fejl. Overvågning viser, at fejlen opstod fra 13:03:07 til 14:04:12. Testene udføres hvert femte minut.
Jeg er sikker på, at du vil finde ud af det. Er du sikker på, at du ikke har brug for din egen person i Europa? 🙂
Og han svarede:
Fra: Matthew Prince
Dato: 7. oktober 2010, 9:57
Emne: Re: Hvor er min DNS?
Til: John Graham-CummingTak skal du have. Vi svarede alle, der skrev. Jeg er på vej til kontoret nu, og vi skriver noget på bloggen eller fastgør et officielt indlæg på vores opslagstavle. Jeg er helt enig, ærlighed er alt.
Nu er Cloudflare en rigtig stor virksomhed, jeg arbejder for den, og nu skal jeg skrive åbent om vores fejl, dens konsekvenser og vores handlinger.
Begivenheder den 2. juli
Den 2. juli udrullede vi en ny regel i Managed Rules for WAF'er på hver processorkerne, der behandler HTTP/HTTPS-trafik på Cloudflare-netværket verden over. Vi forbedrer konstant administrerede regler for WAF'er som reaktion på nye sårbarheder og trusler. I maj skyndte vi os f.eks for at beskytte mod en alvorlig sårbarhed i SharePoint. Hele pointen med vores WAF er evnen til hurtigt og globalt at implementere regler.
Desværre indeholdt sidste torsdags opdatering et regulært udtryk, der spildte for mange HTTP/HTTPS CPU-ressourcer på backtracking. Vores kerne proxy-, CDN- og WAF-funktioner led som følge heraf. Grafen viser, at processorressourcer til at betjene HTTP/HTTPS-trafik når næsten 100 % på servere i vores netværk.
CPU-brug på ét sted under en hændelse
Som et resultat endte vores kunder (og vores kunders klienter) med en 502 fejlside i Cloudflare-domæner. 502-fejl blev genereret af Cloudflare front-end-webservere, der stadig havde frie kerner, men som ikke var i stand til at kommunikere med processer, der håndterede HTTP/HTTPS-trafik.
Vi ved, hvor mange gener dette har givet vores kunder. Vi skammer os frygtelig. Og denne fejl forhindrede os i effektivt at håndtere hændelsen.
Hvis du var en af disse kunder, var du sandsynligvis bange, vred og ked af det. Desuden har vi ikke haft en . Det høje CPU-forbrug skyldtes én WAF-regel med et dårligt formuleret regulært udtryk, der resulterede i overdreven backtracking. Her er det skyldige udtryk: (?:(?:"|'|]|}||d|(?:nan|infinity|true|false|null|undefined|symbol|math)|`|-|+)+[)]*;?((?:s|-|~|!|{}||||+)*.*(?:.*=.*)))
Selvom dette er interessant i sig selv (og jeg vil tale om det mere detaljeret nedenfor), var Cloudflare-tjenesten nede i 27 minutter, ikke kun på grund af et dårligt regulært udtryk. Det tog os et stykke tid at beskrive rækkefølgen af begivenheder, der førte til fejlen, så vi var langsomme til at reagere. Til sidst i indlægget vil jeg beskrive backtracking i et regulært udtryk og fortælle dig, hvad du skal gøre med det.
Hvad skete der
Lad os starte i rækkefølge. Alle tider her er i UTC.
Klokken 13 lavede en ingeniør på firewall-teamet en lille ændring af registreringsreglerne ved hjælp af en automatisk proces. Derfor blev der oprettet en ændringsanmodningsbillet. Vi administrerer sådanne billetter gennem Jira (skærmbillede nedenfor).
Efter 3 minutter dukkede den første side af PagerDuty op, der rapporterede et problem med WAF. Dette var en syntetisk test, der tester funktionaliteten af WAF'er (vi har hundredvis af dem) uden for Cloudflare for at overvåge normal drift. Dette blev umiddelbart efterfulgt af sider med advarsler om andre Cloudflare end-to-end-servicetests, der mislykkedes, globale trafikproblemer, udbredte 502-fejl og et væld af rapporter fra vores Points of Presence (PoP) i byer rundt om i verden, der indikerede en mangel af CPU-ressourcer.
Jeg modtog flere af disse advarsler, stormede ud af et møde og var på vej til bordet, da lederen af vores løsningsudviklingsafdeling sagde, at vi havde mistet 80 % af vores trafik. Jeg løb til vores SRE-ingeniører, som allerede arbejdede på problemet. Først troede vi, at det var en form for ukendt angreb.
Cloudflare SRE-ingeniører er spredt rundt i verden og overvåger situationen døgnet rundt. Disse advarsler giver dig typisk besked om specifikke lokale problemer af begrænset omfang, spores på interne dashboards og løses flere gange om dagen. Men disse sider og meddelelser indikerede noget virkelig alvorligt, og SRE-ingeniører erklærede straks sværhedsgraden P0 og kontaktede ledelses- og systemingeniører.
Vores London-ingeniører lyttede til et foredrag i hovedsalen i det øjeblik. Foredraget måtte afbrydes, alle samledes i et stort mødelokale, og flere specialister blev tilkaldt. Dette var ikke et typisk problem, som SRE'er selv kunne håndtere. Det hastede med at inddrage de rigtige specialister.
Klokken 14:00 konstaterede vi, at problemet var med WAF, og der var intet angreb. Ydelsesteamet trak CPU-dataene, og det blev klart, at WAF var skylden. En anden medarbejder bekræftede denne teori ved hjælp af strace. En anden så i loggene, at der var et problem med WAF. Klokken 14:02 kom hele holdet til mig, da det blev foreslået at bruge global kill, en mekanisme indbygget i Cloudflare, der lukker en komponent ned på verdensplan.
Hvordan vi lavede global drab for WAF er en anden historie. Så enkelt er det ikke. Vi bruger vores egne produkter, og siden vores service virkede ikke, vi kunne ikke godkende og logge ind på det interne kontrolpanel (da alt var rettet, fandt vi ud af, at nogle teammedlemmer havde mistet adgangen på grund af en sikkerhedsfunktion, der deaktiverer legitimationsoplysninger, hvis det interne kontrolpanel ikke bruges til en lang tid).
Og vi kunne ikke komme til vores interne tjenester, såsom Jira eller byggesystemet. Vi havde brug for en løsningsmekanisme, som vi brugte sjældent (denne skal også løses). Endelig lykkedes det en ingeniør at deaktivere WAF kl. 14:07, og kl. 14:09 var trafik- og CPU-niveauet tilbage til det normale overalt. Resten af Cloudflares beskyttelsesmekanismer fungerede som normalt.
Så gik vi i gang med at genoprette WAF. Situationen var ud over det sædvanlige, så vi kørte negative tests (for at spørge os selv, om ændringen virkelig var problemet) og positive tests (så vi sikrede, at tilbagerulningen virkede) i én by ved at bruge separat trafik og overføre betalende kunder derfra.
14:52 var vi overbevist om, at vi forstod årsagen og lavede en rettelse og aktiverede WAF igen.
Sådan fungerer Cloudflare
Cloudflare har et team af ingeniører dedikeret til at administrere regler for WAF'er. De stræber efter at forbedre detektionsraterne, reducere falske positiver og reagere hurtigt på nye trusler, efterhånden som de dukker op. I de sidste 60 dage har der været behandlet 476 ændringsanmodninger for administrerede regler for WAF (i gennemsnit én hver 3. time).
Denne særlige ændring skulle implementeres i simuleringstilstand, hvor reel klienttrafik passerer gennem reglen, men intet er blokeret. Vi bruger denne tilstand til at teste effektiviteten af reglerne og måle de falske positive og falske negative satser. Men selv i simuleringstilstand skal reglerne faktisk udføres, og i dette tilfælde indeholdt reglen et regulært udtryk, der forbrugte for mange processorressourcer.
Som du kan se fra ændringsanmodningen ovenfor, har vi en implementeringsplan, en rollback-plan og et link til en intern standarddriftsprocedure (SOP) for denne type implementering. SOP'en for ændring af en regel tillader den at blive offentliggjort globalt. Faktisk, hos Cloudflare gøres tingene helt anderledes, og SOP'en dikterer, at vi først sender softwaren til test og intern brug til et internt tilstedeværelse (PoP) (som vores medarbejdere bruger), derefter til et lille antal kunder i et isoleret sted, så til et stort antal kunder, og først derefter til hele verden.
Sådan ser det ud. Vi bruger git internt via BitBucket. Ingeniører, der arbejder med ændringer, indsender kode, som er bygget til TeamCity, og når buildet er bestået, tildeles anmeldere. Når en pull-anmodning er godkendt, samles koden, og der køres en række tests (igen).
Hvis opbygningen og testene gennemføres med succes, oprettes en ændringsanmodning i Jira, og den relevante leder eller lead skal godkende ændringen. Efter godkendelse sker indsættelsen i det såkaldte "PoP-menageri": HUND, SVIN og (hund, gris og kanariefugl).
DOG PoP er en Cloudflare PoP (som alle andre af vores byer), der kun bruges af Cloudflares medarbejdere. PoP til intern brug giver dig mulighed for at fange problemer, før kundetrafik begynder at strømme ind i løsningen. Nyttig ting.
Hvis HUND-testen er vellykket, flytter koden til PIG-stadiet (marsvin). Dette er Cloudflare PoP, hvor en lille mængde gratis kundetrafik flyder gennem ny kode.
Hvis alt er godt, går koden ind på Canary. Vi har tre Canary PoPs i forskellige dele af verden. I dem passerer trafikken af betalte og gratis klienter gennem den nye kode, og dette er den sidste kontrol for fejl.
Softwareudgivelsesproces hos Cloudflare
Hvis koden er ok på Canary, frigiver vi den. Det tager flere timer eller dage at gennemgå alle stadierne - HUND, SVIN, Kanariefugle, hele verden, afhængig af kodeændringen. På grund af mangfoldigheden af Cloudflares netværk og klienter tester vi koden grundigt, før vi frigiver den globalt til alle klienter. Men WAF følger ikke specifikt denne proces, fordi trusler skal reageres hurtigt.
WAF trusler
I løbet af de sidste par år har der været en betydelig stigning i trusler i almindelige applikationer. Dette skyldes den større tilgængelighed af softwaretestværktøjer. For eksempel skrev vi for nylig om ).
Kilde:
Meget ofte oprettes et proof of concept og offentliggøres straks på Github, så de teams, der vedligeholder applikationen, hurtigt kan teste den og sikre, at den er tilstrækkeligt sikret. Derfor har Cloudflare brug for muligheden for at reagere på nye angreb så hurtigt som muligt, så kunderne har mulighed for at rette deres software.
Et godt eksempel på Cloudflares hurtige reaktion er implementeringen af SharePoint sårbarhedsbeskyttelse i maj (). Næsten umiddelbart efter meddelelserne blev offentliggjort, bemærkede vi et stort antal forsøg på at udnytte sårbarheden i vores kunders SharePoint-installationer. Vores fyre overvåger konstant nye trusler og skriver regler for at beskytte vores kunder.
Reglen, der forårsagede problemet i torsdags, skulle beskytte mod cross-site scripting (XSS). Sådanne angreb er også blevet meget hyppigere i de senere år.
Kilde:
Standardproceduren for at ændre en administreret regel for en WAF er at udføre kontinuerlig integration (CI) test før global implementering. Sidste torsdag gjorde vi dette og udrullede reglerne. Klokken 13 indsendte en ingeniør en godkendt pull-anmodning med en ændring.
13:37 samlede TeamCity reglerne, kørte test og gav grønt lys. WAF testsuiten tester WAF'ens kernefunktionalitet og består af et stort antal enhedstests for individuelle funktioner. Efter enhedstests testede vi reglerne for WAF ved hjælp af et stort antal HTTP-anmodninger. HTTP-anmodninger kontrollerer, hvilke anmodninger der skal blokeres af WAF (for at opsnappe angrebet), og hvilke der kan tillades igennem (for ikke at blokere alt og undgå falske positiver). Men vi testede ikke for overdreven CPU-brug, og en undersøgelse af logfilerne for tidligere WAF-builds viser, at udførelsestiden for regeltesten ikke steg, og det var svært at mistænke, at der ikke ville være nok ressourcer.
Testene bestod, og TeamCity begyndte automatisk at implementere ændringen kl. 13:42.
Quicksilver
WAF-reglerne fokuserer på øjeblikkelig afhjælpning af trusler, så vi implementerer dem ved hjælp af Quicksilvers distribuerede nøgleværdilager, som udbreder ændringer globalt på få sekunder. Alle vores kunder bruger denne teknologi, når de ændrer konfigurationen i dashboardet eller via API'et, og det er takket være den, at vi reagerer lynhurtigt på ændringer.
Vi har ikke talt meget om Quicksilver. Tidligere brugte vi som en globalt distribueret butik med nøgleværdier, men der var driftsproblemer med den, og vi skrev vores egen butik, replikeret i mere end 180 byer. Vi bruger nu Quicksilver til at skubbe konfigurationsændringer til klienter, opdatere WAF-regler og distribuere JavaScript-kode skrevet af klienter til Cloudflare Workers.
Det tager kun et par sekunder fra at klikke på en knap på et dashboard eller kalde en API til at foretage en konfigurationsændring på verdensplan. Kunderne elskede denne opsætningshastighed. Og Workers giver dem næsten øjeblikkelig global softwareimplementering. I gennemsnit udbreder Quicksilver omkring 350 ændringer i sekundet.
Og Quicksilver er meget hurtig. I gennemsnit opnåede vi den 99. percentil på 2,29 sekunder for at udbrede ændringer til alle computere verden over. Hastighed er normalt en god ting. Når du aktiverer en funktion eller rydder cachen, sker det jo næsten øjeblikkeligt og overalt. Afsendelse af kode gennem Cloudflare Workers sker med samme hastighed. Cloudflare lover sine kunder hurtige opdateringer på det rigtige tidspunkt.
Men i dette tilfælde spillede hastighed en grusom joke med os, og reglerne ændrede sig overalt i løbet af få sekunder. Du har måske bemærket, at WAF-koden bruger Lua. Cloudflare bruger Lua flittigt i produktion og detaljer vi er . Lua WAF bruger internt og anvender backtracking til matchning. Den har ingen mekanismer til at beskytte mod udtryk, der kommer ud af kontrol. Nedenfor vil jeg fortælle mere om dette, og hvad vi gør ved det.
Før reglerne blev implementeret, gik alt glat: pull-anmodningen blev oprettet og godkendt, CI/CD-pipelinen indsamlede og testede koden, ændringsanmodningen blev indsendt i henhold til SOP'en, der styrer implementering og rollback, og implementeringen blev fuldført.
Cloudflare WAF-implementeringsproces
Noget gik galt
Som jeg sagde, implementerer vi snesevis af nye WAF-regler hver uge, og vi har mange systemer på plads til at beskytte mod de negative konsekvenser af en sådan implementering. Og når noget går galt, er det som regel en kombination af flere omstændigheder på én gang. Hvis du kun finder én grund, er dette selvfølgelig betryggende, men det er ikke altid sandt. Disse er årsagerne, der tilsammen førte til svigt af vores HTTP/HTTPS-tjeneste.
- En ingeniør skrev et regulært udtryk, der kunne resultere i overdreven .
- En funktion, der kunne have forhindret det regulære udtryk i at spilde for meget CPU, blev ved en fejl fjernet i en refactoring af WAF flere uger tidligere - refaktoreringen var nødvendig for at få WAF til at forbruge færre ressourcer.
- Den regulære udtryksmotor havde ingen kompleksitetsgarantier.
- Testpakken kunne ikke registrere for stort CPU-forbrug.
- SOP'et tillader ikke-hastende regelændringer at blive udrullet globalt uden en flertrinsproces.
- Tilbageføringsplanen krævede at køre en fuld WAF build to gange, hvilket tog lang tid.
- Den første alarm om globale trafikproblemer blev udløst for sent.
- Vi tog et stykke tid at opdatere statussiden.
- Vi havde problemer med at få adgang til systemer på grund af en fejl, og bypass-proceduren var ikke veletableret.
- SRE-ingeniører mistede adgangen til nogle systemer, fordi deres legitimationsoplysninger udløb på grund af sikkerhedsmæssige årsager.
- Vores kunder havde ikke adgang til Cloudflares dashboard eller API, fordi de går gennem en Cloudflare-region.
Hvad har ændret sig siden sidste torsdag
For det første stoppede vi fuldstændigt alt arbejde med udgivelser til WAF og gør følgende:
- Vi genindfører CPU-overforbrugsbeskyttelsen, som vi fjernede. (Parat)
- Manuel kontrol af alle 3868 regler i de administrerede regler for WAF for at finde og rette andre potentielle tilfælde af overdreven tilbagesporing. (Bekræftelse afsluttet)
- Vi inkluderer præstationsprofilering for alle regler i testsættet. (Forventet: 19. juli)
- Skift til en regulært udtryksmotor eller - begge giver driftstidsgarantier. (Forventet: 31. juli)
- Vi omskriver SOP'en for at implementere regler i etaper, ligesom anden software i Cloudflare, men samtidig have mulighed for at nøde global implementering, hvis angreb allerede er begyndt.
- Vi udvikler muligheden for omgående at fjerne Cloudflare-dashboardet og API fra Cloudflare-regionen.
- Automatisering af sideopdateringer .
På lang sigt bevæger vi os væk fra Lua WAF, jeg skrev for et par år siden. Flytter WAF til . På denne måde vil WAF være hurtigere og modtage et ekstra niveau af beskyttelse.
Konklusion
Denne fejl skabte problemer for os og vores kunder. Vi handlede hurtigt for at rette op på situationen og arbejder nu på fejlene i de processer, der forårsagede nedbruddet, samt graver endnu dybere for at sikre os mod potentielle problemer med regulære udtryk i fremtiden, når vi migrerer til ny teknologi.
Vi er meget flove over dette afbrydelse og undskylder over for vores kunder. Vi håber, at disse ændringer vil sikre, at noget som dette ikke sker igen.
Ansøgning. Backtracking af regulære udtryk
For at forstå hvordan udtrykket:
(?:(?:"|'|]|}||d
(?:nan|infinity|true|false|null|undefined|symbol|math)|`|-
|+)+[)]*;?((?:s|-|~|!|{}||||+)*.*(?:.*=.*)))spiste alle CPU-ressourcerne, skal du vide lidt om, hvordan standard-regulære udtryksmotoren fungerer. Problemet her er mønsteret .*(?:.*=.*). (?: og tilsvarende ) er en ikke-fangende gruppe (det vil sige, at udtrykket i parentes er grupperet som et enkelt udtryk).
I sammenhæng med overdreven CPU-forbrug kan dette mønster beskrives som .*.*=.*. I denne form ser mønsteret unødvendigt komplekst ud. Men endnu vigtigere, i den virkelige verden kan udtryk (som komplekse udtryk i WAF-regler), der beder motoren om at matche et fragment efterfulgt af et andet fragment, føre til katastrofal tilbagesporing. Og det er derfor.
I regulært udtryk . betyder, at du skal matche én karakter, .* - match nul eller flere tegn "grådigt", det vil sige at fange et maksimum af tegn, så .*.*=.* betyder match nul eller flere tegn, match derefter nul eller flere tegn, find bogstavet = tegn, match nul eller flere tegn.
Lad os tage prøvelinjen x=x. Det svarer til udtrykket .*.*=.*. .*.* før lighedstegnet matcher det første x (en af grupperne .* svarer til x, og den anden - nul tegn). .* efter = kampe sidst x.
Denne sammenligning kræver 23 trin. Første gruppe .* в .*.*=.* handler grådigt og matcher hele strengen x=x. Motoren flytter til næste gruppe .*. Vi har ikke flere karakterer at matche, så den anden gruppe .* matcher nul tegn (dette er tilladt). Så bevæger motoren sig til skiltet =. Der er ikke flere symboler (første gruppe .* brugte hele udtrykket x=x), ingen sammenligning forekommer.
Og så vender den regulære udtryksmotor tilbage til begyndelsen. Han går videre til den første gruppe .* og sammenligner det с x= (i stedet x=x), og tager derefter imod den anden gruppe .*. Anden gruppe .* sammenlignes med den anden x, og vi har igen ingen tegn tilbage. Og når motoren når igen = в .*.*=.*, intet virker. Og han går tilbage igen.
Denne gang gruppen .* stadig matcher x=, men den anden gruppe .* ikke mere x, og nul tegn. Motoren forsøger at finde en bogstavelig karakter = i mønsteret .*.*=.*, men kommer ikke ud (trods alt har den første gruppe allerede besat det .*). Og han går tilbage igen.
Denne gang den første gruppe .* tager kun det første x. Men den anden gruppe .* "grådigt" fanger =x. Har du allerede gættet, hvad der vil ske? Motoren forsøger at matche det bogstavelige =, fejler og laver endnu et tilbagespor.
Den første gruppe af .* matcher stadig den første x. Anden .* tager kun =. Motoren kan selvfølgelig ikke matche det bogstavelige =, fordi den anden gruppe allerede har gjort dette .*. Og igen på vej tilbage. Og vi forsøger at matche en streng med tre karakterer!
Som et resultat, den første gruppe .* matcher kun den første x, anden .* - med nul tegn, og motoren matcher endelig det bogstavelige = i udtryk с = i kø. Næste er den sidste gruppe .* sammenlignes med den sidste x.
23 trin kun for x=x. Se en kort video om brug af Perl , som viser, hvordan trin og tilbageføring opstår.
Dette er allerede meget arbejde, men hvad nu hvis i stedet x=x vi vil have x=xx? Det er 33 trin. Og hvis x=xxx? 45. Forholdet er ikke lineært. Grafen viser en sammenligning fra x=x til x=xxxxxxxxxxxxxxxxxxxx (20 x efter =). Hvis vi har 20 x efter =, fuldfører motoren matchningen i 555 trin! (Desuden, hvis vi har tabt x= og strengen består simpelthen af 20 x, vil motoren tage 4067 trin for at forstå, at der ikke er nogen match).
Denne video viser al tilbagetrækningen til sammenligning x=xxxxxxxxxxxxxxxxxxxx:
Problemet er, at efterhånden som strengstørrelsen øges, vokser matchningstiden superlineært. Men tingene kan blive endnu værre, hvis det regulære udtryk er lidt ændret. Lad os sige, at vi havde .*.*=.*; (det vil sige, at der var et bogstaveligt semikolon i slutningen af mønsteret). For eksempel for at matche et udtryk som foo=bar;.
Og her ville tilbagetrækning være en sand katastrofe. Til sammenligning x=x det vil tage 90 skridt, ikke 23. Og det tal vokser hurtigt. At sammenligne x= og 20 x, 5353 trin er nødvendige. Her er diagrammet. Se på akseværdierne Y sammenlignet med det foregående diagram.
Hvis du er interesseret, så tjek alle 5353 mislykkede matchende trin x=xxxxxxxxxxxxxxxxxxxx и .*.*=.*;
Ved at bruge doven i stedet for grådig matching, kan omfanget af backtracking kontrolleres. Hvis vi ændrer det oprindelige udtryk til .*?.*?=.*?, til sammenligning x=x det vil tage 11 trin (ikke 23). Som for x=xxxxxxxxxxxxxxxxxxxx. Alt sammen fordi ? efter .* beder motoren om at matche et minimum antal tegn, før den går videre.
Men dovne kortlægninger løser ikke helt tilbagesporingsproblemet. Hvis vi erstatter det katastrofale eksempel .*.*=.*; på .*?.*?=.*?;, vil udførelsestiden forblive den samme. x=x kræver stadig 555 trin, og x= og 20 x - 5353.
Det eneste, der kan gøres (udover fuldstændig at omskrive mønsteret for større specificitet) er at opgive den regulære udtryksmotor med dens tilbagesporingsmekanisme. Det er, hvad vi vil gøre i løbet af de næste par uger.
Løsningen på dette problem har været kendt siden 1968, hvor Kent Thompson skrev en artikel ("Programmeringsmetoder: Regular Expression Search Algorithm"). Artiklen beskriver en mekanisme, der giver dig mulighed for at konvertere et regulært udtryk til ikke-deterministiske finite state-maskiner, og efter tilstandsændringer i ikke-deterministiske finite state-maskiner, bruge en algoritme, hvis eksekveringstid afhænger lineært af den matchede streng.
Programmeringsmetoder
Regulære udtryk søgealgoritme
Ken Thompson
Bell Telephone Laboratories, Inc., Murray Hill, New JerseyDen beskriver en metode til at søge efter en specifik streng af tegn i tekst og diskuterer implementeringen af denne metode i compilerform. Compileren tager det regulære udtryk som kildekode og producerer IBM 7094-programmet som objektkode. Objektprogrammet tager input i form af søgetekst og udsender et signal hver gang en tekststreng matches mod et givet regulært udtryk. Artiklen giver eksempler, problemer og løsninger.
Algoritme
Tidligere søgealgoritmer resulterede i tilbagesporing, hvis en delvis vellykket søgning ikke gav et resultat.I kompileringstilstand fungerer algoritmen ikke med symboler. Den sender instruktioner til kompileret kode. Udførelsen er meget hurtig - efter at have sendt data til toppen af den aktuelle liste, søger den automatisk efter alle mulige på hinanden følgende tegn i det regulære udtryk.
Kompilerings- og søgealgoritmen er inkluderet i tidsdelingsteksteditoren som kontekstuel søgning. Dette er naturligvis langt fra den eneste anvendelse af en sådan søgeprocedure. For eksempel bruges en variant af denne algoritme som en symbolsøgning i en tabel i assembler.
Det antages, at læseren er fortrolig med regulære udtryk og IBM 7094 computerprogrammeringssproget.Kompiler
Compileren består af tre trin, der kører parallelt. Det første trin er syntaksfiltrering, som kun tillader syntaktisk korrekte regulære udtryk at passere igennem. Dette trin indsætter også operatoren "·" for at matche regulære udtryk. I det andet trin konverteres det regulære udtryk til postfix-form. På tredje trin oprettes objektkode. De første 2 faser er indlysende, og vi vil ikke dvæle ved dem.
Thompsons artikel taler ikke om ikke-deterministiske finite state-maskiner, men den forklarer den lineære tidsalgoritme godt og præsenterer et ALGOL-60-program, der genererer assemblersprogkode til IBM 7094. Implementeringen er vanskelig, men ideen er meget enkel.
nuværende søgesti. Det er repræsenteret af et ⊕-ikon med en indgang og to udgange.
Figur 1 viser funktionerne i det tredje kompileringstrin, når et regulært udtrykseksempel transformeres. De første tre tegn i eksemplet er a, b, c, og hver opretter en stakindgang S[i] og et NNODE-felt.NNODE til eksisterende kode for at generere det resulterende regulære udtryk i en enkelt stakindgang (se figur 5)
Sådan ville et regulært udtryk se ud .*.*=.*, hvis du forestiller dig det som på billederne fra Thompsons artikel.
I fig. 0 er der fem tilstande, der starter fra 0, og 3 cyklusser, der starter fra tilstande 1, 2 og 3. Disse tre cyklusser svarer til tre .* i et regulært udtryk. 3 ovaler med prikker svarer til ét symbol. Oval med et skilt = matcher en bogstavelig karakter =. Tilstand 4 er endelig. Hvis vi når det, så matches det regulære udtryk.
For at se, hvordan et sådant tilstandsdiagram kan bruges til matchning af regulære udtryk .*.*=.*, vil vi se på strengmatchning x=x. Programmet starter fra tilstand 0, som vist i fig. 1.
For at denne algoritme skal fungere, skal tilstandsmaskinen være i flere tilstande samtidigt. En ikke-deterministisk finit maskine vil lave alle mulige overgange samtidigt.
Før den når at læse inputdataene, går den i begge første tilstande (1 og 2), som vist i fig. 2.
I fig. 2 viser, hvad der sker, når han ser på den første x в x=x. x kan kortlægge til toppunktet, gå fra tilstand 1 og tilbage til tilstand 1. Or x kan kortlægge til punktet nedenfor, gå fra tilstand 2 og tilbage til tilstand 2.
Efter at have matchet den første x в x=x vi er stadig i tilstand 1 og 2. Vi kan ikke nå tilstand 3 eller 4, fordi vi har brug for en bogstavelig karakter =.
Algoritmen overvejer derefter = в x=x. Ligesom x før den kan den matches til en af de to øverste sløjfer fra tilstand 1 til tilstand 1 eller fra tilstand 2 til tilstand 2, men algoritmen kan matche den bogstavelige = og gå fra tilstand 2 til tilstand 3 (og straks 4). Dette er vist i fig. 3.
Algoritmen går derefter videre til den sidste x в x=x. Fra tilstand 1 og 2 er de samme overgange mulige tilbage til tilstande 1 og 2. Fra tilstand 3 x kan matche punktet til højre og gå tilbage til tilstand 3.
På dette stadium, hver karakter x=x overvejet, og da vi har nået tilstand 4, matcher det regulære udtryk den streng. Hvert tegn behandles én gang, så denne algoritme er lineær i længden af inputstrengen. Og ingen tilbagetrækning.
Det er klart, efter at have nået tilstand 4 (når algoritmen har matchet x=) hele det regulære udtryk matches, og algoritmen kan afsluttes uden at overveje det overhovedet x.
Denne algoritme afhænger lineært af størrelsen af inputstrengen.
Kilde: www.habr.com