För nästan 9 år sedan var Cloudflare ett litet företag, och jag arbetade inte för det, jag var bara en kund. En månad efter lanseringen av Cloudflare fick jag ett meddelande om att min webbplats DNS verkar inte fungera. Cloudflare har gjort en förändring till , och det var en trasig DNS.
Jag skrev omedelbart till Matthew Prince med titeln "Var är min DNS?" och han skickade tillbaka ett långt svar fullt med tekniska detaljer (), varpå jag svarade:
Från: John Graham-Cumming
Datum: 7 oktober 2010, 9:14
Ämne: Re: Var är min DNS?
Till: Matthew PrinceKul rapport, tack. Jag ringer definitivt om det blir problem. Det är förmodligen värt att skriva ett inlägg om detta när du har samlat all teknisk information. Jag tror att folk kommer att njuta av en öppen och ärlig berättelse. Speciellt om du bifogar grafer för att visa hur trafiken har vuxit sedan lanseringen.
Jag har bra övervakning på min sida och jag får ett SMS om varje fel. Övervakning visar att felet inträffade från 13:03:07 till 14:04:12. Tester utförs var femte minut.
Jag är säker på att du kommer att ta reda på det. Är du säker på att du inte behöver din egen person i Europa? 🙂
Och han svarade:
Från: Matthew Prince
Datum: 7 oktober 2010, 9:57
Ämne: Re: Var är min DNS?
Till: John Graham-CummingTack. Vi svarade alla som skrev. Jag är på väg till kontoret nu och vi ska skriva något på bloggen eller fästa ett officiellt inlägg på vår anslagstavla. Jag håller helt med, ärlighet är allt.
Nu är Cloudflare ett riktigt stort företag, jag jobbar för det, och nu måste jag skriva öppet om vårt misstag, dess konsekvenser och våra handlingar.
Händelser den 2 juli
Den 2 juli rullade vi ut en ny regel i Managed Rules för WAFs på varje processorkärna som bearbetar HTTP/HTTPS-trafik på Cloudflare-nätverket över hela världen. Vi förbättrar ständigt hanterade regler för WAF:er som svar på nya sårbarheter och hot. I maj skyndade vi till exempel för att skydda mot en allvarlig sårbarhet i SharePoint. Hela poängen med vår WAF är möjligheten att snabbt och globalt distribuera regler.
Tyvärr innehöll förra torsdagens uppdatering ett reguljärt uttryck som slösade bort för mycket HTTP/HTTPS CPU-resurser på backtracking. Våra centrala proxy-, CDN- och WAF-funktioner led av detta. Grafen visar att processorresurserna för att betjäna HTTP/HTTPS-trafik når nästan 100 % på servrar i vårt nätverk.
CPU-användning vid en närvaropunkt under en incident
Som ett resultat fick våra kunder (och våra kunders klienter) en 502-felsida på Cloudflare-domäner. 502-fel genererades av Cloudflare front-end webbservrar som fortfarande hade fria kärnor men som inte kunde kommunicera med processer som hanterade HTTP/HTTPS-trafik.
Vi vet hur mycket besvär detta har orsakat våra kunder. Vi skäms fruktansvärt. Och detta misslyckande hindrade oss från att effektivt hantera incidenten.
Om du var en av dessa kunder var du förmodligen rädd, arg och upprörd. Dessutom har vi inte haft en . Den höga CPU-förbrukningen berodde på en WAF-regel med ett dåligt formulerat reguljärt uttryck som resulterade i överdriven backtracking. Här är det skyldiga uttrycket: (?:(?:"|'|]|}||d|(?:nan|infinity|true|false|null|undefined|symbol|math)|`|-|+)+[)]*;?((?:s|-|~|!|{}||||+)*.*(?:.*=.*)))
Även om detta är intressant i sig (och jag ska prata om det mer i detalj nedan), var Cloudflare-tjänsten nere i 27 minuter, inte bara på grund av ett dåligt reguljärt uttryck. Det tog oss ett tag att beskriva händelseförloppet som ledde till misslyckandet, så vi var långsamma med att svara. I slutet av inlägget kommer jag att beskriva backtracking i ett reguljärt uttryck och berätta vad du ska göra med det.
Vad hände
Låt oss börja i ordning. Alla tider här är i UTC.
Klockan 13:42 gjorde en ingenjör i brandväggsteamet en liten ändring i detektionsreglerna med hjälp av en automatisk process. Följaktligen skapades en ändringsbegäran. Vi hanterar sådana biljetter genom Jira (skärmdump nedan).
Efter 3 minuter dök den första sidan av PagerDuty upp och rapporterade ett problem med WAF. Detta var ett syntetiskt test som testar funktionaliteten hos WAF (vi har hundratals av dem) utanför Cloudflare för att övervaka normal drift. Detta följdes omedelbart av sidor med varningar om andra Cloudflare end-to-end-tjänsttester som misslyckades, globala trafikproblem, utbredda 502-fel och massor av rapporter från våra Points of Presence (PoP) i städer runt om i världen som indikerade en brist av CPU-resurser.
Jag fick flera av dessa varningar, stormade ut från ett möte och var på väg till bordet när chefen för vår avdelning för lösningsutveckling sa att vi tappat 80 % av vår trafik. Jag sprang till våra SRE-ingenjörer, som redan arbetade med problemet. Först trodde vi att det var någon form av okänd attack.
Cloudflares SRE-ingenjörer är utspridda över hela världen och övervakar situationen dygnet runt. Vanligtvis meddelar dessa varningar dig om specifika lokala problem av begränsad omfattning, spåras på interna instrumentpaneler och löses flera gånger om dagen. Men dessa sidor och meddelanden indikerade något riktigt allvarligt, och SRE-ingenjörer deklarerade omedelbart svårighetsgraden P0 och kontaktade lednings- och systemingenjörer.
Våra Londoningenjörer lyssnade på en föreläsning i stora salen just då. Föreläsningen fick avbrytas, alla samlades i ett stort konferensrum och fler specialister tillkallades. Detta var inte ett typiskt problem som SRE kunde ta itu med själva. Det var angeläget att involvera rätt specialister.
Vid 14:00 konstaterade vi att problemet var med WAF och att det inte fanns någon attack. Prestandateamet drog CPU-data och det blev klart att WAF var skyldig. En annan anställd bekräftade denna teori med hjälp av strace. Någon annan såg i loggarna att det var ett problem med WAF. Klockan 14:02 kom hela teamet till mig när det föreslogs att använda global kill, en mekanism inbyggd i Cloudflare som stänger av en komponent över hela världen.
Hur vi gjorde global kill för WAF är en annan historia. Så enkelt är det inte. Vi använder våra egna produkter, och sedan vår tjänst fungerade inte, vi kunde inte autentisera och logga in på den interna kontrollpanelen (när allt var fixat fick vi veta att några teammedlemmar hade förlorat åtkomst på grund av en säkerhetsfunktion som inaktiverar autentiseringsuppgifter om den interna kontrollpanelen inte används för en länge sedan).
Och vi kunde inte komma till våra interna tjänster, som Jira eller byggsystemet. Vi behövde en lösningsmekanism, som vi använde sällan (denna kommer också att behöva redas ut). Slutligen lyckades en ingenjör avaktivera WAF klockan 14:07, och klockan 14:09 var trafik- och CPU-nivåerna tillbaka till det normala överallt. Resten av Cloudflares skyddsmekanismer fungerade som vanligt.
Sedan började vi återställa WAF. Situationen var utöver det vanliga, så vi körde negativa tester (frågade oss själva om förändringen verkligen var problemet) och positiva tester (se till att återställningen fungerade) i en stad med separat trafik och överförde betalande kunder därifrån.
Klockan 14:52 var vi övertygade om att vi förstod orsaken och gjorde en korrigering och aktiverade WAF igen.
Hur Cloudflare fungerar
Cloudflare har ett team av ingenjörer dedikerade till att hantera regler för WAF. De strävar efter att förbättra upptäcktsfrekvensen, minska falska positiva resultat och reagera snabbt på nya hot när de dyker upp. Under de senaste 60 dagarna har det bearbetats 476 ändringsförfrågningar för hanterade regler för WAF (i genomsnitt en var tredje timme).
Denna speciella ändring behövde distribueras i simuleringsläge, där verklig klienttrafik passerar genom regeln, men ingenting är blockerat. Vi använder det här läget för att testa reglernas effektivitet och mäta de falska positiva och falska negativa frekvenserna. Men även i simuleringsläge måste reglerna faktiskt exekveras, och i det här fallet innehöll regeln ett reguljärt uttryck som konsumerade för mycket processorresurser.
Som du kan se från ändringsförfrågan ovan har vi en implementeringsplan, en återställningsplan och en länk till en intern standardoperativ procedur (SOP) för denna typ av implementering. SOP för att ändra en regel tillåter att den publiceras globalt. Faktiskt, på Cloudflare görs saker helt annorlunda, och SOP dikterar att vi först skickar programvaran för testning och intern användning till en intern närvaropunkt (PoP) (som våra anställda använder), sedan till ett litet antal kunder i en isolerad plats, sedan till ett stort antal kunder och först då till hela världen.
Så här ser det ut. Vi använder git internt via BitBucket. Ingenjörer som arbetar med ändringar skickar in kod, som är byggd till TeamCity, och när bygget går igenom tilldelas granskare. När en pull-begäran har godkänts, sätts koden ihop och en serie tester körs (igen).
Om bygget och testerna slutförs framgångsrikt skapas en ändringsbegäran i Jira och lämplig chef eller ledare måste godkänna ändringen. Efter godkännande sker utplacering i det så kallade "PoP-menageriet": DOG, PIG och (hund, gris och kanariefågel).
DOG PoP är en Cloudflare PoP (som alla andra av våra städer) som endast används av Cloudflares anställda. PoP för internt bruk låter dig fånga problem innan kundtrafik börjar flöda in i lösningen. Användbar sak.
Om HUND-testet lyckas flyttas koden till PIG-stadiet (marsvin). Detta är Cloudflare PoP, där en liten mängd gratis kundtrafik flödar genom ny kod.
Om allt är bra går koden till Canary. Vi har tre Canary PoPs i olika delar av världen. I dem passerar trafiken av betalda och gratis klienter genom den nya koden, och detta är den sista kontrollen för fel.
Programvarusläppprocess hos Cloudflare
Om koden är ok på Kanarieöarna släpper vi den. Att gå igenom alla stadier - HUND, GRIS, Kanarieöarna, hela världen - tar flera timmar eller dagar, beroende på kodändringen. På grund av mångfalden av Cloudflares nätverk och klienter testar vi koden noggrant innan vi släpper den globalt till alla kunder. Men WAF följer inte specifikt denna process eftersom hot måste bemötas snabbt.
WAF-hot
Under de senaste åren har det skett en betydande ökning av hoten i vanliga applikationer. Detta beror på den ökade tillgängligheten av verktyg för mjukvarutestning. Till exempel skrev vi nyligen om ).
Källa:
Mycket ofta skapas ett proof of concept och publiceras omedelbart på Github så att teamen som underhåller applikationen snabbt kan testa den och säkerställa att den är tillräckligt säkrad. Därför behöver Cloudflare förmågan att svara på nya attacker så snabbt som möjligt så att kunderna har möjlighet att fixa sin mjukvara.
Ett bra exempel på Cloudflares snabba svar är implementeringen av SharePoints sårbarhetsskydd i maj (). Nästan omedelbart efter att tillkännagivandena gjordes märkte vi ett stort antal försök att utnyttja sårbarheten i våra kunders SharePoint-installationer. Våra killar övervakar ständigt nya hot och skriver regler för att skydda våra kunder.
Regeln som orsakade problemet i torsdags var tänkt att skydda mot cross-site scripting (XSS). Sådana attacker har också blivit mycket vanligare de senaste åren.
Källa:
Standardproceduren för att ändra en hanterad regel för en WAF är att utföra testning av kontinuerlig integration (CI) före global distribution. I torsdags gjorde vi detta och rullade ut reglerna. Klockan 13:31 skickade en ingenjör in en godkänd pull-förfrågan med en ändring.
Klockan 13:37 samlade TeamCity in reglerna, körde tester och gav klartecken. WAF-testsviten testar kärnfunktionaliteten i WAF och består av ett stort antal enhetstester för individuella funktioner. Efter enhetstester testade vi reglerna för WAF med ett stort antal HTTP-förfrågningar. HTTP-förfrågningar kontrollerar vilka förfrågningar som bör blockeras av WAF (för att avlyssna attacken) och vilka som kan tillåtas igenom (för att inte blockera allt och undvika falska positiva). Men vi testade inte för överdriven CPU-användning, och att undersöka loggarna för tidigare WAF-byggen visar att körtiden för regeltestet inte ökade, och det var svårt att misstänka att det inte skulle finnas tillräckligt med resurser.
Testerna klarade och TeamCity började automatiskt distribuera ändringen klockan 13:42.
Kvicksilver
WAF-regler fokuserar på omedelbar åtgärdande av hot, så vi distribuerar dem med Quicksilvers distribuerade nyckel-värdelager, som sprider förändringar globalt på några sekunder. Alla våra kunder använder denna teknik när de ändrar konfigurationen i instrumentpanelen eller via API:t, och det är tack vare den som vi reagerar blixtsnabbt på förändringar.
Vi har inte pratat så mycket om Quicksilver. Tidigare använde vi som en globalt distribuerad butik med nyckelvärden, men det fanns driftsproblem med den, och vi skrev vår egen butik, replikerad i mer än 180 städer. Vi använder nu Quicksilver för att driva konfigurationsändringar till klienter, uppdatera WAF-regler och distribuera JavaScript-kod skriven av klienter till Cloudflare Workers.
Det tar bara några sekunder från att klicka på en knapp på en instrumentpanel eller anropa ett API till att göra en konfigurationsändring över hela världen. Kunderna älskade denna snabbhet i installationen. Och Workers ger dem nästan omedelbar global programvarudistribution. I genomsnitt sprider Quicksilver cirka 350 förändringar per sekund.
Och Quicksilver är väldigt snabb. I genomsnitt uppnådde vi den 99:e percentilen på 2,29 sekunder för att sprida förändringar till varje dator över hela världen. Snabbhet brukar vara bra. När allt kommer omkring, när du aktiverar en funktion eller rensar cachen händer det nästan omedelbart och överallt. Att skicka kod via Cloudflare Workers sker med samma hastighet. Cloudflare lovar sina kunder snabba uppdateringar vid rätt tidpunkt.
Men i det här fallet spelade hastigheten ett grymt skämt för oss, och reglerna ändrades överallt på några sekunder. Du kanske har märkt att WAF-koden använder Lua. Cloudflare använder Lua flitigt i produktion och detaljer vi . Lua WAF använder internt och tillämpar backtracking för matchning. Den har inga mekanismer för att skydda mot uttryck som går utom kontroll. Nedan kommer jag att prata mer om detta och vad vi gör åt det.
Innan reglerna implementerades gick allt smidigt: pull-begäran skapades och godkändes, CI/CD-pipelinen samlade in och testade koden, ändringsbegäran skickades in enligt SOP som reglerar driftsättning och återställning, och distributionen slutfördes.
Cloudflare WAF-distributionsprocess
Något gick fel
Som jag sa, vi distribuerar dussintals nya WAF-regler varje vecka, och vi har många system på plats för att skydda mot de negativa konsekvenserna av en sådan utplacering. Och när något går fel är det oftast en kombination av flera omständigheter samtidigt. Om du bara hittar en anledning är detta naturligtvis betryggande, men det är inte alltid sant. Dessa är anledningarna som tillsammans ledde till att vår HTTP/HTTPS-tjänst misslyckades.
- En ingenjör skrev ett reguljärt uttryck som kunde resultera i överdrivet .
- En funktion som kunde ha förhindrat det reguljära uttrycket från att slösa bort för mycket CPU togs av misstag bort i en refaktorering av WAF flera veckor tidigare – refaktoreringen behövdes för att WAF skulle förbruka mindre resurser.
- Motorn för reguljära uttryck hade inga komplexitetsgarantier.
- Testsviten kunde inte upptäcka överdriven CPU-förbrukning.
- SOP tillåter icke-brådskande regeländringar att rullas ut globalt utan en flerstegsprocess.
- Återställningsplanen krävde att man körde en fullständig WAF-version två gånger, vilket tog lång tid.
- Den första larmet om globala trafikproblem utlöstes för sent.
- Vi tog ett tag att uppdatera statussidan.
- Vi hade problem med att komma åt system på grund av ett fel, och förbikopplingsproceduren var inte väl etablerad.
- SRE-ingenjörer förlorade åtkomst till vissa system eftersom deras autentiseringsuppgifter gick ut på grund av säkerhetsskäl.
- Våra kunder hade inte tillgång till Cloudflares instrumentpanel eller API eftersom de går igenom en Cloudflare-region.
Vad har förändrats sedan i torsdags
Först stoppade vi helt allt arbete med utgåvor för WAF och gör följande:
- Vi återinför CPU-överanvändningsskyddet som vi tog bort. (Redo)
- Manuell kontroll av alla 3868 XNUMX regler i de hanterade reglerna för WAF för att hitta och korrigera andra potentiella fall av överdriven backtracking. (Verifiering slutförd)
- Vi inkluderar prestationsprofilering för alla regler i testsetet. (Förväntad: 19 juli)
- Byter till en motor för reguljära uttryck eller - Båda ger körtidsgarantier. (Förväntad: 31 juli)
- Vi skriver om SOP för att distribuera regler i etapper, som annan mjukvara i Cloudflare, men samtidigt ha möjligheten att nödsätta global utplacering om attacker redan har börjat.
- Vi utvecklar möjligheten att omedelbart ta bort Cloudflares instrumentpanel och API från Cloudflare-regionen.
- Automatisera siduppdateringar .
Långsiktigt går vi bort från Lua WAF som jag skrev för några år sedan. Flytta WAF till . På så sätt blir WAF snabbare och får en extra skyddsnivå.
Slutsats
Detta misslyckande orsakade problem för oss och våra kunder. Vi agerade snabbt för att rätta till situationen och arbetar nu med bristerna i processerna som orsakade kraschen, samt gräver ännu djupare för att skydda oss mot potentiella problem med reguljära uttryck i framtiden vid migrering till ny teknik.
Vi är mycket generade över detta avbrott och ber våra kunder om ursäkt. Vi hoppas att dessa förändringar kommer att säkerställa att något liknande inte händer igen.
Ansökan. Backtracking reguljära uttryck
För att förstå hur uttrycket:
(?:(?:"|'|]|}||d
(?:nan|infinity|true|false|null|undefined|symbol|math)|`|-
|+)+[)]*;?((?:s|-|~|!|{}||||+)*.*(?:.*=.*)))åt upp alla CPU-resurser behöver du veta lite om hur standardmotorn för reguljära uttryck fungerar. Problemet här är mönstret .*(?:.*=.*). (?: och motsvarande ) är en icke-fångande grupp (det vill säga uttrycket inom parentes är grupperat som ett enda uttryck).
I samband med överdriven CPU-förbrukning kan detta mönster beskrivas som .*.*=.*. I denna form ser mönstret onödigt komplext ut. Men ännu viktigare, i den verkliga världen kan uttryck (som komplexa uttryck i WAF-regler) som ber motorn att matcha ett fragment följt av ett annat fragment leda till katastrofal backtracking. Och det är varför.
I reguljärt uttryck . betyder att du måste matcha en karaktär, .* - matcha noll eller fler tecken "girigt", det vill säga fånga maximalt antal tecken, så att .*.*=.* betyder matcha noll eller fler tecken, matcha sedan noll eller fler tecken, hitta bokstavlig = tecken, matcha noll eller fler tecken.
Låt oss ta testlinjen x=x. Det motsvarar uttrycket .*.*=.*. .*.* innan likhetstecknet matchar det första x (en av grupperna .* motsvarar x, och den andra - noll tecken). .* efter = matcherna senast x.
Denna jämförelse kräver 23 steg. Första gruppen .* в .*.*=.* agerar girigt och matchar hela strängen x=x. Motorn går till nästa grupp .*. Vi har inga fler karaktärer att matcha, så den andra gruppen .* matchar noll tecken (detta är tillåtet). Sedan går motorn till skylten =. Det finns inga fler symboler (första gruppen .* använde hela uttrycket x=x), ingen jämförelse sker.
Och sedan återgår motorn för reguljära uttryck till början. Han går vidare till den första gruppen .* och jämför det с x= (istället för x=x), och tar sedan emot den andra gruppen .*. Andra gruppen .* jämförs med den andra x, och vi har återigen inga tecken kvar. Och när motorn når igen = в .*.*=.*, ingenting fungerar. Och han backar igen.
Denna gång gruppen .* fortfarande matchar x=, men den andra gruppen .* inte mer x, och noll tecken. Motorn försöker hitta en bokstavlig karaktär = i mönstret .*.*=.*, men kommer inte ut (trots allt har den första gruppen redan ockuperat den .*). Och han backar igen.
Den här gången den första gruppen .* tar bara det första x. Men den andra gruppen .* "girigt" fångar =x. Har du redan gissat vad som kommer att hända? Motorn försöker matcha det bokstavliga =, misslyckas och gör ytterligare en backtracking.
Den första gruppen .* matchar fortfarande den första x. Andra .* bara tar =. Motorn kan förstås inte matcha det bokstavliga =, eftersom den andra gruppen redan har gjort detta .*. Och återigen backa. Och vi försöker matcha en sträng med tre tecken!
Som ett resultat, den första gruppen .* matchar endast den första x, andra .* - med noll tecken, och motorn matchar äntligen det bokstavliga = i uttryck с = i kö. Nästa är den sista gruppen .* jämförs med den senaste x.
23 steg endast för x=x. Se en kort video om hur du använder Perl , som visar hur steg och bakåtspårning sker.
Detta är redan mycket arbete, men tänk om istället x=x vi kommer att ha x=xx? Det är 33 steg. Och om x=xxx? 45. Förhållandet är inte linjärt. Grafen visar en jämförelse från x=x до x=xxxxxxxxxxxxxxxxxxxx (20 x efter =). Om vi har 20 x efter =, motorn slutför matchningen i 555 steg! (Dessutom, om vi har förlorat x= och strängen består helt enkelt av 20 x, kommer motorn att ta 4067 steg för att förstå att det inte finns några matchningar).
Den här videon visar all backtracking för jämförelse x=xxxxxxxxxxxxxxxxxxxx:
Problemet är att när strängstorleken ökar, växer matchningstiden superlinjärt. Men saker och ting kan bli ännu värre om det reguljära uttrycket modifieras något. Låt oss säga att vi hade .*.*=.*; (det vill säga det fanns ett bokstavligt semikolon i slutet av mönstret). Till exempel för att matcha ett uttryck som foo=bar;.
Och här skulle backtracking vara en riktig katastrof. För jämförelse x=x det kommer att ta 90 steg, inte 23. Och den siffran växer snabbt. Att jämföra x= och 20 x, 5353 steg behövs. Här är diagrammet. Titta på axelvärdena Y jämfört med föregående diagram.
Om du är intresserad, kolla in alla 5353 XNUMX misslyckade matchningssteg x=xxxxxxxxxxxxxxxxxxxx и .*.*=.*;
Genom att använda lat snarare än girig matchning kan omfattningen av backtracking kontrolleras. Om vi ändrar det ursprungliga uttrycket till .*?.*?=.*?, för jämförelse x=x det tar 11 steg (inte 23). Som för x=xxxxxxxxxxxxxxxxxxxx. Allt för att ? efter .* säger till motorn att matcha ett minsta antal tecken innan den går vidare.
Men lata kartläggningar löser inte helt bakåtspårningsproblemet. Om vi ersätter det katastrofala exemplet .*.*=.*; på .*?.*?=.*?;, kommer exekveringstiden att förbli densamma. x=x kräver fortfarande 555 steg, och x= och 20 x - 5353.
Det enda som kan göras (förutom att helt skriva om mönstret för större specificitet) är att överge motorn för reguljära uttryck med dess bakåtspårningsmekanism. Detta är vad vi kommer att göra under de kommande veckorna.
Lösningen på detta problem har varit känd sedan 1968, då Kent Thompson skrev en artikel ("Programmeringsmetoder: Regular Expression Search Algorithm"). Artikeln beskriver en mekanism som låter dig konvertera ett reguljärt uttryck till icke-deterministiska finita tillståndsmaskiner, och efter tillståndsändringar i icke-deterministiska finita tillståndsmaskiner, använda en algoritm vars exekveringstid beror linjärt på den matchade strängen.
Programmeringsmetoder
Reguljära uttryck sökalgoritm
Ken Thompson
Bell Telephone Laboratories, Inc., Murray Hill, New JerseyDen beskriver en metod för att söka efter en specifik teckensträng i text och diskuterar implementeringen av denna metod i kompilatorform. Kompilatorn tar det reguljära uttrycket som källkod och producerar IBM 7094-programmet som objektkod. Objektprogrammet tar input i form av söktext och avger en signal varje gång en textsträng matchas mot ett givet reguljärt uttryck. Artikeln ger exempel, problem och lösningar.
Algoritm
Tidigare sökalgoritmer resulterade i backtracking om en delvis lyckad sökning misslyckades med att ge resultat.I kompileringsläge fungerar inte algoritmen med symboler. Den skickar instruktioner till kompilerad kod. Exekveringen är mycket snabb - efter att ha skickat data till toppen av den aktuella listan, söker den automatiskt efter alla möjliga på varandra följande tecken i det reguljära uttrycket.
Kompilerings- och sökalgoritmen ingår i textredigeraren för tidsdelning som kontextuell sökning. Naturligtvis är detta långt ifrån den enda tillämpningen av ett sådant sökförfarande. Till exempel används en variant av denna algoritm som en symbolsökning i en tabell i assembler.
Det förutsätts att läsaren är bekant med reguljära uttryck och datorprogrammeringsspråket IBM 7094.Kompilator
Kompilatorn består av tre steg som löper parallellt. Det första steget är syntaxfiltrering, som tillåter endast syntaktisk korrekta reguljära uttryck att passera igenom. Detta steg infogar också operatorn "·" för att matcha reguljära uttryck. I det andra steget konverteras det reguljära uttrycket till postfix-form. I det tredje steget skapas objektkod. De två första stegen är uppenbara, och vi kommer inte att uppehålla oss vid dem.
Thompsons artikel talar inte om icke-deterministiska finita tillståndsmaskiner, men den förklarar den linjära tidsalgoritmen väl och presenterar ett ALGOL-60-program som genererar assemblerspråkkod för IBM 7094. Implementeringen är knepig, men idén är väldigt enkel.
aktuell sökväg. Den representeras av en ⊕-ikon med en ingång och två utgångar.
Figur 1 visar funktionerna för det tredje kompileringssteget vid transformering av ett exempel på reguljärt uttryck. De tre första tecknen i exemplet är a, b, c, och var och en skapar en stackpost S[i] och ett NNODE-fält.NNODE till befintlig kod för att generera det resulterande reguljära uttrycket i en enda stackpost (se figur 5)
Så här skulle ett reguljärt uttryck se ut .*.*=.*, om du föreställer dig det som på bilderna från Thompsons artikel.
I fig. 0 finns det fem tillstånd som börjar från 0 och 3 cykler som börjar från tillstånd 1, 2 och 3. Dessa tre cykler motsvarar tre .* i ett reguljärt uttryck. 3 ovaler med prickar motsvarar en symbol. Oval med en skylt = matchar en bokstavlig karaktär =. Tillstånd 4 är slutgiltigt. Om vi når det, så matchas det reguljära uttrycket.
För att se hur ett sådant tillståndsdiagram kan användas för matchning av reguljära uttryck .*.*=.*, ska vi titta på strängmatchning x=x. Programmet startar från tillstånd 0, som visas i fig. 1.
För att denna algoritm ska fungera måste tillståndsmaskinen vara i flera tillstånd samtidigt. En icke-deterministisk finit maskin kommer att göra alla möjliga övergångar samtidigt.
Innan den hinner läsa indata går den in i båda första tillstånden (1 och 2), som visas i Fig. 2.
I fig. 2 visar vad som händer när han tittar på den första x в x=x. x kan mappa till topppunkten, gå från tillstånd 1 och tillbaka till tillstånd 1. Or x kan mappa till punkten nedan, gå från tillstånd 2 och tillbaka till tillstånd 2.
Efter att ha matchat den första x в x=x vi är fortfarande i tillstånd 1 och 2. Vi kan inte nå tillstånd 3 eller 4 eftersom vi behöver en bokstavlig karaktär =.
Algoritmen överväger sedan = в x=x. Liksom x före det kan det matchas till någon av de två översta slingorna från tillstånd 1 till tillstånd 1 eller från tillstånd 2 till tillstånd 2, men algoritmen kan matcha den bokstavliga = och flytta från tillstånd 2 till tillstånd 3 (och omedelbart 4). Detta visas i fig. 3.
Algoritmen går sedan vidare till den sista x в x=x. Från tillstånd 1 och 2 är samma övergångar möjliga tillbaka till tillstånd 1 och 2. Från tillstånd 3 x kan matcha punkten till höger och gå tillbaka till tillstånd 3.
I detta skede, varje karaktär x=x övervägt, och eftersom vi har nått tillstånd 4, matchar det reguljära uttrycket den strängen. Varje tecken bearbetas en gång, så denna algoritm är linjär i längden på inmatningssträngen. Och ingen backtracking.
Uppenbarligen, efter att ha nått tillstånd 4 (när algoritmen har matchat x=) hela det reguljära uttrycket matchas, och algoritmen kan avslutas utan att överväga det alls x.
Denna algoritm beror linjärt på storleken på inmatningssträngen.
Källa: will.com