المستوى المطلوب: محترف. يفترض هذا المقال إلمامك بالتعابير النمطية (Regex) وبأساسيات تعقيد الخوارزميات. لو التعابير النمطية جديدة عليك تمامًا، اقرأه على مهل — الأمثلة تشرح الفكرة قبل التعريف العلمي.

تعبير نمطي واحد، مكتوب بحسن نية للتحقق من مدخل، يقدر يرفع استهلاك المعالج إلى 100% ويجمّد خدمتك بمدخل طوله 30 حرفًا. المشكلة اسمها التراجع الكارثي (Catastrophic Backtracking)، والثغرة الناتجة اسمها ReDoS. هنا هتعرف ليه بتحصل بالظبط، وإزاي تقيسها بنفسك، وإزاي تقفلها.

لماذا يتحوّل تعبير نمطي بريء إلى هجوم حرمان من الخدمة

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

معظم محرّكات Regex الشائعة (PCRE، وJava، وJavaScript، ومكتبة re في بايثون) تستخدم خوارزمية تراجع (backtracking). الخوارزمية دي مرنة وبتدعم مزايا زي الـ backreferences، لكن ثمنها إن زمن تنفيذها ممكن يقفز أسّيًا مع طول المدخل. الافتراض إن أي مدخل نصّي بسيط بيتعالج بسرعة — والافتراض ده غلط مع أنماط معيّنة.

المفهوم: أولًا بمثال بسيط

تخيّل موظف بيحاول يوزّع 30 كرة على صندوقين، والشرط إن ما يفضلش أي صندوق فاضي، وفي الآخر لازم تكون آخر كرة حمرا. لو كل الكرات زرقا، هو مش هيكتشف إن الشرط مستحيل من أول محاولة. هيجرّب كل توزيعة ممكنة: 29 كرة في الأول وواحدة في التاني، 28 و2، وهكذا، وكل توزيعة يعيد تقسيمها من جوّه. عدد المحاولات بينفجر، وهو بيدوّر على حل غير موجود أصلًا.

محرّك الـ Regex بيعمل نفس الحاجة بالظبط. لمّا يقابل نمط زي (a+)+$ مع نص كله a منتهي بحرف مش مطابق (زي !)، بيوزّع الحروف على الكمّيتين المتداخلتين بكل الطرق الممكنة قبل ما يستسلم.

المفهوم: الآن علميًا وبدقّة

الكمّيتان المتداخلتان (a+)+ بتخلّقان غموضًا: سلسلة من n حرف a ممكن تتقسّم على المجموعات الداخلية بعدد يتناسب مع 2^n طريقة. طالما في تطابق ناجح، المحرّك بيلاقي أول طريقة وبيقف. لكن لو المدخل فشل في آخر خطوة (بسبب $ اللي مش هيتحقق)، المحرّك مجبر يجرّب كل التقسيمات قبل ما يعلن الفشل. النتيجة تعقيد زمني أسّي O(2^n) بدل الخطي.

الرقم اللي بيصدم: عند 30 حرفًا فقط، 2^30 يساوي تقريبًا 1.07 مليار خطوة. ده بيترجم لثوانٍ من المعالجة على نواة واحدة، مقفولة 100%، من غير أي شبكة أو قاعدة بيانات في المعادلة.

قِس المشكلة بنفسك

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

import re, time

# نمط هش: كمّيتان متداخلتان على نفس الحرف
pattern = re.compile(r"(a+)+$")

for n in range(24, 32):
    s = "a" * n + "!"                 # مدخل يجبر المحرّك على الفشل في آخر خطوة
    start = time.perf_counter()
    pattern.search(s)
    took = time.perf_counter() - start
    print(f"{n:>2} chars -> {took:8.3f}s")

مخرجات تقريبية على جهاز عادي: عند 26 حرفًا أقل من ثانية، عند 28 حوالي 1.5 ثانية، عند 30 حوالي 6 ثوانٍ، عند 31 حوالي 12 ثانية. الزمن بيتضاعف مع كل حرف تضيفه. ده هو التراجع الكارثي بالتفاصيل: مدخل صغير جدًا، تكلفة ضخمة.

السيناريو الواقعي: انقطاع Cloudflare

