الـ 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+)+$ مع مدخل بيفشل، وبيزوّد حرف واحد كل مرة:
import re, time
evil = re.compile(r"^(a+)+$")
for n in range(20, 31):
s = "a" * n + "!" # مدخل بيفشل المطابقة في آخر حرف
start = time.perf_counter()
evil.search(s)
elapsed = time.perf_counter() - start
print(f"n={n:>2} time={elapsed:8.3f}s")
المخرجات بتوضّح المضاعفة الأسّية. على جهاز عادي هتلاقي حاجة قريبة من كده: عند n=25 حوالي 0.6 ثانية، عند n=28 حوالي 5 ثواني، وعند n=30 أكتر من 20 ثانية. زوّد الرقم لـ 40 وهتستنى ساعات على مطابقة نص طوله 40 حرف بس. ده مش خطأ في جهازك، ده تعريف الانفجار الأسّي.
حادثة Cloudflare الحقيقية: 27 دقيقة والإنترنت واقف
في 2 يوليو 2019 الساعة 13:42 UTC، Cloudflare نشرت قاعدة جديدة في جدار الحماية (WAF) بتحاول تمسك أنماط JavaScript خبيثة. القاعدة كانت فيها الجزء المتفجّر .*(?:.*=.*) — .* متداخلة جوه .*، نفس فخ التداخل بالظبط.
Cloudflare بتعالج حوالي 10 ملايين طلب في الثانية. يعني 10 ملايين فرصة في الثانية عشان الـ regex ده يقابل نص بيفجّره. القاعدة اتنشرت على كل السيرفرات في العالم دفعة واحدة من غير canary ولا rollout تدريجي. النتيجة: استهلاك المعالج قفز لـ 100% على كل الأجهزة عالميًا في ثواني، والخدمة وقفت 27 دقيقة. المصدر الرسمي في آخر المقال بيشرح التفاصيل دقيقة بدقيقة.
الحل: محرّكات الوقت الخطّي (Linear-Time Engines)
الحل الجذري إنك تستخدم محرّك regex مبني على DFA/NFA ومبيعملش backtracking أصلاً، فبيضمن زمن O(n) مهما كان النمط. أشهرهم RE2 من Google — وهو بالظبط اللي انتقلت له Cloudflare بعد الحادثة. بدائل تانية:
- RE2 (C++ مع bindings لـ Python وGo وغيرهم)، وGo بيستخدمه في مكتبته القياسية
regexp. - RE2JS — منفذ RE2 لـ JavaScript. في اختبار موثّق، عالج نصًّا مؤذيًا 30,000 مرة في ~454 مللي ثانية، بينما محرّك
RegExpالأصلي اتعلّق أكتر من دقيقة و45 ثانية على تقييم واحد. - .NET 7 (2022) ضاف
RegexOptions.NonBacktrackingاللي بيضمن الوقت الخطّي. - مكتبة regex بتاعة Rust كمان بتضمن الوقت الخطّي.
مثال سريع في Python بمكتبة google-re2:
# pip install google-re2
import re2
pat = re2.compile(r"^(a+)+$")
print(pat.search("a" * 100000 + "!")) # بيرجع None فورًا، بدون تعليق
الـ trade-offs: إيه اللي بتكسبه وإيه اللي بتخسره
الوقت الخطّي مش ببلاش. RE2 وأمثاله مبيدعموش بعض المميزات اللي بتحتاج backtracking أساسًا:
- بتكسب: ضمان رياضي بزمن O(n)، ومناعة كاملة ضد ReDoS.
- بتخسر: الـ backreferences (زي
\1) والـ lookahead/lookbehind في أغلب هذه المحرّكات.
لو أنماطك بتعتمد على المميزات دي، عندك بديل أرخص: سيب المحرّك زي ما هو، بس حُط timeout على تنفيذ الـ regex. في .NET فيه Regex بيقبل matchTimeout. في Node تقدر تشغّل الـ regex في worker thread وتقتله لو عدّى حد زمني. التكلفة هنا: تعقيد إضافي في الكود، والـ timeout بيعالج العَرَض مش السبب.
متى لا تشغّل بالك
مش كل regex خطر. تجاهل الموضوع بأمان في الحالات دي:
- النمط بيشتغل على مدخلات ثابتة وموثوقة معروفة الطول (مثلاً قيم من ملف config انت كاتبه)، مش مدخل مستخدم.
- النمط مفيهوش مُكمِّمَات متداخلة ولا بدائل متداخلة (
(a+)+،(a|a)*،(.*)*). لو مفيش تداخل، مفيش انفجار. - طول المدخل محدود بسقف صغير مضمون قبل الوصول للـ regex.
الخطوة التالية
افتح كودك دلوقتي ودوّر على أي regex بيشتغل على مدخل مستخدم وفيه مُكمِّم متداخل. خُد كل واحد منهم، اختبره بمدخل مؤذي مصمَّم للفشل (زي "a"*40 + "!") مع timeout قدره ثانية واحدة. أي regex بيعدّي الثانية = ثغرة ReDoS. حوّله لـ RE2 أو أعِد كتابته بدون تداخل. أدوات زي redos-detector وrecheck بتفحص أنماطك تلقائيًا. ابدأ بالأنماط اللي على حدود النظام (WAF، فاليديشن الفورم، parsing الهيدرز) — دي أكتر نقطة الخطر فيها حقيقي.
المصادر
- Cloudflare — Details of the Cloudflare outage on July 2, 2019 (التقرير الرسمي عن الحادثة والنمط المتفجّر).
- OWASP — Regular expression Denial of Service (ReDoS).
- Regular-Expressions.info — Catastrophic Backtracking.
- Google RE2 — محرّك regex بزمن خطّي.
- RE2JS — منفذ RE2 إلى JavaScript (أرقام المقارنة ~454ms مقابل أكثر من دقيقة و45 ثانية).