Motores de regex: cómo tu expresión se convierte en un autómata

Un regex mal escrito puede colgar un servidor durante minutos con una sola peticion. No es un bug exotico: se llama ReDoS y ocurre porque la mayoria de los motores de regex prueban miles de combinaciones antes de rendirse.

La razon tiene que ver con como esta construido el motor por dentro. Algunos compilan el patron en un automata que recorre el texto una sola vez. Otros prueban caminos uno por uno y a veces retroceden sin limite. Entender esa diferencia es lo que separa un validador de formularios inofensivo de una vulnerabilidad de denegacion de servicio.

TL;DR

• Entenderas como un patron de regex se compila en un automata (NFA) via la construccion de Thompson.- Vas a poder detectar patrones vulnerables a ReDoS antes de que lleguen a produccion, como (a+)+$.- Vas a distinguir un motor con backtracking (PCRE, Python re, V8) de uno basado en automatas (RE2, regex de Rust).- Vas a instalar y probar RE2 en Python con pip install google-re2 para garantizar tiempo lineal.- Vas a poder medir con tu propio reloj si una regex tiene complejidad exponencial en el peor caso.- Vas a conocer la maquina virtual de Pike, la base de RE2 y del motor regex de Rust y Go.- Vas a saber cuando SI necesitas backreferences y lookaround, y cuando conviene sacrificarlos por seguridad.

Que es un motor de regex y por que importa

Un motor de regex es el programa que toma un patron como /ab*c/ y decide si una cadena de texto lo cumple. No interpreta el patron caracter por caracter de forma ingenua: primero lo convierte en una estructura interna que puede ejecutar de forma eficiente.

Existen dos familias de motores de regex segun como resuelven esa ejecucion. La primera, la mas comun, prueba alternativas y retrocede cuando falla (backtracking). La segunda compila el patron en un automata finito y avanza sin retroceder nunca. Esa decision de diseño afecta directamente el rendimiento, las funciones que el motor puede ofrecer y su seguridad frente a entradas maliciosas.

Motores como PCRE (usado por PHP y muchas herramientas de linting), el modulo re de Python y el motor Irregexp de V8 en JavaScript usan backtracking. Motores como RE2 de Google, el crate regex de Rust y el paquete regexp de Go usan automatas.

Como funciona por dentro: de la expresion al automata

El parser: de texto a arbol sintactico

Lo primero que hace cualquier motor es parsear el patron. a(b|c)*d se convierte en un arbol donde cada nodo representa una operacion: concatenacion, alternancia (|) o repeticion (*, +, ?). Este arbol es identico sea cual sea la familia de motor; la diferencia empieza en el siguiente paso.

Construccion de Thompson: del arbol al NFA

Ken Thompson describio en 1968 un algoritmo para convertir ese arbol en un automata finito no determinista (NFA) con un numero de estados proporcional al tamaño del patron. Cada operacion del arbol (concatenar, alternar, repetir) tiene una regla fija para combinar fragmentos de automata en uno mas grande. El resultado es un grafo de estados conectados por transiciones de caracter o transiciones vacias (epsilon).

flowchart TD
 A["Patron: /ab*c/"] --> B["Parser: arbol sintactico"]
 B --> C["Construccion de Thompson"]
 C --> D["NFA (no determinista)"]
 D --> E["Subset construction"]
 E --> F["DFA (determinista)"]
 F --> G["Texto de entrada"]
 G --> H["Match o no match"]

Lo importante de la construccion de Thompson, y la razon por la que Russ Cox la documento en detalle, es que el NFA resultante tiene un tamaño lineal respecto al patron. Eso es lo que permite despues ejecutar el match sin explotar en tiempo.

flowchart LR
 S0(("inicio")) -- "a" --> S1(("medio"))
 S1 -- "b" --> S1
 S1 -- "c" --> S2(("aceptar"))

Determinizacion: de NFA a DFA

Un NFA puede estar en varios estados a la vez, lo que en teoria obligaria a explorar ramas. El algoritmo de subset construction convierte ese NFA en un DFA (automata determinista) donde cada estado del DFA representa un conjunto de estados posibles del NFA. El motor final recorre el texto una sola vez, un caracter a la vez, sin retroceder jamas.
Un DFA solo necesita un puntero y una tabla de transiciones por estado.

Backtracking: como funcionan PCRE, Python re y JavaScript

La mayoria de los lenguajes de programacion no usan automatas puros porque quieren ofrecer funciones que un automata finito no puede expresar: backreferences (\1) y lookahead/lookbehind con contenido variable. Para soportarlas, el motor prueba el patron como si fuera una busqueda con retroceso: si una alternativa falla, vuelve atras y prueba la siguiente.

