¿Cómo funcionan las expresiones regulares? (Backtracking y rendimiento)

Es probable que todo desarrollador haya utilizado Expresiones Regulares (Regex) en algún momento para la validación de correo electrónico o el análisis de cadenas.

Si bien es una herramienta poderosa y conveniente, ¿sabías que una sola expresión regular mal escrita puede derribar un servidor completo?

En este artículo, exploraremos la mecánica interna de los motores de expresiones regulares y discutiremos el Backtracking, el principal culpable de los problemas de rendimiento.

1. Tipos de Motores Regex

Los motores Regex generalmente se dividen en dos categorías:

1. DFA (Autómata Finito Determinista): Dirigido por texto y rápido, pero carece de soporte para funciones avanzadas como referencias inversas. (ej., awk, lex)
2. NFA (Autómata Finito No Determinista): Dirigido por patrones y rico en funciones, pero puede ser extremadamente lento en los peores escenarios. (ej., Java, Python, Ruby, JavaScript y la mayoría de los lenguajes modernos)

La mayoría de los lenguajes que usamos emplean motores NFA. Y el mecanismo central de NFA es el Backtracking.

2. ¿Qué es el Backtracking?

El Backtracking es el proceso en el que el motor de expresiones regulares, al no encontrar una coincidencia, "retrocede para intentar un camino diferente".

Por ejemplo, hagamos coincidir el patrón /A.*B/ con la cadena A...BC.

1. Coincide con A. (Éxito)
2. .* es codicioso, por lo que consume el resto de la cadena (...BC) hasta el final.
3. Ahora intenta coincidir con B, pero ha llegado al final de la cadena, por lo que falla.
4. Ocurre Backtracking: El motor hace que .* renuncie (retroceda) al último carácter (C) e intenta de nuevo.
5. Todavía no es B, así que retrocede de nuevo.
6. Esto se repite hasta que encuentra B.

3. La Catástrofe: ReDoS

Si el patrón es complejo y la cadena es larga, el número de pasos de backtracking puede aumentar exponencialmente.

Este fenómeno, donde el tiempo de procesamiento explota para entradas específicas debido a patrones como (a+)+ (Cuantificadores Anidados), se llama ReDoS (Regular Expression Denial of Service).

Un atacante puede explotar esto enviando cadenas maliciosas a tu servidor, causando que el uso de la CPU aumente al 100% y provocando una denegación de servicio.

Consejos para Prevenir ReDoS

1. Evita Cuantificadores Anidados: Usa a+ en lugar de (a+)+.
2. Usa Cuantificadores Perezosos: Usa .*? en lugar de .* para coincidir solo tanto como sea necesario.
3. Sé Específico: En lugar de .* (cualquier carácter), usa rangos restringidos como [^"]* (cualquier carácter excepto una comilla).

Conclusión

Las Expresiones Regulares son un arma de doble filo.

Usadas correctamente, son magia que convierte docenas de líneas de código en una sola. Usadas ciegamente, pueden ser una bomba de tiempo.

Al escribir expresiones regulares complejas, siempre considera el potencial de backtracking y acostúmbrate a realizar pruebas de rendimiento.