Cara Menghindari Catastrophic Backtracking dalam Regex?

Catastrophic Backtracking dari ekspresi reguler mengacu pada fakta bahwa ekspresi reguler melakukan backtracking terlalu banyak saat mencocokkan, menyebabkan CPU 100% dan memblokir layanan normal.

Latar Belakang

Saya telah membaca sebuah artikel yang merinci proses penemuan dan penyelesaian dari backtrace reguler yang menyebabkan CPU 100%. Artikel aslinya cukup panjang, dan saya telah mengalami masalah serupa dua kali sebelumnya dalam pengembangan OpenResty.

Berikut adalah ringkasan singkatnya agar Anda tidak perlu menghabiskan waktu untuk latar belakang.

Mesin regularisasi untuk sebagian besar bahasa pengembangan diimplementasikan menggunakan NFA berbasis backtracking (bukan berdasarkan NFA Thompson).
catastrophic backtracking dengan CPU 100% jika ada terlalu banyak backtracking.
perlu menganalisis dump dengan gdb, atau systemtap untuk melacak lingkungan online.
Masalah seperti ini sulit dideteksi sebelum kode diluncurkan dan memerlukan tinjauan kasus per kasus terhadap ekspresi reguler.

Dari sudut pandang pengembangan, memperbaiki ekspresi reguler yang bermasalah adalah akhir dari cerita. Paling banyak, tambahkan mekanisme keamanan untuk membatasi jumlah backtracking, seperti ini di OpenResty.

lua_regex_match_limit 100000;

Dengan cara ini, bahkan jika ada catastrophic backtracking, itu akan dibatasi dan tidak akan menjalankan CPU penuh.

Nah, apakah ini sudah terlihat sempurna? Mari kita melampaui tingkat pengembangan dan melihat ini dari dimensi yang berbeda.

Penyerang

Cukup gunakan satu mesin, kirim permintaan, Anda dapat menjatuhkan server di sisi lain, ini adalah senjata nuklir impian seorang peretas. Dibandingkan dengan ini, apa itu DDoS lemah, gerakannya besar dan mahal.

Serangan ini juga memiliki namanya sendiri: ReDoS (RegEx Denial of Service).

Karena ekspresi reguler sangat banyak digunakan dan ada di hampir setiap bagian layanan backend, ada peluang untuk memanfaatkannya dengan menemukan salah satu kerentanannya.

Bayangkan skenario di mana seorang peretas menemukan kerentanan ReDoS di WAF dan mengirim permintaan untuk menjatuhkan WAF; Anda tidak dapat menemukan masalah dalam waktu singkat, bahkan tidak menyadari bahwa ini adalah serangan; Anda memilih untuk me-restart atau sementara mematikan WAF untuk menjaga bisnis Anda tetap berjalan; sementara WAF tidak berfungsi, peretas menggunakan SQL injection untuk mencuri database Anda. Anda, di sisi lain, mungkin masih sama sekali tidak menyadarinya.

Karena penggunaan luas perangkat lunak sumber terbuka dan layanan cloud, tidak cukup hanya memastikan bahwa ekspresi reguler yang Anda tulis bebas dari kerentanan. Itu topik lain, kita akan mulai di sini hanya dengan membahas ekspresi reguler yang berada dalam kendali kita sendiri.

Bagaimana menemukan ekspresi reguler seperti itu?

Langkah pertama dalam menyelesaikan masalah adalah menemukannya, dan mencoba menemukan semuanya, juga dikenal sebagai kemampuan untuk menemukannya dengan aman.

Mengharapkan tinjauan kode manual untuk menemukan aturan yang bermasalah tidak dapat diandalkan. Sebagian besar pengembang tidak memiliki kesadaran keamanan, dan bahkan jika mereka mencari, kecil kemungkinan mereka dapat menemukan masalah dalam ekspresi reguler yang kompleks.

Di sinilah alat otomatisasi berguna.

Kami memiliki dua metode otomatis berikut untuk menyelesaikan ini.

Pengujian statis

Alat seperti ini dapat memindai kode untuk ekspresi reguler dan, menurut algoritma tertentu, menemukan ekspresi reguler dengan catastrophic backtracking dari mereka.

Misalnya, RXXR2, yang diimplementasikan berdasarkan algoritma dalam makalah yang mengubah ekspresi reguler menjadi ε-NFA dan kemudian mencarinya, tetapi tidak mendukung sintaks ekstensi ekspresi reguler, sehingga akan ada laporan yang terlewat.

Fuzzing dinamis

Tes fuzz adalah metode pengujian perangkat lunak umum yang mendeteksi crash perangkat lunak, kebocoran memori, dan masalah lainnya dengan memasukkan banyak data acak dalam waktu yang lama.

