Claude skill ReDoS and catastrophic backtracking security

ReDoS is distinct from other denial-of-service vectors in that it requires no network amplification, no infrastructure access, and no authentication. A single HTTP request containing a carefully crafted string value causes the skill server to consume 100% of a CPU core for an arbitrarily long period. The attacker does not need to flood the server with traffic — one request is sufficient. In MCP skills, every tool argument that is validated with a regex is a potential ReDoS surface: search query fields, email addresses, repository URLs, file paths, and any free-text input that passes through a pattern match before being used.

SA-SKL-REGEX-001: Nested quantifiers with overlapping character classes — exponential backtracking on untrusted input

The canonical ReDoS pattern is a regex where an outer quantifier wraps an inner group that itself contains a quantifier, and both quantifiers can match the same characters. When the overall pattern fails to match at the end of the input, the engine must explore all possible ways the outer and inner quantifiers could have distributed their matches — this is exponential in the length of the input:

// VULNERABLE: nested quantifiers with overlapping character classes
// Classic pattern: (a+)+  or  (\w+\s*)+ style
// These cause exponential backtracking on any string that ALMOST matches
// but fails at the last character.

// Example 1: simple nested quantifier
const nestedPlus = /^(a+)+$/;
// Input: 'aaaaaaaaaaaaaaaaaaaab'  (20 'a' chars followed by 'b')
// The 'b' makes the overall match fail, but the engine tries all ways to
// partition the 20 'a' chars between the inner (a+) groups:
//   (a)(a)(a)...(a)b — fail at 'b'
//   (aa)(a)(a)...(a)b — fail at 'b'
//   (aaa)(a)(a)...(a)b — fail at 'b'
//   ... 2^20 = 1,048,576 combinations explored before returning false
//   For n=30: 2^30 = 1 billion combinations → ~5 seconds on modern hardware
//   For n=40: 2^40 = 1 trillion → hours

console.time('redos');
/^(a+)+$/.test('aaaaaaaaaaaaaaaaaaaaaaaaaab');  // n=25 'a' + 'b'
console.timeEnd('redos');  // may hang for 30+ seconds

// Example 2: real-world equivalent in input validation
// A developer tries to validate that input contains only word characters
// separated by optional whitespace:
const inputValidator = /^(\w+\s*)+$/;
// Input that triggers ReDoS: 'abcdefghijklmnopqrstuvwxyz '  (26 chars + space + fail char)
// OR: '                         !'  (spaces + non-word char)

// Example 3: tag/identifier validation — appears in MCP tool argument validation
const tagPattern = /^([a-zA-Z0-9]+-?)+[a-zA-Z0-9]$/;
// Intended: validate slug like "my-skill-tool-name"
// ReDoS input: 'aaaaaaaaaaaaaaaaaaaaaaaaa-'  (many 'a' chars + trailing '-')
// The trailing '-' makes it fail, triggering exponential backtracking

// WHY IT'S EXPONENTIAL: ambiguous quantifiers
// (a+)+  can match "aaa" as:
//   one group: (aaa)
//   two groups: (a)(aa) or (aa)(a)
//   three groups: (a)(a)(a)
// For n characters, there are 2^(n-1) ways to partition them.
// Each partition is tried before the engine concludes failure.

// SECURE ALTERNATIVES:

// Option 1: Rewrite without nested quantifiers (preferred for simple patterns)
// Instead of  /^(\w+\s*)+$/   use  /^\w[\w\s]*$/  or  /^[\w\s]+$/
// Instead of  /^([a-zA-Z0-9]+-?)+[a-zA-Z0-9]$/  use  /^[a-zA-Z0-9]+(-[a-zA-Z0-9]+)*$/
//   This is non-ambiguous: [a-zA-Z0-9]+ matches the first segment,
//   (-[a-zA-Z0-9]+)* matches additional segments — no overlapping alternation

// Option 2: Use the re2 npm package (Google RE2 — linear-time regex engine)
// RE2 guarantees O(n) matching time for all patterns by disabling backreferences
// and lookaround assertions. Drop-in replacement for most validation use cases.
import RE2 from 're2';

