Negação de serviço por expressão regular (ReDoS) e retrocesso catastrófico

As expressões regulares são incrivelmente poderosas, mas é difícil encontrar alguém que as considere muito intuitivas. Claro, você conhece aquele desenvolvedor que é ótimo nisso, mas a maioria sabe o suficiente para causar problemas. Infelizmente, o risco relacionado a expressões regulares e segurança é bastante alto. Não entender bem as expressões regulares pode acabar facilitando para que invasores tirem seu site do ar. Vamos usar a seguinte expressão regular como exemplo:

regex = /A(B|C+)+D/

Se analisarmos essa expressão, veremos o que ela faz:

• A A string deve começar com a letra ‘A’

• (B|C+)+ Em seguida, a string deve conter, depois da letra A, a letra ‘B’ ou uma ou mais ocorrências da letra ‘C’ (o + corresponde a uma ou mais ocorrências). O + no fim desse trecho indica que podemos procurar uma ou mais correspondências desse trecho.

• D Por fim, garantimos que esse trecho da string termine com um ‘D’

A expressão corresponderia a entradas como os exemplos a seguir:

ABBD
ABCCCCD
ABCBCCCD
ACCCCCD

De modo geral, um mecanismo de expressões regulares não leva muito tempo para encontrar uma correspondência. Por exemplo, veja o que acontece quando testamos a expressão com a seguinte string de 30 caracteres: “ACCCCCCCCCCCCCCCCCCCCCCCCCCCCD”.

$ time node -e '/A(B|C+)+D/.test("ACCCCCCCCCCCCCCCCCCCCCCCCCCCCD")'
0.04s user 0.01s system 95% cpu 0.052 total

Como esperado, a string corresponde à expressão, e isso acontece rapidamente. Todo o processo leva cerca de 52 ms (em um MacBook Air). Agora, vamos ver o que acontece quando testamos outra string de 30 caracteres. Desta vez, em vez de fornecer uma string válida, vamos fornecer uma inválida, substituindo o “D” no final por um “X”: “ACCCCCCCCCCCCCCCCCCCCCCCCCCCCX”.

$ time node -e '/A(B|C+)+D/.test("ACCCCCCCCCCCCCCCCCCCCCCCCCCCCX")'
1.79s user 0.02s system 99% cpu 1.812 total

De repente, o teste leva quase dois segundos para ser concluído — mais de dez vezes o tempo necessário para testar uma string válida! Essa diferença drástica se deve à forma como as expressões regulares são avaliadas. Em resumo, elas não desistem facilmente.

Como funcionam os mecanismos de expressões regulares

Os mecanismos de expressões regulares variam, mas a maioria funciona de maneira bem parecida. O mecanismo encontra a primeira forma possível de aceitar o caractere atual e passa para o próximo. Se não conseguir corresponder ao próximo caractere, ele retrocede para verificar se havia outra forma de processar o caractere anterior. Se avançar demais nessa busca e só então descobrir que a string não corresponde à expressão, e se muitos caracteres tiverem vários caminhos válidos na expressão, o número de etapas de retrocesso pode ficar muito alto, resultando no que chamamos de retrocesso catastrófico. Vamos ver como nossa expressão se depara com esse problema usando uma string mais curta: “ACCCX”. Embora pareça bastante simples, ainda há quatro formas diferentes de o mecanismo corresponder a esses três C:

1. CCC

2. CC+C

3. C+CC

4. C+C+C.

O mecanismo precisa testar cada uma dessas combinações para verificar se alguma delas pode corresponder à expressão. Somando isso às outras etapas necessárias, podemos usar o depurador RegEx 101 para ver que o mecanismo precisa executar 38 etapas no total antes de concluir que a string não corresponde. A partir daí, o número de etapas necessárias para validar uma string só aumenta.

Quando a string contém 14 C, o mecanismo precisa executar mais de 65.000 etapas só para verificar se ela é válida. Agora imagine esse processo aplicado à nossa string original: “ACCCCCCCCCCCCCCCCCCCCCCCCCCCCX”. Dá para ver como o retrocesso pode sair rapidamente do controle. A captura de tela a seguir mostra apenas uma pequena parte do trabalho executado pelo mecanismo, conforme relatado pelo depurador RegEx101.

Considerando a forma como o mecanismo avalia uma expressão regular, fica mais fácil entender por que o tempo necessário para processar uma expressão inválida aumenta tanto: existe uma relação exponencial entre o tamanho da string e o número de caminhos que o mecanismo precisa avaliar. Se adicionarmos apenas mais um caractere à sequência inválida, o tempo de avaliação quase dobra.

