Redaction regexes that ran in quadratic time on long text
Two patterns used to hide email-like values in provider text backtracked from every position on long input without whitespace. Both were replaced with bounded, linear-time alternatives.
Symptoms
CodeQL code scanning raised alert #4 (js/polynomial-redos) on the scrub function of the PayU India adapter. A follow-up test of the core email pattern measured 18 to 26 seconds for 80,000 characters.
Reproduction
Pass a long string with no whitespace and no @ character to the scrubber, for example 80,000 repeated letters. The PayU India scrubber used:
text.replace(/\S*@\S*/g, "[redacted]")The core email pattern had the same shape: an unbounded character class on both sides of @.
Expected and observed behavior
- Expected
- Scrubbing cost grows linearly with input length; pasted text of a few megabytes is processed in well under a second.
- Observed
- The regex engine retries the match from every starting position, so the work grows with the square of the input length.
Root cause
An unbounded \S* before @ matches the entire remaining run of non-space characters from each starting position, fails to find @, and backtracks. On a run of length n this repeats n times, giving O(n²) work. Issue #40 describes it: "On a long string without whitespace and without @, the engine retries from every position, so the cost grows quadratically."
Resolution
The PayU India scrubber now bounds the input and redacts whole tokens instead of matching a pattern around @ (pull request #41):
// Bounded input and a token pass (not /\S*@\S*/) keep the cost linear.
const t = v
.slice(0, max * 4)
.split(/(\s+)/)
.map((token) => (token.includes("@") ? "[redacted]" : token))
.join("")The core email pattern was given RFC 5321 length limits so each side of @ is bounded (pull request #43):
/[A-Za-z0-9._%+-]{1,64}@[A-Za-z0-9.-]{1,253}[.][A-Za-z]{2,24}/gValidation
A test feeds a UPI id followed by a long whitespace-free run. Pull request #41 reports 100 PayU India tests passing; pull request #43 adds a linear-time test for the core pattern and reports 4,574 tests passing.
Remaining limitations
Whether CodeQL closed alert #4 after the merge was not verified for this record. Redaction remains best effort, as the project README states.