Como Evitar o Catastrophic Backtracking em Regex?

O Catastrophic Backtracking de expressões regulares refere-se ao fato de que a expressão regular retrocede excessivamente ao tentar fazer uma correspondência, causando 100% de uso da CPU e bloqueando serviços normais.

Contexto

Li um artigo detalhando o processo de descoberta e resolução de um problema de retrocesso em expressões regulares que levou a 100% de uso da CPU. O artigo original é bastante longo, e já me deparei com problemas semelhantes duas vezes antes no desenvolvimento do OpenResty.

Aqui está um breve resumo para que você não precise gastar tempo com o contexto.

1. Os motores de expressões regulares na maioria das linguagens de desenvolvimento são implementados usando NFA baseado em retrocesso (em vez de NFA baseado em Thompson).
2. O retrocesso catastrófico pode causar 100% de uso da CPU se houver muitos retrocessos.
3. É necessário analisar o dump com gdb ou systemtap para localizar o problema em um ambiente online.
4. Tais problemas são difíceis de detectar antes que o código entre em produção e exigem uma revisão caso a caso das expressões regulares.

Do ponto de vista do desenvolvimento, corrigir as expressões regulares problemáticas é o fim da história. No máximo, adicionar um mecanismo de segurança para limitar o número de retrocessos, como este no OpenResty.

lua_regex_match_limit 100000;

Dessa forma, mesmo que ocorra um retrocesso catastrófico, ele será limitado e não consumirá toda a CPU.

Bem, parece perfeito, não é? Vamos além do nível de desenvolvimento e olhar isso de uma dimensão diferente.

Ataques

Basta usar uma máquina, enviar uma requisição, e você pode derrubar o servidor do outro lado. Isso é simplesmente o sonho de um hacker de ter uma arma nuclear. Comparado a isso, o DDoS é fraco, pois exige muito movimento e é caro.

Esse ataque também tem seu próprio nome: ReDoS (RegEx Denial of Service).

Como as expressões regulares são amplamente utilizadas e existem em quase todas as partes dos serviços de back-end, há uma oportunidade de explorar uma das vulnerabilidades.

Imagine um cenário em que um hacker descobre uma vulnerabilidade de ReDoS no WAF e envia uma requisição para derrubar o WAF; você não consegue localizar o problema em um curto período de tempo, nem mesmo percebendo que se trata de um ataque; você escolhe reiniciar ou desligar temporariamente o WAF para manter seu negócio funcionando; enquanto o WAF está fora de ação, o hacker usa injeção de SQL para roubar seu banco de dados. Você, por outro lado, pode ainda estar completamente no escuro.

Devido ao uso generalizado de software de código aberto e serviços em nuvem, não é suficiente apenas garantir que as expressões regulares que você escreve estejam livres de vulnerabilidades. Esse é outro tópico, começaremos aqui discutindo apenas as expressões regulares que estão sob nosso controle.

Como descobrir tais expressões regulares?

O primeiro passo para resolver problemas é encontrá-los e tentar encontrar todos eles, também conhecido como a capacidade de encontrá-los com segurança.

Esperar que uma revisão manual do código encontre regras problemáticas não é confiável. A maioria dos desenvolvedores não tem consciência de segurança, e mesmo que procurassem, é improvável que conseguissem encontrar o problema em uma expressão regular complexa.

É aqui que as ferramentas de automação entram em cena.

Temos os seguintes dois métodos automatizados para resolver isso.

• Teste estático

Essas ferramentas podem escanear o código em busca de expressões regulares e, de acordo com um determinado algoritmo, encontrar as expressões com retrocesso catastrófico.

Por exemplo, RXXR2, que é implementado com base em um algoritmo de um artigo que converte expressões regulares em ε-NFA e depois as pesquisa, mas não suporta a sintaxe estendida de expressões regulares, então haverá falsos negativos.

• Fuzzing dinâmico

O teste de fuzzing é um método geral de teste de software que detecta falhas, vazamentos de memória e outros problemas ao inserir grandes quantidades de dados aleatórios por longos períodos de tempo.

