Keep regular expressions from stalling the server

How to do it

A backtracking engine can spend minutes on a short crafted string when a pattern nests repetition, such as (a+)+$ or ([a-zA-Z]+)*$. OWASP calls these evil patterns. In Node.js one such match blocks every other request, because the server runs your code on one thread. Go's regexp package guarantees time linear in the input, and RE2 bindings exist for most languages. .NET takes a match timeout and offers a non-backtracking option. Where you keep a backtracking engine, cap the input first, as Cap the size of every request and answer says. Remove nested quantifiers, and escape any user text that must go into a pattern. A linter rule, such as regexp/no-super-linear-backtracking in ESLint, finds many evil patterns in CI.

Examples

JavaScript example

import RE2 from 're2';

const MAX_SLUG_LENGTH = 100;
const SLUG = new RE2('^[a-z0-9]+(?:-[a-z0-9]+)*$');

export const isSlug = value => value.length <= MAX_SLUG_LENGTH && SLUG.test(value);

Python example

import re

MAX_SLUG_LENGTH = 100
SLUG = re.compile(r"[a-z0-9]+(?:-[a-z0-9]+)*")

def is_slug(value: str) -> bool:
    return len(value) <= MAX_SLUG_LENGTH and SLUG.fullmatch(value) is not None

How to check

On the test copy, send every field that a pattern checks 50,000 copies of a followed by !. Each answer arrives within 1 second. A small page fetched at the same time passes Prove one request cannot stall the site. A search of the code finds no pattern built from request data.

Sources

• OWASP on regular expression denial of service
• CWE-1333 Inefficient Regular Expression Complexity
• Go regexp package

Related rules

• API-93 Cap the size of every request body in API design
• TST-54 Prove one request cannot stall the site in Testing