إعادة حجب الخدمة

تحدث أخطر أنواع المشاكل مع مطابقة التعبيرات النمطية المتراجعة، حيث يكون وقت تشغيل بعض الأنماط أسيًا بالنسبة لطول سلسلة الإدخال. ^{[ 8 ]} بالنسبة لسلاسل من${\displaystyle n}$عدد الأحرف، ووقت التشغيل هو${\displaystyle O(2^{n})}$يحدث هذا عندما يكون للتعبير النمطي ثلاث خصائص:

• يطبق التعبير النمطي التكرار ( +, *) على تعبير فرعي؛
• يمكن أن يتطابق التعبير الفرعي مع نفس المدخلات بطرق متعددة، أو يمكن أن يتطابق التعبير الفرعي مع سلسلة إدخال تمثل بادئة لتطابق محتمل أطول؛
• وبعد التعبير الفرعي المتكرر، يوجد تعبير يطابق شيئًا لا يطابقه التعبير الفرعي.

يمكن شرح الشرط الثاني بشكل أفضل من خلال مثالين:

• في (a|a)+$، يتم تطبيق التكرار على التعبير الفرعي a|a، والذي يمكن أن يتطابق aبطريقتين على كل جانب من جوانب التناوب.
• في (a+)*$، يتم تطبيق التكرار على التعبير الفرعي a+، والذي يمكن أن يطابق aأو aa، إلخ.

في كلا المثالين، استخدمنا $مطابقة نهاية السلسلة، محققين بذلك الشرط الثالث، ولكن من الممكن أيضًا استخدام حرف آخر لهذا الغرض. على سبيل المثال، (a|aa)*cيمتلك نفس البنية الإشكالية.

ستُظهر جميع التعبيرات النمطية الثلاثة المذكورة أعلاه زمن تشغيل أُسّيًا عند تطبيقها على سلاسل نصية من الشكل التالي:${\displaystyle a...ax}$على سبيل المثال، عند محاولة مطابقتها aaaaaaaaaaaaaaaaaaaaaaaaxباستخدام محرك تعبيرات التراجع، سيستغرق الأمر وقتًا طويلاً لإكماله، وسيتضاعف وقت التشغيل تقريبًا لكل عنصر إضافي aقبل النقطة x.

من الممكن أيضًا وجود عملية تراجع تستغرق وقتًا متعدد الحدود${\displaystyle O(n^{x})}$بدلاً من التوزيع الأسي. قد يُسبب هذا مشاكل أيضًا مع المدخلات الطويلة جدًا، على الرغم من قلة الاهتمام بهذه المشكلة لأن المدخلات الخبيثة يجب أن تكون أطول بكثير لإحداث تأثير ملحوظ. مثال على هذا النمط هو " a*b?a*c"، عندما تكون المدخلات عبارة عن سلسلة طويلة بشكل تعسفي من " a".

تم العثور على ما يُسمى بتعبيرات نمطية "خبيثة" أو ضعيفة في مستودعات التعبيرات النمطية على الإنترنت. تجدر الإشارة إلى أنه يكفي العثور على تعبير فرعي ضعيف لمهاجمة التعبير النمطي الكامل.

1. RegExLib، المعرّف = 1757 (التحقق من صحة البريد الإلكتروني) – انظر الجزء الأحمر^([a-zA-Z0-9])(([\-.]|[_]+)?([a-zA-Z0-9]+))*(@){1}[a-z0-9]+[.]{1}(([a-z]{2,3})|([a-z]{2,3}[.]{1}[a-z]{2,3}))$
2. مستودع تعابير التحقق من صحة OWASP ، اسم فئة Java - انظر الجزء الأحمر^(([a-z])+.)+[A-Z]([a-z])+$

هذان المثالان عرضة أيضًا للمدخلات aaaaaaaaaaaaaaaaaaaaaaaa!.

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

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

في حالة تطبيقات الويب، قد يستخدم المبرمج نفس التعبير النمطي للتحقق من صحة المدخلات على كلٍ من جانب العميل وجانب الخادم في النظام. يمكن للمهاجم فحص كود العميل، بحثًا عن تعبيرات نمطية خبيثة، وإرسال مدخلات مُصممة خصيصًا مباشرةً إلى خادم الويب لتعطيله. ^{[ 9 ]}

بينما تفتقر بعض مكتبات التعبيرات النمطية إلى آليات دفاع مدمجة ضد هجمات حجب الخدمة المُعاد تنفيذها (ReDoS)، مثل مكتبة C++ القياسية<regex> ، ومكتبة C POSIX <regex.h>^{[ 20 ]} ، ومكتبة Boostboost.regex (التي تستخدم التراجع، مما يؤدي إلى زمن تنفيذ أُسّي)، فإن مكتبات تعبيرات نمطية أخرى مُصممة خصيصًا لمنع هجمات حجب الخدمة المُعاد تنفيذها. ويتم ذلك باستخدام آلات الحالة المحدودة الحتمية، التي تعمل بزمن خطي يتناسب مع حجم المُدخلات.

