Arquivo

Archive for the ‘Teoria da Computação’ Category

Preparando as RFCs para o UIMA

Introdução

Uma vez entendido o UIMA segue a aprendizagem sobre ele. Olhando primeira figura do texto Instalação do Apache UIMA (Apache UIMA Installation), vê-se o conjunto de material não estruturado a ser analisado, reproduzida na Figura 1, com ênfase no repositório do RFC Editor, onde repousam os principais documentos do IETF.

aeasd-1

Figura 1. O repositório das RFCs. Primeira base não estruturada a ser analisada pelo UIMA.

Como trabalhar com o repositório das RFCs

RFCs não possuem data e hora marcadas para aparecer e, estão em um formato que deve ser normalizado (brancos, figuras em texto, autores, diferenças de padrões de escrita, etc.), para adaptar-se ao UIMA ou outra aplicação. Este processo de normalização é, na verdade uma “arrumação” sobre os dados de entrada e possui as característica descritas por Wickham (2014)1. Portanto é necessário, um pré-processamento, no qual estas duas questões serão resolvidas. A Figura 2 apresenta um modelo preliminar a ser seguido.

uima-preprocessamentorfcs

Figura 2. O pré-processamento das RFCs.

O próprio RFC Editor recomenda um mecanismo2 de recuperação de RFCs usando o rsync, uma ferramenta disponível nos sistema a la Unix e também, no Windows. Como mostra a Figura 2, o rsync trás a base do RFC Editor para o diretório rfstemp/ local, de forma incremental, como se desejava. Sobre este diretório, um programa em Python (denominado preprocess.py) é executado periodicamente e, sempre, executa o rsync, transferindo as novas RFCs para o diretório rfcs/, as quais são consumidas pelo UIMA. A Figura 3 mostra o exemplo de uma execução do rsync, no Windows 10, via prompt e uma nova RFC disponível (rfc7715.txt). Naturalmente, esta execução não foi a primeira vez, oportunidade em que isto é, o diretório rfstemp/ já tinha sido populado com TODAS as RFCs.

uima-rsync-exemplo

Figura 3. Execução do rsync e a disponibilidade de uma nova RFC enfatizada em vermelho.

A periodicidade de execução do programa preprocess.py é feita, automaticamente, através do cron (um processo, também, disponível para o Windows). Ele preserva a informação sobre a última RFC atualizada, captura as novas, normalizando e colocando-as no diretório de entrada para o UIMA (rfcs/). O processo de normalização é simples, retirando tudo o que é texto inútil de cada RFC (brancos, rodapés, etc.). Em função do UIMA, o programa preprocess.py, eventualmente, evoluirá o processo de normalização e/ou aperfeiçoará a entrada (isto é, o conteúdo do diretório rfcs/).

O UIMA, ao consumir as RFCs deixa o diretório rfcs vazio. Nas atividades do UIMA, Java é a principal linguagem, como vimos no primeiro artigo da série: Instalação do Apache UIMA (Apache UIMA Installation). O segundo artigo é uma visão geral do UIMA: Funcionamento Básico do Apache UIMA


  1. Wickham, H. Tidy Statistic. Journal of Statistical Software, Foundation for Open Access Statistics, v. 59, n. 10, 2014.
  2. https://www.rfc-editor.org/retrieve/rsync/

Instalação do Apache UIMA (Apache UIMA Installation)

Introdução

Introduction


Este texto relata o processo de instalação do Eclipse, juntamente com o Apache UIMA1. O objetivo é usar o Apache UIMA, em uma primeira etapa, para testar a hipótese ilustrada pela Figura 1.


This paper reports the Eclipse installation process along with Apache UIMA1. The goal is to use the Apache UIMA, in a first step, to test the hypothesis illustrated in Figure 1.

aeasd
Figura 1. Modelo a ser testado no Apache UIMA.
Figure 1. Model to be tested in Apache UIMA.


