💻 computer science

PUFFERDOS: Efficient and Effective Attack String Generation for Regular Expression Denial of Service Vulnerabilities

Este artículo presenta PUFFERDOS, una nueva herramienta que genera cadenas de ataque ReDoS prácticas y efectivas mediante la síntesis de entradas basadas en tres patrones vulnerables formalmente verificados y su refinamiento a través de la ejecución concolica composicional para asegurar la explotabilidad en el mundo real dentro de presupuestos de longitud realistas.

Autores originales: Shangzhi Xu, Ziqi Ding, Xiao Cheng, Yuekang Li, Nan Sun, Benjamin Turnbull, Shuangxiang Kan, Siqi Ma

Publicado 2026-06-19

📖 5 min de lectura🧠 Análisis profundo

CC BY 4.0

Autores originales: Shangzhi Xu, Ziqi Ding, Xiao Cheng, Yuekang Li, Nan Sun, Benjamin Turnbull, Shuangxiang Kan, Siqi Ma

Artículo original bajo licencia CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta es una explicación generada por IA del artículo a continuación. No ha sido escrita ni avalada por los autores. Para mayor precisión técnica, consulte el artículo original. Leer descargo de responsabilidad completo

Imagina que tienes a un guardia de seguridad muy inteligente, pero ligeramente obsesivo, en la puerta de un edificio. Su trabajo es comprobar si tu tarjeta de identificación (la entrada) coincide con un patrón específico (la expresión regular, o "regex"). Normalmente, esto es rápido y fácil.

Pero hay un truco. Si le entregas una tarjeta de identificación muy específica y confusa, el cerebro del guardia se queda atrapado en un bucle. Empieza a comprobar todas las formas posibles en las que tu identificación podría coincidir con el patrón, una y otra vez, hasta que se queda sin energía y se desmaya. Esto se llama un ataque ReDoS (Denegación de Servicio por Expresión Regular). Es como engañar a una calculadora para que haga matemáticas para siempre hasta que se bloquea.

Durante mucho tiempo, los investigadores de seguridad han intentado encontrar estas trampas y crear "identificaciones de prueba" para demostrar que el guardia está averiado. Sin embargo, los métodos antiguos tenían dos grandes problemas:

Las identificaciones eran demasiado largas: Requerían entradas tan enormes (como un libro lleno de texto) que ningún sitio web real aceptaría jamás.
No encajaban con el edificio: Probaban al guardia de forma aislada, ignorando el hecho de que en un edificio real puede haber otros guardias (filtros) que detengan tu identificación antes de que llegue a la puerta principal.

Aquí entra PUFFERDOS. Piensa en PUFFERDOS como un maestro cerrajero que no solo elige la cerradura, sino que descubre exactamente cómo caminar por todo el edificio para llegar a la cerradura, utilizando la llave más corta y eficiente posible.

Así es como funciona PUFFERDOS, desglosado en pasos sencillos:

1. La estrategia del "Punto de Parada" (Hacer que el guardia trabaje más duro)

Los investigadores se dieron cuenta de que, para hacer que el guardia se congele, no basta con un patrón cualquiera que sea confuso; necesitas un patrón donde el guardia tenga que dar pasos diminutos e ineficientes.

La analogía: Imagina que el guardia camina por un pasillo. Si haces que se detenga en cada pulgada para revisar el suelo, se cansará rápido. Si solo se detiene cada 10 pies, se cansará más lento.
La solución: PUFFERDOS crea "llaves" (cadenas de ataque) que obligan al guardia a detenerse en cada pequeña pulgada. Lo hace eligiendo cuidadosamente caracteres específicos y organizándolos de modo que el guardia tenga que retroceder (volver atrás para comprobar de nuevo) tantas veces como sea posible. Esto hace que el ataque sea miles de veces más rápido que los métodos anteriores porque logra el mismo efecto de "congelación" con una llave mucho más corta.

2. Los tres patrones de "Trampa"

El equipo descubrió que la mayoría de las cerraduras rotas caen en tres formas específicas. PUFFEDORS tiene una receta especial para cada una:

La trampa de un solo bucle: Un único patrón que puede leerse de varias formas confusas. PUFFERDOS elige el carácter más corto y confuso para repetir.
La trampa de dos bucles: Dos patrones uno al lado del otro que pueden leer el mismo carácter. PUFFERDOS utiliza un carácter que ambos patrones pueden leer, forzándolos a discutir sobre quién se encarga de procesarlo.
La trampa de bucles múltiples: Una larga cadena de patrones. PUFFERDOS construye una llave que obliga al guardia a comprobar cada eslabón de la cadena individualmente.

3. El recorrido por el "Mundo Real" (Ejecución Concolica)

Esta es la parte más importante. Las herramientas antiguas simplemente probaban la cerradura en el vacío. PUFFERDOS simula el edificio completo.

