# 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:** Python

- Prevalence: मध्यम 3 भाषाएँ कवर की गईं
- Impact: उच्च 1 उच्च गंभीरता वाले नियम
- Prevention: प्रलेखित 3 फिक्स उदाहरण

**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

1 Shoulder डिटेक्शन नियमों पर आधारित ReDoS के लिए रोकथाम रणनीतियाँ।

### Key Practices

- Use exponential time complexity when matching certain inputs

### Python

Replace nested quantifiers with simple patterns and bounded repetition

## Warning Signs

- [MEDIUM] regular expressions with catastrophic backtracking patterns that can
cause exponential time complexi

## Consequences

- DoS

## Mitigations

- regex में नेस्टेड quantifiers और ओवरलैपिंग alternations से बचें
- regex के लिए timeout तंत्रों का उपयोग करें
- non-backtracking regex engines का उपयोग करने पर विचार करें

## Detection

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

## Rules by Language

### Python (1 rules)

- **Regular Expression Denial of Service (ReDoS)** [MEDIUM]: Detects regular expressions with catastrophic backtracking patterns that can
cause exponential time complexity when matching certain inputs. Attackers can
exploit this to cause denial of service. Use simpler patterns or set timeouts.
  - Remediation: Avoid nested quantifiers like (a+)+. Use simple patterns with bounded quantifiers.

```python
import re

# Safe: simple character class with bounded quantifiers
pattern = re.compile(r'^[a-zA-Z0-9_]{3,20}$')

if not pattern.match(username):
    raise ValueError('Invalid username')
```

Learn more: https://shoulder.dev/learn/python/cwe-1333/redos