CVE-2026-116577: Algorithmic Complexity Denial of Service in Tornado HTTP Header Parser

Tornado is a Python web framework and asynchronous networking library designed to handle large numbers of concurrent connections. Unlike traditional multi-threaded WSGI servers, Tornado relies on a single-threaded, non-blocking event loop (IOLoop) per worker process. Network I/O and protocol parsing are cooperatively scheduled on this primary thread before control is passed to application-level request handlers.

In Tornado versions prior to 6.6.0, the HTTP framing component (tornado.httputil.HTTPHeaders) exhibits an inefficient algorithmic complexity flaw classified under CWE-407 (Inefficient Algorithmic Complexity) and CWE-770 (Allocation of Resources Without Limits or Throttling). Specifically, the HTTPHeaders.parse_line method supports obsolete HTTP/1.x line folding (obs-fold), a legacy mechanism where header lines beginning with whitespace (SP or HTAB) are treated as continuations of the preceding header field.

When processing these continuation lines, Tornado performs repeated in-place string concatenations on an element stored inside a list (self._as_list[self._last_key][-1] += new_part). Because Python strings are immutable, each concatenation inside a list element prevents Python from applying its in-place string resizing optimization, forcing a full memory reallocation and buffer copy on every single continuation line.

An unauthenticated client can exploit this behavior by submitting an HTTP header block containing thousands of short continuation lines within the allowed max_header_size window (64 KB by default). Because header parsing executes synchronously on the IOLoop thread prior to routing or application logic, the resulting $O(N^2)$ CPU consumption blocks the event loop from servicing all other active sockets managed by that worker process.

The root cause of CVE-2026-116577 lies in the interaction between legacy HTTP protocol parsing and Python's internal memory management for immutable string objects. Under RFC 2616 Section 4.2, HTTP header values could span multiple lines if each subsequent line began with a space (0x20) or horizontal tab (0x09). Although RFC 7230 Section 3.2.4 and RFC 9112 Section 5.2 formally obsoleted line folding and instructed servers to reject or replace obs-fold sequences, Tornado retained support for backward compatibility prior to version 6.6.0.

When an HTTP/1.x message arrives at tornado.http1connection.HTTP1Connection, the header block is read up to max_header_size (defaulting to 65,536 bytes) and split into individual lines passed sequentially to HTTPHeaders.parse_line. When parse_line encounters a line starting with whitespace, it strips surrounding whitespace, prepends a single space, validates the slice against a regular expression, and appends it to the last value list entry for the active header key.

While CPython includes an optimization in unicode_concatenate that attempts to resize strings in place using _PyUnicode_Resize when the target string has a reference count of 1, this optimization only triggers for local variable assignments or direct dictionary bindings in specific bytecode patterns. When the target of += is an indexed list element (self._as_list[self._last_key][-1]), the interpreter loads the item onto the evaluation stack (incrementing its reference count), performs a binary add (BINARY_OP), and stores the new reference back into the list (STORE_SUBSCR).

Consequently, for a header containing $N$ continuation lines of length $c$, the $k$-th continuation requires allocating a new string buffer of size $k \cdot c$ and copying the entire accumulated string. Across $N$ continuations, the total bytes copied is proportional to $\sum_{k=1}^{N} k \cdot c = c \cdot \frac{N(N+1)}{2} = O(N^2)$. Within a 64 KB header limit, a client can fit approximately 16,000 to 21,000 three-byte continuation lines (such as a\n or a\r\n). In addition to quadratic memory copying, each line triggers a synchronous regular expression match (_ABNF.field_value.fullmatch), compounding the CPU overhead on the event loop thread.

In Tornado versions prior to 6.6.0, tornado/httputil.py maintained an instance attribute self._last_key on the HTTPHeaders class specifically to track which header field should receive subsequent folded lines. Below is the vulnerable implementation of HTTPHeaders.parse_line prior to commit 1b7a1dc9f340f52de929852e8125aa12f25297c9:

