Regular expression Denial of Service (ReDoS) is a type of Denial of Service (DoS) attack that exploits the fact that most regular expression (regex) implementations may exhibit exponential or super-linear complexity when processing certain input patterns.
This vulnerability can cause an application to consume excessive amounts of CPU resources, leading to performance degradation or making the application unresponsive.
Moreover, this condition will change the system and will deny all the requests to the server.
How ReDoS works
1. Regular expressions
Regular expressions are patterns used to match character combinations in strings. They are commonly used for validating, parsing, and manipulating text.
2. Vulnerable patterns
Certain regex patterns are susceptible to ReDoS. These patterns often involve nested repetitions, such as the use of the * (zero or more), + (one or more), and {n,} (n or more) quantifiers in a way that causes the regex engine to perform many backtracking operations.
For example, the pattern ^(a+)+$ is vulnerable because it can cause the regex engine to repeatedly attempt different ways of matching when given a long string of “a”s followed by a non-matching character.
3. Attack execution
An attacker crafts a string that triggers excessive backtracking in the regex engine. For the regex ^(a+)+$, an input like “aaaaaaaaaaaaaaaaaaaaa!” would cause the engine to explore many ways to match the string, consuming a significant amount of processing time.
4. Impact
During the time the regex engine is processing the malicious input, CPU resources are heavily consumed. This can slow down or crash the application, leading to a denial of service.
Example
The following is a complex expression that can take a large time frame to process.
^([a-zA-Z0-9])(([\-.]|[_]+)?([a-zA-Z0-9]+))*(@){1}[a-z0-9]+[.]{1}(([a-z]{2,3})|([a-z]{2,3}[.]{1}[a-z]{2,3}))$
What are the impacts of Regular Expression Denial of Service (ReDoS) attacks?
Regular Expression Denial of Service (ReDoS) attacks can have significant negative impacts on an application’s performance and availability. Here are some common impacts:
1. Performance degradation
Increased CPU usage: The application can experience a significant increase in CPU usage as the regex engine tries to process the crafted malicious input. This can lead to slower response times for legitimate users.
Memory consumption: In some cases, the regex engine may also consume a large amount of memory, exacerbating performance degradation.
2. Service unavailability
Application crashes: Excessive backtracking and resource consumption can cause the application to crash, resulting in service downtime.
Timeouts: The application may hit internal or external timeout limits, making it unable to process legitimate requests within the expected time frame.
3. Denial of Service (DoS)
Complete service outage: In severe cases, the application may become completely unresponsive, effectively causing a denial of service to all users.
Partial Denial of Service: Some parts of the application may become unusable while other parts remain functional, leading to partial service disruption.
4. Impact on dependent services
Cascading failures: If the affected application is part of a larger system or microservices architecture, the unavailability of one service can cause failures or degraded performance in other dependent services.
Load balancers and proxy servers: Increased load on the application can affect load balancers and proxy servers, potentially causing issues in routing traffic properly.
5. User experience
Delayed responses: Users may experience delays in response times, leading to frustration and poor user experience.
Failed transactions: Critical transactions might fail to be completed, affecting business operations and potentially leading to financial losses.
6. Reputation damage
Customer trust: Prolonged or repeated downtime can erode customer trust and lead to a loss of users or customers.
Brand image: Frequent service disruptions can harm the brand’s reputation, making it harder to attract and retain users.
7. Operational costs
Increased operational overhead: Mitigating the attack and restoring service can require significant effort from the development and operations teams.
Infrastructure costs: Higher resource consumption can lead to increased costs for cloud services or on-premises infrastructure.
8. Security concerns
Exploitation by attackers: Attackers can use ReDoS as a vector for further attacks, exploiting the application’s unavailability to bypass security measures or perform other malicious activities.
Potential data breaches: While ReDoS itself does not typically lead to data breaches; the disruption it causes can create opportunities for attackers to exploit other vulnerabilities.
How can you prevent Regular Expression Denial of Service (ReDoS) attacks?
Mitigating Regular Expression Denial of Service (ReDoS) attacks involves several strategies aimed at optimizing regex patterns, controlling input, and implementing safeguards to limit resource consumption. Here are effective measures to mitigate ReDoS attacks:
1. Optimize regular expressions
Avoid vulnerable patterns
Nested quantifiers: Avoid patterns with nested quantifiers that can lead to excessive backtracking, such as (a+)+ or (a aa)*. Backreferences: Be cautious with backreferences, which can also lead to performance issues.
Precompile and Cache Regex
Precompiling: Precompile regex patterns where possible to improve performance.
- Caching: Cache compiled regex patterns to avoid recompilation overhead.
2. Input validation and limitation
Limit input length
Max length: Restrict the length of input strings processed by regex to a reasonable size.
Sanitize input: Ensure input is sanitized to remove or escape potentially malicious content.
3. Implement timeouts
Timeouts
Regex timeouts: Implement timeouts for regex operations to abort if they take too long.
Overall timeouts: Use overall request timeouts to ensure the application doesn’t get stuck on a single request.
4. Resource limits
- CPU and memory limits: Set limits on CPU and memory usage to prevent any single operation from consuming excessive resources.
5. Use ReDoS-Safe libraries
Safe Regex libraries
RE2: Consider using regex libraries like Google’s RE2, which are designed to handle regex safely without causing excessive backtracking.
6. Monitoring and alerts
Monitor resource usage
CPU and memory monitoring: Monitor CPU and memory usage to detect unusual spikes that may indicate a ReDoS attack.
Logs and metrics: Analyze logs and metrics for patterns that suggest prolonged regex operations.
7. Penetration testing
ReDoS testing: Include ReDoS scenarios in your penetration testing to ensure your application can handle malicious regex inputs.
