¿Cómo evitar el retroceso catastrófico en Regex?

El retroceso catastrófico de expresiones regulares se refiere al hecho de que la expresión regular retrocede demasiado al coincidir, causando un uso del 100% de la CPU y bloqueando los servicios normales.

Antecedentes

He leído un artículo que detalla el proceso de descubrimiento y resolución de un retroceso regular que lleva al 100% de la CPU. El artículo original es bastante largo, y he encontrado problemas similares dos veces antes en el desarrollo de OpenResty.

Aquí hay un breve resumen para que no tengas que perder tiempo en los antecedentes.

1. Los motores de expresiones regulares para la mayoría de los lenguajes de desarrollo están implementados utilizando NFA basado en retroceso (en lugar de basado en el NFA de Thompson).
2. Retroceso catastrófico con 100% de CPU si hay demasiados retrocesos.
3. Es necesario analizar el volcado con gdb o systemtap para localizar el entorno en línea.
4. Tales problemas son difíciles de detectar antes de que el código esté en producción y requieren una revisión caso por caso de las expresiones regulares.

Desde un punto de vista de desarrollo, arreglar las expresiones regulares problemáticas es el final de la historia. Como máximo, agregar un mecanismo de seguridad para limitar el número de retrocesos, como este en OpenResty.

lua_regex_match_limit 100000;

De esta manera, incluso si hay un retroceso catastrófico, estará limitado y no consumirá toda la CPU.

Bueno, ¿parece perfecto ya? Vayamos más allá del nivel de desarrollo y miremos esto desde una dimensión diferente.

Atacantes

Solo usa una máquina, envía una solicitud, y puedes golpear al otro lado del servidor, esto es simplemente el sueño de un arma nuclear para un hacker. Comparado con esto, ¿qué es un DDoS? Es débil, el movimiento es grande y costoso.

Este ataque también tiene su propio nombre: ReDoS (RegEx Denial of Service).

Dado que las expresiones regulares son tan ampliamente utilizadas y existen en casi todas las partes del servicio back-end, hay una oportunidad para aprovecharla al encontrar una de las vulnerabilidades.

Imagina un escenario en el que un hacker descubre una vulnerabilidad ReDoS en el WAF y envía una solicitud para derribar el WAF; no puedes localizar el problema en un corto período de tiempo, ni siquiera dándote cuenta de que es un ataque; eliges reiniciar o apagar temporalmente el WAF para mantener tu negocio en marcha; mientras el WAF está fuera de servicio, el hacker usa inyección SQL para llevarse tu base de datos. Tú, por otro lado, puedes seguir completamente a oscuras.

Debido al uso generalizado de software de código abierto y servicios en la nube, no es suficiente solo asegurarse de que las expresiones regulares que escribes estén libres de vulnerabilidades. Ese es otro tema, comenzaremos aquí solo discutiendo las expresiones regulares que están bajo nuestro control.

¿Cómo descubrir tales expresiones regulares?

El primer paso para resolver problemas es encontrarlos, y tratar de encontrarlos todos, también conocido como la capacidad de encontrarlos de manera segura.

Esperar que una revisión manual del código encuentre reglas problemáticas no es confiable. La mayoría de los desarrolladores no tienen conciencia de seguridad, e incluso si la tuvieran, es poco probable que puedan encontrar el problema en una expresión regular compleja.

Aquí es donde las herramientas de automatización son útiles.

Tenemos los siguientes dos métodos automatizados para resolver esto.

• Pruebas estáticas

Tales herramientas pueden escanear el código en busca de expresiones regulares y, según un cierto algoritmo, encontrar las expresiones regulares con retroceso catastrófico.

Por ejemplo, RXXR2, que está implementado basado en un algoritmo en un artículo que convierte expresiones regulares a ε-NFA y luego las busca, pero no soporta la sintaxis extendida de expresiones regulares, por lo que habrá informes omitidos.

• Fuzzing dinámico

La prueba de fuzzing es un método general de prueba de software que detecta caídas de software, fugas de memoria y otros problemas al ingresar grandes cantidades de datos aleatorios durante largos períodos de tiempo.

De manera similar, podemos usar este enfoque en pruebas de expresiones regulares. Podemos generar datos de prueba basados en expresiones regulares existentes, o podemos generarlos completamente al azar.

