فهم التعقب التراجعي في RegEx

فهم التَّعقُّب التَّراجِعي الكارثي في التعابير النَّمطيَّة (RegEx)

مقدِّمة عامَّة

التعابير النمطية (Regular Expressions) هي لغة وصفية مضغوطة صُمِّمت لتمكين المطوِّر من البحث في النصوص أو التحقُّق من بنيتها وفق أنماط محدَّدة بدقّة. وعلى الرغم من بساطتها الظاهرية، تُعَدُّ RegEx أداة قويَّة يمكنها – في حال أُسيء استخدامها – أن تتحوَّل إلى عبءٍ حقيقي على الأداء، خصوصًا عندما يحدث ما يُسمَّى التعقُّب التَّراجِعي الكارثي (Catastrophic Backtracking). تتجلّى هذه الظاهرة في ارتفاعٍ هائل في عدد المسارات التي يحاول المفسِّر تتبُّعها لتطابق النمط مع النصّ، ما يؤدِّي غالبًا إلى استهلاك غير متوقَّع للزمن والذاكرة، وقد يتسبَّب في تجميد التطبيق أو إيقاف خادم الويب بالكامل.

ماهية التعقُّب التَّراجِعي: لمحةٌ عن آليَّة عمل مُفسِّر RegEx

عند تنفيذ تعبير نمطي، ينتقل المُفسِّر خطوةً خطوة عبر النصّ ويحاول مقارنة كل رمز بالحرف المقابل في النمط. تستخدم كثير من المحرِّكات خوارزمية تُعرَف باسم NFA البطيئة (Backtracking NFA)، والتي تعتمد على فكرة تجربة مسار ثم الرجوع (Backtrack) إذا فشل المسار الحالي. فإذا تباينت الأحرف، يعود المُفسِّر إلى آخر نقطة قرار ويختبر فرعًا بديلًا.

عندما يحتوي النمط على تكرارات شرهة (Greedy Quantifiers) أو مجموعات بديلة متداخلة دون حدود واضحة، قد ينفجر عدد المسارات الممكنة انفجارًا أُسِّيًّا. هنا بالضبط يحدث التعقُّب التَّراجِعي الكارثي، إذ يحاول المُفسِّر استكشاف ملايين المسارات النظرية قبل أن يُقرّر أن النص لا يطابق النمط.

الأسباب الجذرية للتعقُّب التَّراجِعي الكارثي

دراسة حالة: تحليل نمط يُؤدِّي إلى انفجار أُسِّي

لننظر إلى التعبير التالي:

regex
CopyEdit
^(a+)+b$

وعلى النصّ:

nginx
CopyEdit
aaaaaaaaaaaaaaaaaaaa

يحاول المُفسِّر بدايةً مطابقة الجزء (a+)+ مع السلسلة الكاملة من الحروف ‎a‎، ثم يبحث عن ‎b‎ النهائي. عندما يعجز عن العثور عليه، يرجع خطوةً واحدة ويُقلِّص التكرار الخارجي بحرف، فيبقى حرف ‎a‎ أخير ربما يتطابق مع ‎b‎… وهكذا دواليك حتى يستنفد جميع التوزيعات الممكنة. يبيّن التحليل الرياضي أنّ عدد المسارات المحتملة يساوي تقريبًا 2ⁿ حيث n هو عدد الحروف ‎a‎ في النصّ، ما يعني أنّ 20 حرفًا فقط كافية لإجبار المُفسِّر على اختبار أكثر من مليون مسار.

المؤشِّرات العمليَّة على وجود المشكلة

1. ارتفاع استهلاك وحدة المعالجة CPU عند تمرير مدخلات كبيرة.

2. استجابة بطيئة أو تجمُّد مفاجئ في صفحة الويب التي تتحقَّق من حقول نموذجية.

3. ظهور استثناءات مهلة (Timeout) في الخادم الخلفي.

4. تقارير حماية التطبيقات (WAF/IDS) التي تُشير إلى هجمات ReDoS (Regular‑expression Denial of Service).

استراتيجيات وقائية لتجنُّب الكارثة

1. تقييد التكرارات الشرهة باستخدام الحدود المسبقة

استبدال النمط الشره .* بحدٍّ أكثر تحديدًا مثل:

regex
CopyEdit
[^\n\r]{0,100}

2. اعتماد التكرارات المتملِّكة (Possessive Quantifiers) أو النظرة المتقدمة السلبية

في لغات تدعمها (Java، Perl):

regex
CopyEdit
(a++)+

أو استعمال نظرة متقدمة للسماح بالتطابق مرةً واحدة:

regex
CopyEdit
^(?:(?!b).)*b$

3. إعادة كتابة البدائل المتداخلة

بدلًا من:

regex
CopyEdit
(cat|car|can)

يُعاد كتابتها:

regex
CopyEdit
ca[trn]

4. التقسيم المسبق للنصّ أو استخدام مكتبات تحليل متخصِّصة

في حالات نماذج HTML، يمكن التحقُّق من كل حقل على حدة بدل بناء تعبير هائل واحد يُعالج كل شيء.

5. الاستفادة من محرِّكات DFA أو خوارزميات Thompson NFA

مترجمات مثل RE2 من Google أو Rust regex crate تستند إلى خوارزمية تُنهي مطابقة RegEx في زمن خطي دون Backtracking.

خوارزمية RE2 مثالًا على التخلُّص من التراجع

صُمِّمت مكتبة RE2 كي تُشغِّل التعابير النمطية في زمن ‎O(n)‎ للمدخل النصي ‎n‎، عبر بناء مخطَّط حالات DFA يزحف على النصّ دون أي تراجع. قد يَنتج عن ذلك استهلاك أكبر قليلًا للذاكرة عند الإنشاء الأوّلي للحالة، لكنه يضمن ألّا تتجاوز المهلة الزمنية المقبولة حتى في مدخلات مُعادية الطول.

مقارنة بين NFA التراجعي وDFA المتقدِّم

آثار أمنية: هجمات حجب الخدمة بواسطة RegEx (ReDoS)

يمكن للمهاجم إرسال مدخلات مصمَّمة خصيصًا لإطلاق التعقُّب التَّراجِعي الكارثي، متسبِّبًا في شَلّ خدمة حرجة. يُصنَّف هذا الهجوم ضمن فئة حجب الخدمة على طبقة التطبيقات، وغالبًا ما يمرُّ دون رصدٍ إذا لم تُفعَّل محدِّدات معدل الطلب أو حدود المهلة.

خطوات عملية لتدقيق التعابير النمطية في المشاريع القائمة

1. فحص الكود بمُحلِّلات ثابتة قادرة على الكشف عن التكرارات الشرهة مثل ‎.*‎ المتداخلة.

2. إنشاء اختبارات حمولة (Stress Tests) بمدخلات طويلة غير متطابقة قصد قياس أداء RegEx.

3. تتبع نسبة CPU في الإنتاج وتفعيل تنبيه عند تجاوز عتبة محدَّدة أثناء تنفيذ الدوال التي تستخدم RegEx.

4. مراجعة الأطر (Frameworks) للتأكُّد من أنّها تُتيح ضبط مهلة للـ RegEx أو استخدام مكتبة DFA.

خاتمة

يظلُّ التعقُّب التَّراجِعي الكارثي خطرًا قائمًا في أي نظام يعتمد التعابير النمطية دون ضوابط صارمة، لا سيّما في البيئات التي تتلقَّى مدخلات من المستخدمين مباشرة. إن الوعي بأسبابه – من التكرارات الشرهة إلى البدائل المتداخلة – واعتماد ممارسات وقائية بما في ذلك إعادة كتابة الأنماط أو استخدام محرِّكات آمنة، يُشكِّل خطَّ الدفاع الأوّل ضد هجمات ReDoS ويحفظ استقرار التطبيق وأمنه.

المراجع

1. Cox, R. (2010). Regular Expression Matching Can Be Simple And Fast. Google Inc.

2. OWASP Foundation. Regular Expression Denial of Service – ReDoS Cheat Sheet.