Preventing ReDoS When Parsing FOIA Request Text with Regex #

Within Email & Form Parsing Pipelines, the regex tier that extracts statutory fields is the single component most exposed to a denial-of-service crafted by a hostile submitter. A public records inbox accepts text from anyone, and a single adversarial body can drive a naive pattern into catastrophic backtracking that pins a CPU for seconds or minutes. This page shows how to recognize the vulnerable patterns, rewrite them so they run in linear time, and wrap every match in the input bounds, timeouts, and audit-logged rejections that keep one malicious request from stalling the queue for everyone else.

Problem Framing & Statutory Requirement #

A regular-expression denial of service — ReDoS — exploits patterns whose backtracking cost grows exponentially with input length. When a pattern contains a quantified group that itself contains a quantifier, and the two can match the same characters in more than one way, a crafted string forces the engine to explore an astronomical number of match paths before it gives up. The classic shape is (a+)+$ fed a long run of a followed by a non-matching character: every partition of the run is retried. In a FOIA parser, the danger is not academic. The intake stage is where the statutory clock starts — the federal Freedom of Information Act fixes a 20-business-day response window under 5 U.S.C. § 552(a)(6)(A)(i), and state analogues impose their own — so an ingestion worker wedged by one payload is not merely a performance bug; it delays every request behind it and can cause an agency to miss deadlines it cannot prove it ever began processing.

The threat model is specific: the request body is untrusted input, submitted by a member of the public, that a pattern will scan character by character. Two properties therefore have to hold for every regex the parser runs against that body. First, bounded work: the time to accept or reject any input must grow at most linearly with its length, so no submitter can convert a short string into unbounded compute. Second, fail-safe rejection: when a pattern cannot complete within a strict deadline, the parser must abandon it, log the rejection with the request’s correlation identity, and escalate the payload to human review rather than hang the worker. A parser that silently blocks on a pathological input is worse than one that rejects a valid request, because the block is invisible until the queue backs up and deadlines slip.

Prerequisites & Environment Setup #

• Python 3.11+ for dataclasses and structured exception handling.
• The third-party regex module for two features the standard-library re lacks: atomic groups and possessive quantifiers (?>...) / a++, and a per-call timeout= argument that raises rather than blocks. The standard library is used for everything else to keep the audit surface small.
• A worker-level timeout mechanism as defense in depth — signal.setitimer on a single-threaded worker, or a subprocess/thread deadline where signals are unavailable — so even a pattern that slips through pattern review cannot run unbounded.
• Append-only audit access — the parser needs write-only access to an audit sink to record rejections, and no standing access to the fulfillment store. Enforce that split per Security Boundary Configuration so a wedged or exploited parser cannot reach records it has no business reading.

The patterns themselves are shared with the deterministic extraction tier documented in Parsing Multi-Format FOIA Submissions with Python Regex; this page hardens the engine that runs them.

The Defense Stack #

No single control is sufficient. A safe parser layers four independent defenses so a payload that defeats one still hits the next: an input-length bound caps the work any pattern can be asked to do, a timeout guard abandons a match that runs long, an atomic-group or possessive pattern removes the backtracking that causes the blow-up in the first place, and a fail-safe reject-and-log path turns any breach into an audited escalation rather than a hung worker.

Step-by-Step Implementation #

1. Recognize the vulnerable pattern #

The tell-tale shape is a quantifier applied to a group that itself contains a quantifier over an overlapping character class — nested quantification with ambiguity. The pattern below looks harmless and even parses correctly on well-formed input, but on a long run of its inner character followed by a failing character, the engine retries every possible split. The point here is to recognize the shape, not to run it against a hostile string; the demonstration deliberately matches only a short, safe literal.

import re

# VULNERABLE: an outer + over an inner \w+ that can partition the same run
# many ways. On a crafted input this backtracks catastrophically. Shown for
# recognition only — never run against untrusted or long input.
VULNERABLE = re.compile(r"^(\w+\s?)+:$")

# Safe *because the input is a short trusted literal*, not because the pattern
# is safe. This illustrates the shape without triggering the blow-up.
assert VULNERABLE.match("case id:") is not None

# The same danger hides in field extractors, e.g. a naive "requester" matcher:
#   r"(?:name\s*)+[:\-]\s*(.+)+$"   <-- nested (.+)+ is the red flag

The reliable way to catch these before they ship is a lint step that flags nested quantifiers and unbounded .*/.+ inside a repeated group, plus a rule that every pattern run against untrusted text must carry an explicit upper bound on repetition.

2. Rewrite with atomic groups and bounded quantifiers #

