బ్యాక్‌ట్రాకింగ్: ఒక అవలోకనం

అత్యాశతో కూడిన క్వాంటిఫైయర్ "ఓవర్‌షూట్" అయినప్పుడు, ఇంజిన్ బ్యాక్‌ట్రాకింగ్ని నిర్వహిస్తుంది: అది వెనక్కి అడుగులు వేస్తుంది, మరొక కాన్ఫిగరేషన్‌ని ప్రయత్నిస్తుంది, మళ్లీ ప్రయత్నిస్తుంది. సాధారణ నమూనాలపై అది కనిపించదు; పేలవంగా వ్రాసిన నమూనాలపై ఇది ** ఘాతాంకం** అవుతుంది మరియు సెకన్ల పాటు బ్రౌజర్‌ను స్తంభింపజేయండి. ఇది 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+)+), ఇంజిన్ విఫలమయ్యే ముందు ఘాతాంకమైన మార్గాల సంఖ్యను అంచనా వేస్తుంది. అక్షర తరగతులను మినహాయించి జెనరిక్ వైల్డ్‌కార్డ్‌లను భర్తీ చేయడం వలన బ్యాక్‌ట్రాకింగ్ మార్గాలను నాటకీయంగా తగ్గిస్తుంది.

దీనిని ప్రయత్నించండి

వ్యాయామం సమీక్షించండి

అదనపు సవాలు