ReDoS — regex 30 karakter yang bisa bikin server kena 100% CPU

Isi

Regex engine kebanyakan (PCRE, JavaScript, Python re, Java) pakai backtracking. Artinya kalau satu jalur gagal, dia mundur dan coba jalur lain. Masalahnya: kalau pola punya nested quantifier, jumlah jalur yang dicoba tumbuh eksponensial — bukan linear — terhadap panjang input.

Contoh klasik:

^(\w+\s?)*$

Coba input normal "hello world" → cepat. Coba input jahat: "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa!" (30 a lalu !). Engine bakal coba semua cara membagi 30 a ke dalam grup berulang. Jumlah kombinasinya ~2³⁰ ≈ 1 miliar. Server hang beberapa detik sampai menit, dari satu request. Ini DoS tanpa perlu botnet.

Kenapa (\w+\s?)* berbahaya: \w+ dan \s? bisa sama-sama match karakter yang sama dalam banyak cara berbeda, jadi ada banyak "pembagian" valid yang harus dicoba ulang saat $ gagal.

Pola yang perlu dicurigai (bukan otomatis salah, tapi cek):

Kasus nyata (terdokumentasi, bukan karangan): - Cloudflare, 2 Juli 2019 — outage global ~27 menit. Penyebab: satu rule WAF berisi regex yang backtracking-nya meledak, CPU seluruh edge node kena 100%. - Stack Overflow, 2016 — outage karena regex di parser komentar yang catastrophic di input tertentu.

Dua-duanya bukan serangan. Itu bug di kode sendiri yang baru ketahuan saat input kebetulan pas.

Cara mitigasi, urut dari paling murah:

1. Batasi panjang input sebelum regex jalan. Kalau field cuma butuh 50 karakter, tolak 10.000 karakter di depan. Ini menutup 80% kasus.
2. Sederhanakan pola. ^(\w+\s?)*$ bisa diganti ^\w+(\s\w+)*$ — tidak ada overlap, tidak ada backtracking eksplosif.
3. Pakai engine linear-time kalau regex-nya dari user/config: RE2 (Go, google/re2 untuk C++), re2 npm package, atau Rust regex crate. Engine ini tidak punya backtracking sama sekali, jadi ReDoS mustahil — trade-off: tidak support backreference dan lookaround.
4. Kasih timeout / jalankan di worker terpisah. Node tidak punya regex timeout native; solusinya worker thread dengan terminate(), atau pindah ke re2.
5. Validasi manual untuk hal sederhana. Email, nomor telepon, URL — sering lebih aman pakai parser/library daripada regex buatan sendiri.

Satu hal yang bisa langsung dipakai

Tes regex production-mu sekarang, sebelum ada yang nemuin:

# pola + input jahat, ukur waktunya
time node -e "/(\w+\s?)+\$/.test('a'.repeat(28)+'!')"

Kalau selesai > 1 detik, itu sudah lampu merah. Untuk Python:

python3 -c "import re,time;t=time.time();re.match(r'(\w+\s?)+$','a'*28+'!');print(time.time()-t)"

Naikkan angka 28 sedikit demi sedikit. Kalau waktunya dobel tiap +1 karakter, itu tanda eksponensial murni — bukan cuma "lambat".

Takeaway

Regex yang lambat bukan regex yang jelek — regex yang lambat adalah bug keamanan. Kalau quantifier-nya bersarang, panjang input adalah remote control ke CPU server-mu.