Na figura, (1), representa o modelo AEASD (Autonomous Elements Architecture for Specific Domains) (BRAGA; OMAR; GRANVILLE, 2015), o qual organiza um ambiente de agentes inteligentes com características voltadas para o domínio específico dos Sistemas Autônomos, que povoam a Internet. Presume-se que os elementos inteligentes terão mais autonomia, se conseguirem aprender, ensinar e cooperar através de uma base de conhecimento ou ontologia, (2), local ou remota (como a Wikidata2 e/ou outras). Esta ontologia pode ser construída a partir de bases de dados não estruturadas, (3), desde que se possua as ferramentas adequadas (FAN et al., 2012). Um conjunto de tais ferramentas foi desenvolvido pela IBM (FERRUCCI, 2012) (FERRUCCI et al., 2010), através de uma competente equipe quando da construção do IBM Watson, (5), diante do incrível desafio de vencer humanos no Jeopardy! – existem diversos vídeos no YouTube sobre este evento, que aconteceu em 2011. Há fortes indícios de que com adaptações adequadas, tais técnicas possam ser transportadas para domínios específicos (FERRUCCI; BROWN, 2011), como o domínio de interesse da hipótese a ser testada, (4). Através das técnicas adaptadas, bases intermediárias, (6), poderão ser construídas, sobre as quais novas ferramentas, (7), podem direcionar o conhecimento adquirido no formato adequado, (2). Os elementos inteligentes do modelo AEASD irão interagir com as novas ferramentas adaptadas, (5), e desenvolvidas, (7).


In the figure, (1) represents the AEASD
model (Autonomous Elements Architecture for Specific Domains) (BRAGA; OMAR; GRANVILLE, 2015), which organizes an intelligent agents environment with features focused on the specific area of ​​Autonomous Systems, populating the Internet. It is assumed these smart elements will have more autonomy, if they can learn, teach and cooperate through a knowledge base or ontology, (2), local or remote (such as Wikidata2 and / or others). This ontology can be constructed from unstructured databases, (3), provided that it has the appropriate tools (FAN et al., 2012).
A set of such tools was developed by IBM (FERRUCCI, 2012) (FERRUCCI et al., 2010), through a competent team when the construction of the IBM Watson, (5), facing the incredible challenge to beat humans in Jeopardy! – there are several videos on YouTube about this event, which took place
in 2011. There is strong evidence that with appropriate adjustments, such techniques
can be transported to specific areas (FERRUCCI; BROWN, 2011), as the domain of interest hypothesis to be tested, (4). Through the adapted techniques, intermediate bases, (6), may be built, for which new tools, (7), can direct the acquired knowledge in the proper format, (2). Intelligent elements in AEASD model will interact with new adapted tools, (5), and developed, (7).
.

Neste texto, a preocupação é mostrar, informalmente, a experiência da implementação do Apache UIMA sob o ambiente do Eclipse (MARS.1) em Windows 10, sob Notebook Dual Core (inicialmente) e servir como guia de apoio aos interessados. Posteriormente, outros textos poderão ser produzidos com abordagens focadas no Apache UIMA, como ferramenta de análise dos dados não estruturados dentro do domínio da Infraestrutura da Internet e seus resultados em relação às experiências sobre a hipótese mostrada na Figura 1. A Figura 2, abstratamente, ilustra a tarefa do Apache UIMA em submeter informações (multi modal) do mundo não estruturado, sob um processo de transformação ao mundo dos dados estruturados. Sem mágica, naturalmente.

In this text, the concern is to show informally the experience of implementation of Apache UIMA under the Eclipse environment (MARS.1) in Windows 10, under Notebook Dual Core (initially) and serve as a guide to support interested. Later, other texts can be
produced with approaches focused on the Apache UIMA as unstructured data analysis tool within the Internet infrastructure domain and its results against experience on the hypothesis shown in Figure 1. Figure 2, abstractly, illustrates the Apache UIMA task
to submit information from (multi modal) unstructured world, in a process of transformation to the world of structured data. No magic, of course.

uima-estrutura
Figura 2. O que faz o Apache UIMA8.
Figure 2. What does the Apache UIMA8.

 

… from now on, only in Portuguese…

 

Instalação do Apache UIMA

 

São em sete, o número de etapas3 para se preparar o Apache UIMA para o trabalho a ser executado. Todas elas envolvem diretamente a implementação do Eclipse.

  1. Instalar o Eclipse
  2. Instalar os plugins UIMA no Eclipse
  3. Instalar algumas extensões complementares no Eclipse
  4. Instalar o UIMA SDK
  5. Instalar o código fonte UIMA nos arquivos jar
  6. Instalar o Javadocs do UIMA
  7. Preparar o Eclipse para ver o Código Exemplo

 

Instalação do Eclipse

 

1). Foi instalado o Java SE Develpment Kit (8u66)4

