ReDoS stands for regular expression denial-of-service. ReDoS bugs occur when a specially crafted string is passed to an inefficient regular expression causing it to take a very long time to complete. The references section at the end contains resources for a more complete introduction to ReDoS bugs, but let's start with a few examples.
One type of inefficient expression occurs with nested quantifiers. A simple
example would be (a+)+. I know, why would anyone ever use a regular
expression like this? Imagine "a" is a more complex sub-expression. Don't
worry, we'll get into more complex examples and real-world bugs later. Another
type of inefficient expression occurs with mutually inclusive alternation. More
simply, these are either/or expressions with overlapping character space like
([a-z]|a)+. Both these inefficient expressions must also contain a pattern
after the inefficient portion that cannot be matched against, like
(a+)+b. This causes backtracking, and in the inefficient case it causes
what's called "catastrophic backtracking."
The engine backtracks step-by-step through a long string. Note the debugger had to halt to avoid ReDoS.
To automate finding these types of bugs we've added heuristics for detecting inefficient regular expressions into Python static analysis tooling. From here, we ran the tooling against a large corpus of open source Python projects to detect ReDoS bugs at scale.
Dlint is a static analysis tool for encouraging best coding practices and ensuring Python code is secure. A new rule has been added to Dlint to search for inefficient regular expressions when using the Python re module: DUO138. Detecting if complex regular expressions can exhibit catastrophic backtracking is a difficult task, and normal input will rarely surface these types of bugs. Catastrophic backtracking can impact the security and availability of an application, thus opening the door for denial-of-service attacks. To mitigate this risk, and more efficiently detect these types of bugs, we should look to automated tooling to help us solve the problem. Once automated tooling is built we can run it at scale and work toward eliminating bug classes.
The r2c distributed analysis platform allows developers, security researchers, and code sleuths alike to run static analysis tooling across thousands of repositories to detect bugs at scale. To run Dlint on the r2c platform we must first turn it into an r2c "analyzer." This artifact can be found in the dlint-r2c repository. Once we have our analyzer built we can run it and go bug hunting.
Bug Hunting
When running an analysis job we must first choose an analyzer and a set of codebases to run it against, or an "input set" in r2c's platform:
r2c provides a useful list of default input sets to choose from, such as the top 5000 PyPI packages, Python repositories that use the Flask web framework, the top 1000 NPM packages, or you can always generate a custom input set. Once a job is running we can monitor its progress:
As findings begin to roll in we can use the built-in triager to investigate results:
Running Dlint across such a large corpus produced many findings. For a quick first pass I scanned the results for findings in commonly used projects that I recognized. The advantages of such a large result set are twofold: first, we can report true positives to the offending project to improve their resilience to ReDoS, and second, we can use false positives as a means for improving our detection algorithms in Dlint. Individual findings can be investigated further to determine if they're a true or false positive:
There was one finding in particular that piqued my interest:
The _urllib2_fork.py file seems to be a vendored copy of the Python
urllib2 module (moved to
urllib in Python 3). I wonder
if the same issue exists in the Python source tree? We can investigate further
by running Dlint manually against the repository:
$ python -m flake8 --select=DUO138 Lib/urllib/
Lib/urllib/request.py:940:10: DUO138 catastrophic "re" usage - denial-of-service possible
Lib/urllib/request.py:2553:13: DUO138 catastrophic "re" usage - denial-of-service possibleThe finding on line 2553 appears to be a false positive, but the finding on
line 940 corresponds to the _urllib2_fork.py finding and is a true positive.
This part of the urllib.request module handles HTTP authentication,
so a DoS bug may have security implications. Let's look at the finding a bit
closer:
rx = re.compile('(?:.*,)*[ \t]*([^ \t]+)[ \t]+'
'realm=(["\']?)([^"\']*)\\2', re.I)The finding was flagged due to nested quantifiers in the (?:.*,)* portion of
the regular expression. Since "." and "," overlap (dot means any character) we
can cause catastrophic backtracking. We simply need to repeat a comma and then
include a character causing the expression to backtrack:
>>> import re
>>> rx = re.compile('(?:.*,)*[ \t]*([^ \t]+)[ \t]+realm=(["\']?)([^"\']*)\\2', re.I)
>>> rx.search(',' * 64 + ' ')
...Spins...Looking at the context in urllib.request more closely, this regular expression
is used to handle a server response when attempting HTTP basic or proxy
authentication. So a server sending a specially crafted response could cause a
DoS on the client. Here's a more complete example:
>>> from urllib.request import AbstractBasicAuthHandler
>>> auth_handler = AbstractBasicAuthHandler()
>>> auth_handler.http_error_auth_reqed(
'www-authenticate',
'unused',
'unused',
{
'www-authenticate': 'Basic ' + ',' * 64 + ' ' + 'foo' + ' ' + 'realm'
}
)Note that both urllib.request.HTTPBasicAuthHandler and
urllib.request.ProxyBasicAuthHandler inherit from AbstractBasicAuthHandler.
This finding resulted in Python bpo-39503 and CVE-2020-8492.
Dlint and r2c's distributed analysis platform also found the following ReDoS bugs:
To find bugs like these and others check out r2c's Semgrep, distributed analysis platform, and the Dlint static analysis project.