# tornado/httputil.py (Vulnerable code prior to 6.6.0)
def parse_line(self, line: str, *, _chars_are_bytes: bool = True) -> None:
    if m := re.search(r"\r?\n$", line):
        line = line[: m.start()]
    if not line:
        # Empty line, or the final CRLF of a header block.
        return
    if line[0] in HTTP_WHITESPACE:
        # continuation of a multi-line header
        if self._last_key is None:
            raise HTTPInputError("first header line cannot start with whitespace")
        new_part = " " + line.strip(HTTP_WHITESPACE)
        if _chars_are_bytes:
            # Synchronous regex validation executed per continuation line
            if not _ABNF.field_value.fullmatch(new_part[1:]):
                raise HTTPInputError("Invalid header continuation %r" % new_part)
        else:
            if _FORBIDDEN_HEADER_CHARS_RE.search(new_part):
                raise HTTPInputError("Invalid header value %r" % new_part)
        # VULNERABLE: Repeated concatenation on a list element causes O(N^2) allocations
        self._as_list[self._last_key][-1] += new_part
        self._combined_cache.pop(self._last_key, None)
    else:
        try:
            name, value = line.split(":", 1)
        except ValueError:
            raise HTTPInputError("no colon in header line")
        self.add(name, value.strip(HTTP_WHITESPACE), _chars_are_bytes=_chars_are_bytes)

Rather than refactoring the continuation logic to buffer fragments and join them once at the end of the header block, the Tornado maintainers resolved the issue in pull request #3765 by removing support for obsolete line folding altogether. This change had previously been scheduled for Tornado 7.0, as permitted by RFC 9112 Section 5.2, which allows HTTP servers to reject obs-fold lines with a 400 Bad Request response.

# tornado/httputil.py (Patched in commit 1b7a1dc9f340f52de929852e8125aa12f25297c9)
def parse_line(self, line: str, *, _chars_are_bytes: bool = True) -> None:
    if m := re.search(r"\r?\n$", line):
        line = line[: m.start()]
    if not line:
        # Empty line, or the final CRLF of a header block.
        return
    if line[0] in HTTP_WHITESPACE:
        # FIXED: Immediate rejection of any header line starting with whitespace
        raise HTTPInputError(
            "header line cannot start with whitespace, folding not supported"
        )
    try:
        name, value = line.split(":", 1)
    except ValueError:
        raise HTTPInputError("no colon in header line")
    self.add(name, value.strip(HTTP_WHITESPACE), _chars_are_bytes=_chars_are_bytes)

The patch also removed self._last_key from HTTPHeaders.__init__ and HTTPHeaders.add. Furthermore, during testing of the new rejection behavior, the maintainers identified a secondary issue in tornado/http1connection.py (fixed in commit 09591f65286a600c2196df9c33b792b889a6bccb). When HTTP1Connection operated in client mode and received a malformed response header triggering HTTPInputError before headers_received was invoked, the request delegate was never notified of connection closure, causing the client caller to hang.

# tornado/http1connection.py (Patched in commit 09591f65286a600c2196df9c33b792b889a6bccb)
        except httputil.HTTPInputError as e:
            gen_log.info("Malformed HTTP message from %s: %s", self.context, e)
            if not self.is_client:
                await self.stream.write(b"HTTP/1.1 400 Bad Request\r\n\r\n")
            elif not need_delegate_close:
                # FIXED: Ensure client delegate is notified on early header parse failure
                need_delegate_close = True
            self.close()
            return False

The fix is complete with respect to folded headers because parse_line immediately raises HTTPInputError in $O(1)$ time upon detecting leading whitespace. However, note that if a client sends thousands of separate headers with identical names (e.g., X: a\r\nX: b\r\n...), HTTPHeaders.add appends each value to self._as_list[norm_name] in $O(1)$ amortized time and only joins them via ". ".join(...) when self.__getitem__ or self.get is called, which operates in linear $O(N)$ time.

Exploiting CVE-2026-116577 requires no authentication, valid session tokens, or knowledge of specific application endpoints. Because HTTP1Connection._read_message parses the HTTP request line and headers before invoking the application routing table or request handler delegates, any publicly reachable Tornado HTTP/1.x listener is vulnerable if exposed directly or through a proxy that forwards folded headers.

To maximize the ratio of continuation lines ($N$) to total byte length within the default 65,536-byte max_header_size limit, an attacker constructs a minimal request line followed by a single single-character header name and thousands of continuation lines. Additionally, because Tornado prior to 7.0 accepts bare line feeds (\n) without carriage returns (\r) as line terminators, an attacker can reduce each continuation line to 3 bytes ( a\n).

