{"slug":"redos-regex-rewrite","name":"ReDoS Regex Rewrite: Same Answers, Linear Time","version":"1.0.0","updated_at":"2026-10-09T04:32:42.998Z","use_when":"Rewrites a JavaScript regular expression that can hang on a crafted input (catastrophic backtracking, ReDoS) into one that gives exactly the same yes or no for every text and runs in linear time, answered as JSON with the pattern and flags. Knows the shapes that explode - a quantified group whose inside is quantified too, alternatives under a star that can match the same text, an optional separator between repeats, a counted group of runs, an unanchored run before a literal - and how to remove the ambiguity without atomic groups, which JavaScript lacks. Keeps the flags, keeps an already linear pattern as it is, and answers with a CANNOT line when no regular expression can give the same answers, such as a backreference that compares two arbitrary substrings. Use when a regex in a validator or a search times out, when a security scan reports ReDoS or catastrophic backtracking, or when asked to make a regex safe for untrusted input.","not_for":"Writing a new regular expression from examples, changing what a pattern accepts, other regex engines than the JavaScript one in Node and the browsers, or proving a pattern safe for every engine. It rewrites one pattern used as a yes or no test and keeps its flags; matched text and capture groups are not preserved unless a backreference needs them.","languages":["en"],"tags":["regex","redos","security","javascript","validation","performance"],"category":"code","category_url":"https://aiskills402.com/categories/code","keywords":["catastrophic backtracking","make a regex safe","security scan reports ReDoS"],"faq":[{"q":"How can a short pattern hang a whole server?","a":"The engine in Node and the browsers backtracks: when a match fails at the end, it goes back and tries every other way the pattern could have split the text. A group of runs inside another run, two alternatives that start alike, or an optional separator between repeats gives a forty-character string billions of splits. The input that triggers it is usually a near miss, such as letters followed by one wrong character."},{"q":"Why not just add a lazy quantifier or an atomic group?","a":"JavaScript has no atomic groups and no possessive quantifiers, so those patterns do not compile. A lazy quantifier only changes the order in which the splits are tried, not how many there are, so the near miss still hangs. The fix is a pattern in which every character can be consumed in one way only, written from the set of texts the original accepts, with its edges checked."},{"q":"When does it refuse to rewrite?","a":"When a backreference has to repeat an arbitrary earlier piece of text, such as the same word twice or the same number on both sides of a dash, no regular expression can describe that set, so no rewrite can give the same answers quickly. You get one CANNOT REWRITE line with the reason. A request to change what the pattern accepts is refused too, because that is a new regex, not a safe copy."},{"q":"Does it help Claude Sonnet?","a":"Only a little, so two cents. Both Claude models rewrote twenty-two patterns, file loaded and not, and every answer was run: same yes or no as the original on thousands of short texts, and no near-miss input above 200 ms. Plain Sonnet already fixed all thirteen hanging patterns. It missed one refusal: a pattern whose first word must equal its last got another backreference pattern back, still not linear. With the file it refused it. Haiku also went from 21 to 22."}],"examples":[{"lang":"en","model":"claude-sonnet-5-5","input_excerpt":"Pattern (source, no slashes): ^(a+)+$\nFlags: (none)","output_excerpt":"{\"pattern\": \"^a+$\", \"flags\": \"\"}"}],"page_url":"https://aiskills402.com/skills/redos-regex-rewrite","markdown_url":"https://aiskills402.com/skills/redos-regex-rewrite.md","image_url":"https://cdn.aiskills402.com/og/skills/redos-regex-rewrite/7343614a.png","related_url":"https://api.aiskills402.com/v1/skills/redos-regex-rewrite/related","purchases_count":null,"tested":{"date":"2026-10-09","strong":{"model":"claude-sonnet-5-5 (Claude Code alias \"sonnet\")","verdict":"Right on all 22, checked by running every answer: the same yes or no as the original on a pool of short texts, and each near-miss input finished within 200 ms. It collapsed nested runs, made optional separators mandatory where the set allows, shrank unanchored runs to one character, worked out a glued repeat of digits and decimals, turned a backreference over runs of one letter into an even count, kept the flags, left seven linear patterns as they were or rewrote them to the same set, and refused both patterns whose backreference repeats arbitrary text."},"weak":{"model":"claude-haiku-5-5 (Claude Code alias \"haiku\")","verdict":"Right on all 22, checked by running every answer, with the same rewrites, the same seven safe patterns kept and the same two refusals as Sonnet."},"note":"Twenty-two JavaScript patterns used with test(), written by us: 13 that hang on a near-miss input (nested runs, optional separators, overlapping alternatives, a dot run in a repeat, a counted group, unanchored runs, a classic e-mail validator, Unicode words, a backreference over runs of one letter), 2 that no regular expression can replace (a backreference that repeats arbitrary text) and 7 safe controls. The accepted strings of each original are measured over an exhaustive pool of short texts plus edits of seeds; every answer must agree on all of them and finish each near-miss input within 200 ms. The case script proves that each trap really hangs and each control does not. The examples in the skill are deliberately not the test patterns. No check was widened. One run per model and pattern.","baseline":{"date":"2026-10-09","rows":[{"label":"Patterns handled right (22 patterns)","better":"higher","strong":{"with":{"n":22,"of":22},"without":{"n":21,"of":22}},"weak":{"with":{"n":22,"of":22},"without":{"n":21,"of":22}}}],"note":"Same request on both sides; it states the JSON shape and asks for a CANNOT line when no linear pattern gives the same answers. Without the skill both models already rewrote all thirteen hanging patterns correctly and kept the safe ones. Each missed one refusal: for a pattern whose first word must equal its last word they returned another pattern with the same backreference, which still is not linear."},"report_url":null},"price_usd":"0.02","price_micro":20000,"size_bytes":9102,"sha256":"3d16d260937d252e2f55bea38ade73fb8924b3b98ad7987170770d29d5e6041f","outline":["The answer","Only the yes or no counts","The shapes that hang","How to rewrite","When the pattern is already safe","When to refuse","Work in this order","Short example"],"license":{"summary":"Perpetual, non-exclusive; use and modify for yourself incl. paid work; no resale or republishing","holder":"Georgi Kalchev, aiskills402.com","url":"https://aiskills402.com/docs#license"},"buy_url":"https://api.aiskills402.com/v1/skills/redos-regex-rewrite/file","redownload_url_template":"https://api.aiskills402.com/v1/purchases/{token}","mcp_tool":null,"payment":{"protocol":"x402","scheme":"exact","asset":"USDC","selling":true,"network":"base","network_caip2":"eip155:8453","pay_to":"0x8e37022edcf0f21cf3c9f93fee9d4d32519f36f4","facilitator":"cdp"},"seo_title":"Fix a ReDoS Regex Without Changing Its Answers","seo_description":"Rewrite a JavaScript regex that hangs on crafted input into one with the same yes or no for every text, in linear time; flags kept. $0.02 once, in USDC.","versions":[{"version":"1.0.0","date":"2026-10-09","changelog":"# Changelog\n\n## 1.0.0 — 2026-10-09\n\nFirst release: rewrites a JavaScript regular expression used with test() that can backtrack catastrophically into one that accepts exactly the same texts in linear time, answered as JSON with the pattern and the unchanged flags; returns an already linear pattern unchanged and answers with a CANNOT REWRITE line when a backreference must repeat arbitrary text. The examples in the skill are not the test patterns. The tests measure the accepted set of each original over a pool of short strings, run every answer on near-miss inputs under a 200 ms limit, and the case script proves each trap really hangs and each control does not. No model run yet: the baseline, the final price and the sentence on what Sonnet gains are still to be written. Price 40000 is provisional.\n\n## 1.0.1 — 2026-10-09 (finalised after the model test)\n\n- Measured on 22 patterns: Sonnet 21 -> 22, Haiku 21 -> 22 (without -> with the skill, same checks). No check was widened.\n- Before the run: one backreference case got a 200001-character near-miss input, because a quadratic rewrite with the same answers passed under 200 ms at 40001.\n- Price: $0.02 (Sonnet gain 1).\n"}]}