# 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.

- 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

3개의 Shoulder 탐지 규칙을 기반으로 한 ReDoS 예방 전략.

### Key Practices

- Use exponential time complexity when matching certain inputs

### Go

Avoid nested quantifiers in regex; use specific character classes instead

### JavaScript

Avoid nested quantifiers in regex and validate input length before matching

### Python

Replace nested quantifiers with simple patterns and bounded repetition

## Warning Signs

- [HIGH] potentially catastrophic regular expressions that could lead to ReDoS attacks
- [MEDIUM] regular expressions with catastrophic backtracking patterns that can
cause exponential time complexi

## Consequences

- DoS

## Mitigations

- 정규식에서 중첩 수량자와 겹치는 분기(alternation)를 피하세요
- 정규식에 타임아웃 메커니즘을 사용하세요
- 백트래킹을 하지 않는 정규식 엔진 사용을 검토하세요

## Detection

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

## Rules by Language

### Go (1 rules)

- **Regular Expression Denial of Service** [MEDIUM]: Regex pattern with nested quantifiers causes catastrophic backtracking.
  - Remediation: Avoid nested quantifiers like (a+)+. Use possessive quantifiers or atomic groups.

```go
// Avoid patterns like: (a+)+, (.*)*
// Use specific patterns instead
re := regexp.MustCompile(`^[a-z]+$`)
```

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

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

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