2). Foi instalado o Eclipse “for Java Developers”5, que inclui: Java IDE, cliente GIT, Editor XML, Myliyn, integrador Maven e WindowBulder. Em seguida foi incluído o m2e e o Py IDE. Para as instalações posteriores, veja a documentação6 do Eclipse.

3). Instalados os plugins do UIMA, conforme pode ser visto na Figura 3.

eclipse-uima

Figura 3. Versões dos plugins UIMA instalados no Eclipse.

4). Adicionar a variável de ambiente para o Maven7, recomentado em “One time setup ofr Maven” e “One time setup for Eclipse”. Detalhes nas Figuras 4 e 5.

eclipse-maven

Figura 4. Inclusão da variável de ambiente MAVEN_OPTS (Resultado final)

eclipse-maven2

Figura 5. Visão geral da operação de inclusão da variável de ambiente MAVEN_OPTS.

5). Instalar o UIMA SDK (Apache UIMA Version 2.8.1) disponível em http://mirror.nbtelecom.com.br/apache//uima//uimaj-2.8.1/uimaj-2.8.1-bin.zip . Descompacte-o em qualquer diretório. No meu caso foi em E:apache-uima. Em seguida crie a variável de ambiente %UIMA_HOME% para este diretório. Faça o mesmo para %ECLIPSE_HOME%, para o caminho C:Usersjbeclipsejava-marseclipse.

6). Em seguida executar adjustExamplePaths.bat, no diretório %UIMA_HOME%bin cujo resultado segue abaixo. É preciso ficar atento às quebras de linhas forçadas, para que o texto caiba integralmente.