Demikian pula, kita dapat menggunakan pendekatan ini dalam tes reguler. Kita dapat menghasilkan data uji berdasarkan ekspresi reguler yang ada, atau kita dapat menghasilkan data uji sepenuhnya secara acak.

SlowFuzz adalah salah satu alat sumber terbuka, juga berdasarkan implementasi algoritma dari sebuah makalah, makalah akan dicantumkan di akhir tulisan ini, ini adalah alat serbaguna, dan tidak melakukan pemrosesan untuk struktur ekspresi reguler, sehingga akan ada laporan yang terlewat.

SDLFuzzer adalah alat deteksi ReDoS khusus yang dikembangkan oleh Microsoft beberapa tahun yang lalu, tetapi tidak lagi dikelola.

Tidak banyak alat yang dapat dipilih di bidang ini, dan tidak banyak perhatian. Namun, saya senang menemukan makalah tentang ReDoS oleh beberapa guru dan PhD dari Universitas Nanjing selama pencarian informasi, dan mengopen-source alat ReScue bersama dengan makalah: https://2bdenny.github.io/ReScue/. Alat ini telah mengidentifikasi kerentanan ReDoS di beberapa proyek sumber terbuka.

Berikut adalah hasil tes perbandingan dalam makalah.

Bisakah ini diselesaikan sekali dan untuk selamanya?

Bahkan jika kita menggunakan alat seperti itu, pasti akan ada alarm palsu dan alarm yang terlewat, jadi apakah ada cara sekali dan untuk selamanya untuk menyelesaikan ReDoS?

Maka kita harus kembali ke akar masalah untuk menemukan jawabannya: mesin reguler menggunakan backtracking untuk mencocokkan.

Tidakkah akan baik jika kita meninggalkan pendekatan ini? Ya, sudah ada cukup banyak implementasi lain dari mesin reguler yang dapat menyelesaikan masalah ini sekali dan untuk selamanya. Mereka semua meninggalkan backtracking dan menggunakan pendekatan automaton NFA/DFA untuk mengimplementasikan, keuntungannya adalah cocok untuk pencocokan streaming dan juga lebih aman, kerugiannya adalah tidak mendukung banyak sintaks ekstensi ekspresi reguler, seperti backreferences, yah ini umumnya juga tidak digunakan.

Google RE2

RE2 Google adalah salah satu proyek sumber terbuka yang lebih lengkap. Ini mendukung sebagian besar sintaks PCRE, dan ada implementasi perpustakaan untuk Go, Python, Perl, Node.js, dan bahasa pengembangan lainnya, biaya awal dan penggantian sangat rendah.

Mari kita ambil Perl sebagai contoh dan lihat apakah RE2 dapat menghindari masalah catastrophic backtracking.

Mari kita lihat grafik perbandingan hasil ini.

Kodenya adalah sebagai berikut, Anda dapat mencobanya sendiri jika tertarik.

time perl -e 'if ("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" =~ /a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa/) {print("hit");}'

40.80s user 0.00s system 99% cpu 40.800 total

Dibutuhkan 40,8 detik untuk menjalankan ekspresi reguler ini, selama waktu itu CPU adalah 99%.

Dengan RE2, kontrasnya sangat jelas.

time perl -e 'use re::engine::RE2; if ("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" =~ /a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa/) {print(" hit");}'

perl -e 0.00s user 0.00s system 34% cpu 0.011 total

Intel Hyperscan

Intel Hyperscan juga merupakan mesin reguler yang mirip dengan RE2, dan ada perpustakaan untuk Perl, Python, dan bahasa lainnya, sehingga tidak terlalu sulit untuk memulai.

Hanya sesuai dengan praktik Intel, lebih banyak mengikat platform, hanya dapat berjalan di x86.

Jika ada manfaat unik, mungkin kemampuan untuk bekerja lebih baik dengan set instruksi dan perangkat keras Intel, dengan peningkatan kinerja, seperti menggabungkannya dengan DPDK sendiri.

Snort, alat deteksi intrusi jaringan sumber terbuka, juga menggunakan Hyperscan untuk menggantikan mesin reguler sebelumnya, sehingga siswa yang familiar dengan Snort dapat mencobanya.

Ekstensi

Berikut adalah beberapa makalah tentang ekspresi reguler, yang dapat dibaca sebagai ekstensi jika Anda tertarik.

SlowFuzz: Automated Domain-Independent Detection of Algorithmic Complexity Vulnerabilities: https://arxiv.org/pdf/1708.08437.pdf
Static Analysis for Regular Expression Exponential Runtime via Substructural Logics: https://arxiv.org/abs/1405.7058.pdf
ReScue: Crafting Regular Expression DoS Attacks: https://dl.acm.org/doi/10.1145/3238147.3238159
Regular Expression Matching Can Be Simple And Fast: https://swtch.com/~rsc/regexp/regexp1.html