Regular expressions (regexes) are specially encoded strings of texts used to define search patterns. Without them helping users access specific information and log into their accounts, applications would not be as efficient as they are today. While they are useful, regexes have a fault in their configurations, resulting in application vulnerabilities that can be exploited in a number of ways. In particular, cyber criminals know that a poorly constructed regex opens up the possibility for an exploit, making them a common target for an application attack such as regular expression denial-of-service (ReDoS) attacks.
What Is a ReDoS Attack?
A ReDoS attack is a denial-of-service (DoS) attack that exploits an application’s exponential evaluation of regular expressions. Regex implementations evaluate inputs exponentially based on their size; so, the larger the input string, the longer it takes for the application to match and execute requests. An attacker can exploit this exponential time vulnerability by creating a long string that overwhelms or crashes the application. DoS attacks are used to overwhelm applications with traffic, making them inaccessible to users. Application disruptions and outages can have wide-ranging implications—from degradation in operational efficiency, to reduced revenues, to damaged brand reputation. Other repercussions include penalties from sensitive data exposure, which result in $50,000 per attack on average.
Attackers can launch DoS attacks without any prior knowledge or hacking experience, using application attacking methods like brute force. Brute-force attacks consist of bad actors taking guesses in order to pass authentications or gain access into user or administrative accounts. Login and authentication pages are the most targeted areas in applications, highly vulnerable to brute-force attacks. Most applications are configured to limit the number of login attempts as a means to protect from brute-force attacks; however, they lack the ability to detect brute-force attack behavior. Attackers know this and can increase the efficiency of DoS attacks using the help of malicious bots. These bots are configured to try out numerous attempts at one time, which dramatically surpasses what individual cyber criminals can instigate on their own. Attackers have the option to use individual bots or create a network of malicious bots that can target an application's authentication page all at once, thus crashing the application. As bots make up 40% of traffic, they compromise a large concern to application security.
While bots pose a huge problem in application security, sophisticated DoS attacks are both hard to prevent and detect, slipping past most legacy security measures. These attacks take advantage of a vulnerability in the regex engine that matches inputs to its corresponding string. They take a few requests to execute and take little traffic to overwhelm the system.
How Does a ReDoS Attack Work?
Most regular expressions have exponential time worst-case complexity—increasing evaluation time exponentially in relation to regex input size. These naive algorithms are read by regex engines that display nondeterministic finite automation (NFA), where each input can have several possible next states. The next step is a deterministic algorithm that attempts to find the next possible match, trying all NFA paths one by one until either a match is found or all possible attempts were exhausted. Attackers can create corrupted regular expressions, converting them into a malicious regex that hangs the system. When a regex engine cannot find a match between a string and a regular expression, it begins to backtrack, searching for a different path of execution over and over, hanging the application.
Attackers can exploit applications that use regular expressions by sending carefully crafted inputs to those that contain an evil regex or by injecting an evil regex into applications that accept user input. For those containing a vulnerability that attackers can exploit, bad actors can submit a valid value and then change the request. This malicious input hangs applications, leaving the regex engine looking for a match in an event known as catastrophic backtracking. Backtracking can go on for ages, leaving the application on a continuous search from which it cannot come out.
How To Prevent a ReDoS Attack
ReDoS attacks are preventable by eliminating the use of regexes in application development altogether. However, it is not so simple, as using other means of validating strings opens up the possibility for more serious application vulnerabilities like SQL injection or cross-site scripting (XSS). Therefore, securing applications from these vulnerabilities requires a combination of methods, including continuous monitoring of an application’s behavior.
Building Better Regular Expressions
Besides avoiding regular expressions altogether, an effective defense against ReDoS attacks is to build better expressions. Using certain signs in regex like '+' or '*' could leave room for a malicious regex insertion attack due to their ambiguity. These values are prone to backtracking, only needing a well-constructed algorithm to leave them hanging. In addition to avoiding these special characters in the construction of regular expressions, grouping with any kind of repetition, alternation, or overlapping should be avoided to prevent the possibility of hanging the application.
Filter and Sanitize Inputs
Another way to prevent and block ReDoS attacks is to filter and sanitize inputs and analyze incoming traffic. Filtering traffic enables developers to specify parameters of searches, which involves a lot of complex mathematics. Algorithms used to create regexes are “intuitive,” programmed to find the fastest and most optimal solution to evaluation. The issue here goes back to the configuration of filters and sanitizers, each option specific to the types of data it catches and analyzes. These filters provide a means of protection, but they still leave the possibility for a ReDoS attack out in the open if they are not constructed properly.
Instrumentation Shifts Application Security Left and Extends It Right Into Production
An important starting point in preventing ReDoS attacks is to shift application security left in development by embedding security in applications. Doing so empowers developers to continuously detect and remediate vulnerabilities while they write code. This reduces security debt—minimizing the likelihood that vulnerabilities will slip into production while streamlining the time required to fix vulnerabilities. At the same time, security instrumentation virtually eliminates false positives that consume valuable time in triage, diagnosis, and remediation.
Security instrumentation also enables organizations to extend security into production. Runtime application self-protection (RASP) blocks ReDoS attacks, which can be complex. Legacy perimeter defenses cannot continuously monitor application behavior in runtime and stop the insertion of malicious regexes until it is too late. Extending security into production using security instrumentation, security operations (SecOps) teams can pinpoint attacks that connect with vulnerabilities that they can exploit and block them before they can successfully exploit them. RASP affords application security for applications in production—continuous and point-in-time protection.