Validate input safely and prevent regex denial of service

The regex engines in JavaScript (V8), Python's re, Java, .NET by default, PHP's PCRE and Ruby backtrack: when a path fails, they return to the last choice and try another. A pattern is dangerous when one input can match in many ways and the input almost matches, so the engine tries every way before giving up. In ^(a+)+$ a run of n letters can be split between the two loops in 2^(n-1) ways, and a final "!" makes every split fail.

Quadratic cases need longer input but are easier to write by accident. Searching for \s+$ in a long run of spaces followed by "x" restarts at each space and rescans to the end. A trimming regex of that shape took Stack Overflow down for 34 minutes in July 2016, when a post contained about 20,000 consecutive whitespace characters. In Cloudflare's 27-minute outage in July 2019, a WAF rule containing .*(?:.*=.*) pushed CPUs serving HTTP traffic to nearly 100% worldwide.

The table shows the fastest of three runs on one Apple-silicon laptop. Absolute times vary by machine; the growth rate doesn't.

Each engine special-cases different patterns. Java 21 matched ^(a+)+$ instantly but stayed quadratic on \s+$, and (x+x+)+y took 23 seconds on 2,000 characters. .NET skipped the \s+$ work but not the nested loop. No backtracking engine is safe across the board, so fix the pattern or change engine.

Your own validation regexes are only part of the exposure. path-to-regexp generated a backtracking regex for Express routes with two parameters in one segment, such as /:a-:b (CVE-2024-45296); its 0.1.x line needed a second fix in 0.1.12 (CVE-2024-52798). The generated regex took 40 ms on a path with 8,000 repetitions and 162 ms on 16,000. semver (CVE-2022-25883) and cross-spawn (CVE-2024-21538) had the same class of bug, so keep dependencies current.

Look for any place where the engine can split the same characters more than one way, then ask what happens when the input almost matches. These shapes cause most cases:

• A quantified group whose body can match a variable amount of the same text: (a+)+, (\w+\s?)*, ([a-z0-9]+-?)*.
• Alternatives that overlap inside a loop: (\w|\d)+ took 422 ms on 27 characters in Node.js 26, though Python's re handled it instantly.
• Adjacent quantifiers that compete for the same characters, such as (x+x+)+y or .*(?:.*=.*).
• A quantifier followed by $ in an unanchored search, such as \s+$, which reruns from every start position.
• Any pattern assembled from user input.

This slug check looks harmless. Because the hyphen is optional, "aaaa" can be split into groups in many ways, and Node.js runs the match on the event loop. In a test, a 29-character request held the server for 1.1 seconds, and a normal request sent 20 ms later waited just as long.

import express from "express";

const app = express();

// Vulnerable: "-?" lets a run of letters split into groups in 2^(n-1) ways,
// and a near-miss such as "aaaa…a!" makes the engine try every one of them.
const SLUG = /^([a-z0-9]+-?)*$/;

app.get("/posts/:slug", (req, res) => {
  if (!SLUG.test(req.params.slug)) return res.status(400).send("invalid slug");
  res.send(`post ${req.params.slug}`);
});

export default app;

Make every repetition start with a character the previous one can't consume: here each loop iteration must begin with a hyphen, so there is only one way to match. Then check the type and length before the regex runs. The rewrite also rejects leading, trailing and doubled hyphens, which the original accepted. It rejected a 1,000,000-character near miss in under 10 ms. Fixes for other stacks are at /fix/regex-dos/.

// One way to match any input: each repetition must start with "-".
const SLUG = /^[a-z0-9]+(?:-[a-z0-9]+)*$/;

export function isSlug(value) {
  // typeof first: ?slug=a&slug=b arrives as an array in Express.
  return typeof value === "string" && value.length <= 64 && SLUG.test(value);
}

A timing assertion with a long near-miss input catches the next person who makes the pattern ambiguous again.

Static checks find most cases before review. eslint-plugin-regexp's recommended config includes no-super-linear-backtracking and no-dupe-disjunctions; add no-super-linear-move for quadratic cases. Together they flagged every vulnerable pattern in this guide and passed the rewrites. CodeQL's js/redos and py/redos queries flag exponential patterns, and js/polynomial-redos and py/polynomial-redos flag quadratic ones that user input reaches; Java, C# and Ruby have equivalents.

import { test } from "node:test";
import assert from "node:assert/strict";
import { isSlug } from "./slug.mjs";

test("accepts real slugs and rejects everything else", () => {
  for (const ok of ["a", "post-1", "2026-10-10-release"]) assert.ok(isSlug(ok), ok);
  for (const bad of ["", "-a", "a-", "a--b", "Post", "a_b", "a\n", "a".repeat(65), ["a", "b"], 42]) {
    assert.ok(!isSlug(bad), JSON.stringify(bad));
  }
});

