ব্যাকট্র্যাকিং: একটি ওভারভিউ

যখন একটি লোভী কোয়ান্টিফায়ার "ওভারশুট" করে, তখন ইঞ্জিনটি ব্যাকট্র্যাকিং সম্পাদন করে: এটি পিছিয়ে যায়, অন্য কনফিগারেশন চেষ্টা করে, পুনরায় চেষ্টা করে। সহজ নিদর্শন এটি অদৃশ্য; খারাপভাবে লিখিত প্যাটার্নে এটি সূচকীয় হয়ে যেতে পারে এবং সেকেন্ডের জন্য ব্রাউজার ফ্রিজ করুন। এটি 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 → প্যাটার্নটি ব্যর্থ হয়, কিন্তু সেখানে পৌঁছানোর জন্য ইঞ্জিন প্রতিবার চেষ্টা করে a এর সম্ভাব্য বিভাজন। ব্যাপ্তিসূচক বৃদ্ধি: 30 a এর সাথে আপনি পারবেন ঘন্টার জন্য অপেক্ষা করুন।

ব্যাকট্র্যাকিং এবং ReDoS এর বিপদ

যখন একটি প্যাটার্নে ওভারল্যাপিং বা নেস্টেড কোয়ান্টিফায়ার থাকে (যেমন (a+)+), তখন ইঞ্জিন ব্যর্থ হওয়ার আগে একটি সূচকীয় সংখ্যক পথের মূল্যায়ন করে। ক্যারেক্টার ক্লাস বাদ দিয়ে জেনেরিক ওয়াইল্ডকার্ড প্রতিস্থাপন করা ব্যাকট্র্যাকিং পাথগুলিকে নাটকীয়ভাবে হ্রাস করে।

চেষ্টা করে দেখুন

ব্যায়াম পর্যালোচনা করুন

অতিরিক্ত চ্যালেঞ্জ