// RE2 evaluates in linear time — the 'aaaaab' attack string runs in microseconds
const safeValidator = new RE2('^(\\w+\\s*)+$');
// Note: RE2 will throw on patterns with backreferences or lookahead — use try/catch

// Option 3: Input length limit before regex test
function validateTag(input) {
  // ReDoS severity scales with input length — cap at reasonable maximum
  if (typeof input !== 'string' || input.length > 128) {
    return false;
  }
  // Even a vulnerable regex is bounded if input is limited to 128 chars:
  // 2^128 operations is still astronomical — limit to 32-64 chars for worst-case safety
  return /^[a-zA-Z0-9]+(-[a-zA-Z0-9]+)*$/.test(input);
}

// DETECTION HEURISTIC (SkillAudit):
// Patterns with nested quantifiers: (X+)+ or (X+)* or (X*)+ etc.
// where X contains quantified subexpressions or character classes that
// overlap with the outer pattern's character class.
const riskyPatterns = [
  /\([\w\[\]\\+*]+\+\)[+*]/,    // (expr+)+ or (expr+)*
  /\([\w\[\]\\+*]+\*\)[+*]/,    // (expr*)+ or (expr*)*
  /\([\w\[\]\\+*?]+\)\{.*\}/,   // (expr){n,m} with inner quantifier
];

SA-SKL-REGEX-002: Email/URL validation regex with catastrophic backtracking on malformed input

Email address validation is one of the most common sources of production ReDoS because the “standard” email regex that developers copy from Stack Overflow or write intuitively is catastrophically backtracking on malformed input with no @ character. The malformed email string forces the engine to try all possible ways the local-part quantifiers could divide the characters — none of which will ever produce a valid match — before concluding failure:

// VULNERABLE: email validation regex with catastrophic backtracking
// This pattern appears in hundreds of npm packages, blog posts, and Stack Overflow answers:
const emailRegex = /^([a-zA-Z0-9]+(\.)?)+@[a-zA-Z0-9]+\.[a-zA-Z]{2,}$/;

// ATTACK: input with no '@' character forces the entire string to be consumed
// by the local-part pattern before failing. The (\.)?  zero-or-one dot makes
// the outer quantifier's scope ambiguous with the inner character class.
// Input: 'aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa'
//         (100 'a' characters, no '@')
// Engine tries 2^50+ combinations of how to partition the 100 chars
// Returns 'false' after ~hours

// Timing demo:
console.time('email-redos');
emailRegex.test('a'.repeat(80));  // 80 'a' chars, no '@'
console.timeEnd('email-redos');   // Expected: 30+ seconds on V8

// ALSO VULNERABLE: URL validation patterns with similar structure
const urlRegex = /^(https?:\/\/)?([\w-]+(\.[\w-]+)+)(\/[\w-./?%&=]*)?$/;
// Input: 'x'.repeat(50) + '!'  (50 word chars + invalid trailing char, no dot)
// The  ([\w-]+(\.[\w-]+)+)  inner pattern has overlapping quantifiers

// ANOTHER COMMON VULNERABLE PATTERN: IP address validation
const ipRegex = /^(\d+\.){3}\d+$/;
// Actually safe — but frequently replaced with more "flexible" versions like:
const brokenIpRegex = /^(\d+\.?)+$/;  // VULNERABLE: (digit+dot?)+ overlapping

// WHY EMAIL VALIDATION IS ESPECIALLY RISKY:
// Email addresses come from user registration forms, tool arguments, webhook payloads
// A single automated tool call with a crafted "email" field takes down the skill
// The crafted input looks superficially like a valid email attempt — not obviously malicious

// SECURE ALTERNATIVES:

// Option 1: Use the email-validator package (non-backtracking implementation)
import { validate } from 'email-validator';
// email-validator splits on '@' first, then validates each part separately
// — O(n) time, no catastrophic backtracking
function validateEmail(input) {
  if (typeof input !== 'string') return false;
  if (input.length > 254) return false;  // RFC 5321 maximum email length
  return validate(input);
}

