Como funcionam as expressões regulares? (Backtracking e desempenho)

Todo desenvolvedor provavelmente já usou Expressões Regulares (Regex) em algum momento para validação de e-mail ou análise de strings.

Embora seja uma ferramenta poderosa e conveniente, você sabia que uma única regex mal escrita pode derrubar um servidor inteiro?

Neste artigo, exploraremos a mecânica interna dos mecanismos de regex e discutiremos o Backtracking, o principal culpado por trás dos problemas de desempenho.

1. Tipos de Mecanismos Regex

Os mecanismos Regex geralmente se enquadram em duas categorias:

1. DFA (Autômato Finito Determinístico): Direcionado por texto e rápido, mas não suporta recursos avançados como referências anteriores. (ex: awk, lex)
2. NFA (Autômato Finito Não Determinístico): Direcionado por padrão e rico em recursos, mas pode ser extremamente lento nos piores cenários. (ex: Java, Python, Ruby, JavaScript e a maioria das linguagens modernas)

A maioria das linguagens que usamos emprega mecanismos NFA. E o mecanismo central do NFA é o Backtracking.

2. O que é Backtracking?

Backtracking é o processo em que o mecanismo de regex, ao falhar em encontrar uma correspondência, "volta para tentar um caminho diferente".

Por exemplo, vamos combinar o padrão /A.*B/ com a string A...BC.

1. Combina com A. (Sucesso)
2. .* é ganancioso, então consome o resto da string (...BC) até o fim.
3. Agora ele tenta combinar B, mas chegou ao fim da string, então falha.
4. Ocorre Backtracking: O mecanismo faz .* desistir (retroceder) do último caractere (C) e tenta novamente.
5. Ainda não é B, então ele retrocede novamente.
6. Isso se repete até encontrar B.

3. A Catástrofe: ReDoS

Se o padrão for complexo e a string for longa, o número de etapas de backtracking pode aumentar exponencialmente.

Esse fenômeno, onde o tempo de processamento explode para entradas específicas devido a padrões como (a+)+ (Quantificadores Aninhados), é chamado de ReDoS (Regular Expression Denial of Service).

Um invasor pode explorar isso enviando strings maliciosas para o seu servidor, fazendo com que o uso da CPU aumente para 100% e causando uma negação de serviço.

Dicas para Prevenir ReDoS

1. Evite Quantificadores Aninhados: Use a+ em vez de (a+)+.
2. Use Quantificadores Preguiçosos: Use .*? em vez de .* para combinar apenas o necessário.
3. Seja Específico: Em vez de .* (qualquer caractere), use intervalos restritos como [^"]* (qualquer caractere, exceto aspas).

Conclusão

Expressões Regulares são uma faca de dois gumes.

Usadas corretamente, são mágicas que transformam dezenas de linhas de código em uma. Usadas cegamente, podem ser uma bomba-relógio.

Ao escrever regex complexas, sempre considere o potencial de backtracking e crie o hábito de realizar testes de desempenho.