التراجع: نظرة عامة

عندما "يتجاوز" محدد الكم الجشع، يقوم المحرك بالتراجع: فإنه يتراجع، ويحاول تكوينًا آخر، ويعيد المحاولة. على أنماط بسيطة ذلك غير مرئي؛ في الأنماط المكتوبة بشكل سيء، يمكن أن تصبح أسية و تجميد المتصفح لمدة ثواني. إنه جذر ReDoS (العادي تعبير رفض الخدمة).

Pattern: .*\d
Sample:  abc123def
Steps:
  1.  .*  consumes everything: "abc123def"
  2.  \d  fails (end of string).
  3.  Backtrack: .* drops 'f' -> "abc123de", \d fails on 'f'.
  4.  Backtrack: .* drops 'ef' -> "abc123d", \d fails on 'e'.
  5.  ... and so on until \d finds a digit: match = "abc123" + "?"... actually
       the pattern matches "abc123" because .* leaves "def" and \d looks at '3'? No: the
       backtrack continues and .* ends up being "abc12", \d=3.  Final match: "abc123".

يصل المحرك دائمًا إلى هناك، ولكن إذا احتوى المُحدِّد الكمي الجشع محدد كمية جشع آخر (على سبيل المثال (a+)+)، عدد التكوينات لمحاولة يمكن أن تنفجر.

أنماط كارثية

Pattern: (a+)+b
Sample:  aaaaaaaaaaaaaaaaaaaaa

لا يوجد أي زائدة b → يفشل النمط، ولكن للوصول إلى هناك، يحاول المحرك كل مرة التقسيم المحتمل لـ as. النمو الأسي: يمكنك تحقيق ذلك خلال 30 as انتظر لساعات.

مخاطر التراجع وReDoS

عندما يحتوي النمط على محددات كمية متداخلة أو متداخلة (على سبيل المثال (a+)+)، يقوم المحرك بتقييم عدد كبير من المسارات قبل الفشل. يؤدي استبدال أحرف البدل العامة باستبعاد فئات الأحرف إلى تقليل مسارات التراجع بشكل كبير.

جربه

تمرين المراجعة

التحدي الإضافي