Vor fast 9 Jahren war Cloudflare ein kleines Unternehmen, und ich habe nicht für das Unternehmen gearbeitet, ich war nur ein Kunde. Einen Monat nach dem Start von Cloudflare erhielt ich eine Benachrichtigung, dass meine Website DNS scheint nicht zu funktionieren. Cloudflare hat eine Änderung vorgenommen , und es gab einen defekten DNS.
Ich schrieb sofort an Matthew Prince mit dem Titel „Wo ist mein DNS?“ und er schickte eine lange Antwort voller technischer Details zurück (), worauf ich antwortete:
Von: John Graham-Cumming
Datum: 7. Oktober 2010, 9:14
Betreff: Betreff: Wo ist mein DNS?
An: Matthew PrinceCooler Bericht, danke. Ich werde auf jeden Fall anrufen, wenn es Probleme gibt. Es lohnt sich wahrscheinlich, einen Beitrag darüber zu schreiben, wenn Sie alle technischen Informationen gesammelt haben. Ich denke, die Leute werden eine offene und ehrliche Geschichte genießen. Vor allem, wenn Sie Grafiken hinzufügen, um zu zeigen, wie der Traffic seit der Einführung gewachsen ist.
Ich habe eine gute Überwachung meiner Website und erhalte bei jedem Fehler eine SMS. Die Überwachung zeigt, dass der Fehler zwischen 13:03:07 und 14:04:12 aufgetreten ist. Die Tests werden alle fünf Minuten durchgeführt.
Ich bin sicher, Sie werden es herausfinden. Sind Sie sicher, dass Sie in Europa keine eigene Person benötigen? 🙂
Und er antwortete:
Von: Matthew Prince
Datum: 7. Oktober 2010, 9:57
Betreff: Betreff: Wo ist mein DNS?
An: John Graham-CummingDanke. Wir haben allen geschrieben, die geschrieben haben. Ich bin jetzt auf dem Weg ins Büro und wir werden etwas auf dem Blog schreiben oder einen offiziellen Beitrag an unsere Pinnwand pinnen. Ich stimme voll und ganz zu, Ehrlichkeit ist alles.
Jetzt ist Cloudflare ein wirklich großes Unternehmen, ich arbeite für es und jetzt muss ich offen über unseren Fehler, seine Konsequenzen und unser Handeln schreiben.
Ereignisse vom 2. Juli
Aus diesem Grund haben wir am 2. Juli eine neue Regel in den verwalteten Regeln für WAFs eingeführt auf jedem Prozessorkern, der HTTP/HTTPS-Verkehr im Cloudflare-Netzwerk weltweit verarbeitet. Als Reaktion auf neue Schwachstellen und Bedrohungen verbessern wir ständig die verwalteten Regeln für WAFs. Im Mai zum Beispiel haben wir uns beeilt zum Schutz vor einer schwerwiegenden Sicherheitslücke in SharePoint. Der springende Punkt unserer WAF ist die Fähigkeit, Regeln schnell und global bereitzustellen.
Leider enthielt das Update vom letzten Donnerstag einen regulären Ausdruck, der beim Backtracking zu viele HTTP/HTTPS-CPU-Ressourcen verschwendete. Unsere zentralen Proxy-, CDN- und WAF-Funktionen litten darunter. Die Grafik zeigt, dass die Prozessorressourcen für die Bereitstellung des HTTP/HTTPS-Verkehrs auf den Servern in unserem Netzwerk fast 100 % erreichen.
CPU-Auslastung an einem Point of Presence während eines Vorfalls
Infolgedessen bekamen unsere Kunden (und die Kunden unserer Kunden) eine 502-Fehlerseite in Cloudflare-Domänen. 502-Fehler wurden von Cloudflare-Frontend-Webservern generiert, die noch über freie Kerne verfügten, aber nicht in der Lage waren, mit Prozessen zu kommunizieren, die HTTP/HTTPS-Verkehr verarbeiten.
Wir wissen, wie viel Unannehmlichkeiten dies für unsere Kunden verursacht hat. Wir schämen uns furchtbar. Und dieses Versagen hinderte uns daran, den Vorfall effektiv zu bewältigen.
Wenn Sie einer dieser Kunden waren, waren Sie wahrscheinlich verängstigt, wütend und verärgert. Außerdem hatten wir noch keine . Der hohe CPU-Verbrauch war auf eine WAF-Regel mit einem schlecht formulierten regulären Ausdruck zurückzuführen, der zu übermäßigem Backtracking führte. Hier ist der schuldige Ausdruck: (?:(?:"|'|]|}||d|(?:nan|infinity|true|false|null|undefined|symbol|math)|`|-|+)+[)]*;?((?:s|-|~|!|{}||||+)*.*(?:.*=.*)))
Das ist zwar an sich schon interessant (und ich werde weiter unten ausführlicher darauf eingehen), aber der Cloudflare-Dienst war nicht nur wegen eines fehlerhaften regulären Ausdrucks 27 Minuten lang ausgefallen. Wir brauchten eine Weile, um die Abfolge der Ereignisse zu beschreiben, die zum Ausfall führten, und reagierten daher nur langsam. Am Ende des Beitrags beschreibe ich das Backtracking in einem regulären Ausdruck und erkläre Ihnen, was Sie damit machen können.
Was ist passiert
Beginnen wir der Reihe nach. Alle Zeiten hier sind in UTC.
Um 13:42 Uhr nahm ein Ingenieur des Firewall-Teams eine kleine Änderung an den Erkennungsregeln vor mithilfe eines automatischen Prozesses. Dementsprechend wurde ein Änderungsanfrageticket erstellt. Wir verwalten solche Tickets über Jira (Screenshot unten).
Nach 3 Minuten erschien die erste Seite von PagerDuty, die ein Problem mit WAF meldete. Dabei handelte es sich um einen synthetischen Test, der die Funktionalität von WAFs (wir haben Hunderte davon) außerhalb von Cloudflare testet, um den normalen Betrieb zu überwachen. Unmittelbar darauf folgten seitenweise Warnungen über das Scheitern anderer Cloudflare-End-to-End-Diensttests, globale Verkehrsprobleme, weit verbreitete 502-Fehler und eine Menge Berichte von unseren Points of Presence (PoP) in Städten auf der ganzen Welt, die auf einen Mangel hinwiesen der CPU-Ressourcen.
Ich erhielt mehrere dieser Benachrichtigungen, stürmte aus einer Besprechung und war auf dem Weg zum Tisch, als der Leiter unserer Abteilung für Lösungsentwicklung sagte, dass wir 80 % unseres Datenverkehrs verloren hätten. Ich rannte zu unseren SRE-Ingenieuren, die bereits an dem Problem arbeiteten. Zuerst dachten wir, es handele sich um einen unbekannten Angriff.
Die SRE-Ingenieure von Cloudflare sind über die ganze Welt verstreut und überwachen die Situation rund um die Uhr. In der Regel benachrichtigen Sie diese Warnungen über bestimmte lokale Probleme von begrenztem Umfang, werden auf internen Dashboards verfolgt und mehrmals täglich behoben. Aber diese Seiten und Meldungen deuteten auf etwas wirklich Ernstes hin, und die SRE-Ingenieure erklärten sofort den Schweregrad P0 und kontaktierten Management- und Systemingenieure.
Unsere Londoner Ingenieure lauschten gerade einem Vortrag in der Haupthalle. Der Vortrag musste unterbrochen werden, alle versammelten sich in einem großen Konferenzraum und weitere Spezialisten wurden hinzugezogen. Dies war kein typisches Problem, mit dem SREs alleine fertig werden konnten. Es war dringend erforderlich, die richtigen Spezialisten einzubinden.
Um 14:00 Uhr stellten wir fest, dass das Problem bei der WAF lag und es keinen Angriff gab. Das Performance-Team zog die CPU-Daten und es wurde klar, dass die WAF schuld war. Ein anderer Mitarbeiter bestätigte diese Theorie mithilfe von Strace. Jemand anderes hat in den Protokollen gesehen, dass es ein Problem mit WAF gab. Um 14:02 Uhr kam das gesamte Team auf mich zu, als vorgeschlagen wurde, Global Kill zu verwenden, einen in Cloudflare integrierten Mechanismus, der eine Komponente weltweit abschaltet.
Wie wir für die WAF globale Tötungen erzielten, ist eine andere Geschichte. So einfach ist das nicht. Wir verwenden unsere eigenen Produkte und seitdem unseren Service hat nicht funktioniert, wir konnten uns nicht authentifizieren und uns nicht beim internen Kontrollpanel anmelden (als alles repariert war, erfuhren wir, dass einige Teammitglieder aufgrund einer Sicherheitsfunktion, die Anmeldeinformationen deaktiviert, wenn das interne Kontrollpanel für einen Zeitraum nicht verwendet wird, den Zugriff verloren hatten lange Zeit).
Und wir konnten nicht auf unsere internen Dienste wie Jira oder das Build-System zugreifen. Wir brauchten einen Workaround-Mechanismus, den wir nur selten nutzten (dieser muss ebenfalls ausgearbeitet werden). Schließlich gelang es einem Ingenieur, die WAF um 14:07 Uhr zu deaktivieren, und um 14:09 Uhr waren der Datenverkehr und die CPU-Niveaus überall wieder normal. Die übrigen Schutzmechanismen von Cloudflare funktionierten wie gewohnt.
Dann machten wir uns daran, die WAF wiederherzustellen. Die Situation war außergewöhnlich, also führten wir in einer Stadt negative Tests (wobei wir uns fragten, ob die Änderung wirklich das Problem war) und positive Tests (um sicherzustellen, dass das Rollback funktionierte) durch und nutzten getrennten Verkehr, um zahlende Kunden von dort zu transferieren.
Um 14:52 Uhr waren wir überzeugt, dass wir den Grund verstanden hatten, nahmen eine Korrektur vor und aktivierten WAF erneut.
So funktioniert Cloudflare
Cloudflare verfügt über ein Team von Ingenieuren, die sich mit der Verwaltung von Regeln für WAFs befassen. Sie sind bestrebt, die Erkennungsraten zu verbessern, Fehlalarme zu reduzieren und schnell auf neu auftretende Bedrohungen zu reagieren. In den letzten 60 Tagen wurden 476 Änderungsanfragen für verwaltete Regeln für WAF verarbeitet (durchschnittlich eine alle 3 Stunden).
Diese spezielle Änderung musste im Simulationsmodus implementiert werden, in dem echter Client-Verkehr die Regel durchläuft, aber nichts blockiert wird. Wir verwenden diesen Modus, um die Wirksamkeit der Regeln zu testen und die Falsch-Positiv- und Falsch-Negativ-Raten zu messen. Aber auch im Simulationsmodus müssen die Regeln tatsächlich ausgeführt werden, und in diesem Fall enthielt die Regel einen regulären Ausdruck, der zu viele Prozessorressourcen verbrauchte.
Wie Sie der Änderungsanforderung oben entnehmen können, verfügen wir über einen Bereitstellungsplan, einen Rollback-Plan und einen Link zu einer internen Standardarbeitsanweisung (SOP) für diese Art der Bereitstellung. Die SOP zum Ändern einer Regel ermöglicht deren globale Veröffentlichung. Tatsächlich werden die Dinge bei Cloudflare völlig anders gehandhabt, und die SOP schreibt vor, dass wir die Software zum Testen und zur internen Verwendung zunächst an einen internen Point of Presence (PoP) (den unsere Mitarbeiter nutzen) und dann an eine kleine Anzahl von Kunden versenden an einem isolierten Ort, dann an eine große Anzahl von Kunden und erst dann an die ganze Welt.
So sieht es aus. Wir nutzen Git intern über BitBucket. Ingenieure, die an Änderungen arbeiten, übermitteln den Code, der erstellt wird, an TeamCity, und wenn der Build erfolgreich ist, werden Prüfer zugewiesen. Sobald eine Pull-Anfrage genehmigt wurde, wird der Code zusammengestellt und eine Reihe von Tests (erneut) ausgeführt.
Wenn der Build und die Tests erfolgreich abgeschlossen werden, wird in Jira eine Änderungsanforderung erstellt und der entsprechende Manager oder Lead muss die Änderung genehmigen. Nach der Genehmigung erfolgt der Einsatz in der sogenannten „PoP-Menagerie“: DOG, PIG und (Hund, Schwein und Kanarienvogel).
DOG PoP ist ein Cloudflare PoP (wie jede andere unserer Städte), der nur von Cloudflare-Mitarbeitern genutzt wird. Mit PoP für den internen Gebrauch können Sie Probleme erkennen, bevor Kundenverkehr in die Lösung fließt. Nützliches Ding.
Wenn der DOG-Test erfolgreich ist, geht der Code zur PIG-Stufe (Meerschweinchen) über. Dies ist Cloudflare PoP, bei dem ein kleiner Teil des kostenlosen Kundenverkehrs durch neuen Code fließt.
Wenn alles in Ordnung ist, wird der Code in Canary übertragen. Wir haben drei kanarische PoPs in verschiedenen Teilen der Welt. In ihnen durchläuft der Datenverkehr von kostenpflichtigen und kostenlosen Kunden den neuen Code, und dies ist die letzte Prüfung auf Fehler.
Software-Release-Prozess bei Cloudflare
Wenn der Code in Canary in Ordnung ist, veröffentlichen wir ihn. Das Durchlaufen aller Phasen – DOG, PIG, Canary, die ganze Welt – dauert je nach Codeänderung mehrere Stunden oder Tage. Aufgrund der Vielfalt des Netzwerks und der Kunden von Cloudflare testen wir den Code gründlich, bevor wir ihn weltweit für alle Kunden freigeben. Die WAF verfolgt diesen Prozess jedoch nicht gezielt, da auf Bedrohungen schnell reagiert werden muss.
WAF-Drohungen
In den letzten Jahren kam es zu einem erheblichen Anstieg der Bedrohungen in gängigen Anwendungen. Dies ist auf die größere Verfügbarkeit von Softwaretesttools zurückzuführen. Wir haben zum Beispiel kürzlich darüber geschrieben ).
Source:
Sehr oft wird ein Proof of Concept erstellt und sofort auf Github veröffentlicht, damit die Teams, die die Anwendung betreuen, diese schnell testen und sicherstellen können, dass sie ausreichend gesichert ist. Daher benötigt Cloudflare die Fähigkeit, schnellstmöglich auf neue Angriffe zu reagieren, damit Kunden die Möglichkeit haben, ihre Software zu reparieren.
Ein gutes Beispiel für die schnelle Reaktion von Cloudflare ist die Bereitstellung von SharePoint-Schwachstellenschutz im Mai (). Fast unmittelbar nach den Ankündigungen bemerkten wir eine Vielzahl von Versuchen, die Schwachstelle in den SharePoint-Installationen unserer Kunden auszunutzen. Unsere Mitarbeiter überwachen ständig neue Bedrohungen und schreiben Regeln zum Schutz unserer Kunden.
Die Regel, die am Donnerstag das Problem verursachte, sollte vor Cross-Site-Scripting (XSS) schützen. Auch solche Angriffe sind in den letzten Jahren deutlich häufiger geworden.
Source:
Das Standardverfahren zum Ändern einer verwalteten Regel für eine WAF besteht darin, vor der globalen Bereitstellung kontinuierliche Integrationstests (CI) durchzuführen. Letzten Donnerstag haben wir das gemacht und die Regeln eingeführt. Um 13:31 Uhr reichte ein Ingenieur einen genehmigten Pull-Request mit einer Änderung ein.
Um 13:37 Uhr sammelte TeamCity die Regeln ein, führte Tests durch und gab grünes Licht. Die WAF-Testsuite testet die Kernfunktionalität der WAF und besteht aus einer Vielzahl von Unit-Tests für einzelne Funktionen. Nach Unit-Tests haben wir die Regeln für die WAF anhand einer großen Anzahl von HTTP-Anfragen getestet. HTTP-Anfragen prüfen, welche Anfragen von der WAF blockiert werden sollen (um den Angriff abzufangen) und welche durchgelassen werden können (um nicht alles zu blockieren und Fehlalarme zu vermeiden). Wir haben jedoch nicht auf übermäßige CPU-Auslastung getestet, und die Untersuchung der Protokolle früherer WAF-Builds zeigt, dass sich die Ausführungszeit des Regeltests nicht erhöht hat, und es war schwer zu vermuten, dass nicht genügend Ressourcen vorhanden sein würden.
Die Tests wurden bestanden und TeamCity begann um 13:42 Uhr mit der automatischen Bereitstellung der Änderung.
Quecksilber
WAF-Regeln konzentrieren sich auf die sofortige Behebung von Bedrohungen. Deshalb stellen wir sie mithilfe des verteilten Schlüsselwertspeichers von Quicksilver bereit, der Änderungen in Sekundenschnelle weltweit verbreitet. Alle unsere Kunden nutzen diese Technologie, wenn sie die Konfiguration im Dashboard oder über die API ändern, und dank ihr können wir blitzschnell auf Änderungen reagieren.
Wir haben nicht viel über Quicksilver gesprochen. Zuvor haben wir verwendet als global verteilter Schlüsselwert-Shop, aber es gab betriebliche Probleme damit, und wir haben unseren eigenen Shop geschrieben, der in mehr als 180 Städten repliziert wurde. Wir verwenden Quicksilver jetzt, um Konfigurationsänderungen an Clients weiterzuleiten, WAF-Regeln zu aktualisieren und von Clients geschriebenen JavaScript-Code an Cloudflare-Worker zu verteilen.
Vom Klicken auf eine Schaltfläche in einem Dashboard oder dem Aufruf einer API bis zur weltweiten Durchführung einer Konfigurationsänderung vergehen nur wenige Sekunden. Die Kunden waren von dieser schnellen Einrichtung begeistert. Und Workers ermöglicht ihnen eine fast sofortige globale Softwarebereitstellung. Im Durchschnitt verbreitet Quicksilver etwa 350 Änderungen pro Sekunde.
Und Quicksilver ist sehr schnell. Im Durchschnitt haben wir das 99. Perzentil von 2,29 Sekunden erreicht, um Änderungen an jeden Computer weltweit weiterzugeben. Geschwindigkeit ist normalerweise eine gute Sache. Denn wenn Sie eine Funktion aktivieren oder den Cache leeren, geschieht dies fast sofort und überall. Das Senden von Code über Cloudflare Workers erfolgt mit der gleichen Geschwindigkeit. Cloudflare verspricht seinen Kunden schnelle Updates zur richtigen Zeit.
Aber in diesem Fall spielte uns die Geschwindigkeit einen grausamen Streich und die Regeln änderten sich überall innerhalb von Sekunden. Möglicherweise ist Ihnen aufgefallen, dass der WAF-Code Lua verwendet. Cloudflare nutzt Lua in großem Umfang in Produktion und Details wir . Lua WAF verwendet intern und wendet Backtracking für den Abgleich an. Es verfügt über keine Mechanismen zum Schutz vor außer Kontrolle geratenen Ausdrücken. Im Folgenden werde ich mehr darüber sprechen und darüber, was wir dagegen tun.
Bevor die Regeln bereitgestellt wurden, verlief alles reibungslos: Der Pull-Request wurde erstellt und genehmigt, die CI/CD-Pipeline sammelte und testete den Code, der Änderungsantrag wurde gemäß der SOP übermittelt, die die Bereitstellung und das Rollback regelt, und die Bereitstellung wurde abgeschlossen.
Cloudflare WAF-Bereitstellungsprozess
Was ist schiefgelaufen?
Wie ich bereits sagte, implementieren wir jede Woche Dutzende neuer WAF-Regeln und verfügen über zahlreiche Systeme, um uns vor den negativen Folgen einer solchen Implementierung zu schützen. Und wenn etwas schief geht, ist es meist eine Kombination mehrerer Umstände gleichzeitig. Wenn Sie nur einen Grund finden, ist das natürlich beruhigend, aber es stimmt nicht immer. Dies sind die Gründe, die zusammen zum Ausfall unseres HTTP/HTTPS-Dienstes geführt haben.
- Ein Ingenieur hat einen regulären Ausdruck geschrieben, der zu einer Überschreitung führen könnte .
- Eine Funktion, die hätte verhindern können, dass der reguläre Ausdruck übermäßige CPU-Ressourcen verschwendet, wurde bei einem WAF-Refactoring einige Wochen zuvor versehentlich entfernt – das Refactoring war erforderlich, damit die WAF weniger Ressourcen verbraucht.
- Die Engine für reguläre Ausdrücke hatte keine Komplexitätsgarantien.
- Die Testsuite konnte keinen übermäßigen CPU-Verbrauch feststellen.
- Die SOP ermöglicht die globale Einführung nicht dringender Regeländerungen ohne einen mehrstufigen Prozess.
- Der Rollback-Plan erforderte die zweimalige Ausführung eines vollständigen WAF-Builds, was viel Zeit in Anspruch nahm.
- Die erste Warnung vor weltweiten Verkehrsproblemen wurde zu spät ausgelöst.
- Es hat eine Weile gedauert, die Statusseite zu aktualisieren.
- Aufgrund eines Fehlers hatten wir Probleme beim Zugriff auf die Systeme und das Umgehungsverfahren war nicht gut etabliert.
- SRE-Ingenieure verloren aus Sicherheitsgründen den Zugriff auf einige Systeme, da ihre Zugangsdaten abgelaufen waren.
- Unsere Kunden hatten keinen Zugriff auf das Cloudflare-Dashboard oder die Cloudflare-API, da sie eine Cloudflare-Region nutzen.
Was sich seit letztem Donnerstag geändert hat
Erstens haben wir alle Arbeiten an Veröffentlichungen für WAF vollständig eingestellt und gehen wie folgt vor:
- Wir führen den CPU-Überlastungsschutz, den wir entfernt haben, wieder ein. (Bereit)
- Manuelle Überprüfung aller 3868 Regeln in den verwalteten Regeln für die WAF, um andere potenzielle Fälle von übermäßigem Backtracking zu finden und zu korrigieren. (Verifizierung abgeschlossen)
- Wir integrieren Leistungsprofile für alle Regeln im Testsatz. (Voraussichtlich: 19. Juli)
- Wechsel zu einer Engine für reguläre Ausdrücke oder - beide bieten Laufzeitgarantien. (Voraussichtlich: 31. Juli)
- Wir schreiben die SOP neu, um die Regeln stufenweise bereitzustellen, wie andere Software in Cloudflare, haben aber gleichzeitig die Möglichkeit, eine globale Notfallbereitstellung durchzuführen, wenn Angriffe bereits begonnen haben.
- Wir entwickeln die Möglichkeit, das Cloudflare-Dashboard und die API dringend aus der Cloudflare-Region zu entfernen.
- Seitenaktualisierungen automatisieren .
Langfristig entfernen wir uns von der Lua WAF, die ich vor ein paar Jahren geschrieben habe. WAF verschieben nach . Dadurch wird die WAF schneller und erhält ein zusätzliches Maß an Schutz.
Abschluss
Dieser Ausfall verursachte Ärger für uns und unsere Kunden. Wir haben schnell gehandelt, um die Situation zu beheben, und arbeiten nun an den Fehlern in den Prozessen, die den Absturz verursacht haben, und graben noch tiefer, um mögliche Probleme mit regulären Ausdrücken in der Zukunft bei der Migration auf neue Technologien zu verhindern.
Dieser Ausfall ist uns sehr peinlich und wir entschuldigen uns bei unseren Kunden. Wir hoffen, dass diese Änderungen sicherstellen, dass so etwas nicht noch einmal passiert.
Anwendung. Reguläre Ausdrücke zurückverfolgen
Um zu verstehen, wie der Ausdruck:
(?:(?:"|'|]|}||d
(?:nan|infinity|true|false|null|undefined|symbol|math)|`|-
|+)+[)]*;?((?:s|-|~|!|{}||||+)*.*(?:.*=.*)))Da das System alle CPU-Ressourcen verbraucht hat, müssen Sie ein wenig darüber wissen, wie die Standard-Engine für reguläre Ausdrücke funktioniert. Das Problem hier ist das Muster .*(?:.*=.*). (?: und entsprechend ) ist eine nicht einfangende Gruppe (d. h. der Ausdruck in Klammern wird als einzelner Ausdruck gruppiert).
Im Zusammenhang mit übermäßigem CPU-Verbrauch kann dieses Muster wie folgt beschrieben werden: .*.*=.*. In dieser Form wirkt das Muster unnötig komplex. Aber was noch wichtiger ist: In der realen Welt können Ausdrücke (wie komplexe Ausdrücke in WAF-Regeln), die die Engine auffordern, ein Fragment gefolgt von einem anderen Fragment zuzuordnen, zu katastrophalen Rückverfolgungen führen. Und deshalb.
Im regulären Ausdruck . bedeutet, dass Sie ein Zeichen zuordnen müssen, .* - Passen Sie null oder mehr Zeichen „gierig“ an, d. h. es wird ein Maximum an Zeichen erfasst, damit .*.*=.* bedeutet, null oder mehr Zeichen abzugleichen, dann null oder mehr Zeichen abzugleichen, das Literal = Zeichen zu finden, null oder mehr Zeichen abzugleichen.
Nehmen wir die Testlinie x=x. Es entspricht dem Ausdruck .*.*=.*. .*.* bevor das Gleichheitszeichen mit dem ersten übereinstimmt x (eine der Gruppen .* Streichhölzer x, und das zweite - null Zeichen). .* after = passt zuletzt x.
Dieser Vergleich erfordert 23 Schritte. Erste Gruppe .* в .*.*=.* wirkt gierig und passt die gesamte Zeichenfolge an x=x. Die Engine wechselt zur nächsten Gruppe .*. Wir haben keine passenden Charaktere mehr, also die zweite Gruppe .* entspricht null Zeichen (dies ist zulässig). Dann bewegt sich die Lokomotive zum Schild =. Es gibt keine weiteren Symbole (erste Gruppe). .* habe den ganzen Ausdruck verwendet x=x), findet kein Vergleich statt.
Und dann kehrt die Engine für reguläre Ausdrücke zum Anfang zurück. Er geht weiter zur ersten Gruppe .* und vergleicht es с x= (Anstelle von x=x) und übernimmt dann die zweite Gruppe .*. Zweite Gruppe .* wird mit dem zweiten verglichen x, und wir haben wieder keine Zeichen mehr. Und wenn der Motor wieder erreicht = в .*.*=.*, nichts funktioniert. Und er macht wieder einen Rückzieher.
Diesmal die Gruppe .* passt immer noch x=, aber die zweite Gruppe .* nicht mehr xund null Zeichen. Die Engine versucht, ein wörtliches Zeichen zu finden = im Muster .*.*=.*, kommt aber nicht heraus (die erste Gruppe hat es schließlich schon besetzt). .*). Und er macht wieder einen Rückzieher.
Diesmal die erste Gruppe .* nimmt nur das erste x. Aber die zweite Gruppe .* „gierig“ fängt ein =x. Haben Sie schon erraten, was passieren wird? Die Engine versucht, das Literal abzugleichen =, schlägt fehl und macht einen weiteren Backtracking.
Die erste Gruppe von .* stimmt immer noch mit dem ersten überein x. Zweite .* dauert nur =. Natürlich kann die Engine nicht mit dem Wortlaut übereinstimmen =, weil die zweite Gruppe dies bereits getan hat .*. Und wieder ein Rückzieher. Und wir versuchen, eine Zeichenfolge aus drei Zeichen zuzuordnen!
Als Ergebnis die erste Gruppe .* passt nur zum ersten xzweite .* - mit null Zeichen, und die Engine stimmt schließlich mit dem Literal überein = im Ausdruck с = im Einklang. Als nächstes kommt die letzte Gruppe .* wird mit dem letzten verglichen x.
23 Schritte nur für x=x. Sehen Sie sich ein kurzes Video über die Verwendung von Perl an , das zeigt, wie Schritte und Backtracking erfolgen.
Das ist schon eine Menge Arbeit, aber was wäre, wenn stattdessen x=x wir werden haben x=xx? Das sind 33 Schritte. Und wenn x=xxx? 45. Die Beziehung ist nicht linear. Die Grafik zeigt einen Vergleich von x=x auf x=xxxxxxxxxxxxxxxxxxxx (20 x nach =). Wenn wir 20 x danach haben =, die Engine führt das Matching in 555 Schritten durch! (Außerdem, wenn wir verloren haben x= und die Zeichenfolge besteht einfach aus 20 x, benötigt die Engine 4067 Schritte, um zu verstehen, dass es keine Übereinstimmungen gibt).
Dieses Video zeigt das gesamte Backtracking zum Vergleich x=xxxxxxxxxxxxxxxxxxxx:
Das Problem besteht darin, dass mit zunehmender Stringgröße die Anpassungszeit superlinear zunimmt. Aber es kann noch schlimmer werden, wenn der reguläre Ausdruck leicht verändert wird. Nehmen wir an, wir hätten es getan .*.*=.*; (das heißt, am Ende des Musters befand sich ein wörtliches Semikolon). Zum Beispiel, um einen Ausdruck wie „zu finden“. foo=bar;.
Und hier wäre ein Rückzieher eine echte Katastrophe. Zum Vergleich x=x Es werden 90 Schritte erforderlich sein, nicht 23. Und diese Zahl wächst schnell. Vergleichen x= und 20 xEs sind 5353 Schritte erforderlich. Hier ist das Diagramm. Schauen Sie sich die Achsenwerte an Y im Vergleich zum vorherigen Diagramm.
Wenn Sie interessiert sind, sehen Sie sich alle 5353 fehlgeschlagenen Matching-Schritte an x=xxxxxxxxxxxxxxxxxxxx и .*.*=.*;
Durch die Verwendung von Lazy anstelle von Greedy Matching kann das Ausmaß des Backtrackings gesteuert werden. Wenn wir den ursprünglichen Ausdruck ändern in .*?.*?=.*?, zum Vergleich x=x es werden 11 Schritte benötigt (nicht 23). Wie für x=xxxxxxxxxxxxxxxxxxxx. Alles weil ? nach .* weist die Engine an, eine Mindestanzahl von Zeichen zuzuordnen, bevor sie fortfährt.
Aber Lazy Mappings lösen das Backtracking-Problem nicht vollständig. Wenn wir das katastrophale Beispiel ersetzen .*.*=.*; auf .*?.*?=.*?;, die Ausführungszeit bleibt gleich. x=x erfordert immer noch 555 Schritte, und x= und 20 x - 5353.
Das Einzige, was getan werden kann (neben dem vollständigen Umschreiben des Musters für eine größere Spezifität), besteht darin, die Engine für reguläre Ausdrücke mit ihrem Backtracking-Mechanismus aufzugeben. Das werden wir in den nächsten Wochen tun.
Die Lösung dieses Problems ist seit 1968 bekannt, als Kent Thompson einen Artikel schrieb („Programmiermethoden: Suchalgorithmus für reguläre Ausdrücke“). Der Artikel beschreibt einen Mechanismus, der es Ihnen ermöglicht, einen regulären Ausdruck in nicht deterministische endliche Automaten umzuwandeln und nach Zustandsänderungen in nicht deterministischen endlichen Automaten einen Algorithmus zu verwenden, dessen Ausführungszeit linear von der übereinstimmenden Zeichenfolge abhängt.
Programmiermethoden
Suchalgorithmus für reguläre Ausdrücke
Ken Thompson
Bell Telephone Laboratories, Inc., Murray Hill, New JerseyEs beschreibt eine Methode zum Suchen nach einer bestimmten Zeichenfolge im Text und erläutert die Implementierung dieser Methode in Compilerform. Der Compiler verwendet den regulären Ausdruck als Quellcode und erzeugt das IBM 7094-Programm als Objektcode. Das Objektprogramm nimmt Eingaben in Form von Suchtext entgegen und gibt jedes Mal ein Signal aus, wenn eine Textzeichenfolge mit einem bestimmten regulären Ausdruck übereinstimmt. Der Artikel liefert Beispiele, Probleme und Lösungen.
Algorithm
Frühere Suchalgorithmen führten zu einem Backtracking, wenn eine teilweise erfolgreiche Suche kein Ergebnis lieferte.Im Kompilierungsmodus funktioniert der Algorithmus nicht mit Symbolen. Es übergibt Anweisungen an kompilierten Code. Die Ausführung ist sehr schnell – nach der Übergabe der Daten an den Anfang der aktuellen Liste wird automatisch nach allen möglichen aufeinanderfolgenden Zeichen im regulären Ausdruck gesucht.
Der Kompilierungs- und Suchalgorithmus ist als kontextbezogene Suche im Time-Sharing-Texteditor enthalten. Natürlich ist dies bei weitem nicht die einzige Anwendung eines solchen Suchverfahrens. Eine Variante dieses Algorithmus wird beispielsweise als Symbolsuche in einer Tabelle im Assembler verwendet.
Es wird davon ausgegangen, dass der Leser mit regulären Ausdrücken und der Computerprogrammiersprache IBM 7094 vertraut ist.Compiler
Der Compiler besteht aus drei parallel laufenden Stufen. Die erste Stufe ist die Syntaxfilterung, die nur syntaktisch korrekte reguläre Ausdrücke durchlässt. In diesem Schritt wird auch der Operator „·“ eingefügt, um reguläre Ausdrücke abzugleichen. Im zweiten Schritt wird der reguläre Ausdruck in die Postfix-Form umgewandelt. Im dritten Schritt wird Objektcode erstellt. Die ersten beiden Phasen liegen auf der Hand und wir werden nicht näher darauf eingehen.
In Thompsons Artikel geht es nicht um nichtdeterministische Finite-State-Maschinen, aber er erklärt den linearen Zeitalgorithmus gut und stellt ein ALGOL-60-Programm vor, das Assembler-Code für den IBM 7094 generiert. Die Implementierung ist knifflig, aber die Idee ist sehr einfach.
aktueller Suchpfad. Es wird durch ein ⊕-Symbol mit einem Eingang und zwei Ausgängen dargestellt.
Abbildung 1 zeigt die Funktionen des dritten Kompilierungsschritts bei der Transformation eines Beispiels für einen regulären Ausdruck. Die ersten drei Zeichen im Beispiel sind a, b, c und jedes erstellt einen Stapeleintrag S[i] und ein NNODE-Feld.NNODE zu vorhandenem Code, um den resultierenden regulären Ausdruck in einem einzelnen Stapeleintrag zu generieren (siehe Abbildung 5)
So würde ein regulärer Ausdruck aussehen .*.*=.*, wenn man es sich wie auf den Bildern aus Thompsons Artikel vorstellt.
In Abb. 0 gibt es fünf Zustände, die bei 0 beginnen, und 3 Zyklen, die bei den Zuständen 1, 2 und 3 beginnen. Diese drei Zyklen entsprechen drei .* in einem regulären Ausdruck. 3 Ovale mit Punkten entsprechen einem Symbol. Oval mit einem Schild = entspricht einem wörtlichen Zeichen =. Zustand 4 ist endgültig. Wenn wir es erreichen, wird der reguläre Ausdruck abgeglichen.
Erfahren Sie, wie ein solches Zustandsdiagramm für den Abgleich regulärer Ausdrücke verwendet werden kann .*.*=.*, schauen wir uns den String-Matching an x=x. Das Programm startet im Zustand 0, wie in Abb. 1.
Damit dieser Algorithmus funktioniert, muss sich die Zustandsmaschine gleichzeitig in mehreren Zuständen befinden. Eine nichtdeterministische endliche Maschine führt alle möglichen Übergänge gleichzeitig durch.
Bevor es Zeit hat, die Eingabedaten zu lesen, wechselt es in die beiden ersten Zustände (1 und 2), wie in Abb. 2.
In Abb. 2 zeigt, was passiert, wenn er sich das erste ansieht x в x=x. x kann dem obersten Punkt zugeordnet werden, von Zustand 1 und zurück zu Zustand 1. Oder x kann auf den Punkt unten abgebildet werden, von Zustand 2 und zurück zu Zustand 2.
Nach dem Abgleich mit dem ersten x в x=x Wir befinden uns immer noch in den Zuständen 1 und 2. Wir können Zustand 3 oder 4 nicht erreichen, weil wir einen wörtlichen Charakter benötigen =.
Der Algorithmus berücksichtigt dann = в x=x. Wie x zuvor kann es einer der beiden oberen Schleifen von Zustand 1 zu Zustand 1 oder von Zustand 2 zu Zustand 2 zugeordnet werden, der Algorithmus kann jedoch mit dem Literal übereinstimmen = und wechseln Sie von Zustand 2 zu Zustand 3 (und sofort zu Zustand 4). Dies ist in Abb. dargestellt. 3.
Der Algorithmus fährt dann mit dem letzten fort x в x=x. Von den Zuständen 1 und 2 sind die gleichen Übergänge zurück zu den Zuständen 1 und 2 möglich. Von Zustand 3 x kann mit dem Punkt rechts übereinstimmen und zu Zustand 3 zurückkehren.
Zu diesem Zeitpunkt jeder Charakter x=x berücksichtigt, und da wir Zustand 4 erreicht haben, stimmt der reguläre Ausdruck mit dieser Zeichenfolge überein. Jedes Zeichen wird einmal verarbeitet, daher ist dieser Algorithmus linear in der Länge der Eingabezeichenfolge. Und kein Zurückverfolgen.
Offensichtlich nach Erreichen von Zustand 4 (wenn der Algorithmus übereinstimmt). x=) wird der gesamte reguläre Ausdruck abgeglichen und der Algorithmus wird möglicherweise beendet, ohne ihn überhaupt zu berücksichtigen x.
Dieser Algorithmus hängt linear von der Größe der Eingabezeichenfolge ab.
Source: habr.com