استخدام مكتبة RE2 من جوجل للغة C++ : ^{[ 21 ]}

استيراد < re2 / re2 . h > ; استيراد std ;باستخدام std :: string_view ؛ باستخدام re2 :: RE2 ؛constexpr string_view TEXT = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa!" ; constexpr string_view PATTERN = "^(a+)+$" ;int main ( int argc , char * argv []) { bool isMatch = RE2 :: FullMatch ( TEXT , PATTERN ); std :: println ( "نتيجة المطابقة: {}" , isMatch ); }

استخدام regexالحزمة لـ Rust : ^{[ 22 ]}

استخدم التعبير النمطي :: التعبير النمطي ;نص ثابت : & str = "aaaaaaaaaaaaaaaaaaaaaaaaa!" ; نمط ثابت : & str = r"^(a+)+$" ;fn main () { // تُرجع الدالة Regex::new() قيمة Result<Regex, Error> ويجب فك تغليفها match Regex :: new ( PATTERN ) { Ok ( re ) => { let is_match : bool = re . is_match ( TEXT ); println! ( "نتيجة المطابقة: {}" , is_match ); } Err ( err ) => { eprintln! ( "فشل فك تغليف التعبير النمطي: {}" , err ); } } }

يمكن استخدام مهلات زمنية لإلغاء مهام التعبير النمطي إذا استغرقت وقتًا طويلاً.

تُعدّ خاصية المهلة الزمنية جزءًا لا يتجزأ من مكتبة .NET القياسية ، حيث يدعم الصنف System.Text.RegularExpressions.Regexخاصيةً معينة MatchTimeout. ^{[ 23 ]} فيما يلي مثال بلغة C# :

namespace Wikipedia.Examples ;باستخدام System ؛ باستخدام System.Text.RegularExpressions ؛public class Example { private const string Text = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa!" ; private const string Pattern = @"^(a+)+$" ;static void Main ( string [] args ) { try { Regex re = new ( Pattern , RegexOptions.None , TimeSpan.FromMilliseconds ( 100 ) ) ; bool isMatch = re.IsMatch ( Text ) ; Console.WriteLine ( $ "نتيجة المطابقة: { isMatch}" ); } catch ( RegexMatchTimeoutException ex ) { Console.WriteLine ( $ " انتهت مهلة عملية التعبير النمطي! { ex.Message } " ) ; } } }

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

توفر مكتبة التعبيرات النمطية في وقت الترجمة للغة C++ ( ctre ) من تطوير هانا دوسيكوفا، ctre::match<>دالة تقوم بتحليل التعبيرات النمطية أثناء الترجمة. ^{[ 24 ]} إذا تسبب نمط ما أثناء الترجمة في تجاوز constexprحد خطوات التقييم، فسيفشل التجميع. وقد تم اقتراحها لإضافتها إلى مكتبة C++ القياسية ، ولكنها لم تُدرج فيها حتى الآن. ^{[ 25 ]}

استيراد < ctre.hpp > ؛ استيراد std ؛​​باستخدام std :: string_view ؛constexpr string_view TEXT = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaa!" ;int main ( int argc , char * argv []) { // ctre::match<> هو نوع ctre::regex_results<> // تتم عملية المطابقة في وقت الترجمة عند وضع علامة constexpr constexpr bool isMatch = ctre :: match < "^(a+)+$" > ( TEXT ); std :: println ( "نتيجة المطابقة: {}" , isMatch ); }

توفر لغة البرمجة Dstd.regex.ctRegex خاصية التعبير النمطي في وقت الترجمة. ^{[ 26 ]}

في لغة Rust، يمكن إنجاز التعبيرات النمطية في وقت الترجمة بواسطة بعض المكتبات الخارجية، مثل lazy_regex و ctreg و regex-automata ، والتي توفر وحدات ماكرو متنوعة للتحقق من صحة التعبيرات النمطية في وقت الترجمة. ^{[ 27 ]}

في لغة C#، توجد System.Text.RegularExpressions.GeneratedRegexAttributeخاصية تقوم بإنشاء تطبيق للتعبير النمطي من خلال توليد المصدر في partialطريقة ما. ^{[ 28 ]}

namespace Wikipedia.Examples ;باستخدام System ؛ باستخدام System.Text.RegularExpressions ؛public partial class Example { [GeneratedRegex(@"^(a+)+$")] private static partial Regex Pattern ();private const string Text = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaa!" ;static void Main ( string [] args ) { // يتم تنفيذ منطق IsMatch() أثناء التشغيل bool isMatch = Pattern (). IsMatch ( Text ); Console . WriteLine ( $"نتيجة المطابقة: {isMatch}" ); } }