How to Prevent ReDoS in APIs and API Gateways

APIs, API frameworks and API gateways evaluate regular expressions against client input all the time: in routes, in validation rules, in OpenAPI schemas and in gateway policies. Preventing ReDoS has two parts: write expressions that cannot be slowed down, and limit what an attacker can send to them. For an introduction to ReDoS, read ReDoS Attacks on APIs and Gateways.

1. Catastrophic Backtracking: Overlapping Wildcards

The most common cause is several .* or .+ in one expression, separated by a character that . can also match. Route patterns of APIs are a typical example:

^/articles/(.*)/(.*)/(.*)/comments$

^/articles/(.*)/(.*)/(.*)/comments$

For a path that almost matches, the engine tries every way to split the input among the three groups. With n characters that is about n³ attempts. The run time grows with the cube of the input length: double the input, and the run time grows eight-fold.

The fix is almost always to say what a field must not contain:

^/articles/([^/]*)/([^/]*)/([^/]*)/comments$

^/articles/([^/]*)/([^/]*)/([^/]*)/comments$

[^/] is a character class. The square brackets list the characters that are allowed at this position, and a ^ right after the opening bracket turns the list around: [^/] stands for any character except a slash. With *, [^/]* matches any number of characters that are not slashes, for example 2026 or redos.

Now each group stops at the next /, there is only one way to split the input, and the run time is linear.

2. How to Write Safe Regular Expressions

Most dangerous expressions can be rewritten with a few simple rules. The table shows each rule with an expression to avoid and a safe alternative.

3. Safe Regular Expressions in OpenAPI

OpenAPI documents use regular expressions extensively. Do not avoid them: restricted strings protect an API against injection and other attacks. Instead, make them safe with the following techniques.

3.1 Anchor Patterns

In OpenAPI, a pattern is not anchored automatically: [0-9]{5} also accepts abc12345xyz, and the engine retries it at every position. So when a pattern should describe the whole value, which is often the case, start it with ^ and end it with $:

zipCode:
  type: string
  pattern: ^[0-9]{5}$

zipCode:
  type: string
  pattern: ^[0-9]{5}$

3.2 Limit the Length of Variable Patterns

A pattern with an open-ended quantifier such as *, + or {2,} can match values of any length. Combine such a pattern with maxLength, so that validators that check the length first never run the expression on a long value. The anchored zipCode above has a fixed length and needs no maxLength, because it fails after a few characters. The slug below, for article URLs like redos-in-apis, can vary in length, so it is anchored and limited:

slug:
  type: string
  maxLength: 80
  pattern: ^[a-z0-9]+(-[a-z0-9]+)*$

slug:
  type: string
  maxLength: 80
  pattern: ^[a-z0-9]+(-[a-z0-9]+)*$

3.3 Limit the Length of Formats

The same applies to the format keyword: a format such as email is often checked with a regular expression and accepts values of any length. So give the email below a maxLength as well:

email:
  type: string
  format: email
  maxLength: 254

email:
  type: string
  format: email
  maxLength: 254

3.4 Use Enums for Known Values

Where the allowed values are known, use an enum instead of a pattern. Like status below, it needs no regular expression at all:

status:
  type: string
  enum: [open, shipped, delivered]

status:
  type: string
  enum: [open, shipped, delivered]

4. Prevention in API Gateways

4.1 Prefer Prefix Routing over Regex Routing

Routing runs for every request, before authentication, so a slow routing expression can be triggered by anyone who can reach the gateway.

And URLs can be long: web servers, proxies and gateways commonly accept request lines of up to 8 KB, such as Apache, nginx and Tomcat with their default settings. As the samples have shown, a few kilobytes are enough to keep a regular expression busy for seconds.

For example, instead of the regular expression ^/articles/.*, route with the plain prefix /articles/. It matches the same requests and needs no regular expression at all.

4.2 Authenticate and Rate Limit First

Put authentication and rate limiting before policies that apply regular expressions such as path rewriters, so that only known clients can reach them.

4.3 Set Limits

Restrict the size of certain input. The time a regex needs grows with the size of the input. Gateways provide options or plugins that help to enforce those limits:

• Request line: the maximum length of the method, path and query. Most APIs need far less than the common default of 8 KB.
• Headers: the maximum size of a single header and of all headers together. Without such a limit, a single header can be several megabytes long. Be aware that cookies and JSON Web Tokens in the Authorization header can be quite large.
• Body: the maximum size of the request body.
• Values in the body: the maximum length of strings in JSON or XML, enforced with OpenAPI maxLength or with JSON and XML protection.