The structural fix removes the ambiguity. An atomic group (?>...) or a possessive quantifier a++ tells the engine that once it has matched a span, it must never give those characters back — which is exactly the backtracking that ReDoS exploits. Replacing greedy nesting with an atomic, bounded rewrite makes the match linear in the input length. The third-party regex module supports both constructs (the standard-library re does not before Python 3.11’s limited support), so the parser standardizes on it.

import regex  # third-party: atomic groups, possessive quantifiers, per-call timeout

# SAFE REWRITE: possessive/atomic and explicitly bounded. The (?>...) atomic
# group cannot give back what it matched, so there is no exponential retry, and
# the {0,80} cap bounds repetition so work is linear in input length.
SAFE_REQUESTER = regex.compile(
    r"(?:name)\s*[:\-]\s*(?>[A-Za-z0-9 ,.'\-]{0,80})",
    regex.IGNORECASE,
)

# A bounded, possessive date matcher — {6,12} caps the digits, ++ is possessive.
SAFE_DATE = regex.compile(r"date\s*[:\-]\s*([0-9/\-.]{6,12})", regex.IGNORECASE)

Bounding every quantifier ({0,80}, {6,12}) does double duty: it encodes the real-world maximum length of a legitimate field and it removes the unbounded repetition that backtracking needs to explode. A requester name longer than eighty characters is far more likely to be an attack or a corrupt paste than a real name, and rejecting it is the correct behavior.

3. Cap input length and enforce a per-match timeout #

Structural safety is the primary defense, but a parser hardens further by never handing a pattern more input than a real field could contain, and by abandoning any match that exceeds a strict time budget. The regex module’s timeout= argument raises TimeoutError instead of blocking, and a worker-level signal alarm backs it up where the pattern engine cannot self-interrupt. Neither path ever runs unbounded.

import signal
import json
import logging
from contextlib import contextmanager

logger = logging.getLogger("intake.parser.redos")

MAX_FIELD_INPUT = 4096      # a real statutory field never approaches this
MATCH_DEADLINE_S = 0.25     # generous for a linear pattern; fatal to a backtracker


@contextmanager
def match_deadline(seconds: float):
    """Worker-level backstop: abort a stuck match with SIGALRM (single-threaded).

    Defense in depth behind the regex-module timeout, so a pattern the engine
    cannot self-interrupt still cannot wedge the worker.
    """
    def _raise(signum, frame):
        raise TimeoutError("match exceeded worker deadline")

    previous = signal.signal(signal.SIGALRM, _raise)
    signal.setitimer(signal.ITIMER_REAL, seconds)
    try:
        yield
    finally:
        signal.setitimer(signal.ITIMER_REAL, 0)   # always disarm
        signal.signal(signal.SIGALRM, previous)


def extract_field(pattern: "regex.Pattern", body: str, correlation_id: str):
    """Run one hardened extraction against untrusted text, fail-safe on breach."""
    bounded = body[:MAX_FIELD_INPUT]            # cap BEFORE the engine sees it
    try:
        with match_deadline(MATCH_DEADLINE_S):
            # regex-module timeout is the primary guard; SIGALRM is the backstop.
            m = pattern.search(bounded, timeout=MATCH_DEADLINE_S)
        return m.group(0) if m else None
    except TimeoutError as exc:
        # Fail safe: a payload that cannot be parsed in time is rejected and logged,
        # never allowed to hang the ingestion worker and stall the statutory clock.
        logger.warning(json.dumps({
            "event": "regex_timeout_rejected",
            "correlation_id": correlation_id,
            "pattern": pattern.pattern,
            "input_len": len(bounded),
            "deadline_s": MATCH_DEADLINE_S,
            "action": "escalate_human_review",
        }))
        return None

4. Reject and log as an audited escalation #

A timeout or a length overflow is a security event, so it is recorded like one. The rejection writes a single append-only JSON line carrying the correlation identity, the pattern that timed out, and the action taken, then routes the payload to human review rather than dropping it. That record is what lets a security team spot a probing campaign and what proves the request was preserved, not lost, when a deadline is later examined.

def parse_with_escalation(body: str, correlation_id: str) -> dict:
    """Extract all fields under hardened matching; escalate on any rejection."""
    result: dict[str, object] = {"correlation_id": correlation_id, "fields": {}}
    rejected = False

    for name, pattern in (("requester", SAFE_REQUESTER), ("request_date", SAFE_DATE)):
        value = extract_field(pattern, body, correlation_id)
        if value is None and len(body) > MAX_FIELD_INPUT:
            rejected = True
        if value is not None:
            result["fields"][name] = value

    result["route"] = "human_review" if rejected else "auto"
    logger.info(json.dumps({
        "event": "parse_completed",
        "correlation_id": correlation_id,
        "route": result["route"],
        "fields_found": list(result["fields"].keys()),
    }))
    return result