$ time node -e '/A(B|C+)+D/.test("ACCCCCCCCCCCCCCCCCCCCCCCCCCCCCX")'
3.51s user 0.06s system 95% cpu 3.732 total

Node e ReDoS

Agentes mal-intencionados podem explorar as complexidades da análise de expressões regulares enviando uma string longa e complicada que faça o mecanismo levar um tempo excessivo para avaliá-la, causando o que chamamos de ataque de negação de serviço por expressão regular (ReDoS).

Isso certamente não é ideal em nenhum ambiente, mas é ainda pior em ambientes JavaScript, inclusive no Node. Como explicamos ao falar sobre ataques de temporização em um post anterior, o Node.js (e o JavaScript em geral) é orientado a eventos.

Isso significa que, se uma thread estiver ocupada com uma solicitação ReDoS bem-sucedida, ela bloqueará todo o loop de eventos, impedindo que o aplicativo execute qualquer outro processamento.

Um exemplo do mundo real

Vamos analisar um exemplo recente do mundo real encontrado na popular moment biblioteca. moment é usada para analisar, validar, manipular e formatar datas. Com essa ferramenta, você pode especificar o formato desejado para a data usando o método format():

moment().format('MMM Do YY');

//example output: Nov 22nd 16

Ao definir o formato, moment usa uma expressão regular para validá-lo. Nas versões de moment anteriores à 2.15.2, a expressão regular é assim:

var MONTHS_IN_FORMAT = /D[oD]?(\[[^\[\]]*\]|\s+)+MMMM?/;

O ponto principal aqui é o trecho (\[[^\[\]]*\]|\s+)+ da expressão. Vale destacar que \s+ verifica a presença de um ou mais espaços. No entanto, o + logo após esse grupo também significa que o grupo entre parênteses pode aparecer uma ou mais vezes. Isso significa que, se houver muitos espaços no formato, o mecanismo de expressões regulares pode tentar agrupá-los de várias maneiras para encontrar uma correspondência. Eles podem ser agrupados em um único grupo grande, correspondido uma vez; divididos em grupos individuais, cada um correspondido separadamente; ou organizados de qualquer outra forma entre esses extremos. O resultado é que a avaliação de uma string quase válida pode levar muito tempo.

Veja este exemplo que publicamos quando encontramos a vulnerabilidade:

var m = require("moment");
m.locale("be");
m().format("D                               MMN MMMM");
// Normal date format, other than the 31 spaces included in the string

Neste caso, passamos uma string de 40 caracteres com vários espaços. Ao executar o teste em um laptop padrão, vimos que a expressão bloqueava o loop de eventos por cerca de 20 segundos.

$ time node -e '/D[oD]?(\[[^\[\]]*\]|\s+)+MMMM?/.test("D                               MMN MMMM");'
21.24s user 0.14s system 96% cpu 22.079 total

Depois que divulgamos a vulnerabilidade à equipe de moment, o autor preparou uma correção (você pode testar agora para verificar se o patch se aplica ao seu caso), removendo o operador + desnecessário de dentro dos parênteses:

var MONTHS_IN_FORMAT = /D[oD]?(\[[^\[\]]*\]|\s)+MMMM?/;

Com isso, você elimina dois grupos de correspondência diferentes, cada um dos quais poderia incluir desde um até todos os espaços. Como o operador + não vem mais depois do s, ele só pode corresponder a um espaço de cada vez. Ao testar a string novamente com a nova expressão regular, o mecanismo leva apenas alguns milissegundos para identificar que não há correspondência.

$ time node -e '/D[oD]?(\[[^\[\]]*\]|\s)+MMMM?/.test("D                               MMN MMMM");'
0.05s user 0.02s system 53% cpu 0.135 total

Como evitar o retrocesso catastrófico

Para evitar o retrocesso catastrófico, fique atento sempre que usar operadores ‘+’ ou ‘*’ próximos uns dos outros. Nesses casos, é provável que eles acabem em uma disputa que resulte em retrocesso catastrófico. Verifique se ambos os operadores são realmente necessários. Você também pode considerar substituir um deles por um intervalo limitado. Se você se lembra da vulnerabilidade ReDoS em moment, nós a corrigimos eliminando um dos operadores ‘+’. Também poderíamos ter substituído um deles por um intervalo, limitando o número de espaços permitido em uma string válida:

