Como posso reconhecer um regex maligno?

Recentemente, tomei conhecimento dos ataques de negação de serviço de expressão regular e decidi eliminar os chamados padrões de regex ‘malignos’ sempre que eu os encontrava em minha base de código – ou pelo menos aqueles usados ​​na input do usuário. Os exemplos dados no link OWASP acima e na Wikipédia são úteis, mas eles não fazem um ótimo trabalho em explicar o problema em termos simples.

Uma descrição de regexes malignos, da wikipedia :

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

Com exemplos, novamente da wikipedia :

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

Este é um problema que simplesmente não tem uma explicação mais simples? Estou à procura de algo que torne mais fácil evitar esse problema ao escrever regexes ou encontrá-los em uma base de código existente.

Por que os regexes malignos são um problema?

Porque os computadores fazem exatamente o que você manda, mesmo que não seja o que você quis dizer ou seja totalmente irracional. Se você pedir a um mecanismo do Regex para provar que, para alguma input específica, existe ou não uma correspondência para um determinado padrão, o mecanismo tentará fazer isso independentemente de quantas combinações diferentes devam ser testadas.

Aqui está um padrão simples inspirado no primeiro exemplo no post do OP:

 ^((ab)*)+$ 

Dada a input:

abababababababababababab

O mecanismo regex tenta algo como (abababababababababababab) e uma correspondência é encontrada na primeira tentativa.

Mas então nós jogamos a chave de macaco em:

abababababababababababab a

O motor tentará primeiro (abababababababababababab) mas isso falha por causa disso. Isso causa um rastreamento catastrófico, porque nosso padrão (ab)* , em uma demonstração de boa fé, liberará uma de suas capturas (será “retrocedido”) e permitirá que o padrão externo tente novamente. Para o nosso mecanismo de regex, parece algo como isto:

(abababababababababababab) – Não
(ababababababababababab)(ab) – Não
(abababababababababab)(abab) – Não
(abababababababababab)(ab)(ab) – Não
(ababababababababab)(ababab) – Não
(ababababababababab)(abab)(ab) – Não
(ababababababababab)(ab)(abab) – Não
(ababababababababab)(ab)(ab)(ab) – Não
(abababababababab)(abababab) – Não
(abababababababab)(ababab)(ab) – Não
(abababababababab)(abab)(abab) – Não
(abababababababab)(abab)(ab)(ab) – Não
(abababababababab)(ab)(ababab) – Não
(abababababababab)(ab)(abab)(ab) – Não
(abababababababab)(ab)(ab)(abab) – Não
(abababababababab)(ab)(ab)(ab)(ab) – Não
(ababababababab)(ababababab) – Não
(ababababababab)(abababab)(ab) – Não
(ababababababab)(ababab)(abab) – Não
(ababababababab)(ababab)(ab)(ab) – Não
(ababababababab)(abab)(abab)(ab) – Não
(ababababababab)(abab)(ab)(abab) – Não
(ababababababab)(abab)(ab)(ab)(ab) – Não
(ababababababab)(ab)(abababab) – Não
(ababababababab)(ab)(ababab)(ab) – Não
(ababababababab)(ab)(abab)(abab) – Não
(ababababababab)(ab)(abab)(ab)(ab) – Não
(ababababababab)(ab)(ab)(ababab) – Não
(ababababababab)(ab)(ab)(abab)(ab) – Não
(ababababababab)(ab)(ab)(ab)(abab) – Não
(ababababababab)(ab)(ab)(ab)(ab)(ab) – Não

