חזרה לאחור: סקירה כללית

כאשר מכמת תאב בצע "חורגת", המנוע מבצע עקיבה לאחור: הוא נסוג אחורה, מנסה תצורה אחרת, מנסה שוב. על דפוסים פשוטים זה הוא בלתי נראה; על דפוסים כתובים בצורה גרועה זה יכול להפוך למעריכי ו להקפיא את הדפדפן לשניות. זה השורש של 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+)+), המנוע מעריך מספר מעריכי של נתיבים לפני כשל. החלפת תווים כלליים כלליים במחלקות אופי לא כוללות מפחיתה באופן דרמטי את נתיבים לאחור.

נסה את זה

סקירת התרגיל

אתגר נוסף