E:apache-uimabin>adjustExamplePaths.bat
E:apache-uimabin>setlocal
E:apache-uimabin>if "" == "" (set UIMA_JAVA_CALL=java )  
else (set "UIMA_JAVA_CALL=binjava" )
E:apache-uimabin>"java" -cp "E:apache-uima/lib/uima-core.jar" 
org.apache.uima.internal.util.ReplaceStringInFiles 
"E:apache-uima/examples" .xml "C:/Program Files/apache-uima" 
"E:apache-uima" -ignorecase
Ignoring case
Working on file: E:apache-uimaexamplesdataxml
IBM_LifeSciences.xml
Working on file: E:apache-uimaexamplesdataxml
New_IBM_Fellows.xml
Working on file: E:apache-uimaexamplesdataxml
SeminarChallengesInSpeechRecognition.xml
Working on file: E:apache-uimaexamplesdataxml
TrainableInformationExtractionSystems.xml
Working on file: E:apache-uimaexamplesdataxml
UIMASummerSchool2003.xml
Working on file: E:apache-uimaexamplesdataxml
UIMA_Seminars.xml
Working on file: E:apache-uimaexamplesdataxml
WatsonConferenceRooms.xml
Working on file: E:apache-uimaexamplesdeployvinci
Deploy_MeetingDetectorTAE.xml
File modified, number of instances replaced: 1
Working on file: E:apache-uimaexamplesdeployvinci
Deploy_PersonTitleAnnotator.xml
File modified, number of instances replaced: 1
Working on file: E:apache-uimaexamplesdeployvinci
Deploy_XmiWriterWithTutorialTypeSystem.xml
File modified, number of instances replaced: 1
Working on file: E:apache-uimaexamplesdescriptors
MixedAggregate.xml
Working on file: E:apache-uimaexamplesdescriptors
analysis_engineGovernmentOfficialRecognizer_RegEx_TAE.xml
Working on file: E:apache-uimaexamplesdescriptors
analysis_engineNamesAndGovernmentOfficials_TAE.xml
Working on file: E:apache-uimaexamplesdescriptors
analysis_engineNamesAndPersonTitles_TAE.xml
Working on file: E:apache-uimaexamplesdescriptors
analysis_enginePersonTitleAnnotator.xml
Working on file: E:apache-uimaexamplesdescriptors
analysis_enginePersonTitleAnnotator_WithinNamesOnly.xml
Working on file: E:apache-uimaexamplesdescriptors
analysis_engineRegExAnnotator.xml
Working on file: E:apache-uimaexamplesdescriptors
analysis_engineSimpleEmailRecognizer_RegEx_TAE.xml
Working on file: E:apache-uimaexamplesdescriptors
analysis_engineSimpleNameRecognizer_RegEx_TAE.xml
Working on file: E:apache-uimaexamplesdescriptors
analysis_engineSimpleTokenAndSentenceAnnotator.xml
Working on file: E:apache-uimaexamplesdescriptors
analysis_engineSofaExampleAnnotator.xml
Working on file: E:apache-uimaexamplesdescriptors
analysis_engineUIMA_Analysis_Example.xml
Working on file: E:apache-uimaexamplesdescriptors
analysis_engineXmlDetagger.xml
Working on file: E:apache-uimaexamplesdescriptors
cas_consumerAnnotationPrinter.xml
Working on file: E:apache-uimaexamplesdescriptors
cas_consumerInlineXmlCasConsumer.xml
Working on file: E:apache-uimaexamplesdescriptors
cas_consumerXCasWriterCasConsumer.xml
Working on file: E:apache-uimaexamplesdescriptors
cas_consumerXmiEcoreCasConsumer.xml
Working on file: E:apache-uimaexamplesdescriptors
cas_consumerXmiWriterCasConsumer.xml
Working on file: E:apache-uimaexamplesdescriptors
cas_consumerXmiWriterWithTutorialTypeSystem.xml
Working on file: E:apache-uimaexamplesdescriptors
cas_multiplierSegmenterAndTokenizerAE.xml
Working on file: E:apache-uimaexamplesdescriptors
cas_multiplierSegment_Annotate_Merge_AE.xml
Working on file: E:apache-uimaexamplesdescriptors
cas_multiplierSimpleTextMerger.xml
Working on file: E:apache-uimaexamplesdescriptors
cas_multiplierSimpleTextSegmenter.xml
Working on file: E:apache-uimaexamplesdescriptors
collection_processing_engineMeetingFinderCPE_Integrated.xml
Working on file: E:apache-uimaexamplesdescriptors
collection_processing_engineMeetingFinderCPE_Managed_Unix.xml
File modified, number of instances replaced: 5
Working on file: E:apache-uimaexamplesdescriptors
collection_processing_engineMeetingFinderCPE_Managed_Windows.xml
File modified, number of instances replaced: 5
Working on file: E:apache-uimaexamplesdescriptors
collection_processing_engineMeetingFinderCPE_NonManaged.xml
Working on file: E:apache-uimaexamplesdescriptors
collection_processing_engineMeetingFinderCPE_
NonManagedCasConsumer.xml
Working on file: E:apache-uimaexamplesdescriptors
collection_processing_engineMeetingFinderCPE_WithXmlDetagging.xml
File modified, number of instances replaced: 1
Working on file: E:apache-uimaexamplesdescriptors
collection_readerFileSystemCollectionReader.xml
File modified, number of instances replaced: 1
Working on file: E:apache-uimaexamplesdescriptors
collection_readerXmiCollectionReader.xml
File modified, number of instances replaced: 1
Working on file: E:apache-uimaexamplesdescriptors
flow_controllerAdvancedFixedFlowController.xml
Working on file: E:apache-uimaexamplesdescriptors
flow_controllerMeetingDetectorTAE_AdvancedFixedFlow.xml
Working on file: E:apache-uimaexamplesdescriptors
flow_controllerMeetingDetectorTAE_Whiteboard.xml
Working on file: E:apache-uimaexamplesdescriptors
flow_controllerWhiteboardFlowController.xml
Working on file: E:apache-uimaexamplesdescriptors
soapServiceGovernmentTitleRecognizerService.xml
Working on file: E:apache-uimaexamplesdescriptors
soapServiceNamesAndPersonTitlesService.xml
Working on file: E:apache-uimaexamplesdescriptors
soapServicePersonTitleAnnotatorService.xml
Working on file: E:apache-uimaexamplesdescriptors
soapServiceSimpleNameRecognizerService.xml
Working on file: E:apache-uimaexamplesdescriptors
tutorialex1RoomNumberAnnotator.xml
Working on file: E:apache-uimaexamplesdescriptors
tutorialex1TutorialTypeSystem.xml
Working on file: E:apache-uimaexamplesdescriptors
tutorialex2RoomNumberAnnotator.xml
Working on file: E:apache-uimaexamplesdescriptors
tutorialex3RoomNumberAndDateTime.xml
Working on file: E:apache-uimaexamplesdescriptors
tutorialex3TutorialDateTime.xml
Working on file: E:apache-uimaexamplesdescriptors
tutorialex3TutorialTypeSystem.xml
Working on file: E:apache-uimaexamplesdescriptors
tutorialex4MeetingAnnotator.xml
Working on file: E:apache-uimaexamplesdescriptors
tutorialex4MeetingDetectorTAE.xml
Working on file: E:apache-uimaexamplesdescriptors
tutorialex4TutorialTypeSystem.xml
Working on file: E:apache-uimaexamplesdescriptors
tutorialex5RoomNumberAnnotator.xml
Working on file: E:apache-uimaexamplesdescriptors
tutorialex6TutorialTypeSystem.xml
Working on file: E:apache-uimaexamplesdescriptors
tutorialex6UimaAcronymAnnotator.xml
Working on file: E:apache-uimaexamplesdescriptors
tutorialex6UimaMeetingAnnotator.xml
Working on file: E:apache-uimaexamplesdescriptors
tutorialex6UimaMeetingDetectorTAE.xml
Working on file: E:apache-uimaexamplesdescriptors
tutorialsearchMeetingIndexBuildSpec.xml
Working on file: E:apache-uimaexamplesdescriptors
vinciServiceMeetingDetectorVinciService.xml
Working on file: E:apache-uimaexamplesdescriptors
vinciServicePersonTitleVinciService.xml
Working on file: E:apache-uimaexamplesdescriptors
vinciServiceXmiWriterVinciServiceWithTutorialTypeSystem.xml
Working on file: E:apache-uimaexamplesresourcesorg
apacheuimaexamplesSourceDocumentInformation.xml

