Menjaga input pengguna dari ekspresi reguler terhadap serangan

9

Saya mengetahui penolakan layanan ekspresi reguler (ReDoS). Apakah ada cara yang masuk akal untuk memungkinkan pengguna membuat regex khusus sambil memastikan bahwa mereka tidak mengirimkan pola yang lambat secara eksponensial?

regular-expressions icirellik
sumber
Anda kurang detail. Platform, penggunaan, dll.
whatsisname
8
Alih-alih mencoba menghindari pengguna yang mengirimkan regex buruk, mungkin solusi di mana setelah jangka waktu tertentu Anda membatalkan eksekusi?
Samuel

Jawaban:

8

Masalah dengan ekspresi reguler bukanlah regex itu sendiri, tetapi bahwa mesin regex yang memiliki semua jenis fitur "nyaman" seperti mundur. Karena itu, menggunakan mesin regex tanpa fitur-fitur ini menghindari.

Ekspresi reguler konsep ilmu komputer selalu dapat dicocokkan dalam waktu linier setelah mereka dikompilasi ke mesin keadaan terbatas. Jadi mesin regex berbasis mesin negara tidak dapat digunakan untuk ReDoS. Namun, mesin negara yang diperlukan mungkin menjadi agak besar dalam contoh patologis. Tetapi membatasi memori yang tersedia cenderung lebih mudah daripada membatasi waktu komputasi yang tersedia.

Mesin RE2 dikembangkan secara khusus untuk menangani regex yang tidak terpercaya dan dirancang untuk eksekusi linear-time.

Alternatif lain adalah merakit regex sendiri dari notasi yang disederhanakan. Misalnya, Anda mungkin mengizinkan pengguna menggunakan pola glob (seperti *.txt). Anda kemudian dapat menguraikannya dengan cara yang mencegah backtracking, misalnya dengan melarang bersarang dan hanya menggunakan quantifier serakah. Untuk banyak kasus penggunaan, notasi pola yang disederhanakan sepenuhnya memadai.

amon
sumber
11

Menganalisis ekspresi reguler untuk melihat apakah akan lambat atau tidak, tanpa analisis menjadi lambat itu sendiri , sama dengan memecahkan masalah yang berhenti. Dengan kata lain, tidak mungkin menemukan solusi yang benar dan lengkap.

Anda dapat, tentu saja, menemukan solusi yang benar dan di lengkap. Misalnya, Anda dapat bekerja dengan daftar putih terbatas fitur yang aman digunakan (mis. Kelas karakter ya, tidak ada pengulangan ...). Ini akan memungkinkan Anda untuk melewati banyak regex tidak kritis, menolak semua yang kritis, dan (salah) menolak beberapa yang baik-baik saja, tetapi terlalu rumit untuk membuktikan aman secara otomatis.

Kilian Foth
sumber
3
Apakah Anda memiliki kutipan untuk pernyataan pertama Anda? Saya akan tertarik melihat bukti seperti itu. Regex tidak menyelesaikan-Turing, sehingga masalah penghentian mungkin tidak berlaku.
Sebastian Redl
3
@SebastianRedl Memang benar bahwa, ekspresi reguler tidak menyelesaikan Turing, tetapi semua pustaka regex yang digunakan populer memiliki ekstensi yang membuatnya tidak lagi teratur. Membatasi pengguna untuk secara harfiah ekspresi reguler bisa, pada kenyataannya, menjadi solusi yang baik untuk situasi ini.
Kilian Foth
2
@KilianFoth: IIRC, bahkan ekspresi reguler yang benar (dalam arti kata CompSci) dapat memerlukan jumlah eksponensial backtracking. Tetapi karena mereka tidak menyelesaikan Turing, untuk regex mana pun secara teori dimungkinkan untuk menetapkan batas atas ini. Namun, ini meninggalkan dua masalah: menentukan batas atas secara otomatis adalah tugas yang tidak sepele, dan hasilnya dapat memberikan hasil yang terlalu tinggi (seperti, batas atas jauh lebih tinggi dari waktu yang diharapkan ).
MSalters
@memisahkan setiap ekspresi reguler yang benar secara mekanis dapat dikonversi menjadi otomat keadaan terbatas deterministik, yaitu selalu memungkinkan untuk mencocokkan ekspresi tanpa mengulangi sama sekali. FSA Anda mungkin menjadi terlalu besar, tentu saja, tetapi itu menunjukkan bahwa batas jumlah negara dalam FSA yang dihasilkan adalah solusi yang cukup untuk mencegah serangan yang dimaksud.
Jules
1

Sebagai penulis re parser untuk proyek lazarus saya akan mengatakan tidak ada cara untuk memahami ekspresi reguler yang diberikan sumber daya apa yang akan dikonsumsi pada teks yang diberikan.

Tanpa menghabiskan sumber daya yang sama yang saya maksud (setidaknya dalam arti besar-O).

Jadi pendekatan terbaik - jalankan kembali parser di utas terpisah dan bunuh setelah waktu habis.

ANDgineer
sumber
0

Selain jawaban lain, solusi mungkin juga untuk menggulung perpustakaan regex Anda sendiri, yang memungkinkan instrumentasi kinerja selama eksekusi, dan dengan demikian menyediakan sarana untuk membunuh eksekusi setengah jalan jika beberapa kriteria terpenuhi.

Demikian pula, Anda bisa menjalankan regex di utas lain dan membunuh utas jika terlalu lama.

Apa namanya
sumber