ReDoS

Um Ataque de negação de serviço por uso de expressão regular (também conhecido como ReDoS, um acrônimo em inglês para Regular expression Denial of Service) é um ataque de complexidade algorítmica que produz uma negação-de-serviço, fornecendo uma expressão regular que leva muito tempo para ser avaliada. O ataque explora o fato de que a maioria das implementações de expressões regulares têm custo de tempo exponencial no pior caso: o tempo pode crescer exponencialmente em relação ao tamanho da entrada. Um invasor pode, portanto, fazer um programa passar uma quantidade efetivamente infinita de tempo processando fornecendo uma expressão regular como tal, deixando o programa lento ou o tornando irresponsivo.

Descrição

Reconhecimento de expressão regulares pode ser feito através da construção de um autômato finito. As expressões regulares podem ser facilmente convertidas em autômatos finitos não determinísticos (AFNs), em que, para cada estado e símbolo de entrada, podem existir vários possíveis próximos estados. Depois de construir o autômato, várias possibilidades existem:

• a máquina pode convertê-lo para um autômato finito determinístico (AFD) e executar a entrada pelo autômato resultante;
• a máquina pode tentar um por um todos os caminhos possíveis até que uma correspondência seja encontrada ou até que todos os caminhos sejam testados e falhem ("backtracking").
• a máquina pode considerar todos os caminhos possíveis através do autômato não determinístico em paralelo;
• a máquina pode converter o autômato não determinístico para um AFD preguiçosamente (por exemplo, enquanto roda, durante o reconhecimento).

Dos algoritmos acima, os dois primeiros são problemáticos. O primeiro é problemático, porque um autômato determinístico pode ter até $2^{m}$ estados onde $m$ é o número de estados do autômato não determinístico; assim, a conversão do AFN para um AFD pode levar um tempo exponencial. O segundo é problemático, porque um autômato não determinístico pode ter um número exponencial de caminhos de comprimento $n$, de modo que a caminhada através de uma entrada de comprimento $n$ também vai levar um tempo exponencial. Os dois últimos algoritmos, no entanto, não apresentam um comportamento patológico.

Note que para expressões regulares não-patológicas os algoritmos problemáticos são, normalmente, rápidos e, na prática, pode-se esperar que eles "compilem" uma expressão regular em tempo O(m) e a reconheçam em tempo O(n); em vez disso, a simulação de um AFN e a computação preguiçosa do AFD tem O(m²n) como complexidade de pior caso. Um Ataque de negação de serviço por uso de expressão regular ocorre quando essas expectativas são aplicadas a expressões regulares fornecidas pelo usuário, e expressões regulares mal-intencionadas fornecidas pelo usuário causam o pior caso de complexidade do reconhecedor de expressão regular.

Enquanto algoritmos regex podem ser escritos de uma forma eficiente, a maior parte das maquinas de expressão regular que existem estendem a linguagem de expressão regular com outras construções, que nem sempre podem ser resolvidas de forma eficiente. Tais padrões estendidos essencialmente forçam a implementação de expressões regulares na maioria das linguagens de programação a usarem backtracking.

Exemplos

Regexes maliciosos

Regexes maliciosos que ficam emperrados em entradas modificadas podem ser diferentes dependendo do reconhecedor de expressão regular que está sob ataque. Para reconhecedores com backtrack, eles ocorrem sempre que estes fatores ocorrem:

• a expressão regular aplica a repetição ("+", "*") para uma subexpressão complexa;
• para a subexpressão repetida, existe uma correspondência que também é um sufixo de outra correspondência válida.

A segunda condição é melhor explicada com um exemplo: na expressão regular (a[ab]*)⁺, tanto "a" quanto "aa" podem corresponder à subexpressão repetida a[ab]*. Portanto, após o reconhecimento de "a", o autômato não determinístico pode tentar uma nova correspondência de [ab]* ou uma correspondência de "a". Se a entrada tem muitos "a"s consecutivos, cada um deles vai dobrar o número de caminhos possíveis pelo autômato. Exemplos de regexes mal-intencionados incluem o seguinte:

