flawopen.com/Apa itu ReDoS/Explained

Apa itu ReDoS (backtracking katastrofik)?

CWE-1333: Inefficient Regular Expression ComplexityHalaman referensi

Jawaban singkat

Engine regex dengan backtracking dapat mencoba beberapa cara membagi masukan yang sama setelah pencocokan gagal. Pada pola ambigu tertentu, jumlah percobaan tumbuh eksponensial seiring panjang masukan. Latensi bergantung pada regex, engine, ukuran masukan, konkurensi, dan batas sumber daya; permintaan mahal berulang dapat menghabiskan kapasitas layanan.

POLA RENTAN

# Nested quantifier
^(a+)+$

# Overlapping alternatives, quantified
^(a|aa)+$

# A long matching prefix plus a final mismatch can
# force extensive retries in vulnerable engines.
# Do not benchmark this with attacker-sized input.

LEBIH AMAN

# Bound input before matching, then use a simple
# full-string identifier rule with no nested ambiguity.
import re

IDENTIFIER = re.compile(r"[a-z0-9]{1,64}\Z")

def valid_identifier(value: str) -> bool:
    if not isinstance(value, str) or len(value) > 64:
        return False
    return IDENTIFIER.fullmatch(value) is not None

# A bound reduces worst-case work; still set request
# size, concurrency, and execution-time limits.

Mengapa backtracking dapat melonjak

Pola seperti ^(a+)+$ bersifat ambigu pada engine backtracking: rangkaian aaaa dapat dibagi ke quantifier bertingkat dengan beberapa cara. Karakter terakhir yang tidak cocok dapat membuat engine menjelajahi alternatif sebelum menyimpulkan bahwa seluruh string gagal.

Untuk pola yang memiliki ambiguitas tersebut, jalur yang dijelajahi dapat tumbuh eksponensial berdasarkan panjang awalan yang cocok sebelum karakter gagal. Ini bergantung pada kombinasi pola dan engine tertentu, bukan semua regex atau kegagalan. Masukan lebih pendek juga berisiko saat permintaan bersamaan; batasi ukuran masukan, konkurensi, dan waktu.

Jalur masukan tidak tepercaya menuju regex

Validasi masukan adalah contoh yang jelas, tetapi risiko juga ada pada penguraian User-Agent dan header lain, pemrosesan log, Markdown dan penyorotan sintaks, perutean URL, filter konten dan aturan WAF, serta pustaka yang menjalankan regex pada field kiriman aplikasi. Paket populer pernah menerbitkan advisori ReDoS; dependensi sama pentingnya dengan pola buatan sendiri.

Pertanyaan umum

Which languages are affected?

Risiko bergantung pada engine dan pola, bukan bahasa saja. Engine backtracking umum dapat memeriksa terlalu banyak alternatif pada pola tertentu. Dokumentasi Go menjamin regexp berjalan linear terhadap panjang masukan. Crate Rust regex mendokumentasikan O(m·n) untuk satu pencarian (m ukuran pola, n ukuran masukan), sehingga linear terhadap n untuk pola tetap; iterator pencarian berulang memiliki batas terburuk berbeda. Engine ini tidak mendukung fitur seperti backreference yang menghalangi jaminan tersebut.

Is a length limit enough on its own?

Batas panjang mengurangi pekerjaan pencocokan, tetapi nilai aman bergantung pada pola, engine, laju permintaan, dan anggaran layanan. Perbaiki pola ambigu dan terapkan batas sebelum penguraian atau pencocokan.

How do I find vulnerable patterns?

Gunakan penganalisis statis yang memahami ReDoS dan tinjau temuannya sesuai engine yang dipakai. Periksa grup berulang yang memuat pengulangan atau alternatif dengan awalan tumpang tindih; lalu uji dengan masukan terbatas dan timeout ketat di lingkungan terisolasi.

Can I add a timeout instead?

Dukungan timeout berbeda menurut runtime dan API. Di .NET, tetapkan timeout eksplisit untuk pencocokan dengan masukan tidak tepercaya. Untuk runtime lain, periksa kontrol yang didokumentasikan engine terkait; gunakan engine lebih aman atau desain ulang pola jika timeout tidak tersedia. Timeout melengkapi batas masukan dan konkurensi, tetapi tidak membuat pola ambigu menjadi efisien.

Referensi

Lihat juga ReDoS Node.js: Regex dan CVE-2026-83606