// Option 2: Pre-check for structural requirements before applying regex
// Most ReDoS attacks exploit the REJECTION path — the regex runs forever trying to fail.
// A simple pre-check eliminates the vulnerable path entirely:
function validateEmailSafe(input) {
  if (typeof input !== 'string') return false;
  if (input.length > 254) return false;         // RFC 5321 max
  if (!input.includes('@')) return false;         // must have '@' — eliminates attack input
  const atIndex = input.indexOf('@');
  if (atIndex === 0 || atIndex === input.length - 1) return false;  // '@' not at edges
  // Only now apply the regex — input is guaranteed to have '@' in a non-edge position
  // The local-part (before '@') is now bounded: no full-string backtracking possible
  const [local, domain] = input.split('@');
  if (local.length > 64) return false;          // RFC 5321 max local-part length
  if (domain.length > 255) return false;        // RFC 5321 max domain length
  return /^[a-zA-Z0-9._%+\-]+$/.test(local) && /^[a-zA-Z0-9.\-]+\.[a-zA-Z]{2,}$/.test(domain);
  // Both sub-regexes are simple character class + quantifier — no nested quantifiers
}

// Option 3: use re2 for the validation regex
import RE2 from 're2';
const safeEmailRegex = new RE2('^[a-zA-Z0-9._%+\\-]+@[a-zA-Z0-9.\\-]+\\.[a-zA-Z]{2,}$');
// RE2's linear-time engine evaluates 100-char input in microseconds regardless of structure

// DETECTION (SkillAudit):
// Email/URL validation patterns where local-part or path segment uses (X+)+ or (X+)?+
// tool argument named 'email', 'emailAddress', 'url', 'repoUrl' applied with regex
// that lacks a pre-check for '@' or '://' before the full regex is tested

SA-SKL-REGEX-003 (CRITICAL): User-supplied regex pattern evaluated with new RegExp — attacker provides catastrophic pattern

MCP tools that accept a search or filter pattern argument and compile it with new RegExp(userInput) give the attacker full control over the regex engine. Beyond ReDoS, the attacker can craft patterns that consume unlimited memory, cause the process to hang indefinitely, or trigger V8 optimizer pathways that are expensive to execute. This is the most severe SA-SKL-REGEX finding because the attacker does not need to discover an existing vulnerable pattern — they supply their own:

// VULNERABLE: user-supplied pattern compiled directly with new RegExp
import { McpServer } from '@modelcontextprotocol/sdk/server/mcp.js';
import { z } from 'zod';

const server = new McpServer({ name: 'file-search', version: '1.0.0' });

server.tool(
  'search_files',
  {
    searchPattern: z.string().describe('Regex pattern to search for in file contents'),
    directory: z.string().describe('Directory to search'),
  },
  async ({ searchPattern, directory }) => {
    // BUG: compiles user-supplied string as a RegExp
    // Attacker sends searchPattern: "(a+)+"
    // Applied to file content 'aaaaaaaaaaaaaaaaab' — hangs for seconds
    // Attacker sends: "([\\s\\S]+)+" applied to a 10KB file — hangs for minutes
    // Attacker sends: "(?:(?:a|aa)+)+" — ReDoS via alternation and nesting
    const regex = new RegExp(searchPattern, 'g');  // BUG: user controls the pattern

    const files = await readDirectory(directory);
    const results = [];
    for (const file of files) {
      const content = await readFile(file);
      // regex.test() or content.match(regex) — each file call may hang
      if (regex.test(content)) {
        results.push(file);
      }
    }
    return { content: [{ type: 'text', text: results.join('\n') }] };
  }
);

// ADDITIONAL ATTACK VECTORS via user-supplied RegExp:
// 1. Memory exhaustion via catastrophic group captures:
//    "(.{1,1000}){1,1000}" — creates 1 million capture groups in memory
// 2. V8 JIT deoptimization: certain patterns trigger deoptimization of V8's
//    regex JIT compiler, causing 10-100x slowdown even for "safe" patterns
// 3. Unicode catastrophe: patterns with Unicode mode (/u flag) and invalid
//    Unicode sequences cause V8 to scan the full Unicode table
// 4. Invalid regex syntax crashes the call:
//    "(" (unclosed group) — new RegExp("(") throws SyntaxError
//    Must be wrapped in try/catch, and the error reveals the server is
//    evaluating user-supplied regex (information disclosure)

