Bijna 9 jaar geleden was Cloudflare een klein bedrijfje, en ik werkte er niet voor, ik was gewoon een klant. Een maand na de lancering van Cloudflare kreeg ik een melding dat mijn website DNS lijkt down te zijn. Cloudflare heeft een wijziging aangebracht in , en er was een kapotte DNS.
Ik schreef onmiddellijk naar Matthew Prince met als onderwerp "Waar is mijn DNS?", en hij stuurde een lang, technisch antwoord (), waarop ik antwoordde:
Van: John Graham-Cumming
Datum: 7 oktober 2010, 9:14
Onderwerp: Re: Waar is mijn DNS?
Aan: Matthew PrinceGeweldig rapport, bedankt. Ik bel zeker als er problemen zijn. Misschien moet ik er een blogpost over schrijven zodra je alle technische informatie bij elkaar hebt. Ik denk dat mensen een open en eerlijk verhaal zouden waarderen. Vooral als je er grafieken bij zou voegen om te laten zien hoe het verkeer sinds de lancering is gegroeid.
Ik heb een goede monitoring op mijn site en ontvang een sms-bericht over elke storing. De monitoring geeft aan dat de storing plaatsvond van 13:03:07 tot 14:04:12. Er worden elke vijf minuten tests uitgevoerd.
Ik weet zeker dat je er wel uitkomt. Weet je zeker dat je geen eigen man in Europa nodig hebt? 🙂
En hij antwoordde:
Van: Matthew Prince
Datum: 7 oktober 2010, 9:57
Onderwerp: Re: Waar is mijn DNS?
Aan: John Graham-CummingBedankt. We hebben iedereen die ons geschreven heeft, beantwoord. Ik ben nu onderweg naar kantoor en we zullen iets op de blog schrijven of een officieel bericht op ons prikbord hangen. Ik ben het er helemaal mee eens, eerlijkheid is alles.
Cloudflare is inmiddels een heel groot bedrijf, ik werk er en nu moet ik openlijk schrijven over onze fout, de gevolgen ervan en onze acties.
Gebeurtenissen van 2 juli
Op 2 juli hebben we een nieuwe regel in Managed Rules voor WAF geïmplementeerd die op elke CPU-kern die HTTP/HTTPS-verkeer verwerkt in het netwerk van Cloudflare wereldwijd. We verbeteren voortdurend beheerde regels voor WAF als reactie op nieuwe kwetsbaarheden en bedreigingen. In mei hebben we bijvoorbeeld snel actie ondernomen ter bescherming tegen een ernstige kwetsbaarheid in SharePoint. Het hele punt van onze WAF is de mogelijkheid om snel en wereldwijd regels te implementeren.
Helaas bevatte de update van afgelopen donderdag een reguliere expressie die te veel van de HTTP/HTTPS CPU gebruikte voor backtracking. Dit had invloed op de functionaliteit van onze kernproxy, CDN en WAF. De grafiek laat zien dat de CPU voor het verwerken van HTTP/HTTPS-verkeer bijna 100% bereikt op servers in ons netwerk.
CPU-gebruik op een van de aanwezigheidspunten tijdens het incident
Wat er uiteindelijk gebeurde, was dat onze klanten (en de klanten van onze klanten) 502-foutpagina's tegenkwamen op Cloudflare-domeinen. De 502-fouten werden gegenereerd door de front-end webservers van Cloudflare, die nog wel cores beschikbaar hadden, maar geen contact konden maken met de processen die HTTP/HTTPS-verkeer afhandelden.
We weten hoeveel ongemak dit onze klanten heeft bezorgd. We schamen ons diep. En door deze storing konden we het incident niet effectief afhandelen.
Als je een van die klanten was, was je waarschijnlijk bang, boos en overstuur. Bovendien hebben we er al zes jaar geen meer gehad. Het hoge CPU-gebruik werd veroorzaakt door een enkele WAF-regel met een slecht geformuleerde reguliere expressie die resulteerde in overmatig backtracking. Dit is de boosdoener: (?:(?:"|'|]|}||d|(?:nan|infinity|true|false|null|undefined|symbol|math)|`|-|+)+[)]*;?((?:s|-|~|!|{}||||+)*.*(?:.*=.*)))
Hoewel het op zichzelf al interessant is (en daarover later meer), was het niet alleen een slechte regex die ervoor zorgde dat Cloudflare 27 minuten plat lag. Het duurde even voordat we de gebeurtenissen die tot de storing leidden beschreven, dus het duurde even voordat we reageerden. Aan het einde van dit bericht bespreek ik regex backtracking en wat je eraan kunt doen.
Wat is er gebeurd
Laten we bij het begin beginnen. Alle tijden hier zijn in UTC.
Om 13:42 uur heeft een technicus van het firewallteam een kleine wijziging aangebracht in de detectieregels via een geautomatiseerd proces. Er is een ticket voor een wijzigingsverzoek aangemaakt. We beheren dergelijke tickets via Jira (screenshot hieronder).
Binnen 3 minuten verscheen de eerste PagerDuty-pagina met een melding van een WAF-probleem. Het was een synthetische test die de functionaliteit van WAF (we hebben er honderden) buiten Cloudflare testte om te controleren of deze goed functioneerde. Al snel volgden pagina's met meldingen van fouten in andere end-to-end Cloudflare-servicetests, wereldwijde verkeersproblemen, wijdverspreide 502-fouten en een reeks rapporten van onze PoP's in steden over de hele wereld die wezen op CPU-knelpunten.
Ik kreeg een paar van deze meldingen, verliet de vergadering en was op weg naar de tafel toen onze hoofdoplossingen me vertelden dat we 80% van ons verkeer kwijt waren. Ik rende naar onze SRE-engineers die al aan het probleem werkten. In eerste instantie dachten we dat het een onbekende aanval was.
De SRE's van Cloudflare zijn wereldwijd verspreid en monitoren de situatie 0/XNUMX. Deze meldingen gaan doorgaans over specifieke, lokale problemen van beperkte omvang, die worden bijgehouden op interne dashboards en meerdere keren per dag worden opgelost. Deze pagina's en meldingen gaven echter aan dat er iets ernstigs aan de hand was, en de SRE's verhoogden het ernstniveau onmiddellijk naar PXNUMX en namen contact op met het management en de systeemtechnici.
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 vergaderzaal en er werden meer specialisten opgeroepen. Dit was geen typisch probleem dat SRE alleen kon oplossen. De juiste specialisten moesten direct worden ingezet.
Om 14:00 uur stelden we vast dat de WAF het probleem was en dat er geen aanval was geweest. Het performanceteam verzamelde CPU-gegevens en het werd duidelijk dat de WAF de boosdoener was. Een ander teamlid bevestigde deze theorie met behulp van strace. Iemand anders zag in de logs dat de WAF het probleem was. Om 14:02 uur kwam het hele team naar mij toe met het voorstel om een global kill te gebruiken – een mechanisme ingebouwd in Cloudflare dat één component wereldwijd uitschakelt.
Hoe we WAF wereldwijd hebben verslagen, is een verhaal apart. Zo eenvoudig is het niet. We gebruiken onze eigen producten en omdat onze service niet werkte, konden we ons niet authenticeren en inloggen op het interne controlepaneel (toen alles was opgelost, kwamen we erachter dat sommige teamleden toegang verloren vanwege een beveiligingsfunctie die inloggegevens uitschakelt als het interne controlepaneel gedurende een langere tijd niet wordt gebruikt).
En we konden onze interne services, zoals Jira of het buildsysteem, niet bereiken. We hadden een tijdelijke oplossing nodig, die we niet vaak gebruikten (ook hieraan moet gewerkt worden). Uiteindelijk slaagde een engineer erin om de WAF om 14:07 uur uit te schakelen, en om 14:09 uur waren het dataverkeer en de CPU-niveaus overal weer normaal. De rest van Cloudflare's verdediging werkte zoals gebruikelijk.
Vervolgens zijn we begonnen met het herstellen van de WAF. De situatie was ongewoon, dus hebben we negatieve tests uitgevoerd (om onszelf af te vragen of deze wijziging echt het probleem was) en positieve tests (om te controleren of de terugdraaiing werkte) in één stad met gescheiden verkeer, en de betalende klanten van daaruit overgezet.
Om 14:52 uur wisten we zeker dat we de oorzaak hadden gevonden, het probleem hadden opgelost en de WAF opnieuw hadden ingeschakeld.
Hoe Cloudflare werkt
Cloudflare heeft een team van engineers dat zich volledig toelegt op Managed Rules voor WAF. Ze streven ernaar de detectiepercentages te verbeteren, het aantal foutpositieve meldingen te verminderen en snel te reageren op nieuwe bedreigingen zodra deze zich voordoen. In de afgelopen 60 dagen zijn er 476 wijzigingsverzoeken voor Managed Rules voor WAF verwerkt (gemiddeld één per 3 uur).
Deze specifieke wijziging moest worden geïmplementeerd in de simulatiemodus, waarbij echt klantverkeer de regel passeert, maar er niets wordt geblokkeerd. We gebruiken deze modus om de effectiviteit van regels te testen en het aantal foutpositieve en foutnegatieve resultaten 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 CPU verbruikte.
Zoals u kunt zien in het bovenstaande wijzigingsverzoek, hebben we een implementatieplan, een rollbackplan en een link naar een interne standaardwerkprocedure (SOP) voor dit type implementatie. De SOP voor de regelwijziging staat wereldwijde publicatie toe. Bij Cloudflare is de situatie echter heel anders. De SOP schrijft voor dat de software eerst moet worden gepusht naar een interne PoP (die door onze medewerkers wordt gebruikt) voor testen en intern gebruik, vervolgens naar een klein aantal klanten op een afgelegen locatie, vervolgens naar een groot aantal klanten en ten slotte naar de rest van de wereld.
Zo ziet het eruit. We gebruiken Git intern via BitBucket. Engineers die aan wijzigingen werken, pushen code, die in TeamCity wordt gebouwd. Wanneer de build is goedgekeurd, worden er reviewers aangesteld. Wanneer de pull-request is goedgekeurd, wordt de code gebouwd en worden er (opnieuw) een reeks tests uitgevoerd.
Als de build en tests succesvol zijn afgerond, wordt er een wijzigingsverzoek aangemaakt in Jira en moet de wijziging worden goedgekeurd door de juiste manager of lead. Na goedkeuring wordt deze geïmplementeerd in de zogenaamde "PoP-menagerie": DOG, PIG en (hond, varken en kanarie).
DOG PoP is een Cloudflare PoP (net als al onze andere steden) die alleen door Cloudflare-medewerkers wordt gebruikt. Een PoP voor intern gebruik stelt je in staat problemen op te sporen voordat de oplossing klantenverkeer begint te ontvangen. Handig.
Als de DOG-test slaagt, gaat de code naar de PIG-fase (proefkonijn). Dit is Cloudflare PoP, waarbij een kleine hoeveelheid gratis klantverkeer via de nieuwe code wordt doorgestuurd.
Als alles in orde is, gaat de code naar Canary. We hebben drie Canary PoP's in verschillende delen van de wereld. Zij voeren de nieuwe code uit via betaald en gratis klantverkeer, en dit is de laatste controle op fouten.
Het softwarereleaseproces van Cloudflare
Als de code in Canary in orde is, geven we deze vrij. Het doorlopen van alle fasen – DOG, PIG, Canary, wereldwijd – duurt een paar uur of dagen, afhankelijk van de codewijziging. Vanwege het diverse netwerk en de diverse klanten van Cloudflare testen we de code grondig voordat we deze wereldwijd aan alle klanten vrijgeven. WAF volgt dit proces echter niet bewust, omdat bedreigingen snel moeten worden aangepakt.
WAF-bedreigingen
De afgelopen jaren is het aantal bedreigingen in gangbare applicaties aanzienlijk toegenomen. Dit komt door de grotere beschikbaarheid van softwaretesttools. We schreven er bijvoorbeeld onlangs over ).
Bron:
Vaak wordt een proof of concept gemaakt en direct op Github gepubliceerd, zodat de teams die de applicatie beheren deze snel kunnen testen en ervoor kunnen zorgen dat deze adequaat beschermd is. Cloudflare moet dus zo snel mogelijk kunnen reageren op nieuwe aanvallen, zodat klanten de kans krijgen hun software te repareren.
Een goed voorbeeld van de snelle reactie van Cloudflare is de uitrol van bescherming tegen de kwetsbaarheid van SharePoint in mei (Vrijwel direct na de publicatie van de aankondigingen zagen we een groot aantal pogingen om de kwetsbaarheid in de SharePoint-installaties van onze klanten te misbruiken. Onze mensen houden voortdurend nieuwe bedreigingen in de gaten en schrijven regels om onze klanten te beschermen.
De regel die donderdag voor het probleem zorgde, was bedoeld als bescherming tegen cross-site scripting (XSS), een aanval die de laatste jaren ook steeds vaker voorkomt.
Bron:
De standaardprocedure voor het wijzigen van een beheerde regel voor een WAF is het uitvoeren van CI-tests (Continuous Integration) voordat deze wereldwijd wordt geïmplementeerd. Afgelopen donderdag hebben we dat gedaan en de regels geïmplementeerd. Om 13:31 uur diende een engineer een goedgekeurde pull request in met de wijziging.
Om 13:37 uur verzamelde TeamCity de regels, voerde de tests uit en gaf groen licht. De WAF-testsuite test de kernfunctionaliteit van de WAF en bestaat uit een groot aantal unittests voor individuele functies. Na de unittests testten we de WAF-regels met een groot aantal HTTP-verzoeken. De HTTP-verzoeken controleren welke verzoeken door de WAF moeten worden geblokkeerd (om de aanval te onderscheppen) en welke kunnen worden doorgelaten (om te voorkomen dat alles wordt geblokkeerd en om foutpositieve resultaten te voorkomen). We hebben echter niet getest op overmatig CPU-gebruik. Uit onderzoek van de logs van eerdere WAF-builds blijkt dat de uitvoeringstijd van de test met de regel niet toenam en dat het moeilijk te vermoeden was dat er onvoldoende resources waren.
De tests waren succesvol en TeamCity begon om 13:42 uur automatisch met het doorvoeren van de wijziging.
Kwikzilver
WAF-regels zijn ontworpen om bedreigingen direct aan te pakken. Daarom implementeren we ze met Quicksilver, een gedistribueerde sleutel-waardeopslag die wijzigingen wereldwijd binnen enkele seconden distribueert. Al onze klanten gebruiken deze technologie wanneer ze configuraties wijzigen in het dashboard of via de API, en het stelt ons in staat om zo snel op wijzigingen te reageren.
We hebben niet veel over Quicksilver gesproken. We gebruikten vroeger als een wereldwijd gedistribueerde key-value store, maar deze had operationele problemen. Daarom hebben we onze eigen store geschreven die in meer dan 180 steden werd gerepliceerd. Met Quicksilver pushen we nu clientconfiguratiewijzigingen, werken we WAF-regels bij en distribueren we door de client geschreven JavaScript naar Cloudflare Workers.
Van het klikken op een knop op een dashboard of het aanroepen van een API tot het wereldwijd wijzigen van de configuratie: het duurt slechts een paar seconden. Klanten zijn dol op deze snelle installatie. En Workers bieden hen een vrijwel directe wereldwijde implementatie. Gemiddeld verwerkt Quicksilver ongeveer 350 wijzigingen per seconde.
En Quicksilver is razendsnel. Gemiddeld bereikten we het 99e percentiel van 2,29 seconden om wijzigingen door te voeren naar elke computer wereldwijd. Snelheid is meestal een goede zaak. Wanneer je een functie inschakelt of de cache wist, gebeurt dat immers vrijwel direct en overal. Het versturen van code via Cloudflare Workers gebeurt met dezelfde snelheid. Cloudflare belooft zijn klanten snelle updates wanneer ze die nodig hebben.
Maar in dit geval speelde de snelheid een wrede grap met ons, en de regels veranderden overal in een paar seconden. Je hebt misschien gemerkt dat de WAF-code Lua gebruikt. Cloudflare gebruikt Lua uitgebreid in productie, en details we . Lua WAF gebruikt intern en gebruikt backtracking om te matchen. Het heeft geen mechanismen om te beschermen tegen onbeheerste expressies. Ik zal hier later meer over vertellen en wat we eraan doen.
Voordat de regels werden geïmplementeerd, verliep alles soepel: er werd een pull-aanvraag aangemaakt en goedgekeurd, de CI/CD-pijplijn bouwde en testte de code, er werd een wijzigingsverzoek ingediend volgens de SOP die de implementatie en rollback regelt, en de implementatie werd uitgevoerd.
Cloudflare WAF-implementatieproces
Wat ging er mis?
Zoals ik al zei, implementeren we wekelijks tientallen nieuwe WAF-regels en hebben we meerdere systemen om ons te beschermen tegen de negatieve gevolgen van dergelijke implementaties. En als er iets misgaat, is het meestal een combinatie van meerdere factoren. Het vinden van slechts één oorzaak is geruststellend, maar dat is niet altijd het geval. Dit zijn de factoren die er samen voor hebben gezorgd dat onze HTTP/HTTPS-service faalde.
- Een ingenieur heeft een reguliere expressie geschreven die kan leiden tot overmatige .
- Een functie die had kunnen voorkomen dat de reguliere expressie te veel CPU gebruikte, werd enkele weken eerder per ongeluk verwijderd tijdens een WAF-refactoring. De refactoring was nodig om ervoor te zorgen dat de WAF minder bronnen zou verbruiken.
- De reguliere expressie-engine bood geen complexiteitsgaranties.
- De testsuite kon geen overmatig CPU-gebruik detecteren.
- De SOP-procedure maakt wereldwijde implementatie van niet-dringende regelwijzigingen mogelijk zonder een proces in meerdere stappen.
- Voor het terugdraaiplan moest de volledige WAF-build twee keer worden uitgevoerd, wat veel tijd kost.
- De eerste waarschuwing voor wereldwijde verkeersproblemen kwam te laat.
- We waren traag met het bijwerken van de statuspagina.
- Door een storing hadden we problemen met de toegang tot systemen en de oplossing hiervoor was niet goed uitgewerkt.
- SRE-technici verloren de toegang tot bepaalde systemen omdat hun inloggegevens om veiligheidsredenen waren verlopen.
- Onze klanten hadden geen toegang tot het Cloudflare-dashboard of de API omdat ze via een Cloudflare-regio gingen.
Wat is er veranderd sinds afgelopen donderdag
Ten eerste hebben we alle werkzaamheden aan releases voor WAF volledig stopgezet en nu doen we het volgende:
- We hebben de bescherming tegen overmatig CPU-verbruik die we hadden verwijderd, opnieuw geïntroduceerd. (Klaar)
- Handmatig controleren van alle 3868 regels in beheerde regels voor WAF om andere potentiële gevallen van overmatig backtracking te vinden en op te lossen. (Controle voltooid)
- Inclusief prestatieprofilering voor alle regels in de testsuite. (Verwacht: 19 juli)
- Overstappen naar de reguliere expressie-engine of — beide bieden een looptijdgarantie. (Verwacht: 31 juli)
- We zijn de SOP aan het herschrijven om regels gefaseerd te implementeren, net als andere software in Cloudflare. We hebben echter nog steeds de mogelijkheid om een noodimplementatie wereldwijd uit te voeren als er al aanvallen zijn begonnen.
- We zijn bezig met het ontwikkelen van de mogelijkheid om het Cloudflare-dashboard en de API zo snel mogelijk uit de Cloudflare-regio te halen.
- Automatische paginavernieuwing .
Op de lange termijn stappen we af van de Lua WAF die ik een paar jaar geleden schreef. We verplaatsen de WAF naar Op deze manier zal WAF sneller zijn en een extra beschermingsniveau krijgen.
Conclusie
Deze storing was vervelend voor ons en onze klanten. We hebben snel gereageerd om de situatie te verhelpen en werken momenteel aan het verhelpen van de fouten in de processen die de storing veroorzaakten. Daarnaast werken we aan een verdere bescherming tegen mogelijke toekomstige problemen met reguliere expressies door over te stappen op nieuwe technologie.
Het spijt ons zeer voor deze storing en we bieden onze excuses aan onze klanten aan. We hopen dat deze wijzigingen ervoor zorgen dat dit niet meer gebeurt.
Bijlage: Backtracking van reguliere expressies
Om te begrijpen hoe de uitdrukking:
(?:(?:"|'|]|}||d
(?:nan|infinity|true|false|null|undefined|symbol|math)|`|-
|+)+[)]*;?((?:s|-|~|!|{}||||+)*.*(?:.*=.*)))Omdat alle CPU-bronnen worden gebruikt, moet je een beetje weten hoe de standaard reguliere expressie-engine werkt. Het probleem zit hem hier in het patroon. .*(?:.*=.*). (?: en de bijbehorende ) — dit is geen vastleggende groep (dat wil zeggen, de uitdrukking tussen haakjes is gegroepeerd als één enkele uitdrukking).
In de context van overmatig CPU-verbruik kan dit patroon worden beschreven als .*.*=.*In deze vorm lijkt het patroon onnodig complex. Maar belangrijker nog: in de praktijk kunnen dergelijke expressies (zoals complexe expressies in WAF-regels) die de engine vragen om een fragment gevolgd door een ander fragment te matchen, leiden tot catastrofale backtracking. Dit is waarom.
In reguliere expressie . betekent dat je één teken moet matchen, .* — nul of meer tekens gretig matchen, dat wil zeggen door zoveel mogelijk tekens te vangen, zodat .*.*=.* betekent nul of meer tekens matchen, dan nul of meer tekens matchen, het letterlijke = teken vinden, nul of meer tekens matchen.
Laten we een testreeks nemen x=x. Het komt overeen met de uitdrukking .*.*=.*. .*.* vóór het gelijkteken overeenkomt met de eerste x (een van de groepen .* komt overeen met x, en de tweede - nul tekens). .* after = komt overeen met de laatste x.
Deze vergelijking vereist 23 stappen. De eerste groep .* в .*.*=.* gedraagt zich "gulzig" en past bij de hele lijn x=xDe motor gaat naar de volgende groep. .*. We hebben geen karakters meer om te matchen, dus de tweede groep .* komt overeen met nul tekens (dit is toegestaan). Vervolgens gaat de engine naar het teken =Er zijn geen symbolen meer (eerste groep) .* gebruikte de hele uitdrukking x=x), vindt er geen overeenkomst plaats.
En hier gaat de reguliere expressie-engine terug naar het begin. Hij gaat naar de eerste groep. .* en vergelijkt het с x= (in plaats van x=x), en neemt vervolgens de tweede groep op zich .*Tweede groep .* wordt vergeleken met de tweede x, en we hebben geen symbolen meer over. En als de motor het begeeft = в .*.*=.*, niets werkt. En hij gaat weer terug.
Deze keer de groep .* past nog steeds x=, maar de tweede groep .* niet meer x, en nul tekens. De engine probeert een letterlijk teken te vinden = in het patroon .*.*=.*, maar het werkt niet (de eerste groep heeft het immers al gedaan) .*). En hij gaat weer terug.
Deze keer de eerste groep .* neemt alleen de eerste x. Maar de tweede groep .* "gretig" vangt =xHeb je al geraden wat er gaat gebeuren? De engine probeert de letterlijke waarde te matchen. =, mislukt en gaat weer terug op zijn stappen.
De eerste groep .* komt nog steeds overeen met de eerste x. Seconde .* duurt slechts =. Natuurlijk kan de motor niet tippen aan de letterlijke =, omdat de tweede groep het al heeft gedaan .*. En weer teruggaan. En hier proberen we een reeks van drie tekens te matchen!
Als gevolg hiervan is de eerste groep .* komt alleen overeen met de eerste x, de tweede .* — met nul tekens, en de engine komt uiteindelijk overeen met de letterlijke = in de uitdrukking с = op een rij. Dan de laatste groep .* wordt vergeleken met de laatste x.
23 stappen alleen voor x=xBekijk een korte video over het gebruik van Perl , die laat zien hoe stappen en terugstappen plaatsvinden.
Dit is al een hoop werk, maar wat als we in plaats daarvan x=x wij zullen hebben x=xx? Dat zijn 33 stappen. En als x=xxx? 45. De afhankelijkheid is niet lineair. De grafiek toont een vergelijking van x=x naar x=xxxxxxxxxxxxxxxxxxxx (20 x na =). Als we 20 x na hebben =, voert de engine de matching uit in 555 stappen! (Bovendien, als we verloren zijn x= en de lijn bestaat uit slechts 20 x, dan zal de engine 4067 stappen ondernemen om te bepalen dat er geen overeenkomsten zijn.
Deze video toont alle backtracking voor vergelijking x=xxxxxxxxxxxxxxxxxxxx:
Het probleem is dat de matchingtijd superlineair toeneemt naarmate de string groter wordt. Maar het kan nog erger worden als de reguliere expressie lichtjes wordt aangepast. Stel dat we .*.*=.*; (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 regelrechte ramp zijn. Ter vergelijking: x=x Het kost 90 stappen in plaats van 23. En dat aantal groeit snel. Ter vergelijking: x= en 20 xEr zijn 5353 stappen nodig. Hier is de grafiek. Kijk naar de waarden op de as. Y vergeleken met de vorige grafiek.
Als je geïnteresseerd bent, bekijk dan alle 5353 stappen van mislukte matching x=xxxxxxxxxxxxxxxxxxxx и .*.*=.*;
Door lazy in plaats van greedy matching te gebruiken, kan de mate van backtracking worden gecontroleerd. Door de oorspronkelijke expressie te wijzigen in .*?.*?=.*?, ter vergelijking x=x het zal 11 stappen duren (niet 23). Wat betreft x=xxxxxxxxxxxxxxxxxxxx. Allemaal omdat ? na .* vertelt de engine dat er een minimaal aantal tekens moet worden gevonden voordat er verder wordt gegaan.
Maar lazy matching lost het backtrackingprobleem niet volledig op. Als we het rampzalige voorbeeld vervangen .*.*=.*; op .*?.*?=.*?;, blijft de uitvoeringstijd hetzelfde. x=x vereist nog steeds 555 stappen, maar x= en 20 x - 5353.
Het enige wat we kunnen doen (behalve het patroon volledig herschrijven om specifieker te zijn) is de reguliere-expressie-engine met zijn backtracking-mechanisme te verlaten. Dat is wat we de komende weken gaan doen.
De oplossing voor dit probleem is al bekend sinds 1968, toen Kent Thompson een artikel schreef ("Programmeermethoden: Zoekalgoritme voor reguliere expressies"). Het artikel beschrijft een mechanisme waarmee een reguliere expressie kan worden omgezet in niet-deterministische, eindige automaten, en na statuswijzigingen in niet-deterministische, eindige automaten, met behulp van een algoritme waarvan de uitvoeringstijd lineair afhankelijk is van de overeenkomende string.
Programmeermethoden
Zoekalgoritme voor reguliere expressies
Ken Thompson
Bell Telephone Laboratories, Inc., Murray Hill, N.J.Dit artikel beschrijft een methode voor het zoeken naar een specifieke tekenreeks in een tekst en bespreekt de implementatie van deze methode in de vorm van een compiler. De compiler accepteert een reguliere expressie als broncode en genereert een programma voor de IBM 7094 als objectcode. Het objectprogramma accepteert invoer in de vorm van tekst om naar te zoeken en geeft een pieptoon wanneer een tekstreeks overeenkomt met de opgegeven reguliere expressie. Voorbeelden, problemen en oplossingen worden gegeven.
Het algoritme
Eerdere zoekalgoritmes resulteerden in een terugwerkende kracht als een gedeeltelijk succesvolle zoekopdracht geen resultaten opleverde.In de compileermodus werkt het algoritme niet met symbolen. Het geeft instructies door aan de gecompileerde code. De uitvoering is zeer snel: nadat de gegevens bovenaan de huidige lijst zijn geplaatst, zoekt het automatisch naar alle mogelijke opeenvolgende symbolen in de reguliere expressie.
Het compilatie- en zoekalgoritme is in de timesharing-teksteditor opgenomen als contextzoekfunctie. Dit is natuurlijk lang niet de enige toepassing van een dergelijke zoekprocedure. Een variant van dit algoritme wordt bijvoorbeeld gebruikt als symbooltabelzoekfunctie in Assembler.
Wij gaan ervan uit dat de lezer bekend is met reguliere expressies en met de computerprogrammeertaal IBM 7094.Compiler
De compiler bestaat uit drie parallelle fasen. De eerste fase is syntaxisfiltering, waarbij alleen syntactisch correcte reguliere expressies worden doorgelaten. In deze fase wordt ook de "·"-operator ingevoegd voor het matchen van reguliere expressies. De tweede fase converteert de reguliere expressie naar een postfix-vorm. De derde fase genereert de objectcode. De eerste twee fasen zijn voor de hand liggend en we zullen er niet verder op ingaan.
In het artikel van Thompson worden niet-deterministische eindige automaten niet besproken, maar het geeft wel een goede uitleg van het lineaire-tijdalgoritme en bevat een ALGOL-60-programma dat assemblercode genereert voor de IBM 7094. De implementatie is lastig, maar het idee is heel eenvoudig.
Het huidige zoekpad. Dit wordt weergegeven door het ⊕-pictogram met één ingang en twee uitgangen.
Figuur 1 toont de functies van de derde fase van compilatie bij het transformeren van de voorbeeldreguliere expressie. De eerste drie tekens in het voorbeeld zijn a, b en c, en elk genereert een stack-item S[i] en een veld NNODE.NNODE toevoegen aan de bestaande code om de uiteindelijke reguliere expressie in één enkele stapelvermelding te genereren (zie Afbeelding 5)
Dit is hoe de reguliere expressie eruit zou zien .*.*=.*, als je het je voorstelt zoals op de afbeeldingen in het artikel van Thompson.
In figuur 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 de drie .* in een reguliere expressie. Drie ovalen met stippen komen overeen met één teken. Een ovaal met een teken = komt overeen met een letterlijk teken =Toestand 4 is de eindtoestand. Als we deze hebben bereikt, is de reguliere expressie gematcht.
Om te zien hoe een dergelijk toestandsdiagram kan worden gebruikt voor het matchen van reguliere expressies .*.*=.*, we zullen kijken naar string matching x=xHet programma start vanaf toestand 0, zoals weergegeven in Figuur 1.
Om dit algoritme te laten werken, moet de toestandsautomaat zich in meerdere toestanden tegelijk bevinden. Een niet-deterministische toestandsautomaat maakt alle mogelijke overgangen tegelijkertijd.
Voordat het de invoergegevens kan lezen, gaat het in de eerste twee toestanden (1 en 2), zoals weergegeven in figuur 2.
Figuur 2 laat zien wat er gebeurt als hij naar de eerste kijkt x в x=x. x kan het hoogste punt evenaren door van toestand 1 naar toestand 1 te gaan. Of x kan het onderstaande punt matchen door van toestand 2 naar toestand 2 te gaan.
Na vergelijking 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 symbool nodig hebben =.
Het algoritme houdt vervolgens rekening met = в x=xNet als x hiervoor kan het worden vergeleken met een van de twee bovenste cycli met een overgang van toestand 1 naar toestand 1 of van toestand 2 naar toestand 2, maar het algoritme kan een letterlijke = en ga van toestand 2 naar toestand 3 (en onmiddellijk naar toestand 4). Dit is weergegeven in figuur 3.
Dan gaat het algoritme verder naar de laatste x в x=xVanuit toestand 1 en 2 zijn dezelfde overgangen terug naar toestand 1 en 2 mogelijk. Vanuit toestand 3 x kan het punt aan de rechterkant vinden en teruggaan naar toestand 3.
In dit stadium is elk symbool x=x overwogen, en zodra we toestand 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 invoerstring. En geen backtracking.
Het is duidelijk dat na het bereiken van toestand 4 (wanneer het algoritme overeenkomt met x=) de volledige reguliere expressie wordt gematcht en het algoritme kan worden beëindigd zonder rekening te houden met eventuele wijzigingen. x.
Dit algoritme is lineair afhankelijk van de grootte van de invoerreeks.
Bron: www.habr.com
