سطر regex واحد ممكن يخلّي سيرفرك يصرف 100% CPU لدقائق على input طوله 30 حرف فقط. ده مش سيناريو نظري — ده اللي حصل لـ Cloudflare في 2 يوليو 2019 وفصل جزء كبير من الإنترنت 27 دقيقة كاملة. المقال ده هيوريك بالظبط ليه بيحصل، وإزاي تمنعه قبل ما يحصلك.
ReDoS: لما سطر Regex واحد بيقفل السيرفر
المشكلة باختصار
الـ ReDoS (Regular Expression Denial of Service) هو هجوم أو خطأ بسيط في كتابة regex بيخلّي الـ engine يدخل في عدد محاولات أسي (exponential) بدل ما يرجّع نتيجة في الوقت الطبيعي. الكود اللي بيشتغل في 2ms على input نضيف، بياخد 30 ثانية أو أكتر لما الـ input يبقى مصمم مخصوص.
مثال بسيط لأي مبتدئ: قصة رف المطابخ
تخيّل معاك رف فيه 30 علبة، وبتدور على علبة مكتوب عليها "ملح". الطريقة المنطقية: تبص على كل علبة مرة واحدة. لو لقيتها، توقف. لو خلصت الـ 30 علبة، تستنتج إنها مش موجودة. بالظبط 30 محاولة.
طيب تخيّل إن صاحب المحل غبي شوية. بدل ما يكتفي بالمحاولة الأولى، لما ميلاقيش الملح هو بيقول: "يمكن أنا بصيت بالترتيب الغلط". فبيعيد، بس المرة دي يقلب العلبتين الأولانيتين، يدور تاني. مفيش؟ يقلب العلب التلاتة الأولانيين، يدور تاني. ومع كل فشل، بيجرّب توليفة جديدة من ترتيب العلب.
عدد التوليفات الممكنة لـ 30 علبة = 2^30، يعني أكتر من مليار محاولة. هو ده بالظبط اللي بيحصل جوّا الـ regex engine لما يقابل catastrophic backtracking.
التفسير العلمي الدقيق: Catastrophic Backtracking
معظم الـ regex engines في JavaScript و Python و Java و .NET و PHP بتشتغل بطريقة اسمها NFA with backtracking. يعني الـ engine بيبني Nondeterministic Finite Automaton ويجرّب كل مسار ممكن لحد ما يلاقي match (أو يفشل).
المشكلة بتظهر لما يبقى عندك quantifier متداخل مع quantifier تاني، زي (a+)+ أو (.*)+. الـ engine هنا عنده أكتر من طريقة عشان يقسّم نفس الـ input بين الجروبات الداخلية والخارجية. لو الـ input في آخره حرف بيمنع الـ match، الـ engine بيرجع ويجرّب كل التوزيعات الممكنة قبل ما يستسلم. عدد المسارات = O(2^n) حيث n طول الـ input.
الـ engines المحصّنة (زي Google RE2 و Rust's regex crate) بتستخدم Deterministic Finite Automaton — بتديك ضمان O(n) دايماً، بس بتتنازل عن features زي \1 backreferences و lookaheads.
كود تقدر تجرّبه دلوقتي
شغّل الكود ده في Node.js وشوف بعنيك الفرق بين input نضيف وinput خبيث:
// ملف: redos-demo.js
const evilPattern = /^(a+)+$/;
function measure(input, label) {
const start = Date.now();
evilPattern.test(input);
const elapsed = Date.now() - start;
console.log(`${label}: ${elapsed}ms`);
}
// Input نضيف — match ناجح وسريع
measure("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa", "match ناجح (30 حرف)");
// Input خبيث — آخر حرف مختلف، الـ engine هيحاول كل تركيبة
measure("aaaaaaaaaaaaaaaaaaaaaaaaaaaaa!", "match فاشل (30 حرف + !)");
// على لاب توب عادي: > 30,000ms