4.4 Treat Gateway Configuration Like Code

Keep it in version control, review new regular expressions, and test them before deployment.

5. Prevention in API Frameworks

5.1 Constrain Path Parameters, Not Whole Paths

A simple constraint on a single parameter, like {id:[0-9]+} in Spring, cannot run past the parameter. A regular expression over the whole path can.

@GetMapping("/articles/{id:[0-9]+}/comments")
public List<Comment> comments(@PathVariable long id) { ... }

@GetMapping("/articles/{id:[0-9]+}/comments")
public List<Comment> comments(@PathVariable long id) { ... }

5.2 Never Build a Regular Expression from Client Input

A search term that ends up in a pattern lets the client choose the expression. Escape it, for example with Pattern.quote() in Java, or use plain string matching.

// Dangerous: the client chooses the regular expression
Pattern.compile(term).matcher(title).find();

// Safe: the term is matched literally
Pattern.compile(Pattern.quote(term)).matcher(title).find();

// Even simpler: no regular expression at all
title.contains(term);

// Dangerous: the client chooses the regular expression
Pattern.compile(term).matcher(title).find();

// Safe: the term is matched literally
Pattern.compile(Pattern.quote(term)).matcher(title).find();

// Even simpler: no regular expression at all
title.contains(term);

5.3 Use a Safe Engine Where the Platform Offers One

Go and Rust use regex engines with linear run time, RE2/J brings the same to Java, and .NET supports match timeouts and RegexOptions.NonBacktracking.

RE2/J has the same API as java.util.regex, but guarantees linear run time:

com.google.re2j.Pattern p = com.google.re2j.Pattern.compile("^/articles/(.*)/(.*)/(.*)/comments$");
p.matcher(path).matches();

com.google.re2j.Pattern p = com.google.re2j.Pattern.compile("^/articles/(.*)/(.*)/(.*)/comments$");
p.matcher(path).matches();

In .NET, a regular expression can run without backtracking, or with a timeout:

var safe = new Regex(@"^/articles/(.*)/(.*)/(.*)/comments$", RegexOptions.NonBacktracking);
var limited = new Regex(@"^/articles/(.*)/(.*)/(.*)/comments$", RegexOptions.None, TimeSpan.FromMilliseconds(100));

var safe = new Regex(@"^/articles/(.*)/(.*)/(.*)/comments$", RegexOptions.NonBacktracking);
var limited = new Regex(@"^/articles/(.*)/(.*)/(.*)/comments$", RegexOptions.None, TimeSpan.FromMilliseconds(100));

5.4 Keep Libraries Up to Date

Routing and validation libraries have had ReDoS vulnerabilities of their own. Package managers report known vulnerabilities in dependencies, for example:

npm audit

npm audit

6. Test and Review

6.1 Test with Hostile Input

Try a few thousand repetitions of the separator characters of your expression, with an ending that does not match, for example /articles/ followed by 2,000 slashes. Measure the time and double the input. If the time grows much faster than the input, rewrite the expression. Add these inputs to your automated tests, so that a later change cannot bring the problem back.

6.2 Static Analysis

Static analysis tools find many vulnerable regular expressions without running them. CodeQL and SonarQube report inefficient regular expressions in source code, and dedicated checkers such as recheck analyze a single expression and even generate an attack string for it. Most tools only scan source code, so extract the patterns from OpenAPI documents and gateway configurations and check them as well.

6.3 AI-Assisted Review

AI code assistants are good at spotting overlapping wildcards and nested quantifiers, and at suggesting a safe rewrite. Ask them to review the regular expressions in your code, OpenAPI documents and gateway configuration. Like static analysis, they can miss problems or report false ones, so confirm each finding and each rewrite with a test.

6.4 Review Regularly in CI/CD

A single review is not enough: new routes, OpenAPI documents and gateway policies add new regular expressions all the time. Apply DevOps principles and treat these checks like any other quality gate. Integrate the hostile-input tests and the static analysis into your CI/CD pipeline, so that every change to code, OpenAPI documents and gateway configuration is checked automatically before it is deployed.

For the features of Membrane API Gateway that apply regular expressions, with safe example configurations, read ReDoS Protection in Membrane API Gateway.

For more API security topics, see the API security overview.