Regular expression Denial of Service - ReDoS

Açıqlama

Problemli Regex naïve alqoritmi

Müntəzəm İfadə naïve alqoritmi, hər bir vəziyyət və giriş simvolu cütü üçün bir neçə mümkün növbəti vəziyyətin ola biləcəyi sonlu vəziyyət maşını olan Qeyri-müəyyən Sonlu Avtomat(Nondeterministic Finite Automaton) (NFA) qurur. Sonra mühərrik girişin sonuna qədər keçid etməyə başlayır. Bir neçə mümkün sonrakı vəziyyət ola biləcəyi üçün deterministik alqoritmdən istifadə olunur. Bu alqoritm uyğunluq tapılana qədər (və ya bütün yollar sınanıb uğursuzluğa düçar olana qədər) bütün mümkün yolları (lazım olduqda) bir-bir sınayır.

Məsələn, Regex ^(a+)+$ aşağıdakı NFA ilə təmsil olunur:

aaaaX girişi üçün yuxarıdakı qrafikdə 16 mümkün yol var. Amma aaaaaaaaaaaaaaaaX üçün 65536 mümkün yol var və hər əlavə a üçün bu rəqəm ikiqatdır. Bu, naïve alqoritmin problemli olduğu ekstremal haldır, çünki o, bir çox yollardan keçməli və sonra uğursuz olmalıdır.

Diqqət yetirin ki, bütün alqoritmlər naïve deyil və əslində Regex alqoritmləri effektiv şəkildə yazıla bilər. Təəssüf ki, bu gün əksər Regex mühərrikləri təkcə “təmiz” Regeksləri deyil, həm də “genişlənmiş” Regeksləri “xüsusi əlavələrlə” həll etməyə çalışırlar, məsələn, həmişə effektiv şəkildə həll edilə bilməyən back-reference-lar. Beləliklə, Regex "genişləndirilməsə" belə, sadəlövh bir alqoritm istifadə olunur.

Evil Regexes

Hazırlanmış girişə ilişə bilsə, Regex "evil" adlanır.

Evil Regex nümunəsi aşağıdakıları ehtiva edir:

• Repetition-la qruplaşdırma

• Təkrarlanan qrup daxilində:

  • Repetition

  • Overlapping ilə alternativ

Evil Patterns nümunələri

• (a+)+

• ([a-zA-Z]+)*

• (a|aa)+

• (a|a?)+

• (.*a){x} for x \> 10

Yuxarıda göstərilənlərin hamısı girişə həssasdır aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa! (Daha sürətli və ya daha yavaş maşınlardan istifadə edərkən minimum giriş uzunluğu bir qədər dəyişə bilər).

ReDoS Controlling Input və Regex

Aşağıda həm girişi, həm də regexi idarə etdiyiniz ReDoS nümunələri verilmişdir:

function check_time_regexp(regexp, text){
    var t0 = new Date().getTime();;
    new RegExp(regexp).test(text);
    var t1 = new Date().getTime();;
    console.log("Regexp " + regexp + " took " + (t1 - t0) + " milliseconds.")
}

// This payloads work because the input has several "a"s
[
//  "((a+)+)+$",  //Eternal,
//  "(a?){100}$", //Eternal
    "(a|a?)+$",
    "(\\w*)+$",   //Generic
    "(a*)+$",
    "(.*a){100}$",
    "([a-zA-Z]+)*$", //Generic
    "(a+)*$",
].forEach(regexp => check_time_regexp(regexp, "aaaaaaaaaaaaaaaaaaaaaaaaaa!"))

/*
Regexp (a|a?)+$ took 5076 milliseconds.
Regexp (\w*)+$ took 3198 milliseconds.
Regexp (a*)+$ took 3281 milliseconds.
Regexp (.*a){100}$ took 1436 milliseconds.
Regexp ([a-zA-Z]+)*$ took 773 milliseconds.
Regexp (a+)*$ took 723 milliseconds.
*/