بیک ٹریکنگ: ایک جائزہ

جب ایک لالچی کوانٹیفائر "اوور شوٹ" کرتا ہے، تو انجن بیک ٹریکنگ انجام دیتا ہے: یہ پیچھے ہٹتا ہے، دوسری ترتیب آزماتا ہے، دوبارہ کوشش کرتا ہے۔ سادہ پیٹرن پر پوشیدہ ہے؛ ناقص تحریری نمونوں پر یہ تعارف اور بن سکتا ہے۔ براؤزر کو سیکنڈوں کے لیے منجمد کریں۔ یہ 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+)+)، تو انجن ناکام ہونے سے پہلے راستوں کی ایک کفایتی تعداد کا جائزہ لیتا ہے۔ کریکٹر کلاسز کو چھوڑ کر عام وائلڈ کارڈز کو تبدیل کرنے سے ڈرامائی طور پر بیک ٹریکنگ کے راستے کم ہو جاتے ہیں۔

اسے آزمائیں

ورزش کا جائزہ لیں۔

اضافی چیلنج