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

Displayed time zone: Guadalajara, Mexico City, Monterrey change

15:30 - 17:00
15:30
22m
Talk
Text Filtering and Ranking for Security Bug Report Prediction
Journal-First
Fayola Peters Lero - The Irish Software Research Centre and University of Limerick, Thein Than Tun , Yijun Yu The Open University, UK, Bashar Nuseibeh The Open University (UK) & Lero (Ireland)
DOI
15:52
22m
Talk
STADS: Software Testing as Species Discovery
Journal-First
Marcel Böhme Monash University
DOI
16:15
22m
Talk
The Impact of Regular Expression Denial of Service (ReDoS) in Practice: An Empirical Study at the Ecosystem Scale
Research Papers
James C. Davis Virginia Tech, USA, Christy A. Coghlan Virginia Tech, USA, Francisco Servant Virginia Tech, Dongyoon Lee Virginia Tech, USA
16:37
22m
Talk
FraudDroid: Automated Ad Fraud Detection for Android Apps
Research Papers
Feng Dong Beijing University of Posts and Telecommunications, China, Haoyu Wang , Li Li Monash University, Australia, Yao Guo Peking University, Tegawendé F. Bissyandé University of Luxembourg, Luxembourg, Tianming Liu Beijing University of Posts and Telecommunications, China, Guoai Xu , Jacques Klein University of Luxembourg, SnT