ReDoS & Catastrophic Backtracking — Regex

ReDoS: Ketika Regex Jadi Senjata Makan Tuan Regex yang terlihat sederhana kadang bisa bikin server hang berjam-jam. Penyebabnya: catastrophic backtracking —…

ReDoS (Regular expression Denial of Service) terjadi saat satu regex butuh waktu sangat lama untuk satu isian tertentu, sampai program yang menjalankannya macet: tab browser membeku, atau server berhenti melayani semua orang. Penyebabnya catastrophic backtracking. Bayangin kamu disuruh memeriksa apakah sebuah tulisan bisa dipotong jadi kata-kata yang sah, dan caramu mencoba setiap cara memotongnya, satu per satu. Kalau tulisannya sah, cara pertama langsung berhasil. Kalau gak sah, kamu baru boleh bilang "gak" setelah semua cara dicoba: tulisan 4 huruf punya 8 cara potong, 27 huruf punya 67 juta. Di pelajaran ini kita lihat itu terjadi pada validator nama pemesan PO Dapur Ratna.

🧪 Tebakan cepat: validator /^(\w+\s?)+$/ memeriksa nama Dina dalam sekejap. Isian "Dina" + "a".repeat(14) + "!" (18 huruf lalu tanda seru) butuh sekitar 2 ms. Kalau hurufnya ditambah satu, waktunya jadi kira-kira berapa: 2,1 ms, 3 ms, atau 4 ms? Tebak dulu, jawabannya ada di bagian "Mengukur: tiap huruf menggandakan waktunya".

Backtracking: mundur, lalu coba jalan lain

Di pelajaran quantifier kamu sudah lihat + mengambil sebanyak mungkin, lalu mundur kalau sisa pola gak cocok. Mundur itu namanya backtracking. Mesin regex JavaScript bekerja begitu: tiap ada pilihan (berapa huruf yang diambil +, ambil atau lewati ?, kiri atau kanan |), dia memilih satu dan jalan terus. Kalau mentok, dia kembali ke pilihan terakhir dan mencoba pilihan lain. Baru setelah semua pilihan habis, dia menjawab false.

Biasanya pilihannya sedikit, jadi cepat. Masalah muncul kalau satu teks bisa dicocokkan dengan banyak cara.

Pola rawan: ^(\w+\s?)+$

Validator nama pemesan: "satu kata atau lebih, dipisah spasi". Pola pertama yang terpikir:

const rawan = /^(\w+\s?)+$/;

const namaDiChat = [...new Set(chat.match(/(?<=\] )[^:]+(?=:)/g))];
for (const nama of namaDiChat) {
  console.log(nama, rawan.test(nama));
}
// Ratna (Admin) false
// Dina true
// Bayu true
// Sari true

Semua cepat. Tapi lihat isi group-nya: \w+ lalu \s?. Karena \s? boleh kosong, satu kata bisa dipotong jadi beberapa putaran group. Dina bisa dibaca 8 cara: [Dina], [Din][a], [Di][na], [Di][n][a], [D][ina], [D][in][a], [D][i][na], [D][i][n][a]. Di antara tiap dua huruf ada satu celah, dan tiap celah boleh dipotong atau gak. Jadi n huruf punya 2 pangkat (n - 1) cara: 20 huruf sudah 524.288 cara.

Mengukur: tiap huruf menggandakan waktunya

Ukur pakai performance.now(), dan pasang rem supaya pengukurannya berhenti sebelum macet:

const rawan = /^(\w+\s?)+$/;
rawan.test("Dina!"); // pemanasan: panggilan pertama selalu lebih lambat

for (let n = 18; n <= 27; n++) {
  const nama = "Dina" + "a".repeat(n - 4) + "!";
  const mulai = performance.now();
  const hasil = rawan.test(nama);
  const ms = performance.now() - mulai;
  console.log(n, "huruf:", hasil, ms.toFixed(1), "ms");
  if (ms > 500) break; // berhenti sebelum macet
}