A payload routed to human_review here flows into the same fail-safe lane the parent parsing pipeline uses, and the rejection lines land in the store described in Audit Logging Architecture. De-duplicated, validated payloads then continue to Priority Scoring Algorithms.

Validation & Verification #

Prove the hardening holds rather than trusting that the rewrite “looks safe”:

• Linear-time property. Run each production pattern against inputs of growing length (a long run of its inner character plus a failing suffix) under the timeout, and assert the elapsed time stays roughly linear. A pattern whose time curve bends upward is still vulnerable and must be rewritten before it ships. Keep these inputs bounded and always under the deadline so the test itself never hangs.
• Timeout fires and is logged. Feed the parser a length-overflow payload and assert it emits exactly one regex_timeout_rejected or a human_review route, and that the worker returns control promptly. A rejection with no audit line is a compliance gap.
• Bounds enforced before matching. Assert extract_field never passes more than MAX_FIELD_INPUT characters to the engine, so the cap is structural, not incidental.
• Lint gate. Add a CI check that fails the build on nested quantifiers or unbounded repetition inside a repeated group in any committed pattern, so a vulnerable regex cannot merge.

import time

def test_pattern_stays_linear_and_bounded():
    # Bounded, always-terminating input — never a hanging call.
    for n in (100, 200, 400):
        probe = ("a" * n) + "!"          # fails the pattern, exercises backtracking
        start = time.perf_counter()
        SAFE_REQUESTER.search(probe[:MAX_FIELD_INPUT], timeout=MATCH_DEADLINE_S)
        assert time.perf_counter() - start < MATCH_DEADLINE_S   # never wedges

Troubleshooting & Edge Cases #

• A pattern review misses a nested quantifier. A reviewer approves (?:\w+\s*)+ because it reads naturally. Fix: rely on the automated lint gate, not human reading — nested quantifiers are hard to spot by eye and easy to match mechanically.
• signal is unavailable off the main thread. signal.setitimer only works on the main thread of the main interpreter, so a worker pool that runs matches on threads cannot use it. Fix: use the regex module’s timeout= as the primary guard everywhere, and reserve the signal backstop for single-threaded workers or move matching into a subprocess with a wall-clock deadline.
• Unicode length vs. byte length. A cap measured in code points can still admit a very large byte string of multi-byte characters. Fix: bound both — cap code points for the matcher and reject oversized raw payloads at ingestion — so neither dimension can be inflated.
• Legitimate long fields. A genuinely long record description can exceed a tight field cap and be rejected. Fix: size each field’s bound to its real-world maximum, and route an over-length field to human review rather than truncating and parsing a partial value.
• Alarm left armed after an exception. A timeout that forgets to disarm the interval timer can fire during unrelated later work. Fix: always disarm in a finally block, as the match_deadline context manager does, so the alarm cannot leak.

Compliance Verification Checklist #

• Every pattern run against untrusted request text uses atomic groups or possessive quantifiers and carries an explicit upper bound on repetition, so match time is linear in input length.
• Input is capped to a per-field maximum before the pattern engine sees it, bounding work structurally rather than incidentally.
• Each match runs under a strict per-call timeout (regex module timeout=), with a worker-level signal backstop where the thread model allows it.
• A timeout or length overflow rejects the payload and routes it to human review instead of hanging the worker or dropping the request.
• Every rejection emits exactly one append-only JSON audit line carrying the correlation identity, the offending pattern, and the action taken (NIST SP 800-53 AU-9).
• A CI lint gate fails the build on nested quantifiers or unbounded repetition inside a repeated group in any committed pattern.
• The parser holds write-only audit access and no standing access to the fulfillment store (NIST SP 800-53 AC-6).
• The interval timer is always disarmed in a finally block so an alarm cannot leak into later work.

FAQ #

Related #

• Email & Form Parsing Pipelines — the parent pipeline whose regex tier this page hardens.
• Parsing Multi-Format FOIA Submissions with Python Regex — the deterministic pattern library the hardened engine runs.
• Audit Logging Architecture — the append-only store that preserves parser rejection events.
• Security Boundary Configuration — the least-privilege boundary that contains a wedged or exploited parser.
• Priority Scoring Algorithms — the downstream stage that consumes validated payloads once parsing clears.

← Back to all public records automation topics