(ab)(ab)(ab)(ab)(ab)(ab)(ab)(ab)(abababab) – Não
(ab)(ab)(ab)(ab)(ab)(ab)(ab)(ab)(ababab)(ab) – Não
(ab)(ab)(ab)(ab)(ab)(ab)(ab)(ab)(abab)(abab) – Não
(ab)(ab)(ab)(ab)(ab)(ab)(ab)(ab)(abab)(ab)(ab) – Não
(ab)(ab)(ab)(ab)(ab)(ab)(ab)(ab)(ab)(ababab) – Não
(ab)(ab)(ab)(ab)(ab)(ab)(ab)(ab)(ab)(abab)(ab) – Não
(ab)(ab)(ab)(ab)(ab)(ab)(ab)(ab)(ab)(ab)(abab) – Não
(ab)(ab)(ab)(ab)(ab)(ab)(ab)(ab)(ab)(ab)(ab)(ab) – Nope

O número de combinações possíveis aumenta exponencialmente com o comprimento da input e, antes que você perceba, o mecanismo regex está consumindo todos os resources do sistema tentando resolver isso até que, tendo esgotado todas as combinações possíveis de termos, ele finalmente desiste e relatórios “Não há correspondência”. Enquanto isso, seu servidor se transformou em uma pilha de metal fundido em chamas. (Curiosamente, isso é basicamente como um brute-forcer de senha funciona, pois isso está na mesma class de problemas .)

Como Manchar Regexes Malignos

Na verdade é muito complicado. Eu mesmo escrevi um casal, embora eu saiba o que eles são e geralmente como evitá-los. Veja Regex levando surpreendentemente muito tempo . Envolver tudo o que você puder em um grupo atômico pode ajudar a evitar o problema de retrocesso. Basicamente, ele diz ao mecanismo de regex para não revisitar uma determinada expressão – “bloquear o que quer que você tenha combinado na primeira tentativa”. Note, no entanto, que as expressões atômicas não impedem o retrocesso na expressão, então ^(?>((ab)*)+)$ ainda é perigoso, mas ^(?>(ab)*)+$ é seguro ( vai corresponder (abababababababababababab) e, em seguida, recusar-se a desistir de qualquer um dos caracteres correspondentes, evitando assim um retrocesso catastrófico).

Infelizmente, uma vez que está escrito, é realmente muito difícil encontrar um problema regex imediatamente ou rapidamente. No final, reconhecer um regex ruim é como reconhecer qualquer outro código ruim – é preciso muito tempo e experiência e / ou um único evento catastrófico.


Curiosamente, desde que esta resposta foi escrita pela primeira vez, uma equipe da Universidade do Texas em Austin publicou um artigo descrevendo o desenvolvimento de uma ferramenta capaz de realizar análises estáticas de Expressões Regulares com o propósito expresso de encontrar esses padrões “malignos”. A ferramenta foi desenvolvida para analisar programas Java, mas eu suspeito que nos próximos anos veremos mais ferramentas desenvolvidas em torno de análise e detecção de padrões problemáticos em JavaScript e outras linguagens, especialmente à medida que a taxa de ataques ReDoS continua a subir .

Detecção estática de vulnerabilidades de DoS em programas que usam expressões regulares
Valentin Wüstholz, Oswaldo Olivo, Marijn JH Heule e Isil Dillig
A Universidade do Texas em Austin

Eu resumiria como “repetição de repetição”. O primeiro exemplo que você listou é bom, já que ele diz “a letra a, uma ou mais vezes seguidas. Isso pode acontecer novamente uma ou mais vezes seguidas”.

O que procurar neste caso é a combinação dos quantificadores, como * e +.

Uma coisa um pouco mais sutil de se olhar é a terceira e a quarta. Esses exemplos contêm uma operação OR, na qual ambos os lados podem ser verdadeiros. Isso combinado com um quantificador da expressão pode resultar em um lote de possíveis correspondências, dependendo da cadeia de input.

Para resumir, estilo TLDR:

Tenha cuidado como os quantificadores são usados ​​em combinação com outros operadores.