في 2 يوليو 2019، خرجت خدمات Cloudflare عالميًا لمدة تقارب 27 دقيقة. السبب لم يكن هجومًا خارجيًا، بل قاعدة WAF جديدة فيها تعبير نمطي يحتوي .*(?:.*=.*). النمط ده فيه نفس المرض: كمّيات متداخلة تسبّب تراجعًا كارثيًا. القاعدة اتنشرت على كل الأجهزة، فقفز استهلاك المعالج إلى 100% على شبكتهم بالكامل. درس مباشر: التعبير النمطي الهش مش مجرد بطء، ده سطح هجوم — أي مستخدم يقدر يبعت مدخلًا مصمّمًا خصيصًا يشلّ عاملًا كاملًا (worker) بطلب واحد.

الحل: ثلاث خطوات بترتيب الأولوية

1. احذف الكمّيات المتداخلة. غالبًا النمط ممكن يتكتب من غير تداخل. (a+)+ بيساوي منطقيًا a+. راجع كل نمط فيه (X+)+ أو (X*)* أو (X+)* — دي الأنماط الخطيرة.
2. استخدم محرّكًا خطيًا. RE2 (من Google) بيضمن زمنًا خطيًا O(n) لأنه ما بيعملش تراجع أصلًا. في بايثون: pip install google-re2. في Go محرّك regexp القياسي مبني على RE2 افتراضيًا، فهو محصّن ضد ReDoS.
3. لو لازم تفضل على محرّك تراجع، استخدم المجموعات الذرّية أو الكمّيات الاستحواذية لمنع التراجع: (?>a+)+$ أو (a++)+$ (متاحة في مكتبة regex في بايثون وفي Java وPCRE). وحُط سقفًا صارمًا لطول المدخل قبل التمرير للـ Regex.

# البديل الآمن: RE2 — زمن خطي، بلا تراجع
import re2   # pip install google-re2

pattern = re2.compile(r"(a+)+$")
# مدخل بمئة ألف حرف يكتمل في أجزاء من الميلي ثانية بدل التجمّد
print(bool(pattern.search("a" * 100000 + "!")))

الـ trade-off هنا

RE2 بيكسبك أمانًا وزمنًا خطيًا مضمونًا، بس بتخسر مزايا معيّنة: مفيش دعم للـ backreferences ولا lookaround في RE2. لو أنماطك محتاجة المزايا دي فعلًا، فالبديل هو البقاء على محرّك تراجع مع مجموعات ذرّية + حدّ لطول المدخل + مهلة تنفيذ (timeout). التكلفة: تعقيد أعلى في المراجعة، وخطر إن نمط جديد يتسرّب من غير تحصين. المكسب: احتفاظك بكامل قدرات التعبير النمطي.

متى لا تشغل بالك بهذا

لو التعبير النمطي بيشتغل على مدخلات ثابتة تحت سيطرتك بالكامل (أسماء ملفات في سكربت بناء مثلًا)، وطولها محدود وما بييجيش من مستخدم خارجي، فخطر ReDoS شبه معدوم — مش محتاج تعيد هندسة أي حاجة. المشكلة بتظهر بس لمّا مدخل غير موثوق يوصل لنمط فيه غموض. كمان لو أنماطك كلها بسيطة وخطية (بلا كمّيات متداخلة)، فأنت آمن أصلًا حتى مع محرّك تراجع.

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

افتح كل نمط Regex في كودك بيشتغل على مدخل من المستخدم، ودوّر على الأنماط الثلاثة الخطيرة: (X+)+ و(X*)* و(X+)*. لأول نمط تلاقيه، شغّل عليه سكربت القياس اللي فوق بمدخل فاشل متزايد الطول. لو الزمن بيتضاعف مع كل حرف، ده هو التراجع الكارثي — حصّنه بـ RE2 أو مجموعة ذرّية فورًا.

المصادر

• Cloudflare — "Details of the Cloudflare outage on July 2, 2019" (blog.cloudflare.com): التقرير الرسمي لحادثة التعبير النمطي.
• OWASP — "Regular expression Denial of Service - ReDoS" (owasp.org): تعريف الثغرة وأنماطها الخطيرة.
• Russ Cox — "Regular Expression Matching Can Be Simple And Fast" (swtch.com/~rsc/regexp): الأساس النظري لـ RE2 والفرق بين NFA والتراجع.
• Google RE2 — مستودع ومواصفات المحرّك (github.com/google/re2).
• توثيق بايثون الرسمي لمكتبتَي re وregex (docs.python.org)، وتوثيق حزمة google-re2.