ReDoS from an inefficient regular expression

Description

Nested repetitions such as (.+)+, (.*)+ or (r+){m,}, and ambiguous alternatives, can cause catastrophic backtracking. Matching may take exponential time as input grows. An attacker can submit a long near-match, such as repeated a characters followed by X, to occupy the CPU and delay or halt responses. In an event-loop runtime such as Node.js, one request may affect the whole service.

The actual cost depends on the pattern, input and engine. Nested repetition does not make every match exponential.

Potential impact

Long-running matches may delay or stop request processing.
Backtracking may consume excessive CPU, memory or stack resources.
API latency and timeouts may increase.
A small number of malicious requests may reduce the capacity of an entire instance.

Remediation

Remove nested or overlapping repetition. For example, replace /^_(__|.)+_$/ with /^_(__|[^_])+_$/ where that matches the required input language.
Use fixed lengths or bounds such as {0,64} where possible.
Limit input length before matching and reject inputs above the limit, for example 256 characters.
Consider an engine that guarantees linear-time matching, such as an RE2-based library, when its features fit the application.
Use linters and static analysis as aids, and also review input limits and engine behavior.
A request timeout does not interrupt a synchronous match. Use a worker or process that can be terminated, or an engine with enforceable limits.

Examples

Before

javascript

// Nested repetition may cause excessive backtracking
const express = require('express');
const app = express();

// Repeat the letter group: ^([a-z]+)+$
const usernameRegex = new RegExp("^([a-z]+)+$", "i");

app.get('/check', (req, res) => {
  const name = (req.query.name || '').toString();
  // No length limit and a risky expression
  if (usernameRegex.test(name)) {
    return res.send('ok');
  }
  res.status(400).send('invalid');
});

app.listen(3000);
// A long input such as 'a'.repeat(50000) + '!' may occupy the CPU

After

javascript

// Bounded expression and input length, with an optional RE2 alternative
const express = require('express');
// Optional: when using RE2
// const RE2 = require('re2');
const app = express();

// Remove nesting and specify a bound: ^[A-Za-z]{1,64}$
// Use the native RegExp
const usernameRegex = new RegExp("^[A-Za-z]{1,64}$");
// When using RE2:
// const usernameRegex = new RE2('^[A-Za-z]{1,64}$');

app.get('/check', (req, res) => {
  const name = String(req.query.name || '');

  // Check the length before matching as an additional defense
  if (name.length === 0 || name.length > 64) {
    return res.status(400).send('invalid');
  }

  if (!usernameRegex.test(name)) {
    return res.status(400).send('invalid');
  }
  res.send('ok');
});

app.listen(3000);

Explanation:

Before: Both the inner group and outer group in ^([a-z]+)+$ repeat. Long near-matches such as aaaa...! may cause extensive backtracking, blocking the Node.js event loop. The route also has no length limit.
After: The pattern removes the nested repetition and limits length explicitly. An RE2-based engine is an optional way to avoid backtracking behavior. These changes reduce the opportunity for crafted inputs to consume the CPU and delay the service.

References

CWE-1333