// SECURE OPTION 1: Reject user-supplied patterns entirely — use literal string search
server.tool(
  'search_files',
  {
    searchTerm: z.string().max(256).describe('Literal string to search for in files'),
    directory: z.string(),
  },
  async ({ searchTerm, directory }) => {
    // Literal string search — no regex engine involved, O(n) time guaranteed
    const files = await readDirectory(directory);
    const results = [];
    for (const file of files) {
      const content = await readFile(file);
      if (content.includes(searchTerm)) {  // String.includes — no regex
        results.push(file);
      }
    }
    return { content: [{ type: 'text', text: results.join('\n') }] };
  }
);

// SECURE OPTION 2: Use safe-regex to reject patterns with exponential complexity
import safeRegex from 'safe-regex';

server.tool(
  'search_files',
  {
    searchPattern: z.string().max(256).describe('Regex pattern — ReDoS patterns rejected'),
    directory: z.string(),
  },
  async ({ searchPattern, directory }) => {
    // safe-regex performs static analysis of the pattern's complexity
    // Returns false for patterns with exponential or polynomial worst-case complexity
    if (!safeRegex(searchPattern)) {
      throw new Error(
        'Pattern rejected: contains nested quantifiers or ambiguous alternation ' +
        'that could cause catastrophic backtracking. Use a simpler pattern.'
      );
    }

    // Additional: wrap in try/catch for invalid syntax
    let regex;
    try {
      regex = new RegExp(searchPattern, 'g');
    } catch (e) {
      throw new Error(`Invalid regex pattern: ${e.message}`);
    }

    const files = await readDirectory(directory);
    const results = [];
    for (const file of files) {
      const content = await readFile(file);
      // Safe: pattern was approved by safe-regex analysis
      if (regex.test(content)) {
        results.push(file);
      }
      // Reset lastIndex after each file — global flag accumulation (see REGEX-004)
      regex.lastIndex = 0;
    }
    return { content: [{ type: 'text', text: results.join('\n') }] };
  }
);

// SECURE OPTION 3: Use RE2 for user-supplied patterns
// RE2 guarantees O(n) time but rejects patterns with backreferences/lookahead
import RE2 from 're2';

let re2regex;
try {
  re2regex = new RE2(searchPattern);  // throws if backreferences/lookahead present
} catch (e) {
  throw new Error(`Pattern not supported: ${e.message}. Backreferences and lookahead are not allowed.`);
}
// RE2 evaluates in linear time — no ReDoS possible regardless of input
if (re2regex.test(content)) { ... }

SA-SKL-REGEX-004: RegExp with global flag and exec() loop on stream — lastIndex accumulation causes O(n²) behavior

JavaScript’s regular expressions with the /g (global) or /y (sticky) flag maintain state in the lastIndex property. When a global RegExp instance is created once and reused across multiple exec() calls on different strings, the lastIndex from the previous match carries over to the next call. On large streaming inputs, this causes the engine to start each match not from position 0 but from the last match position — producing missed matches, incorrect results, and on certain input patterns, quadratic scanning:

// VULNERABLE: global RegExp created once and reused across multiple calls
import { McpServer } from '@modelcontextprotocol/sdk/server/mcp.js';

// BUG: global RegExp created at module level — lastIndex persists across tool calls
const MENTION_REGEX = /@(\w+)/g;  // global flag

server.tool(
  'extract_mentions',
  { text: z.string() },
  async ({ text }) => {
    const mentions = [];
    let match;

    // BUG: if MENTION_REGEX.lastIndex is non-zero from a previous call,
    // this loop starts searching from the middle of the string, not position 0.
    // For input "hello @alice @bob @charlie":
    //   Call 1: lastIndex=0 → finds @alice (lastIndex=12), @bob (lastIndex=17), @charlie (lastIndex=25) ✓
    //   Call 2: lastIndex=25 → searches from position 25 → finds nothing → returns []
    //   (even if call 2 has identical input)
    while ((match = MENTION_REGEX.exec(text)) !== null) {
      mentions.push(match[1]);
    }
    // After the loop: MENTION_REGEX.lastIndex === 0 (reset on exhaustion) — OK for full strings
    // But if the loop is broken early (return inside loop, exception), lastIndex is stuck mid-string

    return { content: [{ type: 'text', text: JSON.stringify(mentions) }] };
  }
);

