Há quase 9 anos, a Cloudflare era uma empresa minúscula e eu não trabalhava para ela, era apenas um cliente. Um mês após o lançamento da Cloudflare, recebi uma notificação de que meu site O DNS não parece estar funcionando. Cloudflare fez uma mudança em , e houve um DNS quebrado.
Escrevi imediatamente para Matthew Prince com o título “Onde está meu DNS?” e ele respondeu uma longa resposta cheia de detalhes técnicos (), ao que respondi:
De: John Graham-Cumming
Data: 7 de outubro de 2010, 9h14
Assunto: Re: Onde está meu DNS?
Para: Matthew PrinceRelatório legal, obrigado. Com certeza ligarei se houver problemas. Provavelmente vale a pena escrever um post sobre isso depois de coletar todas as informações técnicas. Acho que as pessoas vão gostar de uma história aberta e honesta. Especialmente se você anexar gráficos para mostrar como o tráfego cresceu desde o lançamento.
Tenho um bom monitoramento em meu site e recebo um SMS sobre cada falha. O monitoramento mostra que a falha ocorreu das 13h03:07 às 14h04:12. Os testes são realizados a cada cinco minutos.
Tenho certeza que você vai descobrir. Tem certeza de que não precisa de sua própria pessoa na Europa? 🙂
E ele respondeu:
De: Mateus Príncipe
Data: 7 de outubro de 2010, 9h57
Assunto: Re: Onde está meu DNS?
Para: John Graham-CummingObrigado. Respondemos a todos que escreveram. Estou a caminho do escritório agora e escreveremos algo no blog ou afixaremos uma postagem oficial em nosso quadro de avisos. Concordo plenamente, honestidade é tudo.
Agora a Cloudflare é uma empresa realmente grande, eu trabalho para ela e agora tenho que escrever abertamente sobre nosso erro, suas consequências e nossas ações.
Eventos de 2 de julho
No dia 2 de julho, lançamos uma nova regra em Regras Gerenciadas para WAFs devido à qual em cada núcleo do processador processando tráfego HTTP/HTTPS na rede Cloudflare em todo o mundo. Estamos constantemente melhorando as regras gerenciadas para WAFs em resposta a novas vulnerabilidades e ameaças. Em maio, por exemplo, corremos para se proteger contra uma vulnerabilidade grave no SharePoint. O objetivo principal do nosso WAF é a capacidade de implantar regras de forma rápida e global.
Infelizmente, a atualização da última quinta-feira continha uma expressão regular que desperdiçava muitos recursos da CPU HTTP/HTTPS no retrocesso. Como resultado, nossas funções principais de proxy, CDN e WAF sofreram. O gráfico mostra que os recursos do processador para atender o tráfego HTTP/HTTPS atingem quase 100% nos servidores da nossa rede.
Uso da CPU em um ponto de presença durante um incidente
Como resultado, nossos clientes (e os clientes de nossos clientes) acabaram com uma página de erro 502 nos domínios Cloudflare. Erros 502 foram gerados por servidores web front-end da Cloudflare que ainda tinham núcleos livres, mas não conseguiam se comunicar com processos que lidavam com tráfego HTTP/HTTPS.
Sabemos o quanto isso tem causado transtorno aos nossos clientes. Estamos terrivelmente envergonhados. E esta falha impediu-nos de lidar eficazmente com o incidente.
Se você fosse um desses clientes, provavelmente estava assustado, irritado e chateado. Além disso, não tivemos um . O alto consumo de CPU ocorreu devido a uma regra WAF com uma expressão regular mal formulada que resultou em retrocesso excessivo. Aqui está a expressão culpada: (?:(?:"|'|]|}||d|(?:nan|infinity|true|false|null|undefined|symbol|math)|`|-|+)+[)]*;?((?:s|-|~|!|{}||||+)*.*(?:.*=.*)))
Embora isso seja interessante por si só (e falarei sobre isso com mais detalhes abaixo), o serviço Cloudflare ficou fora do ar por 27 minutos, não apenas por causa de uma expressão regular incorreta. Demorou um pouco para descrever a sequência de eventos que levaram ao fracasso, por isso demoramos a responder. No final do post, descreverei o retrocesso em uma expressão regular e direi o que fazer com ele.
O que aconteceu
Vamos começar em ordem. Todos os horários aqui estão em UTC.
Às 13h42, um engenheiro da equipe de firewall fez uma pequena alteração nas regras de detecção usando um processo automático. Dessa forma, foi criado um ticket de solicitação de alteração. Gerenciamos esses tickets por meio do Jira (captura de tela abaixo).
Após 3 minutos, a primeira página do PagerDuty apareceu, relatando um problema com o WAF. Este foi um teste sintético que testa a funcionalidade dos WAFs (temos centenas deles) fora da Cloudflare para monitorar a operação normal. Isso foi imediatamente seguido por páginas de alertas sobre falhas em outros testes de serviço ponta a ponta da Cloudflare, problemas de tráfego global, erros 502 generalizados e uma tonelada de relatórios de nossos pontos de presença (PoP) em cidades ao redor do mundo que indicavam uma falta de recursos da CPU.
Recebi vários desses alertas, saí furioso de uma reunião e estava a caminho da mesa quando o chefe do nosso departamento de desenvolvimento de soluções disse que havíamos perdido 80% do nosso tráfego. Corri para nossos engenheiros do SRE, que já estavam trabalhando no problema. A princípio pensamos que era algum tipo de ataque desconhecido.
Os engenheiros de SRE da Cloudflare estão espalhados pelo mundo e monitoram a situação 0 horas por dia. Normalmente, esses alertas notificam você sobre problemas locais específicos de escopo limitado, são rastreados em painéis internos e resolvidos várias vezes por dia. Mas essas páginas e notificações indicavam algo realmente sério, e os engenheiros do SRE declararam imediatamente o nível de gravidade PXNUMX e contataram os engenheiros de gestão e de sistema.
Nossos engenheiros londrinos estavam ouvindo uma palestra no salão principal naquele momento. A palestra teve que ser interrompida, todos se reuniram em uma grande sala de conferências e mais especialistas foram chamados. Este não era um problema típico que os SREs pudessem resolver sozinhos. Era urgente envolver os especialistas certos.
Às 14h determinamos que o problema era com o WAF e não houve ataque. A equipe de desempenho extraiu os dados da CPU e ficou claro que a culpa era do WAF. Outro funcionário confirmou essa teoria usando strace. Outra pessoa viu nos logs que havia um problema com o WAF. Às 00h14, toda a equipe me procurou quando foi proposto o uso do global kill, um mecanismo integrado ao Cloudflare que desliga um componente em todo o mundo.
Como matamos globalmente o WAF é uma história diferente. Não é assim tão simples. Usamos nossos próprios produtos e, como nosso serviço não funcionou, não conseguimos autenticar e fazer login no painel de controle interno (quando tudo foi consertado, descobrimos que alguns membros da equipe perderam o acesso devido a um recurso de segurança que desativa credenciais se o painel de controle interno não for usado por um muito tempo).
E não conseguimos acessar nossos serviços internos, como Jira ou o sistema de compilação. Precisávamos de um mecanismo de solução alternativa, que usávamos com pouca frequência (isso também precisará ser resolvido). Finalmente, um engenheiro conseguiu desativar o WAF às 14h07 e, às 14h09, o tráfego e os níveis de CPU voltaram ao normal em todos os lugares. Os demais mecanismos de proteção da Cloudflare funcionaram normalmente.
Então começamos a restaurar o WAF. A situação estava fora do comum, então realizamos testes negativos (perguntando-nos se a mudança era realmente o problema) e testes positivos (certificando-nos de que a reversão funcionou) em uma cidade usando tráfego separado, transferindo clientes pagantes de lá.
Às 14h52 estávamos convencidos de que entendíamos o motivo e fizemos uma correção, e habilitamos o WAF novamente.
Como funciona o Cloudflare
A Cloudflare possui uma equipe de engenheiros dedicada ao gerenciamento de regras para WAFs. Eles se esforçam para melhorar as taxas de detecção, reduzir falsos positivos e responder rapidamente a novas ameaças à medida que surgem. Nos últimos 60 dias, foram processadas 476 solicitações de alteração de regras gerenciadas para WAF (uma média de uma a cada 3 horas).
Essa mudança específica precisava ser implantada em modo de simulação, onde o tráfego real do cliente passa pela regra, mas nada é bloqueado. Usamos este modo para testar a eficácia das regras e medir as taxas de falsos positivos e falsos negativos. Mas mesmo no modo de simulação, as regras devem realmente ser executadas e, neste caso, a regra continha uma expressão regular que estava consumindo muitos recursos do processador.
Como você pode ver na solicitação de mudança acima, temos um plano de implantação, um plano de reversão e um link para um procedimento operacional padrão (SOP) interno para esse tipo de implantação. O POP para alteração de uma regra permite que ela seja publicada globalmente. Na verdade, na Cloudflare, as coisas são feitas de forma completamente diferente, e o SOP determina que primeiro enviemos o software para teste e uso interno para um ponto de presença interno (PoP) (que nossos funcionários usam), depois para um pequeno número de clientes em um local isolado, depois para um grande número de clientes e só então para o mundo inteiro.
Isto é o que parece. Usamos git internamente via BitBucket. Os engenheiros que trabalham nas alterações enviam o código, que é montado no TeamCity, e quando a construção é aprovada, os revisores são designados. Depois que uma solicitação pull é aprovada, o código é montado e uma série de testes é executada (novamente).
Se a compilação e os testes forem concluídos com êxito, uma solicitação de alteração será criada no Jira e o gerente ou líder apropriado deverá aprovar a alteração. Após a aprovação, a implantação ocorre no chamado “zoológico PoP”: DOG, PIG e (cachorro, porco e canário).
DOG PoP é um PoP da Cloudflare (como qualquer outra de nossas cidades) usado apenas por funcionários da Cloudflare. O PoP para uso interno permite detectar problemas antes que o tráfego do cliente comece a fluir para a solução. Coisa útil.
Se o teste DOG for bem-sucedido, o código passa para o estágio PIG (cobaia). Este é o Cloudflare PoP, onde uma pequena quantidade de tráfego gratuito do cliente flui através de um novo código.
Se tudo estiver bem, o código vai para o Canary. Temos três PoPs Canárias em diferentes partes do mundo. Neles, o tráfego de clientes pagos e gratuitos passa pelo novo código, sendo esta a última verificação de erros.
Processo de lançamento de software na Cloudflare
Se o código estiver ok no Canary, nós o liberamos. Passar por todas as etapas - DOG, PIG, Canary, o mundo inteiro - leva várias horas ou dias, dependendo da mudança de código. Devido à diversidade da rede e dos clientes da Cloudflare, testamos exaustivamente o código antes de lançá-lo globalmente para todos os clientes. Mas o WAF não segue especificamente esse processo porque as ameaças precisam ser respondidas rapidamente.
Ameaças WAF
Nos últimos anos, houve um aumento significativo de ameaças em aplicações comuns. Isso se deve à maior disponibilidade de ferramentas de teste de software. Por exemplo, escrevemos recentemente sobre ).
Fonte:
Muitas vezes, uma prova de conceito é criada e publicada imediatamente no Github para que as equipes que mantêm o aplicativo possam testá-lo rapidamente e garantir que ele esteja adequadamente protegido. Portanto, a Cloudflare precisa ser capaz de responder a novos ataques o mais rápido possível para que os clientes tenham a oportunidade de consertar seus softwares.
Um ótimo exemplo da resposta rápida da Cloudflare é a implantação de proteções contra vulnerabilidades do SharePoint em maio (). Quase imediatamente após os anúncios terem sido feitos, notámos um grande número de tentativas de explorar a vulnerabilidade nas instalações do SharePoint dos nossos clientes. Nossos funcionários estão constantemente monitorando novas ameaças e redigindo regras para proteger nossos clientes.
A regra que causou o problema na quinta-feira deveria proteger contra cross-site scripting (XSS). Tais ataques também se tornaram muito mais frequentes nos últimos anos.
Fonte:
O procedimento padrão para alterar uma regra gerenciada para um WAF é realizar testes de integração contínua (CI) antes da implantação global. Na quinta-feira passada fizemos isso e implementamos as regras. Às 13h31, um engenheiro enviou uma solicitação pull aprovada com uma alteração.
Às 13h37 o TeamCity coletou as regras, fez testes e deu sinal verde. O conjunto de testes WAF testa a funcionalidade principal do WAF e consiste em um grande número de testes unitários para funções individuais. Após testes unitários, testamos as regras do WAF usando um grande número de solicitações HTTP. As solicitações HTTP verificam quais solicitações devem ser bloqueadas pelo WAF (para interceptar o ataque) e quais podem ser permitidas (para não bloquear tudo e evitar falsos positivos). Mas não testamos o uso excessivo da CPU e o exame dos logs de compilações anteriores do WAF mostra que o tempo de execução do teste de regras não aumentou e era difícil suspeitar que não haveria recursos suficientes.
Os testes foram aprovados e o TeamCity começou a implantar automaticamente a mudança às 13h42.
Mercúrio
As regras do WAF se concentram na correção imediata de ameaças, por isso as implantamos usando o armazenamento distribuído de valores-chave do Quicksilver, que propaga alterações globalmente em segundos. Todos os nossos clientes utilizam esta tecnologia quando alteram a configuração no dashboard ou via API, e é graças a ela que respondemos às mudanças na velocidade da luz.
Não falamos muito sobre Mercúrio. Anteriormente usávamos como um armazenamento de valores-chave distribuído globalmente, mas houve problemas operacionais com ele, e criamos nosso próprio armazenamento, replicado em mais de 180 cidades. Agora usamos o Quicksilver para enviar alterações de configuração aos clientes, atualizar regras WAF e distribuir código JavaScript escrito por clientes para trabalhadores da Cloudflare.
Leva apenas alguns segundos, desde clicar em um botão em um painel ou chamar uma API, até fazer uma alteração na configuração em todo o mundo. Os clientes adoraram essa velocidade de configuração. E o Workers oferece implantação global de software quase instantânea. Em média, o Quicksilver propaga cerca de 350 alterações por segundo.
E o Mercúrio é muito rápido. Em média, atingimos o percentil 99 de 2,29 segundos para propagar alterações para todos os computadores em todo o mundo. A velocidade geralmente é uma coisa boa. Afinal, quando você habilita uma função ou limpa o cache, isso acontece quase que instantaneamente e em qualquer lugar. O envio de código por meio do Cloudflare Workers ocorre na mesma velocidade. A Cloudflare promete aos seus clientes atualizações rápidas na hora certa.
Mas, neste caso, a velocidade nos pregou uma peça cruel e as regras mudaram em todos os lugares em questão de segundos. Você deve ter notado que o código WAF usa Lua. Cloudflare usa Lua extensivamente em produção e detalhes nós . Lua WAF usa internamente e aplica retrocesso para correspondência. Não possui mecanismos de proteção contra expressões que fogem ao controle. Abaixo falarei mais sobre isso e o que estamos fazendo a respeito.
Antes da implantação das regras, tudo correu bem: a solicitação pull foi criada e aprovada, o pipeline de CI/CD coletou e testou o código, a solicitação de mudança foi enviada de acordo com o SOP que rege a implantação e reversão, e a implantação foi concluída.
Processo de implantação do Cloudflare WAF
O que deu errado
Como eu disse, implantamos dezenas de novas regras do WAF todas as semanas e temos muitos sistemas em funcionamento para proteção contra as consequências negativas de tal implantação. E quando algo dá errado, geralmente é uma combinação de várias circunstâncias ao mesmo tempo. Se você encontrar apenas um motivo, isso, é claro, será reconfortante, mas nem sempre é verdade. Estas são as razões que juntas levaram ao fracasso do nosso serviço HTTP/HTTPS.
- Um engenheiro escreveu uma expressão regular que pode resultar em excesso .
- Um recurso que poderia ter evitado que a expressão regular desperdiçasse muita CPU foi removido por engano em uma refatoração do WAF várias semanas antes – a refatoração foi necessária para fazer o WAF consumir menos recursos.
- O mecanismo de expressões regulares não tinha garantias de complexidade.
- O conjunto de testes não conseguiu detectar o consumo excessivo de CPU.
- O SOP permite que alterações de regras não urgentes sejam implementadas globalmente sem um processo de várias etapas.
- O plano de reversão exigia a execução completa do WAF duas vezes, o que demorava muito.
- O primeiro alerta sobre problemas de tráfego global foi acionado tarde demais.
- Demoramos um pouco para atualizar a página de status.
- Tivemos problemas para acessar os sistemas devido a uma falha e o procedimento de bypass não estava bem estabelecido.
- Os engenheiros do SRE perderam acesso a alguns sistemas porque suas credenciais expiraram por motivos de segurança.
- Nossos clientes não tinham acesso ao painel ou API da Cloudflare porque passam por uma região da Cloudflare.
O que mudou desde quinta-feira passada
Primeiro, paramos completamente todo o trabalho nos lançamentos do WAF e estamos fazendo o seguinte:
- Estamos reintroduzindo a proteção contra uso excessivo da CPU que removemos. (Preparar)
- Verificação manual de todas as 3868 regras nas regras gerenciadas do WAF para encontrar e corrigir outros casos potenciais de retrocesso excessivo. (Verificação concluída)
- Incluímos perfis de desempenho para todas as regras no conjunto de testes. (Previsto: 19 de julho)
- Mudando para um mecanismo de expressão regular ou - ambos fornecem garantias de tempo de execução. (Previsto: 31 de julho)
- Estamos reescrevendo o SOP para implantar regras em etapas, como outros softwares na Cloudflare, mas ao mesmo tempo ter a capacidade de implantação global de emergência caso os ataques já tenham começado.
- Estamos desenvolvendo a capacidade de remover urgentemente o painel e a API da Cloudflare da região da Cloudflare.
- Automatizando atualizações de página .
A longo prazo, estamos nos afastando do Lua WAF que escrevi há alguns anos. Movendo WAF para . Desta forma o WAF será mais rápido e receberá um nível adicional de proteção.
Conclusão
Essa falha causou problemas para nós e nossos clientes. Agimos rapidamente para corrigir a situação e agora estamos trabalhando nas falhas nos processos que causaram a falha, além de nos aprofundarmos ainda mais para nos proteger contra possíveis problemas com expressões regulares no futuro, ao migrar para uma nova tecnologia.
Estamos muito envergonhados com esta interrupção e pedimos desculpas aos nossos clientes. Esperamos que essas mudanças garantam que algo assim não aconteça novamente.
Aplicativo. Retrocedendo expressões regulares
Para entender como funciona a expressão:
(?:(?:"|'|]|}||d
(?:nan|infinity|true|false|null|undefined|symbol|math)|`|-
|+)+[)]*;?((?:s|-|~|!|{}||||+)*.*(?:.*=.*)))consumiu todos os recursos da CPU, você precisa saber um pouco sobre como funciona o mecanismo de expressão regular padrão. O problema aqui é o padrão .*(?:.*=.*). (?: e correspondente ) é um grupo sem captura (ou seja, a expressão entre parênteses é agrupada como uma única expressão).
No contexto de consumo excessivo de CPU, esse padrão pode ser descrito como .*.*=.*. Nesta forma, o padrão parece desnecessariamente complexo. Mas o mais importante é que, no mundo real, expressões (como expressões complexas nas regras do WAF) que solicitam ao mecanismo que corresponda a um fragmento seguido por outro fragmento podem levar a um retrocesso catastrófico. E é por causa disso.
Em expressão regular . significa que você precisa combinar um caractere, .* - combinar zero ou mais caracteres "avidamente", ou seja, capturando o máximo de caracteres, para que .*.*=.* significa combinar zero ou mais caracteres, então combinar zero ou mais caracteres, encontrar o literal = caractere, combinar zero ou mais caracteres.
Vamos pegar a linha de teste x=x. Corresponde à expressão .*.*=.*. .*.* antes que o sinal de igual corresponda ao primeiro x (um dos grupos .* соответствует x, e o segundo - zero caracteres). .* depois = últimas partidas x.
Esta comparação requer 23 etapas. Primeiro grupo .* в .*.*=.* age avidamente e corresponde a toda a string x=x. O motor passa para o próximo grupo .*. Não temos mais personagens para combinar, então o segundo grupo .* corresponde a zero caracteres (isso é permitido). Então o motor se move para o sinal =. Não há mais símbolos (primeiro grupo .* usei toda a expressão x=x), nenhuma comparação ocorre.
E então o mecanismo de expressões regulares retorna ao início. Ele passa para o primeiro grupo .* e compara с x= (em vez de x=x), e então assume o segundo grupo .*. Segundo grupo .* é comparado com o segundo x, e novamente não temos mais caracteres. E quando o motor chegar novamente = в .*.*=.*, nada funciona. E ele recua novamente.
Desta vez o grupo .* ainda corresponde x=, mas o segundo grupo .* não mais xe zero caracteres. O mecanismo está tentando encontrar um caractere literal = no padrão .*.*=.*, mas não sai (afinal, o primeiro grupo já o ocupou .*). E ele recua novamente.
Desta vez o primeiro grupo .* leva apenas o primeiro x. Mas o segundo grupo .* captura "avidamente" =x. Você já adivinhou o que vai acontecer? O mecanismo tenta corresponder ao literal =, falha e faz outro retrocesso.
O primeiro grupo de .* ainda corresponde ao primeiro x... O segundo .* só leva =. Claro, o mecanismo não pode corresponder ao literal =, porque o segundo grupo já fez isso .*. E novamente retrocedendo. E estamos tentando combinar uma sequência de três caracteres!
Como resultado, o primeiro grupo .* corresponde apenas ao primeiro xsegundo .* - com zero caracteres, e o mecanismo finalmente corresponde ao literal = em expressão с = em linha. O próximo é o último grupo .* é comparado com o último x.
23 etapas apenas para x=x. Assista a um pequeno vídeo sobre como usar Perl , que mostra como ocorrem as etapas e o retrocesso.
Isso já dá muito trabalho, mas e se em vez disso x=x nós teremos x=xx? São 33 passos. E se x=xxx? 45. A relação não é linear. O gráfico mostra uma comparação de x=x para x=xxxxxxxxxxxxxxxxxxxx (20 x depois =). Se tivermos 20 x depois =, o mecanismo completa a correspondência em 555 etapas! (Além disso, se perdemos x= e a string consiste simplesmente em 20 x, o mecanismo executará 4067 etapas para entender que não há correspondências).
Este vídeo mostra todos os retrocessos para comparação x=xxxxxxxxxxxxxxxxxxxx:
O problema é que à medida que o tamanho da string aumenta, o tempo de correspondência aumenta de forma superlinear. Mas as coisas podem ficar ainda piores se a expressão regular for ligeiramente modificada. Digamos que tivemos .*.*=.*; (ou seja, havia um ponto e vírgula literal no final do padrão). Por exemplo, para corresponder a uma expressão como foo=bar;.
E aqui voltar atrás seria um verdadeiro desastre. Para comparação x=x serão necessários 90 passos, não 23. E esse número está crescendo rapidamente. Comparar x= e 20 x, são necessárias 5353 etapas. Aqui está o gráfico. Veja os valores do eixo Y comparado ao gráfico anterior.
Se você estiver interessado, confira todas as 5353 etapas de correspondência com falha x=xxxxxxxxxxxxxxxxxxxx и .*.*=.*;
Usando correspondência preguiçosa em vez de gananciosa, a extensão do retrocesso pode ser controlada. Se mudarmos a expressão original para .*?.*?=.*?, para comparação x=x serão necessários 11 passos (não 23). Quanto a x=xxxxxxxxxxxxxxxxxxxx... Tudo porque ? depois .* diz ao mecanismo para corresponder a um número mínimo de caracteres antes de prosseguir.
Mas os mapeamentos preguiçosos não resolvem completamente o problema do retrocesso. Se substituirmos o exemplo catastrófico .*.*=.*; em .*?.*?=.*?;, o tempo de execução permanecerá o mesmo. x=x ainda requer 555 passos, e x= e 20 x - 5353.
A única coisa que pode ser feita (além de reescrever completamente o padrão para maior especificidade) é abandonar o mecanismo de expressão regular com seu mecanismo de retrocesso. É isso que faremos nas próximas semanas.
A solução para este problema é conhecida desde 1968, quando Kent Thompson escreveu um artigo (“Métodos de Programação: Algoritmo de Pesquisa de Expressão Regular”). O artigo descreve um mecanismo que permite converter uma expressão regular em máquinas de estados finitos não determinísticos e, após mudanças de estado em máquinas de estados finitos não determinísticos, usar um algoritmo cujo tempo de execução depende linearmente da string correspondente.
Métodos de programação
Algoritmo de pesquisa de expressão regular
Ken Thompson
Bell Telephone Laboratories, Inc., Murray Hill, Nova JerseyEle descreve um método para procurar uma sequência específica de caracteres no texto e discute a implementação desse método na forma de compilador. O compilador utiliza a expressão regular como código-fonte e produz o programa IBM 7094 como código-objeto. O programa objeto recebe a entrada na forma de texto de pesquisa e emite um sinal cada vez que uma sequência de texto é comparada com uma determinada expressão regular. O artigo fornece exemplos, problemas e soluções.
Algoritmo
Os algoritmos de pesquisa anteriores resultavam em retrocesso se uma pesquisa parcialmente bem-sucedida não produzisse um resultado.No modo de compilação, o algoritmo não funciona com símbolos. Ele passa instruções para o código compilado. A execução é muito rápida - após passar os dados para o topo da lista atual, ele procura automaticamente todos os caracteres consecutivos possíveis na expressão regular.
O algoritmo de compilação e pesquisa está incluído no editor de texto de compartilhamento de tempo como pesquisa contextual. É claro que esta está longe de ser a única aplicação de tal procedimento de pesquisa. Por exemplo, uma variante deste algoritmo é usada como uma pesquisa de símbolos em uma tabela em assembler.
Presume-se que o leitor esteja familiarizado com expressões regulares e com a linguagem de programação de computador IBM 7094.Compilador
O compilador consiste em três estágios executados em paralelo. O primeiro estágio é a filtragem de sintaxe, que permite a passagem apenas de expressões regulares sintaticamente corretas. Esta etapa também insere o operador "·" para corresponder às expressões regulares. Na segunda etapa, a expressão regular é convertida para o formato postfix. Na terceira etapa, o código objeto é criado. Os primeiros 2 estágios são óbvios e não vamos nos alongar sobre eles.
O artigo de Thompson não fala sobre máquinas de estados finitos não determinísticos, mas explica bem o algoritmo de tempo linear e apresenta um programa ALGOL-60 que gera código em linguagem assembly para o IBM 7094. A implementação é complicada, mas a ideia é muito simples.
caminho de pesquisa atual. É representado por um ícone ⊕ com uma entrada e duas saídas.
A Figura 1 mostra as funções da terceira etapa de compilação ao transformar um exemplo de expressão regular. Os primeiros três caracteres no exemplo são a, b, c, e cada um cria uma entrada de pilha S[i] e um campo NNODE.NNODE ao código existente para gerar a expressão regular resultante em uma única entrada de pilha (veja a Figura 5)
Esta é a aparência de uma expressão regular .*.*=.*, se você imaginar como nas fotos do artigo de Thompson.
Na Fig. 0, existem cinco estados começando em 0 e 3 ciclos que começam nos estados 1, 2 e 3. Esses três ciclos correspondem a três .* em uma expressão regular. 3 formas ovais com pontos correspondem a um símbolo. Oval com um sinal = corresponde a um caractere literal =. O estado 4 é final. Se chegarmos lá, a expressão regular será correspondida.
Para ver como esse diagrama de estado pode ser usado para correspondência de expressões regulares .*.*=.*, veremos a correspondência de strings x=x. O programa inicia no estado 0, conforme mostrado na Fig. 1.
Para que este algoritmo funcione, a máquina de estados deve estar em vários estados simultaneamente. Uma máquina finita não determinística fará todas as transições possíveis simultaneamente.
Antes que tenha tempo de ler os dados de entrada, ele entra nos dois primeiros estados (1 e 2), como mostrado na Fig. 2.
Na Fig. 2 mostra o que acontece quando ele olha para o primeiro x в x=x. x pode mapear até o ponto superior, indo do estado 1 e voltando ao estado 1. Ou x pode mapear até o ponto abaixo, indo do estado 2 e voltando ao estado 2.
Depois de combinar o primeiro x в x=x ainda estamos nos estados 1 e 2. Não podemos atingir o estado 3 ou 4 porque precisamos de um caractere literal =.
O algoritmo então considera = в x=x. Como x antes dele, ele pode corresponder a qualquer um dos dois loops superiores do estado 1 ao estado 1 ou do estado 2 ao estado 2, mas o algoritmo pode corresponder ao literal = e passar do estado 2 para o estado 3 (e imediatamente 4). Isto é mostrado na figura. 3.
O algoritmo então passa para o último x в x=x. Dos estados 1 e 2, as mesmas transições são possíveis de volta aos estados 1 e 2. Do estado 3 x pode coincidir com o ponto à direita e voltar ao estado 3.
Nesta fase, cada personagem x=x considerado, e como atingimos o estado 4, a expressão regular corresponde a essa string. Cada caractere é processado uma vez, portanto este algoritmo é linear no comprimento da string de entrada. E sem retrocesso.
Obviamente, depois de atingir o estado 4 (quando o algoritmo corresponde x=) toda a expressão regular é correspondida e o algoritmo pode terminar sem considerá-la x.
Este algoritmo depende linearmente do tamanho da string de entrada.
Fonte: habr.com