var MONTHS_IN_FORMAT = /D[oD]?(\[[^\[\]]*\]|\s+){0,10}MMMM?/;

A análise de expressões regulares é bastante ingênua, mas algumas linguagens introduziram recursos avançados que podem ajudar a evitar o retrocesso catastrófico. Por exemplo, vamos considerar a expressão simplificada que usamos no início:

regex = /A(B|C+)+D/

Grupos atômicos

Como vimos, a expressão pode causar retrocesso catastrófico. O analisador de expressões regulares compatível com Node.js não oferece um recurso nativo que possamos usar para eliminar o problema. Em algumas outras linguagens, porém, isso é possível. O Ruby, por exemplo, oferece suporte a grupos atômicos. Com eles, você pode instruir o analisador de expressões regulares a não retroceder depois que um grupo corresponder. Para isso, basta adicionar ?> antes de um grupo, assim:

/A(?>B|C+)+D/

Adicionar ?> ao grupo que procura uma determinada quantidade de “C” faz com que ele se torne atômico. Antes, o analisador de expressões regulares precisa considerar dois operadores concorrentes. O “C” dentro do grupo pode corresponder qualquer número de vezes, ou o próprio grupo pode corresponder qualquer número de vezes. Assim, se uma expressão inválida enviada contiver muitos caracteres “C”, o analisador ficará preso em uma disputa entre os dois grupos, tentando repetidamente encontrar alguma combinação que torne a expressão válida.

Com o agrupamento atômico, porém, o analisador fixa a correspondência desse grupo. Neste caso, ele corresponderá à quantidade de “C” presente na string. Quando a expressão for inválida, não será possível retroceder nesse grupo — a correspondência fica definida. Sem precisar redistribuir os “C” entre os dois operadores de correspondência possíveis, o mecanismo identifica rapidamente uma expressão inválida, evitando o retrocesso catastrófico.

Lookahead

Embora o JavaScript não ofereça suporte a grupos atômicos, ele oferece suporte a lookahead, que pode produzir, em linhas gerais, o mesmo efeito do agrupamento atômico.

A(?=(B|C+))\1+D

Neste caso, usamos ?= para especificar um lookahead. Isso significa que a expressão regular corresponderá a esse grupo somente se ele for seguido imediatamente pelo próximo grupo. Com \1, capturamos o grupo correspondido, criando efetivamente um grupo atômico. A partir daí, o analisador tratará essa correspondência como se fosse um grupo atômico e evitará o retrocesso catastrófico.

Se testarmos nossa string com a expressão usando lookahead, veremos que o tempo para identificá-la como inválida diminuiu drasticamente (de 1,8 segundo sem lookahead para 94 ms com ele):

$ time node -e '/A(?=(B|C+))\1+D/.test("ACCCCCCCCCCCCCCCCCCCCCCCCCCCCCX")'
0.05s user 0.02s system 51% cpu 0.094 total

A desvantagem é a complexidade. Você evita o retrocesso catastrófico, mas deixa a expressão mais complexa — não só mais difícil de entender para outras pessoas da equipe, como também mais sujeita a erros. Se conseguir identificar a combinação de operadores que pode causar retrocesso (neste caso, os dois +), talvez seja melhor reformular toda a expressão para deixá-la mais clara e legível.

Resumo

Os ataques ReDoS podem paralisar um aplicativo. Isso é especialmente verdadeiro no Node.js, onde o loop de eventos amplia ainda mais o impacto do retrocesso catastrófico.

Para evitar vulnerabilidades ReDoS, é preciso monitorar suas expressões regulares e testar suas dependências para detectar vulnerabilidades desse tipo.

Já houve algumas tentativas de criar ferramentas para detectar automaticamente expressões vulneráveis a ataques ReDoS (principalmente o safe-regex), mas, mesmo em testes limitados, encontramos vários falsos positivos e algumas expressões consideradas seguras que não eram.

Testar suas dependências é bem mais simples — e a Snyk pode fazer isso por você.

De todo modo, vale a pena experimentar. Uma ferramenta como o depurador do RegEx101 é uma ótima maneira de testar diferentes expressões e entender melhor as etapas que os analisadores de expressões regulares executam ao tentar encontrar uma correspondência.

Quem sabe — com tempo e prática suficientes, talvez um dia você seja quem aparece para salvar o dia graças ao seu conhecimento avançado de expressões regulares.