बैकट्रैकिंग: एक सिंहावलोकन

जब एक लालची क्वांटिफायर "ओवरशूट" हो जाता है, तो इंजन बैकट्रैकिंग करता है: यह पीछे हटता है, दूसरे कॉन्फ़िगरेशन का प्रयास करता है, पुनः प्रयास करता है। सरल पैटर्न पर यह अदृश्य है; खराब तरीके से लिखे गए पैटर्न पर यह घातीय बन सकता है और ब्राउज़र को कुछ सेकंड के लिए फ़्रीज़ करें. यह 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+)+), तो इंजन विफल होने से पहले पथों की एक घातीय संख्या का मूल्यांकन करता है। चरित्र वर्गों को छोड़कर सामान्य वाइल्डकार्ड को बदलने से बैकट्रैकिंग पथ नाटकीय रूप से कम हो जाते हैं।

इसे अजमाएं

व्यायाम की समीक्षा करें

अतिरिक्त चुनौती