Da mesma forma, podemos usar essa abordagem em testes de expressões regulares. Podemos gerar dados de teste com base em expressões regulares existentes ou gerá-los completamente aleatórios.

SlowFuzz é uma das ferramentas de código aberto, também baseada em um algoritmo de um artigo, o artigo será listado no final deste texto, é uma ferramenta de uso geral e não faz processamento para a estrutura da expressão regular, então haverá falsos negativos.

SDLFuzzer é uma ferramenta especializada em detecção de ReDoS desenvolvida pela Microsoft há alguns anos, mas não é mais mantida.

Há poucas ferramentas para escolher nesta área, e não há muita atenção. No entanto, fiquei animado ao encontrar um artigo sobre ReDoS de vários professores e doutores da Universidade de Nanjing durante minha busca por informações, e eles abriram o código da ferramenta ReScue junto com o artigo: https://2bdenny.github.io/ReScue/. Essa ferramenta identificou vulnerabilidades de ReDoS em vários projetos de código aberto.

Aqui estão os resultados dos testes comparativos no artigo.

É possível resolver de uma vez por todas?

Mesmo usando essas ferramentas, inevitavelmente haverá falsos positivos e falsos negativos, então existe uma maneira de resolver o ReDoS de uma vez por todas?

Então temos que voltar à raiz do problema para encontrar a resposta: o motor de expressões regulares usa retrocesso para correspondência.

Não seria possível se abandonássemos essa abordagem? Sim, já existem várias outras implementações de motores de expressões regulares que podem resolver isso de uma vez por todas. Todos abandonam o retrocesso e usam a abordagem de autômatos NFA/DFA, a vantagem é que são adequados para correspondência em fluxo e também são mais seguros, a desvantagem é que não suportam muitas sintaxes estendidas de expressões regulares, como referências anteriores, mas essas geralmente não são usadas mesmo.

• Google RE2

O RE2 da Google é um dos projetos de código aberto mais completos. Ele suporta a maioria das sintaxes do PCRE, e há implementações de bibliotecas para Go, Python, Perl, Node.js e outras linguagens de desenvolvimento, o custo de início e substituição é muito baixo.

Vamos usar Perl como exemplo e ver se o RE2 pode evitar problemas de retrocesso catastrófico.

Vamos dar uma olhada neste gráfico comparativo de resultados.

O código é o seguinte, você pode tentar por conta própria se estiver interessado.

time perl -e 'if ("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" =~ /a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa/) {print("hit");}'

40.80s user 0.00s system 99% cpu 40.800 total

Leva 40,8 segundos para executar essa expressão regular, durante os quais a CPU fica em 99%.

Com o RE2, o contraste é muito claro.

time perl -e 'use re::engine::RE2; if ("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" =~ /a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa/) {print(" hit");}'

perl -e 0.00s user 0.00s system 34% cpu 0.011 total

• Intel Hyperscan

O Intel Hyperscan também é um motor de expressões regulares semelhante ao RE2, e há bibliotecas para Perl, Python e outras linguagens, então não é muito difícil começar.

Apenas, de acordo com a prática da Intel, há mais vinculação à plataforma, só pode ser executado em x86.

Se houver um benefício único, pode ser a capacidade de funcionar melhor com o conjunto de instruções e hardware da Intel, com melhorias de desempenho, como combiná-lo com seu próprio DPDK.

Snort, uma ferramenta de detecção de intrusão em rede de código aberto, também usa o Hyperscan para substituir o motor de expressões regulares anterior, então alunos familiarizados com o Snort podem experimentar.

Extensões

Aqui estão alguns artigos sobre expressões regulares, que podem ser lidos como uma extensão se você estiver interessado.

1. SlowFuzz: Automated Domain-Independent Detection of Algorithmic Complexity Vulnerabilities: https://arxiv.org/pdf/1708.08437.pdf

2. Static Analysis for Regular Expression Exponential Runtime via Substructural Logics: https://arxiv.org/abs/1405.7058.pdf

3. ReScue: Crafting Regular Expression DoS Attacks: https://dl.acm.org/doi/10.1145/3238147.3238159

4. Regular Expression Matching Can Be Simple And Fast: https://swtch.com/~rsc/regexp/regexp1.html