Fai case 9 anos Cloudflare era unha pequena empresa, e eu non traballaba para ela, só era un cliente. Un mes despois de lanzar Cloudflare, recibín unha notificación de que o meu sitio web Parece que o DNS non funciona. Cloudflare fixo un cambio en , e había un DNS roto.
Inmediatamente escribín a Matthew Prince co título "Onde está o meu DNS?" e el enviou unha longa resposta chea de detalles técnicos (), ao que lle respondín:
Autor: John Graham-Cumming
Data: 7 de outubro de 2010, 9:14
Asunto: Re: Onde está o meu DNS?
Para: Matthew PrinceExcelente informe, grazas. Definitivamente chamarei se hai problemas. Probablemente paga a pena escribir unha publicación sobre isto unha vez que recollas toda a información técnica. Creo que a xente gozará dunha historia aberta e honesta. Especialmente se lle achegas gráficos para mostrar como creceu o tráfico desde o lanzamento.
Teño un bo seguimento no meu sitio e recibo unha SMS sobre cada fallo. O seguimento mostra que o fallo ocorreu entre as 13:03:07 e as 14:04:12. As probas realízanse cada cinco minutos.
Seguro que o descubrirás. Estás seguro de que non necesitas a túa propia persoa en Europa? 🙂
E el respondeu:
De: Matthew Prince
Data: 7 de outubro de 2010, 9:57
Asunto: Re: Onde está o meu DNS?
Para: John Graham-CummingGrazas. Respondemos a todos os que escribiron. Estou de camiño á oficina e escribiremos algo no blog ou fixaremos unha publicación oficial no noso taboleiro de anuncios. Estou totalmente de acordo, a honestidade é todo.
Agora Cloudflare é unha empresa moi grande, traballo para ela e agora teño que escribir abertamente sobre o noso erro, as súas consecuencias e as nosas accións.
Acontecementos do 2 de xullo
O 2 de xullo lanzamos unha nova regra en Regras xestionadas para WAF polo que en cada núcleo do procesador que procesa o tráfico HTTP/HTTPS na rede Cloudflare en todo o mundo. Estamos mellorando constantemente as regras xestionadas para os WAF en resposta a novas vulnerabilidades e ameazas. En maio, por exemplo, apresuramos para protexerse contra unha vulnerabilidade grave en SharePoint. O principal obxectivo do noso WAF é a capacidade de implementar regras de forma rápida e global.
Desafortunadamente, a actualización do pasado xoves contiña unha expresión regular que desperdiciaba demasiados recursos da CPU HTTP/HTTPS ao retroceder. Como resultado, as nosas funcións básicas de proxy, CDN e WAF sufriron. O gráfico mostra que os recursos do procesador para servir o tráfico HTTP/HTTPS alcanzan case o 100 % nos servidores da nosa rede.
Uso da CPU nun punto de presenza durante un incidente
Como resultado, os nosos clientes (e os clientes dos nosos clientes) acabaron cunha páxina de erro 502 nos dominios de Cloudflare. Os servidores web front-end de Cloudflare xeraron erros 502 que aínda tiñan núcleos libres pero que non se podían comunicar cos procesos que xestionaban o tráfico HTTP/HTTPS.
Sabemos cantos inconvenientes lles causou aos nosos clientes. Estamos terriblemente avergoñados. E este fallo impediunos xestionar eficazmente o incidente.
Se foses un destes clientes, probablemente estabas asustado, enfadado e molesto. Ademais, non tivemos un . O alto consumo de CPU debeuse a unha regra WAF cunha expresión regular mal redactada que provocou un retroceso excesivo. Aquí está a expresión culpable: (?:(?:"|'|]|}||d|(?:nan|infinity|true|false|null|undefined|symbol|math)|`|-|+)+[)]*;?((?:s|-|~|!|{}||||+)*.*(?:.*=.*)))
Aínda que isto é interesante por si mesmo (e falarei sobre iso con máis detalle a continuación), o servizo Cloudflare estivo inactivo durante 27 minutos non só por mor dunha mala expresión regular. Levamos un tempo describir a secuencia de acontecementos que levaron ao fracaso, polo que tardamos en responder. Ao final da publicación, describirei o retroceso nunha expresión regular e dicirche que facer con el.
Que pasou
Comecemos en orde. Todos os horarios aquí son en UTC.
Ás 13:42, un enxeñeiro do equipo do firewall fixo un pequeno cambio nas regras de detección utilizando un proceso automático. En consecuencia, creouse un ticket de solicitude de cambio. Xestionamos este tipo de entradas a través de Jira (captura de pantalla a continuación).
Despois de 3 minutos, apareceu a primeira páxina de PagerDuty, informando dun problema con WAF. Esta foi unha proba sintética que proba a funcionalidade dos WAF (temos centos deles) fóra de Cloudflare para supervisar o funcionamento normal. Isto foi seguido inmediatamente por páxinas de alertas sobre outras probas de servizo de extremo a extremo de Cloudflare que fallaban, problemas de tráfico global, erros 502 xeneralizados e unha tonelada de informes dos nosos puntos de presenza (PoP) en cidades de todo o mundo que indicaban unha falta. de recursos da CPU.
Recibín varias destas alertas, saín dunha reunión e ía camiño da mesa cando o xefe do noso departamento de desenvolvemento de solucións dixo que perdimos o 80% do noso tráfico. Fun cara aos nosos enxeñeiros de SRE, que xa estaban traballando no problema. Ao principio pensamos que era algún tipo de ataque descoñecido.
Os enxeñeiros de Cloudflare SRE están espallados polo mundo e supervisan a situación durante todo o día. Normalmente, estas alertas infórmanche de problemas locais específicos de alcance limitado, fanse un seguimento en paneis internos e resólvense varias veces ao día. Pero estas páxinas e notificacións indicaban algo realmente grave e os enxeñeiros de SRE declararon inmediatamente o nivel de gravidade P0 e contactaron cos enxeñeiros de xestión e sistemas.
Os nosos enxeñeiros de Londres estaban a escoitar unha conferencia na sala principal nese momento. A charla tivo que ser interrompida, todos se reuniron nunha gran sala de conferencias e chamáronse máis especialistas. Este non era un problema típico que os SRE puidesen tratar con eles mesmos. Era urxente involucrar aos especialistas axeitados.
Ás 14:00 horas determinamos que o problema era do WAF e non había ningún ataque. O equipo de rendemento sacou os datos da CPU e quedou claro que o WAF tiña a culpa. Outro empregado confirmou esta teoría usando strace. Alguén máis viu nos rexistros que había un problema co WAF. Ás 14:02 p.m., todo o equipo chegou a min cando se propuxeron usar a eliminación global, un mecanismo integrado en Cloudflare que apaga un compoñente en todo o mundo.
Como fixemos a matanza global para WAF é unha historia diferente. Non é tan sinxelo. Usamos os nosos propios produtos, e dende o noso servizo non funcionou, non puidemos autenticarnos e iniciar sesión no panel de control interno (cando todo foi arranxado, decatámonos de que algúns membros do equipo perderan o acceso debido a unha función de seguranza que desactiva as credenciais se o panel de control interno non se utiliza para Moito tempo).
E non puidemos acceder aos nosos servizos internos, como Jira ou o sistema de compilación. Necesitabamos un mecanismo de solución, que usabamos con pouca frecuencia (tamén haberá que resolver). Finalmente, un enxeñeiro conseguiu desactivar o WAF ás 14:07 e ás 14:09, os niveis de tráfico e CPU volveron á normalidade en todas partes. O resto dos mecanismos de protección de Cloudflare funcionaron normalmente.
Despois puxémonos a restaurar o WAF. A situación era fóra do normal, polo que realizamos probas negativas (preguntándonos se o cambio era realmente o problema) e probas positivas (asegurándonos de que o retroceso funcionase) nunha cidade usando tráfico separado, trasladando os clientes que pagaban desde alí.
Ás 14:52 estabamos convencidos de que entendiamos o motivo e fixemos unha corrección, e volvemos a habilitar WAF.
Como funciona Cloudflare
Cloudflare ten un equipo de enxeñeiros dedicados á xestión de regras para WAF. Esfórzanse por mellorar as taxas de detección, reducir os falsos positivos e responder rapidamente ás novas ameazas a medida que xorden. Nos últimos 60 días, procesáronse 476 solicitudes de cambio para as regras xestionadas para WAF (unha media cada 3 horas).
Este cambio en particular tivo que implementarse no modo de simulación, onde o tráfico real do cliente pasa pola regra, pero non se bloquea nada. Usamos este modo para probar a eficacia das regras e medir as taxas de falsos positivos e falsos negativos. Pero mesmo no modo de simulación, as regras deben ser executadas, e neste caso a regra contiña unha expresión regular que consumía demasiados recursos do procesador.
Como podes ver na solicitude de cambio anterior, temos un plan de implantación, un plan de retroceso e unha ligazón a un procedemento operativo estándar interno (SOP) para este tipo de implantación. O SOP para cambiar unha regra permite que se publique globalmente. En realidade, en Cloudflare, as cousas fanse de forma completamente diferente, e o SOP indica que primeiro enviamos o software para probas e uso interno a un punto de presenza interno (PoP) (que usan os nosos empregados) e despois a un pequeno número de clientes. un lugar illado, despois a un gran número de clientes, e só despois a todo o mundo.
Isto é o que parece. Usamos git internamente a través de BitBucket. Os enxeñeiros que traballan en cambios envían o código, que está construído para TeamCity, e cando a compilación pasa, asígnanse os revisores. Unha vez que se aproba unha solicitude de extracción, ensambla o código e realízanse (de novo) unha serie de probas.
Se a compilación e as probas se completan con éxito, créase unha solicitude de cambio en Jira e o xestor ou o responsable responsable debe aprobar o cambio. Despois da aprobación, prodúcese o despregamento na denominada "menaxería PoP": DOG, PIG e (can, porco e canario).
DOG PoP é un Cloudflare PoP (como todas as outras cidades das nosas cidades) que só o utilizan os empregados de Cloudflare. PoP para uso interno permítelle detectar problemas antes de que o tráfico de clientes comece a fluír cara á solución. Cousa útil.
Se a proba DOG ten éxito, o código pasa á fase PIG (cobaia). Este é Cloudflare PoP, onde unha pequena cantidade de tráfico gratuíto de clientes flúe a través do novo código.
Se todo está ben, o código entra en Canarias. Temos tres PoPs canarios en diferentes partes do mundo. Neles, o tráfico de clientes de pago e gratuíto pasa polo novo código, e esta é a última comprobación de erros.
Proceso de lanzamento de software en Cloudflare
Se o código está ben en Canarias, soltámolo. Percorrer todas as etapas - CAN, PORCO, Canario, todo o mundo - leva varias horas ou días, dependendo do cambio de código. Debido á diversidade da rede e dos clientes de Cloudflare, probamos a fondo o código antes de publicalo globalmente para todos os clientes. Pero WAF non segue especificamente este proceso porque hai que responder rapidamente ás ameazas.
Ameazas WAF
Nos últimos anos, houbo un aumento significativo das ameazas nas aplicacións comúns. Isto débese á maior dispoñibilidade de ferramentas de proba de software. Por exemplo, escribimos recentemente sobre ).
Fonte:
Moitas veces, unha proba de concepto créase e publícase inmediatamente en Github para que os equipos que manteñen a aplicación poidan probala rapidamente e asegurarse de que estea adecuadamente protexida. Polo tanto, Cloudflare necesita a capacidade de responder aos novos ataques o máis rápido posible para que os clientes teñan a oportunidade de arranxar o seu software.
Un gran exemplo da resposta rápida de Cloudflare é a implantación de proteccións contra vulnerabilidades de SharePoint en maio (). Case inmediatamente despois de que se fixeran os anuncios, observamos un gran número de intentos de explotar a vulnerabilidade nas instalacións de SharePoint dos nosos clientes. Os nosos rapaces están constantemente supervisando novas ameazas e escribindo regras para protexer os nosos clientes.
Suponse que a regra que causou o problema o xoves protexe contra os scripts entre sitios (XSS). Estes ataques tamén foron moito máis frecuentes nos últimos anos.
Fonte:
O procedemento estándar para cambiar unha regra xestionada para un WAF é realizar probas de integración continua (CI) antes da implantación global. O xoves pasado fixemos isto e publicamos as normas. Ás 13:31, un enxeñeiro presentou unha solicitude de retirada aprobada cun cambio.
Ás 13:37 TeamCity recolleu as normas, realizou probas e deu o visto e prace. O paquete de probas WAF proba a funcionalidade básica do WAF e consta dunha gran cantidade de probas unitarias para funcións individuais. Despois das probas unitarias, probamos as regras para o WAF utilizando un gran número de solicitudes HTTP. As solicitudes HTTP comproban que solicitudes debe ser bloqueada polo WAF (para interceptar o ataque) e cales se poden permitir (para non bloquear todo e evitar falsos positivos). Pero non probamos o uso excesivo da CPU e examinando os rexistros das compilacións anteriores de WAF mostra que o tempo de execución das probas de regras non aumentou e era difícil sospeitar que non había recursos suficientes.
As probas pasaron e TeamCity comezou a implementar automaticamente o cambio ás 13:42.
Mercurio
As regras de WAF céntranse na corrección inmediata das ameazas, polo que as implementamos mediante a tenda de valores-chave distribuída de Quicksilver, que propaga os cambios a nivel global en segundos. Todos os nosos clientes utilizan esta tecnoloxía cando cambian a configuración no panel ou a través da API, e é grazas a ela que respondemos aos cambios á velocidade do lóstrego.
Non falamos moito de Quicksilver. Anteriormente usabamos como unha tenda de clave-valor distribuída a nivel mundial, pero houbo problemas operativos con ela e creamos a nosa propia tenda, replicada en máis de 180 cidades. Agora usamos Quicksilver para enviar cambios de configuración aos clientes, actualizar as regras de WAF e distribuír o código JavaScript escrito polos clientes aos traballadores de Cloudflare.
Só leva uns segundos facer clic nun botón dun panel ou chamar a unha API para facer un cambio de configuración en todo o mundo. Aos clientes encantoulles esta velocidade de configuración. E Workers ofrécelle unha implementación global de software case instantánea. De media, Quicksilver propaga uns 350 cambios por segundo.
E Quicksilver é moi rápido. De media, alcanzamos o percentil 99 de 2,29 segundos para propagar os cambios a todos os ordenadores do mundo. A velocidade adoita ser boa. Despois de todo, cando activas unha función ou borras a caché, ocorre case ao instante e en todas partes. O envío de código a través de Cloudflare Workers ocorre á mesma velocidade. Cloudflare promete aos seus clientes actualizacións rápidas no momento axeitado.
Pero neste caso, a velocidade xogounos unha broma cruel e as regras cambiaron en todas partes en cuestión de segundos. Quizais teña notado que o código WAF usa Lua. Cloudflare usa Lua amplamente na produción e nos detalles nós . Lua usa WAF internamente e aplica retroceso para a correspondencia. Non ten mecanismos para protexerse contra expresións que se descontrolan. A continuación falarei máis sobre isto e o que estamos facendo ao respecto.
Antes de que as regras fosen despregadas, todo saíu sen problemas: a solicitude de extracción foi creada e aprobada, a canalización CI/CD recompilou e probou o código, a solicitude de cambio presentouse segundo o SOP que regula a implantación e a recuperación e completouse a implantación.
Proceso de implementación de Cloudflare WAF
Algo fallou
Como dixen, implementamos ducias de novas regras de WAF cada semana e temos moitos sistemas instalados para protexernos contra as consecuencias negativas desta implantación. E cando algo sae mal, adoita ser unha combinación de varias circunstancias á vez. Se atopas só unha razón, isto, por suposto, é tranquilizador, pero non sempre é certo. Estes son os motivos que xuntos levaron á falla do noso servizo HTTP/HTTPS.
- Un enxeñeiro escribiu unha expresión regular que pode resultar excesiva .
- Unha característica que podería evitar que a expresión regular malgaste demasiada CPU eliminouse por erro nunha refactorización do WAF varias semanas antes; a refactorización era necesaria para que o WAF consumise menos recursos.
- O motor de expresións regulares non tiña garantías de complexidade.
- O conxunto de probas non puido detectar un consumo excesivo de CPU.
- O SOP permite que os cambios de regras non urxentes se implementen globalmente sen un proceso de varios pasos.
- O plan de retroceso requiriu executar unha compilación completa de WAF dúas veces, o que levou moito tempo.
- A primeira alerta sobre problemas de tráfico global disparouse demasiado tarde.
- Tardamos un tempo en actualizar a páxina de estado.
- Tivemos problemas para acceder aos sistemas debido a unha falla e o procedemento de derivación non estaba ben establecido.
- Os enxeñeiros de SRE perderon o acceso a algúns sistemas porque as súas credenciais caducaron por motivos de seguridade.
- Os nosos clientes non tiveron acceso ao panel de control nin á API de Cloudflare porque pasan por unha rexión de Cloudflare.
O que cambiou dende o xoves pasado
En primeiro lugar, paramos completamente todo o traballo en versións para WAF e estamos a facer o seguinte:
- Reintroducimos a protección contra o uso excesivo da CPU que eliminamos. (Listo)
- Comprobando manualmente as 3868 regras das regras xestionadas para que o WAF atope e corrixa outros posibles casos de retroceso excesivo. (Verificación completada)
- Incluímos un perfil de rendemento para todas as regras do conxunto de probas. (Previsto: 19 de xullo)
- Cambiando a un motor de expresións regulares ou - ambos ofrecen garantías de tempo de execución. (Previsto: 31 de xullo)
- Estamos reescribindo o SOP para implementar regras por etapas, como outro software en Cloudflare, pero ao mesmo tempo temos a capacidade de implementar con urxencia globalmente se os ataques xa comezaron.
- Estamos a desenvolver a capacidade de eliminar con urxencia o panel de control e a API de Cloudflare da rexión de Cloudflare.
- Automatización das actualizacións da páxina .
A longo prazo afastámonos do Lua WAF que escribín hai uns anos. Mover WAF a . Deste xeito, o WAF será máis rápido e recibirá un nivel adicional de protección.
Conclusión
Este fallo causounos problemas a nós e aos nosos clientes. Actuamos rapidamente para corrixir a situación e agora estamos traballando nos fallos nos procesos que provocaron o accidente, ademais de investigar aínda máis para evitar posibles problemas coas expresións regulares no futuro ao migrar á nova tecnoloxía.
Estamos moi avergoñados por esta interrupción e pedimos desculpas aos nosos clientes. Agardamos que estes cambios garanticen que algo así non se repita.
Aplicación. Retroceder as expresións regulares
Para entender como a expresión:
(?:(?:"|'|]|}||d
(?:nan|infinity|true|false|null|undefined|symbol|math)|`|-
|+)+[)]*;?((?:s|-|~|!|{}||||+)*.*(?:.*=.*)))consumiu todos os recursos da CPU, cómpre saber un pouco sobre como funciona o motor estándar de expresións regulares. O problema aquí é o patrón .*(?:.*=.*). (?: e correspondente ) é un grupo non capturador (é dicir, a expresión entre parénteses agrúpase como unha única expresión).
No contexto do consumo excesivo de CPU, este patrón pódese describir como .*.*=.*. Nesta forma, o patrón parece innecesariamente complexo. Pero o máis importante é que no mundo real, as expresións (como expresións complexas nas regras de WAF) que piden ao motor que coincida cun fragmento seguido doutro poden provocar un retroceso catastrófico. E por iso.
En expresión regular . significa que tes que facer coincidir un personaxe, .* - facer coincidir cero ou máis caracteres "con ganas", é dicir, capturando un máximo de caracteres, de xeito que .*.*=.* significa que coincida con cero ou máis caracteres, despois coincida con cero ou máis caracteres, busque o literal = carácter, coincida con cero ou máis caracteres.
Imos tomar a liña de proba x=x. Corresponde á expresión .*.*=.*. .*.* antes de que o signo de igual coincida co primeiro x (un dos grupos .* corresponde a x, e o segundo - cero caracteres). .* despois = últimos partidos x.
Esta comparación require 23 pasos. Primeiro grupo .* в .*.*=.* actúa con avaricia e coincide con toda a cadea x=x. O motor pasa ao seguinte grupo .*. Non temos máis personaxes que coincidir, polo que o segundo grupo .* coincide con cero caracteres (isto está permitido). Entón o motor móvese ao sinal =. Non hai máis símbolos (primeiro grupo .* utilizou toda a expresión x=x), non hai comparación.
E entón o motor de expresións regulares volve ao principio. Pasa ao primeiro grupo .* e compárao с x= (no seu lugar x=x), e logo asume o segundo grupo .*. Segundo grupo .* se compara co segundo x, e de novo non nos quedan personaxes. E cando o motor chega de novo = в .*.*=.*, nada funciona. E volve dar marcha atrás.
Esta vez o grupo .* aínda coincide x=, pero o segundo grupo .* nunca máis x, e cero caracteres. O motor está tentando atopar un carácter literal = no patrón .*.*=.*, pero non sae (despois de todo, o primeiro grupo xa o ocupou .*). E volve dar marcha atrás.
Esta vez o primeiro grupo .* só toma a primeira x. Pero o segundo grupo .* capturas "avidamente". =x. Xa adiviñaches que pasará? O motor tenta coincidir co literal =, falla e fai outra marcha atrás.
O primeiro grupo de .* aínda coincide co primeiro x. Segundo .* só leva =. Por suposto, o motor non pode coincidir co literal =, porque o segundo grupo xa o fixo .*. E de novo retrocede. E estamos tentando facer coincidir unha cadea de tres caracteres!
Como resultado, o primeiro grupo .* coincide só co primeiro x, segundo .* - con cero caracteres e o motor finalmente coincide co literal = na expresión с = en liña. O seguinte é o último grupo .* compárase co último x.
23 pasos só para x=x. Mira un pequeno vídeo sobre o uso de Perl , que mostra como se producen os pasos e as marchas atrás.
Isto xa é moito traballo, pero e se en cambio x=x teremos x=xx? Son 33 pasos. E se x=xxx? 45. A relación non é lineal. O gráfico mostra unha comparación de x=x para x=xxxxxxxxxxxxxxxxxxxx (20 x despois =). Se temos 20 x despois =, o motor completa a coincidencia en 555 pasos! (Ademais, se perdemos x= e a cadea consiste simplemente en 20 x, o motor dará 4067 pasos para entender que non hai coincidencias).
Este vídeo mostra todo o retroceso para comparar x=xxxxxxxxxxxxxxxxxxxx:
O problema é que a medida que aumenta o tamaño da corda, o tempo de coincidencia crece de forma superlineal. Pero as cousas poden empeorar aínda que se modifique lixeiramente a expresión regular. Digamos que tiñamos .*.*=.*; (é dicir, había un punto e coma literal ao final do patrón). Por exemplo, para facer coincidir unha expresión como foo=bar;.
E aquí retroceder sería un verdadeiro desastre. Para comparación x=x dará 90 pasos, non 23. E ese número medra rapidamente. Para comparar x= e 20 x, son necesarios 5353 pasos. Aquí está o gráfico. Observa os valores do eixe Y en comparación co gráfico anterior.
Se estás interesado, consulta os 5353 pasos coincidentes con erros x=xxxxxxxxxxxxxxxxxxxx и .*.*=.*;
Usando a correspondencia preguiceiro en lugar de codicioso, pódese controlar o alcance do retroceso. Se cambiamos a expresión orixinal a .*?.*?=.*?, para comparación x=x levará 11 pasos (non 23). Como para x=xxxxxxxxxxxxxxxxxxxx. Todo porque ? despois .* dille ao motor que coincida cun número mínimo de caracteres antes de continuar.
Pero os mapeos preguiceiros non solucionan completamente o problema do retroceso. Se substituímos o exemplo catastrófico .*.*=.*; en .*?.*?=.*?;, o tempo de execución seguirá sendo o mesmo. x=x aínda require 555 pasos, e x= e 20 x - 5353.
O único que se pode facer (ademais de reescribir completamente o patrón para unha maior especificidade) é abandonar o motor de expresións regulares co seu mecanismo de retroceso. Isto é o que faremos nas próximas semanas.
A solución a este problema coñécese desde 1968, cando Kent Thompson escribiu un artigo ("Métodos de programación: Algoritmo de busca de expresións regulares"). O artigo describe un mecanismo que permite converter unha expresión regular en máquinas de estados finitos non deterministas e, tras cambios de estado en máquinas de estados finitos non deterministas, utilizar un algoritmo cuxo tempo de execución depende linealmente da cadea coincidente.
Métodos de programación
Algoritmo de busca de expresións regulares
Ken Thompson
Bell Telephone Laboratories, Inc., Murray Hill, Nova XerseiDescribe un método para buscar unha cadea específica de caracteres no texto e analiza a implementación deste método en forma de compilador. O compilador toma a expresión regular como código fonte e produce o programa IBM 7094 como código obxecto. O programa obxecto recibe a entrada en forma de texto de busca e emite un sinal cada vez que se relaciona unha cadea de texto cunha determinada expresión regular. O artigo ofrece exemplos, problemas e solucións.
Algoritmo
Os algoritmos de busca anteriores producían un retroceso se unha busca parcialmente exitosa non producía un resultado.No modo de compilación, o algoritmo non funciona con símbolos. Pasa instrucións ao código compilado. A execución é moi rápida: despois de pasar os datos á parte superior da lista actual, busca automaticamente todos os caracteres consecutivos posibles na expresión regular.
O algoritmo de compilación e busca inclúese no editor de texto de tempo compartido como busca contextual. Por suposto, esta está lonxe de ser a única aplicación deste procedemento de busca. Por exemplo, unha variante deste algoritmo úsase como busca de símbolos nunha táboa en ensamblador.
Suponse que o lector está familiarizado coas expresións regulares e coa linguaxe de programación informática IBM 7094.Compilador
O compilador consta de tres etapas que se executan en paralelo. A primeira etapa é o filtrado de sintaxe, que permite que só pasen expresións regulares sintácticamente correctas. Este paso tamén insire o operador "·" para que coincida con expresións regulares. No segundo paso, a expresión regular convértese a forma postfix. Na terceira etapa, créase o código obxecto. As 2 primeiras etapas son obvias, e non nos deteremos nelas.
O artigo de Thompson non fala de máquinas de estados finitos non deterministas, pero si explica ben o algoritmo de tempo lineal e presenta un programa ALGOL-60 que xera código de linguaxe ensamblador para o IBM 7094. A implementación é complicada, pero a idea é moi sinxela.
ruta de busca actual. Represéntase cunha icona ⊕ cunha entrada e dúas saídas.
A figura 1 mostra as funcións do terceiro paso de compilación ao transformar un exemplo de expresión regular. Os tres primeiros caracteres do exemplo son a, b, c, e cada un crea unha entrada de pila S[i] e un campo NNODE.NNODE ao código existente para xerar a expresión regular resultante nunha única entrada de pila (consulte a Figura 5)
Así sería unha expresión regular .*.*=.*, se o imaxinas como nas imaxes do artigo de Thompson.
Na Fig. 0 hai cinco estados a partir de 0, e 3 ciclos que parten dos estados 1, 2 e 3. Estes tres ciclos corresponden a tres .* nunha expresión regular. 3 óvalos con puntos corresponden a un símbolo. Ovalado cun sinal = coincide cun carácter literal =. O estado 4 é definitivo. Se chegamos a el, entón a expresión regular coincide.
Para ver como se pode usar un diagrama de estados para a correspondencia de expresións regulares .*.*=.*, veremos a coincidencia de cadeas x=x. O programa comeza a partir do estado 0, como se mostra na Fig. 1.
Para que este algoritmo funcione, a máquina de estados debe estar en varios estados á vez. Unha máquina finita non determinista fará todas as transicións posibles simultaneamente.
Antes de ter tempo para ler os datos de entrada, pasa aos dous primeiros estados (1 e 2), como se mostra na Fig. 2.
Na Fig. 2 mostra o que ocorre cando mira o primeiro x в x=x. x pode mapear ata o punto superior, pasando do estado 1 e de volta ao estado 1. Ou x pode mapear ata o punto seguinte, pasando do estado 2 e de volta ao estado 2.
Despois de igualar o primeiro x в x=x aínda estamos nos estados 1 e 2. Non podemos chegar ao estado 3 ou 4 porque necesitamos un carácter literal =.
O algoritmo considera entón = в x=x. Como x antes del, pódese facer coincidir con calquera dos dous bucles principais do estado 1 ao estado 1 ou do estado 2 ao estado 2, pero o algoritmo pode coincidir co literal = e pasar do estado 2 ao estado 3 (e inmediatamente 4). Isto móstrase na Fig. 3.
Despois, o algoritmo pasa ao último x в x=x. Desde os estados 1 e 2 son posibles as mesmas transicións de volta aos estados 1 e 2. Desde o estado 3 x pode coincidir co punto da dereita e volver ao estado 3.
Nesta fase, cada personaxe x=x considerado, e xa que chegamos ao estado 4, a expresión regular coincide con esa cadea. Cada carácter é procesado unha vez, polo que este algoritmo é lineal na lonxitude da cadea de entrada. E sen retroceso.
Obviamente, despois de alcanzar o estado 4 (cando o algoritmo coincide x=) a expresión regular enteira coincide e o algoritmo pode rematar sen consideralo en absoluto x.
Este algoritmo depende linealmente do tamaño da cadea de entrada.
Fonte: www.habr.com