O que você chama de regex “maligno” é um regex que exibe um retrocesso catastrófico . A página vinculada (que eu escrevi) explica o conceito em detalhes. Basicamente, o retrocesso catastrófico acontece quando uma regex não coincide e diferentes permutações da mesma regex podem encontrar uma correspondência parcial. O mecanismo de regex, em seguida, tenta todas essas permutações. Se você quiser revisar seu código e inspecionar seus regexes, estes são os três principais problemas a serem observados:

  1. Alternativas devem ser mutuamente exclusivas. Se várias alternativas puderem corresponder ao mesmo texto, o mecanismo tentará as duas se o restante da expressão regular falhar. Se as alternativas estiverem em um grupo repetido, haverá um retrocesso catastrófico. Um exemplo clássico é (.|\s)* para corresponder a qualquer quantidade de qualquer texto quando o sabor de regex não tiver um modo de “quebra de linha corresponde a quebras de linha”. Se isso fizer parte de uma regex mais longa, uma string de assunto com espaços de tempo suficientemente longos (combinados por ambos . E \s ) interromperá a regex. A correção é usar (.|\n)* para tornar as alternativas mutuamente exclusivas ou até melhores para especificar quais caracteres são realmente permitidos, como [\r\n\t\x20-\x7E] para printables em ASCII , guias e quebras de linha.

  2. Os tokens quantificados que estão em sequência devem ser mutuamente exclusivos entre si ou serem mutuamente exclusivos, o que os separa. Caso contrário, ambos podem corresponder ao mesmo texto e todas as combinações dos dois quantificadores serão tentadas quando o restante da regex não corresponder. Um exemplo clássico é a.*?b.*?c para combinar 3 coisas com “qualquer coisa” entre elas. Quando c não pode ser igual ao primeiro .*? expandirá caractere por caractere até o final da linha ou arquivo. Para cada expansão, o segundo .*? expandirá caractere por caractere para corresponder ao restante da linha ou arquivo. A solução é perceber que você não pode ter “nada” entre eles. A primeira corrida precisa parar em b e a segunda corrida precisa parar em c . Com caracteres simples, a[^b]*+b[^c]*+c é uma solução fácil. Como agora paramos no delimitador, podemos usar quantificadores possessivos para aumentar ainda mais o desempenho.

  3. Um grupo que contém um token com um quantificador não deve ter um quantificador próprio, a menos que o token quantificado dentro do grupo possa ser correspondido apenas com algo que seja mutuamente exclusivo com ele. Isso garante que não haja maneira de que menos iterações do quantificador externo com mais iterações do quantificador interno possam corresponder ao mesmo texto que mais iterações do quantificador externo com menos iterações do quantificador interno. Esse é o problema ilustrado na resposta do JDB.

Enquanto escrevia minha resposta, decidi que isso merecia um artigo completo no meu site . Isso agora está online também.

Eu não acho que você pode reconhecer tais regexes, pelo menos não todos eles ou não, sem restringir de forma restritiva a sua expressividade. Se você realmente se preocupa com o ReDoSs, eu tentaria protegê-los e matar o processamento deles com um tempo limite. Também pode ser possível que existam implementações RegEx que permitam limitar o valor máximo de backtracking.

Eu surpreendentemente encontrei o ReDOS algumas vezes realizando revisões de código fonte. Uma coisa que eu recomendaria é usar um tempo limite com qualquer mecanismo de Expressão Regular que você esteja usando.

Por exemplo, em C #, posso criar a expressão regular com um atributo TimeSpan .

 string pattern = @"^< ([az]+)([^<]+)*(?:>(.*)< \/\1>|\s+\/>)$"; Regex regexTags = new Regex(pattern, RegexOptions.None, TimeSpan.FromSeconds(1.0)); try { string noTags = regexTags.Replace(description, ""); System.Console.WriteLine(noTags); } catch (RegexMatchTimeoutException ex) { System.Console.WriteLine("RegEx match timeout"); } 