E:apache-uimabin>"java" -cp "E:apache-uima/lib/uima-core.jar" 
org.apache.uima.internal.util.ReplaceStringInFiles 
"E:apache-uima/examples" .classpath "C:/Program Files/
apache-uima" "E:apache-uima" -ignorecase
Ignoring case
Working on file: E:apache-uimaexamples.classpath
File modified, number of instances replaced: 5

E:apache-uimabin>"java" -cp "E:apache-uima/lib/uima-core.jar" 
org.apache.uima.internal.util.ReplaceStringInFiles 
"E:apache-uima/examples" .launch "C:/Program Files/
apache-uima" "E:apache-uima" -ignorecase
Ignoring case
Working on file: E:apache-uimaexamplesrun_configuration
UIMA Annotation Viewer.launch
Working on file: E:apache-uimaexamplesrun_configuration
UIMA CAS Visual Debugger.launch
Working on file: E:apache-uimaexamplesrun_configuration
UIMA CPE GUI.launch
Working on file: E:apache-uimaexamplesrun_configuration
UIMA Document Analyzer.launch
Working on file: E:apache-uimaexamplesrun_configuration
UIMA JCasGen Merge.launch
Working on file: E:apache-uimaexamplesrun_configuration
UIMA JCasGen.launch
Working on file: E:apache-uimaexamplesrun_configuration
UIMA PEAR Installer.launch
Working on file: E:apache-uimaexamplesrun_configuration
UIMA Run AE.launch
Working on file: E:apache-uimaexamplesrun_configuration
UIMA Run CPE.launch
Working on file: E:apache-uimaexamplesrun_configuration
UIMA Start Vinci Service.launch
Working on file: E:apache-uimaexamplesrun_configuration
UIMA Start VNS.launch

E:apache-uimabin>"java" -cp "E:apache-uima/lib/uima-core.jar" 
org.apache.uima.internal.util.ReplaceStringInFiles 
"E:apache-uima/examples" .wsdd "C:/Program Files/
apache-uima" "E:apache-uima" -ignorecase
Ignoring case
Working on file: E:apache-uimaexamplesdeploysoap
Deploy_GovernmentTitleRecognizer.wsdd
File modified, number of instances replaced: 1
Working on file: E:apache-uimaexamplesdeploysoap
Deploy_NamesAndPersonTitles.wsdd
File modified, number of instances replaced: 1
Working on file: E:apache-uimaexamplesdeploysoap
Deploy_PersonTitleAnnotator.wsdd
File modified, number of instances replaced: 1
Working on file: E:apache-uimaexamplesdeploysoap
Deploy_SimpleNameRecognizer.wsdd
File modified, number of instances replaced: 1
Working on file: E:apache-uimaexamplesdeploysoap
Undeploy_GovernmentTitleRecognizer.wsdd
Working on file: E:apache-uimaexamplesdeploysoap
Undeploy_NamesAndPersonTitles.wsdd
Working on file: E:apache-uimaexamplesdeploysoap
Undeploy_PersonTitleAnnotator.wsdd
Working on file: E:apache-uimaexamplesdeploysoap
Undeploy_SimpleNameRecognizer.wsdd
E:apache-uimabin>

