Recipe: Finding ReDoS Vulnerabilities

Relevant source files

The following files were used as context for generating this wiki page:

• website/blog/2023-10-05-finding-back-a-redos-vulnerability-in-zod/index.md
• website/blog/2023-09-21-detect-prototype-pollution-automatically/index.md
• packages/poisoning/package.json
• website/blog/2023-05-30-whats-new-in-fast-check-3-10-0/index.md
• SECURITY.md

Introduction

This document outlines a recipe for using fast-check to anticipate and prevent Regular Expression Denial of Service (ReDoS) vulnerabilities. ReDoS is a category of security issue where a regular expression's execution time becomes uncontrollably long when processing certain inputs, potentially leading to a denial of service. The goal is not just to find crashes, but to pinpoint inputs that drive an algorithm into prolonged or infinite executions.

The approach leverages fast-check's ability to generate random inputs and strategically exploit known weaknesses in JavaScript code. The Zod library's CVE-2023-4316, a ReDoS vulnerability in its email validator, serves as a practical example for this recipe. This technique is part of a broader strategy for security testing, which also includes capabilities like detecting prototype pollution.

Sources: website/blog/2023-10-05-finding-back-a-redos-vulnerability-in-zod/index.md:5-23

The Basic Setup

The fundamental concept is to rephrase the problem into a property that fast-check can test. This involves wrapping the function call under test with a timer and throwing an error if the execution time exceeds a predefined limit.

Sources: website/blog/2023-10-05-finding-back-a-redos-vulnerability-in-zod/index.md:25-30

The basic workflow for a ReDoS property test is as follows:

This diagram illustrates the core logic of a time-based property test for detecting performance issues.

A basic test skeleton looks like this:

import fc from 'fast-check';

const timeLimitMs = 1_000; // A specified limit for the algorithm
const arbitraries = []; // Arbitraries for generating random data
fc.assert(
  fc.property(...arbitraries, (...inputs) => {
    const startTime = performance.now();
    try {
      algorithm(...inputs);
    } catch (err) {}
    const endTime = performance.now();
    const delayMs = endTime - startTime;
    if (delayMs > timeLimitMs) {
      throw new Error(`The computation of algorithm(...inputs) took ${delayMs}ms`);
    }
  }),
);

Sources: website/blog/2023-10-05-finding-back-a-redos-vulnerability-in-zod/index.md:32-48

When applied to the Zod email validator vulnerability, the test is implemented as follows:

import { z } from 'zod'; // eg.: 3.22.2 is vulnerable
import fc from 'fast-check';

const timeLimitMs = 1_000;
const validator = z.string().email();
fc.assert(
  fc.property(fc.emailAddress(), (rawString) => {
    const startTime = performance.now();
    try {
      validator.parse(rawString);
    } catch (err) {}
    const endTime = performance.now();
    const delayMs = endTime - startTime;
    if (delayMs > timeLimitMs) {
      throw new Error(`The computation of validator.parse took ${delayMs}ms`);
    }
  }),
);

Sources: website/blog/2023-10-05-finding-back-a-redos-vulnerability-in-zod/index.md:51-69

Advanced Setup for Robust Detection

While the basic setup can identify vulnerabilities, several enhancements are needed for more robust and efficient detection, especially in well-maintained projects.

Sources: website/blog/2023-10-05-finding-back-a-redos-vulnerability-in-zod/index.md:71-74

Handling Large Inputs

Many DoS and ReDoS issues are triggered by large inputs. By default, fast-check uses small inputs to keep tests fast. To investigate ReDoS, generating larger entries is necessary. This can be configured globally or per-arbitrary.

• Global Configuration: fc.configureGlobal({ baseSize: 'xlarge' });
• Per-Arbitrary Configuration: fc.emailAddress({ size: "xlarge" })

Sources: website/blog/2023-10-05-finding-back-a-redos-vulnerability-in-zod/index.md:77-91

Increasing Test Volume

The default of 100 test runs may be insufficient to find vulnerabilities in stable projects. It is recommended to increase the number of runs significantly during investigation.

fc.assert(property, { numRuns: 1_000_000 });

This number can be adjusted for continuous integration pipelines to balance thoroughness and speed.

Sources: website/blog/2023-10-05-finding-back-a-redos-vulnerability-in-zod/index.md:93-102

Managing Execution Time with Workers

A synchronous piece of code can run for hours or indefinitely, and fast-check alone cannot interrupt it. The @fast-check/worker package solves this by running the property test in a separate worker thread, allowing the main thread to terminate it if it runs too long.

The following diagram shows the interaction between the main thread and the worker:

This diagram shows how @fast-check/worker isolates long-running tests to prevent them from blocking the main process.

To use it, fc.property is replaced by propertyFor and fc.assert is replaced by assert from the worker package. Two key options are used:

• interruptAfterTimeLimit: Kills the worker if a single run exceeds this duration.
• markInterruptAsFailure: Marks the interrupted run as a failure.

Sources: website/blog/2023-10-05-finding-back-a-redos-vulnerability-in-zod/index.md:114-142

Bypassing the Shrinker

