Halos 9 na taon na ang nakalipas Cloudflare ay isang maliit na kumpanya, at hindi ako nagtrabaho para dito, ako ay isang customer lamang. Isang buwan pagkatapos ilunsad ang Cloudflare, nakatanggap ako ng notification na ang aking website Mukhang hindi gumagana ang DNS. Ang Cloudflare ay gumawa ng pagbabago sa , at nagkaroon ng sirang DNS.
Agad akong sumulat kay Matthew Prince na may pamagat na "Nasaan ang aking DNS?" at nagpadala siya ng mahabang tugon na puno ng mga teknikal na detalye (), na sinagot ko:
Mula kay: John Graham-Cumming
Petsa: Oktubre 7, 2010, 9:14
Subject: Re: Nasaan ang aking DNS?
Para kay: Matthew PrinceCool na ulat, salamat. Tatawagan ko talaga kung may problema. Malamang na sulit na magsulat ng post tungkol dito kapag nakolekta mo na ang lahat ng teknikal na impormasyon. Sa tingin ko, magugustuhan ng mga tao ang isang bukas at tapat na kuwento. Lalo na kung nag-attach ka ng mga graph dito upang ipakita kung paano lumaki ang trapiko mula noong ilunsad.
Mayroon akong mahusay na pagsubaybay sa aking site, at nakakatanggap ako ng SMS tungkol sa bawat pagkabigo. Ipinapakita ng pagsubaybay na naganap ang pagkabigo mula 13:03:07 hanggang 14:04:12. Ang mga pagsusulit ay isinasagawa tuwing limang minuto.
Sigurado akong malalaman mo ito. Sigurado ka bang hindi mo kailangan ng sarili mong tao sa Europe? π
At sumagot siya:
Mula kay: Matthew Prince
Petsa: Oktubre 7, 2010, 9:57
Subject: Re: Nasaan ang aking DNS?
Para kay: John Graham-CummingSalamat. Sumagot kami sa lahat ng sumulat. Papunta na ako ngayon sa opisina at may isusulat kami sa blog o i-pin ang isang opisyal na post sa aming bulletin board. Sumasang-ayon ako, ang katapatan ay lahat.
Ngayon ang Cloudflare ay talagang malaking kumpanya, nagtatrabaho ako para dito, at ngayon kailangan kong isulat nang hayagan ang tungkol sa aming pagkakamali, ang mga kahihinatnan nito at ang aming mga aksyon.
Mga kaganapan noong Hulyo 2
Noong Hulyo 2, inilunsad namin ang isang bagong panuntunan sa Mga Pinamamahalaang Panuntunan para sa mga WAF dahil sa kung saan sa bawat processor core na nagpoproseso ng trapiko ng HTTP/HTTPS sa Cloudflare network sa buong mundo. Patuloy naming pinapahusay ang mga pinamamahalaang panuntunan para sa mga WAF bilang tugon sa mga bagong kahinaan at banta. Noong Mayo, halimbawa, nagmadali kami upang maprotektahan laban sa isang malubhang kahinaan sa SharePoint. Ang buong punto ng aming WAF ay ang kakayahang mabilis at buong mundo na mag-deploy ng mga panuntunan.
Sa kasamaang palad, ang pag-update noong nakaraang Huwebes ay naglalaman ng isang regular na expression na nag-aksaya ng masyadong maraming mapagkukunan ng HTTP/HTTPS CPU sa pag-backtrack. Ang aming pangunahing proxy, CDN, at WAF function ay nagdusa bilang isang resulta. Ipinapakita ng graph na ang mga mapagkukunan ng processor para sa paghahatid ng trapiko ng HTTP/HTTPS ay umaabot sa halos 100% sa mga server sa aming network.
Paggamit ng CPU sa isang punto ng presensya habang may insidente
Bilang resulta, ang aming mga kliyente (at mga kliyente ng aming mga kliyente) ay napunta sa isang 502 na pahina ng error sa mga Cloudflare na domain. Ang mga error na 502 ay nabuo ng mga front-end na web server ng Cloudflare na mayroon pa ring mga libreng core ngunit hindi magawang makipag-ugnayan sa mga prosesong nangangasiwa sa trapiko ng HTTP/HTTPS.
Alam namin kung gaano karaming abala ang naidulot nito sa aming mga customer. Sobrang nahihiya kami. At ang kabiguan na ito ay humadlang sa amin sa epektibong pagharap sa insidente.
Kung isa ka sa mga customer na ito, malamang na natakot ka, nagagalit at naiinis. At saka, wala pa kaming a . Ang mataas na pagkonsumo ng CPU ay dahil sa isang panuntunan ng WAF na may mahinang salita na regular na expression na nagresulta sa labis na pag-backtrack. Narito ang ekspresyon ng pagkakasala: (?:(?:"|'|]|}||d|(?:nan|infinity|true|false|null|undefined|symbol|math)|`|-|+)+[)]*;?((?:s|-|~|!|{}||||+)*.*(?:.*=.*)))
Bagama't ito ay kawili-wili sa sarili nitong karapatan (at pag-uusapan ko ito nang mas detalyado sa ibaba), ang serbisyo ng Cloudflare ay nabawasan sa loob ng 27 minuto hindi lamang dahil sa isang masamang regular na pagpapahayag. Nagtagal kami upang ilarawan ang pagkakasunud-sunod ng mga kaganapan na humantong sa kabiguan, kaya mabagal kaming tumugon. Sa dulo ng post, ilalarawan ko ang backtracking sa isang regular na expression at sasabihin sa iyo kung ano ang gagawin dito.
Anong nangyari
Magsimula tayo sa pagkakasunud-sunod. Lahat ng oras dito ay nasa UTC.
Noong 13:42 p.m., gumawa ng maliit na pagbabago sa mga panuntunan sa pagtukoy ang isang engineer sa firewall team gamit ang isang awtomatikong proseso. Alinsunod dito, nilikha ang isang ticket ng kahilingan sa pagbabago. Pinamamahalaan namin ang mga naturang tiket sa pamamagitan ng Jira (screenshot sa ibaba).
Pagkatapos ng 3 minuto, lumabas ang unang pahina ng PagerDuty, na nag-uulat ng problema sa WAF. Isa itong synthetic na pagsubok na sumusubok sa functionality ng mga WAF (mayroon kaming daan-daang mga ito) sa labas ng Cloudflare upang subaybayan ang normal na operasyon. Kaagad itong sinundan ng mga pahina ng mga alerto tungkol sa iba pang Cloudflare na end-to-end na mga pagsubok sa serbisyo na nabigo, mga isyu sa pandaigdigang trapiko, malawak na 502 na mga error, at isang tonelada ng mga ulat mula sa aming Points of Presence (PoP) sa mga lungsod sa buong mundo na nagsasaad ng kakulangan ng mga mapagkukunan ng CPU.
Nakatanggap ako ng ilan sa mga alertong ito, lumabas sa isang pulong, at papunta na ako sa mesa nang sabihin ng pinuno ng aming departamento ng pagpapaunlad ng mga solusyon na nawala sa amin ang 80% ng aming trapiko. Tumakbo ako sa aming mga inhinyero sa SRE, na gumagawa na sa problema. Sa una ay naisip namin na ito ay isang uri ng hindi kilalang pag-atake.
Ang mga inhinyero ng Cloudflare SRE ay nakakalat sa buong mundo at sinusubaybayan ang sitwasyon sa buong orasan. Karaniwan, inaabisuhan ka ng mga alertong ito tungkol sa mga partikular na lokal na isyu na limitado ang saklaw, sinusubaybayan sa mga panloob na dashboard, at nareresolba nang maraming beses bawat araw. Ngunit ang mga page at notification na ito ay nagpahiwatig ng isang bagay na talagang seryoso, at agad na idineklara ng mga inhinyero ng SRE ang antas ng kalubhaan na P0 at nakipag-ugnayan sa mga management at system engineer.
Ang aming mga inhinyero sa London ay nakikinig sa isang lektura sa pangunahing bulwagan sa sandaling iyon. Kinailangang maputol ang lecture, lahat ay nagtipon sa isang malaking conference room, at mas maraming mga espesyalista ang tinawag. Ito ay hindi isang karaniwang problema na maaaring harapin ng mga SRE sa kanilang sarili. Ito ay kagyat na isangkot ang mga tamang espesyalista.
Sa 14:00 namin natukoy na ang problema ay sa WAF at walang pag-atake. Kinuha ng performance team ang data ng CPU at naging malinaw na ang WAF ang may kasalanan. Kinumpirma ng isa pang empleyado ang teoryang ito gamit ang strace. May ibang nakakita sa logs na may problema sa WAF. Noong 14:02 p.m., lumapit sa akin ang buong team noong iminungkahi na gumamit ng global kill, isang mekanismo na binuo sa Cloudflare na nagsasara ng isang bahagi sa buong mundo.
Kung paano namin ginawa ang global kill para sa WAF ay ibang kuwento. Ito ay hindi ganoon kasimple. Ginagamit namin ang aming sariling mga produkto, at mula noong aming serbisyo hindi gumana, hindi kami makapag-authenticate at makapag-log in sa internal control panel (nang naayos na ang lahat, nalaman namin na nawalan ng access ang ilang miyembro ng team dahil sa isang security feature na hindi pinapagana ang mga kredensyal kung hindi ginagamit ang internal control panel para sa isang matagal na panahon).
At hindi kami makapunta sa aming mga panloob na serbisyo, tulad ng Jira o ang build system. Kailangan namin ng isang workaround na mekanismo, na hindi namin madalas gamitin (ito ay kailangan ding ayusin). Sa wakas, nagawang i-disable ng isang engineer ang WAF noong 14:07, at noong 14:09, bumalik sa normal ang trapiko at mga antas ng CPU sa lahat ng dako. Ang natitirang mga mekanismo ng proteksyon ng Cloudflare ay gumana bilang normal.
Pagkatapos ay itinakda namin ang tungkol sa pagpapanumbalik ng WAF. Ang sitwasyon ay hindi karaniwan, kaya nagsagawa kami ng mga negatibong pagsusuri (tinatanong ang aming sarili kung ang pagbabago ba talaga ang problema) at mga positibong pagsusuri (siguraduhing gumana ang rollback) sa isang lungsod gamit ang hiwalay na trapiko, paglilipat ng mga nagbabayad na customer mula doon.
Sa 14:52 kami ay kumbinsido na naiintindihan namin ang dahilan at gumawa ng isang pagwawasto, at pinagana muli ang WAF.
Paano gumagana ang Cloudflare
Ang Cloudflare ay may pangkat ng mga inhinyero na nakatuon sa pamamahala ng mga panuntunan para sa mga WAF. Nagsusumikap silang pahusayin ang mga rate ng pagtuklas, bawasan ang mga maling positibo, at mabilis na tumugon sa mga bagong banta habang lumalabas ang mga ito. Sa nakalipas na 60 araw, mayroong 476 na kahilingan sa pagbabago na naproseso para sa mga pinamamahalaang panuntunan para sa WAF (isang average ng isa bawat 3 oras).
Ang partikular na pagbabagong ito ay kailangang i-deploy sa simulation mode, kung saan ang totoong trapiko ng kliyente ay dumadaan sa panuntunan, ngunit walang naharang. Ginagamit namin ang mode na ito upang subukan ang pagiging epektibo ng mga panuntunan at sukatin ang maling positibo at maling negatibong mga rate. Ngunit kahit na sa simulation mode, ang mga panuntunan ay dapat na aktwal na maisakatuparan, at sa kasong ito ang panuntunan ay naglalaman ng isang regular na expression na kumonsumo ng masyadong maraming mapagkukunan ng processor.
Gaya ng nakikita mo mula sa kahilingan sa pagbabago sa itaas, mayroon kaming plano sa pag-deploy, plano ng rollback, at isang link sa isang panloob na standard operating procedure (SOP) para sa ganitong uri ng deployment. Ang SOP para sa pagbabago ng isang panuntunan ay nagbibigay-daan na mai-publish ito sa buong mundo. Sa totoo lang, sa Cloudflare, ang mga bagay ay ganap na naiiba, at ang SOP ay nagdidikta na una naming ipadala ang software para sa pagsubok at panloob na paggamit sa isang panloob na punto ng presensya (PoP) (na ginagamit ng aming mga empleyado), pagkatapos ay sa isang maliit na bilang ng mga kliyente sa isang nakahiwalay na lokasyon, pagkatapos ay sa isang malaking bilang ng mga kliyente, at pagkatapos lamang sa buong mundo.
Ito ang hitsura nito. Ginagamit namin ang git sa loob sa pamamagitan ng BitBucket. Ang mga inhinyero na nagtatrabaho sa mga pagbabago ay nagsusumite ng code, na binuo sa TeamCity, at kapag pumasa ang build, itatalaga ang mga tagasuri. Kapag naaprubahan ang isang kahilingan sa paghila, ang code ay binuo at ang isang serye ng mga pagsubok ay tatakbo (muli).
Kung matagumpay na nakumpleto ang build at mga pagsubok, isang kahilingan sa pagbabago ang gagawin sa Jira at dapat aprubahan ng naaangkop na manager o lead ang pagbabago. Pagkatapos ng pag-apruba, nangyayari ang deployment sa tinatawag na βPoP menagerieβ: DOG, PIG at (aso, baboy at kanaryo).
Ang DOG PoP ay isang Cloudflare PoP (tulad ng bawat isa sa aming mga lungsod) na ginagamit lamang ng mga empleyado ng Cloudflare. Nagbibigay-daan sa iyo ang PoP para sa panloob na paggamit na mahuli ang mga problema bago magsimulang dumaloy ang trapiko ng customer sa solusyon. Kapaki-pakinabang na bagay.
Kung matagumpay ang pagsusulit ng DOG, lilipat ang code sa yugto ng PIG (guinea pig). Ito ang Cloudflare PoP, kung saan dumadaloy ang isang maliit na halaga ng libreng trapiko ng customer sa pamamagitan ng bagong code.
Kung maayos ang lahat, mapupunta ang code sa Canary. Mayroon kaming tatlong Canary PoP sa iba't ibang bahagi ng mundo. Sa kanila, ang trapiko ng mga bayad at libreng kliyente ay dumadaan sa bagong code, at ito ang huling pagsusuri para sa mga error.
Proseso ng Pagpapalabas ng Software sa Cloudflare
Kung ok ang code sa Canary, ilalabas namin ito. Ang pagdaan sa lahat ng mga yugto - DOG, PIG, Canary, ang buong mundo - ay tumatagal ng ilang oras o araw, depende sa pagbabago ng code. Dahil sa pagkakaiba-iba ng network at mga kliyente ng Cloudflare, masusing sinusuri namin ang code bago ito ilabas sa buong mundo sa lahat ng kliyente. Ngunit ang WAF ay hindi partikular na sumusunod sa prosesong ito dahil ang mga banta ay kailangang matugunan nang mabilis.
Mga banta ng WAF
Sa nakalipas na ilang taon, nagkaroon ng malaking pagtaas sa mga banta sa mga karaniwang aplikasyon. Ito ay dahil sa mas malawak na kakayahang magamit ng mga tool sa pagsubok ng software. Halimbawa, isinulat namin kamakailan ang tungkol sa ).
Pinagmulan:
Kadalasan, ang isang patunay ng konsepto ay nilikha at agad na nai-publish sa Github upang ang mga koponan na nagpapanatili ng application ay maaaring mabilis na subukan ito at matiyak na ito ay sapat na secure. Samakatuwid, kailangan ng Cloudflare ang kakayahang tumugon sa mga bagong pag-atake sa lalong madaling panahon upang magkaroon ng pagkakataon ang mga customer na ayusin ang kanilang software.
Ang isang magandang halimbawa ng mabilis na pagtugon ng Cloudflare ay ang pag-deploy ng mga proteksyon sa kahinaan ng SharePoint noong Mayo (). Halos kaagad pagkatapos gawin ang mga anunsyo, napansin namin ang isang malaking bilang ng mga pagtatangka na pagsamantalahan ang kahinaan sa mga pag-install ng SharePoint ng aming mga customer. Patuloy na sinusubaybayan ng aming mga lalaki ang mga bagong pagbabanta at pagsusulat ng mga panuntunan upang protektahan ang aming mga customer.
Ang panuntunang nagdulot ng problema noong Huwebes ay dapat na nagpoprotekta laban sa cross-site scripting (XSS). Ang ganitong mga pag-atake ay naging mas madalas din sa mga nakaraang taon.
Pinagmulan:
Ang karaniwang pamamaraan para sa pagbabago ng pinamamahalaang panuntunan para sa isang WAF ay ang pagsasagawa ng tuluy-tuloy na pagsasama-sama (CI) na pagsubok bago ang pandaigdigang pag-deploy. Noong nakaraang Huwebes ginawa namin ito at inilunsad ang mga patakaran. Noong 13:31 p.m., nagsumite ang isang engineer ng aprubadong pull request na may pagbabago.
Sa 13:37 kinolekta ng TeamCity ang mga panuntunan, nagpatakbo ng mga pagsusulit at nagbigay ng go-ahead. Sinusubukan ng WAF test suite ang pangunahing functionality ng WAF at binubuo ng malaking bilang ng mga unit test para sa mga indibidwal na function. Pagkatapos ng mga unit test, sinubukan namin ang mga panuntunan para sa WAF gamit ang malaking bilang ng mga kahilingan sa HTTP. Sinusuri ng mga kahilingan sa HTTP kung aling mga kahilingan ang dapat i-block ng WAF (upang ma-intercept ang pag-atake) at kung alin ang maaaring payagan (para hindi ma-block ang lahat at maiwasan ang mga maling positibo). Ngunit hindi namin sinubukan ang labis na paggamit ng CPU, at ang pagsusuri sa mga log ng nakaraang WAF build ay nagpapakita na ang oras ng pagpapatupad ng pagsubok sa panuntunan ay hindi tumaas, at mahirap maghinala na walang sapat na mapagkukunan.
Lumipas ang mga pagsubok at nagsimulang awtomatikong i-deploy ng TeamCity ang pagbabago noong 13:42 p.m.
Asoge
Nakatuon ang mga panuntunan ng WAF sa agarang pagreremedia ng banta, kaya idini-deploy namin ang mga ito gamit ang distributed key-value store ng Quicksilver, na nagpapalaganap ng mga pagbabago sa buong mundo sa ilang segundo. Ginagamit ng lahat ng aming kliyente ang teknolohiyang ito kapag binago nila ang configuration sa dashboard o sa pamamagitan ng API, at salamat dito na tumugon kami sa mga pagbabago nang may bilis ng kidlat.
Hindi pa namin masyadong napag-uusapan ang Quicksilver. Dati ginagamit namin bilang isang tindahan ng key-value na ipinamamahagi sa buong mundo, ngunit may mga problema sa pagpapatakbo dito, at nagsulat kami ng sarili naming tindahan, na ginagaya sa mahigit 180 lungsod. Ginagamit na namin ngayon ang Quicksilver para itulak ang mga pagbabago sa configuration sa mga kliyente, i-update ang mga panuntunan ng WAF, at ipamahagi ang JavaScript code na isinulat ng mga kliyente sa Cloudflare Workers.
Tumatagal lamang ng ilang segundo mula sa pag-click sa isang button sa isang dashboard o pagtawag sa isang API hanggang sa paggawa ng pagbabago sa configuration sa buong mundo. Nagustuhan ng mga customer ang bilis ng pag-setup na ito. At binibigyan sila ng mga Manggagawa ng halos agarang pandaigdigang pag-deploy ng software. Sa karaniwan, ang Quicksilver ay nagpapalaganap ng mga 350 pagbabago bawat segundo.
At ang Quicksilver ay napakabilis. Sa karaniwan, nakamit namin ang 99th percentile na 2,29 segundo upang magpalaganap ng mga pagbabago sa bawat computer sa buong mundo. Ang bilis ay karaniwang isang magandang bagay. Pagkatapos ng lahat, kapag pinagana mo ang isang function o na-clear ang cache, nangyayari ito halos kaagad at saanman. Ang pagpapadala ng code sa pamamagitan ng Cloudflare Workers ay nangyayari sa parehong bilis. Nangangako ang Cloudflare sa mga customer nito ng mabilis na pag-update sa tamang oras.
Ngunit sa kasong ito, ang bilis ay naglaro ng isang malupit na biro sa amin, at ang mga patakaran ay nagbago sa lahat ng dako sa loob ng ilang segundo. Maaaring napansin mo na ang WAF code ay gumagamit ng Lua. Malawakang ginagamit ng Cloudflare si Lua sa produksyon at mga detalye tayo . Ginagamit ng Lua WAF panloob at inilalapat ang backtracking para sa pagtutugma. Wala itong mga mekanismo upang maprotektahan laban sa mga expression na hindi makontrol. Sa ibaba ay pag-uusapan ko ang higit pa tungkol dito at kung ano ang ginagawa natin tungkol dito.
Bago i-deploy ang mga panuntunan, naging maayos ang lahat: ginawa at naaprubahan ang pull request, kinolekta at sinubukan ng pipeline ng CI/CD ang code, isinumite ang kahilingan sa pagbabago ayon sa SOP na namamahala sa deployment at rollback, at natapos ang deployment.
Proseso ng Cloudflare WAF Deployment
Nagkaproblema
Gaya ng sinabi ko, nagde-deploy kami ng dose-dosenang mga bagong panuntunan sa WAF bawat linggo, at mayroon kaming maraming system na nakalagay upang maprotektahan laban sa mga negatibong kahihinatnan ng naturang deployment. At kapag nagkamali, kadalasan ito ay kumbinasyon ng ilang mga pangyayari nang sabay-sabay. Kung makakita ka ng isang dahilan lamang, ito, siyempre, ay nakapagpapatibay, ngunit hindi ito palaging totoo. Ito ang mga dahilan na magkasamang humantong sa pagkabigo ng aming serbisyo ng HTTP/HTTPS.
- Ang isang engineer ay nagsulat ng isang regular na expression na maaaring magresulta sa labis .
- Ang isang tampok na maaaring pumigil sa regular na expression mula sa pag-aaksaya ng masyadong maraming CPU ay nagkamali na inalis sa isang refactoring ng WAF ilang linggo mas maaga-kinailangan ang refactoring upang gawing mas kaunting mapagkukunan ang kumonsumo ng WAF.
- Ang regular na expression engine ay walang mga garantiya sa pagiging kumplikado.
- Hindi matukoy ng test suite ang labis na pagkonsumo ng CPU.
- Ang SOP ay nagbibigay-daan sa hindi-kagyatang mga pagbabago sa panuntunan na mailunsad sa buong mundo nang walang maraming hakbang na proseso.
- Ang plano ng rollback ay nangangailangan ng pagpapatakbo ng buong WAF build nang dalawang beses, na tumagal ng mahabang panahon.
- Ang unang alerto tungkol sa mga pandaigdigang problema sa trapiko ay huli nang na-trigger.
- Nagtagal kami sa pag-update ng status page.
- Nagkaroon kami ng mga problema sa pag-access sa mga system dahil sa isang glitch, at ang pamamaraan ng bypass ay hindi maayos na naitatag.
- Nawalan ng access ang mga inhinyero ng SRE sa ilang system dahil nag-expire ang kanilang mga kredensyal dahil sa mga kadahilanang pangseguridad.
- Walang access ang aming mga customer sa Cloudflare dashboard o API dahil dumaan sila sa isang rehiyon ng Cloudflare.
Ano ang nagbago mula noong nakaraang Huwebes
Una, ganap naming itinigil ang lahat ng trabaho sa mga release para sa WAF at ginagawa ang sumusunod:
- Ibinabalik namin ang proteksyon sa sobrang paggamit ng CPU na inalis namin. (Handa na)
- Manu-manong sinusuri ang lahat ng 3868 na panuntunan sa mga pinamamahalaang panuntunan para mahanap at maitama ng WAF ang iba pang potensyal na kaso ng labis na pag-backtrack. (Nakumpleto ang pag-verify)
- Kasama namin ang pag-profile ng pagganap para sa lahat ng mga panuntunan sa set ng pagsubok. (Inaasahan: Hulyo 19)
- Lumipat sa isang regular na expression engine o - parehong nagbibigay ng mga garantiya ng runtime. (Inaasahan: Hulyo 31)
- Sinusulat namin muli ang SOP upang mag-deploy ng mga panuntunan sa mga yugto, tulad ng iba pang software sa Cloudflare, ngunit sa parehong oras ay may kakayahang mag-emergency na global deployment kung nagsimula na ang mga pag-atake.
- Binubuo namin ang kakayahang agarang alisin ang Cloudflare dashboard at API mula sa rehiyon ng Cloudflare.
- Pag-automate ng mga update sa page .
Matagal na tayong lumalayo sa Lua WAF na isinulat ko ilang taon na ang nakakaraan. Inilipat ang WAF sa . Sa ganitong paraan ang WAF ay magiging mas mabilis at makakatanggap ng karagdagang antas ng proteksyon.
Konklusyon
Ang pagkabigo na ito ay nagdulot ng problema para sa amin at sa aming mga customer. Mabilis kaming kumilos upang itama ang sitwasyon at ngayon ay nagsusumikap sa mga pagkukulang sa mga proseso na naging sanhi ng pag-crash, pati na rin ang paghuhukay ng mas malalim upang mabantayan laban sa mga potensyal na problema sa mga regular na expression sa hinaharap kapag lumipat sa bagong teknolohiya.
Lubos kaming nahihiya tungkol sa pagkawalang ito at humihingi kami ng paumanhin sa aming mga customer. Umaasa kaming masisiguro ng mga pagbabagong ito na hindi na mauulit ang ganitong bagay.
Aplikasyon. Pag-backtrack ng mga regular na expression
Upang maunawaan kung paano ang expression:
(?:(?:"|'|]|}||d
(?:nan|infinity|true|false|null|undefined|symbol|math)|`|-
|+)+[)]*;?((?:s|-|~|!|{}||||+)*.*(?:.*=.*)))Kinain ang lahat ng mga mapagkukunan ng CPU, kailangan mong malaman ang kaunti tungkol sa kung paano gumagana ang karaniwang regular na expression engine. Ang problema dito ay ang pattern .*(?:.*=.*). (?: at katumbas ) ay isang pangkat na hindi nakakakuha (iyon ay, ang expression sa panaklong ay pinagsama bilang isang expression).
Sa konteksto ng labis na pagkonsumo ng CPU, ang pattern na ito ay maaaring ilarawan bilang .*.*=.*. Sa form na ito, ang pattern ay mukhang hindi kinakailangang kumplikado. Ngunit higit sa lahat, sa totoong mundo, ang mga expression (tulad ng mga kumplikadong expression sa mga panuntunan ng WAF) na humihiling sa engine na tumugma sa isang fragment na sinusundan ng isa pang fragment ay maaaring humantong sa sakuna na backtracking. At dahil jan.
Sa regular na pagpapahayag . nangangahulugan na kailangan mong tumugma sa isang karakter, .* - tumugma sa zero o higit pang mga character "sa kasakiman", iyon ay, pagkuha ng isang maximum ng mga character, kaya na .*.*=.* ibig sabihin ay tumugma sa zero o higit pang mga character, pagkatapos ay tumugma sa zero o higit pang mga character, hanapin ang literal na = character, tumugma sa zero o higit pang mga character.
Kunin natin ang linya ng pagsubok x=x. Ito ay tumutugma sa expression .*.*=.*. .*.* bago tumugma ang equal sign sa una x (isa sa mga grupo .* tumutugma sa x, at ang pangalawa - zero character). .* pagkatapos = huling laban x.
Ang paghahambing na ito ay nangangailangan ng 23 hakbang. Unang pangkat .* Π² .*.*=.* kumikilos nang matakaw at tumutugma sa buong string x=x. Lumipat ang makina sa susunod na grupo .*. Wala na kaming mga character na maitutugma, kaya ang pangalawang grupo .* tumutugma sa zero character (ito ay pinapayagan). Pagkatapos ay lumipat ang makina sa sign =. Wala nang mga simbolo (unang pangkat .* ginamit ang buong ekspresyon x=x), walang paghahambing na nangyayari.
At pagkatapos ay bumalik ang regular na expression engine sa simula. Lumipat siya sa unang grupo .* at inihahambing ito Ρ x= (sa halip ng x=x), at pagkatapos ay sasabak sa pangalawang pangkat .*. Pangalawang pangkat .* ay inihambing sa pangalawa x, at wala na kaming natitirang character. At nang umabot muli ang makina = Π² .*.*=.*, walang gumagana. At muli siyang tumalikod.
Sa pagkakataong ito ang grupo .* tugma pa rin x=, ngunit ang pangalawang grupo .* wala na x, at mga zero na character. Sinusubukan ng makina na makahanap ng literal na karakter = sa pattern .*.*=.*, ngunit hindi lumalabas (pagkatapos ng lahat, sinakop na ito ng unang grupo .*). At muli siyang tumalikod.
Sa pagkakataong ito ang unang grupo .* tumatagal lamang ng unang x. Ngunit ang pangalawang grupo .* "sakim" na kinukuha =x. Nahulaan mo na ba kung ano ang mangyayari? Sinusubukan ng makina na tumugma sa literal =, nabigo at gumagawa ng isa pang backtracking.
Ang unang pangkat ng mga .* tugma pa rin sa una x... Ang ikalawa .* kumukuha lamang =. Siyempre, ang makina ay hindi maaaring tumugma sa literal =, dahil nagawa na ito ng pangalawang grupo .*. At muli backtracking. At sinusubukan naming tumugma sa isang string ng tatlong mga character!
Bilang resulta, ang unang pangkat .* tumutugma lamang sa una x, pangalawa .* - na may zero na mga character, at sa wakas ay tumutugma ang makina sa literal = sa pagpapahayag Ρ = nasa linya. Susunod ay ang huling grupo .* ay inihambing sa huli x.
23 hakbang lamang para sa x=x. Manood ng maikling video tungkol sa paggamit ng Perl , na nagpapakita kung paano nangyayari ang mga hakbang at backtracking.
Marami na itong trabaho, ngunit paano kung sa halip x=x magkakaroon kami ng x=xx? Iyan ay 33 hakbang. At kung x=xxx? 45. Ang relasyon ay hindi linear. Ang graph ay nagpapakita ng paghahambing mula sa x=x sa x=xxxxxxxxxxxxxxxxxxxx (20 x pagkatapos =). Kung mayroon tayong 20 x pagkatapos =, kinukumpleto ng makina ang pagtutugma sa 555 na hakbang! (At saka, kung natalo tayo x= at ang string ay binubuo lamang ng 20 x, gagawa ang makina ng 4067 hakbang upang maunawaan na walang mga tugma).
Ipinapakita ng video na ito ang lahat ng backtracking para sa paghahambing x=xxxxxxxxxxxxxxxxxxxx:
Ang problema ay habang lumalaki ang laki ng string, ang oras ng pagtutugma ay lumalaki nang super-linearly. Ngunit maaaring lumala pa ang mga bagay kung bahagyang binago ang regular na expression. Sabihin nating nagkaroon tayo .*.*=.*; (iyon ay, mayroong literal na semicolon sa dulo ng pattern). Halimbawa, upang tumugma sa isang expression tulad ng foo=bar;.
At dito ang pag-backtrack ay magiging isang tunay na sakuna. Para sa paghahambing x=x ito ay kukuha ng 90 hakbang, hindi 23. At ang bilang na iyon ay mabilis na lumalaki. Upang ihambing x= at 20 x, 5353 hakbang ang kailangan. Narito ang tsart. Tingnan ang mga halaga ng axis Y kumpara sa nakaraang tsart.
Kung interesado ka, tingnan ang lahat ng 5353 na nabigong mga hakbang sa pagtutugma x=xxxxxxxxxxxxxxxxxxxx ΠΈ .*.*=.*;
Sa pamamagitan ng paggamit ng tamad sa halip na sakim na pagtutugma, ang lawak ng backtracking ay makokontrol. Kung babaguhin natin ang orihinal na expression sa .*?.*?=.*?, para sa paghahambing x=x aabutin ito ng 11 hakbang (hindi 23). Tungkol naman sa x=xxxxxxxxxxxxxxxxxxxx. Lahat kasi ? pagkatapos .* nagsasabi sa makina na tumugma sa isang minimum na bilang ng mga character bago magpatuloy.
Ngunit ang mga tamad na pagmamapa ay hindi ganap na nalulutas ang problema sa backtracking. Kung papalitan natin ang sakuna na halimbawa .*.*=.*; sa .*?.*?=.*?;, ang oras ng pagpapatupad ay mananatiling pareho. x=x nangangailangan pa rin ng 555 hakbang, at x= at 20 x - 5353.
Ang tanging bagay na maaaring gawin (bukod sa ganap na muling pagsusulat ng pattern para sa higit na pagtitiyak) ay ang abandunahin ang regular na expression engine kasama ang mekanismo ng backtracking nito. Ito ang gagawin natin sa mga susunod na linggo.
Ang solusyon sa problemang ito ay kilala mula noong 1968, nang sumulat si Kent Thompson ng isang artikulo (βMga Paraan ng Programming: Regular Expression Search Algorithmβ). Inilalarawan ng artikulo ang isang mekanismo na nagbibigay-daan sa iyong i-convert ang isang regular na expression sa mga non-deterministic na finite state machine, at pagkatapos ng mga pagbabago ng estado sa non-deterministic na finite state machine, gumamit ng algorithm na ang oras ng pagpapatupad ay nakadepende nang linear sa katugmang string.
Mga Paraan ng Programming
Algorithm ng Paghahanap ng Regular na Expression
Ken Thompson
Bell Telephone Laboratories, Inc., Murray Hill, New JerseyInilalarawan nito ang isang paraan para sa paghahanap para sa isang tiyak na string ng mga character sa teksto at tinatalakay ang pagpapatupad ng paraang ito sa form ng compiler. Kinukuha ng compiler ang regular na expression bilang source code at gumagawa ng IBM 7094 program bilang object code. Ang object program ay kumukuha ng input sa anyo ng search text at naglalabas ng signal sa tuwing ang isang string ng text ay itinutugma laban sa isang naibigay na regular na expression. Ang artikulo ay nagbibigay ng mga halimbawa, problema at solusyon.
Algorithm
Ang mga nakaraang algorithm ng paghahanap ay nagresulta sa pag-backtrack kung ang isang bahagyang matagumpay na paghahanap ay nabigo upang makagawa ng isang resulta.Sa compilation mode, ang algorithm ay hindi gumagana sa mga simbolo. Nagpapasa ito ng mga tagubilin sa pinagsama-samang code. Napakabilis ng pagpapatupad - pagkatapos na maipasa ang data sa tuktok ng kasalukuyang listahan, awtomatiko nitong hahanapin ang lahat ng posibleng magkakasunod na character sa regular na expression.
Ang compilation at search algorithm ay kasama sa time-sharing text editor bilang contextual search. Siyempre, malayo ito sa tanging aplikasyon ng naturang pamamaraan sa paghahanap. Halimbawa, ang isang variant ng algorithm na ito ay ginagamit bilang isang paghahanap ng simbolo sa isang talahanayan sa assembler.
Ipinapalagay na pamilyar ang mambabasa sa mga regular na expression at sa IBM 7094 computer programming language.Compiler
Ang compiler ay binubuo ng tatlong yugto na tumatakbo nang magkatulad. Ang unang yugto ay ang syntax filtering, na nagbibigay-daan lamang sa syntactically correct na mga regular na expression na dumaan. Ang hakbang na ito ay naglalagay din ng "Β·" operator upang tumugma sa mga regular na expression. Sa pangalawang hakbang, ang regular na expression ay na-convert sa postfix form. Sa ikatlong yugto, nilikha ang object code. Ang unang 2 yugto ay halata, at hindi natin ito papansinin.
Ang artikulo ni Thompson ay hindi nagsasalita tungkol sa nondeterministic finite state machines, ngunit ito ay nagpapaliwanag nang maayos sa linear time algorithm at nagpapakita ng isang ALGOL-60 program na bumubuo ng assembly language code para sa IBM 7094. Ang pagpapatupad ay nakakalito, ngunit ang ideya ay napakasimple.
kasalukuyang landas sa paghahanap. Ito ay kinakatawan ng β icon na may isang input at dalawang output.
Ipinapakita ng Figure 1 ang mga function ng ikatlong hakbang ng compilation kapag binago ang isang halimbawa ng regular na expression. Ang unang tatlong character sa halimbawa ay a, b, c, at bawat isa ay lumilikha ng stack entry na S[i] at isang field ng NNODE.NNODE sa umiiral na code upang makabuo ng nagresultang regular na expression sa isang solong stack entry (tingnan ang Figure 5)
Ito ang magiging hitsura ng isang regular na expression .*.*=.*, kung iniisip mo ito tulad ng sa mga larawan mula sa artikulo ni Thompson.
Sa Fig. 0 mayroong limang estado na nagsisimula sa 0, at 3 cycle na nagsisimula sa state 1, 2 at 3. Ang tatlong cycle na ito ay tumutugma sa tatlong .* sa isang regular na expression. 3 oval na may mga tuldok ay tumutugma sa isang simbolo. Oval na may karatula = tumutugma sa isang literal na karakter =. Ang estado 4 ay pinal. Kung maabot natin ito, ang regular na expression ay tugma.
Upang makita kung paano magagamit ang gayong diagram ng estado para sa regular na pagtutugma ng expression .*.*=.*, titingnan natin ang pagtutugma ng string x=x. Ang programa ay nagsisimula mula sa estado 0, tulad ng ipinapakita sa Fig. 1.
Para gumana ang algorithm na ito, ang makina ng estado ay dapat na nasa ilang mga estado nang sabay-sabay. Ang isang non-deterministic finite machine ay gagawa ng lahat ng posibleng transition nang sabay-sabay.
Bago ito magkaroon ng oras upang basahin ang data ng input, napupunta ito sa parehong mga unang estado (1 at 2), tulad ng ipinapakita sa Fig. 2.
Sa Fig. 2 ay nagpapakita kung ano ang mangyayari kapag siya ay tumingin sa una x Π² x=x. x maaaring mapa sa tuktok na punto, mula sa estado 1 at pabalik sa estado 1. O x maaaring mapa sa punto sa ibaba, mula sa estado 2 at pabalik sa estado 2.
Matapos itugma ang una x Π² x=x nasa state 1 at 2 pa tayo. Hindi natin maabot ang state 3 o 4 dahil kailangan natin ng literal na karakter. =.
Pagkatapos ay isinasaalang-alang ng algorithm = Π² x=x. Tulad ng x bago nito, maaari itong itugma sa alinman sa nangungunang dalawang loop mula sa estado 1 hanggang sa estado 1 o mula sa estado 2 hanggang sa estado 2, ngunit ang algorithm ay maaaring tumugma sa literal = at lumipat mula sa estado 2 hanggang sa estado 3 (at kaagad na 4). Ito ay ipinapakita sa Fig. 3.
Ang algorithm pagkatapos ay lumipat sa huli x Π² x=x. Mula sa estado 1 at 2 ang parehong mga paglipat ay posible pabalik sa estado 1 at 2. Mula sa estado 3 x maaaring tumugma sa punto sa kanan at bumalik sa estado 3.
Sa yugtong ito, ang bawat karakter x=x isinasaalang-alang, at dahil naabot namin ang estado 4, ang regular na expression ay tumutugma sa string na iyon. Ang bawat character ay naproseso nang isang beses, kaya ang algorithm na ito ay linear sa haba ng input string. At walang backtracking.
Malinaw, pagkatapos maabot ang estado 4 (kapag ang algorithm ay tumugma x=) ang buong regular na expression ay tumugma, at ang algorithm ay maaaring wakasan nang hindi ito isinasaalang-alang x.
Ang algorithm na ito ay nakadepende nang linear sa laki ng input string.
Pinagmulan: www.habr.com