Skip to content

Regular Expression Denial of Service (ReDoS)

Gixy Check ID: regex_redos

ReDoS (Regular Expression Denial of Service) occurs when a regex pattern with certain structures causes catastrophic backtracking on specially crafted input, consuming excessive CPU time.

Why this matters

nginx uses PCRE regular expressions in several directives where user-controlled input is matched:

  • location ~ pattern - matches request URI
  • if ($var ~ pattern) - matches variables like $http_referer, $request_uri
  • rewrite pattern replacement - matches request URI
  • server_name ~pattern - matches Host header

An attacker who can craft input matching a vulnerable regex can cause nginx workers to hang, leading to denial of service with minimal attack resources.

Vulnerable patterns detected

1. Nested quantifiers (exponential backtracking)

When a quantifier (+, *, {n,m}) is applied to a group that itself contains a quantifier:

# BAD - (a+)+ causes exponential backtracking
location ~ ^/(a+)+$ {
    return 200;
}

# BAD - nested groups with quantifiers
location ~ ^/((ab)+)+/files$ {
    return 200;
}

# BAD - star inside plus
location ~ ^/(a*)+/path$ {
    return 200;
}

Attack input: /aaaaaaaaaaaaaaaaaaaaaaaaaab can cause the regex engine to try exponentially many paths before failing.

2. Overlapping alternatives with quantifiers (polynomial backtracking)

When alternatives in a group can match overlapping input and the group is quantified:

# BAD - 'a' is a prefix of 'ab'
location ~ ^/(a|ab)+$ {
    return 200;
}

# BAD - '.' matches everything including 'x'
location ~ ^/(.|x)+/path$ {
    return 200;
}

Safe patterns

# GOOD - simple character class
location ~ ^/[a-z]+$ {
    return 200;
}

# GOOD - bounded quantifier
location ~ ^/\d{1,10}$ {
    return 200;
}

# GOOD - non-overlapping alternatives
location ~ ^/(foo|bar)$ {
    return 200;
}

# GOOD - single quantifier on simple pattern
location ~ ^/api/v[0-9]+/users$ {
    return 200;
}

How gixy detects ReDoS

Gixy analyzes the parsed regex structure locally, without sending patterns to an external service and without executing attacker-controlled regexes. The default fast analysis detects:

  1. Nested quantifiers - any pattern where a variable-length quantifier contains another variable-length quantifier
  2. Overlapping alternatives - alternation groups inside quantifiers where branches can match the same input

For a more complete analysis, run:

pip install 'gixy-ng[deep]'
gixy --deep /etc/nginx/nginx.conf

Deep mode delegates the regex analysis to ReDoctor, a Python implementation of recheck's hybrid approach. ReDoctor combines automata analysis for exponential and polynomial ambiguity with bounded fuzzing in its safe custom regex VM. This catches non-local cases such as .*a.*a that simple nested-quantifier checks miss, and clears local false positives such as (a|ab)+ when the automaton proves the paths unambiguous.

ReDoctor is an optional dependency; normal Gixy and RPM installations keep using the built-in fast heuristics without it. Gixy keeps its nginx-specific pattern extraction and reporting. ReDoctor results that are unknown or invalid fall back to Gixy's default structural checks. Analysis stays local, and Gixy uses ReDoctor's quick profile with runtime recall disabled, so nginx patterns are never executed by Python's backtracking regex engine.

Recommendations

  1. Avoid nested quantifiers - restructure patterns to use single-level quantifiers
  2. Use non-overlapping alternatives - ensure alternatives don't share common prefixes
  3. Use bounded quantifiers - {1,100} instead of + or * where possible
  4. Prefer prefix/exact locations - use location /path or location = /path instead of regex when possible
  5. Run deep analysis before deploying - use gixy --deep nginx.conf to check the complete configuration locally

References

Harden NGINX with maintained RPMs

Use NGINX Extras by GetPageSpeed for continuously updated NGINX and modules on RHEL/CentOS/Alma/Rocky. Learn more.