# Conceptual payload construction demonstrating header structure
request_line = b"GET / HTTP/1.1\nHost: a\nX: a\n"
# 3 bytes per continuation line: SP (0x20) + 'a' (0x61) + LF (0x0a)
# ~21,800 continuations fit within the default 65,536-byte max_header_size
continuations = b" a\n" * 21800
payload = request_line + continuations + b"\n"

When a Tornado server processes this 64 KB payload, HTTPHeaders.parse_line executes 21,800 iterations. Across these iterations, the accumulated string in self._as_list["X"][-1] grows by 2 bytes per line (" a"), resulting in approximately $\sum_{k=1}^{21800} 2k \approx 475\text{ MB}$ of cumulative memory allocations and string copies for a single 64 KB network packet.

> [!NOTE] > The computational cost scales quadratically with the configured max_header_size. If an application increases max_header_size above the 64 KB default (for example, to accommodate large cookies or custom authentication headers), the CPU time per request increases by the square of that multiplier.

By sending a steady stream of such requests over concurrent connections or via HTTP/1.1 keep-alive pipelining, an attacker can saturate the CPU core assigned to the Tornado worker process, preventing the IOLoop from accepting new sockets or completing in-flight asynchronous callbacks.

The security impact of CVE-2026-116577 is strictly limited to service availability. There is no memory corruption, out-of-bounds read, or state manipulation that would impact confidentiality or integrity. This is reflected in its CVSS v3.1 score of 5.3 (Medium) with vector CVSS:3.1/AV:N/AC:L/PR:N/UI:N/S:U/C:N/I:N/A:L.

In a standard single-process Tornado deployment, occupying the IOLoop thread blocks 100% of request processing for the duration of the header parse loop. Legitimate clients attempting to connect or awaiting responses from asynchronous handlers (such as database queries or upstream API calls ready to resume on the event loop) experience high latency, connection queue saturation, or read timeouts.

In deployments where Tornado is placed behind a compliant reverse proxy (such as Nginx, Envoy, or HAProxy), the practical exposure is significantly reduced. Most modern HTTP proxies adhere to RFC 7230 / RFC 9112 by either rejecting incoming requests containing obs-fold with 400 Bad Request at the edge or normalizing folded headers into a single line before forwarding the request to the upstream Tornado backend.

As of publication, the Exploit Prediction Scoring System (EPSS) assigns CVE-2026-116577 a score of 0.00384 (0.38%), placing it in the 32.33rd percentile. It is not listed in the CISA Known Exploited Vulnerabilities (KEV) catalog, and no active exploitation campaigns in the wild have been reported.

The primary remediation is to upgrade Tornado to version 6.6.0 or later. Version 6.6.0 completely removes support for HTTP header line folding, causing HTTPHeaders.parse_line to raise HTTPInputError immediately upon encountering a header line beginning with whitespace.

pip install --upgrade "tornado>=6.6.0"

> [!IMPORTANT] > Because Tornado 6.6.0 rejects all requests and client responses containing folded headers, administrators should verify that no legacy internal clients or upstream services rely on multi-line HTTP headers (obs-fold) before deploying the upgrade in legacy environments.

For environments where an immediate upgrade to Tornado 6.6.0 is not feasible, security engineers can apply several defense-in-depth mitigations:

1. Enforce Reverse Proxy Normalization: Place Tornado behind a reverse proxy or load balancer (such as Nginx, Envoy, HAProxy, or AWS Application Load Balancer) configured to strictly comply with RFC 9112. Ensure the proxy rejects requests with obsolete line folding or unfolds them into single-line headers prior to upstream forwarding.
2. Reduce max_header_size: Because the quadratic amplification factor is bounded by the maximum number of lines that fit within max_header_size, reducing this parameter on HTTPServer instances directly constrains worst-case CPU consumption.

import tornado.httpserver
import tornado.web
 
app = tornado.web.Application([...])
# Reduce max_header_size from default 65536 bytes to 8192 bytes
server = tornado.httpserver.HTTPServer(app, max_header_size=8192)
server.listen(8888)

3. Multi-Process Worker Isolation: Configure Tornado to run multiple worker processes across available CPU cores (either via tornado.process.fork_processes or an external process supervisor behind a load balancer) so that a blocked IOLoop in one process does not stall all concurrent application traffic.