7). Execute no prompt, eclipse -clean, para carregar o Eclipse.

8). Inclua o caminho %UIMA_HOME% no Eclipse, como mostra a Figura 5.

eclipse-path

Figura 5. Incluindo o %UIMA_HOME% no Eclipse.

9). Crie o novo projeto exemplo do UIMA executando os passos, no Eclipse:

  • Selecione o menu “File” e “Import”
  • Selecione “General/Existing Project into Workspace” e clique no botão “Next”.
  • Clique em “Browse” e indique o diretório %UIMA_HOME%.
  • Clique em “Finish”. Isto irá criar um novo projeto no Eclipse, chamado “uimaj-examples”. Realmente, não houve erro de compilação, como mostra a Figura 6.
eclipse-noproblem

Figura 6. Nenhum erro de compilação do projeto exemplo do UIMA

Após estes passos, o código fonte do UIMA já foi inserido no ambiente do Eclipse, incluindo o Javadocs, não sendo necessário cumprir outras atividades. Portanto, o Eclipse está pronto para o UIMA! Cumpriu-se assim, todas as sete etapas da constantes da seção “Instalação do UIMA”, como mostra a Figura 7.

eclipse-pronto

Figura 7. Visão parcial do Eclipse pronto para o UIMA.

 

Comentários Finais

 

Esta iniciativa de preparar o Apache UIMA para ser testado foi motivado pela disciplina Cognição e Aplicações Computacionais [turma 01A] – 2015/2, ministrada pelos Profs. Dr. Nizam Omar e Dr. Ismar Frango Silveira, no Programa de Pós Graduação em Engenharia Elétrica e Computação, da Universidade Presbiteriana Mackenzie, São Pauo, aos quais expresso meus agradecimentos pela oportunidade.

 

Referências

 

BRAGA, J.; OMAR, N.; GRANVILLE, L. Z. Uma proposta para o uso de elementos inteligentes em domínios restritos da infraestrutura da internet. In: Anais CSBC 2015 – WPIETFIRTF. Recife, Pernambuco, Brasil: [s.n.], 2015.

FAN, J. et al. Automatic knowledge extraction from documents. IBM Journal of Research and Development, IBM, v. 56, n. 3.4, p. 5–1, 2012.

FERRUCCI, D.; BROWN, E. AdaptWatson: A methodology for developing and adapting Watson technology. Armonk, NY, 2011. 8 p. Disponível em: <http://domino.research.ibm.com/library/cyberdig.ns/papers/29303F8DC7A92FC9852579F30049ABCD&gt;.

FERRUCCI, D. A. Introduction to “This is Watson”. IBM Journal of Research and Development, IBM, v. 56, n. 3.4, p. 1–1, 2012.

FERRUCCI, D. et al. Building Watson: An overview of the DeepQA project. AI Magazine, v. 31, n. 3, p. 59–79, 2010.


  1. Apache UIMA. http://uima.apache.org/index.html
  2. Wikidata. https://www.wikidata.org/wiki/Wikidata:Main_Page
  3. UIMA Overview & SDK Setup. http://uima.apache.org/d/uimaj-current/overview_and_setup.pdf
  4. http://www.oracle.com/technetwork/java/javase/downloads/jdk8-downloads-2133151.html
  5. http://www.eclipse.org/users/
  6. http://help.eclipse.org/mars/index.jsp
  7. http://uima.apache.org/one-time-setup.html#maven-setup
  8. Adaptation of Figure 2.1 available in http://uima.apache.org/d/uimaj-current/overview_and_setup.pdf

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.

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.

Soquetes: PHP, IPv6 e inseguridade

 

Introdução

 

Soquete é um recurso muito interessante e bastante usado pelos programadores mais experientes. Soquete é usado quando se deseja conexão entre equipamentos por diversas razões, como por exemplo, se a expectativa é o controle mais refinado da comunicação entre sistemas operacionais diferentes. Este texto mostra algumas preocupações a serem levadas em conta quando a linguagem é o PHP. Tais preocupações devem induzir ao leitor, no final, que a programação do soquete, em si é razoavelmente simples. Mas a programação da aplicação é difícil.

 

Soquetes e o conceito Cliente-Servidor

 

O modelo Cliente-Servidor é inerente ao uso de soquetes. Os diagramas que apresentam os soquetes sempre são formais. Um bom exemplo pode ser visto em [1], onde há uma abstração do relacionamento entre o Cliente e o Servidor usando soquetes. Um diagrama mais refinado é mostrado na figura abaixo.

 

 

