ReDoS: Ketika Regex Jadi Senjata Makan Tuan

Regex yang terlihat sederhana kadang bisa bikin server hang berjam-jam. Penyebabnya: catastrophic backtracking — engine regex mencoba semua kombinasi alternatif sampai kehabisan tenaga. Serangan yang eksploitasi ini disebut ReDoS (Regular expression Denial of Service).

Apa Itu Backtracking?

Ketika regex gagal match di suatu posisi, engine "mundur" dan mencoba jalur alternatif. Untuk pattern simpel ini prosesnya cepat. Tapi kalau ada nested quantifier (quantifier di dalam quantifier), jumlah jalur bisa tumbuh eksponensial.

Contoh Klasik: (a+)+$

const evil = /^(a+)+$/;

evil.test("aaaaaaaaaaaaaaaaaaaaaaaaaaa!");
// Input 27 karakter "a" diikuti "!" yang bikin gagal match.
// Engine harus coba 2^27 = ~134 juta jalur. CPU langsung spike ke 100%.

Pattern (a+)+ ambigu: 4 huruf a bisa dipartisi sebagai (aaaa), (aaa)(a), (aa)(aa), (a)(aaa), (aa)(a)(a), dst. Setiap kali gagal di ujung, engine mundur dan coba partisi lain.

Pola Berbahaya yang Perlu Dikenali

Heuristik: Kalau regex punya (X+)+, (X*)*, atau (X\|Y)+ di mana X dan Y bisa match substring yang sama → waspada.

Cara Deteksi

• regex101.com dengan mode debug menampilkan jumlah step yang engine pakai. Kalau step count meledak untuk input ~20 karakter, regexmu rentan.
• safe-regex (npm) — detektor heuristik sederhana.
• vuln-regex-detector — detektor yang lebih canggih berbasis research.

Mitigasi

1. Ganti nested quantifier dengan character class

// ❌ Rentan: nested quantifier
const bad = /^(\w+)+$/;

// ✅ Aman: character class langsung
const good = /^\w+$/;

2. Batasi panjang input sebelum regex

if (input.length > 1000) throw new Error("Input terlalu panjang");
userRegex.test(input);

3. Gunakan engine linear-time

• RE2 (Google) — dipakai Go regexp, tidak punya backreferences dan lookbehind, tapi dijamin linear O(n).
• Hyperscan (Intel) — optimized untuk network-level regex.
• Di JavaScript: gunakan re2 package via native binding.

4. Bounded quantifier

// ❌ Unbounded: bisa diserang dengan input panjang
/^\w+@\w+\.\w+$/;

// ✅ Bounded: batas wajar
/^\w{1,64}@\w{1,64}\.\w{2,10}$/;

5. Possessive quantifier & atomic group (PCRE, bukan JS)

Di PHP/Java: (a++)+ possessive, tidak mundur. Atomic group (?>a+) juga mencegah backtracking. JavaScript belum support — pakai mitigasi lain.

Kasus Nyata

• Stack Overflow, Juli 2016: Situs down 34 menit karena regex validasi posting dengan pattern /^[\s\u200c]+\|[\s\u200c]+$/ kena ReDoS di post 20KB.
• Cloudflare, Juli 2019: Outage global ~27 menit karena WAF regex dengan pattern .*(?:.*=.*). CPU semua edge server spike ke 100%.
• Node.js CVE-2017-16021: Regex di mime library rentan ReDoS.

Intinya: jangan pernah pakai user input langsung ke regex engine. Selalu validasi panjang, pakai pattern non-ambiguous, dan kalau ragu — gunakan RE2.

🎭 Analogi sehari-hari: ReDoS = bom waktu yang tertanam di kode. Pattern terlihat baik di test, tapi dengan input yang tepat = server hang berjam-jam. Bayangkan satpam yang tugasnya cek nama tamu dari daftar 100 nama. Cepet. Tapi kalau tamunya bawa surat 27 halaman dengan banyak interpretasi ambigu, satpam bingung coba semua kombinasi cara baca = lumpuh.

💡 Cloudflare 2019 outage: Cloudflare WAF (web application firewall) deploy regex .*(?:.*=.*). Pattern keliatan harmless. Tapi kena input tertentu → 27 menit global outage karena CPU edge servers spike 100%. Ini ReDoS di production scale. Bukan teori — terjadi nyata.

⚠️ Pattern berbahaya yang harus dihindari:

• Nested quantifier: (a+)+, (a*)*, (a+b?)+
• Overlapping alternation: (a|a)+, (a|ab)+
• Multiple greedy: .*.*.*
• Optional in repetition: (\d?)+
• (\w+)+@ — ambigu, bisa partition aaa@ macam-macam

🎯 ReDoS prevention checklist:

1. Audit regex dengan tool: https://devina.io/redos-checker atau https://makenowjust-labs.github.io/recheck/
2. Bounded quantifier — \w{1,64} bukan \w+ untuk user input
3. Length limit sebelum regex apply: if (input.length > 1000) reject
4. Pakai RE2 kalau possible (Go bawaan, JS via re2 npm package)
5. Avoid nested quantifier completely di production
6. Timeout regex execution (di Java pakai Matcher.region(), di Node pakai worker thread)
7. Static analysis tools (CodeQL, ESLint plugin redos)

🧪 Test ReDoS suspicion: Input panjang berulang gagal di akhir. Contoh: "a".repeat(30) + "!". Kalau regex hang > 1 detik = ReDoS confirmed.

TL;DR: ReDoS = catastrophic backtracking. Nested quantifier = death sentence. Production deploy real outage (Cloudflare, Stack Overflow). Audit regex, bounded quantifier, length limit input, RE2 untuk user-facing. Jangan pernah trust user input ke regex engine tanpa safeguard.