• (a+)+
• ([a-zA-Z]+)*
• (a|aa)+
• (a|a?)+
• (.*a){x} para x > 10

Todos acima são suscetíveis à entrada aaaaaaaaaaaaaaaaaaaaaaaa!. (O comprimento mínimo de entrada pode mudar ligeiramente, quando usadas máquinas mais rápidas ou mais lentas.)

Outros padrões podem não causar um comportamento exponencial, mas para entradas muito longas (geralmente algumas centenas de caracteres), elas ainda podem causar um grande tempo de reconhecimento. Um exemplo de tal padrão é "a*b?a*x" e a entrada sendo um sequência arbitrariamente longa de "a"s. Tal padrão também pode causar os reconhecedores com backtrack travar.

Regexes vulneráveis em repositórios online

Os chamados regexes  "mals" ou maliciosos foram encontrados em repositórios on-line de expressões regulares. Note que é o suficiente encontrar uma subexpressão má para atacar o regex inteiro:

1. RegExLib, id=1757 (validação de e-mail) - a parte vermelha é uma Regex Má
   ^([a-zA-Z0-9])(([\-.]|[_]+)?([a-zA-Z0-9]+))*(@){1}[a-z0-9]+[.]{1}(([a-z]{2,3})|([a-z]{2,3}[.]{1}[a-z]{2,3}))$
2. Repositório de Validação de Regex da Owasp, o Nome da classe Java - a parte vermelha é uma Regex Má
   ^(([a-z])+.)+[A-Z]([a-z])+$

Estes dois exemplos também são suscetíveis a entrada aaaaaaaaaaaaaaaaaaaaaaaa!.

Ataques

Se um regex for ele próprio afetado pela entrada do usuário, o invasor pode injetar uma regex mal-intencionada e tornar o sistema vulnerável. Portanto, na maioria dos casos o ReDoS pode ser evitado eliminando a possibilidade do usuário executar padrões arbitrários no servidor. Neste caso, aplicativos web e bancos de dados são as principais aplicações vulneráveis. Alternativamente, uma página mal-intencionada pode travar o navegador da web do usuário ou fazer com que ele use uma quantidade arbitrária de memória.

No entanto, alguns dos exemplos do parágrafo acima são consideravelmente menos "artificiais" do que os outros; assim, eles demonstram como um regex vulnerável pode ser usado como um resultado de erros de programação. Neste caso scanners de email e sistemas de detecção de intrusão também podem ser vulneráveis. Felizmente, na maioria dos casos, expressões regulares problemáticas podem ser reescritas como padrões inofensivos. Por exemplo, (.*a){x} pode ser reescrita como([^a]*a){x}.

No caso de uma aplicação web, o programador pode usar a mesma expressão regular para validar a entrada no client-side e também no server-side. Um invasor pode inspecionar o código do client-side, procurando as expressões regulares más, e enviar a entrada trabalhada diretamente para o servidor web para travá-lo.

Veja Também

• Ataque de negação de serviço
• Bug f00f do Pentium
• Guerra cibernética
• Canhão de íons de baixa órbita
• Canhão de íons de alta órbita

Ligações externas

• Exemplos de ReDoS em aplicações open source:
  • ReDoS no DataVault
  • ReDoS no EntLib
  • ReDoS no NASD CORE.NET Terelik
  • ReDoS no .NET Framework
• Alguns benchmarks para ReDoS
  • Achim Hoffman (2010). "ReDoS - benchmark for regular expression DoS in JavaScript". Acesso em : 2010-04-19.
  • Richard M. Smith (2010). "Regular expression denial of service (ReDoS) attack test results". Acesso em : 2010-04-19.
• Artigo na implementação de expressões regulares invulneráveis a certas classes de ReDoS
  • Russ Cox (2007). "Regular Expression Matching Can Be Simple And Fast". Acesso em : 2011-04-20.
• Uma ferramenta para a detecção de vunerabilidades a ReDoS
  • H. Thielecke, A. Rathnayake (2013). "Regular expression denial of service (ReDoS) static analysis". Acesso em : 2013-05-30.