ReDoS: كيف يعطّل تعبير نمطي واحد خادمك بالكامل

import re, time

# نمط هش: كمّيتان متداخلتان على نفس الحرف
pattern = re.compile(r"(a+)+$")

for n in range(24, 32):
    s = "a" * n + "!"                 # مدخل يجبر المحرّك على الفشل في آخر خطوة
    start = time.perf_counter()
    pattern.search(s)
    took = time.perf_counter() - start
    print(f"{n:>2} chars -> {took:8.3f}s")

مخرجات تقريبية على جهاز عادي: عند 26 حرفًا أقل من ثانية، عند 28 حوالي 1.5 ثانية، عند 30 حوالي 6 ثوانٍ، عند 31 حوالي 12 ثانية. الزمن بيتضاعف مع كل حرف تضيفه. ده هو التراجع الكارثي بالتفاصيل: مدخل صغير جدًا، تكلفة ضخمة.

السيناريو الواقعي: انقطاع Cloudflare

في 2 يوليو 2019، خرجت خدمات Cloudflare عالميًا لمدة تقارب 27 دقيقة. السبب لم يكن هجومًا خارجيًا، بل قاعدة WAF جديدة فيها تعبير نمطي يحتوي .*(?:.*=.*). النمط ده فيه نفس المرض: كمّيات متداخلة تسبّب تراجعًا كارثيًا. القاعدة اتنشرت على كل الأجهزة، فقفز استهلاك المعالج إلى 100% على شبكتهم بالكامل. درس مباشر: التعبير النمطي الهش مش مجرد بطء، ده سطح هجوم — أي مستخدم يقدر يبعت مدخلًا مصمّمًا خصيصًا يشلّ عاملًا كاملًا (worker) بطلب واحد.

الحل: ثلاث خطوات بترتيب الأولوية

1. احذف الكمّيات المتداخلة. غالبًا النمط ممكن يتكتب من غير تداخل. (a+)+ بيساوي منطقيًا a+. راجع كل نمط فيه (X+)+ أو (X*)* أو (X+)* — دي الأنماط الخطيرة.
2. استخدم محرّكًا خطيًا. RE2 (من Google) بيضمن زمنًا خطيًا O(n) لأنه ما بيعملش تراجع أصلًا. في بايثون: pip install google-re2. في Go محرّك regexp القياسي مبني على RE2 افتراضيًا، فهو محصّن ضد ReDoS.
3. لو لازم تفضل على محرّك تراجع، استخدم المجموعات الذرّية أو الكمّيات الاستحواذية لمنع التراجع: (?>a+)+$ أو (a++)+$ (متاحة في مكتبة regex في بايثون وفي Java وPCRE). وحُط سقفًا صارمًا لطول المدخل قبل التمرير للـ Regex.

الـ trade-off هنا

RE2 بيكسبك أمانًا وزمنًا خطيًا مضمونًا، بس بتخسر مزايا معيّنة: مفيش دعم للـ backreferences ولا lookaround في RE2. لو أنماطك محتاجة المزايا دي فعلًا، فالبديل هو البقاء على محرّك تراجع مع مجموعات ذرّية + حدّ لطول المدخل + مهلة تنفيذ (timeout). التكلفة: تعقيد أعلى في المراجعة، وخطر إن نمط جديد يتسرّب من غير تحصين. المكسب: احتفاظك بكامل قدرات التعبير النمطي.

متى لا تشغل بالك بهذا

لو التعبير النمطي بيشتغل على مدخلات ثابتة تحت سيطرتك بالكامل (أسماء ملفات في سكربت بناء مثلًا)، وطولها محدود وما بييجيش من مستخدم خارجي، فخطر ReDoS شبه معدوم — مش محتاج تعيد هندسة أي حاجة. المشكلة بتظهر بس لمّا مدخل غير موثوق يوصل لنمط فيه غموض. كمان لو أنماطك كلها بسيطة وخطية (بلا كمّيات متداخلة)، فأنت آمن أصلًا حتى مع محرّك تراجع.

الخطوة التالية

افتح كل نمط Regex في كودك بيشتغل على مدخل من المستخدم، ودوّر على الأنماط الثلاثة الخطيرة: (X+)+ و(X*)* و(X+)*. لأول نمط تلاقيه، شغّل عليه سكربت القياس اللي فوق بمدخل فاشل متزايد الطول. لو الزمن بيتضاعف مع كل حرف، ده هو التراجع الكارثي — حصّنه بـ RE2 أو مجموعة ذرّية فورًا.

المصادر

• Cloudflare — "Details of the Cloudflare outage on July 2, 2019" (blog.cloudflare.com): التقرير الرسمي لحادثة التعبير النمطي.
• OWASP — "Regular expression Denial of Service - ReDoS" (owasp.org): تعريف الثغرة وأنماطها الخطيرة.
• Russ Cox — "Regular Expression Matching Can Be Simple And Fast" (swtch.com/~rsc/regexp): الأساس النظري لـ RE2 والفرق بين NFA والتراجع.
• Google RE2 — مستودع ومواصفات المحرّك (github.com/google/re2).
• توثيق بايثون الرسمي لمكتبتَي re وregex (docs.python.org)، وتوثيق حزمة google-re2.