Somalis in Uganda and Germany

Os resultados da execução do motor de geração com a gramática expandida utili- zando apenas as restrições são apresentados na tabela 6.4. Para esta gramática todos os não-terminais foram utilizados na execução 7. Ela tem sua saturação em 16 passos de derivação. O custo para a utilização de todos os não-terminais foi alto em relação ao tempo de geração e o número de sentenças geradas.

6.2 Avaliação dos Resultados 74 Ord. Exec. maxDerivLen Tempo Exec. C. NT Num. Sentenças

1 10 0:01.80 60% 86 2 11 2:46.02 87.50% 2780 3 12 73:15.00 97.50% 38224 4 13 158:59.00 97.50% 70856 5 14 282:31.00 97.50% 116648 6 15 375:53.00 97.50% 116648 7 16 456:12.00 100% 141128

Tabela 6.4: Resultados da execução da gramática expandida. Apenas com restrições. na tabela 6.5. Para este grupo de execuções o critério de cobertura foi satisfeito na execução 7. Apesar da satisfação deste critério o uso total dos não-terminais não foi atingido, isso porque existem terminais na gramática que se repetem durante a definição dos não-terminais. Em todas as execuções houveram um maior número de sentenças não produzidas devido ao mecanismo de previsão. Como consequência, houve uma redução do tempo de execução do processo de geração em relação às execuções utilizando apenas os controles de derivações. Também pode-se notar uma redução significativa do número de sentenças geradas para a satisfação do critério em questão, tendo como consequência a redução do tempo de execução do conjunto de sentenças durante a realização dos testes.

Ord. Exec. maxDerivLen Tempo Exec. C. NT C. Term. Num. Sentenças

1 10 0:00.31 60% 69.70% 11(3-72) 2 11 0:03.99 85% 90.91% 18(102-2660) 3 12 0:49.04 92.50% 96.97% 21(1104-37099) 4 13 1:50.51 92.50% 96.97% 21(2083-68752) 5 14 2:06.32 92.50% 96.97% 21(2407-114220) 6 15 2:10.71 92.50% 96.97% 21(2407-114220) 7 16 1:42.08 95% 100% 22(1822-139284)

Tabela 6.5: Resultados da execução da gramática expandida: Critério de cobertura de terminais.

Por último os resultados da execução da gramática com o critério de cobertura de regras de produção são apresentados na tabela 6.6. De maneira semelhante ao critério anterior este teve sua satisfação atingida na execução 7. De forma semelhante ao critério anterior, foram apresentadas reduções em relação ao número de sentenças geradas e tempo de geração. A proporção entre descartes e previsões também favoreceu as previsões, justificando assim a redução no tempo de geração.

Como resultado do processo de geração de sentenças para a gramática expandida temos a satisfação dos critérios de cobertura de terminais e produções. Em ambos os casos foi necessário a execução permitindo 16 passos de derivação para a sua satisfação. Este número é justificado por a gramática precisar no mínimo de 16 passos para o uso

6.3 Conclusão 75 Ord. Exec. maxDerivLen Tempo Exec. C. NT C. RP Num. Sentenças

1 10 0:00.69 60% 54.55% 11(3-72) 2 11 0:11.19 87.50% 86.36% 22(102-2656) 3 12 2:37.92 97.50% 96.97% 25(1173-37026) 4 13 3:55.39 97.50% 96.97% 25(2341-68490) 5 14 5:16.99 97.50% 96.97% 25(2953-113670) 6 15 5:27.05 97.50% 96.97% 25(2953-113670) 7 16 3:43.80 100% 100% 26(1883-139219)

Tabela 6.6: Resultados da execução da gramática expandida: Critério de cobertura de regras de produção.

de todos os não-terminais, como pode ser visto nos resultados da execução apenas com controles de derivação. Através do uso dos critérios de cobertura o número de sentenças geradas foi reduzido em relação as execuções com controle de derivações. Além disso, o tempo de geração também foi reduzido com o uso destes critérios. Esta última redução está diretamente relacionada com o número de sentenças que não foram geradas devido a atuação das técnicas de previsões existentes em ambos os critérios.

6.3

Conclusão

