“Ever wondered, what is regular expression denial of service, or ReDoS, all about? Regular expressions, or regex help organizations to search, manipulate or validate text, but an attacker can manipulate inefficient regex patterns or use regex to launch a Denial of Service attack. Checkmarx looks at how these attacks work, and how to avoid ReDoS attacks in Application Security. ”
ReDoS attacks, (Regular expression Denial of Service attacks) can slow down an application, impacting availability or blocking legitimate requests from going through, and even taking a system offline altogether.
Unlike traditional Denial of Service (DoS) attacks where you need a large volume of requests to cause damage, even a single malicious request can lead to a successful ReDoS attack.
This article explains the basics of ReDoS attacks, looking at how regular expressions are used and exploited, and offering advice on how to avoid ReDoS attacks in your organization.
Understanding Regular Expressions
A regular expression, usually known as a “regex” is a sequence of characters which is used to search for one or more characters within a specific string. It works by applying a defined pattern to a text, made up of letters, numbers and special symbols. When you apply a regex pattern to any string, the engine will check the string to see if there is text that matches the pattern.
While some characters simply match themselves — such as letters like a,b,c etc, other characters have specific meanings in regex. \d matches any digit from 0-9, \w matches any letter digit or underscore character, and [] can be used to denote character classes, so for example [xyz] could be matched by x, y or z. In addition, users can include + to mean one or more of the preceding element. You can imagine how regex patterns can get complex, fast!
With additional advanced features, such as quantifiers which define how often an element should appear, anchors which specify position, and lookaheads and lookbehinds which allow matching based on what comes beforehand or afterwards, regex is a powerful tool for processing text. Use cases include:
- Searching: Making it faster or easier to find specific patterns or information in a large amount of text. For example, it could help to find phone numbers or email addresses.
- Validation: Ensuring that all data submitted meets specific criteria, such as validating that passwords meet the requirements for complexity and corporate governance.
- Replacement: Helping to replace parts of text, such as formatting information in a consistent way, or finding and replacing outdated information.
- Extraction: Supporting users in extracting specific parts of text, such as pulling all the dates from a log file, or uncovering particular structured data.
- Manipulation: Allowing users to split, trim or adapt strings based on patterns given, such as separating text into parts at each period, or trimming additional spaces.
What is ReDoS Attack?
ReDoS attack, meaning Regular Expression Denial of Service attack is a type of algorithmic complexity attack where attackers provoke a Denial of Service attack by taking advantage of the use of regex, and exploiting inefficient regex patterns. This causes excessive computational overhead, slowing down evaluation and therefore degrading the performance of an application.
When regex patterns involve multiple options or repetitions, this makes the engine work harder to explore all of the possibilities. In some cases, especially if a regex pattern contains nested quantifiers, they are particularly susceptible to ReDoS attacks, and the engine can be manipulated to enter a catastrophic backtracking state, where if there is a failure part way through the search, the engine tries again — searching the string repeatedly trying to find a match via different paths. Other forms of ReDoS attack can happen via regex injection, where an attacker intentionally injects malicious regex into your system, or through developers downloading malicious regex patterns unintentionally from online code repositories.
In any kind of ReDoS attack, the threat actor is intentionally providing or manipulating input that triggers inefficiencies. When an attacker launches a ReDoS attack, they provide an application with a malicious or evil string to be processed against a vulnerable regex pattern.
This exploits the weaknesses of a regex engine, and the excessive computational power needed to fulfill the request slows down the system, and perhaps crashes the processing server altogether, creating a Denial of Service.
Best Practices for ReDoS Attacks Prevention
A robust application security platform can help with how to avoid ReDoS attacks, implementing specific best practices that reduce risk and maintain optimal availability and performance. These include:
Analysis
Look for tools that can analyze regex patterns throughout the Software Development Life Cycle (SDLC) and alert to those which are inefficient, overly complex, or may be vulnerable to catastrophic backtracking. In some cases, your platform may be able to suggest auto-remediations or guided remediations to support developers in fixing the issue within the IDE.
Governance
To mitigate the impact of an attack, there are many policies that can be put in place. For example, security teams could limit the size of the input which is able to be processed to reduce the risk of overwhelming the system, apply rate limits to regex processing, or implement throttling mechanisms to limit the resources that regex operations can consume.
Monitoring
There are certain signs of a ReDoS attack, for example spikes in CPU usage, or regex operations which are taking longer than you would expect. Ensure you have alerts set up so that incident response can be swift if an attack has been successful. Behind the scenes, conduct regular code reviews to identify any vulnerable patterns, and consider implementing pen tests that simulate ReDoS attacks to evaluate defenses.
Training
Support developers with secure coding practices and tools, so that they can benefit from:
- The safest programming languages: Our research at Checkmarx has shown that Go can avoid disastrous behaviors that lead to a ReDoS attack where other languages cannot.
- Scanning of open source packages: Using malicious package detection and software composition analysis, developers can scan all codes or components from online code repositories before use.
- The ability to check their own regex patterns: Identifying and solving common inefficiencies and vulnerabilities at the earliest stages, that can otherwise lead to a ReDoS attack against your organization.
Remember: Training is most successful when solutions can be accessed from the existing workflows developers are used to, to reduce friction and encourage adoption.
A ReDoS attack can cause severe harm to an organization, crippling its ability to handle legitimate requests, slowing applications down to a crawl, and even causing complete system downtime.
To learn more about how Checkmarx One can provide holistic application security across your organization, and reduce the risk of common threats against your availability and performance, schedule a demo.