test("near-miss inputs fail fast", () => {
  for (const attack of ["a".repeat(64) + "!", "a-".repeat(31) + "!", "a".repeat(1_000_000) + "!"]) {
    const start = performance.now();
    assert.equal(isSlug(attack), false);
    assert.ok(performance.now() - start < 10, `${attack.length} chars took too long`);
  }
});

Use re.fullmatch. With re.match and ^...$, the $ also matches before a trailing newline, so "abc\n" passes; .NET's $ behaves the same way, which is why the C# example below ends in \z. Since Python 3.11, possessive quantifiers and atomic groups stop the engine from re-splitting earlier repetitions. The possessive LEGACY pattern accepted exactly what the nested pattern accepted on every string of up to eight characters drawn from "a", "-" and "!", yet rejected a 100,000-character near miss in under 1 ms.

import re

SLUG = re.compile(r"[a-z0-9]+(?:-[a-z0-9]+)*")  # one way to match any input


def is_slug(value: object) -> bool:
    # fullmatch, not ^...$ with match(): "$" also matches before a trailing "\n".
    return isinstance(value, str) and len(value) <= 64 and SLUG.fullmatch(value) is not None


# Python 3.11+: if you must keep a nested pattern, a possessive loop stops the
# engine from re-splitting earlier repetitions after a later failure.
LEGACY = re.compile(r"(?:[a-z0-9]+-?)*+")

RE2 and engines built on its design (Go's regexp, Rust's regex crate, RE2/J) run in time linear in the input. The trade-off is syntax: they reject backreferences and lookarounds. In Node.js 26, V8's own linear engine is still reachable only through experimental flags: --enable-experimental-regexp-engine enables an l flag, and --enable-experimental-regexp-engine-on-excessive-backtracks switches engines after 50,000 backtracks by default. Use the re2 package in production instead.

A .NET Regex has no timeout by default. [RegularExpression] validation attributes default to 2,000 ms, and the REGEX_DEFAULT_MATCH_TIMEOUT AppContext setting changes the process-wide default. Prefer NonBacktracking; keep a short timeout for patterns that need lookarounds, and treat RegexMatchTimeoutException as invalid input. In a test, a 50 ms timeout fired at 51 ms on an input that would otherwise run for hours.

using System.Text.RegularExpressions;

public static partial class Validators
{
    // NonBacktracking runs in time linear in the input; \z, because $ also matches before a final \n.
    [GeneratedRegex(@"^[a-z0-9]+(?:-[a-z0-9]+)*\z", RegexOptions.NonBacktracking)]
    private static partial Regex Slug();

    public static bool IsSlug(string? value) => value is { Length: > 0 and <= 64 } && Slug().IsMatch(value);

    // A pattern that needs backtracking features gets a per-match time budget instead.
    private static readonly Regex Legacy =
        new(@"^(?!.*--)[a-z0-9-]+\z", RegexOptions.None, TimeSpan.FromMilliseconds(50));

    public static bool IsLegacySlug(string value)
    {
        try { return Legacy.IsMatch(value); }
        catch (RegexMatchTimeoutException) { return false; } // a timeout is a validation failure
    }
}

In Node.js, terminating a worker or running the match through vm with a timeout does interrupt it: on Node.js 26 both stopped, within about 100 ms, a match that would have run for over a minute. Python's re can't be stopped from another thread. A thread pool's result(timeout=0.1) didn't return until a 2.8-second match finished, because the matching thread holds the GIL. SIGALRM interrupts it in the main thread, and a process pool can terminate it. The third-party regex module takes a timeout argument. PHP's PCRE stops after 1,000,000 backtracks by default and preg_match returns false, which code must treat as a rejection. Ruby 3.2 added match memoization and Regexp.timeout.

Building a regex from user text hands the attacker the pattern. For literal search, escape the text: RegExp.escape (Node.js 24 and current browsers), re.escape, Regex.Escape or Pattern.quote; ASVS 5.0 (1.2.9) requires this. When users really write patterns, compile them with RE2 under a length cap. Microsoft warns that NonBacktracking protects against expensive input, not against malicious patterns.

import RE2 from "re2";

// Literal search text: escape it instead of compiling it (RegExp.escape, Node 24+).
export function literalMatcher(text) {
  return new RegExp(RegExp.escape(text), "iu");
}

// Patterns users write themselves: RE2 never backtracks, and it rejects
// backreferences, lookarounds and huge repetition counts with a SyntaxError.
export function userPattern(source) {
  if (typeof source !== "string" || source.length > 200) throw new RangeError("pattern too long");
  return new RE2(source, "iu");
}

Decide what each field may contain and reject everything else: an enum for fixed choices, type and range for numbers, length and structure for strings, required and permitted keys for objects. Denylists that hunt for dangerous strings miss encodings and break legitimate input. Validate on the server even when the browser checks too (ASVS 5.0 2.2.1, 2.2.2). Check what each character class means in your engine: in Python 3, \d and \w match any Unicode digit or letter, so "١٢٣" passes \d+; write [0-9] or pass re.ASCII.