// O(n²) PATTERN: streaming document processing with global RegExp
async function processStream(chunks) {
  const TOKEN_REGEX = /\b\w+\b/g;  // BUG: single instance, reused across chunks
  const tokens = [];

  for (const chunk of chunks) {
    // On each chunk, lastIndex carries over from the previous chunk's final match position
    // If chunk N ended with a match at position 500, chunk N+1 starts searching from
    // lastIndex=500 regardless of the new chunk's length.
    // For 1000 chunks of 1KB each: positions searched = 1 + 2 + 3 + ... + 1000 = O(n²)
    let match;
    while ((match = TOKEN_REGEX.exec(chunk)) !== null) {
      tokens.push(match[0]);
    }
    // lastIndex is NOT reset between chunks — carries over!
  }
  return tokens;
}

// REAL-WORLD O(n²) SCENARIO:
// MCP skill that processes log file chunks looking for error patterns:
const ERROR_REGEX = /\[ERROR\] [\w\s]+/g;  // module-level global RegExp
// For a 10MB log file processed in 1KB chunks (10,000 chunks):
// Chunk 1: scans from 0, finds match at position 800 — lastIndex=850
// Chunk 2: scans from 850 — if chunk 2 is only 1024 bytes, many positions are skipped
//           OR if lastIndex > chunk2.length, lastIndex is reset to 0 (spec behavior)
// Result: missed matches and quadratic expected scanning time across chunks

// SECURE: create a new RegExp instance per call / per chunk
server.tool(
  'extract_mentions',
  { text: z.string() },
  async ({ text }) => {
    // Create a NEW RegExp instance for each tool call — lastIndex always starts at 0
    const mentionRegex = /(@\w+)/g;  // new instance, fresh lastIndex=0
    const mentions = [];
    let match;
    while ((match = mentionRegex.exec(text)) !== null) {
      mentions.push(match[1].slice(1));  // strip '@'
    }
    return { content: [{ type: 'text', text: JSON.stringify(mentions) }] };
  }
);

// SECURE: use String.prototype.matchAll() — handles lastIndex correctly
server.tool(
  'extract_mentions',
  { text: z.string() },
  async ({ text }) => {
    // matchAll() creates a new match iterator with its own fresh lastIndex state
    // Returns all matches as an iterator — no lastIndex accumulation between calls
    const matches = [...text.matchAll(/@(\w+)/g)];
    const mentions = matches.map(m => m[1]);
    return { content: [{ type: 'text', text: JSON.stringify(mentions) }] };
  }
);

// SECURE: streaming processing — reset lastIndex between chunks, or create per-chunk instance
async function processStreamSafe(chunks) {
  const tokens = [];
  for (const chunk of chunks) {
    // Option A: create a new instance per chunk
    const tokenRegex = /\b\w+\b/g;  // new instance for this chunk
    for (const match of chunk.matchAll(tokenRegex)) {
      tokens.push(match[0]);
    }
    // Option B: if reusing, explicitly reset lastIndex after each chunk
    // TOKEN_REGEX.lastIndex = 0;  // reset to start of next chunk
  }
  return tokens;
}

// DETECTION (SkillAudit):
// module-level or outer-scope const/let/var declaration of RegExp with /g or /y flag
// used inside a function body with exec() or test() calls
// OR: RegExp with /g used with .exec() inside a loop without explicit lastIndex reset

Remediation summary

SkillAudit detects all four SA-SKL-REGEX-001 through REGEX-004 patterns through static analysis of MCP tool handler code: nested quantifier regex applied to argument fields, email/URL argument fields tested with known-vulnerable validation patterns, new RegExp(args.*) constructions, and module-scope /g-flag RegExp instances used inside function bodies. For related denial-of-service patterns in MCP skills, see SA-SKL-TRL timeout and rate limit absence and SA-SKL-STR input sanitization bypass. See the complete SA-SKL attack surface reference for the full vulnerability taxonomy.