Include Tests for Pathological Patterns to Ensure Backtracking Limits #16

New issue

Closed

opened 2026-03-11 18:11:00 +03:00 by NiXTheDev · 0 comments

NiXTheDev commented

2026-03-11 18:11:00 +03:00

(Migrated from github.com)

Goal: Protect against Regular Expression Denial of Service (ReDoS) by testing with exponential-time patterns.

Certain regex patterns (e.g., (a*)*, (a|a)*) can cause catastrophic backtracking. Without limits, the engine could hang or consume excessive CPU.

Proposed Solution:

Implement a backtracking limit (e.g., maximum number of steps) configurable at compile or runtime.
Add tests that run these pathological patterns with a short input and ensure they terminate within a reasonable time (or return a timeout error).

Implementation Steps:

Add a backtrack_limit field to Regex or NfaSimulator, defaulting to a high value (e.g., 10_000_000).
In the matching loop, increment a counter and abort if exceeded, returning a RuntimeError.
Add tests with patterns known to cause exponential blowup and verify that they either complete quickly or return an error.

Example:

#[test]
fn test_pathological_pattern_terminates() {
    let re = Regex::new(r"(a*)*").unwrap();
    let input = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa";
    // Should not hang; either returns match or error.
    let _ = re.is_match(input);
}

**Goal**: Protect against Regular Expression Denial of Service (ReDoS) by testing with exponential-time patterns. Certain regex patterns (e.g., `(a*)*`, `(a|a)*`) can cause catastrophic backtracking. Without limits, the engine could hang or consume excessive CPU. **Proposed Solution**: - Implement a backtracking limit (e.g., maximum number of steps) configurable at compile or runtime. - Add tests that run these pathological patterns with a short input and ensure they terminate within a reasonable time (or return a timeout error). **Implementation Steps**: 1. Add a `backtrack_limit` field to `Regex` or `NfaSimulator`, defaulting to a high value (e.g., 10_000_000). 2. In the matching loop, increment a counter and abort if exceeded, returning a `RuntimeError`. 3. Add tests with patterns known to cause exponential blowup and verify that they either complete quickly or return an error. **Example**: ```rust #[test] fn test_pathological_pattern_terminates() { let re = Regex::new(r"(a*)*").unwrap(); let input = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"; // Should not hang; either returns match or error. let _ = re.is_match(input); } ```