Geri izleme: genel bakış

Açgözlü bir nicelik belirteci "aşırıya kaçtığında", motor geri izleme gerçekleştirir: geri adım atar, başka bir konfigürasyonu dener, yeniden dener. Basit desenlerde görünmez; kötü yazılmış kalıplarda üstel hale gelebilir ve tarayıcıyı saniyeler boyunca dondurun. ReDoS'un köküdür (Normal Hizmet Reddi ifadesi).

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

Motor her zaman oraya varır, ancak açgözlü bir niceleyici şunları içeriyorsa başka bir açgözlü niceleyici (ör. (a+)+), konfigürasyonların sayısı denemek patlayabilir.

Felaket desenleri

Pattern: (a+)+b
Sample:  aaaaaaaaaaaaaaaaaaaaa

Takip yok b → model başarısız oluyor, ancak oraya ulaşmak için motor her yolu dener a'lerin olası bölümü. Üstel büyüme: 30 as ile şunları yapabilirsiniz: saatlerce bekleyin.

Geri izlemenin ve ReDoS'un tehlikeleri

Bir model örtüşen veya iç içe geçmiş niceleyiciler içerdiğinde (örneğin (a+)+), motor başarısız olmadan önce üstel sayıda yolu değerlendirir. Genel joker karakterlerin karakter sınıflarını hariç tutacak şekilde değiştirilmesi, geri izleme yollarını önemli ölçüde azaltır.

Deneyin

Alıştırmayı gözden geçirin

Ek zorluk