Quasi 9 anni fa Cloudflare era una piccola azienda e io non lavoravo per essa, ero solo un cliente. Un mese dopo il lancio di Cloudflare, ho ricevuto una notifica che il mio sito web Il DNS non sembra funzionare. Cloudflare ha apportato una modifica a e c'era un DNS non funzionante.
Ho subito scritto a Matthew Prince con il titolo “Dov’è il mio DNS?” e lui mi ha risposto con una lunga risposta ricca di dettagli tecnici (), al che ho risposto:
Da: John Graham-Cumming
Data: 7 ottobre 2010, 9:14
Oggetto: Ri: Dov'è il mio DNS?
A: Matteo PrincipeBel rapporto, grazie. Chiamerò sicuramente se ci saranno problemi. Probabilmente vale la pena scrivere un post a riguardo una volta raccolte tutte le informazioni tecniche. Penso che le persone apprezzeranno una storia aperta e onesta. Soprattutto se alleghi grafici per mostrare come è cresciuto il traffico dal lancio.
Ho un buon monitoraggio sul mio sito e ricevo un SMS per ogni errore. Il monitoraggio mostra che il guasto si è verificato dalle 13:03:07 alle 14:04:12. I test vengono effettuati ogni cinque minuti.
Sono sicuro che lo capirai. Sei sicuro di non aver bisogno della tua persona in Europa? 🙂
E lui rispose:
Da: Matthew Prince
Data: 7 ottobre 2010, 9:57
Oggetto: Ri: Dov'è il mio DNS?
A: John Graham-CummingGrazie. Abbiamo risposto a tutti coloro che hanno scritto. Adesso sto andando in ufficio e scriveremo qualcosa sul blog o affiggeremo un post ufficiale sulla nostra bacheca. Sono completamente d'accordo, l'onestà è tutto.
Ora Cloudflare è un'azienda davvero grande, lavoro per essa e ora devo scrivere apertamente del nostro errore, delle sue conseguenze e delle nostre azioni.
Eventi del 2 luglio
Il 2 luglio abbiamo implementato una nuova regola nelle regole gestite per i WAF, grazie alla quale su ogni core del processore che elabora il traffico HTTP/HTTPS sulla rete Cloudflare in tutto il mondo. Miglioriamo costantemente le regole gestite per i WAF in risposta a nuove vulnerabilità e minacce. A maggio, ad esempio, ci siamo affrettati per proteggersi da una grave vulnerabilità in SharePoint. Il punto centrale del nostro WAF è la capacità di implementare regole rapidamente e a livello globale.
Sfortunatamente, l'aggiornamento di giovedì scorso conteneva un'espressione regolare che sprecava troppe risorse CPU HTTP/HTTPS nel backtracking. Di conseguenza, le nostre funzioni proxy principali, CDN e WAF hanno sofferto. Il grafico mostra che le risorse del processore per servire il traffico HTTP/HTTPS raggiungono quasi il 100% sui server della nostra rete.
Utilizzo della CPU in un punto di presenza durante un incidente
Di conseguenza, i nostri clienti (e i clienti dei nostri clienti) si sono ritrovati con una pagina di errore 502 sui domini Cloudflare. Gli errori 502 sono stati generati dai server Web front-end di Cloudflare che disponevano ancora di core liberi ma non erano in grado di comunicare con i processi che gestivano il traffico HTTP/HTTPS.
Sappiamo quanti disagi ciò ha causato ai nostri clienti. Ci vergogniamo terribilmente. E questo fallimento ci ha impedito di affrontare efficacemente l’incidente.
Se eri uno di questi clienti, probabilmente eri spaventato, arrabbiato e sconvolto. Inoltre, non abbiamo avuto un . L'elevato consumo di CPU era dovuto a una regola WAF con un'espressione regolare mal formulata che provocava un eccessivo backtracking. Ecco l'espressione colpevole: (?:(?:"|'|]|}||d|(?:nan|infinity|true|false|null|undefined|symbol|math)|`|-|+)+[)]*;?((?:s|-|~|!|{}||||+)*.*(?:.*=.*)))
Anche se questo è interessante di per sé (e ne parlerò più dettagliatamente di seguito), il servizio Cloudflare è rimasto inattivo per 27 minuti non solo a causa di una cattiva espressione regolare. Ci è voluto un po' di tempo per descrivere la sequenza degli eventi che hanno portato al fallimento, quindi siamo stati lenti a rispondere. Alla fine del post, descriverò il backtracking in un'espressione regolare e ti dirò cosa farne.
Cosa è successo
Cominciamo in ordine. Tutti gli orari qui sono in UTC.
Alle 13:42, un tecnico del team firewall ha apportato una piccola modifica alle regole di rilevamento utilizzando un processo automatico. Di conseguenza, è stato creato un ticket di richiesta di modifica. Gestiamo tali ticket tramite Jira (screenshot sotto).
Dopo 3 minuti è apparsa la prima pagina di PagerDuty che segnalava un problema con WAF. Questo è stato un test sintetico che testa la funzionalità dei WAF (ne abbiamo centinaia) al di fuori di Cloudflare per monitorare il normale funzionamento. Questo è stato immediatamente seguito da pagine di avvisi relativi al fallimento di altri test del servizio end-to-end Cloudflare, problemi di traffico globale, errori 502 diffusi e un sacco di rapporti dai nostri punti di presenza (PoP) nelle città di tutto il mondo che indicavano una mancanza delle risorse della CPU.
Ho ricevuto molti di questi avvisi, sono uscito precipitosamente da una riunione e stavo andando al tavolo quando il capo del nostro dipartimento di sviluppo delle soluzioni ha detto che avevamo perso l'80% del nostro traffico. Sono corso dai nostri ingegneri SRE, che stavano già lavorando sul problema. All'inizio pensavamo che si trattasse di una specie di attacco sconosciuto.
Gli ingegneri SRE di Cloudflare sono sparsi in tutto il mondo e monitorano la situazione 0 ore su XNUMX. In genere, questi avvisi notificano problemi locali specifici di portata limitata, vengono monitorati su dashboard interni e vengono risolti più volte al giorno. Ma queste pagine e notifiche indicavano qualcosa di veramente serio e gli ingegneri SRE hanno immediatamente dichiarato il livello di gravità PXNUMX e contattato la direzione e gli ingegneri di sistema.
In quel momento i nostri ingegneri londinesi stavano ascoltando una conferenza nell'aula magna. La conferenza dovette essere interrotta, tutti si riunirono in una grande sala conferenze e furono chiamati altri specialisti. Questo non era un tipico problema che gli SRE potevano affrontare da soli. Era urgente coinvolgere gli specialisti giusti.
Alle 14:00 abbiamo stabilito che il problema riguardava il WAF e non c'era stato alcun attacco. Il team delle prestazioni ha estratto i dati della CPU ed è diventato chiaro che la colpa era del WAF. Un altro dipendente ha confermato questa teoria utilizzando strace. Qualcun altro ha visto nei registri che si era verificato un problema con WAF. Alle 14:02, l'intero team è venuto da me quando è stato proposto di utilizzare il global kill, un meccanismo integrato in Cloudflare che spegne un componente in tutto il mondo.
Il modo in cui abbiamo effettuato l'uccisione globale per WAF è una storia diversa. Non è così semplice. Utilizziamo i nostri prodotti e il nostro servizio non ha funzionato, non siamo riusciti ad autenticarci e ad accedere al pannello di controllo interno (una volta sistemato tutto, abbiamo appreso che alcuni membri del team avevano perso l'accesso a causa di una funzionalità di sicurezza che disabilita le credenziali se il pannello di controllo interno non viene utilizzato per un a lungo).
E non potevamo accedere ai nostri servizi interni, come Jira o il sistema di build. Avevamo bisogno di un meccanismo di soluzione alternativa, che abbiamo utilizzato raramente (anche questo dovrà essere risolto). Alla fine, un ingegnere è riuscito a disabilitare il WAF alle 14:07 e alle 14:09 i livelli di traffico e CPU erano tornati alla normalità ovunque. Il resto dei meccanismi di protezione di Cloudflare hanno funzionato normalmente.
Quindi abbiamo iniziato a ripristinare il WAF. La situazione era fuori dall’ordinario, quindi abbiamo eseguito test negativi (chiedendoci se il cambiamento fosse davvero il problema) e test positivi (assicurandoci che il rollback funzionasse) in una città utilizzando traffico separato, trasferendo da lì i clienti paganti.
Alle 14:52 eravamo convinti di aver compreso il motivo, abbiamo apportato una correzione e abilitato nuovamente il WAF.
Come funziona Cloudflare
Cloudflare dispone di un team di ingegneri dedicato alla gestione delle regole per i WAF. Si sforzano di migliorare i tassi di rilevamento, ridurre i falsi positivi e rispondere rapidamente alle nuove minacce non appena emergono. Negli ultimi 60 giorni sono state elaborate 476 richieste di modifica per le regole gestite per WAF (una media di una ogni 3 ore).
Questa particolare modifica doveva essere implementata in modalità di simulazione, in cui il traffico del client reale passa attraverso la regola, ma nulla viene bloccato. Utilizziamo questa modalità per testare l'efficacia delle regole e misurare i tassi di falsi positivi e falsi negativi. Ma anche in modalità simulazione, le regole devono essere effettivamente eseguite e in questo caso la regola conteneva un'espressione regolare che consumava troppe risorse del processore.
Come puoi vedere dalla richiesta di modifica sopra, disponiamo di un piano di distribuzione, un piano di rollback e un collegamento a una procedura operativa standard interna (SOP) per questo tipo di distribuzione. La SOP per la modifica di una regola ne consente la pubblicazione a livello globale. In realtà, in Cloudflare, le cose vengono fatte in modo completamente diverso e la SOP impone di spedire prima il software per test e uso interno a un punto di presenza (PoP) interno (utilizzato dai nostri dipendenti), quindi a un piccolo numero di clienti in un luogo isolato, poi ad un gran numero di clienti, e solo dopo al mondo intero.
Questo è quello che sembra. Usiamo git internamente tramite BitBucket. Gli ingegneri che lavorano sulle modifiche inviano il codice, che viene creato a TeamCity, e quando la build passa, vengono assegnati i revisori. Una volta approvata una richiesta pull, il codice viene assemblato e vengono eseguiti (di nuovo) una serie di test.
Se la compilazione e i test vengono completati correttamente, viene creata una richiesta di modifica in Jira e il manager o lead appropriato deve approvare la modifica. Dopo l'approvazione, l'implementazione avviene nel cosiddetto “serraglio PoP”: DOG, PIG e (cane, maiale e canarino).
DOG PoP è un PoP di Cloudflare (come ogni altra delle nostre città) utilizzato solo dai dipendenti di Cloudflare. Il PoP per uso interno consente di individuare i problemi prima che il traffico dei clienti inizi a confluire nella soluzione. Cosa utile.
Se il test DOG ha esito positivo, il codice passa alla fase PIG (cavia). Questo è Cloudflare PoP, dove una piccola quantità di traffico gratuito dei clienti scorre attraverso un nuovo codice.
Se tutto va bene, il codice va in Canary. Abbiamo tre PoP delle Canarie in diverse parti del mondo. In essi, il traffico dei clienti a pagamento e gratuiti passa attraverso il nuovo codice e questo è l'ultimo controllo degli errori.
Processo di rilascio del software su Cloudflare
Se il codice è ok in Canary, lo rilasciamo. Passare attraverso tutte le fasi - DOG, PIG, Canary, il mondo intero - richiede diverse ore o giorni, a seconda del cambio di codice. A causa della diversità della rete e dei clienti di Cloudflare, testiamo accuratamente il codice prima di rilasciarlo a livello globale per tutti i clienti. Ma WAF non segue specificamente questo processo perché è necessario rispondere rapidamente alle minacce.
Minacce WAF
Negli ultimi anni si è verificato un aumento significativo delle minacce nelle applicazioni comuni. Ciò è dovuto alla maggiore disponibilità di strumenti di test del software. Ad esempio, ne abbiamo scritto di recente ).
Fonte:
Molto spesso viene creata una prova di concetto e immediatamente pubblicata su Github in modo che i team che mantengono l'applicazione possano testarla rapidamente e garantire che sia adeguatamente protetta. Pertanto, Cloudflare ha bisogno della capacità di rispondere ai nuovi attacchi il più rapidamente possibile in modo che i clienti abbiano l’opportunità di riparare il proprio software.
Un ottimo esempio della risposta rapida di Cloudflare è l'implementazione delle protezioni dalle vulnerabilità di SharePoint a maggio (). Quasi immediatamente dopo l'annuncio, abbiamo notato un numero enorme di tentativi di sfruttare la vulnerabilità nelle installazioni SharePoint dei nostri clienti. I nostri ragazzi monitorano costantemente le nuove minacce e scrivono regole per proteggere i nostri clienti.
La regola che ha causato il problema giovedì avrebbe dovuto proteggere dal cross-site scripting (XSS). Negli ultimi anni tali attacchi sono diventati anche molto più frequenti.
Fonte:
La procedura standard per modificare una regola gestita per un WAF consiste nell'effettuare test di integrazione continua (CI) prima della distribuzione globale. Giovedì scorso lo abbiamo fatto e abbiamo introdotto le regole. Alle 13:31, un tecnico ha inviato una richiesta pull approvata con una modifica.
Alle 13:37 TeamCity ha raccolto le regole, ha eseguito i test e ha dato il via libera. La suite di test WAF testa le funzionalità principali del WAF e consiste in un gran numero di test unitari per le singole funzioni. Dopo i test unitari, abbiamo testato le regole per WAF utilizzando un numero enorme di richieste HTTP. Le richieste HTTP controllano quali richieste devono essere bloccate dal WAF (per intercettare l'attacco) e quali possono essere lasciate passare (per non bloccare tutto ed evitare falsi positivi). Ma non abbiamo testato l'utilizzo eccessivo della CPU e l'esame dei log delle build WAF precedenti mostra che il tempo di esecuzione del test delle regole non è aumentato ed era difficile sospettare che non ci sarebbero state risorse sufficienti.
I test sono stati superati e TeamCity ha iniziato a distribuire automaticamente la modifica alle 13:42.
Mercurio
Le regole WAF si concentrano sulla riparazione immediata delle minacce, quindi le distribuiamo utilizzando l'archivio chiave-valore distribuito di Quicksilver, che propaga le modifiche a livello globale in pochi secondi. Tutti i nostri clienti utilizzano questa tecnologia quando modificano la configurazione nella dashboard o tramite API, ed è grazie ad essa che rispondiamo ai cambiamenti alla velocità della luce.
Non abbiamo parlato molto di Quicksilver. In precedenza usavamo come negozio di valori-chiave distribuito a livello globale, ma si sono verificati problemi operativi e abbiamo scritto il nostro negozio, replicato in più di 180 città. Ora utilizziamo Quicksilver per inviare modifiche alla configurazione ai client, aggiornare le regole WAF e distribuire il codice JavaScript scritto dai client ai lavoratori Cloudflare.
Bastano pochi secondi dal clic su un pulsante su una dashboard o dal richiamo di un'API per apportare una modifica alla configurazione in tutto il mondo. I clienti hanno apprezzato questa velocità di configurazione. E Workers offre loro una distribuzione del software globale quasi istantanea. In media, Quicksilver propaga circa 350 cambiamenti al secondo.
E Quicksilver è molto veloce. In media, abbiamo raggiunto il 99° percentile di 2,29 secondi per propagare le modifiche a tutti i computer del mondo. La velocità è solitamente una buona cosa. Dopotutto, quando abiliti una funzione o svuoti la cache, ciò avviene quasi istantaneamente e ovunque. L'invio del codice tramite Cloudflare Workers avviene alla stessa velocità. Cloudflare promette ai suoi clienti aggiornamenti rapidi al momento giusto.
Ma in questo caso la velocità ci ha giocato uno scherzo crudele e le regole sono cambiate ovunque in pochi secondi. Potresti aver notato che il codice WAF utilizza Lua. Cloudflare utilizza ampiamente Lua nella produzione e nei dettagli noi . Lua WAF utilizza internamente e applica il backtracking per la corrispondenza. Non dispone di meccanismi di protezione contro le espressioni che sfuggono al controllo. Di seguito parlerò più approfonditamente di questo e di cosa stiamo facendo al riguardo.
Prima che le regole venissero implementate, tutto è andato liscio: la richiesta pull è stata creata e approvata, la pipeline CI/CD ha raccolto e testato il codice, la richiesta di modifica è stata inviata in base alla SOP che regola la distribuzione e il rollback e la distribuzione è stata completata.
Processo di distribuzione WAF di Cloudflare
Cosa è andato storto
Come ho detto, implementiamo dozzine di nuove regole WAF ogni settimana e disponiamo di molti sistemi per proteggerci dalle conseguenze negative di tale implementazione. E quando qualcosa va storto, di solito è una combinazione di diverse circostanze contemporaneamente. Se si trova un solo motivo, questo, ovviamente, è rassicurante, ma non è sempre vero. Queste sono le ragioni che insieme hanno portato al fallimento del nostro servizio HTTP/HTTPS.
- Un ingegnere ha scritto un'espressione regolare che potrebbe risultare eccessiva .
- Una funzionalità che avrebbe potuto impedire all'espressione regolare di sprecare troppa CPU è stata erroneamente rimossa durante un refactoring del WAF diverse settimane prima: il refactoring era necessario per far sì che il WAF consumasse meno risorse.
- Il motore delle espressioni regolari non aveva garanzie di complessità.
- La suite di test non è riuscita a rilevare un consumo eccessivo di CPU.
- La SOP consente di implementare a livello globale modifiche alle regole non urgenti senza un processo in più fasi.
- Il piano di rollback richiedeva l'esecuzione di una build WAF completa due volte, il che ha richiesto molto tempo.
- Il primo allarme sui problemi del traffico globale è stato lanciato troppo tardi.
- Abbiamo impiegato un po' di tempo per aggiornare la pagina di stato.
- Abbiamo avuto problemi di accesso ai sistemi a causa di un problema tecnico e la procedura di bypass non era ben definita.
- Gli ingegneri SRE hanno perso l'accesso ad alcuni sistemi perché le loro credenziali sono scadute per motivi di sicurezza.
- I nostri clienti non hanno avuto accesso al dashboard o all'API di Cloudflare perché attraversano una regione Cloudflare.
Cosa è cambiato rispetto a giovedì scorso
Innanzitutto, abbiamo interrotto completamente tutto il lavoro sui rilasci per WAF e stiamo facendo quanto segue:
- Stiamo reintroducendo la protezione dall'uso eccessivo della CPU che abbiamo rimosso. (Pronto)
- Controllare manualmente tutte le 3868 regole nelle regole gestite per il WAF per trovare e correggere altri potenziali casi di backtracking eccessivo. (Verifica completata)
- Includiamo la profilazione delle prestazioni per tutte le regole nel set di test. (Previsto: 19 luglio)
- Passaggio a un motore di espressioni regolari o - Entrambi forniscono garanzie di runtime. (Previsto: 31 luglio)
- Stiamo riscrivendo la SOP per implementare le regole in più fasi, come altri software in Cloudflare, ma allo stesso tempo avere la capacità di implementare una distribuzione globale di emergenza se gli attacchi sono già iniziati.
- Stiamo sviluppando la possibilità di rimuovere urgentemente la dashboard e l'API di Cloudflare dalla regione di Cloudflare.
- Automatizzazione degli aggiornamenti delle pagine .
A lungo termine ci stiamo allontanando dal Lua WAF che ho scritto qualche anno fa. Spostamento di WAF in . In questo modo il WAF sarà più veloce e riceverà un ulteriore livello di protezione.
conclusione
Questo fallimento ha causato problemi a noi e ai nostri clienti. Abbiamo agito rapidamente per correggere la situazione e ora stiamo lavorando sui difetti nei processi che hanno causato l'arresto anomalo, oltre a scavare ancora più a fondo per proteggerci da potenziali problemi con le espressioni regolari in futuro durante la migrazione alla nuova tecnologia.
Siamo molto imbarazzati per questa interruzione e ci scusiamo con i nostri clienti. Ci auguriamo che questi cambiamenti garantiscano che qualcosa del genere non accada più.
Applicazione. Backtracking delle espressioni regolari
Per capire come funziona l'espressione:
(?:(?:"|'|]|}||d
(?:nan|infinity|true|false|null|undefined|symbol|math)|`|-
|+)+[)]*;?((?:s|-|~|!|{}||||+)*.*(?:.*=.*)))divorato tutte le risorse della CPU, devi sapere qualcosa su come funziona il motore delle espressioni regolari standard. Il problema qui è lo schema .*(?:.*=.*). (?: e corrispondente ) è un gruppo non di acquisizione (ovvero, l'espressione tra parentesi è raggruppata come una singola espressione).
Nel contesto di un consumo eccessivo di CPU, questo modello può essere descritto come .*.*=.*. In questa forma, il modello sembra inutilmente complesso. Ma, cosa ancora più importante, nel mondo reale, le espressioni (come le espressioni complesse nelle regole WAF) che chiedono al motore di abbinare un frammento seguito da un altro frammento possono portare a un catastrofico backtracking. Ed ecco perché.
Nell'espressione regolare . significa che devi abbinare un carattere, .* - abbinare zero o più caratteri "avidamente", cioè catturando un massimo di caratteri, in modo che .*.*=.* significa corrispondere a zero o più caratteri, quindi corrispondere a zero o più caratteri, trovare il carattere letterale =, corrispondere a zero o più caratteri.
Prendiamo la linea di prova x=x. Corrisponde all'espressione .*.*=.*. .*.* prima che il segno uguale corrisponda al primo x (uno dei gruppi .* fiammiferi xe il secondo zero caratteri). .* dopo = corrisponde per ultimo x.
Questo confronto richiede 23 passaggi. Primo gruppo .* в .*.*=.* agisce avidamente e corrisponde all'intera stringa x=x. Il motore si sposta al gruppo successivo .*. Non abbiamo altri caratteri da abbinare, quindi il secondo gruppo .* corrisponde a zero caratteri (questo è consentito). Quindi il motore si sposta verso il segno =. Non ci sono più simboli (primo gruppo .* ha usato l'intera espressione x=x), non avviene alcun confronto.
E poi il motore delle espressioni regolari ritorna all'inizio. Si passa al primo gruppo .* e lo confronta с x= (invece di x=x), per poi affrontare il secondo gruppo .*. Secondo gruppo .* viene confrontato con il secondo x, e ancora una volta non ci sono più personaggi. E quando il motore raggiunge di nuovo = в .*.*=.*, non funziona niente. E torna nuovamente sui suoi passi.
Questa volta il gruppo .* corrisponde ancora x=, ma il secondo gruppo .* non più xe zero caratteri. Il motore sta cercando di trovare un carattere letterale = nel modello .*.*=.*, ma non esce (del resto il primo gruppo lo ha già occupato .*). E torna nuovamente sui suoi passi.
Questa volta il primo gruppo .* prende solo la prima x. Ma il secondo gruppo .* cattura "avidamente". =x. Hai già indovinato cosa accadrà? Il motore tenta di corrispondere al letterale =, fallisce e fa un altro backtracking.
Il primo gruppo di .* corrisponde ancora al primo x... Il secondo .* ci vuole solo =. Naturalmente, il motore non può corrispondere al letterale =, perché il secondo gruppo lo ha già fatto .*. E ancora fare marcia indietro. E stiamo cercando di abbinare una stringa di tre caratteri!
Di conseguenza, il primo gruppo .* corrisponde solo al primo xsecondo .* - con zero caratteri e il motore finalmente corrisponde al letterale = in espressione с = in linea. Il prossimo è l'ultimo gruppo .* viene confrontato con l'ultimo x.
23 passaggi solo per x=x. Guarda un breve video sull'utilizzo di Perl , che mostra come si verificano i passaggi e il backtracking.
Questo è già molto lavoro, ma cosa succederebbe se invece x=x avremo x=xx? Sono 33 passi. E se x=xxx? 45. Il rapporto non è lineare. Il grafico mostra un confronto da x=x a x=xxxxxxxxxxxxxxxxxxxx (20 x dopo =). Se abbiamo 20 x dopo =, il motore completa l'abbinamento in 555 passi! (Inoltre, se abbiamo perso x= e la stringa è composta semplicemente da 20 x, il motore impiegherà 4067 passi per capire che non ci sono corrispondenze).
Questo video mostra tutto il backtracking per il confronto x=xxxxxxxxxxxxxxxxxxxx:
Il problema è che all’aumentare della dimensione della stringa, il tempo di corrispondenza cresce in modo super-lineare. Ma le cose possono peggiorare ulteriormente se l’espressione regolare viene leggermente modificata. Diciamo che abbiamo avuto .*.*=.*; (ovvero, c'era un punto e virgola letterale alla fine del modello). Ad esempio, per abbinare un'espressione come foo=bar;.
E qui fare marcia indietro sarebbe un vero disastro. Per confronto x=x ci vorranno 90 passi, non 23. E quel numero sta crescendo rapidamente. Per confrontare x= e 20 x, sono necessari 5353 passaggi. Ecco il grafico. Guarda i valori dell'asse Y rispetto al grafico precedente.
Se sei interessato, controlla tutti i 5353 passaggi di corrispondenza non riusciti x=xxxxxxxxxxxxxxxxxxxx и .*.*=.*;
Utilizzando l'abbinamento pigro anziché avido, è possibile controllare l'entità del backtracking. Se cambiamo l'espressione originale in .*?.*?=.*?, per confronto x=x ci vorranno 11 passi (non 23). Quanto a x=xxxxxxxxxxxxxxxxxxxx... Tutto perché ? dopo .* dice al motore di abbinare un numero minimo di caratteri prima di proseguire.
Ma le mappature pigre non risolvono completamente il problema del backtracking. Se sostituiamo l’esempio catastrofico .*.*=.*; su .*?.*?=.*?;, il tempo di esecuzione rimarrà lo stesso. x=x richiede ancora 555 passaggi e x= e 20 x - 5353.
L'unica cosa che si può fare (oltre a riscrivere completamente il pattern per una maggiore specificità) è abbandonare il motore delle espressioni regolari con il suo meccanismo di backtracking. Questo è quello che faremo nelle prossime settimane.
La soluzione a questo problema è nota dal 1968, quando Kent Thompson scrisse un articolo (“Metodi di programmazione: algoritmo di ricerca delle espressioni regolari”). L'articolo descrive un meccanismo che consente di convertire un'espressione regolare in macchine a stati finiti non deterministiche e, dopo i cambiamenti di stato nelle macchine a stati finiti non deterministiche, utilizzare un algoritmo il cui tempo di esecuzione dipende linearmente dalla stringa corrispondente.
Metodi di programmazione
Algoritmo di ricerca delle espressioni regolari
Ken Thompson
Bell Telephone Laboratories, Inc., Murray Hill, New JerseyDescrive un metodo per cercare una specifica stringa di caratteri nel testo e discute l'implementazione di questo metodo in forma di compilatore. Il compilatore accetta l'espressione regolare come codice sorgente e produce il programma IBM 7094 come codice oggetto. Il programma oggetto riceve input sotto forma di testo di ricerca ed emette un segnale ogni volta che una stringa di testo viene confrontata con una determinata espressione regolare. L'articolo fornisce esempi, problemi e soluzioni.
Algoritmo
Gli algoritmi di ricerca precedenti comportavano il backtracking se una ricerca parzialmente riuscita non riusciva a produrre un risultato.In modalità compilazione, l'algoritmo non funziona con i simboli. Passa le istruzioni al codice compilato. L'esecuzione è molto veloce: dopo aver passato i dati in cima all'elenco corrente, cerca automaticamente tutti i possibili caratteri consecutivi nell'espressione regolare.
L'algoritmo di compilazione e ricerca è incluso nell'editor di testo time-sharing come ricerca contestuale. Naturalmente, questa non è l'unica applicazione di tale procedura di ricerca. Ad esempio, una variante di questo algoritmo viene utilizzata come ricerca di simboli in una tabella in assembler.
Si presuppone che il lettore abbia familiarità con le espressioni regolari e il linguaggio di programmazione per computer IBM 7094.Compilatore
Il compilatore è costituito da tre fasi eseguite in parallelo. La prima fase è il filtraggio della sintassi, che consente il passaggio solo delle espressioni regolari sintatticamente corrette. Questo passaggio inserisce anche l'operatore "·" per abbinare le espressioni regolari. Nella seconda fase, l'espressione regolare viene convertita nella forma suffissa. Nella terza fase viene creato il codice oggetto. Le prime 2 fasi sono ovvie e non ci soffermeremo su di esse.
L'articolo di Thompson non parla di macchine a stati finiti non deterministiche, ma spiega bene l'algoritmo del tempo lineare e presenta un programma ALGOL-60 che genera codice in linguaggio assembly per l'IBM 7094. L'implementazione è complicata, ma l'idea è molto semplice.
percorso di ricerca corrente. È rappresentato da un'icona ⊕ con un ingresso e due uscite.
La Figura 1 mostra le funzioni del terzo passaggio di compilazione durante la trasformazione di un esempio di espressione regolare. I primi tre caratteri nell'esempio sono a, b, c e ciascuno crea una voce nello stack S[i] e un campo NNODE.NNODE al codice esistente per generare l'espressione regolare risultante in una singola voce dello stack (vedere Figura 5)
Ecco come apparirebbe un'espressione regolare .*.*=.*, se lo immagini come nelle immagini dell'articolo di Thompson.
Nella fig. 0 ci sono cinque stati che iniziano da 0 e 3 cicli che iniziano dagli stati 1, 2 e 3. Questi tre cicli corrispondono a tre .* in un'espressione regolare. 3 ovali con punti corrispondono a un simbolo. Ovale con un segno = corrisponde a un carattere letterale =. Lo stato 4 è definitivo. Se lo raggiungiamo, l'espressione regolare viene abbinata.
Per vedere come è possibile utilizzare un diagramma di stato di questo tipo per la corrispondenza delle espressioni regolari .*.*=.*, esamineremo la corrispondenza delle stringhe x=x. Il programma parte dallo stato 0, come mostrato in Fig. 1.
Perché questo algoritmo funzioni, la macchina a stati deve trovarsi in più stati contemporaneamente. Una macchina finita non deterministica effettuerà tutte le possibili transizioni simultaneamente.
Prima che abbia il tempo di leggere i dati di input, entra in entrambi i primi stati (1 e 2), come mostrato in Fig. 2.
Nella fig. 2 mostra cosa succede quando guarda il primo x в x=x. x può mappare al punto più alto, andando dallo stato 1 e tornando allo stato 1. Oppure x può mappare al punto sottostante, passando dallo stato 2 e di nuovo allo stato 2.
Dopo aver abbinato il primo x в x=x siamo ancora negli stati 1 e 2. Non possiamo raggiungere lo stato 3 o 4 perché abbiamo bisogno di un carattere letterale =.
L'algoritmo quindi considera = в x=x. Come x prima, può essere abbinato a uno dei primi due cicli dallo stato 1 allo stato 1 o dallo stato 2 allo stato 2, ma l'algoritmo può abbinare il valore letterale = e passare dallo stato 2 allo stato 3 (e immediatamente 4). Questo è mostrato nella figura. 3.
L'algoritmo passa quindi all'ultimo x в x=x. Dagli stati 1 e 2 sono possibili le stesse transizioni agli stati 1 e 2. Dallo stato 3 x può corrispondere al punto a destra e tornare allo stato 3.
In questa fase, ogni personaggio x=x considerato e poiché abbiamo raggiunto lo stato 4, l'espressione regolare corrisponde a quella stringa. Ogni carattere viene elaborato una volta, quindi questo algoritmo è lineare nella lunghezza della stringa di input. E senza fare marcia indietro.
Ovviamente, dopo aver raggiunto lo stato 4 (quando l'algoritmo ha abbinato x=) viene soddisfatta l'intera espressione regolare e l'algoritmo potrebbe terminare senza considerarla affatto x.
Questo algoritmo dipende linearmente dalla dimensione della stringa di input.
Fonte: habr.com