Question 1

Apa itu ReDoS (Penolakan Layanan melalui Ekspresi Reguler)?

Accepted Answer

ReDoS adalah kelas kerentanan penolakan layanan di mana string input yang dibuat dengan jahat menyebabkan mesin regex membutuhkan waktu eksponensial atau polinomial untuk mengevaluasi, secara efektif menggantung atau menghentikan proses. Ini muncul dari kombinasi dua faktor: (1) Backtracking — sebagian besar mesin regex menggunakan backtracking untuk menjelajahi semua kemungkinan jalur pencocokan ketika pencocokan gagal, dan (2) Pola yang ambigu — regex di mana banyak jalur dapat mencocokkan karakter input yang sama, menyebabkan backtracking menjelajahi secara eksponensial banyak kombinasi sebelum menyimpulkan tidak ada kecocokan.

Question 2

Pola regex apa yang paling rentan terhadap ReDoS?

Accepted Answer

Pola paling berbahaya melibatkan kuantifier bersarang dan alternasi di mana subpola dapat tumpang tindih. Contoh klasiknya adalah (a+)+ atau (a|aa)+ — keduanya memiliki ledakan eksponensial pada input seperti 'aaaaaaaab'. Pola berisiko lainnya: (.*)* (Kleene star bersarang), (a*b?c*)+ (grup tumpang tindih), dan pola dengan beberapa operator .* atau .+ yang berdekatan.

Question 3

Bagaimana detektor ReDoS mengidentifikasi pola yang rentan?

Accepted Answer

Alat analisis statis mendeteksi ReDoS dengan menganalisis struktur internal regex — khususnya mencari: (1) Kuantifier bersarang: ekspresi di dalam kuantifier yang diulang sendiri (mis. (X+)+). (2) Ambiguitas eksponensial: jalur melalui NFA (Automaton Finite Nondeterministik) yang dapat mencocokkan string yang sama dengan beberapa cara — ini dideteksi dengan menjalankan NFA pada string serangan tertentu atau melalui analisis formal grafik status.

Question 4

Bagaimana cara memperbaiki regex yang rentan terhadap ReDoS?

Accepted Answer

Perbaikan umum: (1) Hapus kuantifier bersarang — tulis ulang (a+)+ sebagai a+. (2) Jadikan alternasi tidak tumpang tindih — alih-alih (cat|catch), gunakan catch|cat (terpanjang terlebih dahulu) atau (cat)(?:ch)?. (3) Gunakan kuantifier posesif atau grup atomik di mana mesin mendukungnya — (?>a+) tidak pernah melakukan backtrack. (4) Gunakan mesin regex waktu linear seperti RE2, Hyperscan, atau paket regexp Go, yang menjamin pencocokan O(n) tanpa backtracking.

Question 5

Mesin regex bahasa pemrograman apa yang rentan terhadap ReDoS?

Accepted Answer

Mesin backtracking (rentan): JavaScript (V8), Python (modul re), Java (java.util.regex), PHP (PCRE), Ruby, .NET — semua dapat menunjukkan ledakan eksponensial. Mesin non-backtracking (aman): RE2 (Google), regexp Go, crate regex Rust, Hyperscan — menjamin waktu linear O(n) tetapi tidak mendukung lookahead/lookbehind atau backreference. Untuk validasi input yang sensitif terhadap keamanan, RE2 atau mesin waktu linear serupa harus sangat diutamakan.

Detektor ReDoS Regex

Pertanyaan yang Sering Diajukan

Comments & Feedback