Tue 6 Nov 2018 16:15 - 16:37 at Horizons 6-9F - Security Chair(s): Lucas Bang

Regular expressions (regexes) are a popular and powerful means of automatically manipulating text. Regexes are also an understudied denial of service vector (ReDoS). If a regex has super-linear worst-case complexity, an attacker may be able to trigger this complexity, exhausting the victim’s CPU resources and causing denial of service. Existing research has shown how to detect these superlinear regexes, and practitioners have identified super-linear regex anti-patterns heuristics that may lead to such complexity.

In this paper, we empirically study three major aspects of ReDoS that have hitherto been unexplored: the incidence of super-linear regexes in practice, how they can be prevented, and how they can be repaired. In the ecosystems of two of the most popular programming languages — JavaScript and Python – we detected thousands of super-linear regexes affecting over 10,000 modules across diverse application domains. We also found that the conventional wisdom for super-linear regex anti-patterns has few false negatives but many false positives; these anti-patterns appear to be necessary, but not sufficient, signals of super-linear behavior. Finally, we found that when faced with a super-linear regex, developers favor revising it over truncating input or developing a custom parser, regardless of whether they had been shown examples of all three fix strategies. These findings motivate further research into ReDoS, since many modules are vulnerable to it and existing mechanisms to avoid it are insufficient. We believe that ReDoS vulnerabilities are a larger threat in practice than might have been guessed.

Tue 6 Nov

fse-2018-research-papers
15:30 - 17:00: Research Papers - Security at Horizons 6-9F
Chair(s): Lucas Bang
fse-2018-Journal-First15:30 - 15:52
Talk
Fayola PetersLero - The Irish Software Research Centre and University of Limerick, Thein Than Tun, Yijun YuThe Open University, UK, Bashar NuseibehThe Open University (UK) & Lero (Ireland)
DOI
fse-2018-Journal-First15:52 - 16:15
Talk
Marcel BöhmeMonash University
DOI
fse-2018-research-papers16:15 - 16:37
Talk
James C. DavisVirginia Tech, USA, Christy A. CoghlanVirginia Tech, USA, Francisco ServantVirginia Tech, Dongyoon LeeVirginia Tech, USA
fse-2018-research-papers16:37 - 17:00
Talk
Feng DongBeijing University of Posts and Telecommunications, China, Haoyu Wang, Li LiMonash University, Australia, Yao GuoPeking University, Tegawendé F. BissyandéUniversity of Luxembourg, Luxembourg, Tianming LiuBeijing University of Posts and Telecommunications, China, Guoai Xu , Jacques KleinUniversity of Luxembourg, SnT