Esse regex é vulnerável à negação de serviço e sem o tempo limite irá girar e consumir resources. Com o tempo limite, ele lançará uma RegexMatchTimeoutException após o tempo limite especificado e não fará com que o uso do recurso leve a uma condição de negação de serviço.

Você vai querer experimentar o valor de tempo limite para garantir que ele funcione para seu uso.

Eu diria que isso está relacionado ao mecanismo regex em uso. Talvez você nem sempre consiga evitar esses tipos de expressões regulares, mas se o mecanismo de regex for criado corretamente, será um problema menor. Veja esta série de blog para uma grande quantidade de informações sobre o tema dos motores regex.

Observe a advertência na parte inferior do artigo, em que o retrocesso é um problema NP-Complete. Atualmente, não há como processá-los com eficiência, e você pode querer desautorizá-los em sua input.

Detectando regexes malignos

Experimente o projeto RegexStaticAnalysis de Nicolaas Weideman.

Regras de ouro

Regexes maus são sempre devidos à ambigüidade no NFA correspondente, que você pode visualizar com ferramentas como o regexper .

Aqui estão algumas formas de ambiguidade. Não use isso em seus regexes.

  1. Quantificadores de aninhamento como (a+)+ (também conhecido como “altura da estrela> 1”). Isso pode causar uma explosão exponencial. Veja a ferramenta safe-regex .
  2. Disjunções de sobreposição quantificadas como (a|a)+ . Isso pode causar uma explosão exponencial.
  3. Evite Adjacências Sobrepostas Quantificadas, como \d+\d+ . Isso pode causar uma explosão polinomial.

Existem algumas maneiras em que posso pensar que você poderia implementar algumas regras de simplificação, executando-as em pequenas inputs de teste ou analisando a estrutura da regex.

  • (a+)+ pode ser reduzido usando algum tipo de regra para replace operadores redundantes por apenas (a+)
  • ([a-zA-Z]+)* também pode ser simplificado com nossa nova regra de combinação de redundância para ([a-zA-Z]*)

O computador poderia executar testes executando as pequenas subexpressões do regex contra sequências geradas aleatoriamente dos caracteres ou sequências de caracteres relevantes, e vendo em quais grupos elas terminariam. Para o primeiro, o computador é como, ei, o regex quer um, então vamos tentar com 6aaaxaaq . Em seguida, ele vê que todos os a’s, e apenas o primeiro grupo, acabam em um grupo e conclui que, não importa quantos itens sejam colocados, isso não importará, já que + fica todo no grupo. O segundo, é como, ei, o regex quer um monte de letras, então vamos tentar com -fg0uj= , e então ele vê que novamente cada grupo está em um grupo, então ele se livra do + no final .

Agora precisamos de uma nova regra para lidar com as próximas: A regra de opções eliminar-irrelevantes.

  • Com (a|aa)+ , o computador dá uma olhada nele e é como, nós gostamos daquele segundo grande, mas podemos usar esse primeiro para preencher mais lacunas, vamos pegar muitos aa como podemos e ver se conseguirmos mais alguma coisa depois que terminarmos. Pode ser executado em outra string de teste, como `eaaa @ a ~ aa ‘. para determinar isso.

  • Você pode se proteger de (a|a?)+ Fazendo com que o computador perceba que as strings são correspondidas por a? não são os droides que estamos procurando, porque como sempre pode combinar com qualquer lugar, decidimos que não gostamos de coisas como (a?)+ e jogamos fora.

  • Nós protegemos de (.*a){x} fazendo com que ele perceba que os caracteres correspondidos por a já teriam sido capturados por .* . Em seguida, descartamos essa parte e usamos outra regra para replace os quantificadores redundantes em (.*){x} .

Enquanto implementar um sistema como este seria muito complicado, este é um problema complicado, e uma solução complicada pode ser necessária. Você também deve usar as técnicas que outras pessoas trouxeram, como permitir apenas o regex de uma quantidade limitada de resources de execução antes de eliminá-lo se ele não terminar.