Arquivo

Archive for the ‘autômatos finitos’ Category

Expressões regulares, autômato finito não determinístico e autômato finito determinístico


 

Introdução

 

No desenvolvimento de um programa (http://www.braga.eti.br/ca/) para exibir quaisquer das 256 regras de autômatos celulares (ACs) propostos pelo incrível Stephen Wolfram, em seu volumoso livro “A New Kind of Science” deparou-se com a questão, simples, de como tratar as possíveis combinações de entrada, do referido programa, já que o usuário poderia:

  1. Pedir o AC de uma única regra (x, onde 0 \leq x \geq 255);
  2. Pedir um conjunto de ACs no seguinte formato: xy, onde x, y \leq 255\,\,e\,\,x < y;
  3. Pedir vários ACs, combinando as duas alternativas anteriores separadas por vírgula (,), em um número finito (e, arbitrário) de vezes.

Este artigo trata das etapas necessárias para que se possa implementar, de forma correta, o tratamento da entrada do programa proposto. Tais etapas são: (a) a construção da expressão regular, (b) a transformação da expressão regular em um autômato finito não determinístico (NFA), (c) a redução do NFA para um autômato finito determinístico (DFA) e, (d) a implementação propriamente dita.

 

Expressão Regular

 

Na literatura de computação, principalmente, os trabalhos de pessoas que lidam com inseguridade como, por exemplo, LANGSEC: Language-theoretic Security recomendam, insistentemente, o uso de linguagens regulares para tratar as entradas de um programa. Nesta direção, se considerado que nos itens de 1 a 3 das especificações acima, as variáveis x e y (diferentes entre si) são números de 0 a 255 pode-se adotar tais números como símbolos, e com as abstrações admissíveis usar a letra (ou símbolo!) n para representá-los e, adicionalmente reconhecer, que dois outros símbolos como pré-requisitos, (, e ), as seguintes combinações de entrada são possíveis:

  • n
  • n, n-n
  • n, n-n, n, …,n, n-n, …
  • n-n, …, n, …,n, n-n, …
  • etc

De tais combinações, depois de um pequeno esforço mental é possível identificar a expressão regular que responde ao desejado:

(n\mid nn)(,n\mid,nn)^*

A noção de abstração aplicada à formulação da expressão regular implica que serão deixadas para a implementação, as questões limitantes do uso do símbolo n e da representação infinita do *.

Dada a expressão regular, a próxima etapa é a construção do NFA.

 

Autômato finito não determinístico (NFA)

 

Construir um NFA a partir de uma expressão regular utilizando-se do algoritmo disponível em várias referências é uma tarefa extremamente agradável, muito embora, um pouco trabalhosa. em determinados casos. Entretanto, na Internet existem diversos ambientes para construção do NFA, de forma automática. Um deles é o Regular Expression to NFA. Usando-o, obtemos o NFA exibido na Figura 1.

 

nfa-erca

Figura 1. NFA obtido automaticamente. Fonte: Regular Expression to NFA.

 

Autômato finito determinístico (DFA)

 

O mesmo construtor do NFA, fornece o DFA, imediatamente, conforme visto na Figura 2.

 

dfa-erca

Figura 2. DFA produzido a partir do NFA da Figura 1. Fonte: Regular Expression to NFA.

 

 

Implementação

 

No Capítulo 10, “Patterns, Automata, and Regular Expressions”, do livro de Al Aho e Jeff Ullman, imperdível e disponível na Internet em Foundations of Computer Science, exibe um algoritmo de implementação de um autômato, extremamente simples, como se pode verificar. Foi usado aquele algoritmo para a implementação e, na oportunidade garantindo as restrições sobre a expressão regular lembradas acima.

Anúncios

Máquinas de estado finito: Parte Prática: MEF do BGP

 

Introdução

 

O foco deste blogue é a infraestrutura da Internet (II). Vez ou outra, um deslize ocorre resultando um texto inesperado e desconexo com a II. Geralmente, tais desvios decorrem de motivações que não estão claras nos textos mas que, eventualmente, serão esclarecidas.

Dada a justificativa, o texto atual está orientado a um dos componentes que irão fazer parte do projeto descrito em [3]. Trata-se da máquina de estado finito (MEF), base para o autômato finito presente na relação entre ROPEs (Repositórios de Objetos de Projeto Estendidos). Máquina de estado finito é um modelo que captura trecho de uma computação. Há definições melhores, e para avançarmos sobre elas veremos os aspectos práticos e teóricos relacionados.

A visão prática é a máquina de estado finito ou MEF, do BGP, já falada no blogue, mas sem os detalhes importantes de seu comportamento. A visão teórica será a representação formal da MEF do BGP à luz de uma modelagem aritmética apropriada, seguindo a sugestão de [6], página 443.

A descrição da MEF do BGP será um apanhado do que está descrito em alguns textos importantes. Stewart4, na página 31, item 2.1 tem uma descrição simples e didáticamente irrepreensível, como sempre. Ele avança, no item seguinte (2.2, página 33) para os tipos de mensagens do BGP. É imperdível, a leitura! White e outros5, na página 22 oferecem uma oportunidade de vislumbrar o MFE do BGP, em uma única figura, com tudo o que será descrito abaixo, sob a ótica prática (ou direta). Por fim, vale lembrar que a RFC42711 é, naturalmente, a referência definitiva e no item 8, página 37, ela lembra bem que a proposta é conceitual e não necessáriamente exige-se sua implementação ipsis literae. Mas, o autor não sabe informar se algum BGP (a.k.a., sua MEF) implementado em algum roteador disponível no mercado deixa de cumprir a especificação da RFC4271.

 

A MEF do BGP

 

A Figura 1, abaixo exibe uma representação da MEF do BGP. Na realidade, como veremos mais tarde esta MEF é um autômato finito representado por seis estados: Idle, Connect, Active, OpenSent, OpenConfirm e Established. O estado inicial do MEF é o Idle. Um estado muda para outro estado de acordo com a representação das setas (arcos ou arestas) identificadas por uma letra (de A a U), para facilitar o entendimento do MEF, na sequência.

 

Figura 1. Máquina de Estado Finito do BGP. Desenhado pelo autor com base no item 8.2.2 da RFC4271.

 

Existem 28 eventos que podem gerar transições na MEF do BGP, e eles estão enumeradas abaixo:

    1. ManualStart
    2. ManualStop
    3. AutomaticStart
    4. ManualStart_with_PassiveTcpEstablishmen
    5. AutomaticStart_with_PassiveTcpEstablishment
    6. AutomaticStart_with_DampPeerOscillations
    7. AutomaticStart_with_DampPeerOscillations_and_PassiveTcpEstablishment
    8. AutomaticStop
    9. ConnectRetryTimer_Expires
    10. HoldTimer_Expires
    11. KeepaliveTimer_Expires
    12. DelayOpenTimer_Expires
    13. IdleHoldTimer_Expires
    14. TcpConnection_Valid
    15. Tcp_CR_Acked
    16. Tcp_CR_Invalid
    17. TcpConnectionConfirmed
    18. TcpConnectionFails
    19. BGPOpen
    20. BGPOpen with DelayOpenTimer running
    21. BGPHeaderErr
    22. BGPOpenMsgErr
    23. OpenCollisionDump
    24. NotifMsgVerErr
    25. NotifMsg
    26. KeepAliveMsg
    27. UpdateMsg
    28. UpdateMsgErr

Alguns destes eventos são opcionais, mas é pouco provável que alguma implementação de BGP deixe algum de fora. A descrição detalhada destes eventos estão na RFC42711, item 8.1 na página 38. Muitos destes eventos precisam de parâmetros, denominados atributos de sessão associados a eles. Existem dois tipos de atributos, os obrigatórios (ou mandatórios) e os opcionais. Os obrigatórios são:

      1. State
      2. ConnectRetryCounter
      3. ConnectRetryTimer
      4. ConnectRetryTime
      5. HoldTimer
      6. HoldTime
      7. KeepaliveTimer
      8. KeepaliveTime
      9.  

        O atributo state indica o estado corrente da MEF do BGP e o atributo ConnectRetryCounter indica o número de vezes que um BGP tentou estabelecer uma sessão com seu empareado. O restantes dos atributos obrigatórios estão escritos no item 10 da RFC42711. Os atributos opcionais são, continuando a sequência acima:

      10. AcceptConnectionsUnconfiguredPeers
      11. AllowAutomaticStart
      12. AllowAutomaticStop
      13. CollisionDetectEstablishedState
      14. DampPeerOscillations
      15. DelayOpen
      16. DelayOpenTime
      17. DelayOpenTimer
      18. IdleHoldTime
      19. IdleHoldTimer
      20. PassiveTcpEstablishment
      21. SendNOTIFICATIONwithoutOPEN
      22. TrackTcpState

Os atributos opcionais e as relações com os eventos estão descritos no item 8.1.1 e 8.2.1.3 da RFC42711.

Um exemplo de como os atributos estão associados a eventos é o evento 9, ConnectRetryTimer_Expires. Este evento ocorrerá (ou será gerado), se o atributo obrigatório 3, ConnectRetruTimer expirar.

 

O comportamento da MEF do BGP

 

A transição entre cada estado da MEF mostrada na Figura 1 é uma combinação do evento e de atributos a ele associados. A RFC42711, no item 8.2.2 descreve com detalhes refinados como ocorre a transição entre cada estado da MEF. Não entraremos em detalhes sobre a transição, por limitação de espaço e de foco. Entretanto daremos uma ideia geral do mecanismo, mostrando a transição do estado Connect para o estado OpenConfirm, através de L, pois esta transição é uma novidade em relação às RFCs anteriores, do BGP.

Suponha que o estado da MEF seja Connect. Se uma mensagem OPEN é recebida enquanto o evento 20 (BGPOpen with DelayOpenTimer running) está ativo no sistema local (MEF que estamos analisando), então ocorrerá o seguinte:

      • Se o processo sobre o atributo ConnectRetryTimer está ativo, então ele é parado e o ConnectRetryTimer (c) é zerado;
      • Completa a inicialização do BGP;
      • Para e zera o atributo DelayOpenTimer (p);
      • Envia uma mensagem OPEN;
      • Envia uma mensagem KEEPALIVE;
      • Se o valor inicial do atributo HoldTimer (e) não é zero, então:
        • Inicia o valor do atributo KeepaliveTimer (g) com o valor inicial e,
        • Restabeleça o atributo HoldTimer para o valor negociado;
      • Entretanto, se o valor inicial do atributo HoldTimer (e) é zero, então:
        • Restabeleça o atributo KeepaliveTimer (g) e,
        • Restabeleça o atributo HoldTimer (e) para zero;
      • Mude o estado para OpenConfirm

Então podemos dizer que L (transição do estado Connect para o estado OpenConfirm) será ativada, quanto o evento 20c,e,g,p ocorrer (dependendo de condições dos atributos apresentados nos índices superiores). É uma representação abstrata, cuja principal finalidade é a de exibir a transição, o evento e os atributos diretamente envolvidos. A abstração remove detalhes relevantes que a RFC4271 esclarece apropriadamente, razão pela qual a ela se deve recorrer para o comportamento completo da transição. Assim pensando, a Tabela 1 mostra as 21 transições (representadas pelas letras maiúsculas na Figura 1), os eventos envolvidos em cada uma e os atributos associados.

Arco Transição Eventos e atributos envolvidos
A Idle=>Idle 6m, 7m, 13m
B Idle=>Active 4b,c, 5b,c
C Active=>Active 16c,n, 17c,n
D Active=>OpenConfirm 20c,e,g,p
E OpenConfirm=>Established 26e
F Established=>Established 26e, 27e
G Established=>Idle 2b,c, 8b,c,m, 9b,c,m, 10b,c,e,m, 12b,c,m, 13b,c,m, 18b,c, 19b,c,l,m, 20b,c,m, 21b,c,m, 22b,c,m, 23b,c,l,m, 24b,c, 25b,c, 28b,c,m
H Idle=>Connect 1b,c, 3b,c
I Connect=>Idle 2b,c, 8b,d,m,p, 10b,d,m,p, 11b,d,m,p, 13b,d,m,p,18c,p, 19b,d,m,p, 21c,m,t, 23b,d,m,p, 24d,m,p, 25b,d,m,p, 26b,d,m,p, 27b,d,m,p, 28b,d,m,p
J Connect=>Connect 9c,p, 16c,n,p, 17c,n,p
K Connect=>OpenSent 12e, 16c,e,n, 17c,e,n
L Connect=>OpenConfirm 20c,e,g,p
M Connect=>Active 18c,p
N Active=>Connect 9c
O Active=>OpenSent 12c,p, 16c,e,n, 17c,e,n
P OpenSent=>Active 18c
Q OpenSent=>OpenConfirm 19e,g,p
R OpenSent=>Idle 2c, 8b,c,m, 9b,c,m, 10b,e,m, 11b,c,m, 12b,c,m, 13b,c,m, 20b,c,m, 21b,c,m, 22b,c,m, 23b,c,m, 24c, 25b,c,m, 26b,c,m, 27b,c,m, 28b,c,m
S OpenConfirm=>OpenConfirm 11g
T OpenConfirm=>Idle 2b,c, 8b,c,m, 9b,c,m, 10b,c,m, 12b,c,m, 13b,c,m, 14b,c,m, 16b,c,m, 17b,c,m, 18b,c, 19b,c,m, 20b,c,m, 21b,c, 22b,c, 23b,c,m, 25b,c, 27b,c,m, 28b,c,m
U Active=>Idle 2b,c,p,t, 8b,c,m, 10b,c,m, 11b,c,m, 13b,c,m, 18b,c,m, 19b,c,m, 21b,c,m,t, 22b,c,m,t, 23b,c,m, 24b,c,m,p, 25b,c,m, 26b,c,m, 27b,c,m, 28b,c,m
Tabela 1. Transições do MEF do BGP, eventos e atributos envolvidos.

 

Observações complementares

 

As RFC62867 e RFC66082 aparecem em Referências, por serem atualizações da RFC42711, sem interesse direto, no presente texto, embora sejam importantes na implementação do BGP e de sua MEF.

 

Referências

 

    1. RFC4271, A Border Gateway Protocol 4 (BGP-4) Y. Rekhter, T. Li, S. Hares [ January 2006 ] (TXT = 222702) (Obsoletes RFC1771) (Updated-By RFC6286, RFC6608) (Status: DRAFT STANDARD) (Stream: IETF, Area: rtg, WG: idr). Acessado em 26/08/2012.
    2. RFC6608, Subcodes for BGP Finite State Machine Error J. Dong, M. Chen, A. Suryanarayana [ May 2012 ] (TXT = 8612) (Updates RFC4271) (Status: PROPOSED STANDARD) (Stream: IETF, Area: rtg, WG: idr). Acessado em 26/08/2012.
    3. Julião Braga. (2012). Objetos de Projeto Estendidos (OPE). Disponível em: https://juliaobraga.wordpress.com/2012/08/22/objetos-de-projeto-estendidos-ope/. Acessado em 26/08/2012.
    4. Stewart, J. W. III. BGP4: inter-domain routing in the Internet. Reading, Mass.: Addison Wesley, 1998.
    5. White, R., McPherson, D., Sangli, S. Practical BGP. Boston, MA: Pearson, 2005. 434 p.
    6. Gersting, J. L. Fundamentos Matemáticos para a Ciência da Computação: um tratamento moderno de matemática discreta. Tradução: Valéria de Magalhães Iorio. Rio de Janeiro: LTC, 2008. PLT 166, Anhanguera Educacional S. A. 5a. edição, 597 p.
    7. RFC6286, Autonomous-System-Wide Unique BGP Identifier for BGP-4 E. Chen, J. Yuan [ June 2011 ] (TXT = 7497) (Updates RFC4271) (Status: PROPOSED STANDARD) (Stream: IETF, Area: rtg, WG: idr). Acessado em 26/08/2012.
%d blogueiros gostam disto: