كيفية تجنب التراجع الكارثي في التعبيرات النمطية (Regex)؟

يشير التراجع الكارثي للتعبيرات العادية إلى حقيقة أن التعبير العادي يعود للخلف بشكل مفرط عند التطابق، مما يتسبب في استخدام 100% من وحدة المعالجة المركزية (CPU) وإعاقة الخدمات العادية.

الخلفية

لقد قرأت مقالًا يوضح عملية اكتشاف وحل مشكلة التراجع العادي الذي يؤدي إلى استخدام 100% من وحدة المعالجة المركزية. المقال الأصلي طويل نوعًا ما، وقد واجهت مشاكل مماثلة مرتين من قبل أثناء تطوير OpenResty.

إليك ملخصًا مختصرًا حتى لا تضطر لقضاء الوقت في قراءة الخلفية.

1. محركات التعبيرات العادية لمعظم لغات البرمجة يتم تنفيذها باستخدام NFA القائم على التراجع (بدلاً من NFA القائم على Thompson).
2. يؤدي التراجع الكارثي إلى استخدام 100% من وحدة المعالجة المركزية إذا كان هناك الكثير من التراجعات.
3. يجب تحليل الـ dump باستخدام gdb أو systemtap لتحديد البيئة التشغيلية.
4. مثل هذه المشاكل يصعب اكتشافها قبل نشر الكود وتتطلب مراجعة كل تعبير عادي على حدة.

من وجهة نظر التطوير، فإن إصلاح التعبيرات العادية المشكلة هو نهاية القصة. على الأكثر، يمكن إضافة آلية أمان للحد من عدد التراجعات، مثل هذه في OpenResty.

lua_regex_match_limit 100000;

بهذه الطريقة، حتى لو كان هناك تراجع كارثي، سيتم الحد منه ولن يستخدم وحدة المعالجة المركزية بالكامل.

حسنًا، هل يبدو هذا مثاليًا بالفعل؟ دعنا نتجاوز مستوى التطوير وننظر إلى هذا من بعد آخر.

المهاجمون

فقط باستخدام جهاز واحد، يمكن إرسال طلب لإصابة الخادم على الجانب الآخر، وهذا ببساطة حلم القراصنة بالحصول على أسلحة نووية. مقارنة بهذا، فإن هجمات DDoS تبدو ضعيفة، حيث تتطلب حركة كبيرة وتكلفة عالية.

هذا الهجوم له اسم خاص به: ReDoS (RegEx Denial of Service).

نظرًا لأن التعبيرات العادية مستخدمة على نطاق واسع وتوجد في كل جزء تقريبًا من الخدمات الخلفية، فهناك فرصة للاستفادة من ذلك من خلال العثور على أحد الثغرات.

تخيل سيناريو حيث يكتشف أحد القراصنة ثغرة ReDoS في جدار الحماية (WAF) ويقوم بإرسال طلب لإسقاطه؛ أنت غير قادر على تحديد المشكلة في فترة زمنية قصيرة، ولا تدرك حتى أنها هجوم؛ تقوم بإعادة التشغيل أو إيقاف جدار الحماية مؤقتًا للحفاظ على استمرارية عملك؛ بينما يكون جدار الحماية معطلًا، يستخدم القرصان حقن SQL لسرقة قاعدة البيانات الخاصة بك. أنت، من ناحية أخرى، قد تكون لا تزال في الظلام تمامًا.

نظرًا للاستخدام الواسع للبرمجيات مفتوحة المصدر والخدمات السحابية، فإن التأكد من أن التعبيرات العادية التي تكتبها خالية من الثغرات ليس كافيًا. هذا موضوع آخر، وسنبدأ هنا بمناقشة التعبيرات العادية التي تكون تحت سيطرتنا فقط.

كيف يمكن اكتشاف مثل هذه التعبيرات العادية؟

الخطوة الأولى في حل المشكلات هي اكتشافها، ومحاولة اكتشافها جميعًا، والمعروفة أيضًا بالقدرة على اكتشافها بأمان.

توقع أن يتم اكتشاف القواعد المشكلة من خلال مراجعة يدوية للكود ليس أمرًا موثوقًا به. معظم المطورين ليس لديهم وعي أمني، وحتى إذا كانوا يبحثون عنها، فمن غير المرجح أن يتمكنوا من اكتشاف المشكلة في تعبير عادي معقد.

هنا تأتي الأدوات الآلية لتنقذ الموقف.

لدينا طريقتان آليتان لحل هذا.

• الاختبار الثابت

يمكن لهذه الأدوات مسح الكود للبحث عن التعبيرات العادية، ووفقًا لخوارزمية معينة، اكتشاف التعبيرات التي تحتوي على تراجع كارثي.

على سبيل المثال، RXXR2، والذي يتم تنفيذه بناءً على خوارزمية في ورقة بحثية تقوم بتحويل التعبير العادي إلى ε-NFA ثم البحث عنه، ولكنه لا يدعم التركيبات الموسعة للتعبيرات العادية، لذلك سيكون هناك تقارير مفقودة.

• الاختبار الديناميكي العشوائي (Fuzzing)

اختبار Fuzz هو طريقة عامة لاختبار البرمجيات تكتشف أعطال البرمجيات، تسرب الذاكرة، وغيرها من المشاكل من خلال إدخال كميات كبيرة من البيانات العشوائية على مدى فترات طويلة.

وبالمثل، يمكننا استخدام هذه الطريقة في اختبارات التعبيرات العادية. يمكننا إنشاء بيانات اختبار بناءً على التعبيرات العادية الموجودة، أو يمكننا إنشاؤها بشكل عشوائي تمامًا.

SlowFuzz هي واحدة من الأدوات مفتوحة المصدر، والتي تعتمد أيضًا على خوارزمية في ورقة بحثية، سيتم ذكر الورقة في نهاية هذا المقال، وهي أداة عامة ولا تقوم بمعالجة هيكل التعبير العادي، لذلك سيكون هناك تقارير مفقودة.

SDLFuzzer هي أداة متخصصة لاكتشاف ReDoS طورتها Microsoft منذ بضع سنوات، ولكنها لم تعد محفوظة.

لا يوجد الكثير من الأدوات المتاحة في هذا المجال، ولا يوجد الكثير من الاهتمام. ومع ذلك، كنت متحمسًا لاكتشاف ورقة بحثية حول ReDoS من قبل عدة أساتذة وطلاب دكتوراه من جامعة نانجينغ، وقاموا بنشر الأداة ReScue مع الورقة البحثية: https://2bdenny.github.io/ReScue/. هذه الأداة اكتشفت ثغرات ReDoS في عدة مشاريع مفتوحة المصدر.

إليك نتائج الاختبارات المقارنة في الورقة البحثية.

هل يمكن حلها بشكل نهائي؟

حتى إذا استخدمنا مثل هذه الأدوات، سيكون هناك حتمًا إنذارات خاطئة وإنذارات مفقودة، فهل هناك طريقة نهائية لحل ReDoS؟

ثم يجب أن نعود إلى جذر المشكلة لإيجاد الإجابة: محرك التعبير العادي يستخدم التراجع للتطابق.

ألن يكون الأمر جيدًا إذا تخلينا عن هذه الطريقة؟ نعم، هناك بالفعل العديد من التطبيقات الأخرى لمحركات التعبيرات العادية التي يمكن أن تحل المشكلة بشكل نهائي. جميعها تتخلى عن التراجع وتستخدم طريقة NFA/DFA الأوتوماتيكية للتنفيذ، الميزة هي أنها مناسبة للتطابق المتدفق وهي أيضًا أكثر أمانًا، العيب هو أنها لا تدعم العديد من التركيبات الموسعة للتعبيرات العادية، مثل المراجع الخلفية، والتي عادةً لا يتم استخدامها.

• Google RE2

Google RE2 هو أحد المشاريع مفتوحة المصدر الأكثر اكتمالًا. يدعم معظم تركيب PCRE، وهناك مكتبات للغات تطوير مثل Go وPython وPerl وNode.js، وتكلفة البدء والاستبدال منخفضة جدًا.

لنأخذ Perl كمثال ونرى إذا كان RE2 يمكنه تجنب مشاكل التراجع الكارثي.

لنلقي نظرة على هذا الرسم البياني المقارن للنتائج.

الكود كما يلي، يمكنك تجربته بنفسك إذا كنت مهتمًا.

time perl -e 'if ("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" =~ /a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa/) {print("hit");}'

40.80s user 0.00s system 99% cpu 40.800 total

يستغرق تشغيل هذا التعبير العادي 40.8 ثانية، وخلال هذه الفترة تكون وحدة المعالجة المركزية بنسبة 99%.

مع RE2، الفرق واضح جدًا.

time perl -e 'use re::engine::RE2; if ("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" =~ /a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa/) {print(" hit");}'

perl -e 0.00s user 0.00s system 34% cpu 0.011 total

• Intel Hyperscan

Intel Hyperscan هو أيضًا محرك تعبيرات عادية مشابه لـ RE2، وهناك مكتبات للغات مثل Perl وPython، لذا فإن البدء به ليس صعبًا للغاية.

فقط وفقًا لممارسة Intel، يتم ربطه أكثر بالمنصة، ويمكن تشغيله فقط على x86.

إذا كان هناك فائدة فريدة، فقد تكون القدرة على العمل بشكل أفضل مع مجموعة تعليمات Intel والأجهزة، مع تحسينات في الأداء، مثل دمجه مع DPDK الخاص بها.

Snort، أداة اكتشاف التسلل الشبكي مفتوحة المصدر، تستخدم أيضًا Hyperscan لاستبدال محرك التعبيرات العادية السابق، لذا يمكن للطلاب المألوفين مع Snort تجربته.

توسعات

إليك بعض الأوراق البحثية حول التعبيرات العادية، يمكن قراءتها كتوسعة إذا كنت مهتمًا.

1. SlowFuzz: Automated Domain-Independent Detection of Algorithmic Complexity Vulnerabilities: https://arxiv.org/pdf/1708.08437.pdf

2. Static Analysis for Regular Expression Exponential Runtime via Substructural Logics: https://arxiv.org/abs/1405.7058.pdf

3. ReScue: Crafting Regular Expression DoS Attacks: https://dl.acm.org/doi/10.1145/3238147.3238159

4. Regular Expression Matching Can Be Simple And Fast: https://swtch.com/~rsc/regexp/regexp1.html