الـ ReDoS: إزاي تعبير نمطي واحد يوقّع سيرفرك بالكامل
هذا المقال لمستوى: محترف. بيفترض إنك مرتاح مع الـ regex وبتشغّله على مدخلات مستخدم غير موثوقة (نماذج، هيدرز، بارامترات URL). لو لسه بتتعلّم أساسيات التعبيرات النمطية، ابدأ من هناك ثم ارجع.
ركّز في السطر ده: regex واحد غلط ممكن يرفع استهلاك المعالج إلى 100% ويطفّي خدمتك بالكامل من غير أي هجوم خارجي معقّد. في 2 يوليو 2019 ده بالظبط اللي حصل لـ Cloudflare، وطفّى جزء كبير من الإنترنت 27 دقيقة. المشكلة اسمها ReDoS، وهي غالبًا موجودة في كودك دلوقتي وانت مش واخد بالك.
المشكلة باختصار
محرّك الـ regex في أغلب اللغات (JavaScript، Python، Java، PHP، .NET القديم) بيشتغل بأسلوب اسمه backtracking. الأسلوب ده قوي لأنه بيدعم مميزات زي backreferences وlookaround. بس عنده عيب قاتل: مع نمط معيّن ومدخل معيّن، عدد المحاولات بيتضاعف أسّيًا مع كل حرف. النتيجة إن مطابقة نص من 30 حرف ممكن تاخد ساعات بدل ميكروثانية.
المثال البسيط الأول: الحارس اللي بيرجع يجرّب كل الطرق
تخيّل حارس عند مدخل عمارة، ومطلوب منه يتأكد إن اسم كامل مكوّن من مجموعات حروف بيساوي شرط معيّن. لو الاسم مطابق، يمشي بسرعة. لكن لو الاسم غير مطابق في آخر حرف، الحارس ما بيقولش "مرفوض" على طول. بدل كده بيرجع لأول اسم ويجرّب توزيعة تانية للحروف على المجموعات، وبعدين توزيعة تالتة، وهكذا.
لو عندك مجموعتين متداخلتين بيقدروا يقسّموا نفس الحروف، عدد التوزيعات اللي الحارس لازم يجرّبها قبل ما يستسلم بيتضاعف مع كل حرف يزيد. ده بالظبط اللي بيحصل فعلاً جوه المحرّك، ومحدش شايفه لأنه كله بيتم في أجزاء من الثانية… لحد ما المدخل يكبر شوية.
الشرح العلمي: التراجع الكارثي (Catastrophic Backtracking)
خلّينا ندقّق. النمط الكلاسيكي المتفجّر هو ^(a+)+$. عندك هنا مُكمِّمَين متداخلين (nested quantifiers): a+ جوه (...)+. المحرّك يقدر يقسّم سلسلة الحروف aaaa على المجموعات بعدد ضخم من الطرق: مجموعة واحدة فيها 4، أو 3+1، أو 2+2، أو 1+1+1+1، وهكذا.
طول ما المدخل مطابق، المحرّك بيلاقي حل بسرعة. المشكلة تظهر لما نحط حرف في الآخر يكسر المطابقة، زي aaaa!. هنا $ بيفشل، فالمحرّك بيرجع يجرّب كل توزيعة ممكنة قبل ما يعلن الفشل. عدد التوزيعات دي بيكبر بصيغة O(2^n) بالنسبة لعدد الحروف n. يعني كل حرف زيادة = ضِعف الزمن.
الافتراض المهم: الكارثة بتحصل بس لما النمط يقبل مطابقات متعدّدة متداخلة (ambiguity)، والمدخل مصمَّم عشان يفشل في آخر خطوة. بدون التداخل ده، الـ backtracking عادي ومش خطر.
الكود اللي بيثبت الانفجار بالأرقام
جرّب السكربت ده بنفسك في Python. بيقيس زمن مطابقة ^(a+)+$ مع مدخل بيفشل، وبيزوّد حرف واحد كل مرة:
