# Inefficient Regular Expression Complexity (CWE-1333)

The product uses a regular expression with an inefficient, possibly exponential worst-case computational complexity that consumes excessive CPU cycles.

**Stack:** JavaScript

- Prevalence: Medium 3 languages covered
- Impact: High 1 high-severity rules
- Prevention: Documented 3 fix examples

**OWASP:** Injection (A03:2021-Injection) - #3

## Description

Certain regular expression patterns can take exponential time to evaluate on certain inputs (ReDoS). Attackers can craft inputs that cause the regex engine to consume excessive CPU time, leading to denial of service.

## Prevention

Prevention strategies for ReDoS based on 1 Shoulder detection rules.

### JavaScript

Avoid nested quantifiers in regex and validate input length before matching

## Warning Signs

- [HIGH] potentially catastrophic regular expressions that could lead to ReDoS attacks

## Consequences

- DoS

## Mitigations

- Avoid nested quantifiers and overlapping alternations in regexes
- Use regex timeout mechanisms
- Consider using non-backtracking regex engines

## Detection

- Total rules: 3
- Languages: go, javascript, typescript, python

## Rules by Language

### Javascript (1 rules)

- **Regular Expression Denial of Service (ReDoS)** [HIGH]: Detects potentially catastrophic regular expressions that could lead to ReDoS attacks.

ReDoS occurs when regular expressions with certain patterns cause exponential backtracking,
leading to excessive CPU consumption. Evil regexes typically contain:

1. Nested quantifiers (e.g., (a+)+, (a*)*)
2. Alternation with overlapping patterns (e.g., (a|ab)*, (a|a)*)
3. Grouping with repetition where the group can match the same input in multiple ways
4. Complex patterns with overlapping possibilities that cause catastrophic backtracking

When user input is matched against these patterns, an attacker can craft input that
causes the regex engine to take exponential time, effectively causing a denial of service.
  - Remediation: Avoid nested quantifiers and use safe regex libraries:

```javascript
const safeRegex = require('safe-regex');

if (!safeRegex(pattern)) {
  return res.status(400).json({ error: 'Invalid regex' });
}

if (input.length > 1000) {
  return res.status(400).json({ error: 'Input too long' });
}

const result = input.match(/^[a-zA-Z0-9]+$/);
```

Learn more: https://shoulder.dev/learn/javascript/cwe-1333/regex-dos

### Typescript (1 rules)

- **Regular Expression Denial of Service (ReDoS)** [HIGH]: Detects potentially catastrophic regular expressions that could lead to ReDoS attacks.

ReDoS occurs when regular expressions with certain patterns cause exponential backtracking,
leading to excessive CPU consumption. Evil regexes typically contain:

1. Nested quantifiers (e.g., (a+)+, (a*)*)
2. Alternation with overlapping patterns (e.g., (a|ab)*, (a|a)*)
3. Grouping with repetition where the group can match the same input in multiple ways
4. Complex patterns with overlapping possibilities that cause catastrophic backtracking

When user input is matched against these patterns, an attacker can craft input that
causes the regex engine to take exponential time, effectively causing a denial of service.
  - Remediation: Avoid nested quantifiers and use safe regex libraries:

```javascript
const safeRegex = require('safe-regex');

if (!safeRegex(pattern)) {
  return res.status(400).json({ error: 'Invalid regex' });
}

if (input.length > 1000) {
  return res.status(400).json({ error: 'Input too long' });
}

const result = input.match(/^[a-zA-Z0-9]+$/);
```

Learn more: https://shoulder.dev/learn/javascript/cwe-1333/regex-dos