La analogía: Imagina que tienes una llave que abre una puerta, pero la puerta está detrás de un control de seguridad, un recepcionista y un laberinto. Las herramientas antiguas solo te mostraban que la llave funciona en la puerta. PUFFERDOS te guía a través del laberinto, comprueba si el recepcionista te deja pasar y se asegura de que realmente llegues a la puerta.
El método: Utiliza una técnica llamada "ejecución concolica composicional". Piensa en esto como un resumen de mapa. En lugar de volver a recorrer cada paso del edificio cada vez, PUFFERDOS crea una "hoja de trucos" para cada habitación (función) del edificio. Pregunta: "¿Si le doy a esta habitación una llave confusa, la pasa a la siguiente habitación o la desecha?".
Al usar estas hojas de trucos, PUFFERDOS puede averiguar rápidamente si una llave corta y eficiente llegará realmente a la cerradura vulnerable en un programa real, o si será bloqueada por un filtro antes de que el proceso comience.

Los Resultados

El equipo probó PUFFERDOS en miles de programas del mundo real y en vulnerabilidades conocidas (CVE).

Velocidad: Generó cadenas de ataque que fueron entre 97 y 3.800 veces más eficientes que la mejor herramienta anterior. Podía congelar un sistema con una cadena diminuta en lugar de una enorme.
Tasa de éxito: Recreó con éxito el 96,8% de las vulnerabilidades conocidas (comparado con el 77,4% de la herramienta antigua).
Nuevos descubrimientos: Cuando probaron PUFFERDOS en 12 proyectos de software populares y reales, encontraron 59 nuevas vulneridades de seguridad, previamente desconocidas, que las herramientas antiguas pasaron por alto porque las herramientas antiguas no podían generar un ataque realista y lo suficientemente corto para demostrar que la vulnerabilidad existía.

En resumen: PUFFERDOS es una forma más inteligente y práctica de encontrar y demostrar que un sistema informático puede ser congelado por un patrón confuso. No solo encuentra la cerradura; encuentra la llave más corta y realista para trabarla, demostrando que el peligro es real y debe ser solucionado.

Resumen Técnico: PUFFERDOS

Planteamiento del Problema

Los ataques de Denegación de Servicio por Expresiones Regulares (ReDoS) explotan el comportamiento de ejecución de caso patológico en el peor de los casos de los motores de expresiones regulares con retroceso (backtracking), forzándolos a explorar un número superlineal o exponencial de rutas de coincidencia. Esto consume recursos excesivos de CPU, lo que provoca la degradación del servicio o la falta de disponibilidad. Aunque existen numerosas herramientas de detección para identificar expresiones regulares vulnerables y generar cadenas de prueba de concepto, los enfoques actuales sufren dos limitaciones críticas que dificultan la explotación práctica:

Longitudes de Entrada Poco Prácticas: Las herramientas existentes a menudo generan cadenas de ataque que son irrealmente largas (por ejemplo, requiriendo cientos de miles de caracteres) para provocar una ralentización significativa. En despliegues del mundo real, las restricciones de entrada (como los límites de encabezados HTTP) suelen truncar estas cadenas antes de que puedan alcanzar la expresión regular vulnerable, invalidando el ataque.
Falta de Validación a Nivel de Programa: Muchas cadenas generadas se validan únicamente contra la expresión regular de forma aislada. No tienen en cuenta las restricciones de flujo de datos, la lógica de filtrado o la truncación de la entrada dentro del programa anfitrión. En consecuencia, estas cadenas a menudo no pueden llegar a la expresión regular vulnerable en un contexto de ejecución real, lo que lleva a los desarrolladores a descartar las vulnerabilidades reportadas como de baja severidad o inexplotables.

Metodología

Los autores proponen PUFFERDOS, un marco híbrido diseñado para sintetizar cadenas de ataque que sean tanto eficientes (maximizando el costo de coincidencia dentro de presupuestos de longitud realistas) como efectivas (validadas para alcanzar la expresión regular vulnerable en el programa real). La metodología consta de tres componentes principales:

1. Análisis Formal y Taxonomía de Patrones

Los autores primero formalizan la relación entre la estructura de la cadena de ataque y el costo de coincidencia. A través de pruebas formales (Lemas 3.2–3.4 y Teorema 3.5), establecen que el costo de coincidencia aumenta cuando:

Las unidades de repetición son lo más cortas posible.
Las unidades de repetición se seleccionan de la intersección de los alfabetos de las Expresiones de Bucle (LE) adyacentes, permitiendo que múltiples LE consuman la misma subcadena.
Los puntos de parada (índices donde las LE terminan) están separados en lugar de entrelazados, obligando al motor a reprocesar segmentos de entrada más largos durante el retroceso.

Basándose en esto, definen tres patrones vulnerables para guiar la generación de cadenas:

Exponencial de Un Bucle (EOL): Una única LE con subexpresiones de despliegue que tienen alfabetos superpuestos.
Intersección de Bucle-Bucle (LIL): Dos LE adyacentes separadas por un segmento de no-bucle que puede ser coincidido por ambas LE.
Multi-Bucle Polinomial (PML): LE adyacentes con alfabetos disjuntos o separadores que no pueden ser consumidos por ambas.

