Bijna 9 jaar geleden was Cloudflare een klein bedrijf, en ik werkte er niet voor, ik was gewoon een klant. Een maand na de lancering van Cloudflare ontving ik een melding dat mijn website DNS lijkt niet te werken. Cloudflare heeft daar verandering in gebracht , en er was een kapotte DNS.
Ik schreef onmiddellijk naar Matthew Prince met de titel “Waar is mijn DNS?” en hij stuurde een lang antwoord vol technische details terug (), waarop ik antwoordde:
Van: John Graham-Cumming
Datum: 7 oktober 2010, 9:14
Onderwerp: Re: Waar is mijn DNS?
Aan: Matthew PrinsLeuk verslag, bedankt. Ik zal zeker bellen als er problemen zijn. Het is waarschijnlijk de moeite waard om hier een bericht over te schrijven zodra je alle technische informatie hebt verzameld. Ik denk dat mensen zullen genieten van een open en eerlijk verhaal. Vooral als je er grafieken aan toevoegt om te laten zien hoe het verkeer sinds de lancering is gegroeid.
Ik heb een goede monitoring op mijn site en ontvang bij elke storing een sms. Uit monitoring blijkt dat de storing tussen 13:03:07 en 14:04:12 heeft plaatsgevonden. Elke vijf minuten worden er tests uitgevoerd.
Ik weet zeker dat je er wel achter komt. Weet u zeker dat u in Europa geen eigen persoon nodig heeft? 🙂
En hij antwoordde:
Van: Matthew Prins
Datum: 7 oktober 2010, 9:57
Onderwerp: Re: Waar is mijn DNS?
Aan: John Graham-CummingBedankt. We hebben gereageerd op iedereen die schreef. Ik ben nu op weg naar kantoor en we zullen iets op de blog schrijven of een officieel bericht op ons prikbord prikken. Ik ben het er volledig mee eens, eerlijkheid is alles.
Nu is Cloudflare een heel groot bedrijf, ik werk ervoor, en nu moet ik openlijk schrijven over onze fout, de gevolgen ervan en onze acties.
Evenementen van 2 juli
Op 2 juli hebben we een nieuwe regel geïntroduceerd in Managed Rules voor WAF's op elke processorkern die HTTP/HTTPS-verkeer op het Cloudflare-netwerk wereldwijd verwerkt. We verbeteren voortdurend de beheerde regels voor WAF's als reactie op nieuwe kwetsbaarheden en bedreigingen. In mei hadden we bijvoorbeeld haast ter bescherming tegen een ernstige kwetsbaarheid in SharePoint. Het hele punt van onze WAF is het vermogen om snel en wereldwijd regels in te voeren.
Helaas bevatte de update van afgelopen donderdag een reguliere expressie die te veel HTTP/HTTPS CPU-bronnen verspilde aan backtracking. Onze kernproxy-, CDN- en WAF-functies hadden hieronder te lijden. De grafiek laat zien dat de processorbronnen voor het verwerken van HTTP/HTTPS-verkeer bijna 100% bereiken op servers in ons netwerk.
CPU-gebruik op een bepaald punt tijdens een incident
Als gevolg hiervan kregen onze klanten (en de klanten van onze klanten) een 502-foutpagina in Cloudflare-domeinen. 502-fouten werden gegenereerd door front-end-webservers van Cloudflare die nog steeds vrije kernen hadden, maar niet konden communiceren met processen die HTTP/HTTPS-verkeer verwerkten.
Wij weten hoeveel ongemak dit voor onze klanten heeft veroorzaakt. Wij schamen ons vreselijk. En deze mislukking heeft ons ervan weerhouden het incident effectief aan te pakken.
Als u een van deze klanten was, was u waarschijnlijk bang, boos en overstuur. Bovendien hebben we nog geen . Het hoge CPU-verbruik was te wijten aan een WAF-regel met een slecht geformuleerde reguliere expressie die resulteerde in overmatige backtracking. Hier is de schuldige uitdrukking: (?:(?:"|'|]|}||d|(?:nan|infinity|true|false|null|undefined|symbol|math)|`|-|+)+[)]*;?((?:s|-|~|!|{}||||+)*.*(?:.*=.*)))
Hoewel dit op zichzelf interessant is (en ik zal er hieronder meer in detail over praten), was de Cloudflare-service 27 minuten lang niet beschikbaar, niet alleen vanwege een slechte reguliere expressie. Het kostte ons een tijdje om de opeenvolging van gebeurtenissen te beschrijven die tot de mislukking leidden, dus we reageerden traag. Aan het einde van het bericht zal ik het backtracken in een reguliere expressie beschrijven en vertellen wat je ermee moet doen.
Wat is er gebeurd
Laten we op volgorde beginnen. Alle tijden hier zijn in UTC.
Om 13 uur heeft een technicus van het firewallteam een kleine wijziging aangebracht in de detectieregels met behulp van een automatisch proces. Daarom is er een wijzigingsaanvraagticket aangemaakt. Wij beheren dergelijke tickets via Jira (screenshot hieronder).
Na 3 minuten verscheen de eerste pagina van PagerDuty, waarop een probleem met WAF werd gemeld. Dit was een synthetische test die de functionaliteit van WAF's (we hebben er honderden) buiten Cloudflare test om de normale werking te controleren. Dit werd onmiddellijk gevolgd door pagina's met waarschuwingen over het mislukken van andere end-to-end-servicetests van Cloudflare, wereldwijde verkeersproblemen, wijdverbreide 502-fouten en een heleboel rapporten van onze Points of Presence (PoP) in steden over de hele wereld die duidden op een gebrek van CPU-bronnen.
Ik ontving verschillende van deze waarschuwingen, stormde een vergadering uit en was op weg naar de tafel toen het hoofd van onze afdeling voor oplossingsontwikkeling zei dat we 80% van ons verkeer verloren hadden. Ik rende naar onze SRE-ingenieurs, die al aan het probleem werkten. In eerste instantie dachten we dat het een onbekende aanval was.
Cloudflare SRE-ingenieurs zijn verspreid over de hele wereld en houden de situatie 0 uur per dag in de gaten. Deze waarschuwingen brengen u doorgaans op de hoogte van specifieke lokale problemen met een beperkte reikwijdte, worden bijgehouden op interne dashboards en worden meerdere keren per dag opgelost. Maar deze pagina's en meldingen wezen op iets heel ernstigs, en SRE-ingenieurs verklaarden onmiddellijk het ernstniveau PXNUMX en namen contact op met het management en de systeemingenieurs.
Onze Londense ingenieurs luisterden op dat moment naar een lezing in de grote zaal. De lezing moest worden onderbroken, iedereen verzamelde zich in een grote vergaderruimte en er werden nog meer specialisten gebeld. Dit was geen typisch probleem dat SRE's zelf konden oplossen. Het was urgent om de juiste specialisten erbij te betrekken.
Om 14 uur stelden we vast dat het probleem bij de WAF lag en dat er geen aanval plaatsvond. Het prestatieteam haalde de CPU-gegevens op en het werd duidelijk dat de WAF de schuldige was. Een andere medewerker bevestigde deze theorie met behulp van strace. Iemand anders zag in de logboeken dat er een probleem was met WAF. Om 00:14 uur kwam het hele team naar me toe toen werd voorgesteld om global kill te gebruiken, een mechanisme ingebouwd in Cloudflare dat één component wereldwijd afsluit.
Hoe we een wereldwijde moord voor WAF hebben gepleegd, is een ander verhaal. Het is niet zo eenvoudig. Wij gebruiken onze eigen producten en sindsdien onze service werkte niet, we konden ons niet authenticeren en inloggen op het interne controlepaneel (toen alles was opgelost, kwamen we erachter dat sommige teamleden de toegang waren kwijtgeraakt vanwege een beveiligingsfunctie die inloggegevens uitschakelt als het interne controlepaneel niet wordt gebruikt voor een lange tijd).
En we konden niet bij onze interne diensten komen, zoals Jira of het buildsysteem. We hadden een oplossingsmechanisme nodig, dat we niet vaak gebruikten (dit zal ook moeten worden uitgewerkt). Uiteindelijk slaagde één ingenieur erin om de WAF om 14:07 uur uit te schakelen, en om 14:09 uur waren het verkeer en de CPU-niveaus overal weer normaal. De rest van de beschermingsmechanismen van Cloudflare werkten normaal.
Daarna begonnen we met het herstellen van de WAF. De situatie was buitengewoon, dus hebben we in één stad negatieve tests uitgevoerd (waarbij we ons afvroegen of de verandering echt het probleem was) en positieve tests (om er zeker van te zijn dat het terugdraaien werkte), waarbij we betalende klanten van daaruit overbrachten.
Om 14:52 waren we ervan overtuigd dat we de reden begrepen, voerden een correctie uit en schakelden WAF opnieuw in.
Hoe Cloudflare werkt
Cloudflare heeft een team van ingenieurs die zich toeleggen op het beheren van regels voor WAF's. Ze streven ernaar het detectiepercentage te verbeteren, het aantal valse positieven te verminderen en snel te reageren op nieuwe bedreigingen zodra deze zich voordoen. In de afgelopen 60 dagen zijn er 476 wijzigingsverzoeken verwerkt voor beheerde regels voor WAF (gemiddeld één per drie uur).
Deze specifieke wijziging moest worden geïmplementeerd in de simulatiemodus, waarbij echt clientverkeer de regel passeert, maar niets wordt geblokkeerd. We gebruiken deze modus om de effectiviteit van de regels te testen en de fout-positieve en fout-negatieve percentages te meten. Maar zelfs in de simulatiemodus moeten de regels daadwerkelijk worden uitgevoerd, en in dit geval bevatte de regel een reguliere expressie die te veel processorbronnen in beslag nam.
Zoals u kunt zien in het wijzigingsverzoek hierboven, hebben we een implementatieplan, een rollback-plan en een link naar een interne standaard operationele procedure (SOP) voor dit type implementatie. De SOP voor het wijzigen van een regel maakt het mogelijk dat deze wereldwijd wordt gepubliceerd. Eigenlijk worden de zaken bij Cloudflare compleet anders gedaan, en de SOP schrijft voor dat we de software eerst voor testen en intern gebruik verzenden naar een intern punt van aanwezigheid (PoP) (dat onze medewerkers gebruiken), en vervolgens naar een klein aantal klanten in een geïsoleerde locatie, vervolgens naar een groot aantal klanten, en dan pas naar de hele wereld.
Dit is hoe het eruit ziet. We gebruiken git intern via BitBucket. Ingenieurs die aan wijzigingen werken, dienen code in, die in TeamCity wordt gebouwd, en wanneer de build is voltooid, worden reviewers toegewezen. Zodra een pull request is goedgekeurd, wordt de code samengesteld en wordt er (opnieuw) een reeks tests uitgevoerd.
Als de build en tests succesvol zijn afgerond, wordt er een wijzigingsverzoek aangemaakt in Jira en moet de betreffende manager of lead de wijziging goedkeuren. Na goedkeuring vindt inzet plaats in de zogenaamde “PoP menagerie”: DOG, PIG en (hond, varken en kanarie).
DOG PoP is een Cloudflare PoP (zoals elke andere stad) die alleen wordt gebruikt door Cloudflare-medewerkers. Met PoP voor intern gebruik kunt u problemen onderkennen voordat het klantverkeer de oplossing binnenstroomt. Nuttig ding.
Als de DOG-test succesvol is, gaat de code naar de PIG-fase (cavia). Dit is Cloudflare PoP, waarbij een kleine hoeveelheid gratis klantenverkeer via nieuwe code stroomt.
Als alles goed is, gaat de code naar Canary. We hebben drie Canarische PoP's in verschillende delen van de wereld. Daarin passeert het verkeer van betaalde en gratis klanten de nieuwe code, en dit is de laatste controle op fouten.
Softwarereleaseproces bij Cloudflare
Als de code in Canary in orde is, geven we deze vrij. Het doorlopen van alle fasen - DOG, PIG, Canary, de hele wereld - duurt enkele uren of dagen, afhankelijk van de codewijziging. Vanwege de diversiteit van het netwerk en de klanten van Cloudflare testen we de code grondig voordat we deze wereldwijd vrijgeven aan alle klanten. Maar WAF volgt dit proces niet specifiek omdat er snel op bedreigingen moet worden gereageerd.
WAF-bedreigingen
De afgelopen jaren is het aantal bedreigingen in veelgebruikte toepassingen aanzienlijk toegenomen. Dit komt door de grotere beschikbaarheid van softwaretesttools. We schreven er bijvoorbeeld onlangs over ).
Bron:
Heel vaak wordt er een proof of concept gemaakt en onmiddellijk op Github gepubliceerd, zodat de teams die de applicatie onderhouden deze snel kunnen testen en ervoor kunnen zorgen dat deze voldoende beveiligd is. Daarom heeft Cloudflare de mogelijkheid nodig om zo snel mogelijk op nieuwe aanvallen te reageren, zodat klanten de mogelijkheid hebben om hun software te repareren.
Een goed voorbeeld van de snelle reactie van Cloudflare is de implementatie van SharePoint-kwetsbaarheidsbescherming in mei (). Vrijwel onmiddellijk nadat de aankondigingen waren gedaan, merkten we een groot aantal pogingen op om misbruik te maken van de kwetsbaarheid in de SharePoint-installaties van onze klanten. Onze jongens houden voortdurend nieuwe bedreigingen in de gaten en schrijven regels om onze klanten te beschermen.
De regel die donderdag het probleem veroorzaakte, moest bescherming bieden tegen cross-site scripting (XSS). Dergelijke aanvallen komen de afgelopen jaren ook veel vaker voor.
Bron:
De standaardprocedure voor het wijzigen van een beheerde regel voor een WAF is het uitvoeren van continue integratietests (CI) vóór de wereldwijde implementatie. Afgelopen donderdag hebben we dit gedaan en de regels uitgerold. Om 13 uur diende een ingenieur een goedgekeurde pull-aanvraag met een wijziging in.
Om 13:37 verzamelde TeamCity de regels, voerde tests uit en gaf groen licht. De WAF-testsuite test de kernfunctionaliteit van de WAF en bestaat uit een groot aantal unit-tests voor individuele functies. Na unit-tests hebben we de regels voor de WAF getest met behulp van een groot aantal HTTP-verzoeken. HTTP-verzoeken controleren welke verzoeken door de WAF moeten worden geblokkeerd (om de aanval te onderscheppen) en welke kunnen worden doorgelaten (om niet alles te blokkeren en valse positieven te voorkomen). Maar we hebben niet getest op overmatig CPU-gebruik, en onderzoek van de logs van eerdere WAF-builds laat zien dat de uitvoeringstijd van de regeltest niet toenam, en het was moeilijk te vermoeden dat er niet genoeg bronnen zouden zijn.
De tests zijn geslaagd en TeamCity begon de wijziging om 13 uur automatisch door te voeren.
Kwikzilver
WAF-regels zijn gericht op onmiddellijk herstel van bedreigingen, dus implementeren we ze met behulp van Quicksilver's gedistribueerde sleutelwaardearchief, dat veranderingen binnen enkele seconden wereldwijd doorvoert. Al onze klanten gebruiken deze technologie als ze de configuratie in het dashboard of via de API wijzigen en dankzij deze technologie spelen we razendsnel in op veranderingen.
We hebben niet veel over Quicksilver gesproken. Vroeger gebruikten we als een wereldwijd gedistribueerde winkel met sleutelwaarde, maar er waren operationele problemen mee, en we schreven onze eigen winkel, die in meer dan 180 steden werd gekopieerd. We gebruiken nu Quicksilver om configuratiewijzigingen naar clients te pushen, WAF-regels bij te werken en door clients geschreven JavaScript-code te distribueren naar Cloudflare Workers.
Het duurt slechts een paar seconden vanaf het klikken op een knop op een dashboard of het aanroepen van een API tot het wereldwijd doorvoeren van een configuratiewijziging. Klanten waren dol op deze installatiesnelheid. En Workers biedt hen vrijwel onmiddellijke wereldwijde software-implementatie. Gemiddeld propageert Quicksilver ongeveer 350 wijzigingen per seconde.
En Quicksilver is erg snel. Gemiddeld bereikten we het 99e percentiel van 2,29 seconden om wijzigingen door te geven aan elke computer wereldwijd. Snelheid is meestal een goede zaak. Wanneer u een functie inschakelt of de cache leegmaakt, gebeurt dit immers vrijwel onmiddellijk en overal. Het verzenden van code via Cloudflare Workers gebeurt met dezelfde snelheid. Cloudflare belooft zijn klanten snelle updates op het juiste moment.
Maar in dit geval speelde snelheid een wrede grap met ons, en de regels veranderden overal binnen enkele seconden. Het is je misschien opgevallen dat de WAF-code Lua gebruikt. Cloudflare gebruikt Lua uitgebreid bij de productie en details we . Lua WAF-gebruik intern en past backtracking toe voor matching. Het beschikt niet over mechanismen die bescherming bieden tegen uit de hand gelopen uitingen. Hieronder vertel ik er meer over en wat we eraan doen.
Voordat de regels werden geïmplementeerd, verliep alles soepel: het pull-verzoek werd gemaakt en goedgekeurd, de CI/CD-pijplijn verzamelde en testte de code, het wijzigingsverzoek werd ingediend volgens de SOP die de implementatie en het terugdraaien regelt, en de implementatie was voltooid.
Cloudflare WAF-implementatieproces
Er is iets fout gegaan
Zoals ik al zei, implementeren we elke week tientallen nieuwe WAF-regels, en we hebben veel systemen om ons te beschermen tegen de negatieve gevolgen van een dergelijke implementatie. En als er iets misgaat, is dat meestal een combinatie van meerdere omstandigheden tegelijk. Als je maar één reden vindt, is dat natuurlijk geruststellend, maar het is niet altijd waar. Dit zijn de redenen die samen hebben geleid tot het falen van onze HTTP/HTTPS-service.
- Een ingenieur schreef een reguliere expressie die tot excessief kon leiden .
- Een functie die had kunnen voorkomen dat de reguliere expressie te veel CPU verspilde, werd enkele weken eerder per abuis verwijderd bij een refactoring van de WAF - de refactoring was nodig om de WAF minder bronnen te laten verbruiken.
- De reguliere expressie-engine had geen garanties op complexiteit.
- De testsuite kon geen overmatig CPU-verbruik detecteren.
- Dankzij de SOP kunnen niet-dringende regelwijzigingen wereldwijd worden uitgerold zonder een proces dat uit meerdere stappen bestaat.
- Het rollback-plan vereiste dat er twee keer een volledige WAF-build moest worden uitgevoerd, wat lang duurde.
- De eerste waarschuwing over mondiale verkeersproblemen kwam te laat.
- Het heeft even geduurd voordat de statuspagina werd bijgewerkt.
- We hadden problemen met de toegang tot systemen vanwege een storing en de bypass-procedure was niet goed ingesteld.
- SRE-technici hebben om veiligheidsredenen de toegang tot sommige systemen verloren omdat hun inloggegevens zijn verlopen.
- Onze klanten hadden geen toegang tot het Cloudflare-dashboard of API omdat ze via een Cloudflare-regio gaan.
Wat is er veranderd sinds afgelopen donderdag
Ten eerste hebben we al het werk aan releases voor WAF volledig stopgezet en doen we het volgende:
- We introduceren opnieuw de CPU-overbelastingsbeveiliging die we hebben verwijderd. (Klaar)
- Het handmatig controleren van alle 3868 regels in de beheerde regels zodat de WAF andere potentiële gevallen van buitensporige backtracking kan vinden en corrigeren. (Verificatie voltooid)
- We nemen prestatieprofilering op voor alle regels in de testset. (Verwacht: 19 juli)
- Overschakelen naar een reguliere expressie-engine of - beide bieden runtime-garanties. (Verwacht: 31 juli)
- We herschrijven de SOP om de regels in fasen te implementeren, net als andere software in Cloudflare, maar hebben tegelijkertijd de mogelijkheid om een wereldwijde implementatie in noodgevallen uit te voeren als de aanvallen al zijn begonnen.
- We ontwikkelen de mogelijkheid om het Cloudflare-dashboard en de API dringend uit de Cloudflare-regio te verwijderen.
- Pagina-updates automatiseren .
Op de lange termijn wijken we af van de Lua WAF die ik een paar jaar geleden schreef. WAF verplaatsen naar . Op deze manier zal de WAF sneller zijn en een extra beschermingsniveau krijgen.
Conclusie
Deze storing veroorzaakte problemen voor ons en onze klanten. We hebben snel gehandeld om de situatie te corrigeren en werken nu aan de fouten in de processen die de crash hebben veroorzaakt, en zijn nog dieper aan het graven om ons te beschermen tegen mogelijke problemen met reguliere expressies in de toekomst bij de migratie naar nieuwe technologie.
Wij schamen ons zeer voor deze storing en bieden onze excuses aan aan onze klanten. We hopen dat deze veranderingen ervoor zorgen dat zoiets niet nog een keer gebeurt.
Sollicitatie. Terugkeren van reguliere expressies
Om te begrijpen hoe de uitdrukking:
(?:(?:"|'|]|}||d
(?:nan|infinity|true|false|null|undefined|symbol|math)|`|-
|+)+[)]*;?((?:s|-|~|!|{}||||+)*.*(?:.*=.*)))Als je alle CPU-bronnen hebt opgegeten, moet je iets weten over hoe de standaard reguliere expressie-engine werkt. Het probleem hier is het patroon .*(?:.*=.*). (?: en corresponderend ) is een niet-vastleggende groep (dat wil zeggen: de expressie tussen haakjes is gegroepeerd als een enkele expressie).
In de context van overmatig CPU-verbruik kan dit patroon worden omschreven als .*.*=.*. In deze vorm ziet het patroon er onnodig ingewikkeld uit. Maar wat nog belangrijker is, in de echte wereld kunnen expressies (zoals complexe expressies in WAF-regels) die de engine vragen een fragment te matchen gevolgd door een ander fragment, tot catastrofale backtracking leiden. En dat is waarom.
In reguliere expressie . betekent dat je één karakter moet matchen, .* - match nul of meer karakters "gretig", dat wil zeggen, het vastleggen van een maximum aan karakters, zodat .*.*=.* betekent: match nul of meer karakters, match dan nul of meer karakters, zoek het letterlijke = karakter, match nul of meer karakters.
Laten we de testlijn nemen x=x. Het komt overeen met de uitdrukking .*.*=.*. .*.* voordat het gelijkteken overeenkomt met het eerste x (een van de groepen .* komt overeen met xen de tweede - nul tekens). .* na = laatste wedstrijden x.
Deze vergelijking vereist 23 stappen. Eerste groep .* в .*.*=.* handelt gretig en matcht de hele string x=x. De motor gaat naar de volgende groep .*. We hebben geen overeenkomende karakters meer, dus de tweede groep .* komt overeen met nul tekens (dit is toegestaan). Dan beweegt de motor naar het bord =. Er zijn geen symbolen meer (eerste groep .* gebruikte de hele uitdrukking x=x), vindt er geen vergelijking plaats.
En dan keert de reguliere expressie-engine terug naar het begin. Hij gaat door naar de eerste groep .* en vergelijkt het с x= (in plaats van x=x), en neemt het vervolgens op tegen de tweede groep .*. Tweede groep .* wordt vergeleken met de tweede x, en we hebben opnieuw geen karakters meer. En wanneer de motor weer bereikt = в .*.*=.*, niks werkt. En hij trekt zich weer terug.
Dit keer de groep .* komt nog steeds overeen x=, maar de tweede groep .* niet meer xen nul tekens. De engine probeert een letterlijk karakter te vinden = in het patroon .*.*=.*, maar komt er niet uit (de eerste groep heeft het immers al bezet .*). En hij trekt zich weer terug.
Dit keer de eerste groep .* neemt alleen de eerste x. Maar de tweede groep .* "gretig" vangt =x. Heeft u al geraden wat er gaat gebeuren? De motor probeert de letterlijke te evenaren =, mislukt en maakt opnieuw een backtracking.
De eerste groep .* komt nog steeds overeen met de eerste x. Seconde .* neemt alleen maar =. Natuurlijk kan de motor niet tippen aan de letterlijke =, omdat de tweede groep dit al heeft gedaan .*. En weer achteruit. En we proberen een reeks van drie karakters te matchen!
Als gevolg hiervan, de eerste groep .* komt alleen overeen met de eerste x, seconde .* - met nul tekens, en de engine komt eindelijk overeen met de letterlijke waarde = in expressie с = in lijn. Hierna volgt de laatste groep .* wordt vergeleken met de vorige x.
23 stappen alleen voor x=x. Bekijk een korte video over het gebruik van Perl , die laat zien hoe stappen en backtracking plaatsvinden.
Dit is al een hoop werk, maar wat als dat in plaats daarvan gebeurt? x=x we zullen hebben x=xx? Dat zijn 33 stappen. En als x=xxx? 45. De relatie is niet lineair. De grafiek toont een vergelijking van x=x naar x=xxxxxxxxxxxxxxxxxxxx (20 x na =). Als we 20x daarna hebben =, voltooit de motor de matching in 555 stappen! (Bovendien, als we verloren hebben x= en de string bestaat eenvoudigweg uit 20 x, zal de engine 4067 stappen ondernemen om te begrijpen dat er geen overeenkomsten zijn).
Deze video toont alle backtracking ter vergelijking x=xxxxxxxxxxxxxxxxxxxx:
Het probleem is dat naarmate de tekenreeks groter wordt, de matchingtijd superlineair groeit. Maar het kan nog erger worden als de reguliere expressie enigszins wordt gewijzigd. Laten we zeggen dat we dat hadden gedaan .*.*=.*; (dat wil zeggen, er stond een letterlijke puntkomma aan het einde van het patroon). Om bijvoorbeeld een uitdrukking als foo=bar;.
En hier zou teruggaan een echte ramp zijn. Ter vergelijking x=x er zijn 90 stappen nodig, geen 23. En dat aantal groeit snel. Om te vergelijken x= en 20 x, zijn 5353 stappen nodig. Hier is de grafiek. Kijk naar de aswaarden Y vergeleken met de vorige grafiek.
Als je geïnteresseerd bent, bekijk dan alle 5353 mislukte matchingstappen x=xxxxxxxxxxxxxxxxxxxx и .*.*=.*;
Door luie in plaats van hebzuchtige matching te gebruiken, kan de mate van backtracking worden gecontroleerd. Als we de oorspronkelijke uitdrukking veranderen in .*?.*?=.*?, ter vergelijking x=x er zijn 11 stappen nodig (niet 23). Wat betreft x=xxxxxxxxxxxxxxxxxxxx. Allemaal omdat ? na .* vertelt de engine dat hij een minimum aantal tekens moet matchen voordat hij verder gaat.
Maar luie mappings lossen het backtrackingprobleem niet volledig op. Als we het catastrofale voorbeeld vervangen .*.*=.*; op .*?.*?=.*?;, de uitvoeringstijd blijft hetzelfde. x=x vereist nog steeds 555 stappen, en x= en 20 x - 5353.
Het enige dat gedaan kan worden (naast het volledig herschrijven van het patroon voor meer specificiteit) is het verlaten van de reguliere expressie-engine met zijn backtracking-mechanisme. Dit is wat wij de komende weken gaan doen.
De oplossing voor dit probleem is bekend sinds 1968, toen Kent Thompson een artikel schreef (“Programmeermethoden: zoekalgoritme voor reguliere expressies”). Het artikel beschrijft een mechanisme waarmee je een reguliere expressie kunt omzetten in niet-deterministische eindige-toestandsmachines, en na toestandsveranderingen in niet-deterministische eindige-toestandsmachines een algoritme kunt gebruiken waarvan de uitvoeringstijd lineair afhangt van de overeenkomende string.
Programmeermethoden
Zoekalgoritme voor reguliere expressies
Ken Thompson
Bell Telephone Laboratories, Inc., Murray Hill, New JerseyHet beschrijft een methode voor het zoeken naar een specifieke reeks tekens in tekst en bespreekt de implementatie van deze methode in compilervorm. De compiler neemt de reguliere expressie als broncode en produceert het IBM 7094-programma als objectcode. Het objectprogramma neemt invoer in de vorm van zoektekst en zendt een signaal uit telkens wanneer een tekstreeks wordt vergeleken met een gegeven reguliere expressie. Het artikel geeft voorbeelden, problemen en oplossingen.
Het algoritme
Eerdere zoekalgoritmen resulteerden in backtracking als een gedeeltelijk succesvolle zoekopdracht geen resultaat opleverde.In de compilatiemodus werkt het algoritme niet met symbolen. Het geeft instructies door aan gecompileerde code. De uitvoering is erg snel: nadat de gegevens bovenaan de huidige lijst zijn geplaatst, wordt automatisch gezocht naar alle mogelijke opeenvolgende tekens in de reguliere expressie.
Het compilatie- en zoekalgoritme is als contextueel zoeken in de timesharing-teksteditor opgenomen. Dit is uiteraard verre van de enige toepassing van een dergelijke zoekprocedure. Een variant van dit algoritme wordt bijvoorbeeld gebruikt als symboolzoekopdracht in een tabel in assembler.
Er wordt aangenomen dat de lezer bekend is met reguliere expressies en de computerprogrammeertaal IBM 7094.Compiler
De compiler bestaat uit drie fasen die parallel lopen. De eerste fase is syntaxisfiltering, waardoor alleen syntactisch correcte reguliere expressies worden doorgelaten. Deze stap voegt ook de operator "·" in om reguliere expressies te matchen. In de tweede stap wordt de reguliere expressie geconverteerd naar een postfix-vorm. In de derde fase wordt objectcode gemaakt. De eerste twee fasen liggen voor de hand en we zullen er niet bij stilstaan.
Het artikel van Thompson spreekt niet over niet-deterministische eindige toestandsmachines, maar legt wel het lineaire tijdalgoritme goed uit en presenteert een ALGOL-60-programma dat assembleertaalcode genereert voor de IBM 7094. De implementatie is lastig, maar het idee is heel eenvoudig.
huidige zoekpad. Het wordt weergegeven door een ⊕-pictogram met één ingang en twee uitgangen.
Figuur 1 toont de functies van de derde compilatiestap bij het transformeren van een voorbeeld van een reguliere expressie. De eerste drie tekens in het voorbeeld zijn a, b, c, en elk creëert een stapelinvoer S[i] en een NNODE-veld.NNODE naar bestaande code om de resulterende reguliere expressie in één enkele stapelinvoer te genereren (zie afbeelding 5)
Dit is hoe een reguliere expressie eruit zou zien .*.*=.*, als je het je voorstelt zoals op de afbeeldingen uit het artikel van Thompson.
In afb. 0 zijn er vijf toestanden die beginnen bij 0, en 3 cycli die beginnen bij toestanden 1, 2 en 3. Deze drie cycli komen overeen met drie .* in een reguliere expressie. 3 ovalen met stippen komen overeen met één symbool. Ovaal met een teken = komt overeen met een letterlijk karakter =. Staat 4 is definitief. Als we dit bereiken, wordt de reguliere expressie gematcht.
Om te zien hoe een dergelijk toestandsdiagram kan worden gebruikt voor het matchen van reguliere expressies .*.*=.*, kijken we naar stringmatching x=x. Het programma begint vanaf status 0, zoals weergegeven in Fig. 1.
Om dit algoritme te laten werken, moet de toestandsmachine zich tegelijkertijd in verschillende toestanden bevinden. Een niet-deterministische eindige machine zal alle mogelijke overgangen tegelijkertijd maken.
Voordat het tijd heeft om de invoergegevens te lezen, gaat het naar beide eerste toestanden (1 en 2), zoals weergegeven in figuur 2. XNUMX.
In afb. 2 laat zien wat er gebeurt als hij naar de eerste kijkt x в x=x. x kan naar het bovenste punt toewijzen, gaande van toestand 1 en terug naar toestand 1. Or x kan naar het onderstaande punt verwijzen, gaande van toestand 2 en terug naar toestand 2.
Na het matchen van de eerste x в x=x we bevinden ons nog steeds in toestand 1 en 2. We kunnen toestand 3 of 4 niet bereiken omdat we een letterlijk karakter nodig hebben =.
Het algoritme overweegt vervolgens = в x=x. Net als x ervoor kan het worden gekoppeld aan een van de twee bovenste lussen van toestand 1 naar toestand 1 of van toestand 2 naar toestand 2, maar het algoritme kan overeenkomen met de letterlijke = en ga van toestand 2 naar toestand 3 (en onmiddellijk 4). Dit wordt getoond in Afb. 3.
Het algoritme gaat vervolgens verder met de laatste x в x=x. Vanuit toestand 1 en 2 zijn dezelfde overgangen mogelijk terug naar toestand 1 en 2. Vanaf toestand 3 x kan overeenkomen met het punt aan de rechterkant en teruggaan naar toestand 3.
In dit stadium elk personage x=x overwogen, en aangezien we status 4 hebben bereikt, komt de reguliere expressie overeen met die string. Elk teken wordt één keer verwerkt, dus dit algoritme is lineair in de lengte van de invoertekenreeks. En geen terugkoppeling.
Het is duidelijk dat na het bereiken van toestand 4 (wanneer het algoritme is gematcht). x=) de gehele reguliere expressie wordt gematcht, en het algoritme kan eindigen zonder er überhaupt rekening mee te houden x.
Dit algoritme hangt lineair af van de grootte van de invoerreeks.
Bron: www.habr.com