ReDoS (Regular expression Denial of Service) Attacks

The Regular expression Denial of Service (ReDoS) is a Denial of Service attack, that exploits the fact that most Regular Expression implementations may reach extreme situations that cause them to work very slowly (exponentially related to input size). An attacker can then cause a program using a Regular Expression to enter these extreme situations and then hang for a very long time.

The Regular Expression naïve algorithm builds a Nondeterministic Finite Automaton (NFA), which is a finite state machine where for each pair of state and input symbol there may be several possible next states.

JavaScript Web Apps and Servers Vulnerable to ReDoS Attacks

JavaScript is a high-level, interpreted programming language. It is a language which is also characterized as dynamic, weakly typed, prototype-based and multi-paradigm.

JavaScript web apps and web servers are susceptible to a specific type of vulnerabilities/attacks known as regular expression (regex) denial of service (ReDoS).

These vulnerabilities take place when an attacker sends large and complex pieces of text to the open input of a JavaScript-based web server or app.

If the server component or an app library is not specifically designed to handle various edge cases, the attacker’s input can end up blocking the entire app or server for seconds or minutes at a time, while the server analyzes and pattern-matches the input.

Various programming languages and web server technologies have similar issues with the performance of pattern matching operations and ReDoS attacks, but they are vastly exaggerated in the case of JavaScript because of the single-threaded execution model of most JavaScript servers, where every request is handled by the same thread.

When a ReDoS attack hits, this ends up clogging the entire server, rather than slowing down one particular operation.

ReDoS (Regular expression Denial of Service ) attacks known since 2012

ReDoS attacks in the case of JavaScript servers were first detailed in a research paper published in 2012, but back then, JavaScript, and Node.js, in particular, weren’t the behemoth they are today on the web development scene, hence, this particular issue went largely ignored for another half of decade.

Subsequent research published in 2017 revealed that 5% of the total vulnerabilities found in Node.js libraries and applications were ReDoS (Regular expression Denial of Service) vulnerabilities.

But according to research presented at a security conference last week, the ReDoS (Regular expression Denial of Service) issue is gaining momentum in the JavaScript community because it has been left unaddressed for so many years.

Nearly 340 sites vulnerable to ReDoS attacks

Staicu and Pradel say the primary reason for these flaws is the lack of attention to the performance of regex matching, as most developers seem to be focused on accuracy, leaving big holes in their code that attackers can exploit using ReDoS attacks.

The two also took their research one step further. They devised a method of detecting these vulnerabilities on live websites without actually using the ReDoS exploit code.

They used this method to scan 2,846 popular Node.js-based sites, revealing that 339 —approximately 12%— were vulnerable to at least one ReDoS vulnerabilities.

Some ReDoS issues were patched

Besides JavaScript, Java is also known to be affected by ReDoS attacks. In 2017, researchers from the University of Texas at Austin created a tool named Rexploiter, which they used to find 41 ReDoS (Regular expression Denial of Service) vulnerabilities in 150 Java programs collected from GitHub.

More details about ReDoS vulnerabilities affecting JavaScript are available in a whitepaper titled “Freezing the Web: A Study of ReDoS Vulnerabilities in JavaScript-based Web Servers.” The paper is available for download from here or here, and was also presented at the 27th Usenix Security Symposium held last week in Baltimore, USA.