Fa gairebé 9 anys Cloudflare era una empresa petita i no hi treballava, només era un client. Un mes després de llançar Cloudflare, vaig rebre una notificació que el meu lloc web Sembla que el DNS no funciona. Cloudflare ha fet un canvi a , i hi havia un DNS trencat.
Immediatament vaig escriure a Matthew Prince amb el títol "On és el meu DNS?" i em va enviar una llarga resposta plena de detalls tècnics (), a la qual li vaig respondre:
De: John Graham-Cumming
Data: 7 d'octubre de 2010, 9:14
Assumpte: Re: On és el meu DNS?
A: Matthew PrinceGenial informe, gràcies. Definitivament trucaré si hi ha problemes. Probablement val la pena escriure una publicació sobre això un cop hagueu recopilat tota la informació tècnica. Crec que la gent gaudirà d'una història oberta i honesta. Sobretot si hi adjunteu gràfics per mostrar com ha crescut el trànsit des del llançament.
Tinc un bon seguiment al meu lloc i rebo un SMS sobre cada error. El seguiment mostra que l'error s'ha produït des de les 13:03:07 fins a les 14:04:12. Les proves es fan cada cinc minuts.
Estic segur que ho sabràs. Esteu segur que no necessiteu la vostra pròpia persona a Europa? 🙂
I ell va respondre:
De: Matthew Prince
Data: 7 d'octubre de 2010, 9:57
Assumpte: Re: On és el meu DNS?
A: John Graham-CummingGràcies. Vam respondre a tothom que va escriure. Ara vaig cap a l'oficina i escriurem alguna cosa al bloc o fixarem una publicació oficial al nostre tauler d'anuncis. Estic totalment d'acord, l'honestedat ho és tot.
Ara Cloudflare és una empresa molt gran, hi treballo, i ara he d'escriure obertament sobre el nostre error, les seves conseqüències i les nostres accions.
Actes del 2 de juliol
El 2 de juliol vam llançar una nova regla a Regles gestionades per a WAF, per la qual cosa a cada nucli del processador que processa el trànsit HTTP/HTTPS a la xarxa Cloudflare a tot el món. Estem millorant constantment les regles gestionades per als WAF en resposta a noves vulnerabilitats i amenaces. Al maig, per exemple, ens vam afanyar per protegir contra una vulnerabilitat greu a SharePoint. L'objectiu del nostre WAF és la capacitat de desplegar regles de manera ràpida i global.
Malauradament, l'actualització del dijous passat contenia una expressió regular que malgastava massa recursos de CPU HTTP/HTTPS en retrocedir. Com a resultat, les nostres funcions bàsiques de proxy, CDN i WAF van patir. El gràfic mostra que els recursos del processador per servir el trànsit HTTP/HTTPS arriben gairebé al 100% als servidors de la nostra xarxa.
Ús de la CPU en un punt de presència durant un incident
Com a resultat, els nostres clients (i els clients dels nostres clients) van acabar amb una pàgina d'error 502 als dominis de Cloudflare. Els servidors web de front-end de Cloudflare van generar errors 502 que encara tenien nuclis lliures però que no podien comunicar-se amb els processos que gestionaven el trànsit HTTP/HTTPS.
Sabem les molèsties que això ha causat als nostres clients. Ens fa molta vergonya. I aquest fracàs ens va impedir fer front efectivament a l'incident.
Si eres un d'aquests clients, probablement estaves espantat, enfadat i molest. A més, no hem tingut cap . L'elevat consum de CPU es va deure a una regla WAF amb una expressió regular mal redactada que va provocar un retrocés excessiu. Aquí teniu l'expressió culpable: (?:(?:"|'|]|}||d|(?:nan|infinity|true|false|null|undefined|symbol|math)|`|-|+)+[)]*;?((?:s|-|~|!|{}||||+)*.*(?:.*=.*)))
Tot i que això és interessant per si mateix (i en parlaré amb més detall a continuació), el servei Cloudflare va estar caigut durant 27 minuts no només a causa d'una mala expressió regular. Vam trigar una estona a descriure la seqüència d'esdeveniments que van conduir al fracàs, així que vam trigar a respondre. Al final de la publicació, descriuré la marxa enrere amb una expressió regular i us diré què heu de fer-hi.
Què va passar
Comencem per ordre. Totes les hores aquí són a UTC.
A les 13:42, un enginyer de l'equip del tallafoc va fer un petit canvi a les regles de detecció utilitzant un procés automàtic. En conseqüència, es va crear un tiquet de sol·licitud de canvi. Gestionem aquestes entrades a través de Jira (captura de pantalla a continuació).
Al cap de 3 minuts, va aparèixer la primera pàgina de PagerDuty, informant d'un problema amb WAF. Aquesta va ser una prova sintètica que prova la funcionalitat dels WAF (en tenim centenars) fora de Cloudflare per controlar el funcionament normal. Això va ser seguit immediatament per pàgines d'alertes sobre altres proves de servei d'extrem a extrem de Cloudflare que fallaven, problemes de trànsit global, errors 502 generalitzats i un munt d'informes dels nostres punts de presència (PoP) a ciutats d'arreu del món que indicaven una mancança. de recursos de la CPU.
Vaig rebre diverses d'aquestes alertes, vaig sortir d'una reunió i vaig anar a la taula quan el cap del nostre departament de desenvolupament de solucions va dir que havíem perdut el 80% del nostre trànsit. Vaig córrer als nostres enginyers SRE, que ja estaven treballant en el problema. Al principi vam pensar que era una mena d'atac desconegut.
Els enginyers de Cloudflare SRE estan dispersos per tot el món i controlen la situació durant tot el dia. Normalment, aquestes alertes us notifiquen problemes locals específics d'abast limitat, es fan un seguiment als taulers interns i es resolen diverses vegades al dia. Però aquestes pàgines i notificacions indicaven alguna cosa realment greu, i els enginyers de SRE van declarar immediatament el nivell de gravetat P0 i van contactar amb els enginyers de gestió i sistemes.
Els nostres enginyers de Londres estaven escoltant una conferència a la sala principal en aquell moment. La conferència va haver de ser interrompuda, tothom es va reunir en una gran sala de conferències i es van cridar més especialistes. Aquest no era un problema típic que els SRE poguessin fer front a ells mateixos. Era urgent implicar els especialistes adequats.
A les 14:00 vam determinar que el problema era del WAF i no hi havia atac. L'equip de rendiment va treure les dades de la CPU i va quedar clar que el WAF era el culpable. Un altre empleat va confirmar aquesta teoria mitjançant Strace. Algú més va veure als registres que hi havia un problema amb WAF. A les 14:02 p.m., tot l'equip va venir a mi quan es va proposar utilitzar la matança global, un mecanisme integrat a Cloudflare que tanca un component a tot el món.
Com vam fer la matança global per a WAF és una història diferent. No és tan senzill. Utilitzem els nostres propis productes, i des del nostre servei no va funcionar, no ens vam poder autenticar i iniciar sessió al tauler de control intern (quan tot es va solucionar, vam saber que alguns membres de l'equip havien perdut l'accés a causa d'una funció de seguretat que desactiva les credencials si el tauler de control intern no s'utilitza per a un llarg temps).
I no vam poder accedir als nostres serveis interns, com ara Jira o el sistema de compilació. Necessitàvem un mecanisme de solució, que vam utilitzar amb poca freqüència (també s'haurà de resoldre). Finalment, un enginyer va aconseguir desactivar el WAF a les 14:07 i a les 14:09, el trànsit i els nivells de CPU van tornar a la normalitat a tot arreu. La resta de mecanismes de protecció de Cloudflare van funcionar amb normalitat.
Després ens vam posar a restaurar el WAF. La situació era fora del normal, de manera que vam fer proves negatives (preguntant-nos si el canvi era realment el problema) i proves positives (assegurant-nos que el retrocés funcionés) en una ciutat utilitzant trànsit separat, transferint clients que pagaven des d'allà.
A les 14:52 estàvem convençuts que vam entendre el motiu i vam fer una correcció, i vam tornar a habilitar WAF.
Com funciona Cloudflare
Cloudflare té un equip d'enginyers dedicats a la gestió de regles per a WAF. S'esforcen per millorar les taxes de detecció, reduir els falsos positius i respondre ràpidament a noves amenaces a mesura que surten. En els darrers 60 dies, s'han processat 476 sol·licituds de canvi de regles gestionades per a WAF (una mitjana d'una cada 3 hores).
Aquest canvi en particular s'havia de desplegar en mode de simulació, on el trànsit real del client passa per la regla, però no es bloqueja res. Utilitzem aquest mode per provar l'eficàcia de les regles i mesurar les taxes de falsos positius i falsos negatius. Però fins i tot en mode de simulació, les regles s'han d'executar realment i, en aquest cas, la regla contenia una expressió regular que consumia massa recursos del processador.
Com podeu veure a la sol·licitud de canvi anterior, tenim un pla de desplegament, un pla de retrocés i un enllaç a un procediment operatiu estàndard intern (SOP) per a aquest tipus de desplegament. El SOP per canviar una regla permet que es publiqui globalment. De fet, a Cloudflare, les coses es fan d'una manera completament diferent, i el SOP dicta que primer enviem el programari per a proves i ús intern a un punt de presència intern (PoP) (que utilitzen els nostres empleats) i després a un petit nombre de clients en una ubicació aïllada, després a un gran nombre de clients, i només després a tot el món.
Això és el que sembla. Utilitzem git internament a través de BitBucket. Els enginyers que treballen en els canvis envien el codi, que està creat a TeamCity, i quan la compilació passa, s'assignen els revisors. Un cop s'aprova una sol·licitud d'extracció, s'assembla el codi i es fan una sèrie de proves (de nou).
Si la compilació i les proves es completen amb èxit, es crea una sol·licitud de canvi a Jira i el responsable o responsable ha d'aprovar el canvi. Després de l'aprovació, el desplegament es produeix a l'anomenada "menagerie PoP": DOG, PIG i (gos, porc i canari).
DOG PoP és un Cloudflare PoP (com qualsevol altra de les nostres ciutats) que només l'utilitzen els empleats de Cloudflare. PoP per a ús intern us permet detectar problemes abans que el trànsit de clients comenci a fluir a la solució. Cosa útil.
Si la prova del GOS té èxit, el codi passa a l'etapa PIG (conillet d'índies). Es tracta de Cloudflare PoP, on una petita quantitat de trànsit gratuït de clients flueix a través del codi nou.
Si tot va bé, el codi entra a Canàries. Tenim tres PoPs canaris a diferents parts del món. En ells, el trànsit de clients de pagament i gratuït passa pel nou codi, i aquesta és la darrera comprovació d'errors.
Procés de llançament del programari a Cloudflare
Si el codi està bé a Canary, l'alliberem. Passar per totes les etapes -GO, PORC, Canari, el món sencer- triga unes quantes hores o dies, depenent del canvi de codi. A causa de la diversitat de la xarxa i els clients de Cloudflare, provem el codi a fons abans de llançar-lo globalment a tots els clients. Però WAF no segueix aquest procés específicament perquè les amenaces s'han de respondre ràpidament.
Amenaces de WAF
Durant els últims anys, hi ha hagut un augment significatiu de les amenaces en aplicacions comunes. Això es deu a la major disponibilitat d'eines de prova de programari. Per exemple, recentment hem escrit sobre ).
Font:
Molt sovint, es crea una prova de concepte i es publica immediatament a Github perquè els equips que mantenen l'aplicació puguin provar-la ràpidament i assegurar-se que està adequadament segura. Per tant, Cloudflare necessita la capacitat de respondre als nous atacs el més ràpidament possible perquè els clients tinguin l'oportunitat d'arreglar el seu programari.
Un bon exemple de la resposta ràpida de Cloudflare és el desplegament de les proteccions de vulnerabilitat de SharePoint al maig (). Gairebé immediatament després de fer els anuncis, vam observar un gran nombre d'intents d'explotar la vulnerabilitat a les instal·lacions de SharePoint dels nostres clients. Els nostres nois estan constantment supervisant noves amenaces i escrivint regles per protegir els nostres clients.
La regla que va causar el problema dijous havia de protegir contra els scripts entre llocs (XSS). Aquests atacs també s'han tornat molt més freqüents en els últims anys.
Font:
El procediment estàndard per canviar una regla gestionada per a un WAF és dur a terme proves d'integració contínua (CI) abans del desplegament global. Dijous passat vam fer això i vam desplegar les normes. A les 13:31, un enginyer va presentar una sol·licitud d'extracció aprovada amb un canvi.
A les 13:37 TeamCity va recollir les regles, va fer proves i va donar el vistiplau. El conjunt de proves WAF prova la funcionalitat bàsica del WAF i consta d'un gran nombre de proves unitàries per a funcions individuals. Després de les proves d'unitat, vam provar les regles del WAF mitjançant un gran nombre de sol·licituds HTTP. Les peticions HTTP comproven quines sol·licituds han de ser bloquejades pel WAF (per interceptar l'atac) i quines es poden permetre (per no bloquejar-ho tot i evitar falsos positius). Però no vam provar l'ús excessiu de la CPU i l'examen dels registres de les versions anteriors de WAF mostra que el temps d'execució de la prova de regles no va augmentar i era difícil sospitar que no hi hauria prou recursos.
Les proves van passar i TeamCity va començar a desplegar automàticament el canvi a les 13:42.
Argent viu
Les regles WAF se centren en la correcció immediata de les amenaces, de manera que les despleguem mitjançant el magatzem de valor-clau distribuït de Quicksilver, que propaga els canvis globalment en segons. Tots els nostres clients utilitzen aquesta tecnologia quan canvien la configuració al tauler o a través de l'API, i és gràcies a ella que responem als canvis amb la velocitat del llamp.
No hem parlat gaire de Quicksilver. Abans hem utilitzat com a botiga de valor-clau distribuïda a nivell mundial, però hi va haver problemes operatius i vam crear la nostra pròpia botiga, replicada a més de 180 ciutats. Ara fem servir Quicksilver per enviar canvis de configuració als clients, actualitzar les regles WAF i distribuir codi JavaScript escrit pels clients als treballadors de Cloudflare.
Només triguen uns quants segons fer clic a un botó d'un tauler o trucar a una API per fer un canvi de configuració a tot el món. Als clients els va encantar aquesta velocitat de configuració. I Workers els ofereix un desplegament global de programari gairebé instantani. De mitjana, Quicksilver propaga uns 350 canvis per segon.
I Quicksilver és molt ràpid. De mitjana, vam aconseguir el percentil 99 de 2,29 segons per propagar els canvis a tots els ordinadors del món. La velocitat sol ser una bona cosa. Al cap i a la fi, quan activeu una funció o buideu la memòria cau, passa gairebé a l'instant i a tot arreu. L'enviament de codi a través de Cloudflare Workers es fa a la mateixa velocitat. Cloudflare promet als seus clients actualitzacions ràpides en el moment adequat.
Però en aquest cas, la velocitat ens va fer una broma cruel i les regles van canviar a tot arreu en qüestió de segons. És possible que hàgiu notat que el codi WAF utilitza Lua. Cloudflare utilitza Lua àmpliament en la producció i els detalls som . Lua utilitza WAF internament i aplica marxa enrere per a la concordança. No té mecanismes per protegir-se de les expressions que es descontrolen. A continuació parlaré més d'això i del que estem fent al respecte.
Abans de desplegar les regles, tot va anar sense problemes: es va crear i aprovar la sol·licitud d'extracció, la canalització CI/CD va recopilar i provar el codi, la sol·licitud de canvi es va enviar d'acord amb el SOP que regula el desplegament i la retroalimentació, i el desplegament es va completar.
Procés de desplegament de Cloudflare WAF
Alguna cosa ha anat malament
Com he dit, implementem desenes de noves regles WAF cada setmana i tenim molts sistemes en marxa per protegir-nos de les conseqüències negatives d'aquest desplegament. I quan alguna cosa va malament, sol ser una combinació de diverses circumstàncies alhora. Si només trobeu una raó, això, per descomptat, és tranquil·litzador, però no sempre és cert. Aquests són els motius que junts van provocar el fracàs del nostre servei HTTP/HTTPS.
- Un enginyer va escriure una expressió regular que pot resultar en excessiva .
- Una característica que podria haver evitat que l'expressió regular malgastés massa CPU es va eliminar per error en una refactorització del WAF diverses setmanes abans: la refactorització era necessària per fer que el WAF consumís menys recursos.
- El motor d'expressions regulars no tenia garanties de complexitat.
- El conjunt de proves no ha pogut detectar un consum excessiu de CPU.
- El SOP permet que els canvis de regles que no siguin d'emergència es puguin implementar globalment sense un procés de diversos passos.
- El pla de retrocés requeria executar una compilació WAF completa dues vegades, cosa que va trigar molt de temps.
- La primera alerta sobre problemes de trànsit global es va activar massa tard.
- Hem trigat una estona a actualitzar la pàgina d'estat.
- Vam tenir problemes per accedir als sistemes a causa d'una fallada i el procediment de bypass no estava ben establert.
- Els enginyers SRE van perdre l'accés a alguns sistemes perquè les seves credencials van caducar per motius de seguretat.
- Els nostres clients no tenien accés al tauler o API de Cloudflare perquè passen per una regió de Cloudflare.
El que ha canviat des de dijous passat
En primer lloc, vam aturar completament tot el treball en versions per a WAF i estem fent el següent:
- Estem reintroduint la protecció contra l'ús excessiu de la CPU que vam eliminar. (Llest)
- Comprovació manual de les 3868 regles de les regles gestionades per al WAF per trobar i corregir altres casos potencials de retrocés excessiu. (Verificació completada)
- Incloem un perfil de rendiment per a totes les regles del conjunt de proves. (Esperat: 19 de juliol)
- Canvi a un motor d'expressions regulars o - ambdós ofereixen garanties de temps d'execució. (Esperat: 31 de juliol)
- Estem reescrivint el SOP per desplegar regles per etapes, com altres programaris a Cloudflare, però al mateix temps tenim la capacitat d'emergència al desplegament global si els atacs ja han començat.
- Estem desenvolupant la capacitat d'eliminar urgentment el tauler i l'API de Cloudflare de la regió de Cloudflare.
- Automatització de les actualitzacions de pàgines .
A llarg termini ens estem allunyant del Lua WAF que vaig escriure fa uns anys. S'està movent WAF a . D'aquesta manera, el WAF serà més ràpid i rebrà un nivell addicional de protecció.
Conclusió
Aquesta fallada va causar problemes a nosaltres i als nostres clients. Hem actuat ràpidament per corregir la situació i ara estem treballant en els defectes dels processos que van causar l'accident, a més d'aprofundir encara més per protegir-nos dels possibles problemes amb les expressions regulars en el futur en migrar a la nova tecnologia.
Ens fa molta vergonya aquesta interrupció i demanem disculpes als nostres clients. Esperem que aquests canvis garanteixin que alguna cosa com això no torni a passar.
Aplicació. Retrocés d'expressions regulars
Per entendre com l'expressió:
(?:(?:"|'|]|}||d
(?:nan|infinity|true|false|null|undefined|symbol|math)|`|-
|+)+[)]*;?((?:s|-|~|!|{}||||+)*.*(?:.*=.*)))consumint tots els recursos de la CPU, necessiteu saber una mica sobre com funciona el motor d'expressions regulars estàndard. El problema aquí és el patró .*(?:.*=.*). (?: i corresponent ) és un grup no capturador (és a dir, l'expressió entre parèntesis s'agrupa com una única expressió).
En el context d'un consum excessiu de CPU, aquest patró es pot descriure com .*.*=.*. En aquesta forma, el patró sembla innecessàriament complex. Però el que és més important, al món real, les expressions (com les expressions complexes a les regles WAF) que demanen al motor que coincideixi amb un fragment seguit d'un altre fragment poden provocar un retrocés catastròfic. I per això.
En expressió regular . significa que has de fer coincidir un personatge, .* - coincideix amb zero o més caràcters "avarícia", és a dir, capturant un màxim de caràcters, de manera que .*.*=.* significa que coincideix amb zero o més caràcters, després coincideix amb zero o més caràcters, cerca el literal = caràcter, coincideix amb zero o més caràcters.
Prenem la línia de prova x=x. Correspon a l'expressió .*.*=.*. .*.* abans que el signe igual coincideixi amb el primer x (un dels grups .* correspon x, i el segon - zero caràcters). .* després = darrers partits x.
Aquesta comparació requereix 23 passos. Primer grup .* в .*.*=.* actua amb avaricia i coincideix amb tota la cadena x=x. El motor passa al següent grup .*. No tenim més personatges per coincidir, així que el segon grup .* coincideix amb zero caràcters (això està permès). Aleshores el motor es mou cap al senyal =. No hi ha més símbols (primer grup .* utilitza tota l'expressió x=x), no es produeix cap comparació.
I llavors el motor d'expressions regulars torna al principi. Passa al primer grup .* i ho compara с x= (en lloc de x=x), i després s'enfronta al segon grup .*. Segon grup .* es compara amb la segona x, i de nou no ens queden cap personatge. I quan el motor torni a arribar = в .*.*=.*, no funciona res. I torna a fer marxa enrere.
Aquesta vegada el grup .* encara coincideixen x=, però el segon grup .* no més x, i zero caràcters. El motor està intentant trobar un caràcter literal = en el patró .*.*=.*, però no surt (al cap i a la fi, el primer grup ja l'ha ocupat .*). I torna a fer marxa enrere.
Aquesta vegada el primer grup .* només pren la primera x. Però el segon grup .* captura "avarícia". =x. Ja has endevinat què passarà? El motor intenta coincidir amb el literal =, falla i fa un altre retrocés.
El primer grup de .* encara coincideix amb el primer x... El segon .* només pren =. Per descomptat, el motor no pot coincidir amb el literal =, perquè el segon grup ja ho ha fet .*. I de nou enrere. I estem intentant fer coincidir una cadena de tres caràcters!
Com a resultat, el primer grup .* coincideix només amb el primer x, segon .* - amb zero caràcters, i el motor finalment coincideix amb el literal = en expressió с = en linia. El següent és l'últim grup .* es compara amb l'última x.
23 passos només per x=x. Mira un vídeo breu sobre l'ús de Perl , que mostra com es produeixen els passos i el retrocés.
Això ja és molta feina, però i si en canvi x=x tindrem x=xx? Això són 33 passos. I si x=xxx? 45. La relació no és lineal. El gràfic mostra una comparació a partir de x=x до x=xxxxxxxxxxxxxxxxxxxx (20 x després =). Si tenim 20 x després =, el motor completa la combinació en 555 passos! (A més, si hem perdut x= i la cadena consta simplement de 20 x, el motor farà 4067 passos per entendre que no hi ha coincidències).
Aquest vídeo mostra tota la marxa enrere per a la comparació x=xxxxxxxxxxxxxxxxxxxx:
El problema és que a mesura que augmenta la mida de la corda, el temps de concordança creix de manera súper lineal. Però les coses poden empitjorar encara si l'expressió regular es modifica lleugerament. Diguem que en teníem .*.*=.*; (és a dir, hi havia un punt i coma literal al final del patró). Per exemple, per fer coincidir una expressió com foo=bar;.
I aquí fer marxa enrere seria un autèntic desastre. Per comparació x=x caldrà 90 passos, no 23. I aquesta xifra està creixent ràpidament. Per comparar x= i 20 x, calen 5353 passos. Aquí teniu el gràfic. Observa els valors dels eixos Y comparat amb el gràfic anterior.
Si esteu interessats, consulteu els 5353 passos coincidents fallits x=xxxxxxxxxxxxxxxxxxxx и .*.*=.*;
Mitjançant l'ús de la concordança mandrosa en lloc de cobdiciosa, es pot controlar l'abast del retrocés. Si canviem l'expressió original per .*?.*?=.*?, per comparació x=x caldrà 11 passos (no 23). Pel que fa a x=xxxxxxxxxxxxxxxxxxxx... Tot perquè ? després .* diu al motor que coincideixi amb un nombre mínim de caràcters abans de continuar.
Però els mapes mandrosos no resolen completament el problema de retrocés. Si substituïm l'exemple catastròfic .*.*=.*; en .*?.*?=.*?;, el temps d'execució continuarà sent el mateix. x=x encara requereix 555 passos, i x= i 20 x - 5353.
L'únic que es pot fer (a més de reescriure completament el patró per a una major especificitat) és abandonar el motor d'expressions regulars amb el seu mecanisme de retrocés. Això és el que farem durant les properes setmanes.
La solució a aquest problema es coneix des del 1968, quan Kent Thompson va escriure un article ("Mètodes de programació: algorisme de cerca d'expressions regulars"). L'article descriu un mecanisme que permet convertir una expressió regular en màquines d'estats finits no deterministes i, després dels canvis d'estat en màquines d'estats finits no deterministes, utilitzar un algorisme el temps d'execució del qual depèn linealment de la cadena coincident.
Mètodes de programació
Algorisme de cerca d'expressions regulars
Ken Thompson
Bell Telephone Laboratories, Inc., Murray Hill, Nova JerseyDescriu un mètode per cercar una cadena específica de caràcters al text i discuteix la implementació d'aquest mètode en forma de compilador. El compilador pren l'expressió regular com a codi font i produeix el programa IBM 7094 com a codi objecte. El programa d'objectes pren l'entrada en forma de text de cerca i emet un senyal cada vegada que una cadena de text coincideix amb una expressió regular determinada. L'article ofereix exemples, problemes i solucions.
Algorisme
Els algorismes de cerca anteriors donaven com a resultat un retrocés si una cerca parcialment reeixida no produïa un resultat.En el mode de compilació, l'algorisme no funciona amb símbols. Passa instruccions al codi compilat. L'execució és molt ràpida: després de passar dades a la part superior de la llista actual, cerca automàticament tots els caràcters consecutius possibles a l'expressió regular.
L'algorisme de compilació i cerca s'inclou a l'editor de text de temps compartit com a cerca contextual. Per descomptat, aquesta és lluny de ser l'única aplicació d'aquest procediment de cerca. Per exemple, una variant d'aquest algorisme s'utilitza com a cerca de símbols en una taula en assemblador.
Se suposa que el lector està familiaritzat amb les expressions regulars i el llenguatge de programació informàtic IBM 7094.Compilador
El compilador consta de tres etapes que funcionen en paral·lel. La primera etapa és el filtratge de sintaxi, que només permet que passin expressions regulars sintàcticament correctes. Aquest pas també insereix l'operador "·" per fer coincidir les expressions regulars. En el segon pas, l'expressió regular es converteix en forma postfix. En la tercera etapa, es crea el codi objecte. Les 2 primeres etapes són òbvies, i no ens detenem en elles.
L'article de Thompson no parla de màquines d'estats finits no deterministes, però sí que explica bé l'algoritme de temps lineal i presenta un programa ALGOL-60 que genera codi de llenguatge ensamblador per a l'IBM 7094. La implementació és complicada, però la idea és molt senzilla.
camí de cerca actual. Es representa amb una icona ⊕ amb una entrada i dues sortides.
La figura 1 mostra les funcions del tercer pas de compilació quan es transforma un exemple d'expressió regular. Els tres primers caràcters de l'exemple són a, b, c, i cadascun crea una entrada de pila S[i] i un camp NNODE.NNODE al codi existent per generar l'expressió regular resultant en una única entrada de pila (vegeu la figura 5)
Així seria una expressió regular .*.*=.*, si t'ho imagines com a les imatges de l'article de Thompson.
A la Fig. 0 hi ha cinc estats a partir de 0, i 3 cicles que comencen a partir dels estats 1, 2 i 3. Aquests tres cicles corresponen a tres .* en una expressió regular. 3 ovals amb punts corresponen a un símbol. Oval amb un rètol = coincideix amb un caràcter literal =. L'estat 4 és definitiu. Si hi arribem, l'expressió regular coincideix.
Per veure com es pot utilitzar aquest diagrama d'estats per a la concordança d'expressions regulars .*.*=.*, veurem la concordança de cadenes x=x. El programa comença des de l'estat 0, tal com es mostra a la Fig. 1.
Perquè aquest algorisme funcioni, la màquina d'estats ha d'estar en diversos estats simultàniament. Una màquina finita no determinista farà totes les transicions possibles simultàniament.
Abans que tingui temps de llegir les dades d'entrada, passa als dos primers estats (1 i 2), tal com es mostra a la Fig. 2.
A la Fig. 2 mostra què passa quan mira el primer x в x=x. x pot mapar fins al punt superior, passant de l'estat 1 i tornant a l'estat 1. O bé x pot mapar fins al punt següent, passant de l'estat 2 i tornant a l'estat 2.
Després de fer coincidir el primer x в x=x encara estem als estats 1 i 2. No podem arribar a l'estat 3 o 4 perquè necessitem un caràcter literal =.
L'algoritme considera llavors = в x=x. Igual que x abans, es pot fer coincidir amb qualsevol dels dos bucles principals de l'estat 1 a l'estat 1 o de l'estat 2 a l'estat 2, però l'algorisme pot coincidir amb el literal = i passar de l'estat 2 a l'estat 3 (i immediatament 4). Això es mostra a la Fig. 3.
A continuació, l'algorisme passa a l'últim x в x=x. Des dels estats 1 i 2 són possibles les mateixes transicions cap als estats 1 i 2. Des de l'estat 3 x pot coincidir amb el punt de la dreta i tornar a l'estat 3.
En aquesta etapa, cada personatge x=x considerada, i com que hem arribat a l'estat 4, l'expressió regular coincideix amb aquesta cadena. Cada caràcter es processa una vegada, de manera que aquest algorisme és lineal en la longitud de la cadena d'entrada. I sense fer marxa enrere.
Òbviament, després d'arribar a l'estat 4 (quan l'algorisme ha coincidit x=) tota l'expressió regular coincideix i l'algorisme pot acabar sense tenir-ho en compte x.
Aquest algorisme depèn linealment de la mida de la cadena d'entrada.
Font: www.habr.com