Deep Dive Regular Expressions: Bedah Trik ReDoS & Optimasi Regex Engine

1. Menu Kita Hari Ini & Alat yang Perlu Disiapkan

Pernahkah layanan backend Node.js atau Go Anda tiba-tiba mengalami lonjakan CPU hingga 100% dan tidak merespons request sama sekali, padahal trafik HTTP dari Cloudflare terlihat normal? Kemarin malam, saya mendapati insiden persis seperti itu di salah satu production cluster kami. Usut punya usut, pelakunya bukan serangan DDoS masif, melainkan sebaris ekspresi reguler (regex) sederhana pada modul validasi input form. Dalam 15 menit ke depan, kita akan merakit pemahaman mendalam sekaligus solusi konkret untuk menjinakkan monster bernama Catastrophic Backtracking ini.

[!IMPORTANT] Siapkan terminal Anda, pastikan Node.js (versi 18+) atau Go (versi 1.20+) terinstal dengan baik di mesin lokal, karena kita akan langsung menguji performa regex engine secara hands-on.

Kita tidak akan membuang waktu membahas teori bahasa formal yang membosankan. Kita langsung masuk ke dapur, membongkar mesin di baliknya, dan meracik regex yang aman, cepat, dan efisien untuk production.

2. Peta Jalan Singkat: Apa yang Sedang Kita Rakit

Perjalanan kita dimulai dengan membedah jeroan regex engine modern, melihat perbedaan krusial antara NFA (Non-Deterministic Finite Automaton) dan DFA (Deterministic Finite Automaton). Anda akan paham mengapa NFA yang diadopsi oleh mayoritas bahasa pemrograman populer sangat rentan terhadap jebakan eksponensial.

Setelah itu, kita akan melangkah ke dapur eksperimen untuk mendeteksi pola rentan yang memicu ReDoS (Regular Expression Denial of Service), lalu merestrukturisasinya. Sebagai penutup, kita akan membandingkan performa parsing string menggunakan regex kompleks versus pendekatan lexer/parser manual yang jauh lebih deterministik.

3. Langkah 1: Mempersiapkan Fondasi & Environment

Mari kita buat direktori kerja baru dan inisialisasi skrip pengujian berbasis Node.js untuk mensimulasikan kegagalan regex engine saat menghadapi input yang dirancang khusus (malicious payload).

Buka terminal Anda dan jalankan perintah berikut:

mkdir redos-lab && cd redos-lab
npm init -y
npm install benchmark

[!TIP] Gunakan modul benchmark untuk mengukur eksekusi secara akurat. Kita akan melihat bagaimana perbedaaan satu karakter kuantifikator (quantifier) dapat mengubah waktu eksekusi dari beberapa milidetik menjadi hitungan menit—bahkan hang selamanya.

4. Langkah 2: Meracik Konfigurasi Inti Tanpa Basa-basi

Sekarang, mari kita buat berkas test-redos.js untuk menguji perilaku NFA engine saat mengevaluasi pola yang ambigu. Perhatikan bagaimana backtracking bekerja di balik layar ketika engine mencoba mencocokkan string yang hampir mirip dengan pola yang dicari.

// test-redos.js
const benchmark = require('benchmark');
const suite = new Benchmark.Suite;

// Pola rentan: Nested quantifiers dengan overlap
// Contoh: /^(a+)+$/ 
const vulnerableRegex = /^(a+)+$/;

// Input normal vs Malicious input
const normalString = "aaaaaaaa";
const maliciousString = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaab";

suite
  .add('Normal Input Evaluation', function() {
    vulnerableRegex.test(normalString);
  })
  .add('Malicious Input Evaluation (ReDoS)', function() {
    // Hati-hati: baris ini bisa membuat event loop Node.js freeze jika string terlalu panjang
    vulnerableRegex.test(maliciousString);
  })
  .on('cycle', function(event) {
    console.log(String(event.target));
  })
  .on('complete', function() {
    console.log('Eksperimen selesai. Perhatikan disparitas performa di atas.');
  })
  .run({ 'async': true });

Jalankan skrip tersebut dengan perintah:

node test-redos.js

Perhatikan respons di terminal Anda. Begitu skrip mengevaluasi maliciousString, Anda akan merasakan jeda yang signifikan. Itulah tanda nyata bahwa NFA engine sedang melakukan backtracking jutaan kali mencoba semua kombinasi jalur pencocokan yang mungkin.

5. Langkah 3: Sentuhan Akhir Keamanan & Optimasi

Untuk mengeliminasi kerentanan ReDoS di atas, kita harus menghindari penggunaan nested quantifiers (seperti (a+)+ atau (a|a)+). Ubah pola tersebut menjadi bentuk yang deterministik atau gunakan Atomic Grouping jika didukung, atau sederhanakan struktur logikanya.

Mari kita perbaiki skrip kita menjadi versi yang aman:

// test-safe.js
const safeRegex = /^a+$/;

console.time('Safe Regex Execution');
const maliciousString = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaab";
console.log(safeRegex.test(maliciousString));
console.timeEnd('Safe Regex Execution');

[!WARNING] Jangan pernah mempercayai input pengguna mentah-mentah lalu melewatkannya ke regex yang kompleks tanpa melakukan pembatasan panjang string (string length limiting) terlebih dahulu di lapisan aplikasi atau WAF (Cloudflare/Nginx).

6. Tes Rasa: Memastikan Semuanya Berjalan Sempurna

Mari verifikasi optimasi kita. Ketika Anda menjalankan node test-safe.js, eksekusi akan selesai dalam waktu kurang dari 1 milidetik, berapapun panjang string inputnya (selama dibatasi wajar). Engine tidak lagi melakukan backtracking buta karena struktur ^a+$ bersifat linear (linear time complexity, O(n)) alih-alih eksponensial (O(2^n)).

7. Pertolongan Pertama: Jika Terjadi Kendala Kecil

Jika Anda mendapati aplikasi web masih mengalami lonjakan CPU setelah mengganti pola regex, periksa kembali apakah ada modul pihak ketiga (third-party npm packages) yang menggunakan regex internal yang rentan. Gunakan tools seperti safe-regex di pipeline CI/CD Anda untuk mendeteksi potensi ReDoS secara otomatis sebelum kode masuk ke lingkungan production Nginx/Node.js Anda.