Catastrophic Backtracking

Expressões regulares são uma ferramenta poderosa para encontrar padrões em textos. Mas, nem tudo são flores.. Uma das coisas que podem atrapalhar o uso de expressões regulares é o Catastrophic Backtracking.

O que é o Catastrophic Backtracking?

O Catastrophic Backtracking é um problema que ocorre quando uma expressão regular é executada em um texto muito grande e que possui um padrão muito específico. O interpretador da expressão regular acaba levando bastante tempo para encontrar o padrão e, por isso, ou o sistema fica lento ou até mesmo pode travar por causa disto.

Um exemplo de como esse problema realmente é sério:
Imagine que no front você tenha um input de texto, e que por algum motivo você utiliza uma expressão regular para validar esse texto digitado. Se o usuário ou uma pessoa mal intencionada digitar um texto muito grande e que contenha um padrão específico, com certeza o Catastrophic Backtracking irá ocorrer, e o estrago você já sabe.

Exemplo do site Regular-Expressions.info utilizando a regex ^(.*?,){11}P no RegexBuddy’s debugger:

Como evitar o Catastrophic Backtracking?

• Limite a quantidade de caracteres, tanto no input quanto no regex
• Evite muitas opções de match, busque formas de ser mais específico
• Evite usar muitos metacaracteres como o + ou *, use-os apenas quando necessário!
• • Info: * - Corresponde ao caractere precedente zero ou mais vezes. Por exemplo, zo* corresponde a z ou zoo.
• • Info: + - Corresponde ao caractere precedente uma ou mais vezes. Por exemplo, zo+ corresponde a zoo, mas não a z.
• Teste sua regex antes de colocar em produção, eu utilizo bastante o site: RegExr ou o RegEx101.
  
  

Fontes:

• Runaway Regular Expressions: Catastrophic Backtracking
• Checking Strings: Avoiding Catastrophic Backtracking
• Metacaracteres em Expressões Regulares