2. Generación de Cadenas de Ataque Basada en la Estructura

PUFFERDOS analiza las expresiones regulares vulnerables en un Árbol de Sintaxis Abstracta (rAST) para identificar el patrón vulnerable específico (EOL, LIL o PML). Luego sintetiza cadenas de ataque candidatas ( $s_a = x \cdot y^q \cdot z$ ) utilizando reglas específicas de cada patrón:

Generación de Infix: Selecciona la unidad de repetición más corta ( $y$ ) del alfabeto de intersección de las LE relevantes. Para patrones con múltiples LE, concatena unidades de repetición independientes para asegurar que los puntos de parada estén separados, maximizando los pasos de retroceso.
Construcción de Prefijo/Sufijo: Deriva el prefijo ( $x$ ) de la parte no-bucle del prefijo de la expresión regular y el sufijo ( $z$ ) de la parte no-bucle del sufijo, asegurando que la cadena final sea rechazada por la expresión regular para activar un retroceso exhaustivo.

3. Refinamiento Concolic Composicional Específico para ReDoS

Para asegurar que la cadena generada alcance la expresión regular vulnerable en un programa real, PUFFERDOS emplea una estrategia de ejecución concolic composicional:

Extracción de Rutas: Construye un grafo de llamadas para identificar rutas factibles desde los puntos de entrada del programa hasta la expresión regular vulnerable.
Resumen de Funciones: Realiza pruebas unitarias concolic en las funciones a lo largo de la ruta para generar resúmenes de funciones específicos para ReDoS. A diferencia de los resúmenes tradicionales, estos se podan para retener solo los comportos relevantes para la propagación de la cadena de ataque (por ejemplo, transformaciones de identidad o retornos constantes), descartando el razonamiento de expresiones regulares no relacionado que causa la explosión de rutas.
Refinamiento a Nivel de Sistema: Utiliza los resúmenes para guiar la ejecución concolic a nivel de sistema, resolviendo las restricciones interprocedimentales para refinar la cadena de ataque de modo que supere los filtros y alcance la expresión regular objetivo sin exceder los presupuestos de longitud de entrada realistas.

Contribuciones Clave

Prueba Formal de Eficiencia: El artículo demuestra formalmente que la selección de caracteres específicos y su ordenamiento para separar los puntos de parada en LE adyacentes amplifica significativamente el costo de coincidencia de la expresión regular. Esto conduce a la derivación de tres patrones de expresiones regulares vulnerables y reglas de generación demostrablemente eficientes.
Marco PUFFERDOS: El desarrollo de un generador híbrido que integra reglas de generación formal con refinamiento concolic composicional específico para ReDoS. Este enfoque cierra la brecha entre la detección teórica y la explotación práctica al asegurar que las cadenas sean lo suficientemente cortas para las restricciones del mundo real y válidas dentro del flujo de datos del programa.
Evaluación Exhaustiva: La herramienta es evaluada en un corpus a gran escala de 17,962 expresiones regulares vulnerables, 31 CVE conocidos y 12 proyectos de código abierto populares.

Resultados

La evaluación demuestra mejoras significativas sobre la herramienta de vanguardia, RENGAR:

Eficiencia: PUFFERDOS genera cadenas de ataque que son de 97.2× a 3,872.4× más cortas que las producidas por RENGAR, logrando los mismos umbrales de tiempo de coincidencia (0.1s, 1s y 10s).
Reproducción de CVE: PUFFERDOS reprodujo con éxito el 96.8% de los CVE de ReDoS explotados, en comparación con el 77.4% de RENGAR.
Nuevas Vulnerabilidades: Aplicado a 12 proyectos de código abierto populares, PUFFERDOS descubrió 59 instancias de ReDoS explotables (25 más que RENGAR). Desarrolladores de seis de estos proyectos validaron 21 de los hallazgos.
Impacto en el Mundo Real: En un ejemplo motivador que involucra una biblioteca de resaltado de sintaxis, PUFFERDOS generó una cadena de 1,000 caracteres que causó una suspensión del sistema superior a los 4,000 segundos, mientras que los métodos tradicionales requirieron 500,000 caracteres y no lograron provocar una suspensión debido a la truncación de la entrada en el programa real.

Significado

El artículo argumenta que la utilidad práctica de la detección de ReDoS está actualmente limitada porque las cadenas de ataque generadas suelen ser demasiado largas o no logran propagarse a través de la lógica del programa. Al abordar estas deficiencias específicas, PUFFERDOS proporciona un mecanismo para generar evidencia prácticamente explotable de las vulnerabilidades. Esto es significativo porque aborda directamente la razón por la cual los desarrolladores suelen ignorar los informes de ReDoS (percibiéndolos como de baja severidad o inexplotables). Al proporcionar cadenas de ataque cortas y válidas, PUFFERDOS permite una evaluación de riesgos más precisa y facilita la remediación de las vulnerabilidades de ReDoS en sistemas de software del mundo real.