Antaŭ preskaŭ 9 jaroj Cloudflare estis eta kompanio, kaj mi ne laboris por ĝi, mi estis nur kliento. Monaton post lanĉo de Cloudflare, mi ricevis sciigon pri mia retejo DNS ŝajnas ne funkcii. Cloudflare faris ŝanĝon al , kaj estis rompita DNS.
Mi tuj skribis al Matthew Prince kun la titolo "Kie estas mia DNS?" kaj li resendis longan respondon plenan de teknikaj detaloj (), al kiu mi respondis:
De: John Graham-Cumming
Dato: 7-a de oktobro 2010, 9:14
Temo: Re: Kie estas mia DNS?
Al: Matthew PrinceBonege raporto, dankon. Mi nepre vokos se estos problemoj. Verŝajne indas skribi afiŝon pri tio, kiam vi kolektis ĉiujn teknikajn informojn. Mi pensas, ke homoj ĝuos malferman kaj honestan rakonton. Precipe se vi aldonas al ĝi grafikaĵojn por montri kiel la trafiko kreskis ekde la lanĉo.
Mi havas bonan monitoradon en mia retejo, kaj mi ricevas SMS pri ĉiu malsukceso. Monitorado montras, ke la fiasko okazis de 13:03:07 ĝis 14:04:12. Testoj estas faritaj ĉiujn kvin minutojn.
Mi certas, ke vi eltrovos ĝin. Ĉu vi certas, ke vi ne bezonas vian propran personon en Eŭropo? 🙂
Kaj li respondis:
De: Matthew Prince
Dato: 7-a de oktobro 2010, 9:57
Temo: Re: Kie estas mia DNS?
Al: John Graham-CummingDankon. Ni respondis al ĉiuj, kiuj skribis. Mi nun iras al la oficejo kaj ni skribos ion en la blogo aŭ alpinglos oficialan afiŝon sur nia bulteno. Mi tute konsentas, honesteco estas ĉio.
Nun Cloudflare estas vere granda firmao, mi laboras por ĝi, kaj nun mi devas skribi malkaŝe pri nia eraro, ĝiaj sekvoj kaj niaj agoj.
Okazaĵoj de la 2-a de julio
La 2-an de julio ni lanĉis novan regulon en Administritaj Reguloj por WAF-oj pro tio sur ĉiu procesora kerno prilaboranta HTTP/HTTPS-trafikon en la reto Cloudflare tutmonde. Ni konstante plibonigas administritajn regulojn por WAF-oj responde al novaj vundeblecoj kaj minacoj. En majo, ekzemple, ni rapidis protekti kontraŭ grava vundebleco en SharePoint. La tuta celo de nia WAF estas la kapablo rapide kaj tutmonde deploji regulojn.
Bedaŭrinde, la ĝisdatigo de la pasinta ĵaŭdo enhavis regulan esprimon, kiu malŝparis tro multe da HTTP/HTTPS CPU-resursoj pro retroiro. Nia kerna prokurilo, CDN kaj WAF-funkcioj suferis kiel rezulto. La grafikaĵo montras, ke procesoraj rimedoj por servi HTTP/HTTPS-trafikon atingas preskaŭ 100% ĉe serviloj en nia reto.
CPU-uzo ĉe unu punkto de ĉeesto dum okazaĵo
Kiel rezulto, niaj klientoj (kaj klientoj de niaj klientoj) finis kun 502-erara paĝo en Cloudflare-domajnoj. 502-eraroj estis generitaj de Cloudflare-antaŭfinaj retserviloj, kiuj ankoraŭ havis senpagajn kernojn sed ne povis komuniki kun procezoj pritraktantaj HTTP/HTTPS-trafikon.
Ni scias kiom da ĝeno tio kaŭzis al niaj klientoj. Ni terure hontas. Kaj ĉi tiu malsukceso malhelpis nin efike trakti la okazaĵon.
Se vi estus unu el ĉi tiuj klientoj, vi verŝajne estis timigita, kolera kaj ĉagrenita. Plie, ni ne havis . La alta CPU-konsumo ŝuldiĝis al unu WAF-regulo kun nebone vortigita regula esprimo kiu rezultigis troan malantaŭan spuron. Jen la kulpa esprimo: (?:(?:"|'|]|}||d|(?:nan|infinity|true|false|null|undefined|symbol|math)|`|-|+)+[)]*;?((?:s|-|~|!|{}||||+)*.*(?:.*=.*)))
Kvankam ĉi tio estas interesa en si mem (kaj mi parolos pri ĝi pli detale sube), la servo Cloudflare malfunkciis dum 27 minutoj ne nur pro malbona regula esprimo. Ni bezonis iom por priskribi la sinsekvon de eventoj, kiuj kaŭzis la malsukceson, do ni malrapidis respondi. Je la fino de la afiŝo, mi priskribos retrovojon en regula esprimo kaj diros al vi kion fari kun ĝi.
Kio okazis
Ni komencu en ordo. Ĉiuj tempoj ĉi tie estas en UTC.
Je 13:42 p.m., inĝeniero de la fajroŝirmilo faris malgrandan ŝanĝon al la detektaj reguloj uzante aŭtomatan procezon. Sekve, ŝanĝpeta bileto estis kreita. Ni administras tiajn biletojn per Jira (ekrankopio malsupre).
Post 3 minutoj aperis la unua paĝo de PagerDuty, raportante problemon pri WAF. Ĉi tio estis sinteza testo, kiu testas la funkciecon de WAF-oj (ni havas centojn da ili) ekster Cloudflare por monitori normalan funkciadon. Ĉi tio tuj estis sekvita de paĝoj de atentigoj pri aliaj Cloudflare-fin-al-finaj servaj testoj malsukcesaj, tutmondaj trafikaj problemoj, disvastigitaj 502-eraroj, kaj amaso da raportoj de niaj Punktoj de Ĉeesto (PoP) en urboj ĉirkaŭ la mondo, kiuj indikis mankon. de CPU-resursoj.
Mi ricevis plurajn el ĉi tiuj atentigoj, eliris el kunveno kaj estis survoje al la tablo, kiam la estro de nia disvolva fako de solvoj diris, ke ni perdis 80% de nia trafiko. Mi kuris al niaj SRE-inĝenieroj, kiuj jam laboris pri la problemo. Komence ni pensis, ke ĝi estas ia nekonata atako.
Cloudflare SRE-inĝenieroj estas disigitaj tra la mondo kaj kontrolas la situacion ĉirkaŭ la horloĝo. Tipe, ĉi tiuj atentigoj sciigas vin pri specifaj lokaj problemoj de limigita amplekso, estas spuritaj sur internaj paneloj kaj estas solvitaj plurfoje tage. Sed ĉi tiuj paĝoj kaj sciigoj indikis ion vere seriozan, kaj SRE-inĝenieroj tuj deklaris la severecan nivelon P0 kaj kontaktis administradon kaj sistemajn inĝenierojn.
Niaj Londonaj inĝenieroj aŭskultis prelegon en la ĉefhalo en tiu momento. La prelego devis esti interrompita, ĉiuj kunvenis en granda kongresejo, kaj pli da specialistoj estis alvokitaj. Ĉi tio ne estis tipa problemo, kiun SRE-oj povis trakti sin. Urĝis impliki la ĝustajn specialistojn.
Je 14:00 ni determinis ke la problemo estis kun la WAF kaj ekzistis neniu atako. La spektakloteamo tiris la CPU-datumojn kaj evidentiĝis, ke la WAF kulpas. Alia dungito konfirmis ĉi tiun teorion uzante strace. Iu alia vidis en la protokoloj, ke estis problemo kun WAF. Je 14:02 p.m., la tuta teamo venis al mi kiam oni proponis uzi tutmondan mortigon, mekanismon konstruitan en Cloudflare, kiu malŝaltas unu komponenton tutmonde.
Kiel ni faris tutmondan mortigon por WAF estas malsama rakonto. Ĝi ne estas tiel simpla. Ni uzas niajn proprajn produktojn, kaj ekde nia servo ne funkciis, ni ne povis aŭtentikigi kaj ensaluti en la internan kontrolpanelon (kiam ĉio estis riparita, ni eksciis, ke kelkaj teamanoj perdis la aliron pro sekureca funkcio kiu malŝaltas akreditaĵojn se la interna kontrolpanelo ne estas uzata por longa tempo).
Kaj ni ne povis atingi niajn internajn servojn, kiel Jira aŭ la konstrusistemo. Ni bezonis solvi mekanismon, kiun ni uzis malofte (ĉi tio ankaŭ devos esti ellaborita). Fine, unu inĝeniero sukcesis malŝalti la WAF je 14:07, kaj je 14:09, trafiko kaj CPU-niveloj revenis al normalo ĉie. La resto de la protektaj mekanismoj de Cloudflare funkciis normale.
Tiam ni komencis restarigi la WAF. La situacio estis eksterordinara, do ni kuris negativajn testojn (demandante al ni mem ĉu la ŝanĝo vere estas la problemo) kaj pozitivajn testojn (certante, ke la falo funkciu) en unu urbo uzante apartan trafikon, transdonante pagajn klientojn de tie.
Je 14:52 ni konvinkiĝis, ke ni komprenis la kialon kaj faris korekton, kaj denove ebligis WAF.
Kiel Cloudflare funkcias
Cloudflare havas teamon de inĝenieroj dediĉitaj al administrado de reguloj por WAFoj. Ili strebas plibonigi detektajn indicojn, redukti falsajn pozitivojn kaj rapide respondi al novaj minacoj kiam ili aperas. En la lastaj 60 tagoj, estis 476 ŝanĝpetoj prilaboritaj por administritaj reguloj por WAF (averaĝe unu ĉiu 3 horoj).
Ĉi tiu speciala ŝanĝo devis esti deplojita en simuladreĝimo, kie reala klienttrafiko pasas tra la regulo, sed nenio estas blokita. Ni uzas ĉi tiun reĝimon por testi la efikecon de la reguloj kaj mezuri la malverajn pozitivajn kaj malverajn negativajn indicojn. Sed eĉ en simula reĝimo, la reguloj devas efektive esti ekzekutitaj, kaj ĉi-kaze la regulo enhavis regulan esprimon, kiu konsumis tro multe da procesoraj rimedoj.
Kiel vi povas vidi el la ŝanĝpeto supre, ni havas disfaldan planon, revalidan planon kaj ligon al interna norma operacia proceduro (SOP) por ĉi tiu tipo de deplojo. La SOP por ŝanĝado de regulo permesas ĝin esti publikigita tutmonde. Efektive, ĉe Cloudflare, aferoj estas faritaj tute alimaniere, kaj la SOP diktas, ke ni unue sendas la programaron por testado kaj interna uzo al interna punkto de ĉeesto (PoP) (kiun niaj dungitoj uzas), poste al malgranda nombro da klientoj en izolita loko, poste al granda nombro da klientoj, kaj nur tiam al la tuta mondo.
Jen kiel ĝi aspektas. Ni uzas git interne per BitBucket. Inĝenieroj laborantaj pri ŝanĝoj sendas kodon, kiu estas konstruita al TeamCity, kaj kiam la konstruo pasas, recenzistoj estas asignitaj. Post kiam tira peto estas aprobita, la kodo estas kunvenita kaj serio de testoj estas rulitaj (denove).
Se la konstruo kaj testoj finiĝas sukcese, ŝanĝpeto estas kreita en Jira kaj la taŭga administranto aŭ gvidanto devas aprobi la ŝanĝon. Post aprobo, deplojo okazas en la tielnomitan "PoP menaĝerio": HUNDO, PORKO kaj (hundo, porko kaj kanario).
DOG PoP estas Cloudflare PoP (kiel ĉiu alia el niaj urboj) kiu estas uzata nur de Cloudflare-dungitoj. PoP por interna uzo permesas vin kapti problemojn antaŭ ol klienta trafiko komencas flui en la solvon. Utila afero.
Se la provo de HUNDO estas sukcesa, la kodo moviĝas al la stadio de PIG (kobajo). Ĉi tio estas Cloudflare PoP, kie malgranda kvanto da senpaga klienta trafiko fluas tra nova kodo.
Se ĉio estas bona, la kodo iras en Kanarion. Ni havas tri Kanariajn PoP-ojn en malsamaj partoj de la mondo. En ili, la trafiko de pagitaj kaj senpagaj klientoj pasas tra la nova kodo, kaj ĉi tiu estas la lasta kontrolo pri eraroj.
Programaro-Eldonprocezo ĉe Cloudflare
Se la kodo estas en ordo en Kanario, ni liberigas ĝin. Trairi ĉiujn stadiojn - HUNDO, PORKO, Kanario, la tuta mondo - daŭras plurajn horojn aŭ tagojn, depende de la kodŝanĝo. Pro la diverseco de la reto kaj klientoj de Cloudflare, ni ĝisfunde testas kodon antaŭ ol liberigi ĝin tutmonde al ĉiuj klientoj. Sed WAF ne specife sekvas ĉi tiun procezon ĉar minacoj devas esti responditaj rapide.
WAF-minacoj
Dum la lastaj jaroj, estis signifa pliiĝo en minacoj en oftaj aplikoj. Ĉi tio estas pro la pli granda havebleco de programaraj testaj iloj. Ekzemple, ni lastatempe skribis pri ).
fonto:
Tre ofte, pruvo de koncepto estas kreita kaj tuj eldonita sur Github por ke la teamoj konservantaj la aplikaĵon povas rapide testi ĝin kaj certigi, ke ĝi estas taŭge sekurigita. Tial Cloudflare bezonas la kapablon respondi al novaj atakoj kiel eble plej rapide por ke klientoj havu la ŝancon ripari sian programaron.
Bonega ekzemplo de la rapida respondo de Cloudflare estas la deplojo de SharePoint-vunerebleco-protektoj en majo (). Preskaŭ tuj post kiam la anoncoj estis faritaj, ni rimarkis grandegan nombron da provoj ekspluati la vundeblecon en la SharePoint-instalaĵoj de niaj klientoj. Niaj infanoj konstante kontrolas novajn minacojn kaj verkas regulojn por protekti niajn klientojn.
La regulo, kiu kaŭzis la problemon ĵaŭdon, devis protekti kontraŭ transreta skribo (XSS). Tiaj atakoj ankaŭ fariĝis multe pli oftaj en la lastaj jaroj.
fonto:
La norma proceduro por ŝanĝi administritan regulon por WAF devas fari kontinuan integrigan (CI) testadon antaŭ tutmonda deplojo. Lastan ĵaŭdon ni faris ĉi tion kaj lanĉis la regulojn. Je 13:31 p.m., inĝeniero prezentis aprobitan tirpeton kun ŝanĝo.
Je 13:37 TeamCity kolektis la regulojn, prizorgis testojn kaj donis la permeson. La WAF-testserio testas la kernfunkciecon de la WAF kaj konsistas el granda nombro da unutestoj por individuaj funkcioj. Post unutestoj, ni testis la regulojn por la WAF uzante grandegan nombron da HTTP-petoj. HTTP-petoj kontrolas, kiuj petoj estu blokitaj de la WAF (por kapti la atakon) kaj kiuj povas esti permesitaj (por ne bloki ĉion kaj eviti falsajn pozitivojn). Sed ni ne testis pri troa uzado de CPU, kaj ekzameni la protokolojn de antaŭaj WAF-konstruaĵoj montras, ke la regultest-ekzekuta tempo ne pliiĝis, kaj estis malfacile suspekti, ke ne estos sufiĉe da rimedoj.
La testoj pasis kaj TeamCity komencis aŭtomate deploji la ŝanĝon je 13:42 p.m.
Quicksilver
WAF-reguloj temigas tujan minacan solvadon, do ni disvastigas ilin uzante la distribuitan ŝlosilvaloran vendejon de Quicksilver, kiu disvastigas ŝanĝojn tutmonde en sekundoj. Ĉiuj niaj klientoj uzas ĉi tiun teknologion kiam ili ŝanĝas la agordon en la panelo aŭ per la API, kaj estas danke al ĝi, ke ni respondas al ŝanĝoj kun fulmorapido.
Ni ne multe parolis pri Quicksilver. Antaŭe ni uzis kiel tutmonde distribuita ŝlosilvalora vendejo, sed estis funkciaj problemoj kun ĝi, kaj ni verkis nian propran vendejon, reproduktitan en pli ol 180 urboj. Ni nun uzas Quicksilver por puŝi agordajn ŝanĝojn al klientoj, ĝisdatigi WAF-regulojn kaj distribui JavaScript-kodon skribitan de klientoj al Cloudflare Workers.
Necesas nur kelkajn sekundojn de klakado de butono sur panelo aŭ vokado de API ĝis fari agordan ŝanĝon tutmonde. Klientoj amis ĉi tiun rapidecon de aranĝo. Kaj Laboristoj donas al ili preskaŭ tujan tutmondan programaron deplojon. Averaĝe, Quicksilver propagas ĉirkaŭ 350 ŝanĝojn je sekundo.
Kaj Quicksilver estas tre rapida. Averaĝe ni atingis la 99-an percentilon de 2,29 sekundoj por disvastigi ŝanĝojn al ĉiu komputilo tutmonde. Rapido estas kutime bona afero. Post ĉio, kiam vi ebligas funkcion aŭ malplenigas la kaŝmemoron, ĝi okazas preskaŭ tuj kaj ĉie. Sendi kodon per Cloudflare Workers okazas samrapide. Cloudflare promesas al siaj klientoj rapidajn ĝisdatigojn en la ĝusta tempo.
Sed en ĉi tiu kazo, rapideco ludis kruelan ŝercon kontraŭ ni, kaj la reguloj ŝanĝiĝis ĉie en demando de sekundoj. Vi eble rimarkis, ke la WAF-kodo uzas Lua. Cloudflare uzas Lua vaste en produktado kaj detaloj мы . Lua WAF uzas interne kaj aplikas retrovojon por kongruo. Ĝi ne havas mekanismojn por protekti kontraŭ esprimoj, kiuj foriĝas de kontrolo. Malsupre mi parolos pli pri tio kaj kion ni faras pri ĝi.
Antaŭ ol la reguloj estis deplojitaj, ĉio iris glate: la tirpeto estis kreita kaj aprobita, la CI/KD-dukto kolektis kaj testis la kodon, la ŝanĝpeto estis prezentita laŭ la SOP kiu regas deplojon kaj rollback, kaj la deplojo estis kompletigita.
Cloudflare WAF Deploja Procezo
Io misfunkciis
Kiel mi diris, ni deplojas dekduojn da novaj WAF-reguloj ĉiusemajne, kaj ni havas multajn sistemojn por protekti kontraŭ la negativaj sekvoj de tia deplojo. Kaj kiam io misfunkcias, ĝi kutime estas kombinaĵo de pluraj cirkonstancoj samtempe. Se vi trovas nur unu kialon, ĉi tio, kompreneble, estas trankviliga, sed ĝi ne ĉiam estas vera. Ĉi tiuj estas la kialoj, kiuj kune kondukis al la fiasko de nia HTTP/HTTPS-servo.
- Inĝeniero skribis regulan esprimon, kiu povus rezultigi troan .
- Trajto kiu povus esti malhelpinta la regulan esprimon malŝpari tro multe da CPU estis erare forigita en refactoring de la WAF plurajn semajnojn pli frue - la refactoring estis necesa por igi la WAF konsumi malpli resursojn.
- La regula esprimo motoro havis neniujn kompleksecgarantiojn.
- La testaro ne povis detekti troan CPU-konsumon.
- La SOP permesas ne-urĝajn regulŝanĝojn esti lanĉitaj tutmonde sen plurpaŝa procezo.
- La regresplano postulis ruli plenan WAF-konstruon dufoje, kio daŭris longan tempon.
- La unua atentigo pri tutmondaj trafikproblemoj estis ekigita tro malfrue.
- Ni prenis tempon por ĝisdatigi la statuspaĝon.
- Ni havis problemojn alirantaj sistemojn pro misfunkciado, kaj la pretervojo ne estis bone establita.
- SRE-inĝenieroj perdis aliron al kelkaj sistemoj ĉar iliaj akreditaĵoj eksvalidiĝis pro sekureckialoj.
- Niaj klientoj ne havis aliron al la panelo aŭ API de Cloudflare ĉar ili trairas regionon de Cloudflare.
Kio ŝanĝiĝis ekde lasta ĵaŭdo
Unue, ni tute ĉesigis ĉiun laboron pri eldonoj por WAF kaj faras la jenon:
- Ni reenkondukas la protekton de CPU-trouzo, kiun ni forigis. (Preta)
- Mane kontrolante ĉiujn 3868 regulojn en la administritaj reguloj por ke la WAF trovu kaj korektu aliajn eblajn kazojn de troa malantaŭo. (Konfirmo finita)
- Ni inkluzivas rendimentan profiladon por ĉiuj reguloj en la testaro. (Atendita: la 19-an de julio)
- Ŝanĝi al regula esprimo motoro aŭ - ambaŭ provizas rultempajn garantiojn. (Atendita: la 31-an de julio)
- Ni reverkas la SOP por disfaldi regulojn en etapoj, kiel alia programaro en Cloudflare, sed samtempe havas la kapablon urĝi tutmondan deplojon se atakoj jam komenciĝis.
- Ni disvolvas la kapablon urĝe forigi la panelon kaj API de Cloudflare de la regiono Cloudflare.
- Aŭtomatigi paĝajn ĝisdatigojn .
Longtempe ni malproksimiĝas de la Lua WAF, kiun mi skribis antaŭ kelkaj jaroj. Movante WAF al . Tiel la WAF estos pli rapida kaj ricevos plian nivelon de protekto.
konkludo
Ĉi tiu malsukceso kaŭzis problemojn por ni kaj niaj klientoj. Ni agis rapide por korekti la situacion kaj nun laboras pri la difektoj en la procezoj, kiuj kaŭzis la kraŝon, kaj ankaŭ fosas eĉ pli profunde por gardi eblajn problemojn kun regulaj esprimoj en la estonteco dum migrado al nova teknologio.
Ni tre embarasas pri ĉi tiu malfunkcio kaj pardonpetas niajn klientojn. Ni esperas, ke ĉi tiuj ŝanĝoj certigos, ke io tia ne okazos denove.
Apliko. Retrovoja regulaj esprimoj
Por kompreni kiel la esprimo:
(?:(?:"|'|]|}||d
(?:nan|infinity|true|false|null|undefined|symbol|math)|`|-
|+)+[)]*;?((?:s|-|~|!|{}||||+)*.*(?:.*=.*)))manĝis ĉiujn CPU-rimedojn, vi devas scii iom pri kiel funkcias la norma regula esprimo-motoro. La problemo ĉi tie estas la ŝablono .*(?:.*=.*). (?: kaj responda ) estas nekapta grupo (tio estas, la esprimo en krampoj estas grupigita kiel ununura esprimo).
En la kunteksto de troa CPU-konsumo, ĉi tiu ŝablono povas esti priskribita kiel .*.*=.*. En ĉi tiu formo, la ŝablono aspektas nenecese kompleksa. Sed pli grave, en la reala mondo, esprimoj (kiel kompleksaj esprimoj en WAF-reguloj) kiuj petas al la motoro kongrui kun fragmento sekvita de alia fragmento povas konduki al katastrofa malantaŭo. Kaj tial.
En regula esprimo . signifas, ke vi devas kongrui kun unu signo, .* - kongrui nul aŭ pli da signoj "avide", tio estas, kaptante maksimumon da signoj, tiel ke .*.*=.* signifas kongrui kun nul aŭ pli da signoj, tiam kongrui kun nul aŭ pli da signoj, trovi la laŭvortan = karakteron, kongrui kun nul aŭ pli da signoj.
Ni prenu la testlinion x=x. Ĝi respondas al la esprimo .*.*=.*. .*.* antaŭ ol la egalsigno kongruas kun la unua x (unu el la grupoj .* соответствует x, kaj la duaj - nulaj signoj). .* post = kongruas lasta x.
Ĉi tiu komparo postulas 23 paŝojn. Unua grupo .* в .*.*=.* agas avide kaj kongruas kun la tuta ŝnuro x=x. La motoro moviĝas al la sekva grupo .*. Ni ne havas pliajn signojn por egali, do la dua grupo .* kongruas kun nul signoj (tio estas permesita). Tiam la motoro moviĝas al la signo =. Ne plu ekzistas simboloj (unua grupo .* uzis la tutan esprimon x=x), neniu komparo okazas.
Kaj tiam la regula esprimo motoro revenas al la komenco. Li pluiras al la unua grupo .* kaj komparas ĝin с x= (anstataŭe x=x), kaj tiam alprenas la duan grupon .*. Dua grupo .* estas komparata kun la dua x, kaj al ni denove ne restas signoj. Kaj kiam la motoro denove atingas = в .*.*=.*, nenio funkcias. Kaj li denove retroiras.
Ĉi-foje la grupo .* ankoraŭ kongruas x=, sed la dua grupo .* ne plu x, kaj nul signoj. La motoro provas trovi laŭvortan karakteron = en la ŝablono .*.*=.*, sed ne eliras (finfine, la unua grupo jam okupis ĝin .*). Kaj li denove retroiras.
Ĉi-foje la unua grupo .* prenas nur la unuan x. Sed la dua grupo .* "avide" kaptas =x. Ĉu vi jam divenis, kio okazos? La motoro provas egali la laŭvortan =, malsukcesas kaj faras alian regreson.
Unua grupo .* ankoraŭ kongruas kun la unua x... La dua .* nur prenas =. Kompreneble, la motoro ne povas egali la laŭvortan =, ĉar la dua grupo jam faris tion .*. Kaj denove malantaŭen. Kaj ni provas kongrui kun ĉeno de tri signoj!
Kiel rezulto, la unua grupo .* kongruas nur kun la unua x, dua .* - kun nul signoj, kaj la motoro finfine kongruas kun la laŭvorta = en esprimo с = en linio. Sekva estas la lasta grupo .* estas komparata kun la lasta x.
23 paŝoj nur por x=x. Spektu mallongan filmeton pri uzado de Perl , kiu montras kiel okazas paŝoj kaj retrovojoj.
Ĉi tio jam estas multe da laboro, sed kio se anstataŭe x=x ni havos x=xx? Tio estas 33 paŝoj. Kaj se x=xxx? 45. La rilato ne estas lineara. La grafikaĵo montras komparon de x=x por x=xxxxxxxxxxxxxxxxxxxx (20 x после =). Se ni havas 20 x post =, la motoro kompletigas la kongruon en 555 paŝoj! (Cetere, se ni perdis x= kaj la ŝnuro simple konsistas el 20 x, la motoro prenos 4067 paŝojn por kompreni, ke ne ekzistas matĉoj).
Ĉi tiu video montras ĉiujn retrovojojn por komparo x=xxxxxxxxxxxxxxxxxxxx:
La problemo estas ke kiam la kordgrandeco pliiĝas, la kongrua tempo kreskas super-linie. Sed aferoj povas plimalboniĝi, se la regula esprimo estas iomete modifita. Ni diru, ke ni havis .*.*=.*; (tio estas, estis laŭvorta punktokomo ĉe la fino de la ŝablono). Ekzemple, kongrui kun esprimo kiel foo=bar;.
Kaj ĉi tie retrovoja estus vera katastrofo. Por komparo x=x ĝi prenos 90 paŝojn, ne 23. Kaj tiu nombro rapide kreskas. Kompari x= kaj 20 x, 5353 paŝoj estas bezonataj. Jen la diagramo. Rigardu la aksajn valorojn Y kompare kun la antaŭa diagramo.
Se vi interesiĝas, kontrolu ĉiujn 5353 malsukcesajn kongruajn paŝojn x=xxxxxxxxxxxxxxxxxxxx и .*.*=.*;
Uzante maldiligentan prefere ol avidan kongruadon, la amplekso de retrotravado povas esti kontrolita. Se ni ŝanĝas la originan esprimon al .*?.*?=.*?, por komparo x=x ĝi prenos 11 paŝojn (ne 23). Kiel por x=xxxxxxxxxxxxxxxxxxxx... Ĉio ĉar ? после .* rakontas al la motoro kongrui kun minimuma nombro da karakteroj antaŭ pluiri.
Sed maldiligentaj mapadoj ne tute solvas la problemon de retrovoja. Se ni anstataŭigas la katastrofan ekzemplon .*.*=.*; sur .*?.*?=.*?;, la ekzekuttempo restos la sama. x=x ankoraŭ postulas 555 paŝojn, kaj x= kaj 20 x - NENIU.
La nura afero farebla (krom tute reverki la ŝablonon por pli granda specifeco) estas forlasi la regulan esprimon motoron kun ĝia malantaŭa mekanismo. Jen kion ni faros dum la venontaj semajnoj.
La solvo de ĉi tiu problemo estas konata ekde 1968, kiam Kent Thompson skribis artikolon ("Programado-Metodoj: Regula Esprimo Serĉa Algoritmo"). La artikolo priskribas mekanismon, kiu ebligas al vi konverti regulan esprimon en nedeterminismajn finhavajn ŝtatmaŝinojn, kaj post statoŝanĝoj en nedeterminismaj finhavaj ŝtatmaŝinoj, uzi algoritmon kies ekzekuttempo dependas linie de la kongrua ĉeno.
Programaj Metodoj
Regula Esprima Serĉa Algoritmo
Ken Thompson
Bell Telephone Laboratories, Inc., Murray Hill, Nov-ĴerzejoĜi priskribas metodon por serĉi specifan ĉenon de signoj en teksto kaj diskutas la efektivigon de ĉi tiu metodo en kompililo. La kompililo prenas la regulan esprimon kiel fontkodon kaj produktas la IBM 7094 programon kiel objektokodon. La objektoprogramo prenas enigaĵon en la formo de serĉteksto kaj elsendas signalon ĉiufoje kiam tekstĉeno estas kongrua kontraŭ antaŭfiksita regula esprimo. La artikolo provizas ekzemplojn, problemojn kaj solvojn.
Algoritmo
Antaŭaj serĉalgoritmoj rezultigis retroveturon se parte sukcesa serĉo ne produktis rezulton.En kompilreĝimo, la algoritmo ne funkcias kun simboloj. Ĝi pasas instrukciojn al kompilita kodo. Ekzekuto estas tre rapida - post pasado de datumoj al la supro de la nuna listo, ĝi aŭtomate serĉas ĉiujn eblajn sinsekvajn signojn en la regula esprimo.
La kompilo kaj serĉalgoritmo estas inkluzivita en la tempodivida tekstredaktilo kiel kunteksta serĉo. Kompreneble, ĉi tio estas malproksime de la sola apliko de tia serĉprocedo. Ekzemple, varianto de ĉi tiu algoritmo estas uzata kiel simbolserĉo en tabelo en asemblero.
Oni supozas, ke la leganto konas regulajn esprimojn kaj la IBM 7094 komputila programlingvo.Kompililo
La kompililo konsistas el tri etapoj kurantaj paralele. La unua etapo estas sintaksa filtrado, kiu permesas trapasi nur sintakse ĝustajn regulajn esprimojn. Ĉi tiu paŝo ankaŭ enmetas la operatoron "·" por kongrui kun regulaj esprimoj. En la dua paŝo, la regula esprimo estas konvertita al postfiksa formo. En la tria etapo, objektokodo estas kreita. La unuaj 2 etapoj estas evidentaj, kaj ni ne pritraktos ilin.
La artikolo de Thompson ne parolas pri nedeterminismaj finhavaj ŝtatmaŝinoj, sed ĝi bone klarigas la linearan tempoalgoritmon kaj prezentas ALGOL-60-programon kiu generas asemblalingvan kodon por la IBM 7094. La efektivigo estas malfacila, sed la ideo estas tre simpla.
aktuala serĉvojo. Ĝi estas reprezentita per ⊕ ikono kun unu enigo kaj du eliroj.
Figuro 1 montras la funkciojn de la tria kompilpaŝo dum transformado de regula esprimo ekzemplo. La unuaj tri signoj en la ekzemplo estas a, b, c, kaj ĉiu kreas stakan eniron S[i] kaj NNODE-kampon.NNODE al ekzistanta kodo por generi la rezultan regulan esprimon en ununura staka eniro (vidu Figuro 5)
Jen kiel aspektus regula esprimo .*.*=.*, se vi imagas ĝin kiel en la bildoj de la artikolo de Thompson.
En Fig. 0 estas kvin statoj ekde 0, kaj 3 cikloj, kiuj komenciĝas de statoj 1, 2 kaj 3. Ĉi tiuj tri cikloj respondas al tri. .* en regula esprimo. 3 ovaloj kun punktoj respondas al unu simbolo. Ovala kun signo = kongruas kun laŭvorta signo =. Ŝtato 4 estas fina. Se ni atingas ĝin, tiam la regula esprimo estas kongrua.
Por vidi kiel tia statodiagramo povas esti uzata por regula esprimo kongruo .*.*=.*, ni rigardos kordkongruon x=x. La programo komenciĝas de stato 0, kiel montrite en Fig. 1.
Por ke ĉi tiu algoritmo funkciu, la ŝtatmaŝino devas esti en pluraj ŝtatoj samtempe. Nedeterminisma finhava maŝino faros ĉiujn eblajn transirojn samtempe.
Antaŭ ol ĝi havas tempon por legi la enigajn datumojn, ĝi iras en ambaŭ unuajn statojn (1 kaj 2), kiel montrite en Fig. 2.
En Fig. 2 montras kio okazas kiam li rigardas la unuan x в x=x. x povas mapi al la supra punkto, irante de stato 1 kaj reen al stato 1. Aŭ x povas mapi al la punkto malsupre, irante de stato 2 kaj reen al stato 2.
Post kongruo de la unua x в x=x ni ankoraŭ estas en statoj 1 kaj 2. Ni ne povas atingi staton 3 aŭ 4 ĉar ni bezonas laŭvortan signon =.
La algoritmo tiam konsideras = в x=x. Kiel x antaŭ ĝi, ĝi povas esti egalita al aŭ el la supraj du bukloj de ŝtato 1 ĝis ŝtato 1 aŭ de ŝtato 2 ĝis ŝtato 2, sed la algoritmo povas egali la laŭvortan = kaj moviĝu de stato 2 al stato 3 (kaj tuj 4). Ĉi tio estas montrita en Fig. 3.
La algoritmo tiam pluiras al la lasta x в x=x. De statoj 1 kaj 2 la samaj transiroj eblas reen al statoj 1 kaj 2. De stato 3 x povas egali la punkton dekstre kaj reiri al stato 3.
En ĉi tiu etapo, ĉiu karaktero x=x konsiderite, kaj ĉar ni atingis staton 4, la regula esprimo kongruas kun tiu ĉeno. Ĉiu signo estas prilaborita unufoje, do ĉi tiu algoritmo estas lineara en la longo de la eniga ĉeno. Kaj neniu retroiro.
Evidente, post atingi staton 4 (kiam la algoritmo kongruis x=) la tuta regula esprimo estas kongrua, kaj la algoritmo povas finiĝi sen konsideri ĝin entute x.
Ĉi tiu algoritmo dependas linie de la grandeco de la eniga ĉeno.
fonto: www.habr.com