Hampir 9 tahun yang lalu Cloudflare adalah sebuah syarikat kecil, dan saya tidak bekerja untuknya, saya hanya seorang pelanggan. Sebulan selepas melancarkan Cloudflare, saya menerima pemberitahuan bahawa tapak web saya DNS nampaknya tidak berfungsi. Cloudflare telah membuat perubahan kepada , dan terdapat DNS rosak.
Saya segera menulis kepada Matthew Prince dengan tajuk "Di mana DNS saya?" dan dia menghantar balasan panjang penuh dengan butiran teknikal (), yang saya jawab:
Daripada: John Graham-Cumming
Tarikh: 7 Oktober 2010, 9:14
Subjek: Re: Di manakah DNS saya?
Kepada: Matthew PrinceLaporan yang bagus, terima kasih. Saya pasti akan menghubungi jika ada masalah. Mungkin berbaloi untuk menulis siaran tentang perkara ini setelah anda mengumpulkan semua maklumat teknikal. Saya fikir orang akan menikmati cerita yang terbuka dan jujur. Terutamanya jika anda melampirkan graf padanya untuk menunjukkan bagaimana trafik telah berkembang sejak dilancarkan.
Saya mempunyai pemantauan yang baik di tapak saya, dan saya menerima SMS tentang setiap kegagalan. Pemantauan menunjukkan bahawa kegagalan berlaku dari 13:03:07 hingga 14:04:12. Ujian dijalankan setiap lima minit.
Saya pasti anda akan memikirkannya. Adakah anda pasti anda tidak memerlukan orang anda sendiri di Eropah? π
Dan dia menjawab:
Daripada: Matthew Prince
Tarikh: 7 Oktober 2010, 9:57
Subjek: Re: Di manakah DNS saya?
Kepada: John Graham-CummingTerima kasih. Kami membalas semua orang yang menulis. Saya dalam perjalanan ke pejabat sekarang dan kami akan menulis sesuatu di blog atau menyematkan catatan rasmi pada papan buletin kami. Saya bersetuju sepenuhnya, kejujuran adalah segala-galanya.
Sekarang Cloudflare adalah syarikat yang sangat besar, saya bekerja untuknya, dan sekarang saya perlu menulis secara terbuka tentang kesilapan kami, akibatnya dan tindakan kami.
Peristiwa 2 Julai
Pada 2 Julai, kami melancarkan peraturan baharu dalam Peraturan Terurus untuk WAF pada setiap teras pemproses memproses trafik HTTP/HTTPS pada rangkaian Cloudflare di seluruh dunia. Kami sentiasa menambah baik peraturan terurus untuk WAF sebagai tindak balas kepada kelemahan dan ancaman baharu. Pada bulan Mei, sebagai contoh, kami tergesa-gesa untuk melindungi daripada kelemahan yang serius dalam SharePoint. Inti dari WAF kami ialah keupayaan untuk menggunakan peraturan dengan cepat dan global.
Malangnya, kemas kini Khamis lalu mengandungi ungkapan biasa yang membazirkan terlalu banyak sumber CPU HTTP/HTTPS untuk menjejak ke belakang. Proksi teras kami, CDN dan fungsi WAF terjejas akibatnya. Graf menunjukkan bahawa sumber pemproses untuk menyediakan trafik HTTP/HTTPS mencapai hampir 100% pada pelayan dalam rangkaian kami.
Penggunaan CPU pada satu titik kehadiran semasa kejadian
Akibatnya, pelanggan kami (dan pelanggan pelanggan kami) berakhir dengan halaman ralat 502 dalam domain Cloudflare. Ralat 502 dijana oleh pelayan web bahagian hadapan Cloudflare yang masih mempunyai teras percuma tetapi tidak dapat berkomunikasi dengan proses yang mengendalikan trafik HTTP/HTTPS.
Kami tahu betapa banyak kesulitan yang telah menyebabkan pelanggan kami. Kami sangat malu. Dan kegagalan ini menghalang kami daripada menangani insiden itu dengan berkesan.
Jika anda adalah salah seorang daripada pelanggan ini, anda mungkin takut, marah dan kecewa. Lebih-lebih lagi, kami tidak mempunyai . Penggunaan CPU yang tinggi adalah disebabkan oleh satu peraturan WAF dengan ungkapan biasa yang ditulis dengan buruk yang mengakibatkan penjejakan ke belakang yang berlebihan. Inilah ungkapan bersalah: (?:(?:"|'|]|}||d|(?:nan|infinity|true|false|null|undefined|symbol|math)|`|-|+)+[)]*;?((?:s|-|~|!|{}||||+)*.*(?:.*=.*)))
Walaupun ini menarik dengan sendirinya (dan saya akan membincangkannya dengan lebih terperinci di bawah), perkhidmatan Cloudflare telah dihentikan selama 27 minit bukan sahaja kerana ekspresi biasa yang buruk. Kami mengambil sedikit masa untuk menerangkan urutan peristiwa yang membawa kepada kegagalan, jadi kami lambat bertindak balas. Pada penghujung siaran, saya akan menerangkan penjejakan ke belakang dalam ungkapan biasa dan memberitahu anda perkara yang perlu dilakukan dengannya.
Apa yang berlaku
Mari kita mulakan mengikut urutan. Semua masa di sini adalah dalam UTC.
Pada 13:42 p.m., seorang jurutera dalam pasukan tembok api membuat sedikit perubahan pada peraturan pengesanan menggunakan proses automatik. Sehubungan itu, tiket permintaan perubahan telah dibuat. Kami menguruskan tiket sedemikian melalui Jira (gambar skrin di bawah).
Selepas 3 minit, halaman pertama PagerDuty muncul, melaporkan masalah dengan WAF. Ini adalah ujian sintetik yang menguji kefungsian WAF (kami mempunyai ratusan daripadanya) di luar Cloudflare untuk memantau operasi biasa. Ini diikuti serta-merta dengan halaman makluman tentang ujian perkhidmatan hujung ke hujung Cloudflare lain yang gagal, isu trafik global, ralat 502 yang meluas dan satu tan laporan daripada Tempat Kehadiran (PoP) kami di bandar di seluruh dunia yang menunjukkan kekurangan sumber CPU.
Saya menerima beberapa makluman ini, menyerbu keluar dari mesyuarat dan sedang dalam perjalanan ke meja apabila ketua jabatan pembangunan penyelesaian kami berkata bahawa kami telah kehilangan 80% trafik kami. Saya berlari ke jurutera SRE kami, yang telah menyelesaikan masalah itu. Pada mulanya kami fikir ia adalah sejenis serangan yang tidak diketahui.
Jurutera Cloudflare SRE tersebar di seluruh dunia dan memantau keadaan sepanjang masa. Lazimnya, makluman ini memberitahu anda tentang isu setempat khusus dengan skop terhad, dijejaki pada papan pemuka dalaman dan diselesaikan beberapa kali sehari. Tetapi halaman dan pemberitahuan ini menunjukkan sesuatu yang sangat serius, dan jurutera SRE segera mengisytiharkan tahap keterukan P0 dan menghubungi jurutera pengurusan dan sistem.
Jurutera London kami sedang mendengar ceramah di dewan utama ketika itu. Kuliah terpaksa dihentikan, semua orang berkumpul di bilik persidangan yang besar, dan lebih ramai pakar dipanggil. Ini bukan masalah biasa yang boleh ditangani oleh SRE sendiri. Adalah penting untuk melibatkan pakar yang betul.
Pada pukul 14:00 kami menentukan bahawa masalahnya adalah dengan WAF dan tiada serangan. Pasukan prestasi menarik data CPU dan menjadi jelas bahawa WAF dipersalahkan. Pekerja lain mengesahkan teori ini menggunakan strace. Orang lain melihat dalam log bahawa terdapat masalah dengan WAF. Pada jam 14:02 petang, seluruh pasukan datang kepada saya apabila dicadangkan untuk menggunakan pembunuhan global, mekanisme yang dibina dalam Cloudflare yang menutup satu komponen di seluruh dunia.
Bagaimana kami melakukan pembunuhan global untuk WAF adalah cerita yang berbeza. Ia tidak semudah itu. Kami menggunakan produk kami sendiri, dan sejak perkhidmatan kami tidak berfungsi, kami tidak dapat mengesahkan dan log masuk ke panel kawalan dalaman (apabila semuanya telah ditetapkan, kami mengetahui bahawa beberapa ahli pasukan telah kehilangan akses disebabkan oleh ciri keselamatan yang melumpuhkan kelayakan jika panel kawalan dalaman tidak digunakan untuk lama).
Dan kami tidak dapat mendapatkan perkhidmatan dalaman kami, seperti Jira atau sistem binaan. Kami memerlukan mekanisme penyelesaian, yang jarang kami gunakan (ini juga perlu diuruskan). Akhirnya, seorang jurutera berjaya melumpuhkan WAF pada 14:07, dan pada 14:09, trafik dan tahap CPU kembali normal di mana-mana. Selebihnya mekanisme perlindungan Cloudflare berfungsi seperti biasa.
Kemudian kami mula memulihkan WAF. Situasi adalah luar biasa, jadi kami menjalankan ujian negatif (bertanya kepada diri sendiri sama ada perubahan itu benar-benar masalah) dan ujian positif (memastikan pengembalian berfungsi) di satu bandar menggunakan trafik berasingan, memindahkan pelanggan yang membayar dari sana.
Pada 14:52 kami yakin bahawa kami memahami sebabnya dan membuat pembetulan, dan mendayakan WAF semula.
Bagaimana Cloudflare berfungsi
Cloudflare mempunyai pasukan jurutera yang berdedikasi untuk mengurus peraturan untuk WAF. Mereka berusaha untuk meningkatkan kadar pengesanan, mengurangkan positif palsu dan bertindak balas dengan cepat kepada ancaman baharu apabila ia muncul. Dalam 60 hari yang lalu, terdapat 476 permintaan perubahan yang diproses untuk peraturan terurus untuk WAF (purata satu setiap 3 jam).
Perubahan khusus ini perlu digunakan dalam mod simulasi, di mana trafik pelanggan sebenar melalui peraturan, tetapi tiada apa yang disekat. Kami menggunakan mod ini untuk menguji keberkesanan peraturan dan mengukur kadar positif palsu dan negatif palsu. Tetapi walaupun dalam mod simulasi, peraturan mesti benar-benar dilaksanakan, dan dalam kes ini peraturan itu mengandungi ungkapan biasa yang memakan terlalu banyak sumber pemproses.
Seperti yang anda boleh lihat daripada permintaan perubahan di atas, kami mempunyai pelan penggunaan, pelan rollback dan pautan kepada prosedur pengendalian standard dalaman (SOP) untuk jenis penggunaan ini. SOP untuk menukar peraturan membolehkannya diterbitkan secara global. Sebenarnya, di Cloudflare, perkara dilakukan dengan cara yang berbeza, dan SOP menetapkan bahawa kami mula-mula menghantar perisian untuk ujian dan penggunaan dalaman ke titik kehadiran dalaman (PoP) (yang digunakan oleh pekerja kami), kemudian kepada sebilangan kecil pelanggan dalam lokasi terpencil, kemudian kepada sejumlah besar pelanggan, dan kemudian ke seluruh dunia.
Beginilah rupanya. Kami menggunakan git secara dalaman melalui BitBucket. Jurutera yang bekerja pada perubahan menyerahkan kod, yang dibina kepada TeamCity, dan apabila binaan berlalu, penyemak diberikan. Sebaik sahaja permintaan tarik diluluskan, kod itu dipasang dan satu siri ujian dijalankan (sekali lagi).
Jika binaan dan ujian berjaya diselesaikan, permintaan perubahan dibuat dalam Jira dan pengurus atau ketua yang sesuai mesti meluluskan perubahan itu. Selepas kelulusan, penempatan berlaku ke dalam apa yang dipanggil "PoP menagerie": DOG, PIG dan (anjing, babi dan kenari).
DOG PoP ialah Cloudflare PoP (seperti setiap bandar kami yang lain) yang hanya digunakan oleh pekerja Cloudflare. PoP untuk kegunaan dalaman membolehkan anda menangkap masalah sebelum trafik pelanggan mula mengalir ke dalam penyelesaian. Perkara yang berguna.
Jika ujian DOG berjaya, kod bergerak ke peringkat PIG (guinea pig). Ini ialah Cloudflare PoP, di mana sejumlah kecil trafik pelanggan percuma mengalir melalui kod baharu.
Jika semuanya baik, kod itu masuk ke Canary. Kami mempunyai tiga Canary PoP di bahagian yang berbeza di dunia. Di dalamnya, trafik pelanggan berbayar dan percuma melalui kod baharu, dan ini adalah pemeriksaan terakhir untuk ralat.
Proses Keluaran Perisian di Cloudflare
Jika kod itu ok dalam Canary, kami mengeluarkannya. Melalui semua peringkat - DOG, PIG, Canary, seluruh dunia - mengambil masa beberapa jam atau hari, bergantung pada perubahan kod. Disebabkan oleh kepelbagaian rangkaian dan pelanggan Cloudflare, kami menguji kod secara menyeluruh sebelum mengeluarkannya secara global kepada semua pelanggan. Tetapi WAF tidak mengikuti proses ini secara khusus kerana ancaman perlu dijawab dengan cepat.
Ancaman WAF
Sejak beberapa tahun kebelakangan ini, terdapat peningkatan ketara dalam ancaman dalam aplikasi biasa. Ini disebabkan oleh ketersediaan alat ujian perisian yang lebih banyak. Sebagai contoh, kami baru-baru ini menulis tentang ).
Sumber:
Selalunya, bukti konsep dibuat dan segera diterbitkan di Github supaya pasukan yang menyelenggara aplikasi dapat mengujinya dengan cepat dan memastikan ia selamat dengan secukupnya. Oleh itu, Cloudflare memerlukan keupayaan untuk bertindak balas terhadap serangan baharu secepat mungkin supaya pelanggan mempunyai peluang untuk membetulkan perisian mereka.
Contoh hebat tindak balas pantas Cloudflare ialah penggunaan perlindungan kerentanan SharePoint pada bulan Mei (). Hampir sejurus selepas pengumuman dibuat, kami melihat sejumlah besar percubaan untuk mengeksploitasi kelemahan dalam pemasangan SharePoint pelanggan kami. Kakitangan kami sentiasa memantau ancaman baharu dan menulis peraturan untuk melindungi pelanggan kami.
Peraturan yang menyebabkan masalah pada hari Khamis sepatutnya melindungi daripada skrip rentas tapak (XSS). Serangan sedemikian juga menjadi lebih kerap dalam beberapa tahun kebelakangan ini.
Sumber:
Prosedur standard untuk menukar peraturan terurus untuk WAF ialah menjalankan ujian integrasi berterusan (CI) sebelum penggunaan global. Khamis lalu kami melakukan ini dan melancarkan peraturan. Pada jam 13:31 petang, seorang jurutera menyerahkan permintaan tarik yang diluluskan dengan perubahan.
Pada 13:37 TeamCity mengumpul peraturan, menjalankan ujian dan memberi kebenaran. Suite ujian WAF menguji fungsi teras WAF dan terdiri daripada sejumlah besar ujian unit untuk fungsi individu. Selepas ujian unit, kami menguji peraturan untuk WAF menggunakan sejumlah besar permintaan HTTP. Permintaan HTTP menyemak permintaan yang harus disekat oleh WAF (untuk memintas serangan) dan yang boleh dibenarkan (supaya tidak menyekat segala-galanya dan mengelakkan positif palsu). Tetapi kami tidak menguji penggunaan CPU yang berlebihan, dan memeriksa log binaan WAF sebelumnya menunjukkan bahawa masa pelaksanaan ujian peraturan tidak meningkat, dan sukar untuk mengesyaki bahawa tidak akan ada sumber yang mencukupi.
Ujian lulus dan TeamCity mula menggunakan perubahan secara automatik pada 13:42 p.m.
Quicksilver
Peraturan WAF memfokuskan pada pemulihan ancaman segera, jadi kami menggunakan ia menggunakan kedai nilai kunci teragih Quicksilver, yang menyebarkan perubahan secara global dalam beberapa saat. Semua pelanggan kami menggunakan teknologi ini apabila mereka menukar konfigurasi dalam papan pemuka atau melalui API, dan berkatnya kami bertindak balas terhadap perubahan dengan sepantas kilat.
Kami tidak bercakap banyak tentang Quicksilver. Sebelum ini kami gunakan sebagai kedai nilai kunci yang diedarkan secara global, tetapi terdapat masalah operasi dengannya, dan kami menulis kedai kami sendiri, direplikasi di lebih 180 bandar. Kami kini menggunakan Quicksilver untuk menolak perubahan konfigurasi kepada pelanggan, mengemas kini peraturan WAF dan mengedarkan kod JavaScript yang ditulis oleh pelanggan kepada Cloudflare Workers.
Ia hanya mengambil masa beberapa saat daripada mengklik butang pada papan pemuka atau memanggil API untuk membuat perubahan konfigurasi di seluruh dunia. Pelanggan menyukai kelajuan persediaan ini. Dan Pekerja memberikan mereka penggunaan perisian global yang hampir serta-merta. Secara purata, Quicksilver menyebarkan kira-kira 350 perubahan sesaat.
Dan Quicksilver sangat pantas. Secara purata, kami mencapai persentil ke-99 sebanyak 2,29 saat untuk menyebarkan perubahan kepada setiap komputer di seluruh dunia. Kelajuan biasanya merupakan perkara yang baik. Lagipun, apabila anda mendayakan fungsi atau mengosongkan cache, ia berlaku hampir serta-merta dan di mana-mana sahaja. Menghantar kod melalui Cloudflare Workers berlaku pada kelajuan yang sama. Cloudflare menjanjikan pelanggannya kemas kini pantas pada masa yang tepat.
Tetapi dalam kes ini, kelajuan memainkan jenaka yang kejam kepada kami, dan peraturan berubah di mana-mana dalam masa beberapa saat. Anda mungkin perasan bahawa kod WAF menggunakan Lua. Cloudflare menggunakan Lua secara meluas dalam pengeluaran dan butiran kita . Lua WAF menggunakan secara dalaman dan menggunakan backtracking untuk pemadanan. Ia tidak mempunyai mekanisme untuk melindungi daripada ekspresi yang tidak terkawal. Di bawah saya akan bercakap lebih lanjut mengenai perkara ini dan apa yang kita lakukan mengenainya.
Sebelum peraturan digunakan, segala-galanya berjalan lancar: permintaan tarik dibuat dan diluluskan, saluran paip CI/CD mengumpul dan menguji kod, permintaan perubahan telah diserahkan mengikut SOP yang mengawal penggunaan dan rollback, dan penggunaan telah selesai.
Proses Penyerahan Cloudflare WAF
Sesuatu telah berlaku
Seperti yang saya katakan, kami menggunakan berpuluh-puluh peraturan WAF baharu setiap minggu, dan kami mempunyai banyak sistem untuk melindungi daripada akibat negatif daripada penggunaan sedemikian. Dan apabila sesuatu berlaku, ia biasanya gabungan beberapa keadaan sekaligus. Jika anda mendapati hanya satu sebab, ini, sudah tentu, meyakinkan, tetapi ia tidak selalu benar. Ini adalah sebab yang bersama-sama membawa kepada kegagalan perkhidmatan HTTP/HTTPS kami.
- Seorang jurutera menulis ungkapan biasa yang boleh mengakibatkan berlebihan .
- Satu ciri yang boleh menghalang ungkapan biasa daripada membazir terlalu banyak CPU telah tersilap dialih keluar dalam pemfaktoran semula WAF beberapa minggu sebelumnyaβpemfaktoran semula diperlukan untuk menjadikan WAF menggunakan sumber yang lebih sedikit.
- Enjin ekspresi biasa tidak mempunyai jaminan kerumitan.
- Suite ujian tidak dapat mengesan penggunaan CPU yang berlebihan.
- SOP membenarkan perubahan peraturan tidak mendesak untuk dilancarkan secara global tanpa proses berbilang langkah.
- Pelan rollback memerlukan menjalankan binaan WAF penuh dua kali, yang mengambil masa yang lama.
- Makluman pertama tentang masalah trafik global dicetuskan terlalu lewat.
- Kami mengambil sedikit masa untuk mengemas kini halaman status.
- Kami menghadapi masalah untuk mengakses sistem kerana masalah, dan prosedur pintasan tidak ditetapkan dengan baik.
- Jurutera SRE kehilangan akses kepada beberapa sistem kerana kelayakan mereka tamat tempoh atas sebab keselamatan.
- Pelanggan kami tidak mempunyai akses kepada papan pemuka Cloudflare atau API kerana mereka melalui rantau Cloudflare.
Apa yang berubah sejak Khamis lalu
Mula-mula, kami menghentikan sepenuhnya semua kerja pada keluaran untuk WAF dan melakukan perkara berikut:
- Kami memperkenalkan semula perlindungan berlebihan CPU yang kami alih keluar. (sedia)
- Menyemak semua 3868 peraturan secara manual dalam peraturan terurus untuk WAF mencari dan membetulkan kes lain yang berpotensi untuk menjejak ke belakang yang berlebihan. (Pengesahan selesai)
- Kami menyertakan pemprofilan prestasi untuk semua peraturan dalam set ujian. (Dijangka: 19 Julai)
- Bertukar kepada enjin ekspresi biasa atau - kedua-duanya menyediakan jaminan masa jalan. (Dijangka: 31 Julai)
- Kami sedang menulis semula SOP untuk menggunakan peraturan secara berperingkat, seperti perisian lain dalam Cloudflare, tetapi pada masa yang sama mempunyai keupayaan untuk penempatan global kecemasan jika serangan telah bermula.
- Kami sedang membangunkan keupayaan untuk mengalih keluar papan pemuka dan API Cloudflare dengan segera daripada rantau Cloudflare.
- Mengautomatikkan kemas kini halaman .
Jangka panjang kita beralih daripada Lua WAF yang saya tulis beberapa tahun lalu. Memindahkan WAF ke . Dengan cara ini WAF akan menjadi lebih pantas dan menerima tahap perlindungan tambahan.
Kesimpulan
Kegagalan ini menyebabkan masalah kepada kami dan pelanggan kami. Kami bertindak pantas untuk membetulkan keadaan dan kini sedang mengusahakan kelemahan dalam proses yang menyebabkan ranap itu, serta menggali lebih mendalam untuk mengawal potensi masalah dengan ungkapan biasa pada masa hadapan apabila berhijrah kepada teknologi baharu.
Kami sangat malu dengan gangguan ini dan memohon maaf kepada pelanggan kami. Kami berharap perubahan ini akan memastikan perkara seperti ini tidak berlaku lagi.
Permohonan. Menjejak kembali ungkapan biasa
Untuk memahami bagaimana ungkapan:
(?:(?:"|'|]|}||d
(?:nan|infinity|true|false|null|undefined|symbol|math)|`|-
|+)+[)]*;?((?:s|-|~|!|{}||||+)*.*(?:.*=.*)))memakan semua sumber CPU, anda perlu tahu sedikit tentang cara enjin ekspresi biasa standard berfungsi. Masalahnya di sini ialah coraknya .*(?:.*=.*). (?: dan sepadan ) ialah kumpulan yang tidak menangkap (iaitu, ungkapan dalam kurungan dikumpulkan sebagai ungkapan tunggal).
Dalam konteks penggunaan CPU yang berlebihan, corak ini boleh digambarkan sebagai .*.*=.*. Dalam bentuk ini, corak kelihatan tidak perlu rumit. Tetapi yang lebih penting, dalam dunia nyata, ungkapan (seperti ungkapan kompleks dalam peraturan WAF) yang meminta enjin untuk memadankan serpihan diikuti dengan serpihan lain boleh membawa kepada penjejakan ke belakang yang membawa bencana. Dan itulah sebabnya.
Dalam ungkapan biasa . bermakna anda perlu memadankan satu watak, .* - padankan sifar atau lebih aksara "dengan rakus", iaitu, menangkap maksimum aksara, supaya .*.*=.* bermakna padankan sifar atau lebih aksara, kemudian padankan sifar atau lebih aksara, cari literal = aksara, padankan sifar atau lebih aksara.
Mari kita ambil garis ujian x=x. Ia sepadan dengan ungkapan .*.*=.*. .*.* sebelum tanda sama sepadan dengan yang pertama x (salah satu kumpulan .* sepadan dengan x, dan kedua - sifar aksara). .* selepas = perlawanan terakhir x.
Perbandingan ini memerlukan 23 langkah. Kumpulan pertama .* Π² .*.*=.* bertindak rakus dan sepadan dengan keseluruhan rentetan x=x. Enjin bergerak ke kumpulan seterusnya .*. Kami tidak mempunyai watak lagi untuk dipadankan, jadi kumpulan kedua .* sepadan dengan sifar aksara (ini dibenarkan). Kemudian enjin bergerak ke papan tanda =. Tiada lagi simbol (kumpulan pertama .* menggunakan keseluruhan ungkapan x=x), tiada perbandingan berlaku.
Dan kemudian enjin ekspresi biasa kembali ke permulaan. Dia bergerak ke kumpulan pertama .* dan membandingkannya Ρ x= (sebaliknya x=x), dan kemudian mengambil kumpulan kedua .*. Kumpulan kedua .* dibandingkan dengan yang kedua x, dan kami sekali lagi tidak mempunyai aksara yang tinggal. Dan apabila enjin mencapai semula = Π² .*.*=.*, tiada apa yang berkesan. Dan dia berundur semula.
Kali ini kumpulan .* masih sepadan x=, tetapi kumpulan kedua .* tidak lebih x, dan sifar aksara. Enjin cuba mencari watak literal = dalam corak .*.*=.*, tetapi tidak keluar (lagipun, kumpulan pertama telah pun mendudukinya .*). Dan dia berundur semula.
Kali ini kumpulan pertama .* hanya mengambil x pertama. Tetapi kumpulan kedua .* "tamak" menangkap =x. Adakah anda sudah meneka apa yang akan berlaku? Enjin cuba sepadan dengan literal =, gagal dan membuat satu lagi kemunduran.
Kumpulan pertama .* masih sepadan dengan yang pertama x... Yang kedua .* hanya mengambil =. Sudah tentu, enjin tidak boleh menandingi literal =, kerana kumpulan kedua telah melakukan ini .*. Dan sekali lagi berundur. Dan kami cuba memadankan rentetan tiga aksara!
Hasilnya, kumpulan pertama .* hanya sepadan dengan yang pertama x, kedua .* - dengan sifar aksara, dan enjin akhirnya sepadan dengan literal = dalam ungkapan Ρ = dalam barisan. Seterusnya ialah kumpulan terakhir .* dibandingkan dengan yang terakhir x.
23 langkah sahaja untuk x=x. Tonton video pendek tentang menggunakan Perl , yang menunjukkan cara langkah dan penjejakan ke belakang berlaku.
Ini sudah banyak kerja, tetapi bagaimana jika sebaliknya x=x kita akan mempunyai x=xx? Itu 33 langkah. Dan jika x=xxx? 45. Hubungan itu tidak linear. Graf menunjukkan perbandingan daripada x=x kepada x=xxxxxxxxxxxxxxxxxxxx (20 x selepas =). Jika kita mempunyai 20 x selepas =, enjin melengkapkan padanan dalam 555 langkah! (Lebih-lebih lagi, jika kita telah kalah x= dan rentetan hanya terdiri daripada 20 x, enjin akan mengambil 4067 langkah untuk memahami bahawa tiada padanan).
Video ini menunjukkan semua kemunduran untuk perbandingan x=xxxxxxxxxxxxxxxxxxxx:
Masalahnya ialah apabila saiz rentetan bertambah, masa padanan bertambah secara super-linear. Tetapi keadaan boleh menjadi lebih teruk jika ungkapan biasa diubah suai sedikit. Katakan kita ada .*.*=.*; (iaitu, terdapat koma bertitik literal di hujung corak). Contohnya, untuk memadankan ungkapan seperti foo=bar;.
Dan di sini mundur akan menjadi bencana sebenar. Sebagai perbandingan x=x ia akan mengambil 90 langkah, bukan 23. Dan jumlah itu berkembang dengan cepat. Untuk membandingkan x= dan 20 x, 5353 langkah diperlukan. Inilah cartanya. Lihat nilai paksi Y berbanding carta sebelumnya.
Jika anda berminat, lihat kesemua 5353 langkah padanan yang gagal x=xxxxxxxxxxxxxxxxxxxx ΠΈ .*.*=.*;
Dengan menggunakan padanan malas dan bukannya tamak, tahap kemunduran boleh dikawal. Jika kita menukar ungkapan asal kepada .*?.*?=.*?, sebagai perbandingan x=x ia akan mengambil 11 langkah (bukan 23). Untuk x=xxxxxxxxxxxxxxxxxxxx... Semuanya kerana ? selepas .* memberitahu enjin untuk memadankan bilangan minimum aksara sebelum meneruskan.
Tetapi pemetaan malas tidak menyelesaikan sepenuhnya masalah backtracking. Jika kita menggantikan contoh malapetaka .*.*=.*; pada .*?.*?=.*?;, masa pelaksanaan akan kekal sama. x=x masih memerlukan 555 langkah, dan x= dan 20 x - 5353.
Satu-satunya perkara yang boleh dilakukan (selain menulis semula corak sepenuhnya untuk kekhususan yang lebih besar) ialah meninggalkan enjin ekspresi biasa dengan mekanisme penjejakan belakangnya. Inilah yang akan kami lakukan dalam beberapa minggu akan datang.
Penyelesaian kepada masalah ini telah diketahui sejak 1968, apabila Kent Thompson menulis artikel (βKaedah Pengaturcaraan: Algoritma Carian Ungkapan Biasaβ). Artikel ini menerangkan mekanisme yang membolehkan anda menukar ungkapan biasa kepada mesin keadaan terhingga bukan deterministik, dan selepas perubahan keadaan dalam mesin keadaan terhingga bukan deterministik, gunakan algoritma yang masa pelaksanaannya bergantung secara linear pada rentetan yang dipadankan.
Kaedah Pengaturcaraan
Algoritma Carian Ungkapan Biasa
Ken Thompson
Bell Telephone Laboratories, Inc., Murray Hill, New JerseyIa menerangkan kaedah untuk mencari rentetan aksara tertentu dalam teks dan membincangkan pelaksanaan kaedah ini dalam bentuk pengkompil. Pengkompil mengambil ungkapan biasa sebagai kod sumber dan menghasilkan program IBM 7094 sebagai kod objek. Program objek mengambil input dalam bentuk teks carian dan mengeluarkan isyarat setiap kali rentetan teks dipadankan dengan ungkapan biasa yang diberikan. Artikel tersebut memberikan contoh, masalah dan penyelesaian.
Algoritma
Algoritma carian sebelumnya mengakibatkan penjejakan ke belakang jika carian yang sebahagiannya berjaya gagal menghasilkan hasil.Dalam mod penyusunan, algoritma tidak berfungsi dengan simbol. Ia menghantar arahan kepada kod yang disusun. Pelaksanaan adalah sangat pantas - selepas menghantar data ke bahagian atas senarai semasa, ia secara automatik mencari semua kemungkinan aksara berturut-turut dalam ungkapan biasa.
Algoritma kompilasi dan carian disertakan dalam editor teks perkongsian masa sebagai carian kontekstual. Sudah tentu, ini jauh dari satu-satunya aplikasi prosedur carian sedemikian. Sebagai contoh, varian algoritma ini digunakan sebagai carian simbol dalam jadual dalam pemasang.
Diandaikan bahawa pembaca sudah biasa dengan ungkapan biasa dan bahasa pengaturcaraan komputer IBM 7094.Penyusun
Pengkompil terdiri daripada tiga peringkat berjalan selari. Peringkat pertama ialah penapisan sintaks, yang membenarkan hanya ungkapan biasa yang betul secara sintaksis untuk dilalui. Langkah ini juga memasukkan operator "Β·" untuk memadankan ungkapan biasa. Dalam langkah kedua, ungkapan biasa ditukar kepada bentuk postfix. Pada peringkat ketiga, kod objek dicipta. 2 peringkat pertama adalah jelas, dan kami tidak akan memikirkannya.
Artikel Thompson tidak bercakap tentang mesin keadaan terhingga tidak tentu, tetapi ia menerangkan algoritma masa linear dengan baik dan membentangkan program ALGOL-60 yang menjana kod bahasa pemasangan untuk IBM 7094. Pelaksanaannya adalah rumit, tetapi ideanya sangat mudah.
laluan carian semasa. Ia diwakili oleh ikon β dengan satu input dan dua output.
Rajah 1 menunjukkan fungsi langkah kompilasi ketiga apabila mengubah contoh ungkapan biasa. Tiga aksara pertama dalam contoh ialah a, b, c, dan setiap satu mencipta entri tindanan S[i] dan medan NNODE.NNODE kepada kod sedia ada untuk menjana ungkapan biasa yang terhasil dalam satu entri tindanan (lihat Rajah 5)
Beginilah rupa ungkapan biasa .*.*=.*, jika anda bayangkan seperti dalam gambar dari artikel Thompson.
Dalam Rajah. 0 terdapat lima keadaan bermula dari 0, dan 3 kitaran yang bermula dari keadaan 1, 2 dan 3. Ketiga kitaran ini sepadan dengan tiga .* dalam ungkapan biasa. 3 bujur dengan titik sepadan dengan satu simbol. Bujur dengan tanda = sepadan dengan watak literal =. Negeri 4 adalah muktamad. Jika kita mencapainya, maka ungkapan biasa dipadankan.
Untuk melihat bagaimana rajah keadaan sedemikian boleh digunakan untuk padanan ungkapan biasa .*.*=.*, kita akan melihat padanan rentetan x=x. Program ini bermula dari keadaan 0, seperti yang ditunjukkan dalam Rajah. 1.
Untuk algoritma ini berfungsi, mesin keadaan mesti berada dalam beberapa keadaan serentak. Mesin terhingga bukan deterministik akan membuat semua peralihan yang mungkin secara serentak.
Sebelum ia mempunyai masa untuk membaca data input, ia masuk ke kedua-dua keadaan pertama (1 dan 2), seperti yang ditunjukkan dalam Rajah. 2.
Dalam Rajah. 2 menunjukkan apa yang berlaku apabila dia melihat pada yang pertama x Π² x=x. x boleh memetakan ke titik teratas, pergi dari negeri 1 dan kembali ke negeri 1. Atau x boleh memetakan ke titik di bawah, pergi dari negeri 2 dan kembali ke negeri 2.
Selepas memadankan yang pertama x Π² x=x kami masih di negeri 1 dan 2. Kami tidak dapat mencapai negeri 3 atau 4 kerana kami memerlukan watak literal =.
Algoritma kemudian mempertimbangkan = Π² x=x. Seperti x sebelum itu, ia boleh dipadankan dengan salah satu daripada dua gelung teratas dari keadaan 1 ke keadaan 1 atau dari keadaan 2 ke keadaan 2, tetapi algoritma boleh memadankan literal = dan bergerak dari keadaan 2 ke keadaan 3 (dan serta-merta 4). Ini ditunjukkan dalam Rajah. 3.
Algoritma kemudian bergerak ke yang terakhir x Π² x=x. Dari keadaan 1 dan 2 peralihan yang sama mungkin kembali ke keadaan 1 dan 2. Dari keadaan 3 x boleh memadankan titik di sebelah kanan dan kembali ke keadaan 3.
Pada peringkat ini, setiap watak x=x dipertimbangkan, dan kerana kita telah mencapai keadaan 4, ungkapan biasa sepadan dengan rentetan itu. Setiap aksara diproses sekali, jadi algoritma ini adalah linear dalam panjang rentetan input. Dan tidak berundur.
Jelas sekali, selepas mencapai keadaan 4 (apabila algoritma telah dipadankan x=) keseluruhan ungkapan biasa dipadankan, dan algoritma boleh ditamatkan tanpa mengambil kiranya sama sekali x.
Algoritma ini bergantung secara linear pada saiz rentetan input.
Sumber: www.habr.com