CVE-2026-73556: vLLM: ReDoS via structured_outputs.regex in the lm-format-enforcer backend (no compile timeout) — missed sibling of CVE-2026-55574

Summary

The fix for GHSA-rwxx-mrjm-wc2m ("ReDoS via structuredoutputs.regex compiled without timeout") wrapped the regex compile in the xgrammar and outlines backends with compileregexwithtimeout (and, for outlines, validateregexisbuildable). The lm-format-enforcer backend was left unguarded: it compiles the attacker-supplied regex with no timeout and no buildability check. A single request with a catastrophic regex hangs the structured-output compile step and stalls the engine worker (denial of service).

Affected code (HEAD d6d39c1)

vllm/v1/structuredoutput/backendlmformatenforcer.py: - line 110: characterlevelparser = lmformatenforcer.RegexParser(grammarspec) — builds an interegular FSM from the attacker regex synchronously, no timeout. - line 155: validatestructuredoutputrequestlmformatenforcer returns immediately on if soparams.regex: — no validation.

Sibling backends that WERE patched by GHSA-rwxx: - backendxgrammar.py:92 → compileregexwithtimeout(...). - backendoutlines.py:65 → compileregexwithtimeout(...) (plus validateregexisbuildable).

lm-format-enforcer uses the same interegular DFA-construction primitive the advisory cites for the outlines backend.

Reproduction (runtime-verified against the sink)

The sink lmformatenforcer.RegexParser(<regex>) was exercised directly (this is exactly what the backend calls):

baseline '[0-9]{3}' -> 0.0002 s attacker '(a{1,300}){300}' -> DID NOT COMPLETE in 20 s (one core pegged at 100% in interegular FSM construction)

End-to-end: start vllm serve <model> --structured-outputs-config '{"backend":"lm-format-enforcer"}', then POST /v1/completions with {"structuredoutputs":{"regex":"(a{1,300}){300}"}, ...}. The request never returns; because grammar compile runs in the engine's structured-output path, concurrent requests stall = worker-level DoS. The identical request against the outlines backend is bounded by compileregexwithtimeout and returns a clean error.

Impact

Unauthenticated denial of service (vLLM ships with no authentication by default). One request pegs a CPU core and blocks the structured-output engine path.

Reachability precondition: the operator must have selected backend=lm-format-enforcer via --structured-outputs-config (the default is auto → xgrammar). This is the same opt-in tier as the outlines backend that GHSA-rwxx already covered.

Suggested remediation

Route the lm-format-enforcer regex compile (backendlmformatenforcer.py:110) through the same compileregexwithtimeout guard already applied to the xgrammar and outlines backends, and reject un-buildable / oversized patterns in validatestructuredoutputrequestlmformatenforcer.