Hampir 9 tahun yang lalu Cloudflare adalah sebuah perusahaan kecil, dan saya tidak bekerja untuk itu, saya hanya seorang pelanggan. Sebulan setelah meluncurkan Cloudflare, saya menerima pemberitahuan bahwa situs web saya DNS sepertinya tidak berfungsi. Cloudflare telah melakukan perubahan , dan ada DNS yang rusak.
Saya segera menulis kepada Matthew Prince dengan judul “Di mana DNS saya?” dan dia mengirimkan kembali balasan panjang yang penuh dengan rincian teknis (), yang saya jawab:
Dari: John Graham-Cumming
Tanggal: 7 Oktober 2010, 9:14
Perihal: Re: Dimana DNS saya?
Kepada: Pangeran MatthewLaporan keren, terima kasih. Saya pasti akan menelepon jika ada masalah. Mungkin ada baiknya menulis postingan tentang ini setelah Anda mengumpulkan semua informasi teknis. Saya pikir orang-orang akan menyukai cerita yang terbuka dan jujur. Terutama jika Anda melampirkan grafik untuk menunjukkan pertumbuhan lalu lintas sejak diluncurkan.
Saya memiliki pemantauan yang baik di situs saya, dan saya menerima SMS tentang setiap kegagalan. Pantauan menunjukkan kegagalan terjadi pada pukul 13:03:07 hingga 14:04:12. Tes dilakukan setiap lima menit.
Saya yakin Anda akan mengetahuinya. Apakah Anda yakin tidak membutuhkan orang Anda sendiri di Eropa? 🙂
Dan dia menjawab:
Dari: Matthew Pangeran
Tanggal: 7 Oktober 2010, 9:57
Perihal: Re: Dimana DNS saya?
Kepada: John Graham-CummingTerima kasih. Kami menanggapi semua orang yang menulis. Saya sedang dalam perjalanan ke kantor sekarang dan kami akan menulis sesuatu di blog atau memasang pin pada postingan resmi di papan buletin kami. Saya sangat setuju, kejujuran adalah segalanya.
Sekarang Cloudflare adalah perusahaan yang sangat besar, saya bekerja untuknya, dan sekarang saya harus menulis secara terbuka tentang kesalahan kami, konsekuensinya, dan tindakan kami.
Acara 2 Juli
Pada tanggal 2 Juli kami meluncurkan aturan baru di Aturan Terkelola untuk WAF pada setiap inti prosesor yang memproses lalu lintas HTTP/HTTPS di jaringan Cloudflare di seluruh dunia. Kami terus meningkatkan aturan terkelola untuk WAF sebagai respons terhadap kerentanan dan ancaman baru. Pada bulan Mei, misalnya, kami bergegas untuk melindungi dari kerentanan serius di SharePoint. Inti dari WAF kami adalah kemampuan untuk menerapkan aturan secara cepat dan global.
Sayangnya, pembaruan Kamis lalu berisi ekspresi reguler yang menghabiskan terlalu banyak sumber daya CPU HTTP/HTTPS saat melakukan backtracking. Akibatnya, fungsi proxy inti, CDN, dan WAF kami terganggu. Grafik menunjukkan bahwa sumber daya prosesor untuk melayani lalu lintas HTTP/HTTPS mencapai hampir 100% di server di jaringan kami.
Penggunaan CPU pada satu titik kehadiran selama suatu insiden
Akibatnya, klien kami (dan klien klien kami) mendapatkan halaman kesalahan 502 di domain Cloudflare. Kesalahan 502 dihasilkan oleh server web front-end Cloudflare yang masih memiliki inti bebas tetapi tidak dapat berkomunikasi dengan proses yang menangani lalu lintas HTTP/HTTPS.
Kami tahu betapa besar ketidaknyamanan yang ditimbulkan oleh hal ini kepada pelanggan kami. Kami sangat malu. Dan kegagalan ini menghalangi kami untuk menangani insiden tersebut secara efektif.
Jika Anda salah satu pelanggan ini, Anda mungkin takut, marah, dan kesal. Apalagi kita belum punya . Konsumsi CPU yang tinggi disebabkan oleh satu aturan WAF dengan ekspresi reguler yang ditulis dengan buruk sehingga mengakibatkan kemunduran yang berlebihan. Inilah ekspresi bersalahnya: (?:(?:"|'|]|}||d|(?:nan|infinity|true|false|null|undefined|symbol|math)|`|-|+)+[)]*;?((?:s|-|~|!|{}||||+)*.*(?:.*=.*)))
Meskipun hal ini menarik (dan saya akan membicarakannya lebih detail di bawah), layanan Cloudflare tidak aktif selama 27 menit bukan hanya karena ekspresi reguler yang buruk. Kami memerlukan waktu beberapa saat untuk menjelaskan rangkaian peristiwa yang menyebabkan kegagalan tersebut, sehingga kami lambat dalam merespons. Di akhir postingan, saya akan menjelaskan backtracking dalam ekspresi reguler dan memberi tahu Anda apa yang harus dilakukan dengannya.
Apa yang terjadi
Mari kita mulai secara berurutan. Semua waktu di sini dalam UTC.
Pada pukul 13, seorang teknisi di tim firewall membuat perubahan kecil pada aturan deteksi menggunakan proses otomatis. Oleh karena itu, tiket permintaan perubahan telah dibuat. Kami mengelola tiket tersebut melalui Jira (tangkapan layar di bawah).
Setelah 3 menit, halaman pertama PagerDuty muncul, melaporkan masalah dengan WAF. Ini adalah pengujian sintetis yang menguji fungsionalitas WAF (kami memiliki ratusan di antaranya) di luar Cloudflare untuk memantau pengoperasian normal. Hal ini segera diikuti oleh halaman peringatan tentang kegagalan pengujian layanan end-to-end Cloudflare lainnya, masalah lalu lintas global, kesalahan 502 yang meluas, dan banyak laporan dari Points of Presence (PoP) kami di kota-kota di seluruh dunia yang mengindikasikan adanya kekurangan. sumber daya CPU.
Saya menerima beberapa peringatan ini, keluar dari rapat, dan sedang dalam perjalanan ke meja ketika kepala departemen pengembangan solusi kami mengatakan bahwa kami telah kehilangan 80% lalu lintas kami. Saya menemui teknisi SRE kami, yang sudah menangani masalah tersebut. Awalnya kami mengira itu adalah serangan yang tidak diketahui.
Insinyur Cloudflare SRE tersebar di seluruh dunia dan memantau situasi sepanjang waktu. Biasanya, peringatan ini memberi tahu Anda tentang masalah lokal tertentu dengan cakupan terbatas, dilacak di dasbor internal, dan diselesaikan beberapa kali per hari. Namun halaman dan pemberitahuan ini menunjukkan sesuatu yang sangat serius, dan teknisi SRE segera menyatakan tingkat keparahan P0 dan menghubungi teknisi manajemen dan sistem.
Insinyur kami di London sedang mendengarkan ceramah di aula utama pada saat itu. Ceramahnya harus dihentikan, semua orang berkumpul di ruang konferensi besar, dan lebih banyak spesialis dipanggil. Ini bukanlah masalah umum yang dapat ditangani sendiri oleh SRE. Melibatkan spesialis yang tepat sangatlah mendesak.
Pada pukul 14:00 kami memutuskan bahwa masalahnya ada pada WAF dan tidak ada serangan. Tim kinerja menarik data CPU dan menjadi jelas bahwa WAF-lah yang harus disalahkan. Karyawan lain mengkonfirmasi teori ini menggunakan strace. Orang lain melihat di log bahwa ada masalah dengan WAF. Pada pukul 14:02, seluruh tim mendatangi saya ketika diusulkan untuk menggunakan pembunuhan global, sebuah mekanisme yang dibangun di Cloudflare yang mematikan satu komponen di seluruh dunia.
Cara kami melakukan pembunuhan global untuk WAF adalah cerita yang berbeda. Hal ini tidak sesederhana itu. Kami menggunakan produk kami sendiri, dan sejak layanan kami tidak berfungsi, kami tidak dapat mengautentikasi dan masuk ke panel kontrol internal (ketika semuanya telah diperbaiki, kami mengetahui bahwa beberapa anggota tim kehilangan akses karena fitur keamanan yang menonaktifkan kredensial jika panel kontrol internal tidak digunakan untuk a lama).
Dan kami tidak bisa mengakses layanan internal kami, seperti Jira atau sistem build. Kami membutuhkan mekanisme penyelesaian masalah, yang jarang kami gunakan (ini juga perlu diselesaikan). Akhirnya, seorang insinyur berhasil menonaktifkan WAF pada pukul 14:07, dan pada pukul 14:09, lalu lintas dan tingkat CPU kembali normal di mana pun. Mekanisme perlindungan Cloudflare lainnya berfungsi seperti biasa.
Kemudian kami mulai memulihkan WAF. Situasinya di luar kebiasaan, jadi kami menjalankan tes negatif (bertanya pada diri sendiri apakah perubahan itu benar-benar masalahnya) dan tes positif (memastikan rollback berhasil) di satu kota menggunakan lalu lintas terpisah, memindahkan pelanggan yang membayar dari sana.
Pada 14:52 kami yakin bahwa kami memahami alasannya dan melakukan koreksi, dan mengaktifkan kembali WAF.
Cara kerja Cloudflare
Cloudflare memiliki tim insinyur yang berdedikasi untuk mengelola aturan WAF. Mereka berupaya meningkatkan tingkat deteksi, mengurangi kesalahan positif, dan dengan cepat merespons ancaman baru yang muncul. Dalam 60 hari terakhir, ada 476 permintaan perubahan yang diproses untuk aturan terkelola WAF (rata-rata satu permintaan setiap 3 jam).
Perubahan khusus ini perlu diterapkan dalam mode simulasi, di mana lalu lintas klien nyata melewati aturan, namun tidak ada yang diblokir. Kami menggunakan mode ini untuk menguji efektivitas peraturan dan mengukur tingkat positif palsu dan negatif palsu. Namun bahkan dalam mode simulasi, aturan harus benar-benar dijalankan, dan dalam hal ini aturan berisi ekspresi reguler yang menghabiskan terlalu banyak sumber daya prosesor.
Seperti yang dapat Anda lihat dari permintaan perubahan di atas, kami memiliki rencana penerapan, rencana pengembalian, dan tautan ke prosedur operasi standar (SOP) internal untuk jenis penerapan ini. SOP perubahan suatu aturan memungkinkan untuk dipublikasikan secara global. Sebenarnya, di Cloudflare, segala sesuatunya dilakukan dengan cara yang sangat berbeda, dan SOP mengharuskan kami mengirimkan perangkat lunak terlebih dahulu untuk pengujian dan penggunaan internal ke titik kehadiran internal (PoP) (yang digunakan oleh karyawan kami), kemudian ke sejumlah kecil klien di lokasi terpencil, lalu ke sejumlah besar klien, dan baru kemudian ke seluruh dunia.
Seperti inilah tampilannya. Kami menggunakan git secara internal melalui BitBucket. Insinyur yang mengerjakan perubahan mengirimkan kode, yang dibuat ke TeamCity, dan ketika pembangunan berhasil, peninjau akan ditugaskan. Setelah permintaan penarikan disetujui, kode dirakit dan serangkaian pengujian dijalankan (lagi).
Jika pembangunan dan pengujian berhasil diselesaikan, permintaan perubahan dibuat di Jira dan manajer atau pimpinan yang sesuai harus menyetujui perubahan tersebut. Setelah disetujui, penyebaran terjadi ke dalam apa yang disebut “kebun binatang PoP”: DOG, PIG dan (anjing, babi dan kenari).
DOG PoP adalah Cloudflare PoP (seperti kota lainnya) yang hanya digunakan oleh karyawan Cloudflare. PoP untuk penggunaan internal memungkinkan Anda mengetahui masalah sebelum lalu lintas pelanggan mulai mengalir ke solusi. Hal yang berguna.
Jika pengujian DOG berhasil, kode berpindah ke tahap PIG (kelinci percobaan). Ini adalah Cloudflare PoP, tempat sejumlah kecil lalu lintas pelanggan gratis mengalir melalui kode baru.
Jika semuanya baik-baik saja, kodenya masuk ke Canary. Kami memiliki tiga Canary PoP di berbagai belahan dunia. Di dalamnya, lalu lintas klien berbayar dan gratis melewati kode baru, dan ini adalah pemeriksaan kesalahan terakhir.
Proses Rilis Perangkat Lunak di Cloudflare
Jika kodenya oke di Canary, kami melepaskannya. Melewati semua tahapan - DOG, BABI, Canary, seluruh dunia - membutuhkan waktu beberapa jam atau hari, tergantung pada perubahan kode. Karena keragaman jaringan dan klien Cloudflare, kami menguji kode secara menyeluruh sebelum merilisnya secara global ke semua klien. Namun WAF tidak secara spesifik mengikuti proses ini karena ancaman perlu direspon dengan cepat.
Ancaman WAF
Selama beberapa tahun terakhir, terdapat peningkatan signifikan dalam ancaman pada aplikasi umum. Hal ini disebabkan oleh semakin banyaknya ketersediaan alat pengujian perangkat lunak. Misalnya, kami baru-baru ini menulis tentang ).
Sumber:
Seringkali, bukti konsep dibuat dan segera dipublikasikan di Github sehingga tim pengelola aplikasi dapat dengan cepat mengujinya dan memastikan keamanannya memadai. Oleh karena itu, Cloudflare memerlukan kemampuan untuk merespons serangan baru secepat mungkin sehingga pelanggan mempunyai kesempatan untuk memperbaiki perangkat lunaknya.
Contoh bagus dari respons cepat Cloudflare adalah penerapan perlindungan kerentanan SharePoint pada bulan Mei (). Segera setelah pengumuman tersebut dibuat, kami melihat sejumlah besar upaya untuk mengeksploitasi kerentanan dalam instalasi SharePoint pelanggan kami. Orang-orang kami terus memantau ancaman baru dan menulis peraturan untuk melindungi pelanggan kami.
Aturan yang menyebabkan masalah pada hari Kamis seharusnya melindungi terhadap skrip lintas situs (XSS). Serangan semacam ini juga semakin sering terjadi dalam beberapa tahun terakhir.
Sumber:
Prosedur standar untuk mengubah aturan terkelola untuk WAF adalah dengan melakukan pengujian integrasi berkelanjutan (CI) sebelum penerapan global. Kamis lalu kami melakukan ini dan meluncurkan aturannya. Pada pukul 13, seorang teknisi mengajukan permintaan penarikan yang disetujui beserta perubahannya.
Pada pukul 13:37 TeamCity mengumpulkan aturan, menjalankan tes, dan memberikan lampu hijau. Rangkaian pengujian WAF menguji fungsionalitas inti WAF dan terdiri dari sejumlah besar pengujian unit untuk masing-masing fungsi. Setelah pengujian unit, kami menguji aturan WAF menggunakan permintaan HTTP dalam jumlah besar. Permintaan HTTP memeriksa permintaan mana yang harus diblokir oleh WAF (untuk mencegat serangan) dan mana yang diizinkan masuk (agar tidak memblokir semuanya dan menghindari kesalahan positif). Namun kami tidak menguji penggunaan CPU yang berlebihan, dan pemeriksaan log build WAF sebelumnya menunjukkan bahwa waktu eksekusi pengujian aturan tidak bertambah, dan sulit untuk mencurigai bahwa sumber daya tidak mencukupi.
Pengujian berhasil dan TeamCity mulai menerapkan perubahan secara otomatis pada pukul 13.
Air raksa
Aturan WAF fokus pada remediasi ancaman secara langsung, jadi kami menerapkannya menggunakan penyimpanan nilai kunci Quicksilver yang terdistribusi, yang menyebarkan perubahan secara global dalam hitungan detik. Semua klien kami menggunakan teknologi ini ketika mereka mengubah konfigurasi di dasbor atau melalui API, dan berkat itulah kami merespons perubahan dengan kecepatan kilat.
Kami belum berbicara banyak tentang Quicksilver. Sebelumnya kami menggunakan sebagai toko nilai kunci yang didistribusikan secara global, namun ada masalah operasional dengannya, dan kami membuat toko kami sendiri, yang direplikasi di lebih dari 180 kota. Kami sekarang menggunakan Quicksilver untuk mendorong perubahan konfigurasi ke klien, memperbarui aturan WAF, dan mendistribusikan kode JavaScript yang ditulis oleh klien ke Cloudflare Workers.
Hanya perlu beberapa detik mulai dari mengeklik tombol di dasbor atau memanggil API hingga membuat perubahan konfigurasi di seluruh dunia. Pelanggan menyukai kecepatan pengaturan ini. Dan Workers memberi mereka penerapan perangkat lunak global secara instan. Rata-rata, Quicksilver menyebarkan sekitar 350 perubahan per detik.
Dan Quicksilver sangat cepat. Rata-rata, kami mencapai persentil ke-99 dalam waktu 2,29 detik untuk menyebarkan perubahan ke setiap komputer di seluruh dunia. Kecepatan biasanya merupakan hal yang baik. Lagi pula, saat Anda mengaktifkan suatu fungsi atau menghapus cache, hal itu terjadi hampir seketika dan di mana saja. Pengiriman kode melalui Cloudflare Workers terjadi dengan kecepatan yang sama. Cloudflare menjanjikan pelanggannya pembaruan cepat pada waktu yang tepat.
Namun dalam kasus ini, kecepatan mempermainkan kami, dan peraturan berubah di mana saja dalam hitungan detik. Anda mungkin memperhatikan bahwa kode WAF menggunakan Lua. Cloudflare menggunakan Lua secara ekstensif dalam produksi dan detail kami adalah . Lua WAF menggunakan secara internal dan menerapkan penelusuran mundur untuk pencocokan. Ia tidak memiliki mekanisme untuk melindungi terhadap ekspresi yang tidak terkendali. Di bawah ini saya akan berbicara lebih banyak tentang hal ini dan apa yang kami lakukan untuk mengatasinya.
Sebelum aturan diterapkan, semuanya berjalan lancar: permintaan penarikan dibuat dan disetujui, pipeline CI/CD mengumpulkan dan menguji kode, permintaan perubahan dikirimkan sesuai dengan SOP yang mengatur penerapan dan rollback, dan penerapan selesai.
Proses Penerapan Cloudflare WAF
Apa yang salah
Seperti yang saya katakan, kami menerapkan lusinan aturan WAF baru setiap minggunya, dan kami memiliki banyak sistem untuk melindungi terhadap konsekuensi negatif dari penerapan tersebut. Dan ketika terjadi kesalahan, biasanya itu merupakan kombinasi dari beberapa keadaan sekaligus. Jika Anda hanya menemukan satu alasan, hal ini tentu saja melegakan, namun tidak selalu benar. Ini adalah alasan yang menyebabkan kegagalan layanan HTTP/HTTPS kami.
- Seorang insinyur menulis ekspresi reguler yang bisa menghasilkan berlebihan .
- Sebuah fitur yang dapat mencegah ekspresi reguler membuang terlalu banyak CPU telah dihapus secara keliru saat pemfaktoran ulang WAF beberapa minggu sebelumnya—pemfaktoran ulang diperlukan untuk membuat WAF mengonsumsi lebih sedikit sumber daya.
- Mesin ekspresi reguler tidak memiliki jaminan kompleksitas.
- Rangkaian pengujian tidak dapat mendeteksi konsumsi CPU yang berlebihan.
- SOP ini memungkinkan perubahan peraturan yang tidak mendesak untuk diterapkan secara global tanpa proses multi-langkah.
- Rencana rollback memerlukan menjalankan build WAF penuh dua kali, yang memakan waktu lama.
- Peringatan pertama tentang masalah lalu lintas global terlambat dipicu.
- Kami memerlukan waktu beberapa saat untuk memperbarui halaman status.
- Kami mengalami masalah dalam mengakses sistem karena kesalahan, dan prosedur bypass tidak dilakukan dengan baik.
- Insinyur SRE kehilangan akses ke beberapa sistem karena kredensial mereka telah habis masa berlakunya karena alasan keamanan.
- Pelanggan kami tidak memiliki akses ke dashboard atau API Cloudflare karena mereka melalui wilayah Cloudflare.
Apa yang berubah sejak Kamis lalu
Pertama, kami sepenuhnya menghentikan semua pengerjaan rilis untuk WAF dan melakukan hal berikut:
- Kami memperkenalkan kembali perlindungan penggunaan berlebihan CPU yang telah kami hapus. (Siap)
- Memeriksa secara manual seluruh 3868 aturan dalam aturan yang dikelola agar WAF dapat menemukan dan memperbaiki potensi kasus kemunduran berlebihan lainnya. (Verifikasi selesai)
- Kami menyertakan pembuatan profil kinerja untuk semua aturan dalam set pengujian. (Diharapkan: 19 Juli)
- Beralih ke mesin ekspresi reguler или - keduanya memberikan jaminan runtime. (Diharapkan: 31 Juli)
- Kami sedang menulis ulang SOP untuk menerapkan aturan secara bertahap, seperti perangkat lunak lain di Cloudflare, namun pada saat yang sama memiliki kemampuan untuk penerapan darurat global jika serangan sudah dimulai.
- Kami sedang mengembangkan kemampuan untuk segera menghapus dasbor dan API Cloudflare dari wilayah Cloudflare.
- Mengotomatiskan pembaruan halaman .
Dalam jangka panjang kita menjauh dari Lua WAF yang saya tulis beberapa tahun lalu. Memindahkan WAF ke . Dengan cara ini WAF akan lebih cepat dan menerima tingkat perlindungan tambahan.
Kesimpulan
Kegagalan ini menyebabkan masalah bagi kami dan pelanggan kami. Kami bertindak cepat untuk memperbaiki situasi dan kini sedang memperbaiki kekurangan dalam proses yang menyebabkan error tersebut, serta menggali lebih dalam untuk mencegah potensi masalah ekspresi reguler di masa mendatang saat bermigrasi ke teknologi baru.
Kami sangat malu dengan pemadaman ini dan meminta maaf kepada pelanggan kami. Kami berharap perubahan ini dapat memastikan hal seperti ini tidak terjadi lagi.
Aplikasi. Mundur ekspresi reguler
Untuk memahami bagaimana ekspresi:
(?:(?:"|'|]|}||d
(?:nan|infinity|true|false|null|undefined|symbol|math)|`|-
|+)+[)]*;?((?:s|-|~|!|{}||||+)*.*(?:.*=.*)))menghabiskan semua sumber daya CPU, Anda perlu mengetahui sedikit tentang cara kerja mesin ekspresi reguler standar. Masalahnya di sini adalah polanya .*(?:.*=.*). (?: dan sesuai ) adalah grup yang tidak menangkap (yaitu, ekspresi dalam tanda kurung dikelompokkan sebagai satu ekspresi).
Dalam konteks konsumsi CPU yang berlebihan, pola ini dapat digambarkan sebagai .*.*=.*. Dalam bentuk ini, polanya terlihat terlalu rumit. Namun yang lebih penting, di dunia nyata, ekspresi (seperti ekspresi kompleks dalam aturan WAF) yang meminta mesin untuk mencocokkan sebuah fragmen yang diikuti oleh fragmen lain dapat menyebabkan kemunduran yang sangat besar. Dan itulah kenapa.
Dalam ekspresi reguler . berarti Anda harus mencocokkan satu karakter, .* - mencocokkan nol atau lebih karakter "dengan rakus", yaitu menangkap karakter sebanyak-banyaknya, sehingga .*.*=.* berarti mencocokkan nol atau lebih karakter, lalu mencocokkan nol atau lebih karakter, menemukan karakter = literal, mencocokkan nol atau lebih karakter.
Mari kita ambil jalur tesnya x=x. Itu sesuai dengan ungkapannya .*.*=.*. .*.* sebelum tanda sama dengan cocok dengan yang pertama x (salah satu kelompok .* соответствует x, dan yang kedua - nol karakter). .* setelah = pertandingan terakhir x.
Perbandingan ini membutuhkan 23 langkah. Kelompok pertama .* в .*.*=.* bertindak rakus dan mencocokkan seluruh string x=x. Mesin berpindah ke grup berikutnya .*. Kami tidak memiliki karakter lagi untuk dicocokkan, jadi grup kedua .* cocok dengan nol karakter (ini diperbolehkan). Kemudian mesin bergerak menuju tanda tersebut =. Tidak ada lagi simbol (kelompok pertama .* menggunakan seluruh ekspresi x=x), tidak ada perbandingan yang terjadi.
Dan kemudian mesin ekspresi reguler kembali ke awal. Dia beralih ke kelompok pertama .* dan membandingkannya с x= (bukannya x=x), dan kemudian menghadapi kelompok kedua .*. Kelompok kedua .* dibandingkan dengan yang kedua x, dan sekali lagi kami tidak memiliki karakter tersisa. Dan ketika mesin mencapai lagi = в .*.*=.*, tidak ada yang berhasil. Dan dia mundur lagi.
Kali ini grupnya .* masih cocok x=, tapi kelompok kedua .* tidak lagi x, dan nol karakter. Mesin sedang mencoba menemukan karakter literal = dalam polanya .*.*=.*, tapi tidak keluar (toh kelompok pertama sudah menempatinya .*). Dan dia mundur lagi.
Kali ini kelompok pertama .* hanya mengambil x pertama. Tapi kelompok kedua .* menangkap "serakah". =x. Apakah Anda sudah menebak apa yang akan terjadi? Mesin mencoba mencocokkan literal =, gagal dan melakukan kemunduran lagi.
Kelompok pertama .* masih cocok dengan yang pertama x... Kedua .* hanya membutuhkan waktu =. Tentu saja, mesinnya tidak bisa menandingi literalnya =, karena kelompok kedua sudah melakukan ini .*. Dan lagi mundur. Dan kami mencoba mencocokkan rangkaian tiga karakter!
Hasilnya, kelompok pertama .* hanya cocok dengan yang pertama x, kedua .* - dengan nol karakter, dan mesin akhirnya cocok dengan literal = dalam ekspresi с = Di barisan. Berikutnya adalah kelompok terakhir .* dibandingkan dengan yang terakhir x.
23 langkah hanya untuk x=x. Tonton video singkat tentang penggunaan Perl , yang menunjukkan bagaimana langkah dan kemunduran terjadi.
Ini sudah merupakan pekerjaan yang banyak, tetapi bagaimana jika sebaliknya x=x kami akan memiliki x=xx? Itu 33 langkah. Dan jika x=xxx? 45. Hubungannya tidak linier. Grafik menunjukkan perbandingan dari x=x untuk x=xxxxxxxxxxxxxxxxxxxx (20 x setelah =). Jika kita memiliki 20 x setelahnya =, mesin menyelesaikan pencocokan dalam 555 langkah! (Apalagi jika kita sudah kalah x= dan stringnya hanya terdiri dari 20 x, mesin akan mengambil 4067 langkah untuk memahami bahwa tidak ada kecocokan).
Video ini menunjukkan semua kemunduran untuk perbandingan x=xxxxxxxxxxxxxxxxxxxx:
Masalahnya adalah seiring bertambahnya ukuran string, waktu pencocokan bertambah secara super-linear. Namun keadaan bisa menjadi lebih buruk jika ekspresi regulernya sedikit diubah. Katakanlah kita punya .*.*=.*; (yaitu, ada titik koma literal di akhir pola). Misalnya untuk mencocokkan ekspresi seperti foo=bar;.
Dan di sini kemunduran akan menjadi bencana yang nyata. Untuk perbandingan x=x dibutuhkan 90 langkah, bukan 23. Dan jumlah itu bertambah dengan cepat. Untuk membandingkan x= dan 20 x, diperlukan 5353 langkah. Berikut grafiknya. Lihatlah nilai sumbu Y dibandingkan dengan grafik sebelumnya.
Jika Anda tertarik, lihat 5353 langkah pencocokan yang gagal x=xxxxxxxxxxxxxxxxxxxx и .*.*=.*;
Dengan menggunakan pencocokan yang malas dan tidak serakah, tingkat kemunduran dapat dikendalikan. Jika kita mengubah ekspresi aslinya menjadi .*?.*?=.*?, untuk perbandingan x=x itu akan membutuhkan 11 langkah (bukan 23). Adapun x=xxxxxxxxxxxxxxxxxxxx. Semua karena ? setelah .* memberitahu mesin untuk mencocokkan jumlah minimum karakter sebelum melanjutkan.
Namun pemetaan yang lambat tidak sepenuhnya menyelesaikan masalah kemunduran. Jika kita mengganti contoh bencana tersebut .*.*=.*; pada .*?.*?=.*?;, waktu eksekusi akan tetap sama. x=x masih membutuhkan 555 langkah, dan x= dan 20 x - 5353.
Satu-satunya hal yang dapat dilakukan (selain menulis ulang pola secara menyeluruh agar lebih spesifik) adalah meninggalkan mesin ekspresi reguler dengan mekanisme kemundurannya. Inilah yang akan kami lakukan selama beberapa minggu ke depan.
Solusi untuk masalah ini telah diketahui sejak tahun 1968, ketika Kent Thompson menulis sebuah artikel (“Metode Pemrograman: Algoritma Pencarian Ekspresi Reguler”). Artikel ini menjelaskan mekanisme yang memungkinkan Anda mengonversi ekspresi reguler menjadi mesin keadaan terbatas non-deterministik, dan setelah perubahan keadaan pada mesin keadaan terbatas non-deterministik, gunakan algoritma yang waktu eksekusinya bergantung secara linier pada string yang cocok.
Metode Pemrograman
Algoritma Pencarian Ekspresi Reguler
Ken Thompson
Bell Telephone Laboratories, Inc., Murray Hill, New JerseyIni menjelaskan metode untuk mencari string karakter tertentu dalam teks dan membahas implementasi metode ini dalam bentuk kompiler. Kompiler mengambil ekspresi reguler sebagai kode sumber dan menghasilkan program IBM 7094 sebagai kode objek. Program objek mengambil masukan dalam bentuk teks pencarian dan memancarkan sinyal setiap kali string teks dicocokkan dengan ekspresi reguler yang diberikan. Artikel ini memberikan contoh, masalah dan solusi.
Algoritma
Algoritme pencarian sebelumnya mengakibatkan kemunduran jika pencarian yang berhasil sebagian gagal memberikan hasil.Dalam mode kompilasi, algoritma tidak bekerja dengan simbol. Itu meneruskan instruksi ke kode yang dikompilasi. Eksekusinya sangat cepat - setelah meneruskan data ke bagian atas daftar saat ini, secara otomatis mencari semua kemungkinan karakter berurutan dalam ekspresi reguler.
Algoritma kompilasi dan pencarian disertakan dalam editor teks pembagian waktu sebagai pencarian kontekstual. Tentu saja, ini bukan satu-satunya penerapan prosedur pencarian semacam itu. Misalnya varian dari algoritma ini digunakan sebagai pencarian simbol pada tabel di assembler.
Diasumsikan bahwa pembaca sudah familiar dengan ekspresi reguler dan bahasa pemrograman komputer IBM 7094.Penyusun
Kompiler terdiri dari tiga tahap yang berjalan secara paralel. Tahap pertama adalah pemfilteran sintaksis, yang hanya mengizinkan ekspresi reguler yang benar secara sintaksis untuk melewatinya. Langkah ini juga menyisipkan operator "·" untuk mencocokkan ekspresi reguler. Pada langkah kedua, ekspresi reguler diubah ke bentuk postfix. Pada tahap ketiga, kode objek dibuat. 2 tahap pertama sudah jelas, dan kami tidak akan membahasnya.
Artikel Thompson tidak berbicara tentang mesin keadaan terbatas nondeterministik, tetapi artikel tersebut menjelaskan algoritma waktu linier dengan baik dan menyajikan program ALGOL-60 yang menghasilkan kode bahasa rakitan untuk IBM 7094. Implementasinya rumit, tetapi idenya sangat sederhana.
jalur pencarian saat ini. Diwakili oleh ikon ⊕ dengan satu masukan dan dua keluaran.
Gambar 1 menunjukkan fungsi langkah kompilasi ketiga saat mentransformasikan contoh ekspresi reguler. Tiga karakter pertama dalam contoh adalah a, b, c, dan masing-masing membuat entri tumpukan S[i] dan bidang NNODE.NNODE ke kode yang ada untuk menghasilkan ekspresi reguler yang dihasilkan dalam satu entri tumpukan (lihat Gambar 5)
Seperti inilah ekspresi regulernya .*.*=.*, jika Anda membayangkannya seperti pada gambar dari artikel Thompson.
Pada Gambar. 0 ada lima keadaan yang dimulai dari 0, dan 3 siklus yang dimulai dari keadaan 1, 2 dan 3. Ketiga siklus ini berhubungan dengan tiga .* dalam ekspresi reguler. 3 oval dengan titik sesuai dengan satu simbol. Oval dengan tanda = cocok dengan karakter literal =. Negara bagian 4 adalah final. Jika kita mencapainya, maka ekspresi regulernya cocok.
Untuk melihat bagaimana diagram keadaan tersebut dapat digunakan untuk pencocokan ekspresi reguler .*.*=.*, kita akan melihat pencocokan string x=x. Program dimulai dari keadaan 0, seperti yang ditunjukkan pada Gambar. 1.
Agar algoritma ini dapat bekerja, mesin negara harus berada dalam beberapa keadaan secara bersamaan. Mesin berhingga non-deterministik akan melakukan semua kemungkinan transisi secara bersamaan.
Sebelum ia mempunyai waktu untuk membaca data masukan, ia masuk ke kedua keadaan pertama (1 dan 2), seperti yang ditunjukkan pada Gambar. 2.
Pada Gambar. 2 menunjukkan apa yang terjadi ketika dia melihat yang pertama x в x=x. x dapat memetakan ke titik teratas, beralih dari negara bagian 1 dan kembali ke negara bagian 1. Atau x dapat memetakan ke titik di bawah, pergi dari negara bagian 2 dan kembali ke negara bagian 2.
Setelah mencocokkan yang pertama x в x=x kita masih di status 1 dan 2. Kita tidak bisa mencapai status 3 atau 4 karena kita memerlukan karakter literal =.
Algoritme kemudian mempertimbangkan = в x=x. Seperti x sebelumnya, ia dapat dicocokkan dengan salah satu dari dua loop teratas dari negara bagian 1 ke negara bagian 1 atau dari negara bagian 2 ke negara bagian 2, namun algoritme dapat mencocokkan literal = dan berpindah dari negara bagian 2 ke negara bagian 3 (dan segera 4). Hal ini ditunjukkan pada gambar. 3.
Algoritme kemudian beralih ke yang terakhir x в x=x. Dari negara bagian 1 dan 2 transisi yang sama dimungkinkan kembali ke negara bagian 1 dan 2. Dari negara bagian 3 x dapat mencocokkan titik di sebelah kanan dan kembali ke keadaan 3.
Pada tahap ini, setiap karakter x=x dipertimbangkan, dan karena kita telah mencapai status 4, ekspresi reguler cocok dengan string tersebut. Setiap karakter diproses satu kali, sehingga algoritma ini linier sepanjang string masukan. Dan tidak ada kemunduran.
Tentunya setelah mencapai state 4 (ketika algoritma sudah cocok x=) seluruh ekspresi reguler cocok, dan algoritma dapat berhenti tanpa mempertimbangkannya sama sekali x.
Algoritma ini bergantung secara linier pada ukuran string masukan.
Sumber: www.habr.com