ReScue: crafting regular expression DoS attacks

Yuju Shen, Yanyan Jiang, Chang Xu, Ping Yu, Xiaoxing Ma, Jian Lu

Abstract

Regular expression (regex) with modern extensions is one of the most popular string processing tools. However, poorly-designed regexes can yield exponentially many matching steps, and lead to regex Denial-of-Service (ReDoS) attacks under well-conceived string inputs. This paper presents Rescue, a three-phase gray-box analytical technique, to automatically generate ReDoS strings to highlight vulnerabilities of given regexes. Rescue systematically seeds (by a genetic search), incubates (by another genetic search), and finally pumps (by a regex-dedicated algorithm) for generating strings with maximized search time. We implemenmted the Rescue tool and evaluated it against 29,088 practical regexes in real-world projects. The evaluation results show that Rescue found 49% more attack strings compared with the best existing technique, and applying Rescue to popular GitHub projects discovered ten previously unknown ReDoS vulnerabilities.

BibTeX

@inproceedings{Shen-al:ASE18,
  author    = {Yuju Shen and
               Yanyan Jiang and
               Chang Xu and
               Ping Yu and
               Xiaoxing Ma and
               Jian Lu},
  title     = {{ReScue:} crafting regular expression {DoS} attacks},
  booktitle = {ASE},
  pages     = {225--235},
  publisher = {{ACM}},
  year      = {2018},
}

ReScue: crafting regular expression DoS attacks

Abstract

Related papers