Viru bal 9 Joer war Cloudflare eng kleng Firma, an ech hunn net dofir geschafft, ech war just e Client. E Mount nodeems ech Cloudflare gestart hunn, krut ech eng Notifikatioun datt meng Websäit DNS schéngt net ze schaffen. Cloudflare huet eng Ännerung gemaach , an et war e futtis DNS.
Ech hunn direkt dem Matthew Prince mam Titel "Wou ass meng DNS?" geschriwwen an hien huet eng laang Äntwert voller technesch Detailer zréckgeschéckt (), op déi ech geäntwert hunn:
Vun: John Graham-Cumming
Datum: 7. Oktober 2010, 9:14
Betreff: Re: Wou ass meng DNS?
An: Matthew PrënzCoole Bericht, merci. Ech wäert definitiv ruffen wann et Problemer ginn. Et ass wahrscheinlech derwäert e Post iwwer dëst ze schreiwen wann Dir all technesch Informatioun gesammelt hutt. Ech denken, datt d'Leit eng oppen an éierlech Geschicht genéissen. Besonnesch wann Dir Grafike befestegt fir ze weisen wéi de Traffic zënter dem Start gewuess ass.
Ech hu gutt Iwwerwaachung op mengem Site, an ech kréien eng SMS iwwer all Echec. D'Iwwerwaachung weist datt de Feeler vun 13:03:07 bis 14:04:12 geschitt ass. Tester ginn all fënnef Minutten duerchgefouert.
Ech sécher Dir wäert et Figur eraus. Sidd Dir sécher, datt Dir net Är eege Persoun an Europa brauchen? 🙂
An hien huet geäntwert:
Vun: Matthew Prënz
Datum: 7. Oktober 2010, 9:57
Betreff: Re: Wou ass meng DNS?
An: John Graham-CummingMerci. Mir hu jidderengem geäntwert, dee geschriwwen huet. Ech sinn elo op de Büro ënnerwee a mir schreiwen eppes um Blog oder setzen en offiziellen Post op eisem Bulletin Board. Ech averstanen ganz, Éierlechkeet ass alles.
Elo ass Cloudflare eng wierklech grouss Firma, ech schaffen dofir, an elo muss ech offen iwwer eise Feeler schreiwen, seng Konsequenzen an eis Handlungen.
Evenementer vum 2. Juli
Den 2. Juli hu mir eng nei Regel a Managed Rules fir WAFs ausgerullt wéinst deem op all Prozessor Kärveraarbechtung HTTP/HTTPS Traffic am Cloudflare Netzwierk weltwäit. Mir verbesseren permanent verwaltete Reegele fir WAFs als Äntwert op nei Schwachstelle a Geforen. Am Mee, zum Beispill, hu mer eis séier gemaach fir géint eng schlëmm Schwachstelle am SharePoint ze schützen. De ganze Punkt vun eisem WAF ass d'Fäegkeet fir séier a global Reegelen z'installéieren.
Leider huet den Update vum leschten Donneschdeg e reegelméissegen Ausdrock enthale deen ze vill HTTP/HTTPS CPU Ressourcen op Backtracking verschwenden. Eis Kär Proxy, CDN, a WAF Funktiounen leiden als Resultat. D'Grafik weist datt d'Prozessorressourcen fir den HTTP/HTTPS Traffic ze servéieren bal 100% op Serveren an eisem Netz erreechen.
CPU Notzung op engem Punkt vun der Präsenz während engem Tëschefall
Als Resultat hunn eis Clienten (an eise Clienten hir Clienten) mat enger 502 Fehler Säit op Cloudflare Domainen opgehalen. 502 Fehler goufe vu Cloudflare Front-End Webserver generéiert, déi nach ëmmer gratis Cores haten, awer net fäeg sinn mat Prozesser ze kommunizéieren, déi den HTTP / HTTPS Traffic behandelen.
Mir wëssen wéi vill Nodeel dëst eise Clienten verursaacht huet. Mir schummen eis schrecklech. An dësen Echec huet eis verhënnert effektiv mam Tëschefall ëmzegoen.
Wann Dir ee vun dëse Clienten war, Dir sidd wahrscheinlech Angscht, rosen an opgeregt. Ausserdeem hu mir keng . Den héije CPU Konsum war wéinst enger WAF Regel mat engem schlecht formuléierten regulären Ausdrock, deen zu exzessive Backtracking gefouert huet. Hei ass de schëllegen Ausdrock: (?:(?:"|'|]|}||d|(?:nan|infinity|true|false|null|undefined|symbol|math)|`|-|+)+[)]*;?((?:s|-|~|!|{}||||+)*.*(?:.*=.*)))
Och wann dëst interessant ass a sech selwer (an ech wäert et méi detailléiert drënner schwätzen), war de Cloudflare Service fir 27 Minutten erof net nëmme wéinst engem schlechten reguläre Ausdrock. Et huet eis eng Zäit gedauert fir d'Sequenz vun den Eventer ze beschreiwen, déi zum Echec gefouert hunn, also ware mir lues ze reagéieren. Um Enn vum Post wäert ech d'Backtracking an engem reguläre Ausdrock beschreiwen an Iech soen wat Dir domat maache musst.
Wat ass geschitt
Loosst eis an Uerdnung ufänken. All Zäiten hei sinn an UTC.
Um 13:42 Auer huet en Ingenieur vum Firewall Team eng kleng Ännerung un d'Detektiounsregelen gemaach mat engem automateschen Prozess. Deementspriechend gouf e Changement Ufro Ticket erstallt. Mir verwalten esou Ticketen duerch Jira (Screenshot ënnert).
No 3 Minutten ass déi éischt Säit vum PagerDuty opgetaucht, e Problem mam WAF bericht. Dëst war e syntheteschen Test deen d'Funktionalitéit vu WAFs testt (mir hunn Honnerte vun hinnen) ausserhalb vu Cloudflare fir normal Operatioun ze iwwerwaachen. Dëst gouf direkt gefollegt vu Säite vun Alarmer iwwer aner Cloudflare End-to-End Service Tester, déi feelen, global Verkéiersprobleemer, verbreet 502 Feeler, an eng Tonn vu Berichter vun eise Points of Presence (PoP) a Stied ronderëm d'Welt, déi e Manktem uginn. vun CPU Ressourcen.
Ech krut e puer vun dësen Alarmer, sinn aus enger Versammlung gestiermt a war um Wee op den Dësch wéi de Chef vun eiser Léisungsentwécklungsdepartement gesot huet datt mir 80% vun eisem Traffic verluer hunn. Ech sinn bei eis SRE Ingenieuren gelaf, déi scho mam Problem geschafft hunn. Am Ufank hu mir geduecht datt et eng Aart vun onbekannter Attack wier.
Cloudflare SRE Ingenieuren sinn ronderëm d'Welt verspreet a iwwerwaachen d'Situatioun ronderëm d'Auer. Normalerweis informéieren dës Alarmer Iech iwwer spezifesch lokal Themen vu limitéierten Ëmfang, ginn op internen Dashboards verfollegt a ginn e puer Mol am Dag geléist. Awer dës Säiten an Notifikatiounen hunn eppes wierklech eescht uginn, an SRE Ingenieuren hunn direkt d'Gravitéitsniveau P0 deklaréiert a kontaktéiert Gestioun a Systemingenieuren.
Eis London Ingenieuren hunn dee Moment e Virtrag an der Haaptsall gelauschtert. De Virtrag huet missen ënnerbrach ginn, jiddereen huet sech an engem grousse Konferenzsall versammelt, a méi Spezialisten goufen geruff. Dëst war keen typesche Problem deen d'SREs mat sech selwer këmmeren. Et war dréngend déi richteg Spezialisten anzebezéien.
Um 14:00 hu mir festgestallt, datt de Problem bei der WAF war an et keng Attack gouf. D'Performance-Team huet d'CPU-Daten gezunn an et gouf kloer datt de WAF d'Schold war. En aneren Employé bestätegt dës Theorie mat Strace. Een aneren huet an de Logbicher gesinn datt et e Problem mat WAF gouf. Um 14:02 ass d'ganz Team bei mech komm wann et proposéiert gouf global Kill ze benotzen, e Mechanismus agebaut an Cloudflare deen ee Komponent weltwäit ausschalt.
Wéi mir global Kill fir WAF gemaach hunn ass eng aner Geschicht. Et ass net sou einfach. Mir benotzen eis eege Produkter, an zënter eisem Service huet net geschafft, mir konnten net authentifizéieren an an d'intern Kontrollpanel aloggen (wann alles fixéiert war, hu mir geléiert datt e puer Teammemberen Zougang verluer haten wéinst enger Sécherheetsfunktioun déi Umeldungsinformatiounen ausschalten wann d'intern Kontrollpanel net benotzt gëtt fir eng laang Zait).
A mir konnten net op eis intern Servicer kommen, wéi Jira oder de Bausystem. Mir hunn e Workaround Mechanismus gebraucht, dee mir selten benotzt hunn (dëst muss och ausgeschafft ginn). Endlech huet een Ingenieur et fäerdeg bruecht de WAF um 14:07 auszeschalten, an um 14:09 waren de Traffic an d'CPU Niveauen iwwerall erëm normal. De Rescht vu Cloudflare Schutzmechanismen hunn normal geschafft.
Dunn hu mer eis ugefang fir de WAF ze restauréieren. D'Situatioun war aussergewéinlech, also hu mir negativ Tester gemaach (ufroen ob d'Ännerung wierklech de Problem war) a positiv Tester (fir sécher ze stellen datt d'Rollback funktionnéiert) an enger Stad mat getrennten Traffic, déi bezuelte Clienten vun do iwwerginn.
Um 14:52 ware mir iwwerzeegt datt mir de Grond verstanen hunn an eng Korrektur gemaach hunn, an de WAF erëm aktivéiert hunn.
Wéi Cloudflare funktionnéiert
Cloudflare huet en Team vun Ingenieuren gewidmet fir d'Regele fir WAFs ze managen. Si beméien d'Erkennungsraten ze verbesseren, falsch Positiver ze reduzéieren a séier op nei Bedrohungen z'äntweren wéi se entstinn. An de leschten 60 Deeg goufen et 476 Ännerungsufroe fir verwaltete Regele fir WAF veraarbecht (an der Moyenne vun enger all 3 Stonnen).
Dës speziell Ännerung muss am Simulatiounsmodus ofgesat ginn, wou de richtege Clientverkéier duerch d'Regel passéiert, awer näischt ass blockéiert. Mir benotzen dëse Modus fir d'Effizienz vun de Regelen ze testen an déi falsch positiv a falsch negativ Tariffer ze moossen. Awer och am Simulatiounsmodus mussen d'Regelen tatsächlech ausgefouert ginn, an an dësem Fall enthält d'Regel e reguläre Ausdrock deen ze vill Prozessorressourcen verbraucht.
Wéi Dir aus der Ännerungsufro uewen kënnt gesinn, hu mir en Deploymentplang, e Rollback Plang, an e Link op eng intern Standardbetribsprozedur (SOP) fir dës Zort Deployment. De SOP fir eng Regel z'änneren erlaabt datt se weltwäit publizéiert ginn. Eigentlech, bei Cloudflare ginn d'Saache komplett anescht gemaach, an de SOP diktéiert datt mir d'Software fir d'Test an d'intern Notzung fir d'éischt op en internen Point of Presence (PoP) verschécken (deen eis Mataarbechter benotzen), dann un eng kleng Zuel vu Clienten an eng isoléiert Plaz, dann zu enger grousser Zuel vu Clienten, an nëmmen dann op d'ganz Welt.
Dëst ass wéi et ausgesäit. Mir benotzen git intern iwwer BitBucket. Ingenieuren, déi un Ännerungen schaffen, presentéieren Code, deen op TeamCity gebaut ass, a wann de Bau passéiert, ginn Rezensiounen zougewisen. Wann eng Pull-Ufro guttgeheescht ass, gëtt de Code zesummegesat an eng Serie vun Tester ginn (erëm) ausgefouert.
Wann de Bau an d'Tester erfollegräich ofgeschloss sinn, gëtt eng Ännerungsufro am Jira erstallt an de passenden Manager oder Lead muss d'Ännerung stëmmen. No der Genehmegung geschitt d'Deployment an déi sougenannt "PoP Menagerie": DOG, PIG a (Hond, Schwäin a Kanaren).
DOG PoP ass e Cloudflare PoP (wéi all aner vun eise Stied) deen nëmme vu Cloudflare Mataarbechter benotzt gëtt. PoP fir intern Notzung erlaabt Iech Problemer ze fangen ier de Client Traffic ufänkt an d'Léisung ze fléissen. Nëtzlech Saach.
Wann den DOG Test erfollegräich ass, bewegt de Code op d'PIG (Meerschwäin) Bühn. Dëst ass Cloudflare PoP, wou eng kleng Quantitéit gratis Client Traffic duerch neie Code fléisst.
Wann alles gutt ass, geet de Code an Kanaresch. Mir hunn dräi Kanaresch PoPs a verschiddenen Deeler vun der Welt. An hinnen passéiert de Verkéier vu bezuelte a gratis Clienten duerch den neie Code, an dëst ass déi lescht Kontroll fir Feeler.
Software Release Prozess bei Cloudflare
Wann de Code op Kanaresch ok ass, verëffentlechen mir et. Duerch all Etappe goen - DOG, PIG, Kanaresch, d'ganz Welt - dauert e puer Stonnen oder Deeg, ofhängeg vun der Code änneren. Wéinst der Diversitéit vum Cloudflare Netzwierk a Clienten, testen mir de Code grëndlech ier se et weltwäit un all Clienten verëffentlecht. Awer WAF verfollegt dëse Prozess net spezifesch well Gefore musse séier reagéiert ginn.
WAF Geforen
An de leschte Joren ass et eng bedeitend Erhéijung vun de Gefore bei gemeinsamen Uwendungen ginn. Dëst ass wéinst der méi grousser Disponibilitéit vu Software Testinstrumenter. Zum Beispill, mir geschriwwen kuerzem iwwer ).
Source:
Ganz dacks gëtt e Beweis vum Konzept erstallt an direkt op Github publizéiert, sou datt d'Teams, déi d'Applikatioun erhalen, se séier testen an sécherstellen datt se adäquat geséchert ass. Dofir brauch Cloudflare d'Fäegkeet fir sou séier wéi méiglech op nei Attacken ze reagéieren, sou datt d'Clienten d'Méiglechkeet hunn hir Software ze fixéieren.
E super Beispill vu Cloudflare seng séier Äntwert ass d'Deployment vu SharePoint Schwachstelle Schutz am Mee (). Bal direkt nodeems d'Ukënnegung gemaach goufen, hu mir eng riesech Unzuel u Versuche gemierkt fir d'Schwachheet an de SharePoint-Installatiounen vun eise Clienten auszenotzen. Eis Kärelen iwwerwaachen dauernd nei Bedrohungen a schreiwen Regele fir eis Clienten ze schützen.
D'Regel, déi de Problem en Donneschdeg verursaacht huet, sollt géint Cross-Site Scripting (XSS) schützen. Esou Attentater sinn och an de leschte Jore vill méi heefeg ginn.
Source:
D'Standardprozedur fir eng verwaltet Regel fir e WAF z'änneren ass kontinuéierlech Integratioun (CI) Tester virum globalen Deployment ze maachen. Leschten Donneschdeg hu mir dat gemaach an d'Regelen ausgerullt. Um 13:31 huet en Ingenieur eng guttgeheescht Pull-Ufro mat enger Ännerung ofginn.
Um 13:37 huet TeamCity d'Regelen gesammelt, Tester gemaach an de Go-Ahead ginn. D'WAF Test Suite testt d'Kärfunktioun vum WAF a besteet aus enger grousser Unzuel vun Eenheetstester fir eenzel Funktiounen. No Eenheetstester hu mir d'Regele fir de WAF getest mat enger riesecher Unzuel vun HTTP-Ufroen. HTTP-Ufroe kontrolléieren wéi eng Ufroe solle vum WAF blockéiert ginn (fir d'Attack z'ënnerscheeden) a wat erlaabt ass (fir alles net ze blockéieren a falsch Positiver ze vermeiden). Awer mir hunn net fir exzessiv CPU Benotzung getest, an d'Logbicher vu fréiere WAF baut iwwerpréift weist datt d'Regeltest Ausféierungszäit net eropgeet, an et war schwéier ze verdächtegen datt et net genuch Ressourcen gëtt.
D'Tester sinn passéiert an TeamCity huet ugefaang d'Ännerung automatesch um 13:42 z'installéieren.
récu-
WAF Regele konzentréieren sech op direkt Bedrohungssanéierung, sou datt mir se benotze mat dem Quicksilver verdeelt Schlësselwäertgeschäft, deen Ännerungen weltwäit a Sekonnen propagéiert. All eis Clientë benotzen dës Technologie wann se d'Konfiguratioun am Dashboard oder iwwer d'API änneren, an et ass dank et datt mir mat Blitzgeschwindegkeet op Ännerungen reagéieren.
Mir hunn net vill iwwer Quicksilver geschwat. Virdrun hu mir benotzt als global verdeelt Schlëssel-Wäert Buttek, mä et waren operationell Problemer mat et, a mir geschriwwen eisen eegene Buttek, replizéiert an méi wéi 180 Stied. Mir benotzen elo Quicksilver fir Konfiguratiounsännerungen u Clienten ze drécken, WAF Regelen ze aktualiséieren an JavaScript Code ze verdeelen, geschriwwe vu Clienten un Cloudflare Workers.
Et dauert nëmmen e puer Sekonnen aus engem Klick op e Knäppchen op engem Dashboard oder engem API ruffen fir eng Konfiguratioun änneren weltwäit. D'Clientë hunn dës Geschwindegkeet vum Setup gär. An d'Aarbechter ginn hinnen bal instantane global Software Deployment. Am Duerchschnëtt propagéiert Quicksilver ongeféier 350 Ännerungen pro Sekonn.
A Quicksilver ass ganz séier. Am Duerchschnëtt hu mir den 99. Prozentsaz vun 2,29 Sekonnen erreecht fir Ännerungen op all Computer weltwäit ze propagéieren. Geschwindegkeet ass normalerweis eng gutt Saach. No allem, wann Dir eng Funktioun aktivéiert oder de Cache läscht, geschitt et bal direkt an iwwerall. Code duerch Cloudflare Workers schécken geschitt mat der selwechter Geschwindegkeet. Cloudflare versprécht senge Clienten séier Updates zu der richteger Zäit.
Awer an dësem Fall huet d'Vitesse e grausame Witz op eis gespillt, an d'Regele geännert iwwerall an e puer Sekonnen. Dir hutt vläicht gemierkt datt de WAF Code Lua benotzt. Cloudflare benotzt Lua extensiv a Produktioun an Detailer mir sinn . Lua WAF benotzt intern an applizéiert backtracking fir passende. Et huet keng Mechanismen fir géint Ausdréck ze schützen déi ausser Kontroll kommen. Drënner wäert ech méi iwwer dëst schwätzen a wat mir doriwwer maachen.
Ier d'Regelen ofgesat goufen, ass alles glat gaang: d'Pull-Ufro gouf erstallt an guttgeheescht, d'CI / CD Pipeline huet de Code gesammelt an getest, d'Ännerungsufro gouf no dem SOP proposéiert, deen d'Deployment an d'Rollback regéiert, an d'Deployment gouf ofgeschloss.
Cloudflare WAF Deployment Prozess
Wat ass falsch gaang
Wéi gesot, mir setzen Dosende vun neie WAF Reegelen all Woch an, a mir hu vill Systemer op der Plaz fir géint déi negativ Konsequenze vun esou Asaz ze schützen. A wann eppes falsch geet, ass et normalerweis eng Kombinatioun vu verschiddenen Ëmstänn gläichzäiteg. Wann Dir just ee Grond fannt, ass dëst natierlech berouegend, awer et ass net ëmmer wouer. Dëst sinn d'Grënn, déi zesummen zum Echec vun eisem HTTP/HTTPS Service gefouert hunn.
- En Ingenieur huet e reegelméissegen Ausdrock geschriwwen, deen zu exzessive Resultat kann .
- Eng Feature déi verhënnert hätt datt de regulären Ausdrock ze vill CPU verschwende konnt, gouf falsch an enger Refactoring vum WAF e puer Woche virdru geläscht - d'Refactoring war gebraucht fir datt de WAF manner Ressourcen verbraucht.
- De reguläre Ausdrockmotor huet keng Komplexitéitsgarantien.
- D'Testsuite konnt net exzessive CPU-Verbrauch erkennen.
- De SOP erlaabt net-dréngend Regelännerungen weltwäit auszerollen ouni e Multi-Step Prozess.
- De Rollback Plang erfuerdert zweemol e komplette WAF Build ze lafen, wat laang gedauert huet.
- Déi éischt Alarm iwwer global Verkéiersproblemer gouf ze spéit ausgeléist.
- Mir hunn eng Zäit gedauert fir d'Statussäit ze aktualiséieren.
- Mir haten Problemer mat Zougang zu Systemer wéinst engem glitch, an der Contournement Prozedur war net gutt etabléiert.
- SRE Ingenieuren hunn den Zougang zu e puer Systemer verluer well hir Umeldungsinformatiounen aus Sécherheetsgrënn ofgelaf sinn.
- Eis Clientë haten keen Zougang zum Cloudflare Dashboard oder API well se duerch eng Cloudflare Regioun goen.
Wat huet sech zënter leschten Donneschdeg geännert
Als éischt hu mir all Aarbecht op Verëffentlechunge fir WAF komplett gestoppt a maachen déi folgend:
- Mir stellen den CPU-Iwwerverbrauchsschutz nei, dee mir ewechgeholl hunn. (prett)
- Manuell iwwerpréift all 3868 Regelen an de verwaltete Regele fir de WAF fir aner potenziell Fälle vun exzessive Backtracking ze fannen an ze korrigéieren. (Verifikatioun fäerdeg)
- Mir enthalen Leeschtungsprofiléierung fir all Regelen am Testset. (Erwaart: 19. Juli)
- Wiessel op eng regulär Ausdrock Motor oder - béid bidden Runtime Garantien. (Erwaart: 31. Juli)
- Mir schreiwen de SOP fir Reegelen an Etappen z'installéieren, wéi aner Software an Cloudflare, awer gläichzäiteg d'Fäegkeet hunn d'global Deployment ze Noutfall wann Attacke scho ugefaang hunn.
- Mir entwéckelen d'Fäegkeet fir d'Cloudflare Dashboard an API dréngend aus der Cloudflare Regioun ze läschen.
- Automatiséieren Säit Aktualiséierungen .
Laangfristeg plënnere mir ewech vum Lua WAF, deen ech virun e puer Joer geschriwwen hunn. Plënneren WAF zu . Esou wäert de WAF méi séier sinn an en zousätzleche Schutzniveau kréien.
Konklusioun
Dëse Versoen huet Problemer fir eis an eise Clienten verursaacht. Mir hu séier gehandelt fir d'Situatioun ze korrigéieren a schaffen elo un de Mängel an de Prozesser, déi de Crash verursaacht hunn, wéi och nach méi déif gegruewen fir géint potenziell Probleemer mat regelméissegen Ausdréck an der Zukunft ze schützen wann Dir op nei Technologie migréiert.
Mir sinn ganz ongenéiert iwwer dësen Ausfall an entschëllegen eis Clienten. Mir hoffen datt dës Ännerunge garantéieren datt sou eppes net erëm geschitt.
Applikatioun. Backtracking regelméisseg Ausdréck
Fir ze verstoen wéi den Ausdrock:
(?:(?:"|'|]|}||d
(?:nan|infinity|true|false|null|undefined|symbol|math)|`|-
|+)+[)]*;?((?:s|-|~|!|{}||||+)*.*(?:.*=.*)))giess all CPU Ressourcen, Dir musst e bësse wëssen, wéi de Standard regulären Ausdrock Motor Wierker. De Problem hei ass d'Muster .*(?:.*=.*). (?: an entspriechend ) ass eng net erfaassend Grupp (dat ass, den Ausdrock an parentheses ass als eenzegen Ausdrock gruppéiert).
Am Kontext vun exzessiv CPU Konsum, kann dëst Muster beschriwwe ginn als .*.*=.*. An dëser Form gesäit d'Muster onnéideg komplex aus. Awer méi wichteg, an der realer Welt, Ausdréck (wéi komplex Ausdréck an WAF Regelen), déi de Motor froen fir e Fragment ze passen, gefollegt vun engem anere Fragment, kënnen zu katastrophale Réckzuch féieren. An dofir.
Am reguläre Ausdrock . heescht Dir musst ee Charakter passen, .* - Match null oder méi Zeeche "gierig", dat heescht, e Maximum vun Zeechen erfaassen, sou datt .*.*=.* heescht Match null oder méi Zeechen, dann Match null oder méi Zeechen, fannen de wuertwiertlech = Charakter, Match null oder méi Zeechen.
Loosst eis d'Testlinn huelen x=x. Et entsprécht dem Ausdrock .*.*=.*. .*.* ier d'Gläichheetsschëld déi éischt entsprécht x (eng vun de Gruppen .* entsprécht x, an déi zweet - null Zeechen). .* no = Matcher lescht x.
Dëse Verglach erfuerdert 23 Schrëtt. Éischt Grupp .* в .*.*=.* handelt giereg a passt op de ganze String x=x. De Motor geet op déi nächst Grupp .*. Mir hu keng Zeeche méi ze passen, also déi zweet Grupp .* entsprécht null Zeechen (dëst ass erlaabt). Da geet de Motor op d'Schëld =. Et gi keng Symboler méi (éischt Grupp .* de ganzen Ausdrock benotzt x=x), kee Verglach geschitt.
An da geet de regulären Ausdrockmotor zréck an den Ufank. Hie geet op déi éischt Grupp .* a vergläicht et с x= (amplaz x=x), an iwwerhëlt dann déi zweet Grupp .*. Zweet Grupp .* gëtt mat der zweeter verglach x, a mir hunn erëm keng Zeeche méi. A wann de Motor erëm erreecht = в .*.*=.*, näischt funktionnéiert. An hien geet erëm zréck.
Dës Kéier de Grupp .* nach Mätscher x=, mä déi zweet Grupp .* net méi x, an null Zeechen. De Motor probéiert e wuertwiertleche Charakter ze fannen = am Muster .*.*=.*, awer kënnt net eraus (schliisslech huet déi éischt Grupp et scho besat .*). An hien geet erëm zréck.
Dës Kéier déi éischt Grupp .* hëlt nëmmen déi éischt x. Awer déi zweet Grupp .* "gierig" erfaasst =x. Hutt Dir scho virgestallt wat wäert geschéien? De Motor probéiert de literareschen ze passen =, klappt a mécht en anere Réckwee.
Éischt Grupp .* entsprécht nach ëmmer déi éischt x... Déi zweet .* nëmmen hëlt =. Natierlech kann de Motor net mat der wuertwiertlech Match =, well déi zweet Grupp huet dat schonn gemaach .*. An erëm zréck. A mir probéieren eng String vun dräi Personnagen ze passen!
Als Resultat, déi éischt Grupp .* entsprécht nëmmen déi éischt x, zweeten .* - mat null Zeechen, an de Motor entsprécht endlech de wuertwiertlech = am Ausdrock с = an der Schlaang. Als nächst ass de leschte Grupp .* gëtt mam leschte verglach x.
23 Schrëtt nëmme fir x=x. Kuckt e kuerze Video iwwer d'Benotzung vu Perl , déi weist wéi Schrëtt a Réckwee optrieden.
Dëst ass scho vill Aarbecht, awer wat wann amplaz x=x mir wäerten hunn x=xx? Dat sinn 33 Schrëtt. A wann x=xxx? 45. D'Relatioun ass net linear. D'Grafik weist e Verglach vun x=x ze x=xxxxxxxxxxxxxxxxxxxx (20 x после =). Wa mir hunn 20 x na =, de Motor fäerdeg de Match an 555 Schrëtt! (Ausserdeem, wa mir verluer hunn x= an de String besteet einfach aus 20 x, De Motor wäert 4067 Schrëtt huelen fir ze verstoen datt et keng Mätscher gëtt).
Dëse Video weist all Backtracking zum Verglach x=xxxxxxxxxxxxxxxxxxxx:
De Problem ass datt wéi d'Stringgréisst eropgeet, d'Mataarbechtungszäit super-linear wiisst. Awer d'Saache kënnen nach méi schlëmm ginn wann de reguläre Ausdrock liicht geännert gëtt. Loosst eis soen, mir haten .*.*=.*; (dat ass, et war e wuertwiertlech Semikolon um Enn vum Muster). Zum Beispill, fir en Ausdrock ze passen wéi foo=bar;.
An hei wier de Réckwee eng richteg Katastroph. Zum Verglach x=x et wäert huelen 90 Schrëtt, net 23. An déi Zuel wiisst séier. Ze vergläichen x= an 20 x, 5353 Schrëtt sinn néideg. Hei ass den Diagramm. Kuckt d'Achswäerter Y am Verglach zu der viregter Grafik.
Wann Dir interesséiert sidd, kuckt all 5353 gescheitert passende Schrëtt x=xxxxxxxxxxxxxxxxxxxx и .*.*=.*;
Andeems Dir faul anstatt giereg Matching benotzt, kann d'Ausmooss vum Backtracking kontrolléiert ginn. Wa mir d'Original Ausdrock änneren ze .*?.*?=.*?, zum Verglach x=x et wäert huelen 11 Schrëtt (net 23). Wéi fir x=xxxxxxxxxxxxxxxxxxxx... Alles well ? после .* seet de Motor fir e Minimum Unzuel vun Zeechen ze passen ier Dir weidergeet.
Awer lazy Mappings léisen de Backtracking Problem net komplett. Wa mir dat katastrophal Beispill ersetzen .*.*=.*; op .*?.*?=.*?;, wäert d'Ausféierung Zäit déi selwecht bleiwen. x=x verlaangt nach 555 Schrëtt, an x= an 20 x - 5353.
Dat eenzegt wat ka gemaach ginn (ausser d'Muster komplett nei ze schreiwen fir méi Spezifizitéit) ass de reguläre Ausdrockmotor mat sengem Backtracking-Mechanismus opzeginn. Dëst wäerte mir an den nächste Wochen maachen.
D'Léisung fir dëse Problem ass zënter 1968 bekannt, wéi de Kent Thompson en Artikel geschriwwen huet ("Programméierungsmethoden: Regular Expression Search Algorithmus"). Den Artikel beschreift e Mechanismus deen Iech erlaabt e regelméissegen Ausdrock an net-deterministesche endlechen Staatsmaschinnen ze konvertéieren, an no Staatsännerungen an net-deterministesche endlechen Staatsmaschinnen benotzt en Algorithmus deem seng Ausféierungszäit linear vun der ugepasste String hänkt.
Programméiere Methoden
Regelméisseg Ausdrock Sich Algorithmus
Ken Thompson
Bell Telephone Laboratories, Inc., Murray Hill, New JerseyEt beschreift eng Method fir no enger spezifescher String vun Zeechen am Text ze sichen an diskutéiert d'Ëmsetzung vun dëser Method a Compilerform. De Compiler hëlt de regulären Ausdrock als Quellcode a produzéiert den IBM 7094 Programm als Objektcode. Den Objektprogramm hëlt Input a Form vu Sichtext an emittéiert e Signal all Kéier wann eng String vum Text mat engem bestëmmte reguläre Ausdrock passt. Den Artikel gëtt Beispiller, Problemer a Léisungen.
Algorithmus
Virdrun Sich Algorithmen hunn zu Réckwee gefouert wann eng deelweis erfollegräich Sich net e Resultat produzéiert huet.Am Compilatiounsmodus funktionnéiert den Algorithmus net mat Symboler. Et passéiert Instruktioune fir de kompiléierte Code. D'Ausféierung ass ganz séier - nodeems Dir Daten un d'Spëtzt vun der aktueller Lëscht passéiert, sicht se automatesch no all méigleche konsekutiv Zeechen am reguläre Ausdrock.
De Kompiléierungs- a Sichalgorithmus ass am Time-Sharing Text Editor als kontextuell Sich abegraff. Natierlech ass dëst wäit vun der eenzeger Uwendung vun esou enger Sichprozedur. Zum Beispill gëtt eng Variant vun dësem Algorithmus als Symbol Sich an enger Tabell am Assembler benotzt.
Et gëtt ugeholl datt de Lieser mat reguläre Ausdréck an der IBM 7094 Computerprogramméierungssprooch vertraut ass.Compiler
De Compiler besteet aus dräi Etappen déi parallel lafen. Déi éischt Stuf ass d'Syntaxfilterung, déi et erlaabt nëmme syntaktesch korrekt regulär Ausdréck duerchzegoen. Dëse Schrëtt setzt och den "·" Bedreiwer fir regelméisseg Ausdréck ze passen. Am zweete Schrëtt gëtt de reguläre Ausdrock an d'Postfix Form ëmgewandelt. Op der drëtter Stuf gëtt den Objektcode erstallt. Déi éischt 2 Etappe sinn offensichtlech, a mir wäerten net op se bleiwen.
Dem Thompson säin Artikel schwätzt net iwwer nondeterministesch endlech Staatsmaschinnen, awer et erkläert de linear Zäitalgorithmus gutt a stellt en ALGOL-60 Programm vir, deen Assemblée Sproochcode fir den IBM generéiert 7094. D'Ëmsetzung ass komplizéiert, awer d'Iddi ass ganz einfach.
aktuell Sich Wee. Et gëtt duerch eng ⊕ Ikon mat engem Input an zwee Ausgänge vertruede.
Figur 1 weist d'Funktioune vum drëtte Kompiléierungsschrëtt wann Dir e reguläre Ausdrock Beispill transforméiert. Déi éischt dräi Zeechen am Beispill sinn a, b, c, an all schaaft e Stack Entrée S [i] an engem NNODE Feld.NNODE op existente Code fir de resultéierende reguläre Ausdrock an enger eenzeger Stackentrée ze generéieren (kuckt Figur 5)
Dëst ass wéi e reguläre Ausdrock ausgesäit .*.*=.*, Wann Dir Iech et virstellt wéi an de Biller vum Thompson sengem Artikel.
An Fig. 0 ginn et fënnef Staaten ab 0, an 3 Zyklen, déi vun Staaten 1, 2 an 3 ufänken. Dës dräi Zyklen entspriechen dräi .* an engem reguläre Ausdrock. 3 Ovalen mat Punkte entspriechen engem Symbol. Oval mat engem Schëld = entsprécht engem wuertwiertleche Charakter =. Staat 4 ass final. Wa mir et erreechen, da gëtt de reguläre Ausdrock ugepasst.
Fir ze kucken wéi esou e Staatsdiagramm fir regulär Ausdrock passend benotzt ka ginn .*.*=.*, mir kucken op String Matching x=x. De Programm fänkt vum Staat 0 un, wéi an der Fig. 1.
Fir datt dësen Algorithmus funktionnéiert, muss d'Staatsmaschinn a verschiddene Staaten gläichzäiteg sinn. Eng net-deterministesch finite Maschinn wäert all méiglech Iwwergäng gläichzäiteg maachen.
Ier et Zäit huet d'Inputdaten ze liesen, geet et a béid éischt Staaten (1 an 2), wéi an der Fig. 2.
An Fig. 2 weist wat geschitt wann hien op déi éischt kuckt x в x=x. x kann op den Top Punkt Kaart, aus Staat 1 an zréck op Staat 1. Oder x kann op de Punkt hei ënnen kartéieren, vum Staat 2 an zréck an de Staat 2 goen.
No passenden déi éischt x в x=x mir sinn nach ëmmer an de Staaten 1 an 2. Mir kënnen den Zoustand 3 oder 4 net erreechen, well mir e literaresche Charakter brauchen =.
Den Algorithmus betruecht dann = в x=x. Wéi x virdru, kann et mat entweder vun den Top zwee Schleifen vum Staat 1 op Staat 1 oder vum Staat 2 op Staat 2 ugepasst ginn, awer den Algorithmus kann dem wuertwiertleche passen. = a réckelen vum Staat 2 op Staat 3 (an direkt 4). Dëst ass an der Fig. 3.
Den Algorithmus geet dann op dee leschten x в x=x. Vun Staaten 1 an 2 sinn déi selwecht Iwwergäng méiglech zréck an Staaten 1 an 2. Vun Staat 3 x kann de Punkt op der rietser passen an zréck an de Staat 3.
Op dëser Etapp, all Charakter x=x betruecht, a well mer de Staat erreecht hunn 4, passt de reguläre Ausdrock mat deem String. All Charakter gëtt eemol veraarbecht, sou datt dësen Algorithmus linear an der Längt vun der Input String ass. A kee Réckwee.
Natierlech, nodeems de Staat 4 erreecht huet (wann den Algorithmus ugepasst ass x=) de ganze reguläre Ausdrock passt, an den Algorithmus kann ofschléissen ouni et iwwerhaapt ze berücksichtegen x.
Dësen Algorithmus hänkt linear vun der Gréisst vun der Input String of.
Source: will.com