recursion-dos

Recursion DoS Detection

When to Use

Audit parsers, serializers, tree walkers, deep clone/merge functions, and any recursive function that processes user-controlled data structures with unbounded nesting depth.

Key Distinction: OOM vs RangeError

Crash Type	Severity	Catchable?	Process Dies?
OOM (heap exhaustion)	HIGH 7.5	NO	YES -- uncatchable, process killed
RangeError (stack overflow)	MEDIUM 5.3-6.5	YES (try/catch)	Only if uncaught

OOM crash = process dies regardless of error handling. This is HIGH severity. RangeError = catchable in try/catch. Only HIGH if the library does NOT catch it.

Process

Step 1: Find Recursive Functions

grep -rn "function.*recurse\|function.*recursive\|function.*walk\|function.*traverse" .
grep -rn "function.*serialize\|function.*stringify\|function.*clone\|function.*deep" .
grep -rn "function.*parse\|function.*process\|function.*visit\|function.*transform" .

Look for functions that call themselves:

# Find function definitions and then check if they self-reference
grep -rn "function\s\+\w\+" . --include="*.js" | head -50
# Then for each function name, check if it calls itself

Step 2: Check for Depth Limits

grep -rn "maxDepth\|max_depth\|depthLimit\|depth_limit\|MAX_DEPTH" .
grep -rn "depth\s*>\|depth\s*>=\|depth\s*<\|depth\s*<=" .
grep -rn "recursion.*limit\|stack.*limit\|nesting.*limit" .

Step 3: Test with Nested Input

Create deeply nested input matching the data format:

// JSON-like nesting
let nested = "x";
for (let i = 0; i < 100000; i++) {
  nested = { a: nested };
}

// String-based nesting
let nested = "a";
for (let i = 0; i < 100000; i++) {
  nested = "[" + nested + "]";
}

Step 4: Measure Stack Consumption

// Run in subprocess to avoid crashing main process
const { execSync } = require('child_process');
try {
  execSync('node -e "const pkg = require('./'); pkg.parse(payload)"', {
    timeout: 10000,
    maxBuffer: 1024
  });
} catch (e) {
  if (e.status === null) {
    console.log('[+] OOM: process killed (HIGH severity)');
  } else {
    console.log('[!] RangeError: catchable (MEDIUM severity)');
  }
}

Common Vulnerable Patterns

Pattern 1: Recursive Parser Without Depth Limit

function parse(node) {
  if (node.children) {
    return node.children.map(child => parse(child)); // No depth limit
  }
  return node.value;
}

Pattern 2: Recursive Serializer

function serialize(obj) {
  if (typeof obj === 'object' && obj !== null) {
    return '{' + Object.keys(obj).map(k => k + ':' + serialize(obj[k])).join(',') + '}';
  }
  return String(obj);
}

Pattern 3: Deep Clone Without Limit

function deepClone(obj) {
  if (typeof obj !== 'object' || obj === null) return obj;
  const clone = Array.isArray(obj) ? [] : {};
  for (const key in obj) {
    clone[key] = deepClone(obj[key]); // Unbounded recursion
  }
  return clone;
}

Pattern 4: Circular Reference (Infinite Loop)

Some recursive functions do not detect circular references:

const a = {}; a.self = a;
deepClone(a); // Infinite recursion -> stack overflow

CVSS Guidance

• OOM crash (process dies, unauthenticated): HIGH 7.5
• OOM crash (authenticated): MEDIUM 6.5
• RangeError (catchable but uncaught): HIGH 7.5
• RangeError (caught by library): LOW -- not a vulnerability
• Infinite loop (CPU DoS): MEDIUM 5.3

References

• Sinks -- Recursive operation patterns
• False Positive Indicators
• PoC Skeleton