Order matters. Decode input once, normalize it, then validate the exact value you will use (ASVS 5.0 1.1.1; CWE-180). A check for "../" on the raw value passes the fullwidth "．．／", which NFKC normalization later turns into "../". A value decoded once from %252e%252e%252f reads %2e%2e%2f; decoding it again after validation produces "../". Choose the normalization form deliberately, because NFKC folds characters that differ in meaning. /fix/path-traversal/ covers the path check that follows.

No standard says which copy of a repeated parameter wins, so frameworks disagree. A proxy or WAF that checks one copy while the application uses another lets a forbidden value through (ASVS 5.0 15.3.7). Reject repeated parameters you don't expect. The table shows how each framework tested read ?id=1&id=2 as a single value.

Type checks belong in validation too, because a value of the wrong type can slip past a check written for strings or crash the code after it.

• Check that each scalar really is a string before calling string methods; in Express 5 an array makes .toLowerCase() throw, and the request ends in a 500.
• Keep Express on the simple query parser unless you need nested objects; the extended parser builds them from ?user[role]=admin.
• Coercion hides bad input. Zod's z.coerce.number() turned "" into 0, "0x10" into 16 and ["7"] into 7, and z.coerce.boolean() turned "false" into true. Pydantic's default lax mode accepted "5" and True for an int.
• Compare with strict equality (ASVS 5.0 15.3.5). In PHP 8, "0e123" == "0e456" is still true.

A schema library turns these rules into one declaration. With z.strictObject, unknown keys fail, a repeated status arrives as an array and fails the enum, and the digit regex runs before the conversion to a number. In Ajv, keep coerceTypes off, set additionalProperties to false and pass RE2 as code.regExp: a nested pattern took 12.6 seconds through Ajv's default RegExp on 29 characters and 0.1 ms through RE2. In Java, Jakarta Validation's @Pattern uses java.util.regex and treats null as valid, so pair it with @NotNull and @Size.

import express from "express";
import { z } from "zod";

const ListOrders = z.strictObject({
  status: z.enum(["open", "shipped", "cancelled"]).optional(),
  limit: z.string().regex(/^[1-9][0-9]{0,2}$/).transform(Number).pipe(z.number().max(100)).optional(),
});

const app = express();
app.get("/orders", (req, res) => {
  const query = ListOrders.safeParse(req.query); // repeated keys arrive as arrays and fail here
  if (!query.success) return res.status(400).json({ error: "invalid query" });
  res.json(query.data); // { status?: "open" | "shipped" | "cancelled", limit?: number }
});

export default app;

Pydantic v2 checks pattern constraints with the Rust regex crate by default, so the nested slug pattern that took 2.7 seconds with regex_engine set to python-re ran in 0.06 ms. Patterns that need lookarounds fail when the model is built. strict=True stops "5" and True from becoming integers, and extra="forbid" rejects unknown fields.

from typing import Annotated, Literal

from pydantic import BaseModel, ConfigDict, Field, StringConstraints

# Pydantic's default regex engine is Rust's regex crate, which runs in linear time.
Slug = Annotated[str, StringConstraints(max_length=64, pattern=r"^[a-z0-9]+(?:-[a-z0-9]+)*$")]


class CreatePost(BaseModel):
    model_config = ConfigDict(strict=True, extra="forbid")  # no "5" -> 5, no unknown fields

    slug: Slug
    status: Literal["draft", "published"]
    priority: int = Field(ge=1, le=5)

Sources & further reading

The standards, specifications and documentation behind the guidance above. Each is the evidence for a claim on this page; consult it for detail beyond the defaults and versions listed here.

1. CWE-1333: Inefficient Regular Expression Complexity. CWE 4.20.
2. OWASP Input Validation Cheat Sheet: regular expressions
3. Cloudflare: details of the Cloudflare outage on July 2, 2019
4. Stack Exchange: outage postmortem, July 20, 2016
5. GitHub advisory GHSA-9wv6-86v2-598j: path-to-regexp outputs backtracking regular expressions (CVE-2024-45296)
6. Microsoft Learn: .NET regular expression options, NonBacktracking mode
7. Python 3.14 re module: possessive quantifiers, atomic groups and fullmatch. Python 3.14.8.
8. RE2 README: linear-time matching and unsupported backtracking-only constructs
9. OWASP ASVS 5.0.0, V1 Encoding and Sanitization (1.1.1, 1.2.9, 1.3.12). Version 5.0.0.
10. Express 5 migration guide: upgrade to Express v5 (req.query)

Reference information

Tags

Input validation and parsingDenial of service and resource limits

SDLC phase

Development

Role

DevelopersAppSec engineers

CAPEC attack patterns

• CAPEC-492 at MITRE
• CAPEC-460 at MITRE
• CAPEC-267 at MITRE
• CAPEC-71 at MITRE

Download this guide as Markdown

Continue exploring