Um exemplo de um servidor completo, que aceita telnet, pode ser visto no sítio do PHP, em [2]. Um texto muito interessante, completo e exaustivamente discutido, com exemplos na linguagem C está em [3].

Um problema que ocorreu no exemplo do sítio do PHP, [2], em IPv4, foi o aparecimento de alguns caracteres adicionais, nos 5 primeiros textos que o Cliente enviava para o Servidor. Não consegui resposta para o problema, mas algumas pessoas diziam que se referia ao protocolo do telnet. Mas não apresentavam solução. No primeiro texto do Cliente para o Servidor, este prefixava algo como ÿþÿþ ÿþÿþ’ÿü e, outros caracteres eram adicionados, diminuindo o tamanho, até o quinto texto. A partir do sexto texto, não aparecia mais. A solução encontrada, foi usar a função substr para obter o texto original com base no caracter 22. Tal posição foi encontrada via algumas tentativas/erro.

Em IPv6, este problema não ocorreu. O tratamento IPv6 no PHP (soquete) precisa ser explicitado, no primeiro parâmetro da função socket_create(AF_INET6, SOCK_STREAM, SOL_TCP). Para IPv4, retira-se o 6. Fora a indiossincrasia do IPv4, tudo funcionou conforme o figurino. No final fiquei imaginando se o amadurecimento no desenvolvimento do IPv6 e seus aplicativos (do sistema) refletia estabilidade maior do que o IPv4. Pura conjectura, claro.

Programar o soque é simples, portanto. Há muita ajuda na Internet e googladas procurando por PHP irão trazer resultados interessantes. Mas, programar a aplicação do soquete é uma tarefa difícil. Quem tiver IPv6, pode testar o protótipo, bastanto usar o comando abaixo:

telnet -6 peony.pegasus.com.br 10000

Só irá funcionar, em IPv6! Tudo o que for digitado, exceto os resultados dos comandos descritos na “ajuda”, retornam ao Cliente.

 

Qual a dificuldade no desenvolvimento de programas e/ou aplicações usando soquetes?

 

Muitas!! O exemplo, que pode ser visto pelo telnet acima, é muito simples porque lida com a necessidade de conhecimento da linguagem PHP e as funções disponíveis para os soquetes. É uma questão de treino. A resposta à entrada meu ip, por exemplo, depende de uma função especial, socket_getpeername. Fora as questões abstratas dos manuais deve-se aprender o local onde ela será colocada e de como pode-se evitar a sua execução repetitiva, já que o servidor de soquete sobrevive dentro de alguns do…while(true). No exemplo em pauta foi usado o artifício da numeração das linhas de entrada. A criatividade pode nos remeter a outras soluções.

Por outro lado, a linguagem de entrada é demasiadamente simples e se encaixa no mais baixo nível da hierarquia das linguagens: uma linguagem regular. Além disso, a aplicação do exemplo, isto é, o Servidor usa uma regra básica de somente executar o que reconhece previamente (já que são poucos e bem definidos comandos), repassando de volta ao Cliente a entrada que ela não consegue interpretar. Contudo, uma aplicação, via de regra, tende a complicar o meio de campo participando daquele conjunto indesejável, da indecidibilidade. Há uma linha de pesquisa muito interessante, denominada “A ciência da inseguridade”, nomeada pelo Len Sassaman (morto prematuramente aos 31 anos), Meredith L Patterson, Sergey Bratus e outros. Vale a pena um atento olhar no sítio desta turma, em [4], para garantir que nossas preocupações estejam sólidas em relação aos problemas que ocorrem quando se deseja programar de forma segura. Este mesmo grupo expõe uma questão bastante convincente: protocolos são tão complexos (aka, BGP), que verificar se diferentes implementações atendem às especificações originais é um problema indecidível.

Por fim, se o Servidor for mais complexo no sentido de precisar de reconhecer muitos comandos ou de uma linguagem mais complexa, algumas regras serão observadas, até por recomendação do pessoal do projeto LANGSEC, como por exemplo garantir que o “reconhecedor” da entrada seja gerado por uma gramática, preferencialmente regular ou no máximo, livre de contexto (visível na Hierarquia de Chomsky, mostrada na figura abaixo). Além de outras recomendações, evidentemente!

Classificação de gramáticas formais, segundo Chomsky.

 

