Quay lại: tổng quan

Khi bộ định lượng tham lam "vượt quá", động cơ sẽ thực hiện quay lại: nó lùi lại, thử cấu hình khác, thử lại. Trên các mẫu đơn giản, nó là vô hình; trên các mẫu viết kém, nó có thể trở thành số mũ và đóng băng trình duyệt trong vài giây. Nó là gốc của ReDoS (Thường xuyên biểu thức Từ chối dịch vụ).

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".

Động cơ luôn ở đó, nhưng nếu bộ định lượng tham lam chứa khác bộ định lượng tham lam (ví dụ: (a+)+), số lượng cấu hình để thử có thể phát nổ.

Mô hình thảm họa

Pattern: (a+)+b
Sample:  aaaaaaaaaaaaaaaaaaaaa

Không có dấu vết b → mẫu không thành công, nhưng để đạt được điều đó, động cơ sẽ thử mọi cách phân vùng có thể có của as. Tăng trưởng theo cấp số nhân: với 30 a giây bạn có thể đợi hàng giờ.

Nguy cơ quay lui và ReDoS

Khi một mẫu chứa các bộ định lượng chồng chéo hoặc lồng nhau (ví dụ: (a+)+), công cụ sẽ đánh giá số lượng đường dẫn theo cấp số nhân trước khi thất bại. Việc thay thế các ký tự đại diện chung bằng việc loại trừ các lớp ký tự sẽ làm giảm đáng kể các đường dẫn quay lui.

Hãy thử nó

Xem lại bài tập

Thử thách bổ sung