ReDoS in chat parser role-boundary regex (Python, TypeScript) #446

The role-boundary regex in the Prompty chat parser is vulnerable to catastrophic backtracking (ReDoS). I found and fixed this in the Java runtime while building it (PR #444, commit f63b98b3); the same pattern is present and exploitable in Python and TypeScript. Filing separately rather than widening that PR.

Affected

Root cause

(\[((\w+\s*=\s*"?[^"]*"?\s*,?\s*)+)\])?

The value class [^"]* also matches the separator ,, whitespace, and the closing ]. Combined with the optional "? delimiters, one iteration of the inner group can consume text that a later iteration could equally have consumed, so the outer + has an exponential number of ways to partition the same input. Any input that ultimately fails to match forces the engine to explore all of them.

Note that a quoted attack string is not slow — the quotes anchor [^"]* and defuse the ambiguity. The trigger is unquoted attributes, which the pattern explicitly permits via "?.

Reproduction

Input "user[" + "a=b," * n + "!" (unquoted attributes, no closing ]), matched against each runtime's own compiled pattern:

Roughly 9x per two repetitions. A ~30-character input hangs the process indefinitely.

Reachability

The parser runs over rendered prompt text, so any template that interpolates untrusted content into a position where a line can begin — a user message, retrieved document, or tool result — can carry the payload. It needs no valid role marker to be effective, because the cost is incurred on the failing match.

Fix

Make the value class exclude the separator and the closing bracket so no ambiguous split exists:

(\[(?:\w+\s*=\s*(?:"[^"]*"|[^",\]]*)\s*,?\s*)+\])?

An alternation of "a quoted string" or "an unquoted value containing neither , nor ]". I verified this against both engines — linear, and functionally identical on system:, # assistant:, user[name="Alice"]:, user[name=Bob, id=7]:, and the negative case notarole::

Java additionally uses possessive quantifiers (\w++, \s*+, [^",\]]*+) as belt-and-braces. Python supports these from 3.11, which is Prompty's floor, so the Python fix can match Java exactly; JS has no possessive quantifiers, but the alternation alone is sufficient — there is nothing left to backtrack into.

Each fix should land with a regression test asserting a bounded runtime on a ~20-repetition adversarial input.