CVE-2026-73556: Regular Expression Denial of Service (ReDoS) in vLLM lm-format-enforcer Backend

vLLM is a high-throughput and memory-efficient inference engine for Large Language Models (LLMs). To ensure that model outputs adhere to strict structural constraints, such as JSON schemas or regular expressions, vLLM provides a structured output decoding capability. This execution pathway relies on various parsing backends, including lm-format-enforcer, which translates regular expressions into Finite State Machines (FSMs) to guide the token-generation process.\n\nThe vulnerability lies within this structured decoding pipeline when utilizing the lm-format-enforcer engine. Specifically, the engine accepts user-controlled regular expressions through the structured_outputs.regex parameter at OpenAI-compatible endpoints like /v1/chat/completions and /v1/completions. Prior to version 0.26.0, vLLM failed to validate the execution complexity of these regex expressions or enforce compile-time resource limits on this backend.\n\nThis omission exposes vLLM servers to a remote, unauthenticated Regular Expression Denial of Service (ReDoS). When an attacker submits a highly complex or catastrophic regular expression, the backend thread attempts to parse and compile the expression into an FSM. This operation blocks the thread synchronously, forcing the CPU core to spin at maximum utilization and stalling the entire inference execution pipeline for concurrent requests.

The root cause of CVE-2026-73556 is the uncontrolled resource consumption during the parsing and state compilation of user-supplied regular expressions within lm-format-enforcer. This backend translates regex patterns into state-machine constraints via underlying libraries such as interegular. Because compiling irregular regular expressions (such as those containing nested quantifiers or overlapping loops) requires calculating complex state transitions, the compilation time scales exponentially relative to the expression structure.\n\nIn vulnerable versions, vLLM lacked validation steps or timeout guards when passing input to lmformatenforcer.RegexParser. During normal operation, the parsing of clean schemas is instantaneous. However, an attacker can specify a pattern containing overlapping groupings, such as (a+)+$, which causes catastrophic backtracking or extreme state-space explosion when parsed into an FSM.\n\nBecause Python executes this parsing synchronously on the thread servicing the request, the process consumes 100% of a CPU core. In multi-tenant environments or standard inference pools, this blockage prevents the worker from handling other token-generation streams. This flaw represents a "missed sibling" of CVE-2026-55574; while timeouts were implemented for other structured engines like xgrammar and outlines, lm-format-enforcer was left unprotected.

The vulnerability was addressed in Pull Request #47595 (Commit c9a788eedc412acceaa5112e0d44624b49841577) by implementing validation and compilation timeouts using a utility function compile_regex_with_timeout.\n\nIn vllm/v1/structured_output/backend_lm_format_enforcer.py, the original implementation directly instantiated the regex parser:\n\npython\n# Vulnerable Code Path\nelif request_type == StructuredOutputOptions.REGEX:\n character_level_parser = lmformatenforcer.RegexParser(grammar_spec)\n\n\nThis instruction ran without any thread intervention or timer. The patched version wraps this initialization using a timeout-safe compiler:\n\npython\n# Patched Code Path\nelif request_type == StructuredOutputOptions.REGEX:\n character_level_parser = compile_regex_with_timeout(\n lmformatenforcer.RegexParser,\n grammar_spec,\n )\n\n\nAdditionally, early input validation was introduced to reject malicious inputs at the API gateway layer before they schedule worker threads:\n\npython\n# Early validation in backend_lm_format_enforcer.py\ndef validate_structured_output_request_lm_format_enforcer(params: SamplingParams):\n so_params = params.structured_outputs\n\n if so_params.regex:\n try:\n compile_regex_with_timeout(\n lmformatenforcer.RegexParser,\n so_params.regex,\n )\n except Exception as err:\n raise ValueError(\n f"Failed to compile regex for lm-format-enforcer: {err}"\n ) from err\n\n\nBy testing compile time inside validate_structured_output_request_lm_format_enforcer, the server catches ReDoS inputs early. If compilation exceeds the threshold, the system throws a ValueError, returning an HTTP 400 response and preventing resource exhaustion.

An attacker can trigger this vulnerability by making a single, unauthenticated POST request to the vLLM server's OpenAI-compatible completions endpoints. No special privileges or structural knowledge of the underlying model are required. The attack relies entirely on the inclusion of the structured_outputs JSON block.\n\njson\nPOST /v1/completions HTTP/1.1\nHost: target-vllm-server:8000\nContent-Type: application/json\n\n{\n "model": "meta-llama/Meta-Llama-3-8B-Instruct",\n "prompt": "Synthesize a structured response.",\n "stream": false,\n "structured_outputs": {\n "regex": "(([a-zA-Z0-9])+)+$"\n }\n}\n\n\nWhen the request is processed, the system maps the structured_outputs.regex option to the lm-format-enforcer backend. As the regex engine attempts to expand the FSM states for the catastrophic sub-pattern (([a-zA-Z0-9])+)+$, the calculation complexity balloons.\n\nmermaid\ngraph LR\n Client["Unauthenticated Client"] -->|"Catastrophic Regex"| vLLM["vLLM API Endpoints (/v1/completions)"]\n vLLM -->|"Extracts structured_outputs.regex"| LME["lm-format-enforcer Backend"]\n LME -->|"Synchronous FSM Compilation"| ReDoS["CPU Core Spin (100% Load)"]\n ReDoS -->|"Thread Stalled"| Block["Inference Pipeline Stalls"]\n\n\nThe resulting execution loop does not crash the server immediately with a memory fault but rather holds the designated CPU thread in a perpetual busy-wait state. Sustained attacks consisting of multiple requests can quickly exhaust all available CPU threads in the vLLM worker pool, rendering the service completely unresponsive.

While the security patch effectively mitigates direct ReDoS attacks submitted via the structured_outputs.regex field, several architectural limitations could allow variant bypasses. Security researchers should pay close attention to nested structured outputs, particularly in complex JSON Schemas.\n\nUnder StructuredOutputOptions.JSON_OBJECT, users can supply complete JSON Schemas. If these schemas contain nested properties that use the "pattern" validation keyword (which also accepts regex constraints), the underlying JsonSchemaParser might compile these inner patterns. If the inner pattern compilation does not pass through the compile_regex_with_timeout utility, an attacker could hide a catastrophic regex inside a JSON schema parameter, bypassing the primary validation check.\n\nAnother concern resides in Python's signal-handling mechanism. Python's signal.alarm, which is often used to implement timeout wrapper mechanisms, is strictly limited to POSIX/Unix environments and must run on the process's main thread. If vLLM is deployed on non-POSIX runtimes (such as Windows environments) or schedules validation processes entirely inside worker threads rather than the main loop thread, standard timeout interrupts might be ignored, leaving the resource exhaustion path open.