Neste capítulo foi apresentado o estudo de caso que consistiu da aplicação da ferra- menta à geração de casos de teste para a notação B. Foram apresentadas duas gramáticas extraídas da notação B e os resultados obtidos a partir da execução de ambas foram avaliados.

Com este estudo de caso foi possível observar que a ferramenta gera um conjunto de casos de teste para uma determinada gramática. Também foi possível observar que através do uso dos critérios de cobertura o conjunto de sentenças geradas é reduzido. O conjunto gerado tem um nível de qualidade satisfatório já que foi gerado utilizando um critério de cobertura. O tempo de geração gasto utilizando estes critérios também é reduzido em relação ao tempo gasto utilizando apenas os controles de derivações.

76

7

Trabalhos Relacionados

Neste capítulo são descritos trabalhos que de alguma forma relacionam-se ao presente estudo. Para facilitar a leitura, foram criadas seções distintas, cada uma contendo um grupo de trabalhos identificado como sendo de relevância para esta dissertação.

Inicialmente, na seção 7.1, são relatados os estudos sobre geradores de sentenças que têm como origem uma gramática. Na seção 7.2, são apresentados os estudos relativos à geração levando em consideração os vários tipos de semântica.

7.1

Geração Baseada em Gramáticas

A geração de dados de teste construídos a partir de uma representação formal de uma gramática não é recente. O primeiro esforço nesta direção foi feito para elevar a qualidade dos compiladores. Sander [SANDER, 1962] foi o precursor nesta área, apresentando em 1962 um gerador de dados de teste para compiladores Cobol. Em 1970 Hanford [HAN- FORD, 1970] apresenta um algoritmo para a geração de dados de teste para compiladores FORTRAN e PL/1. Este gerador usa uma representação de gramática chamada gra- mática dinâmica, que consiste de uma gramática livre de contexto contendo instruções para modificar sua estrutura. Outro trabalho que trata da geração para uma linguagem específica é apresentado em [WICHMANN; JONES, 1976]. Nele a geração de sentenças para compiladores da linguagem ALGOL 60 é descrita. O trabalho apresenta como diferencial a geração de sentenças que trabalham com situações limítrofes definidas para cada com- pilador. Existe neste trabalho uma tentativa insatisfatória, segundo o autor, de geração de sentenças válidas em relação à semântica.

Dentro da mesma linha, o trabalho apresentado por Purdom [1972] define um algo- ritmo para a geração de sentenças a partir de uma gramática livre de contexto. Esta gramática deve ter a seguinte característica: o seu símbolo inicial não pode ser utilizado no lado direito de nenhuma regra de produção. Neste trabalho apenas aspectos da sintaxe da linguagem são trabalhados pelas sentenças geradas. O algoritmo tem como objetivo

7.1 Geração Baseada em Gramáticas 77

a geração de um conjunto reduzido de sentenças que satisfaça o critério de cobertura de regras de produção. Durante a execução do algoritmo três estruturas de dados são construídas: (1) a estrutura SLEN que mantém informação sobre o tamanho da menor string gerada a partir de uma determinada regra de produção, (2) RLEN que mantém a informação do tamanho da menor string que pode ser derivada no lado esquerdo de uma regra de produção se esta regra for usada, e (3) PREV é a estrutura que contém o número da regra de produção que deve ser utilizada para introduzir um não-terminal na menor derivação possível. Apesar do fornecimento destas estruturas de dados, o autor apresenta o algoritmo de maneira esquemática. Isto, de acordo com o autor, porque várias estruturas são simples de compreender e difíceis de implementar. Logo, esta apresentação é passível de interpretações e dúvidas.

Em [MALLOY; POWER, 2001] é apresentada uma interpretação e implementação do algoritmo proposto por Purdom. Esta implementação utiliza a linguagem C++ na sua codificação e é dividida em três fases com o intuito, segundo os autores, de deixar o al- goritmo mais claro. A primeira fase é responsável pelo cálculo das estruturas SLEN e RLEN, mesmas estruturas apresentadas no trabalho original. Na segunda fase é compu- tado o valor da estrutura PREV. A terceira e última fase utiliza as estruturas computadas previamente na geração das sentenças. Esta terceira fase tem um destaque especial por ser reformulada pelos autores para esclarecer seu funcionamento e deixá-la mais modular. Além disso, eles também apresentam um estudo de caso do uso da sua implementação para as gramáticas das linguagens ANSI C e GNU C++. Em [MALLOY; POWER, 2005] foi proposta especificação e subsequente implementação do algoritmo, proposto em seu trabalho anterior, codificado na linguagem Python. Neste último os autores afirmam uma redução em relação ao tamanho da sua implementação, tendo a original em C++ cerca de 3000 linhas de código e a última menos de 500 linhas de código em Python.