Referências

 


1. Wikipedia. Berkeley sockets. Wikipedia. [Online] [Citado em: 02 de março de 2012.] http://en.wikipedia.org/wiki/Berkeley_sockets.
2. The PHP Group. Sockets. PHP. [Online] [Citado em: 1 de março de 2012.] http://www.php.net/manual/en/book.sockets.php.
3. Hacking, Jon Erickson. Hacking. [trad.] Marcelo Madeira e Henriqueta Grubba. 1. São Paulo : Digerati Books, 2009. ISBN 978-85-60480-30-2.
4. Sassaman, Len, Patterson, Meredith L. e Bratus, Sergey. LANGSEC: Language-theoretic Security. [Online] http://langsec.org.

Linha Defensiva, o selo site seguro e o Teorema da Parada

Quero reparar um pequeno equívoco, de minha parte. O Fabio Assolin, em mensagem na lista GTS, em novembro de 2008, (aqui), divulgou uma iniciativa da Linha Defensiva1 relativa à criação de um logo com o texto “Este sáitio é segúrio! Eu agarântio!”, associado à conhecida figura do Sô Cleyson. Algumas pequenas reações vieram em seguida: a, b (minha), c, d, e, f, g e outras. Não estou preocupado em entrar no mérito das respostas, mas sim adicionar um argumento, para assegurar, que o ponto de vista da Linha Defensiva está correto e preciso. Ao mesmo tempo, na medida da disponibilidade de meu tempo irei colocar a figura abaixo e suas variações, nos meus sítios:

Achei que a Linha Defensiva foi pragmática em mudar o logo. Na realidade usou o bom senso e exibiu uma bela noção de objetividade em relação ao resultado desejado.

A abordagem que segue, está disponível em prosa e vastamente, se fizermos uma pesquisa por “teorema da parada”. Uma interessante, clara e didática prosa, em abordagens de segurança, está em Duklin2. Em verso, a bela e famosa prova, do Prof. Geoffrey K. Pullum3.

A questão está em uma simples pergunta, portanto: é possível desenvolver um algoritmo (ou programa) que seja capaz de garantir que um sítio é seguro? Mais simples é a resposta: não!*.

Duklin2 é claríssimo e incisivo: Nenhum programa pode dizer (ou explicar) o que um outro programa poderia fazer.

HTML ou qualquer recurso derivado e usado para desenvolver sítios na Web (PHP, ASP, Java, etc.) são linguagens de programação.

Linguagens de programação são sistemas formais. Gödel, por volta de 1932, ao responder a um dos famosos 23 problemas de Hilbert (apresentados em 8 de agosto de 1900, no Congresso Internacional de Matemática em Paris como um desafio para o novo século que estava iniciando), provou que sistemas formais são inconsistentes e incompletos. Por exemplo, a aritmética (ou matemática) é um sistema formal, logo … Na realidade, a prova de Gödel foi sobre a aritmética. Pouco tempo depois, surgiu Turing, com sua famosa Máquina de Turing que fez Alonso Church propor a tese, em linguagem coloquial: um algoritmo é computável se ele for executável em uma Máquina de Turing. Na sequência surgiu, finalmente, o problema da Parada: é possivel executar em uma Máquina de Turing, um programa que receba como entrada um outro programa e suas respectivas entradas? Executar, no sentido de parar, após um tempo finito. A resposta é não*, como já sabemos.

Com esta abordagem informativa, mas cheia de referências, nas quais o formalismo pode ser levantado, a Linha Defensiva está correta! E, quem estiver pagando para colocar um logo de sítio seguro em suas páginas de Web ou para avaliar sua segurança está, literalmente, caíndo no conto do vigário.

Uma bela, completa e didática descrição sobre o trabalho de Gödel e outros, pode ser vista em [4].

Referências:
[1] Linha Defensiva, Este site é seguro. Não Duvide.
[2] Duklin, P., CAN STRONG AUHENTICATION SORT OUT PHISHING AND FRAUD?, Virus Bulletin Conference, October 2006.
[3] Pullum, G. K., SCOOPING THE LOOP SNOOPER A proof that the Halting Problem is undecidable, School of Philosophy, Psychology and Language Sciences, University of Edinburgh, 2008.
[4] Singh, S., O último teorema de Fermat: a história do enigma que confundiu as maiores mentes do mundo durante 358 anos, Record, 2004.

* No sentido de indecidível.

%d blogueiros gostam disto: