Finding Python ReDoS bugs at scale using Dlint and r2c

by Matt Schwager

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."

ReDoS backtracking gif

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:

ReDoS create job image

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:

ReDoS running job image

As findings begin to roll in we can use the built-in triager to investigate results:

ReDoS triager all findings image

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:

ReDoS triager single finding image

There was one finding in particular that piqued my interest:

ReDoS triager urllib finding image

The 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/ DUO138 catastrophic "re" usage - denial-of-service possible
Lib/urllib/ DUO138 catastrophic "re" usage - denial-of-service possible

The finding on line 2553 appears to be a false positive, but the finding on line 940 corresponds to the 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)
>>>',' * 64 + ' ')

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': '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.