هذا المقال يتطلب مستوى: محترف. لو بتكتب تعبيرات نمطية (Regex) على مدخلات جايالك من المستخدم، فيه سطر واحد ممكن يوقّف السيرفر بالكامل من غير ما حد يهاجمك عمداً.
ReDoS: لما تعبير نمطي واحد يقفل السيرفر
في 2 يوليو 2019، خدمات Cloudflare وقعت عالمياً حوالي 27 دقيقة. السبب مكانش هجوم؛ كان تعبير نمطي واحد اترفع في قاعدة الـ WAF، خلّى استهلاك المعالج يقفز لـ100% على كل سيرفراتهم في نفس اللحظة. المقال ده هيوريك بالظبط إزاي بيحصل ده، وإزاي تكتشفه وتصلحه قبل ما يحصل عندك.
المشكلة باختصار
التعبير النمطي المفروض أداة بحث سريعة. لكن نوع معين من الأنماط بيتحول من بحث خطي إلى انفجار أُسّي في عدد الخطوات. المدخل الصغير — 30 حرف يمكن — بياكل المعالج ثواني أو دقائق ويجمّد الـ thread بالكامل. ده اسمه ReDoS: حجب خدمة عن طريق تعبير نمطي (Regular expression Denial of Service).
المفهوم الأساسي: التراجع (Backtracking) بمثال بسيط
تخيّل قفل حقيبة بـ 3 عجلات أرقام. اللص بيجرب توليفة، لو غلط بيرجع خطوة ويغيّر آخر عجلة، يجرب تاني، وهكذا. طول ما فيه احتمالات متبقية، بيرجع ويعيد المحاولة. ده بالظبط اللي محرك الـ Regex بيعمله لما النمط بيسمح بأكتر من طريقة لتقسيم نفس النص: بيجرب تقسيمة، تفشل، يرجع (backtrack) ويجرب تقسيمة تانية.
دلوقتي المفهوم بدقة: محركات regex التقليدية في Python و JavaScript و PCRE بتشتغل بالـ backtracking. نمط زي (a+)+ بيسمح بتقسيم سلسلة الـ a بأكتر من طريقة، وعدد التقسيمات الممكنة بيكبر أُسّياً مع طول السلسلة. طول ما النص بيطابق، المحرك بيلاقي حل بسرعة. المشكلة بتحصل لما النص يفشل في المطابقة النهائية — مثلاً حرف مش a في الآخر. ساعتها المحرك مجبور يجرب كل التقسيمات الممكنة قبل ما يتأكد إن مفيش مطابقة. ده بيخلي التعقيد O(2^n) بدل O(n).
اكتشفها وقيسها بنفسك
الكود ده بيبني القنبلة ويقيس الزمن مع طول المدخل. جرّبه:
import re, time
evil = re.compile(r"(a+)+$") # النمط الخطر: كمية متداخلة
for n in (20, 24, 28, 30):
s = "a" * n + "!" # a كتير + حرف بيفشل المطابقة
t = time.perf_counter()
evil.search(s)
print(n, round(time.perf_counter() - t, 3), "s")
النتيجة على جهاز اختبار عندي (أرقام تقديرية، بتختلف حسب المعالج وإصدار Python):
- 20 حرف ← حوالي 0.01 ثانية
- 24 حرف ← حوالي 0.2 ثانية
- 28 حرف ← حوالي 3.4 ثانية
- 30 حرف ← حوالي 14 ثانية
ركز في النمط: كل حرف زيادة بيضاعف الزمن تقريباً. 30 حرف بس عملوا 14 ثانية تجميد. تخيّل السطر ده في handler بيرد على request، والمدخل جاي من فورم على النت.