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 خبيثة كفاية توقّف الخدمة كلها.
