http.cookiejar split_header_words is quadratic in the Set-Cookie2 length #159642

Bug report

CookieJar.extract_cookies takes time quadratic in the length of a Set-Cookie2 header, also with the default policy (rfc2965=False). A server can send one folded Set-Cookie2 header of a few megabytes and keep a urllib client with an HTTPCookieProcessor busy for minutes on a single response.

import http.client
import io
import time
import urllib.request
from http.cookiejar import CookieJar, split_header_words


class FakeSocket:
    def __init__(self, data):
        self.data = data

    def makefile(self, mode, *args, **kwargs):
        return io.BytesIO(self.data)


def response(lines):
    line = b"a," * 32000  # 64000 bytes, under http.client's 65536 line limit
    raw = (b"HTTP/1.1 200 OK\r\n"
           b"Set-Cookie: x=1\r\n"
           b"Set-Cookie2: " + line + b"\r\n"
           + b"".join(b" " + line + b"\r\n" for _ in range(lines - 1))
           + b"Content-Length: 0\r\n\r\n")
    resp = http.client.HTTPResponse(FakeSocket(raw))
    resp.begin()
    return resp


req = urllib.request.Request("http://example.com/")
for lines in (5, 10, 20):
    resp = response(lines)
    size = len(resp.headers["Set-Cookie2"])
    jar = CookieJar()
    t0 = time.perf_counter()
    jar.extract_cookies(resp, req)
    t1 = time.perf_counter() - t0
    t0 = time.perf_counter()
    split_header_words([resp.headers["Set-Cookie2"]])
    t2 = time.perf_counter() - t0
    print(f"Set-Cookie2 of {size:>8} chars: extract_cookies {t1:6.2f} s, "
          f"split_header_words alone {t2:6.2f} s, cookies stored: "
          f"{sorted(c.name for c in jar)}")

Output on 3.14.4 (the machine was under load, so the absolute times are noisy, but the growth is clear):

Set-Cookie2 of   320012 chars: extract_cookies   1.41 s, split_header_words alone   0.91 s, cookies stored: ['x']
Set-Cookie2 of   640027 chars: extract_cookies   7.16 s, split_header_words alone   6.36 s, cookies stored: ['x']
Set-Cookie2 of  1280057 chars: extract_cookies  21.24 s, split_header_words alone  24.65 s, cookies stored: ['x']

Doubling the header roughly quadruples the time. Only x ends up in the jar. http.client allows lines of up to 65536 bytes and 100 header lines including continuation lines, so a single header can reach about 6.3 MB, which at this rate is on the order of ten minutes of CPU for one response.

Expected: parsing time linear in the header size.

Cause, at 9cb7a5b (the code is the same in 3.14.4):

• split_header_words (Lib/http/cookiejar.py lines 395-433) consumes one token at a time and after each token rebuilds the rest of the string, through unmatched() (340-343, called at 402, 406 and 412) or text.lstrip()[1:] at 421. Each step copies the remaining text, so the loop is quadratic.
• CookieJar.make_cookies (1604-1623) calls split_header_words(rfc2965_hdrs) whenever the response also carries a Set-Cookie header. The quick exit at 1615-1619 does not fire under the default policy in that case. The cookies from the header above have no Version attribute and are later rejected by DefaultCookiePolicy.set_ok_version (970-983), so for them the parsing work is thrown away.

Proposed fix: rewrite the loop to keep a position and use pattern.match(text, pos) (or re.finditer over the whole value) instead of rebuilding the string after every token, which makes it linear without changing the result. A test that parses a header of a few hundred kilobytes in bounded time would guard it.

I can open a PR with the change and a test.

CPython versions tested on:

3.14

Operating systems tested on:

Linux

Linked PRs

• gh-159642: Fix quadratic complexity in http.cookiejar header parsing #159650