Output di Node 22, di satu laptop:

18 huruf: false 1.9 ms
19 huruf: false 3.6 ms
20 huruf: false 7.0 ms
21 huruf: false 14.4 ms
22 huruf: false 27.9 ms
23 huruf: false 56.8 ms
24 huruf: false 113.1 ms
25 huruf: false 225.3 ms
26 huruf: false 460.0 ms
27 huruf: false 930.0 ms

Tiap tambah satu huruf, waktunya dua kali lipat: 18 huruf 1,9 ms, 19 huruf 3,6 ms. Itu jawaban tebakannya. Angka di komputermu pasti beda, tapi pola dua kali lipatnya sama. Dari situ bisa dihitung (bukan diukur): 30 huruf sekitar 7 detik, 40 huruf sekitar 2 jam.

Selama regex jalan, JavaScript gak mengerjakan hal lain. Di browser, tab-nya membeku. Di server Node.js, semua request lain ikut menunggu. Satu orang yang mengirim nama 40 huruf diakhiri ! cukup untuk menghentikan server buat semua orang: itulah denial of service.

Versi aman: ^\w+(?:\s\w+)*$

const aman = /^\w+(?:\s\w+)*$/;

console.log(aman.test("Dina"), aman.test("Putri Salju"), aman.test("Ratna (Admin)")); // true true false
console.log(aman.test("Dina" + "a".repeat(23) + "!"));     // false, 0.0 ms
console.log(aman.test("Dina" + "a".repeat(99996) + "!"));  // false, sekitar 0.5 ms untuk 100.000 huruf

Pola rawan lain dan pasangan amannya:

Pola rawan Kenapa ambigu Versi aman
/^(a+)+$/ quantifier di dalam quantifier /^a+$/
/^(\w+)+$/ sama, untuk huruf apa pun /^\w+$/
/^(\w+\s?)+$/ \s? boleh kosong, jadi potongan kata bebas /^\w+(?:\s\w+)*$/
/^(a|aa)+$/ dua pilihan bisa cocok dengan teks yang sama /^a+$/

Cirinya: ada quantifier (+, *) di dalam group yang juga diulang, dan isi group itu bisa memotong teks yang sama dengan lebih dari satu cara. Perbaikannya: buang pembungkus yang gak perlu ((\w+)+ jadi \w+), atau buat tiap putaran diawali sesuatu yang gak bisa dimakan putaran sebelumnya (\s di depan \w+).

Lapisan pengaman tambahan

Ini bukan cuma teori. Stack Overflow pernah down 34 menit (2016) karena regex pembersih spasi bertemu posting dengan sekitar 20.000 spasi berturut-turut, dan Cloudflare down 27 menit di seluruh dunia (2019) karena satu aturan firewall berisi .*(?:.*=.*).

⚠️ Jebakan yang sering ketemu

TL;DR: ReDoS = regex yang macet karena catastrophic backtracking: mesin mundur dan mencoba setiap cara membagi (partisi) teks sebelum menjawab false. Pemicunya quantifier di dalam quantifier yang ambigu, seperti /^(a+)+$/, /^(\w+)+$/, atau validator nama /^(\w+\s?)+$/, ditambah isian panjang yang gagal di ujung ("Dina" + "a".repeat(23) + "!"). Tiap tambah satu huruf, waktunya dua kali lipat: 27 huruf hampir 1 detik, 40 huruf sekitar 2 jam. Perbaikannya: buat tiap karakter cuma punya satu cara dicocokkan, misalnya /^(\w+)+$/ jadi /^\w+$/ dan /^\w+(?:\s\w+)*$/ untuk kata dipisah spasi. Batasi panjang isian sebagai lapisan kedua, dan untuk pola dari luar pakai mesin linear seperti RE2. Selalu tes isian yang gagal, dan ukur dengan rem.

Yang akan kamu pelajari