Menulis pola aman ReDoS

ReDoS (Regular Expression Denial of Service) adalah kelas serangan yang mana masukan yang dibuat dengan cermat membuat waktu pencocokan regex meledak. Mesin JS menggunakan backtracking: jika suatu pola "ambigu", pada sebuah masukan yang tidak beruntung, ia dapat melakukan sejumlah percobaan secara eksponensial.

Pola bencana klasik

Pattern: ^(a+)+$
Input:   "aaaaaaaaaaaaaaaaaaaaab"

Agar cocok, mesin mencoba setiap kemungkinan partisi "a" di antaranya dua bilangan +. Pada 20 "a", itu berarti 2^20 = ~1 juta percobaan. Pada 30 "a", satu miliar.

Contoh berbahaya lainnya:

• (a*)*b -- "bintang bersarang".
• (a|a)* -- alternatif yang tumpang tindih.
• (\w+)+@ -- kelompok serakah dengan bilangan luar.

Bagaimana mengenali bahayanya

Carilah struktur ini:

1. Penghitung di dalam pembilang: (...+)+, (...*)*, (...{n,})+.
2. Alternatif yang tumpang tindih di bawah pembilang: (a|ab)*, (\w|\d)+.
3. Melihat ke depan/melihat ke belakang dengan alternatif yang kompleks diulangi.

Penulisan ulang yang defensif

Dangerous:  ^(\w+\s+)+$
Safe:       ^(?:\w+\s+)*\w+$

Versi aman memisahkan kasus dasar dari kasus berulang, dan menghapusnya ambiguitas. Teknik lainnya:

• Bilangan posesif (a++) -- tidak didukung di JS, namun tersedia di mesin lain.
• Pola atom ((?>...)) -- tidak di JS.
• Batasi panjang input sebelum mencocokkan.
• Batas waktu pada pencocokan (editor kursus ini menggunakan pekerja dengan batas waktu 500 ms).

Rekomendasi untuk pola aman ReDoS

1. Pastikan opsi dalam pergantian saling eksklusif (misalnya, jangan gunakan (a|a+)).
2. Hindari menerapkan bilangan bertingkat pada ekspresi yang tumpang tindih (misalnya (\\s*)*).
3. Selalu lebih memilih kelas karakter tertentu yang dinegasikan ([^\\n]*) daripada titik wildcard generik (.*).

Cobalah

Tinjau latihan

Tantangan tambahan