Hace casi 9 años, Cloudflare era una empresa pequeña y yo no trabajaba para ella, solo era un cliente. Un mes después de lanzar Cloudflare, recibí una notificación de que mi sitio web El DNS no parece funcionar. Cloudflare ha realizado un cambio en , y había un DNS roto.
Inmediatamente le escribí a Matthew Prince con el título “¿Dónde está mi DNS?” y me envió una larga respuesta llena de detalles técnicos (), a lo que respondí:
De: John Graham-Cumming
Fecha: 7 de octubre de 2010, 9:14
Asunto: Re: ¿Dónde está mi DNS?
Para: Mateo PríncipeBuen informe, gracias. Definitivamente llamaré si hay problemas. Probablemente valga la pena escribir una publicación sobre esto una vez que haya recopilado toda la información técnica. Creo que la gente disfrutará de una historia abierta y honesta. Especialmente si le adjunta gráficos para mostrar cómo ha crecido el tráfico desde el lanzamiento.
Tengo un buen seguimiento de mi sitio y recibo un SMS sobre cada falla. El monitoreo muestra que la falla ocurrió entre las 13:03:07 y las 14:04:12. Las pruebas se realizan cada cinco minutos.
Estoy seguro de que lo resolverás. ¿Estás seguro de que no necesitas tu propia persona en Europa? 🙂
Y él respondió:
De: Mateo Príncipe
Fecha: 7 de octubre de 2010, 9:57
Asunto: Re: ¿Dónde está mi DNS?
Para: John Graham-CummingGracias. Respondimos a todos los que escribieron. Ahora estoy de camino a la oficina y escribiremos algo en el blog o colocaremos una publicación oficial en nuestro tablón de anuncios. Estoy completamente de acuerdo, la honestidad lo es todo.
Ahora Cloudflare es una empresa realmente grande, trabajo para ella y ahora tengo que escribir abiertamente sobre nuestro error, sus consecuencias y nuestras acciones.
Eventos del 2 de julio
El 2 de julio implementamos una nueva regla en Reglas administradas para WAF debido a la cual en cada núcleo de procesador que procesa tráfico HTTP/HTTPS en la red Cloudflare en todo el mundo. Mejoramos constantemente las reglas administradas para WAF en respuesta a nuevas vulnerabilidades y amenazas. En mayo, por ejemplo, nos apresuramos para protegerse contra una vulnerabilidad grave en SharePoint. El objetivo de nuestro WAF es la capacidad de implementar reglas de forma rápida y global.
Desafortunadamente, la actualización del jueves pasado contenía una expresión regular que desperdiciaba demasiados recursos de CPU HTTP/HTTPS al retroceder. Como resultado, nuestras funciones principales de proxy, CDN y WAF sufrieron. El gráfico muestra que los recursos del procesador para atender el tráfico HTTP/HTTPS alcanzan casi el 100% en los servidores de nuestra red.
Uso de CPU en un punto de presencia durante un incidente
Como resultado, nuestros clientes (y los clientes de nuestros clientes) terminaron con una página de error 502 en los dominios de Cloudflare. Los servidores web front-end de Cloudflare generaron errores 502 que todavía tenían núcleos libres pero no podían comunicarse con los procesos que manejaban el tráfico HTTP/HTTPS.
Sabemos cuántos inconvenientes ha causado esto a nuestros clientes. Estamos terriblemente avergonzados. Y este fracaso nos impidió abordar eficazmente el incidente.
Si usted fuera uno de estos clientes, probablemente estaría asustado, enojado y molesto. Es más, no hemos tenido una . El alto consumo de CPU se debió a una regla WAF con una expresión regular mal redactada que resultó en un retroceso excesivo. Aquí está la expresión culpable: (?:(?:"|'|]|}||d|(?:nan|infinity|true|false|null|undefined|symbol|math)|`|-|+)+[)]*;?((?:s|-|~|!|{}||||+)*.*(?:.*=.*)))
Si bien esto es interesante en sí mismo (y hablaré de ello con más detalle a continuación), el servicio Cloudflare estuvo inactivo durante 27 minutos no solo debido a una mala expresión regular. Nos tomó un tiempo describir la secuencia de eventos que llevaron al fracaso, por lo que tardamos en responder. Al final de la publicación, describiré el retroceso en una expresión regular y te diré qué hacer con él.
Que paso
Empecemos en orden. Todos los horarios aquí están en UTC.
A las 13:42, un ingeniero del equipo de firewall realizó un pequeño cambio en las reglas de detección. mediante un proceso automático. En consecuencia, se creó un ticket de solicitud de cambio. Gestionamos dichos tickets a través de Jira (captura de pantalla a continuación).
Después de 3 minutos, apareció la primera página de PagerDuty, informando un problema con WAF. Esta fue una prueba sintética que prueba la funcionalidad de los WAF (tenemos cientos de ellos) fuera de Cloudflare para monitorear el funcionamiento normal. A esto le siguieron inmediatamente páginas de alertas sobre otras pruebas de servicio de extremo a extremo de Cloudflare que fallaron, problemas de tráfico global, errores 502 generalizados y un montón de informes de nuestros puntos de presencia (PoP) en ciudades de todo el mundo que indicaban una falta. de los recursos de la CPU.
Recibí varias de estas alertas, salí furioso de una reunión y me dirigía a la mesa cuando el jefe de nuestro departamento de desarrollo de soluciones dijo que habíamos perdido el 80% de nuestro tráfico. Corrí hacia nuestros ingenieros de SRE, que ya estaban trabajando en el problema. Al principio pensamos que se trataba de algún tipo de ataque desconocido.
Los ingenieros de Cloudflare SRE están dispersos por todo el mundo y monitorean la situación las 0 horas del día. Normalmente, estas alertas le notifican sobre problemas locales específicos de alcance limitado, se rastrean en paneles internos y se resuelven varias veces al día. Pero estas páginas y notificaciones indicaban algo realmente grave, y los ingenieros de SRE inmediatamente declararon el nivel de gravedad PXNUMX y se comunicaron con la administración y los ingenieros de sistemas.
Nuestros ingenieros de Londres estaban en ese momento escuchando una conferencia en la sala principal. La conferencia tuvo que ser interrumpida, todos se reunieron en una gran sala de conferencias y se llamó a más especialistas. Este no era un problema típico que las SRE pudieran resolver por sí mismas. Era urgente involucrar a los especialistas adecuados.
A las 14:00 determinamos que el problema era con el WAF y no hubo ningún ataque. El equipo de rendimiento extrajo los datos de la CPU y quedó claro que el WAF era el culpable. Otro empleado confirmó esta teoría utilizando strace. Alguien más vio en los registros que había un problema con WAF. A las 14:02 p. m., todo el equipo acudió a mí cuando me propusieron utilizar la eliminación global, un mecanismo integrado en Cloudflare que apaga un componente en todo el mundo.
Cómo logramos el asesinato global para WAF es una historia diferente. No es tan simple. Utilizamos nuestros propios productos, y desde nuestro servicio no funcionó, no pudimos autenticarnos e iniciar sesión en el panel de control interno (cuando todo se arregló, supimos que algunos miembros del equipo habían perdido el acceso debido a una característica de seguridad que desactiva las credenciales si el panel de control interno no se usa por un largo tiempo).
Y no pudimos acceder a nuestros servicios internos, como Jira o el sistema de compilación. Necesitábamos un mecanismo de solución, que utilizamos con poca frecuencia (esto también será necesario resolverlo). Finalmente, un ingeniero logró desactivar el WAF a las 14:07 y a las 14:09, el tráfico y los niveles de CPU volvieron a la normalidad en todas partes. El resto de los mecanismos de protección de Cloudflare funcionaron con normalidad.
Luego nos dispusimos a restaurar el WAF. La situación era fuera de lo común, por lo que realizamos pruebas negativas (preguntándonos si el cambio era realmente el problema) y pruebas positivas (asegurándonos de que la reversión funcionaba) en una ciudad usando tráfico separado, transfiriendo clientes que pagaban desde allí.
A las 14:52 estábamos convencidos de que entendíamos el motivo, hicimos una corrección y habilitamos WAF nuevamente.
Cómo funciona Cloudflare
Cloudflare cuenta con un equipo de ingenieros dedicados a gestionar reglas para WAF. Se esfuerzan por mejorar las tasas de detección, reducir los falsos positivos y responder rápidamente a las nuevas amenazas a medida que surgen. En los últimos 60 días, se han procesado 476 solicitudes de cambio de reglas administradas para WAF (un promedio de una cada 3 horas).
Este cambio en particular debía implementarse en modo de simulación, donde el tráfico real del cliente pasa por la regla, pero no se bloquea nada. Usamos este modo para probar la efectividad de las reglas y medir las tasas de falsos positivos y falsos negativos. Pero incluso en el modo de simulación, las reglas realmente deben ejecutarse y, en este caso, la regla contenía una expresión regular que consumía demasiados recursos del procesador.
Como puede ver en la solicitud de cambio anterior, tenemos un plan de implementación, un plan de reversión y un enlace a un procedimiento operativo estándar (SOP) interno para este tipo de implementación. El POE para cambiar una regla permite que se publique globalmente. En realidad, en Cloudflare, las cosas se hacen de manera completamente diferente y el SOP dicta que primero enviamos el software para pruebas y uso interno a un punto de presencia interno (PoP) (que usan nuestros empleados), luego a una pequeña cantidad de clientes en un lugar aislado, luego a un gran número de clientes, y sólo entonces a todo el mundo.
Esto es lo que parece. Usamos git internamente a través de BitBucket. Los ingenieros que trabajan en los cambios envían el código, que se crea para TeamCity, y cuando se aprueba la compilación, se asignan revisores. Una vez que se aprueba una solicitud de extracción, se ensambla el código y se ejecutan (nuevamente) una serie de pruebas.
Si la compilación y las pruebas se completan correctamente, se crea una solicitud de cambio en Jira y el administrador o líder correspondiente debe aprobar el cambio. Después de la aprobación, el despliegue se produce en la denominada “casa de fieras PoP”: DOG, PIG y (perro, cerdo y canario).
DOG PoP es un PoP de Cloudflare (como cualquier otra de nuestras ciudades) que utilizan únicamente los empleados de Cloudflare. PoP para uso interno le permite detectar problemas antes de que el tráfico de clientes comience a fluir hacia la solución. Cosa útil.
Si la prueba DOG tiene éxito, el código pasa a la etapa PIG (conejillo de indias). Este es Cloudflare PoP, donde una pequeña cantidad de tráfico gratuito de clientes fluye a través de un código nuevo.
Si todo está bien, el código pasa a Canary. Disponemos de tres PoP de Canarias en diferentes partes del mundo. En ellos, el tráfico de clientes gratuitos y de pago pasa por el nuevo código, y esta es la última comprobación de errores.
Proceso de lanzamiento de software en Cloudflare
Si el código está bien en Canary, lo publicamos. Pasar por todas las etapas (PERRO, CERDO, Canarias, el mundo entero) lleva varias horas o días, dependiendo del cambio de código. Debido a la diversidad de la red y los clientes de Cloudflare, probamos exhaustivamente el código antes de lanzarlo globalmente a todos los clientes. Pero WAF no sigue específicamente este proceso porque es necesario responder rápidamente a las amenazas.
Amenazas WAF
En los últimos años, ha habido un aumento significativo de amenazas en aplicaciones comunes. Esto se debe a la mayor disponibilidad de herramientas de prueba de software. Por ejemplo, recientemente escribimos sobre ).
Fuente:
Muy a menudo, se crea una prueba de concepto y se publica inmediatamente en Github para que los equipos que mantienen la aplicación puedan probarla rápidamente y asegurarse de que esté adecuadamente protegida. Por lo tanto, Cloudflare necesita la capacidad de responder a nuevos ataques lo más rápido posible para que los clientes tengan la oportunidad de reparar su software.
Un gran ejemplo de la rápida respuesta de Cloudflare es la implementación de protecciones contra vulnerabilidades de SharePoint en mayo (). Casi inmediatamente después de que se hicieran los anuncios, notamos una gran cantidad de intentos de explotar la vulnerabilidad en las instalaciones de SharePoint de nuestros clientes. Nuestros muchachos monitorean constantemente nuevas amenazas y redactan reglas para proteger a nuestros clientes.
Se suponía que la regla que causó el problema el jueves protegería contra secuencias de comandos entre sitios (XSS). Estos ataques también se han vuelto mucho más frecuentes en los últimos años.
Fuente:
El procedimiento estándar para cambiar una regla administrada para un WAF es realizar pruebas de integración continua (CI) antes de la implementación global. El jueves pasado hicimos esto y implementamos las reglas. A la 13:31 p.m., un ingeniero envió una solicitud de extracción aprobada con un cambio.
A las 13:37 TeamCity recopiló las reglas, realizó pruebas y dio el visto bueno. El conjunto de pruebas WAF prueba la funcionalidad principal del WAF y consta de una gran cantidad de pruebas unitarias para funciones individuales. Después de las pruebas unitarias, probamos las reglas para WAF utilizando una gran cantidad de solicitudes HTTP. Las solicitudes HTTP verifican qué solicitudes deben ser bloqueadas por el WAF (para interceptar el ataque) y cuáles pueden permitirse (para no bloquear todo y evitar falsos positivos). Pero no probamos el uso excesivo de la CPU y el examen de los registros de compilaciones WAF anteriores muestra que el tiempo de ejecución de la prueba de reglas no aumentó y era difícil sospechar que no habría suficientes recursos.
Las pruebas pasaron y TeamCity comenzó a implementar automáticamente el cambio a la 13:42 p.m.
Quicksilver
Las reglas WAF se centran en la solución inmediata de amenazas, por lo que las implementamos utilizando el almacén distribuido de valores clave de Quicksilver, que propaga los cambios globalmente en segundos. Todos nuestros clientes utilizan esta tecnología cuando cambian la configuración en el tablero o vía API, y es gracias a ella que respondemos a los cambios a la velocidad del rayo.
No hemos hablado mucho sobre Quicksilver. Anteriormente usábamos como una tienda de valor clave distribuida globalmente, pero hubo problemas operativos y escribimos nuestra propia tienda, replicada en más de 180 ciudades. Ahora usamos Quicksilver para enviar cambios de configuración a los clientes, actualizar las reglas WAF y distribuir código JavaScript escrito por los clientes a los trabajadores de Cloudflare.
Solo se necesitan unos segundos desde hacer clic en un botón en un panel o llamar a una API hasta realizar un cambio de configuración en todo el mundo. A los clientes les encantó esta velocidad de configuración. Y Workers les ofrece una implementación global de software casi instantánea. En promedio, Quicksilver propaga alrededor de 350 cambios por segundo.
Y Quicksilver es muy rápido. En promedio, alcanzamos el percentil 99 de 2,29 segundos para propagar cambios a todas las computadoras del mundo. La velocidad suele ser algo bueno. Después de todo, cuando habilitas una función o borras el caché, sucede casi instantáneamente y en todas partes. El envío de código a través de Cloudflare Workers se produce a la misma velocidad. Cloudflare promete a sus clientes actualizaciones rápidas en el momento adecuado.
Pero en este caso, la velocidad nos jugó una broma cruel y las reglas cambiaron en todas partes en cuestión de segundos. Quizás hayas notado que el código WAF usa Lua. Cloudflare utiliza Lua ampliamente en producción y detalles nosotros . Usos de Lua WAF internamente y aplica retroceso para hacer coincidir. No tiene mecanismos de protección contra expresiones que se salen de control. A continuación hablaré más sobre esto y lo que estamos haciendo al respecto.
Antes de implementar las reglas, todo transcurrió sin problemas: se creó y aprobó la solicitud de extracción, la canalización de CI/CD recopiló y probó el código, la solicitud de cambio se envió de acuerdo con el SOP que rige la implementación y la reversión, y se completó la implementación.
Proceso de implementación de Cloudflare WAF
Qué salió mal
Como dije, implementamos docenas de nuevas reglas WAF cada semana y contamos con muchos sistemas para protegernos contra las consecuencias negativas de dicho despliegue. Y cuando algo sale mal, suele ser una combinación de varias circunstancias a la vez. Si encuentra una sola razón, esto, por supuesto, le tranquilizará, pero no siempre es cierto. Estas son las razones que en conjunto llevaron al fallo de nuestro servicio HTTP/HTTPS.
- Un ingeniero escribió una expresión regular que podría resultar en un exceso .
- Una característica que podría haber evitado que la expresión regular desperdiciara demasiada CPU se eliminó por error en una refactorización del WAF varias semanas antes; la refactorización era necesaria para que el WAF consumiera menos recursos.
- El motor de expresiones regulares no tenía garantías de complejidad.
- El conjunto de pruebas no pudo detectar un consumo excesivo de CPU.
- El SOP permite implementar cambios de reglas no urgentes a nivel mundial sin un proceso de varios pasos.
- El plan de reversión requirió ejecutar una compilación WAF completa dos veces, lo que llevó mucho tiempo.
- La primera alerta sobre problemas de tráfico a nivel mundial se disparó demasiado tarde.
- Nos tomó un tiempo actualizar la página de estado.
- Tuvimos problemas para acceder a los sistemas debido a un problema técnico y el procedimiento de derivación no estaba bien establecido.
- Los ingenieros de la SRE perdieron el acceso a algunos sistemas porque sus credenciales expiraron por razones de seguridad.
- Nuestros clientes no tenían acceso al panel o API de Cloudflare porque pasan por una región de Cloudflare.
Lo que ha cambiado desde el pasado jueves
Primero, detuvimos por completo todo trabajo en las versiones de WAF y estamos haciendo lo siguiente:
- Estamos reintroduciendo la protección contra uso excesivo de la CPU que eliminamos. (Listo)
- Verificar manualmente las 3868 reglas en las reglas administradas para que el WAF encuentre y corrija otros casos potenciales de retroceso excesivo. (Verificación completada)
- Incluimos perfiles de rendimiento para todas las reglas en el conjunto de prueba. (Previsto: 19 de julio)
- Cambiar a un motor de expresiones regulares o - Ambos ofrecen garantías de tiempo de ejecución. (Previsto: 31 de julio)
- Estamos reescribiendo el SOP para implementar reglas en etapas, como otro software en Cloudflare, pero al mismo tiempo tenemos la capacidad de realizar una implementación global de emergencia si los ataques ya han comenzado.
- Estamos desarrollando la capacidad de eliminar urgentemente el panel y la API de Cloudflare de la región de Cloudflare.
- Automatizar actualizaciones de páginas .
A largo plazo nos estamos alejando del Lua WAF que escribí hace unos años. Mover WAF a . De esta forma el WAF será más rápido y recibirá un nivel adicional de protección.
Conclusión
Este fallo nos causó problemas a nosotros y a nuestros clientes. Actuamos rápidamente para corregir la situación y ahora estamos trabajando en las fallas en los procesos que causaron el bloqueo, además de profundizar aún más para protegernos contra posibles problemas con expresiones regulares en el futuro al migrar a nueva tecnología.
Estamos muy avergonzados por esta interrupción y pedimos disculpas a nuestros clientes. Esperamos que estos cambios garanticen que algo como esto no vuelva a suceder.
Solicitud. Retroceder expresiones regulares
Para entender cómo funciona la expresión:
(?:(?:"|'|]|}||d
(?:nan|infinity|true|false|null|undefined|symbol|math)|`|-
|+)+[)]*;?((?:s|-|~|!|{}||||+)*.*(?:.*=.*)))consumió todos los recursos de la CPU, necesita saber un poco sobre cómo funciona el motor de expresión regular estándar. El problema aquí es el patrón. .*(?:.*=.*). (?: y correspondiente ) es un grupo que no captura (es decir, la expresión entre paréntesis está agrupada como una expresión única).
En el contexto del consumo excesivo de CPU, este patrón se puede describir como .*.*=.*. De esta forma, el patrón parece innecesariamente complejo. Pero lo que es más importante, en el mundo real, las expresiones (como las expresiones complejas en las reglas WAF) que le piden al motor que haga coincidir un fragmento seguido de otro fragmento pueden provocar un retroceso catastrófico. Y es por eso.
En expresión regular . significa que necesitas hacer coincidir un carácter, .* - hacer coincidir cero o más caracteres "con avidez", es decir, capturar un máximo de caracteres, de modo que .*.*=.* significa hacer coincidir cero o más caracteres, luego hacer coincidir cero o más caracteres, encontrar el carácter literal =, hacer coincidir cero o más caracteres.
Tomemos la línea de prueba. x=x. Corresponde a la expresión .*.*=.*. .*.* antes de que el signo igual coincida con el primero x (uno de los grupos .* partido xy el segundo, cero caracteres). .* después = últimos partidos x.
Esta comparación requiere 23 pasos. Primer grupo .* в .*.*=.* actúa con avidez y coincide con toda la cadena x=x. El motor pasa al siguiente grupo. .*. No tenemos más personajes con los que coincidir, así que el segundo grupo .* coincide con cero caracteres (esto está permitido). Luego el motor se mueve hacia la señal. =. No hay más símbolos (primer grupo .* usé toda la expresión x=x), no se produce ninguna comparación.
Y luego el motor de expresiones regulares vuelve al principio. Pasa al primer grupo. .* y lo compara с x= (en lugar de x=x), y luego se enfrenta al segundo grupo .*. Segundo grupo .* se compara con el segundo x, y nuevamente no nos quedan caracteres. Y cuando el motor vuelve a alcanzar = в .*.*=.*, nada funciona. Y vuelve a dar marcha atrás.
Esta vez el grupo .* todavía coincide x=, pero el segundo grupo .* no más xy cero caracteres. El motor está intentando encontrar un carácter literal. = en el patrón .*.*=.*, pero no sale (después de todo, el primer grupo ya lo ocupó .*). Y vuelve a dar marcha atrás.
Esta vez el primer grupo .* toma solo la primera x. Pero el segundo grupo .* capturas "con avidez" =x. ¿Ya has adivinado qué pasará? El motor intenta igualar el literal. =, falla y hace otro retroceso.
El primer grupo de .* todavía coincide con el primero x... El segundo .* solo toma =. Por supuesto, el motor no puede coincidir con el literal. =, porque el segundo grupo ya lo ha hecho .*. Y nuevamente retrocediendo. ¡Y estamos intentando hacer coincidir una cadena de tres caracteres!
Como resultado, el primer grupo .* coincide solo con el primero xsegundo .* - con cero caracteres, y el motor finalmente coincide con el literal = en expresión с = en línea. El siguiente es el último grupo. .* se compara con el ultimo x.
23 pasos solo para x=x. Vea un vídeo breve sobre el uso de Perl , que muestra cómo se producen los pasos y el retroceso.
Esto ya supone mucho trabajo, pero ¿y si en lugar de eso? x=x tendremos x=xx? Son 33 pasos. Y si x=xxx? 45. La relación no es lineal. El gráfico muestra una comparación de x=x a x=xxxxxxxxxxxxxxxxxxxx (20 x después =). Si tenemos 20 x después =¡El motor completa la combinación en 555 pasos! (Además, si hemos perdido x= y la cadena simplemente consta de 20 x, el motor dará 4067 pasos para entender que no hay coincidencias).
Este vídeo muestra todos los retrocesos para comparar. x=xxxxxxxxxxxxxxxxxxxx:
El problema es que a medida que aumenta el tamaño de la cadena, el tiempo de coincidencia crece de forma superlineal. Pero las cosas pueden empeorar aún más si se modifica ligeramente la expresión regular. digamos que tuvimos .*.*=.*; (es decir, había un punto y coma literal al final del patrón). Por ejemplo, para hacer coincidir una expresión como foo=bar;.
Y aquí dar marcha atrás sería un verdadero desastre. Para comparacion x=x Se necesitarán 90 pasos, no 23. Y ese número está creciendo rápidamente. Comparar x= y 20 x, se necesitan 5353 pasos. Aquí está el gráfico. Mira los valores del eje. Y en comparación con el gráfico anterior.
Si está interesado, consulte los 5353 pasos coincidentes fallidos x=xxxxxxxxxxxxxxxxxxxx и .*.*=.*;
Al utilizar coincidencias perezosas en lugar de codiciosas, se puede controlar el grado de retroceso. Si cambiamos la expresión original a .*?.*?=.*?, para comparacion x=x Se necesitarán 11 pasos (no 23). Como para x=xxxxxxxxxxxxxxxxxxxx. Todo porque ? después .* le dice al motor que coincida con un número mínimo de caracteres antes de continuar.
Pero los mapeos diferidos no resuelven completamente el problema del retroceso. Si reemplazamos el ejemplo catastrófico .*.*=.*; en .*?.*?=.*?;, el tiempo de ejecución seguirá siendo el mismo. x=x todavía requiere 555 pasos, y x= y 20 x - 5353.
Lo único que se puede hacer (además de reescribir completamente el patrón para una mayor especificidad) es abandonar el motor de expresiones regulares con su mecanismo de retroceso. Esto es lo que haremos durante las próximas semanas.
La solución a este problema se conoce desde 1968, cuando Kent Thompson escribió un artículo (“Métodos de programación: algoritmo de búsqueda de expresiones regulares”). El artículo describe un mecanismo que le permite convertir una expresión regular en máquinas de estados finitos no deterministas y, después de cambios de estado en máquinas de estados finitos no deterministas, utilizar un algoritmo cuyo tiempo de ejecución depende linealmente de la cadena coincidente.
Métodos de programación
Algoritmo de búsqueda de expresiones regulares
Ken Thompson
Bell Telephone Laboratories, Inc., Murray Hill, Nueva JerseyDescribe un método para buscar una cadena específica de caracteres en el texto y analiza la implementación de este método en forma de compilador. El compilador toma la expresión regular como código fuente y produce el programa IBM 7094 como código objeto. El programa objeto recibe información en forma de texto de búsqueda y emite una señal cada vez que una cadena de texto se compara con una expresión regular determinada. El artículo proporciona ejemplos, problemas y soluciones.
Algoritmo
Los algoritmos de búsqueda anteriores daban como resultado un retroceso si una búsqueda parcialmente exitosa no producía un resultado.En modo de compilación, el algoritmo no funciona con símbolos. Pasa instrucciones al código compilado. La ejecución es muy rápida: después de pasar datos al principio de la lista actual, busca automáticamente todos los caracteres consecutivos posibles en la expresión regular.
El algoritmo de compilación y búsqueda se incluye en el editor de texto de tiempo compartido como búsqueda contextual. Por supuesto, esta no es la única aplicación de este tipo de procedimiento de búsqueda. Por ejemplo, una variante de este algoritmo se utiliza como búsqueda de símbolos en una tabla en ensamblador.
Se supone que el lector está familiarizado con las expresiones regulares y el lenguaje de programación informática IBM 7094.Compilador
El compilador consta de tres etapas que se ejecutan en paralelo. La primera etapa es el filtrado de sintaxis, que permite el paso sólo de expresiones regulares sintácticamente correctas. Este paso también inserta el operador "·" para que coincida con expresiones regulares. En el segundo paso, la expresión regular se convierte al formato postfijo. En la tercera etapa, se crea el código objeto. Las dos primeras etapas son obvias y no nos detendremos en ellas.
El artículo de Thompson no habla de máquinas de estados finitos no deterministas, pero explica bien el algoritmo de tiempo lineal y presenta un programa ALGOL-60 que genera código en lenguaje ensamblador para el IBM 7094. La implementación es complicada, pero la idea es muy simple.
ruta de búsqueda actual. Está representado por un icono ⊕ con una entrada y dos salidas.
La Figura 1 muestra las funciones del tercer paso de compilación al transformar un ejemplo de expresión regular. Los primeros tres caracteres del ejemplo son a, b, cy cada uno crea una entrada de pila S[i] y un campo NNODE.NNODE al código existente para generar la expresión regular resultante en una sola entrada de pila (consulte la Figura 5)
Así es como se vería una expresión regular .*.*=.*, si lo imaginas como en las imágenes del artículo de Thompson.
En la Fig. 0 hay cinco estados a partir de 0, y 3 ciclos que parten de los estados 1, 2 y 3. Estos tres ciclos corresponden a tres .* en una expresión regular. 3 óvalos con puntos corresponden a un símbolo. Ovalado con un cartel. = coincide con un carácter literal =. El estado 4 es definitivo. Si lo alcanzamos, entonces la expresión regular coincide.
Para ver cómo se puede utilizar dicho diagrama de estado para la coincidencia de expresiones regulares .*.*=.*, veremos la coincidencia de cadenas x=x. El programa comienza desde el estado 0, como se muestra en la Fig. 1.
Para que este algoritmo funcione, la máquina de estados debe estar en varios estados simultáneamente. Una máquina finita no determinista realizará todas las transiciones posibles simultáneamente.
Antes de que tenga tiempo de leer los datos de entrada, pasa a los dos primeros estados (1 y 2), como se muestra en la Fig. 2.
En la Fig. 2 muestra lo que sucede cuando mira el primero. x в x=x. x se puede asignar al punto superior, yendo desde el estado 1 y regresando al estado 1. O x se puede asignar al punto siguiente, pasando del estado 2 y volviendo al estado 2.
Después de igualar el primero x в x=x Todavía estamos en los estados 1 y 2. No podemos llegar al estado 3 o 4 porque necesitamos un carácter literal. =.
El algoritmo entonces considera = в x=x. Al igual que x antes, se puede hacer coincidir con cualquiera de los dos bucles superiores del estado 1 al estado 1 o del estado 2 al estado 2, pero el algoritmo puede hacer coincidir el literal = y pasar del estado 2 al estado 3 (e inmediatamente al 4). Esto se muestra en la figura. 3.
El algoritmo luego pasa al último. x в x=x. Desde los estados 1 y 2 son posibles las mismas transiciones de regreso a los estados 1 y 2. Desde el estado 3 x Puede hacer coincidir el punto de la derecha y volver al estado 3.
En esta etapa, cada personaje x=x considerado, y como hemos alcanzado el estado 4, la expresión regular coincide con esa cadena. Cada carácter se procesa una vez, por lo que este algoritmo es lineal en la longitud de la cadena de entrada. Y sin marcha atrás.
Obviamente, después de alcanzar el estado 4 (cuando el algoritmo ha coincidido x=) toda la expresión regular coincide y el algoritmo puede terminar sin considerarla en absoluto x.
Este algoritmo depende linealmente del tamaño de la cadena de entrada.
Fuente: habr.com