SlowFuzz es una de las herramientas de código abierto, también basada en la implementación de un algoritmo de un artículo, el artículo se enumerará al final de este documento, es una herramienta de propósito general, y no hace procesamiento para la estructura de la expresión regular, por lo que habrá informes omitidos.

SDLFuzzer es una herramienta especializada en detección de ReDoS desarrollada por Microsoft hace unos años, pero ya no se mantiene.

No hay muchas herramientas para elegir en esta área, y no hay mucha atención. Sin embargo, me emocioné al encontrar un artículo sobre ReDoS de varios profesores y doctorandos de la Universidad de Nanjing durante mi búsqueda de información, y abrieron la herramienta ReScue junto con el artículo: https://2bdenny.github.io/ReScue/. Esta herramienta ha identificado vulnerabilidades ReDoS en varios proyectos de código abierto.

Aquí están los resultados de las pruebas de comparación en el artículo.

¿Se puede hacer de una vez por todas?

Incluso si usamos tales herramientas, inevitablemente habrá falsas alarmas y alarmas omitidas, entonces, ¿hay una manera de resolver ReDoS de una vez por todas?

Entonces tenemos que volver a la raíz del problema para encontrar la respuesta: el motor de expresiones regulares usa retroceso para coincidir.

¿No estaría bien si abandonáramos este enfoque? Sí, ya hay bastantes otras implementaciones de motores de expresiones regulares que pueden resolverlo de una vez por todas. Todas abandonan el retroceso y usan el enfoque de autómata NFA/DFA para implementar, la ventaja es que es adecuado para la coincidencia de flujo y también es más seguro, la desventaja es que no soporta muchas sintaxis extendidas de expresiones regulares, como referencias inversas, bueno, estas generalmente tampoco se usan.

• Google RE2

RE2 de Google es uno de los proyectos de código abierto más completos. Soporta la mayoría de la sintaxis de PCRE, y hay implementaciones de bibliotecas para Go, Python, Perl, Node.js y otros lenguajes de desarrollo, el costo de inicio y reemplazo es muy bajo.

Tomemos Perl como ejemplo y veamos si RE2 puede evitar problemas de retroceso catastrófico.

Echemos un vistazo a esta tabla comparativa de resultados.

El código es el siguiente, puedes probarlo tú mismo si estás interesado.

time perl -e 'if ("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" =~ /a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa/) {print("hit");}'

40.80s user 0.00s system 99% cpu 40.800 total

Toma 40.8 segundos ejecutar esta expresión regular, durante los cuales la CPU está al 99%.

Con RE2, el contraste es muy claro.

time perl -e 'use re::engine::RE2; if ("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" =~ /a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa/) {print(" hit");}'

perl -e 0.00s user 0.00s system 34% cpu 0.011 total

• Intel Hyperscan

Intel Hyperscan también es un motor de expresiones regulares similar a RE2, y hay bibliotecas para Perl, Python y otros lenguajes, por lo que no es demasiado difícil comenzar.

Solo que, de acuerdo con la práctica de Intel, está más vinculado a la plataforma, solo puede ejecutarse en x86.

Si hay un beneficio único, puede ser la capacidad de funcionar mejor con el conjunto de instrucciones y hardware de Intel, con mejoras de rendimiento, como combinarlo con su propio DPDK.

Snort, una herramienta de detección de intrusiones de red de código abierto, también usa Hyperscan para reemplazar el motor de expresiones regulares anterior, por lo que los estudiantes familiarizados con Snort pueden probarlo.

Extensiones

Aquí hay algunos artículos sobre expresiones regulares, que pueden leerse como una extensión si estás interesado.

1. SlowFuzz: Automated Domain-Independent Detection of Algorithmic Complexity Vulnerabilities: https://arxiv.org/pdf/1708.08437.pdf

2. Static Analysis for Regular Expression Exponential Runtime via Substructural Logics: https://arxiv.org/abs/1405.7058.pdf

3. ReScue: Crafting Regular Expression DoS Attacks: https://dl.acm.org/doi/10.1145/3238147.3238159

4. Regular Expression Matching Can Be Simple And Fast: https://swtch.com/~rsc/regexp/regexp1.html