A abordagem proposta por Purdom difere do presente trabalho em relação à forma como a gramática é representada e utilizada pelo seu algoritmo. Além desta diferença, também é notada uma divergência na forma em que o seu algoritmo e o motor de geração trabalham. Em Purdom a gramática é recebida como uma estrutura estática para o processamento pelo algoritmo, já no segundo ela é utilizada tanto para a representação quanto como para definir as operações que serão utilizadas para a geração das sentenças. De fato, o nosso algoritmo gerador está distribuído pela definição da gramática, já que cada parte da representação da gramática é feita através de uma operação. Com esta abordagem temos a implementação de componentes de processamento isolados simples que são compostos no motor de geração para a elaboração das sentenças. Uma desvantagem

7.1 Geração Baseada em Gramáticas 78

em relação ao trabalho proposto é que se torna difícil a visualização da estrutura como um todo, desta forma otimizações em relação à geração de conjuntos mínimos de sentenças se tornam mais complexas. Uma vantagem do nosso trabalho em relação ao proposto pelo autor é a possibilidade de utilizar diferentes critérios de cobertura para a geração das sentenças, já que no seu trabalho o autor apresenta um algoritmo especifico para o critério de cobertura de regras de produções.

Em [LÄMMEL, 2001] são apresentados dois critérios alternativos ao critério de cober- tura de regras de produção utilizado por Purdom, isto porque o critério original não tem a capacidade de detectar erros simples entre a linguagem implementada pelo compilador e a especificada pela gramática. Lämmel motiva seu trabalho no campo da recuperação de gramáticas, especialmente nas situações em que elas não estão acessíveis ou não têm um nível de confiança desejado em relação a correção e completude. Além da definição dos critérios, o autor também estabelece como eles devem ser utilizados para a avaliação e a geração de um conjunto de casos de teste. Apesar do trabalho proposto prover a infra- estrutura adequada para a implementação do critério de cobertura, este critério proposto por Lämmel não é implementado na nossa ferramenta.

Lämmel e Schulte [2006] apresentam uma abordagem combinatória para o teste de software baseados em gramáticas. No trabalho os autores propõem algumas estruturas de controle para limitar a geração combinatória de todas as possibilidades de derivação de uma gramática. A gramática dada como entrada ao processo é descrita através de uma notação que é baseada na notação EBNF, o qual mescla assinaturas e anotações que são utilizadas para declarar as estruturas de controle. As estruturas de controle definidas são: controle sobre o número de passos de derivação a partir de um não-terminal; restrição da quantidade de argumentos que serão combinados na geração de um não-terminal; restrição ao número de repetições (número mínimo e máximo) de uma construção de repetição zero ou mais; limitação em relação à ordem dos argumentos utilizados para uma assinatura de um termo, e em relação à duplicação de argumentos na assinatura que define um termo. Estas estruturas têm uma apresentação formal no trabalho e um critério de cobertura baseado nelas é estabelecido pelos autores.

Algumas das estruturas de controle definidas em [LÄMMEL; SCHULTE, 2006] que res- tringem a altura da árvore de derivação e número de recursões para as repetições são semelhantes às propostas neste trabalho. O controle de altura da árvore de derivação no trabalho proposto é baseado na altura máxima atingida durante o processo como um todo e a apresentada no trabalho do autor é baseada na derivação de um não-terminal espe-

7.2 Geração Baseada em Semântica 79

cífico. Também é fornecida neste trabalho uma estrutura para o controle de ciclos para cada símbolo não-terminal que também está presente no trabalho do autor. O controle do número de recursões de um determinado símbolo é feito, no presente trabalho, através do controle dos ciclos apresentados durante a derivação do símbolo, não existindo assim uma construção específica para este tipo de controle como é apresentado no trabalho dos autores em questão. Além disto, os autores fornecem algumas estruturas específicas para controles adicionais, como por exemplo a ordenação dos argumento e a sua duplicação.

