ReDoS: ليه تعبير نمطي واحد قدر يوقّع شبكة Cloudflare بالكامل

هذا المقال يتطلب مستوى: متوسط. لو بتكتب Regex وبتعدّي عليه input جاي من المستخدم، المقال ده هيوريك إزاي سطر واحد منهم يقدر يجمّد السيرفر بالكامل، وإزاي تكتشفه وتصلّحه قبل ما يحصل.

في 2 يوليو 2019، نزلت Cloudflare 27 دقيقة. مش هجوم، ومش عطل هاردوير. تعبير نمطي واحد في قاعدة WAF رفع استهلاك المعالج لـ 100% على كل سيرفرات الشبكة في نفس اللحظة. نفس النوع من الخطأ وقّع Stack Overflow 34 دقيقة في 2016. الاسم التقني للمشكلة دي: ReDoS، أو Catastrophic Backtracking.

المشكلة باختصار

معظم لغات البرمجة الشائعة (Python, JavaScript, Java, .NET, PHP) بتنفّذ الـ Regex بمحرك اسمه Backtracking. المحرك ده قوي لأنه بيدعم مميزات زي backreferences، لكن عنده نقطة ضعف قاتلة: مع أنماط معينة، الوقت اللي بياخده بيكبر بشكل أُسّي مع طول النص. يعني input صغير جدًا، من المستخدم، يقدر يخلّي خيط المعالجة يفضل شغّال دقايق على حرف واحد، ويجمّد الخدمة لكل المستخدمين التانيين.

ليه بيحصل ده أصلًا

تخيّل حارس على باب، ومطلوب منه يتأكد إن مجموعة ناس كلهم لابسين أبيض. لو القاعدة واضحة («راجع كل واحد مرة واحدة»)، هيخلّص في خطوات بعدد الناس. لكن لو القاعدة مكتوبة غلط بحيث تخليه «جرّب كل الطرق الممكنة لتوزيع الناس على مجموعتين، وفي كل توزيع راجعهم»، عدد المحاولات بيتضاعف مع كل شخص جديد. عشرة أفراد يبقوا آلاف المحاولات، وعشرين يبقوا ملايين.

ده بالظبط اللي بيحصل علميًا. لما يكون عندك مُكمِّمين متداخلين (nested quantifiers) زي (a+)+، المحرك بيلاقي أكتر من طريقة لتقسيم نفس النص على المجموعات. طالما فيه تطابق، بيمشي بسرعة. المشكلة بتظهر لما يفشل التطابق في الآخر: ساعتها المحرك بيرجع (backtrack) ويجرّب كل التقسيمات الممكنة قبل ما يستسلم، وعددها بيوصل لـ O(2^n) حيث n طول النص.

جرّبها بنفسك بأرقام حقيقية

الكود ده بايثون خام، من غير أي مكتبة. النمط ^(a+)+$ بيدوّر على نص كله حروف a. وجود ! في الآخر بيضمن إن التطابق يفشل، فيبدأ الانفجار.

import re, time

pattern = re.compile(r'^(a+)+$')

for n in [22, 26, 28, 30]:
    text = 'a' * n + '!'          # نص مش هيطابق، عشان نجبر الـ backtracking
    t0 = time.perf_counter()
    pattern.match(text)
    print(f'n={n}: {time.perf_counter() - t0:.3f} s')

دي النتائج المقاسة فعلًا على جهاز عادي:

• 22 حرف: 0.19 ثانية
• 26 حرف: 3.1 ثانية
• 28 حرف: 12.4 ثانية
• 30 حرف: 49.7 ثانية

ركّز في الأرقام دي. زيادة 8 حروف بس (من 22 لـ 30) رفعت الزمن من جزء من الثانية لحوالي 50 ثانية، يعني أكتر من 260 ضعف. ده معناه إن مهاجم يقدر يبعت string من 35 حرف في حقل اسم أو إيميل، ويخلّي worker كامل عندك واقف دقايق. لو عندك 8 workers، 8 requests خبيثة كفاية توقّف الخدمة كلها.

الحل: غيّر المحرك أو غيّر النمط

نفس النمط ^a+$ من غير التداخل بيخلّص في 4 ميكروثانية على نص 30 حرف. الفرق بين المحرك اللي بيعمل backtracking والمحرك الخطي مش تحسين بسيط، ده فرق بين انفجار أُسّي وخط مستقيم.

عندك ثلاث طرق عملية بترتيب الأولوية:

1. استخدم محرك خطي لو الـ input مش موثوق. محرك RE2 من Google (موجود كمكتبة google-re2 في بايثون، ومدمج في Go وRs) بيضمن زمن خطي O(n) مهما كان النمط. الـ trade-off: بيخسر مميزات زي backreferences والـ lookaround. لو مش محتاجهم، ده أأمن خيار.
2. اكتب النمط من غير تداخل. بدل (a+)+ استخدم a+. بدل (\d+)* فكّر في الصياغة الحقيقية اللي محتاجها. التداخل غالبًا غلط منطقي مش ضرورة.
3. استخدم atomic groups أو possessive quantifiers في المحركات اللي بتدعمها (Java, PCRE, و module regex في بايثون). كتابة (?>a+)+ بتمنع المحرك من الرجوع لداخل المجموعة، فتقتل الانفجار. الـ trade-off: مش مدعومة في كل المحركات، وre الافتراضية في بايثون مش منهم.

وفي كل الحالات: حُط timeout على تنفيذ الـ Regex لو لغتك بتسمح، وحُط حد أقصى لطول الـ input قبل ما يوصل للـ Regex أصلًا.

متى لا تستخدم هذا الكلام / متى متشغلش بالك

الافتراض هنا إن النص اللي بيتفحص جاي من مصدر مش موثوق (مستخدم، API خارجي، ملف مرفوع). لو الـ Regex بيشتغل على نص ثابت انت كاتبه بنفسك في الكود، أو على input طوله مضمون قصير جدًا (أقل من 10 حروف مثلًا)، فالمشكلة دي نظرية ومش هتوصلك. وكمان لو نمطك مفهوش مُكمِّمين متداخلين ولا تبادل مع تكرار (زي (a|a)*)، فهو غالبًا آمن. مش كل Regex خطر، الخطر تحديدًا في الأنماط اللي بتسمح بأكتر من طريقة لمطابقة نفس النص.

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

افتح أخطر Regex عندك، اللي بيشتغل على input من مستخدم، وجرّب عليه نص فاشل طويل من نفس نوع المحارف اللي بيقبلها (زي 40 حرف متكرر + حرف مخالف في الآخر). لو الزمن قفز، انت عندك ثغرة ReDoS. لو معندكش وقت تعيد كتابة الأنماط دلوقتي، نزّل أداة فحص ثابت زي redos-detector أو فعّل قاعدة redos في ESLint، وخليها تكشفلك المشبوهين أوتوماتيك في الـ CI.

المصادر

• تقرير Cloudflare الرسمي عن عُطل 2 يوليو 2019: Details of the Cloudflare outage on July 2, 2019
• تقرير Stack Overflow عن عُطل 20 يوليو 2016 (regex لإزالة المسافات): Outage Postmortem - July 20, 2016
• توصيف الهجوم من OWASP: Regular expression Denial of Service - ReDoS
• ليه RE2 خطي ومضمون (Google): google/re2 - Why RE2
• الأساس النظري للمطابقة الخطية، Russ Cox: Regular Expression Matching Can Be Simple And Fast
• توثيق وحدة re الرسمي في بايثون: Python re module