Ese enfoque funciona bien en el caso comun. El problema aparece cuando el patron tiene cuantificadores anidados sobre el mismo texto, como (a+)+ o (a|a)*. Ahi el numero de formas de dividir la cadena entre los grupos crece de forma exponencial con la longitud de la entrada.

Por que explota: ReDoS explicado

ReDoS (Regular Expression Denial of Service) es la clase de vulnerabilidad que resulta de ese comportamiento. Un atacante manda una cadena diseñada para maximizar los intentos de backtracking (por ejemplo muchas a seguidas de un caracter que rompe el match) y el servidor queda ocupado evaluando esa unica peticion.

⚠️ Ojo: un patron como ^(a+)+$ parece inofensivo en pruebas con cadenas cortas. El costo solo se nota cuando alguien manda una cadena de miles de caracteres sin el sufijo que hace match, y ahi el motor prueba todas las particiones posibles antes de rendirse.

import re

patron = r"^[\w.+-]+@[\w-]+\.[a-zA-Z]{2,}$"
correo = "[e-mail]"

if re.match(patron, correo):
 print("Correo valido")
else:
 print("Correo invalido")

Este primer ejemplo compila un patron simple sin cuantificadores anidados. El motor de Python (backtracking) lo resuelve en un solo intento por caracter porque no hay ambiguedad en como dividir la cadena entre grupos.

Ejemplos practicos progresivos

import re
import time

patron_peligroso = re.compile(r"(a+)+$")
entrada = "a" * 30 + "!"

inicio = time.time()
patron_peligroso.match(entrada)
print(f"tiempo: {time.time() - inicio:.4f}s")

Aca el grupo (a+)+ puede dividir la racha de "a" de muchisimas formas distintas antes de comprobar que nunca aparece el $ esperado tras un "!". Subi el numero de "a" de 25 a 30 a 35 en tu propia maquina y vas a ver que el tiempo no crece de forma proporcional: crece multiplicandose, porque cada caracter adicional duplica aproximadamente las combinaciones posibles.

flowchart TD
 subgraph Backtracking
 B1["Intento 1: grupo vacio"] --> B2["Intento 2: divide en 2"]
 B2 --> B3["Intento 3: divide en 3"]
 B3 --> B4["... miles de combinaciones"]
 end
 subgraph Automatas
 A1["Un paso por caracter"] --> A2["Sin retroceso"]
 A2 --> A3["Tiempo lineal garantizado"]
 end

Como probarlo paso a paso

Para confirmar en tu propia maquina la diferencia entre un motor con backtracking y uno basado en automatas, instala RE2 en Python:

pip install google-re2

import re2

patron_seguro = re2.compile(r"(a+)+$")
entrada = "a" * 10000 + "!"
patron_seguro.match(entrada) # tiempo lineal, no se cuelga

Si preferis Rust, el crate regex ofrece la misma garantia:

cargo add regex

use regex::Regex;

fn main() {
 let re = Regex::new(r"(a+)+$").unwrap();
 let texto = "a".repeat(10000) + "!";
 println!("{}", re.is_match(&texto));
}

Para verificar que estas usando el motor correcto: RE2 y el crate regex de Rust rechazan backreferences al compilar el patron (error de sintaxis en vez de aceptar), mientras que PCRE y Python re los aceptan sin quejarse. Tambien podes medir el tiempo con time.time(): si duplicar el tamaño de la entrada duplica el tiempo de ejecucion, el motor es lineal; si lo multiplica mucho mas, estas frente a backtracking exponencial.
RE2 y el crate regex de Rust sacrifican backreferences por una garantia de tiempo.

Casos de uso reales

• Web Application Firewalls (WAF): procesan regex contra trafico no confiable, por eso muchos migraron a motores basados en automatas para evitar ReDoS.- Linters y compiladores: usan backtracking porque el patron lo escribe el propio desarrollador del proyecto, no un atacante externo.- Servicios que aceptan regex del usuario (buscadores de logs, validadores configurables): son el caso de mayor riesgo si usan un motor con backtracking sin limite de tiempo.- Bases de datos y proxies como los que implementan reglas de enrutamiento con regex: suelen preferir RE2 por su garantia de tiempo.

Errores comunes y buenas practicas

• Cuantificadores anidados: patrones como (a+)+, (a*)* o (a|a)* son la firma clasica de ReDoS. Evitalos o reescribilos sin anidar el mismo caracter dos veces.- Confiar en timeouts como unica defensa: un timeout evita que el servidor se cuelgue, pero sigue gastando CPU en cada intento hasta que expira.- No validar regex que vienen de input externo: si un usuario puede subir su propio patron (por ejemplo en un buscador configurable), ese patron deberia correr en un motor automata, no en uno con backtracking.- Asumir que greedy y lazy cambian la complejidad: cambiar + por +? (lazy) no arregla un ReDoS estructural, solo cambia el orden en que se prueban las alternativas.

💡 Tip: herramientas como safe-regex o los linters de ESLint con la regla no-misleading-character-class y similares pueden detectar patrones con cuantificadores anidados antes de que lleguen a produccion.

Comparativa con alternativas

MotorTipoComplejidad garantizadaBackreferences / lookaroundCuando usarloPCRE (PHP, herramientas de linting)BacktrackingExponencial en el peor casoSiPatron fijo, escrito por el propio equipoPython re (stdlib)BacktrackingExponencial en el peor casoSiScripts y validaciones con input controladoJavaScript (V8 Irregexp)Backtracking con optimizacionesExponencial en el peor casoSiValidacion de formularios con patrones acotadosRE2 (Google)Automata (Thompson NFA + maquina de Pike)Lineal O(n)NoProcesar regex o texto no confiableregex de RustAutomata (maquina de Pike)Lineal O(n)NoSistemas donde el rendimiento predecible es criticoGo regexp (stdlib)Automata (basado en RE2)Lineal O(n)NoServicios backend que procesan input externo

Profundizando: la maquina virtual de Pike y el costo real de las capturas

Rob Pike diseño una variante de ejecucion de NFA que ademas de decidir si hay match, puede reportar donde empiezan y terminan los grupos capturados, sin renunciar a la garantia de tiempo lineal. Esa tecnica, conocida como maquina virtual de Pike, es la que usan tanto RE2 como el crate regex de Rust para ofrecer group(1) sin backtracking.

La forma en que lo logran es simulando todos los estados posibles del NFA en paralelo, un caracter a la vez, en vez de probarlos uno por uno como hace el backtracking. El costo es proporcional al numero de estados del automata multiplicado por el largo del texto, nunca exponencial.

💭 Clave: la razon real por la que PCRE, Python y JavaScript siguen usando backtracking no es ignorancia de estas tecnicas. Es que backreferences como (\w+)\1 no se pueden expresar con un automata finito: el problema de reconocer esas cadenas no es regular en el sentido formal, y ahi el backtracking (o algo peor) es inevitable.

Esa es la eleccion de fondo: expresividad total con riesgo de tiempo exponencial, o tiempo lineal garantizado sacrificando backreferences y lookaround con contenido variable. Ningun motor resuelve ambos lados sin concesiones.

📖 Resumen en Telegram: Ver resumen

Tu proximo paso: tomá una regex que ya uses en produccion, corre pip install google-re2 y compilala con re2.compile() para ver si el motor automata la acepta sin cambios.

Preguntas frecuentes

Que es ReDoS y como me afecta

ReDoS es una denegacion de servicio causada por un patron de regex que, frente a cierta entrada, hace que el motor pruebe una cantidad exponencial de combinaciones antes de fallar. Afecta a cualquier servicio que evalue regex contra input que no controla por completo.

Por que PCRE no usa automatas si son mas rapidos en el peor caso

Porque PCRE ofrece backreferences y lookaround con contenido variable, funciones que no se pueden representar con un automata finito puro. Renunciar a backtracking significaria renunciar a esas funciones.

Como se si mi regex es vulnerable a backtracking catastrofico

Busca cuantificadores anidados sobre el mismo conjunto de caracteres, como (a+)+, (a*)* o alternancias solapadas como (a|a)*. Si tu patron tiene esa forma, probala con entradas largas y medi el tiempo.

Es RE2 mas lento que PCRE para casos simples

Puede tener un pequeño costo fijo al compilar el automata, pero su tiempo de ejecucion crece de forma lineal siempre, mientras que PCRE puede ser mas rapido en el caso comun y mucho mas lento (o colgarse) en el peor caso.

Funcionan lookahead y lookbehind en RE2

No. RE2 y el crate regex de Rust rechazan al compilar cualquier patron con backreferences o lookaround de contenido variable, precisamente porque romperian la garantia de tiempo lineal.

Que lenguajes usan motores basados en automatas por defecto

Go usa regexp, basado en RE2, por defecto. Rust usa el crate regex, tambien basado en automatas. Python y JavaScript usan backtracking por defecto, aunque en Python se puede instalar google-re2 como alternativa.

Referencias

• Regular Expression Matching Can Be Simple And Fast, Russ Cox: el articulo que popularizo la comparacion entre backtracking y automatas.- RE2 en GitHub: codigo fuente y documentacion del motor de Google.- Documentacion oficial del modulo re de Python: referencia del motor con backtracking de la stdlib.- Documentacion del crate regex de Rust: implementacion basada en la maquina de Pike.- MDN: expresiones regulares en JavaScript: guia de la sintaxis soportada por V8.

📱 ¿Te gusta este contenido? Únete a nuestro canal de Telegram @programacion donde publicamos a diario lo más relevante de tecnología, IA y desarrollo. Resúmenes rápidos, contenido fresco todos los días.