Todos os trabalhos apresentados até então só levam em consideração os testes positi- vos: sentenças que estão de acordo com a especificação da gramática. Porém, em várias situações, testes com sentenças que não estão contidas na linguagem gerada por determi- nada gramática são necessários. Em [ZELENOV; ZELENOVA, 2005] são definidos critérios de cobertura relativos aos testes negativos. Além da proposta dos critérios também foram criados métodos para a geração de conjunto de testes que satisfazem alguns dos critérios apresentados. A satisfação dos critérios por estes conjuntos de teste são feitas através de provas formais, assim garantindo a cobertura total dos critérios.

7.2

Geração Baseada em Semântica

A geração de sentenças baseando-se apenas na gramática da linguagem limita-se aos aspectos estruturais das entradas reconhecidas pelas aplicações em teste. Uma vez testa- dos os aspectos deste nível se faz necessário o teste dos aspectos semânticos do software sob teste.

O primeiro trabalho que tenta tratar deste tipo de teste é [WICHMANN; JONES, 1976], que foca no teste dos compiladores da linguagem ALGOL 60. Porém a iniciativa não surtiu o efeito esperado, uma vez que o componente de análise semântica não foi devidamente testado.

Em [DUNCAN; HUTCHISON, 1981] é apresentada uma abordagem de geração baseada na especificação da semântica descrita através de uma gramática de atributos [KNUTH, 1968; GRUNE; JACOBS, 2008]. O foco do trabalho é a validação da especificação e veri- ficação de uma implementação em relação à especificação. É apresentada a geração de dados de teste e seus resultados esperados. A validação da especificação seria realizada manualmente através da análise destes dados e resultados gerados. Já a verificação da implementação é feita através da execução dos casos de teste por um driver externo. No trabalho são apresentados três estudos de casos relacionados a compiladores, especificação

7.2 Geração Baseada em Semântica 80

de um programa de ordenação e outro de reformatação de texto.

Bazzichi e Spadafora [1982] apresentam um sistema de geração de casos de teste com semântica estática válida. O foco do trabalho são os compiladores, sendo testados os componentes de análise léxica, sintática e semântica. Além destes componentes, tam- bém são testadas as funcionalidades de diagnóstico e tratamento de erros. Condições limites do compilador também são testadas pelos casos de teste gerados. O sistema re- cebe como entrada uma gramática livre de contexto chamada de contex-free parametric grammar [PAPASPYROU; VESCOUKIS, 1999], que consiste de uma gramática que pode ter variáveis associadas aos não-terminais. Este tipo de gramática é considerado de dois níveis como as gramáticas de atributos. Uma vez formalizada a linguagem através da notação de entrada um algoritmo de geração é utilizado para gerar as sentenças. O algoritmo uti- lizado neste processo é uma adaptação do algoritmo proposto por Purdom [1972] ajustado para suportar este tipo específico de gramáticas.

Nos trabalhos anteriores são apresentadas várias formas de geração de testes baseados na especificação semântica. Apesar destes gerarem casos de teste, em nenhum deles é proposto um critério de cobertura em relação a esta especificação semântica. Nesta dire- ção Harm e Lämmel [2000] propõem um critério de cobertura que leva em consideração tanto os aspectos estruturais ou sintáticos quanto os aspectos semânticos. Este novo crité- rio proposto considera duas dimensões de programas declarativos de primeira ordem, tais como: programas lógicos, especificações algébricas construtivas e gramáticas de atributos. No caso de uma gramática de atributos a dimensão sintática da gramática é a que corres- ponde à uma gramática livre de contexto e a dimensão semântica seria a parte que trata dos atributos da gramática. Já nos programas lógicos uma dimensão seria o esqueleto da árvore de prova e a outra estaria ligada aos parâmetros associados aos literais da árvore de prova. Através do critério, as duas dimensões destes programas podem ser trabalhados separadamente ou em conjunto. A cobertura completa do critério não é possível de ser satisfeita em algumas situações. Por conta desta limitação os autores propõem um critério mais relaxado em relação ao original em que é possível gerar um conjunto de testes que o satisfaça. Para este segundo critério de cobertura é apresentado um algoritmo de geração de casos de teste que gera um conjunto de testes que satisfazem o critério.