When the primary goal is to identify an input causing a long execution, shrinking can be bypassed to get a failure report immediately.

fc.assert(property, { endOnFailure: true });

Once a failing input is found, you can remove endOnFailure: true and use the reported seed and path to shrink the counterexample.

Sources: website/blog/2023-10-05-finding-back-a-redos-vulnerability-in-zod/index.md:104-112

Expanding Input Space

DoS scenarios are often triggered by faulty or unexpected inputs. Instead of only generating valid inputs (e.g., fc.emailAddress()), it's beneficial to include a wider range of strings. The fc.oneof arbitrary can be used to combine valid arbitraries with more general ones like fc.fullUnicodeString().

fc.oneof(fc.emailAddress(), fc.fullUnicodeString());

This ensures the code is resilient against any possible user input. Another useful arbitrary is fc.stringMatching, which can generate strings based on a regular expression, allowing for highly specific and complex test cases.

Sources: website/blog/2023-10-05-finding-back-a-redos-vulnerability-in-zod/index.md:144-152, website/blog/2023-05-30-whats-new-in-fast-check-3-10-0/index.md:9-13

The Complete Snippet

Combining all the advanced techniques results in a robust test for finding the ReDoS vulnerability in Zod.

import { z } from 'zod'; // eg.: 3.22.2 is vulnerable
import fc from 'fast-check';
import { isMainThread } from 'node:worker_threads';
import { assert, propertyFor } from '@fast-check/worker';
const property = propertyFor(new URL(import.meta.url));

const timeLimitMs = 1_000;
const validator = z.string().email();
await assert(
  property(fc.emailAddress(), (...inputs) => {
    const startTime = performance.now();
    try {
      algorithm(...inputs);
    } catch (err) {}
    const endTime = performance.now();
    const delayMs = endTime - startTime;
    if (delayMs > timeLimitMs) {
      throw new Error(`The computation of algorithm(...inputs) took ${delayMs}ms`);
    }
  }),
  {
    // we want to stop immediately on failure to report issues asap, drop it to have shrinking
    endOnFailure: true,
    // we want to kill the predicate if it takes more than {interruptAfterTimeLimit}ms
    interruptAfterTimeLimit: 60_000,
    // and mark the run as failed
    markInterruptAsFailure: true,
    // fuzzing implies possibly running for longer than usual tests (when we want to look for the issues, not in CI)
    numRuns: 1_000_000,
  },
);

Running this test against a vulnerable version of Zod quickly identifies an input that causes a long execution time.

Sources: website/blog/2023-10-05-finding-back-a-redos-vulnerability-in-zod/index.md:156-189

Related Vulnerability Detection: Prototype Pollution

fast-check's capabilities extend beyond ReDoS. It can also be used to automatically detect other vulnerabilities like prototype pollution. This is achieved with the @fast-check/poisoning helper package, which detects if global prototypes (like Object.prototype) have been modified during a test run.

A test to find a prototype pollution vulnerability (like CVE-2018-3721 in lodash) would look like this:

import fc from 'fast-check';
import { assertNoPoisoning, restoreGlobals } from '@fast-check/poisoning';
import _ from 'lodash';

test('CVE-2018-3721', () => {
  fc.assert(
    fc
      .property(fc.object(), fc.object(), (instance, other) => {
        const clone = _.cloneDeep(instance);
        _.merge(clone, other);
        assertNoPoisoning();
      })
      .afterEach(restoreGlobals),
  );
});

This demonstrates that the general approach of using fast-check properties can be adapted to find various classes of security vulnerabilities.

Sources: website/blog/2023-09-21-detect-prototype-pollution-automatically/index.md:43-64, packages/poisoning/package.json:2-3, 38-44

Summary of Key Components

The following table summarizes the main tools and configurations used in this recipe.

Component	Package	Description
fc.property	fast-check	Defines a property to be tested with generated values.
fc.assert	fast-check	Runs the property test, with options for numRuns, endOnFailure, etc.
baseSize	fast-check	A global or per-arbitrary setting to control the size of generated values.
assert / propertyFor	@fast-check/worker	Runs property tests in a separate worker thread to handle long-running or infinite executions.
interruptAfterTimeLimit	@fast-check/worker	An option for the worker assert to terminate a test run after a specified duration.
assertNoPoisoning	@fast-check/poisoning	An assertion that checks for prototype pollution vulnerabilities.
Security Reporting	N/A	Vulnerabilities can be reported by opening an issue or via email as per the security policy.

Sources: website/blog/2023-10-05-finding-back-a-redos-vulnerability-in-zod/index.md, website/blog/2023-09-21-detect-prototype-pollution-automatically/index.md, SECURITY.md:12-13

Conclusion

The technique described provides a powerful framework for identifying not only ReDoS but also other performance bottlenecks, accidental algorithmic complexities, or infinite loops. By combining fast-check's arbitraries with time-based assertions and the @fast-check/worker package, developers can build a robust defense against a wide range of denial-of-service vulnerabilities and other hard-to-find bugs.

Sources: website/blog/2023-10-05-finding-back-a-redos-vulnerability-in-zod/index.md:196-198