Meh 9 taun kepungkur Cloudflare minangka perusahaan cilik, lan aku ora nyambut gawe, aku mung dadi pelanggan. Sewulan sawise ngluncurake Cloudflare, aku nampa kabar yen situs webku DNS kayane ora bisa digunakake. Cloudflare wis nggawe owah-owahan menyang , lan ana DNS rusak.
Aku langsung nulis menyang Matthew Prince kanthi judhul "Endi DNSku?"), aku mangsuli:
Saka: John Graham-Cumming
Tanggal: 7 Oktober 2010, 9:14
Subject: Re: Where is my DNS?
Kanggo: Pangeran MatthewLaporan keren, matur nuwun. Aku mesthi bakal nelpon yen ana masalah. Sampeyan bisa uga kudu nulis kirim babagan iki yen sampeyan wis ngumpulake kabeh informasi teknis. Aku wong bakal seneng crita mbukak lan jujur. Utamane yen sampeyan masang grafik kanggo nuduhake carane lalu lintas wis berkembang wiwit diluncurake.
Aku duwe pemantauan apik ing situsku, lan aku nampa SMS babagan saben kegagalan. Pemantauan nuduhake yen kegagalan kedadeyan saka 13:03:07 nganti 14:04:12. Tes ditindakake saben limang menit.
Aku yakin sampeyan bakal ngerti. Apa sampeyan yakin ora perlu wong dhewe ing Eropah? 🙂
Lan wangsulane:
Saka: Matthew Pangeran
Tanggal: 7 Oktober 2010, 9:57
Subject: Re: Where is my DNS?
Kanggo: John Graham-Cummingmatur nuwun. Kita nanggapi saben wong sing nulis. Saiki aku arep menyang kantor lan kita bakal nulis soko ing blog utawa masang kiriman resmi ing papan buletin kita. Aku setuju banget, kejujuran iku kabeh.
Saiki Cloudflare minangka perusahaan sing gedhe banget, aku kerjane, lan saiki aku kudu nulis kanthi terang-terangan babagan kesalahane, akibat lan tumindak kita.
Acara 2 Juli
Ing tanggal 2 Juli, kita ngluncurake aturan anyar ing Aturan Ngatur kanggo WAF amarga ing saben inti prosesor ngolah lalu lintas HTTP/HTTPS ing jaringan Cloudflare ing saindenging jagad. Kita terus-terusan ngapikake aturan sing dikelola kanggo WAF kanggo nanggepi kerentanan lan ancaman anyar. Ing Mei, contone, kita cepet-cepet kanggo nglindhungi saka kerentanan serius ing SharePoint. Inti saka WAF kita yaiku kemampuan kanggo nyebarake aturan kanthi cepet lan global.
Sayange, nganyari Kamis kepungkur ngemot ekspresi reguler sing mbuwang sumber daya CPU HTTP / HTTPS nalika mundur. Fungsi proxy inti, CDN, lan WAF kita nandhang sangsara. Grafik kasebut nuduhake manawa sumber daya prosesor kanggo nglayani lalu lintas HTTP/HTTPS tekan meh 100% ing server ing jaringan kita.
Panggunaan CPU ing sawijining titik nalika kedadeyan
Akibaté, klien kita (lan klien klien kita) rampung karo kaca kesalahan 502 ing domain Cloudflare. Kesalahan 502 digawe dening server web ngarep Cloudflare sing isih duwe intine gratis nanging ora bisa komunikasi karo proses sing nangani lalu lintas HTTP/HTTPS.
Kita ngerti carane akeh ora nyaman iki wis nyebabake pelanggan kita. Kita isin banget. Lan kegagalan iki nyegah kita supaya bisa ngatasi kedadeyan kasebut kanthi efektif.
Yen sampeyan salah siji saka pelanggan iki, sampeyan mbokmenawa wedi, duka lan upset. Menapa malih, kita wis ora duwe a . Konsumsi CPU sing dhuwur amarga siji aturan WAF kanthi ekspresi reguler sing ora apik sing nyebabake mundur sing berlebihan. Punika ekspresi guilty: (?:(?:"|'|]|}||d|(?:nan|infinity|true|false|null|undefined|symbol|math)|`|-|+)+[)]*;?((?:s|-|~|!|{}||||+)*.*(?:.*=.*)))
Nalika iki menarik dhewe (lan aku bakal ngomong babagan iki kanthi luwih rinci ing ngisor iki), layanan Cloudflare mudhun sajrone 27 menit ora mung amarga ekspresi reguler sing ala. Butuh sawetara wektu kanggo njlèntrèhaké urutan acara sing nyebabake kegagalan, mula kita alon-alon nanggapi. Ing pungkasan kirim, aku bakal njlèntrèhaké backtracking ing expression biasa lan pitutur marang kowe apa apa karo.
Ana apa
Ayo dadi miwiti ing urutan. Kabeh wektu ing kene ana ing UTC.
Ing 13:42 pm, insinyur ing tim firewall nggawe owah-owahan cilik ing aturan deteksi nggunakake proses otomatis. Mulane, tiket panjalukan pangowahan digawe. Kita ngatur tiket kasebut liwat Jira (gambar ing ngisor iki).
Sawise 3 menit, kaca pisanan PagerDuty katon, nglaporake masalah karo WAF. Iki minangka tes sintetik sing nguji fungsionalitas WAF (kita duwe atusan) ing njaba Cloudflare kanggo ngawasi operasi normal. Iki langsung diterusake karo kaca tandha babagan tes layanan pungkasan Cloudflare liyane sing gagal, masalah lalu lintas global, kesalahan 502 sing nyebar, lan akeh laporan saka Points of Presence (PoP) ing kutha-kutha ing saindenging jagad sing nuduhake a lack saka sumber daya CPU.
Aku nampa sawetara tandha iki, nyerbu metu saka rapat, lan ing dalan menyang meja nalika kepala departemen pangembangan solusi kita ngandika yen kita wis ilang 80% saka lalu lintas kita. Aku mlayu menyang insinyur SRE, sing wis nggarap masalah kasebut. Kaping pisanan, kita ngira iki minangka serangan sing ora dingerteni.
Insinyur Cloudflare SRE kasebar ing saindenging jagad lan ngawasi kahanan ing saindhenging jam. Biasane, tandha-tandha iki menehi kabar babagan masalah lokal tartamtu kanthi ruang lingkup winates, dilacak ing dashboard internal, lan ditanggulangi kaping pirang-pirang saben dina. Nanging kaca lan kabar kasebut nuduhake ana sing serius, lan insinyur SRE langsung nyatakake tingkat keruwetan P0 lan ngubungi manajemen lan insinyur sistem.
Insinyur London kita lagi ngrungokake ceramah ing bale utama nalika iku. Kuliah kudu diselani, kabeh padha ngumpul ing ruang konferensi gedhe, lan spesialis liyane disebut. Iki dudu masalah khas sing bisa ditangani SRE dhewe. Penting banget kanggo melu spesialis sing tepat.
Ing 14:00 kita nemtokake manawa masalah kasebut ana ing WAF lan ora ana serangan. Tim kinerja narik data CPU lan dadi jelas yen WAF sing disalahake. Pegawe liyane dikonfirmasi teori iki nggunakake strace. Wong liya weruh ing log sing ana masalah karo WAF. Ing 14:02 p.m., kabeh tim teka kula nalika diusulake kanggo nggunakake global matèni, mekanisme dibangun ing Cloudflare sing mati siji komponen donya.
Kepiye carane mateni global kanggo WAF minangka crita sing beda. Iku ora prasaja. Kita nggunakake produk kita dhewe, lan wiwit layanan kita ora bisa digunakake, kita ora bisa otentikasi lan mlebu menyang panel kontrol internal (nalika kabeh wis didandani, kita ngerti yen sawetara anggota tim wis ilang akses amarga fitur keamanan sing mateni kredensial yen panel kontrol internal ora digunakake kanggo a dangu).
Lan kita ora bisa ngakses layanan internal, kayata Jira utawa sistem mbangun. Kita butuh mekanisme workaround, sing jarang digunakake (iki uga kudu digarap). Pungkasan, siji insinyur bisa mateni WAF ing 14:07, lan ing 14:09, lalu lintas lan tingkat CPU bali menyang normal ing endi wae. Mekanisme perlindungan Cloudflare liyane bisa digunakake kaya biasane.
Banjur kita nyetel babagan mulihake WAF. Kahanan kasebut ora biasa, mula kita nindakake tes negatif (takon awake dhewe yen owah-owahan kasebut pancen masalah) lan tes positif (mesthekake rollback bisa digunakake) ing sawijining kutha nggunakake lalu lintas sing kapisah, nransfer pelanggan sing mbayar saka kono.
Ing 14:52 kita padha nggawe percoyo sing kita mangertos alesan lan nggawe koreksi, lan ngaktifake WAF maneh.
Carane Cloudflare dianggo
Cloudflare duwe tim insinyur sing darmabakti kanggo ngatur aturan kanggo WAF. Dheweke ngupayakake ningkatake tingkat deteksi, nyuda positip palsu, lan kanthi cepet nanggapi ancaman anyar nalika muncul. Ing 60 dina pungkasan, ana 476 panjalukan pangowahan sing diproses kanggo aturan sing dikelola kanggo WAF (rata-rata saben 3 jam).
Owah-owahan tartamtu iki kudu disebarake ing mode simulasi, ing ngendi lalu lintas klien nyata ngliwati aturan kasebut, nanging ora ana sing diblokir. Kita nggunakake mode iki kanggo nyoba efektifitas aturan lan ngukur tingkat positif palsu lan negatif palsu. Nanging sanajan ing mode simulasi, aturan kasebut kudu ditindakake, lan ing kasus iki, aturan kasebut ngemot ekspresi biasa sing nggunakake sumber daya prosesor.
Minangka sampeyan bisa ndeleng saka panjalukan pangowahan ing ndhuwur, kita duwe rencana penyebaran, rencana rollback, lan link menyang prosedur operasi standar internal (SOP) kanggo jinis penyebaran iki. SOP kanggo ngganti aturan ngidini supaya bisa diterbitake sacara global. Bener, ing Cloudflare, kabeh ditindakake kanthi beda, lan SOP ndhaptar supaya kita ngirim piranti lunak kanggo tes lan panggunaan internal menyang titik internal (PoP) (sing digunakake karyawan), banjur menyang sawetara klien ing lokasi terisolasi, banjur kanggo nomer akeh klien, lan mung banjur kanggo donya kabèh.
Iki kaya apa. Kita nggunakake git internal liwat BitBucket. Insinyur sing nggarap owah-owahan ngirim kode, sing dibangun kanggo TeamCity, lan nalika mbangun liwat, reviewer diutus. Sawise panyuwunan narik disetujoni, kode diklumpukake lan seri tes ditindakake (maneh).
Yen mbangun lan tes rampung kanthi sukses, panjaluk pangowahan digawe ing Jira lan manajer utawa pimpinan sing cocog kudu nyetujoni owah-owahan kasebut. Sawise disetujoni, penyebaran dumadi menyang sing diarani "PoP menagerie": DOG, PIG lan (asu, babi lan kenari).
DOG PoP minangka Cloudflare PoP (kaya saben kutha liyane) sing mung digunakake dening karyawan Cloudflare. PoP kanggo panggunaan internal ngidini sampeyan nyekel masalah sadurunge lalu lintas pelanggan wiwit mili menyang solusi kasebut. Bab sing migunani.
Yen tes DOG sukses, kode kasebut pindhah menyang tahap PIG (guinea pig). Iki Cloudflare PoP, ing ngendi jumlah lalu lintas pelanggan gratis sing cilik mili liwat kode anyar.
Yen kabeh apik, kode kasebut menyang Canary. Kita duwe telung Canary PoP ing macem-macem negara. Ing wong-wong mau, lalu lintas klien sing mbayar lan gratis ngliwati kode anyar, lan iki minangka mriksa pungkasan kanggo kesalahan.
Proses Rilis Piranti Lunak ing Cloudflare
Yen kode ok ing Canary, kita ngeculake. Ngliwati kabeh tahapan - DOG, PIG, Canary, kabeh jagad - butuh sawetara jam utawa dina, gumantung saka owah-owahan kode. Amarga macem-macem jaringan lan klien Cloudflare, kita nguji kode kasebut sadurunge diluncurake sacara global kanggo kabeh klien. Nanging WAF ora khusus ngetutake proses iki amarga ancaman kudu ditanggapi kanthi cepet.
ancaman WAF
Ing sawetara taun kepungkur, ana peningkatan signifikan ing ancaman ing aplikasi umum. Iki amarga kasedhiyan piranti tes piranti lunak sing luwih akeh. Contone, kita bubar nulis babagan ).
Source:
Asring banget, bukti konsep digawe lan langsung diterbitake ing Github supaya tim sing njaga aplikasi kasebut bisa nyoba kanthi cepet lan mesthekake yen wis aman. Mulane, Cloudflare mbutuhake kemampuan kanggo nanggapi serangan anyar kanthi cepet supaya pelanggan duwe kesempatan kanggo ndandani piranti lunak.
Conto apik saka respon cepet Cloudflare yaiku penyebaran proteksi kerentanan SharePoint ing Mei (). Meh sanalika sawise woro-woro digawe, kita weruh akeh upaya kanggo ngeksploitasi kerentanan ing panginstalan SharePoint pelanggan. Wong lanang kita terus-terusan ngawasi ancaman anyar lan nulis aturan kanggo nglindhungi para pelanggan.
Aturan sing nyebabake masalah ing dina Kamis mesthine kanggo nglindhungi skrip lintas situs (XSS). Serangan kasebut uga dadi luwih kerep ing taun-taun pungkasan.
Source:
Prosedur standar kanggo ngganti aturan sing dikelola kanggo WAF yaiku nganakake tes integrasi terus (CI) sadurunge penyebaran global. Kemis kepungkur kita nindakake iki lan mbalek aturan. Ing 13:31 p.m., insinyur ngirim panjalukan narik disetujoni karo owah-owahan.
Jam 13:37 TeamCity ngumpulake aturan, nglakokake tes lan menehi imbalan. Suite test WAF nguji fungsi inti WAF lan kasusun saka akeh tes unit kanggo fungsi individu. Sawise tes unit, kita nguji aturan kanggo WAF nggunakake panjaluk HTTP sing akeh banget. Panjaluk HTTP mriksa panjaluk sing kudu diblokir dening WAF (kanggo nyegat serangan) lan sing bisa diidini (supaya ora mblokir kabeh lan ngindhari positip palsu). Nanging kita ora nyoba kanggo panggunaan CPU gedhe banget, lan mriksa log saka WAF mbangun sadurungé nuduhake yen wektu eksekusi test aturan ora nambah, lan iku angel Suspect sing ana ora bakal cukup sumber daya.
Tes liwati lan TeamCity wiwit kanthi otomatis nyebarke owah-owahan ing 13:42.
Quicksilver
Aturan WAF fokus ing remediasi ancaman langsung, mula kita nyebarake nggunakake toko nilai kunci sing disebarake Quicksilver, sing nyebarake owah-owahan global sajrone sawetara detik. Kabeh klien kita nggunakake teknologi iki nalika ngganti konfigurasi ing dashboard utawa liwat API, lan iku thanks kanggo kita nanggapi owah-owahan karo kacepetan kilat.
Kita wis ora ngomong akeh babagan Quicksilver. Sadurunge kita digunakake minangka toko kunci-nilai mbagekke global, nanging ana masalah operasional karo, lan kita wrote nyimpen dhewe, replicated ing luwih saka 180 kutha. Saiki kita nggunakake Quicksilver kanggo push owah-owahan konfigurasi kanggo klien, nganyari aturan WAF, lan disebaraké kode JavaScript ditulis dening klien kanggo Cloudflare Workers.
Mung sawetara detik saka ngeklik tombol ing dashboard utawa nelpon API kanggo nggawe pangowahan konfigurasi ing saindenging jagad. Pelanggan seneng kacepetan persiyapan iki. Lan Workers menehi panyebaran piranti lunak global sing meh cepet. Rata-rata, Quicksilver nyebar udakara 350 owah-owahan saben detik.
Lan Quicksilver cepet banget. Rata-rata, kita entuk persentil kaping 99 saka 2,29 detik kanggo nyebarake owah-owahan menyang saben komputer ing saindenging jagad. Kacepetan biasane apik. Sawise kabeh, yen sampeyan ngaktifake fungsi utawa mbusak cache, kedadeyan kasebut meh langsung lan ing endi wae. Ngirim kode liwat Cloudflare Workers dumadi ing kacepetan sing padha. Cloudflare njanjeni para pelanggan nganyari kanthi cepet ing wektu sing tepat.
Nanging ing kasus iki, kacepetan main guyon kejem ing kita, lan aturan diganti nang endi wae ing sawetara detik. Sampeyan bisa uga wis ngelingi yen kode WAF nggunakake Lua. Cloudflare nggunakake Lua sacara ekstensif ing produksi lan rincian kita . Lua WAF migunakake internal lan ditrapake backtracking kanggo cocog. Ora ana mekanisme kanggo nglindhungi ekspresi sing ora bisa dikendhaleni. Ing ngisor iki aku bakal ngomong luwih lengkap babagan iki lan apa sing ditindakake.
Sadurunge aturan disebarake, kabeh lumaku kanthi lancar: panjaluk tarik digawe lan disetujoni, pipa CI / CD ngumpulake lan nguji kode kasebut, panjaluk owah-owahan diajukake miturut SOP sing ngatur penyebaran lan rollback, lan penyebaran rampung.
Proses Penyebaran Cloudflare WAF
Ana sing salah
Nalika aku ngandika, kita masang Welasan aturan WAF anyar saben minggu, lan kita duwe akeh sistem ing Panggonan kanggo nglindhungi saka jalaran negatif saka penyebaran prajurit kuwi. Lan yen ana sing salah, biasane kombinasi sawetara kahanan bebarengan. Yen sampeyan nemokake mung siji alesan, iki, mesthi, reassuring, nanging ora tansah bener. Iki minangka alasan sing nyebabake kegagalan layanan HTTP/HTTPS kita.
- Insinyur nulis ekspresi reguler sing bisa nyebabake kakehan .
- A fitur sing bisa nyegah expression biasa saka mbuang kakehan CPU iki mistakenly dibusak ing refactoring saka WAF sawetara minggu sadurungé-refactoring dibutuhake kanggo WAF nggunakake sumber daya kurang.
- Mesin ekspresi reguler ora duwe jaminan kerumitan.
- Suite test ora bisa ndeteksi konsumsi CPU sing gedhe banget.
- SOP ngidini owah-owahan aturan sing ora penting diluncurake sacara global tanpa proses multi-langkah.
- Rencana rollback mbutuhake mbangun WAF lengkap kaping pindho, sing butuh wektu suwe.
- Tandha pisanan babagan masalah lalu lintas global dipicu kasep.
- We njupuk sawetara wektu kanggo nganyari kaca status.
- Kita duwe masalah ngakses sistem amarga ana kesalahan, lan prosedur bypass durung mapan.
- Insinyur SRE ilang akses menyang sawetara sistem amarga kapercayan wis kadaluwarsa amarga alasan keamanan.
- Pelanggan ora duwe akses menyang dasbor Cloudflare utawa API amarga padha ngliwati wilayah Cloudflare.
Apa sing wis owah wiwit Kamis kepungkur
Kaping pisanan, kita mungkasi kabeh karya babagan rilis kanggo WAF lan nindakake ing ngisor iki:
- We are reintroducing proteksi overuse CPU sing dibusak. (Siap)
- Priksa kanthi manual kabeh 3868 aturan ing aturan sing dikelola kanggo WAF nemokake lan mbenerake kasus potensial liyane saka backtracking sing berlebihan. (Verifikasi rampung)
- Kita kalebu profil kinerja kanggo kabeh aturan ing set test. (Dikarepake: 19 Juli)
- Ngalih menyang mesin ekspresi reguler utawa - loro nyedhiyani njamin runtime. (Dikarepake: 31 Juli)
- Kita nulis maneh SOP kanggo nyebarake aturan kanthi bertahap, kaya piranti lunak liyane ing Cloudflare, nanging ing wektu sing padha duwe kemampuan kanggo nyebarake kanthi cepet kanthi global yen serangan wis diwiwiti.
- Kita ngembangake kemampuan kanggo mbusak dasbor Cloudflare lan API kanthi cepet saka wilayah Cloudflare.
- Ngotomatisasi nganyari kaca .
Long term kita obah adoh saka Lua WAF aku wrote sawetara taun kepungkur. Pindhah WAF menyang . Kanthi cara iki WAF bakal luwih cepet lan nampa tingkat perlindungan tambahan.
kesimpulan
Gagal iki nyebabake masalah kanggo kita lan para pelanggan. Kita tumindak kanthi cepet kanggo mbenerake kahanan kasebut lan saiki lagi nggarap cacat ing proses sing nyebabake kacilakan, uga nggali luwih jero kanggo njaga masalah potensial kanthi ekspresi reguler ing mangsa ngarep nalika pindhah menyang teknologi anyar.
Kita isin banget babagan gangguan iki lan njaluk ngapura marang para pelanggan. Muga-muga owah-owahan iki bakal mesthekake yen kedadeyan kaya iki ora kedadeyan maneh.
Aplikasi. Backtracking ekspresi reguler
Kanggo mangerteni carane ekspresi:
(?:(?:"|'|]|}||d
(?:nan|infinity|true|false|null|undefined|symbol|math)|`|-
|+)+[)]*;?((?:s|-|~|!|{}||||+)*.*(?:.*=.*)))mangan kabeh sumber daya CPU, sampeyan kudu ngerti sethitik bab carane engine expression biasa standar dianggo. Masalah ing kene yaiku pola .*(?:.*=.*). (?: lan cocog ) iku klompok non-capturing (yaiku, ekspresi ing kurung diklompokaké minangka ekspresi siji).
Ing konteks konsumsi CPU gedhe banget, pola iki bisa diterangake minangka .*.*=.*. Ing wangun iki, pola katon ora perlu rumit. Nanging sing luwih penting, ing donya nyata, ekspresi (kaya ekspresi kompleks ing aturan WAF) sing njaluk mesin cocog karo fragmen sing diikuti karo fragmen liyane bisa nyebabake backtracking catastrophic. Lan mulane.
Ing ekspresi reguler . tegese sampeyan kudu cocog karo siji karakter, .* - cocog nul utawa luwih karakter "rakus", sing, njupuk maksimum karakter, supaya .*.*=.* tegese cocog karakter nul utawa luwih, banjur cocog karakter nul utawa luwih, golek literal = karakter, cocog nul utawa karakter liyane.
Ayo dadi njupuk baris test x=x. Iku cocog karo ekspresi .*.*=.*. .*.* sadurunge tandha witjaksono cocog pisanan x (salah sawijining klompok .* соответствует x, lan nomer loro - karakter nol). .* sawise = pertandhingan pungkasan x.
Perbandingan iki mbutuhake 23 langkah. Klompok pisanan .* в .*.*=.* tumindak greedily lan cocog kabeh senar x=x. Mesin pindhah menyang grup sabanjure .*. Kita ora duwe karakter liyane kanggo cocog, dadi klompok kapindho .* cocog karakter nul (iki diijini). Banjur engine pindhah menyang tandha =. Ora ana simbol maneh (klompok pisanan .* digunakake ekspresi kabeh x=x), ora ana perbandingan.
Banjur mesin ekspresi reguler bali menyang wiwitan. Dheweke pindhah menyang klompok pisanan .* lan mbandhingake с x= (tinimbang x=x), banjur njupuk klompok kapindho .*. Klompok kapindho .* dibandhingake karo sing kapindho x, lan kita ora duwe karakter sing isih ana. Lan nalika mesin tekan maneh = в .*.*=.*, ora ana sing bisa. Lan dheweke mundur maneh.
Kali iki grup .* isih cocog x=, nanging klompok kapindho .* ora ono maneh x, lan karakter nul. Mesin nyoba golek karakter harfiah = ing pola .*.*=.*, nanging ora metu (sawise kabeh, klompok pisanan wis dikuwasani .*). Lan dheweke mundur maneh.
Wektu iki klompok pisanan .* njupuk mung pisanan x. Nanging klompok kapindho .* "rakus" nyekel =x. Apa sampeyan wis ngira apa sing bakal kelakon? Mesin nyoba kanggo cocog literal =, gagal lan nggawe backtracking liyane.
Klompok pisanan .* isih cocog karo sing pisanan x. Kapindho .* mung njupuk =. Mesthine, mesin ora bisa cocog karo literal =, amarga klompok kapindho wis nindakake iki .*. Lan maneh backtracking. Lan kita nyoba kanggo cocog senar saka telung karakter!
Akibaté, klompok pisanan .* cocog mung siji x, kapindho .* - karo karakter nul, lan mesin pungkasanipun cocog literal = ing ekspresi с = ing baris. Sabanjure yaiku klompok pungkasan .* dibandhingake karo sing pungkasan x.
23 langkah mung kanggo x=x. Nonton video singkat babagan nggunakake Perl , sing nuduhake carane langkah lan backtracking dumadi.
Iki wis akeh karya, nanging apa yen tinimbang x=x kita bakal duwe x=xx? Iku 33 langkah. Lan yen x=xxx? 45. Hubungane ora linier. Grafik nuduhake comparison saka x=x kanggo x=xxxxxxxxxxxxxxxxxxxx (20 x после =). Yen kita duwe 20 x sawise =, mesin jangkep cocog ing 555 langkah! (Apa maneh, yen kita kalah x= lan senar mung dumadi saka 20 x, mesin bakal njupuk 4067 langkah kanggo mangerteni yen ora ana sing cocog).
Video iki nuduhake kabeh backtracking kanggo mbandhingake x=xxxxxxxxxxxxxxxxxxxx:
Masalahe yaiku nalika ukuran senar mundhak, wektu sing cocog mundhak super-linear. Nanging kahanan bisa dadi luwih elek yen ekspresi reguler rada diowahi. Ayo dadi ngomong kita wis .*.*=.*; (yaiku, ana titik koma harfiah ing mburi pola). Contone, kanggo cocog ekspresi kaya foo=bar;.
Lan ing kene backtracking bakal dadi bilai nyata. Kanggo mbandhingake x=x iku bakal njupuk 90 langkah, ora 23. Lan nomer sing akeh cepet. Kanggo mbandhingake x= lan 20 x, 5353 langkah dibutuhake. Punika bagan. Deleng nilai sumbu Y dibandhingake karo grafik sadurunge.
Yen sampeyan kasengsem, priksa kabeh 5353 langkah cocog sing gagal x=xxxxxxxxxxxxxxxxxxxx и .*.*=.*;
Kanthi nggunakake cocog kesed tinimbang rakus, ombone backtracking bisa kontrol. Yen kita ngganti ekspresi asli dadi .*?.*?=.*?, kanggo mbandhingake x=x iku bakal njupuk 11 langkah (ora 23). Minangka kanggo x=xxxxxxxxxxxxxxxxxxxx. Kabeh amarga ? после .* ngandhani mesin kanggo cocog nomer minimal karakter sadurunge nerusake.
Nanging mappings puguh ora rampung ngrampungake masalah backtracking. Yen kita ngganti conto catastrophic .*.*=.*; ing .*?.*?=.*?;, wektu eksekusi bakal tetep padha. x=x isih mbutuhake 555 langkah, lan x= lan 20 x - 5353.
Siji-sijine sing bisa ditindakake (saliyane nulis ulang pola kanggo spesifik luwih akeh) yaiku ninggalake mesin ekspresi reguler kanthi mekanisme mundur. Iki sing bakal ditindakake sajrone sawetara minggu sabanjure.
Solusi kanggo masalah iki wis dikenal wiwit 1968, nalika Kent Thompson nulis artikel ("Metode Pemrograman: Algoritma Panelusuran Ekspresi Reguler"). Artikel njlèntrèhaké mekanisme sing ngijini sampeyan kanggo Ngonversi expression biasa menyang mesin negara winates non-deterministik, lan sawise owah-owahan negara ing mesin negara winates non-deterministik, nggunakake algoritma kang wektu eksekusi gumantung linearly ing senar cocog.
Metode Pemrograman
Algoritma Panelusuran Ekspresi Reguler
Ken Thompson
Bell Telephone Laboratories, Inc., Murray Hill, New JerseyIki njlèntrèhaké cara kanggo nggoleki senar tartamtu saka karakter ing teks lan ngrembug implementasine saka cara iki ing wangun compiler. Compiler njupuk ekspresi reguler minangka kode sumber lan ngasilake program IBM 7094 minangka kode obyek. Program obyek njupuk input ing wangun teks telusuran lan ngetokake sinyal saben senar teks dicocogake karo ekspresi reguler sing diwenehake. Artikel kasebut nyedhiyakake conto, masalah lan solusi.
Algoritma
Algoritma telusuran sadurunge ngasilake backtracking yen panelusuran sebagian sukses gagal ngasilake asil.Ing mode kompilasi, algoritma ora bisa digunakake karo simbol. Iku liwat instruksi kanggo kode nyawiji. Eksekusi cepet banget - sawise ngirim data menyang ndhuwur dhaptar saiki, kanthi otomatis nggoleki kabeh karakter sing bisa berturut-turut ing ekspresi reguler.
Algoritma kompilasi lan telusuran kalebu ing editor teks nuduhake wektu minangka panelusuran kontekstual. Mesthine, iki adoh saka aplikasi mung prosedur telusuran kasebut. Contone, varian saka algoritma iki digunakake minangka telusuran simbol ing tabel ing assembler.
Dianggep manawa pamaca wis kenal karo ekspresi reguler lan basa pemrograman komputer IBM 7094.Compiler
Compiler kasusun saka telung orane tumrap sekolah mlaku ing podo karo. Tahap pertama yaiku nyaring sintaks, sing mung ngidini ekspresi reguler sing bener kanthi sintaksis. Langkah iki uga nglebokake operator "·" kanggo cocog karo ekspresi reguler. Ing langkah kapindho, ekspresi reguler diowahi dadi wangun postfix. Ing tahap katelu, kode obyek digawe. 2 tahap pisanan wis jelas, lan kita ora bakal ngelingi.
artikel Thompson ora pirembagan bab mesin negara wates nondeterministic, nanging nerangake algoritma wektu linear uga lan presents program ALGOL-60 sing ngasilake kode basa Déwan kanggo IBM 7094. Implementasine angel, nanging idea banget prasaja.
path panelusuran saiki. Iki diwakili dening lambang ⊕ kanthi siji input lan rong output.
Gambar 1 nuduhake fungsi langkah kompilasi katelu nalika ngowahi conto ekspresi reguler. Telung karakter pisanan ing conto yaiku a, b, c, lan saben nggawe entri tumpukan S[i] lan kolom NNODE.NNODE menyang kode sing ana kanggo ngasilake ekspresi reguler sing diasilake ing entri tumpukan siji (pirsani Gambar 5)
Iki minangka ekspresi reguler .*.*=.*, yen sampeyan mbayangno kaya ing gambar saka artikel Thompson.
Ing Fig. 0 ana limang negara sing diwiwiti saka 0, lan 3 siklus sing diwiwiti saka negara 1, 2 lan 3. Telung siklus kasebut cocog karo telung siklus. .* ing ekspresi biasa. 3 oval kanthi titik cocog karo siji simbol. Oval kanthi tandha = cocog karo karakter literal =. State 4 punika final. Yen kita tekan, banjur ekspresi reguler dicocogake.
Kanggo ndeleng carane diagram negara kuwi bisa digunakake kanggo cocog expression biasa .*.*=.*, kita bakal katon ing cocog string x=x. Program kasebut diwiwiti saka negara 0, kaya sing ditampilake ing Fig. 1.
Supaya algoritma iki bisa digunakake, mesin negara kudu ing sawetara negara bebarengan. Mesin winates non-deterministik bakal nggawe kabeh transisi bisa bebarengan.
Sadurunge duwe wektu kanggo maca data input, iku dadi loro negara pisanan (1 lan 2), minangka ditampilake ing Fig. 2.
Ing Fig. 2 nuduhake apa mengkono nalika katon ing pisanan x в x=x. x bisa peta kanggo titik ndhuwur, saka negara 1 lan bali menyang negara 1. Utawa x bisa peta menyang titik ing ngisor iki, pindhah saka negara 2 lan bali menyang negara 2.
Sawise cocog pisanan x в x=x kita isih ana ing negara bagian 1 lan 2. Kita ora bisa nggayuh negara bagian 3 utawa 4 amarga kita butuh karakter literal. =.
Algoritma banjur nimbang = в x=x. Kaya x sadurunge, bisa dicocogake karo salah siji saka rong puteran ndhuwur saka negara 1 menyang negara 1 utawa saka negara 2 kanggo negara 2, nanging algoritma bisa cocog literal = lan pindhah saka negara 2 menyang negara 3 (lan langsung 4). Iki dituduhake ing Fig. 3.
Algoritma banjur pindhah menyang sing pungkasan x в x=x. Saka negara 1 lan 2 transisi sing padha bisa bali menyang negara 1 lan 2. Saka negara 3 x bisa cocog titik ing sisih tengen lan bali menyang negara 3.
Ing tahap iki, saben karakter x=x dianggep, lan wiwit kita wis tekan negara 4, expression biasa cocog senar sing. Saben karakter diproses sapisan, supaya algoritma iki linear dawa string input. Lan ora mundur.
Temenan, sawise tekan negara 4 (nalika algoritma wis cocog x=) kabeh ekspresi reguler dicocogake, lan algoritma bisa mandheg tanpa dipikirake x.
Algoritma iki gumantung linearly ing ukuran string input.
Source: www.habr.com