Em [KALINOV et al., 2003] são introduzidos critérios de cobertura relativos à semântica estática e dinâmica definidos através do formalismo Montage [KUTTER; PIERANTONIO, 1997]. Este formalismo define aspectos da sintaxe, semântica estática e dinâmica. No trabalho além dos critérios de cobertura também é apresentado um sistema para geração

7.3 Considerações Finais 81

de um conjunto de casos de teste que satisfazem os critérios propostos. Este sistema gerador gera sentenças positivas e negativas de teste.

7.3

Considerações Finais

Neste capítulo foram apresentados alguns trabalhos que têm ligação direta com este trabalho. Eles foram divididos em relação ao foco dado ao tipo de especificação utilizada durante o processo de geração de dados e casos de teste.

Na seção 7.1 foram apresentados trabalhos que levam em consideração a sintaxe das linguagens dos casos de teste gerados. Também foram apresentados alguns trabalhos que propõem novos critérios de cobertura baseados na sintaxe e na gramática das linguagens testadas.

A seção 7.2 apresentou vários trabalhos que têm como objetivo testar a semântica associada às linguagens através da geração automática de casos de teste. Dentre estes al- guns focam exclusivamente no segmento da semântica estática, outros vão além e também trabalham a semântica dinâmica. Em relação à semântica este levantamento nos fornece um panorama da área para dar continuidade ao desenvolvimento do nosso trabalho em direção a geração de casos de teste levando em consideração aos vários tipos de semântica. Nenhum dos trabalhos pesquisados apresenta um esquema genérico para implemen- tação de critérios de cobertura em que estes critérios possam ser utilizados durante a ge- ração. Nosso trabalho contribui nesta direção fornecendo uma ferramenta genérica para implementação dos critérios de cobertura. Além disso, este trabalho também fornece a possibilidade de se gerar sentenças para qualquer linguagem que esteja formaliza através da notação EBNF, o que em alguns dos trabalhos pesquisados não é possível.

82

8

Considerações Finais

As aplicações que têm sua entrada formalmente definida através de gramáticas livres de contexto possuem como diferencial para a elevação de seu nível de qualidade a possi- bilidade de automação do seu processo de teste. Um exemplo tradicional de um grupo de software desta categoria são os compiladores (e similarmente, interpretadores e tradutores em geral). Através da utilização dos critérios funcionais de teste é possível proporcionar uma maior confiança nestas aplicações pela geração sistemática e automatizada de casos de teste. Dentro deste cenário as seções seguintes apresentam as contribuições e os pontos em que o presente trabalho pode ser evoluído.

8.1

Contribuições

O trabalho apresentado contribui para a elevação da qualidade desta categoria de software uma vez que a sua utilização fornece casos de teste que procuram avaliar as principais características da aplicação. A ferramenta apresentada neste trabalho utiliza o conceito de critério de cobertura para proporcionar tal elevação do nível de qualidade. Os critérios de cobertura ainda podem ser escolhidos com a finalidade de testar determinados aspectos do software sob teste. Também é possível a criação e adaptação de novos critérios de cobertura utilizando a infraestrutura fornecida pela ferramenta, que é descrita no trabalho na seção 5.4.

Outra contribuição do trabalho é a avaliação do uso da linguagem Lua na implementa- ção deste tipo de ferramenta. A linguagem foi escolhida por fornecer conceitos de corotinas e funções como valores de primeira classe, o que facilitou e simplificou a implementação da ferramenta. Além destes conceitos simplificarem e flexibilizarem a implementação, eles forneceram mecanismos que facilitaram a extensão da ferramenta, como pode ser visto na implementação dos critérios de cobertura apresentada no capítulo 5. Outra característica importante da linguagem é a sua portabilidade, facilitando a utilização da ferramenta em vários sistemas operacionais e diferentes máquinas.

8.2 Trabalhos Futuros 83

Uma decisão importante para o trabalho foi o uso do ambiente Meta-Environment. Através da sua utilização a implementação do parser para a notação de entrada foi sim- plificada. A tradução desta notação para uma utilizada pelo motor de geração foi feita de

In document Refugees’ Self-Reliance and Livelihood Strategies: A Comparative Study of Uganda and Germany (sider 69-0)