VivianeMR-DISSERT

Prévia do material em texto

Viviane de Menezes Ramalho
Geração de Testes a partir de gramáticas: áreas de
aplicação
Natal/RN
2013
Viviane de Menezes Ramalho
Geração de Testes a partir de gramáticas: áreas de
aplicação
Dissertação apresentada ao Programa
de Pós-graduação em Sistemas e Com-
putação do Departamento de Informática
e Matemática Aplicada da Universidade
Federal do Rio Grande do Norte, como
requisito parcial para a obtenção do grau de
Mestre em Ciência da Computação
Orientadora: Profa.Dra. Anamaria Martins Moreira
Universidade Federal do Rio Grande do Norte
Centro de Ciências Exatas e da Terra
Departamento de Informática e Matemática Aplicada
Programa de Pós-graduação em Sistemas e Computação
Natal/RN
2013
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
UFRN / Biblioteca Central Zila Mamede 
Catalogação da Publicação na Fonte 
 
 
Ramalho, Viviane de Menezes. 
 Geração de testes a partir de gramáticas: áreas de aplicação / Viviane 
de Menezes Ramalho. – Natal, RN, 2013. 
 91 f.: il. 
 
 Orientadora: Profa. Dra. Anamaria Martins Moreira. 
 
 Dissertação (Mestrado) – Universidade Federal do Rio Grande do 
Norte. Centro de Ciências Exatas e da Terra. Programa de Pós-Graduação 
em Sistemas e Computação. 
 
1. Teste de software – Dissertação. 2. Geração de testes - Dissertação. 
3. Gramáticas - Softwares - Dissertação. I. Moreira, Anamaria Martins. II. 
Universidade Federal do Rio Grande do Norte. III. Título. 
 
RN/UF/BCZM CDU 004.415.53 
 
 
 
 
 
 
 
Termo de Aprovação
Viviane de Menezes Ramalho
Geração de Testes a partir de gramáticas: áreas de aplicação
Esta dissertação foi julgada adequada para obtenção do título de mestre em Sistemas e
Computação e aprovada em sua forma final pelo Programa de Pós-Graduação em Sistemas
e Computação do Departamento de Informática e Matemática Aplicada da Universidade
Federal do Rio Grande do Norte.
Profa. Dra. Anamaria Martins Moreira
Universidade Federal do Rio Grande do
Norte
(Orientadora)
Prof. Dr. Gibeon Soares de Aquino Júnior
Universidade Federal do Rio Grande do
Norte
Profa. Dra. Patrícia Duarte de Lima
Machado
Universidade Federal de Campina Grande
Aos meus pais, Vanci e Marilene
Agradecimentos
Em primeiro lugar agradeço a Deus, sem Ele nada seria possível.
Aos meus pais, Vanci e Marilene, pelo apoio, dedicação, amor e incentivo que recebo
em todos os momentos da minha vida.
Aos meus irmãos, Vanderlan e Vancilene, pelo incentivo e amizade.
A Marcos - meu esposo - pelo carinho, compreensão, por estar ao meu lado e sempre
acreditar em mim.
As minhas tias, Ester e Nautília, que sempre acreditam em mim e me ajudam em
todos os momentos.
À Régia, minha amiga sempre presente, que me incentiva em tudo que faço, com
palavras de ânimo e encorajamento.
À minha orientadora, Anamaria Moreira Martins, por tudo que com ela aprendi, pela
compreensão, paciência e principalmente pela confiança. Seu apoio foi fundamental para
a conclusão deste trabalho.
Aos meus amigos Sarah, Ernesto, Cleverton, Sidney, Daniel e Haniel, pela ajuda e por
todos os bons momentos que passamos juntos.
Aos funcionários e professores que fazem parte do DIMAP.
“A maior empreitada para que qualquer movimento tenha sucesso
é manter juntas as pessoas que a formaram”
Martin Luther King Jr
Sumário
Lista de Figuras
Lista de Tabelas
Resumo
Abstract
1 Introdução p. 14
1.1 Objetivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 16
1.1.1 Objetivos Gerais . . . . . . . . . . . . . . . . . . . . . . . . . . p. 16
1.1.2 Objetivos Específicos . . . . . . . . . . . . . . . . . . . . . . . . p. 16
1.2 Organização do Trabalho . . . . . . . . . . . . . . . . . . . . . . . . . . p. 16
2 Fundamentação Teórica p. 18
2.1 Gramáticas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 18
2.1.1 Gramáticas Livres de Contexto . . . . . . . . . . . . . . . . . . p. 20
2.1.2 Gramáticas ambíguas . . . . . . . . . . . . . . . . . . . . . . . . p. 21
2.2 Testes de Software . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 22
2.2.1 Critérios de Cobertura . . . . . . . . . . . . . . . . . . . . . . . p. 24
2.2.2 Critérios de Teste Baseados em Sintaxe . . . . . . . . . . . . . . p. 25
3 Lua Language Generator (LGen) p. 29
3.1 Definição de LGen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 29
3.1.1 Controle de Derivações . . . . . . . . . . . . . . . . . . . . . . . p. 29
3.2 Funcionamento de LGen . . . . . . . . . . . . . . . . . . . . . . . . . . p. 32
3.3 Implementação de LGen . . . . . . . . . . . . . . . . . . . . . . . . . . p. 36
3.3.1 Arquitetura de LGen . . . . . . . . . . . . . . . . . . . . . . . . p. 36
3.3.2 Critérios de Cobertura . . . . . . . . . . . . . . . . . . . . . . . p. 37
3.3.2.1 Critério de Cobertura de Terminais . . . . . . . . . . . p. 37
3.3.2.2 Critério de Cobertura de Regras de Produções . . . . p. 37
4 Aplicações com Gramáticas p. 38
4.1 Conjunto de trabalhos que utilizam gramáticas para testes . . . . . . . p. 39
4.1.1 Linha de Produto de Software . . . . . . . . . . . . . . . . . . . p. 39
4.1.2 Teste de Firewall . . . . . . . . . . . . . . . . . . . . . . . . . . p. 42
4.1.3 Analisador feed RSS . . . . . . . . . . . . . . . . . . . . . . . . p. 46
4.1.4 Teste de Protocolo de Rede . . . . . . . . . . . . . . . . . . . . p. 47
4.1.5 Software Voip . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 48
4.2 Conjunto de trabalhos que utilizam gramáticas para diversos fins . . . . p. 49
4.2.1 Rede de Sensores . . . . . . . . . . . . . . . . . . . . . . . . . . p. 49
4.2.2 Bioinformática . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 51
4.2.3 Processamento de Imagens . . . . . . . . . . . . . . . . . . . . . p. 52
4.2.4 Reconhecimento da fala . . . . . . . . . . . . . . . . . . . . . . p. 53
4.2.5 Conclusão . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 53
5 Análise das Gramáticas Identificadas p. 55
5.1 Ambiguidade . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 55
5.2 Gramáticas Probabilísticas . . . . . . . . . . . . . . . . . . . . . . . . . p. 55
5.3 Uso de Recursão . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 56
5.4 Presença de identificadores . . . . . . . . . . . . . . . . . . . . . . . . . p. 56
5.5 Tamanho da gramática . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 57
5.6 Resumo das aplicações que utilizam gramáticas . . . . . . . . . . . . . p. 60
5.6.1 Gramáticas que são utilizadas para descrever configurações . . . p. 60
5.6.2 Gramáticas que são utilizadas para reconhecimento de padrões . p. 60
5.6.3 Gramáticas que são utilizadas para especificações de arquivos . p. 61
6 Estudos de Caso p. 62
6.1 Critérios de avaliação de LGen . . . . . . . . . . . . . . . . . . . . . . . p. 63
6.1.1 Estudo do comportamento de LGen durante o processo de geração
das sentenças . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 63
6.1.2 Satisfação dos critérios de cobertura implementados em LGen . p. 63
6.1.3 Capacidade de detecção de falhas no software que será testado . p. 64
6.2 Estudos de Caso I - Descrições de configurações de software . . . . . . p. 64
6.2.1 Linha de Produto de Software . . . . . . . . . . . . . . . . . . . p. 64
6.2.2 Teste de Firewall . . . . . . . . . . . . . . . . . . . . . . . . . . p. 69
6.3 Estudos de Caso II - Especificações de arquivos . . . . . . . . . . . . . p. 71
6.3.1 Analisador Feed RSS . . . . . . . . . . . . . . . . . . . . . . . . p. 71
6.3.2 Processamento de Imagens . . . . . . . . . . . . . . . . . . . . . p. 72
6.4 Conclusão . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 74
7 Considerações Finais p. 77
7.1 Contribuições . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 77
7.2 Trabalhos Futuros . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . p. 78
Referências p. 80
8 Apêndice p. 84
8.1 Gramática EBNF - Firewall Completa . . . . . . . . . . . . . . . . . . p. 84
8.2 Gramática EBNF - HIS . . . . . . . . . . . . . . . . . . . . . . . . . . p. 85
8.3 Gramática EBNF - Model Transformation . . . . . . . . . . . . . . . . p. 86
8.4 Gramática EBNF - ATM . . . . . . . . . . . . . . . . . . . . . . . . . . p. 88
8.5 Gramática EBNF - Mobile Phone . . . . . . . . . . . . . . . . . . . . . p. 88
8.6 Gramática EBNF - Digital Video System . . . . . . . . . . . . . . . . . p. 89
Lista de Figuras
1 Hierárquia de Chomsky [Rogers, 2012] . . . . . . . . . . . . . . . . . . p. 19
2 Árvore para 000#111 da gramática G1 [Sipser, 1996] . . . . . . . . . . p. 21
3 Árvores de Derivação para a string 1 + 2 ∗ 3 + 4 [Jiang et al., 2010] . . p. 22
4 Representação da definição de critério de cobertura . . . . . . . . . . . p. 25
5 Derivação para o maxCycles igual a 1 . . . . . . . . . . . . . . . . . . . p. 30
6 Derivação para o maxCycles igual a 2 . . . . . . . . . . . . . . . . . . . p. 30
7 Árvore de derivação para o MaxDerivLen igual a 1 . . . . . . . . . . . p. 31
8 Árvore de derivação para o MaxDerivLen igual a 2 . . . . . . . . . . . p. 31
9 Arquitetura de LGen [hentz:2010] . . . . . . . . . . . . . . . . . . . . . p. 36
10 Feature Model GPL [Bagheri et al., 2012]. . . . . . . . . . . . . . . . . p. 41
11 Fragmento da gramatica [Hoffman and Yoo, 2005] . . . . . . . . . . . . p. 44
12 Conexão TCP sendo estabelecida [Hoffman et al., 2010] . . . . . . . . . p. 45
Lista de Tabelas
1 Resumo dos operadores suportados pela notação de entrada . . . . . . p. 26
2 Resultados da execução da gramática apenas com as restrições de ciclos
e número de passos de derivação. . . . . . . . . . . . . . . . . . . . . . p. 34
3 Sentenças geradas apenas com as restrições de ciclos e número de passos
de derivação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 34
4 Resultados da execução da gramática com o Critério de Cobertura de
Terminais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 35
5 Sentenças Geradas com o Critério de Cobertura de Terminais . . . . . . p. 35
6 Resultados da execução da gramática com o Critério de Cobertura de
Regras de Produção . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 35
7 Sentenças Geradas com o Critério de Cobertura de Regras de Produção p. 35
8 Gramáticas Gerais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 59
9 Gramáticas de Linguagens . . . . . . . . . . . . . . . . . . . . . . . . . p. 60
10 Gramáticas identificadas nos trabalhos das áreas de Linha de Produto,
Software VoiP e Firewall . . . . . . . . . . . . . . . . . . . . . . . . . . p. 60
11 Gramáticas identificadas nos trabalhos da área de Redes de Sensores . . p. 60
12 Gramáticas identificadas nos trabalhos das áreas de Analisador Feed
RSS, Protocolos de Rede e Processamento de Imagens . . . . . . . . . . p. 61
13 Resultados da execução da gramática apenas com as restrições de ciclos
e número de passos de derivação. . . . . . . . . . . . . . . . . . . . . . p. 65
14 Resultados da execução da gramática com o critério de cobertura de
terminais. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 66
15 Resultados da execução da gramática com o critério de cobertura de
regras de produção. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 66
16 Geração de sentenças com o critério de cobertura de terminais com
MaxDerivLen igual a 6 . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 67
17 Resultados da geração com outros cinco modelos de linha de produto
[Bagheri et al., 2012] . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 69
18 Resultados da execução da gramática com o critério de cobertura de
terminais. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 71
19 Resultados da execução da gramática com o critério de cobertura de
regras de produção. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 71
20 Resultados da execução da gramática com o critério de cobertura de
terminais. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 71
21 Resultados da execução da gramática com o critério de cobertura de
regras de produção. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 72
22 Resultados da execução da gramática apenas com as restrições de ciclos
e número de passos de derivação. . . . . . . . . . . . . . . . . . . . . . p. 73
23 Resultados da execução da gramática com o critério de cobertura de
terminais. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 73
24 Resultados da execução da gramática com o critério de cobertura de
regras de produção. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 74
25 Sentenças geradas com o critério de terminais com MaxDerivlen igual a 4 p. 74
Resumo
O trabalho proposto por Cleverton Hentz (2010) apresentou uma abordagem para
definição de testes a partir da descrição formal das entradas do programa. Considerando
que alguns programas podem ter suas entradas formalizadas através de gramáticas,
como é o caso dos compiladores, é comum o uso de gramáticas livres de contexto para
especificar o conjunto de entradas válidas. No trabalho original foi desenvolvida LGen,
uma ferramenta que consiste na geração automática de testes para compiladores. No
presente trabalho identificamos tipos de problemas recorrentes em diferentes áreas,
onde gramáticas são usadas para descrevê-los, como por exemplo, para especificar
configurações de software, e que são situações potenciais para o uso de LGen. Além
disso, realizamos estudos de caso com gramáticas de domínios diferentes e a partir destes
estudos foi possível avaliar o comportamento e o desempenho de LGen durante o processo
de geração das sentenças, avaliando aspectos como tempo de execução, quantidade de
sentenças geradas e satisfação de critérios de cobertura disponíveis em LGen.
Palavras-chave: teste de software, geração de testes, gramáticas.
Abstract
The work proposed by Cleverton Hentz (2010) presented an approach to define tests
from the formal description of a program’s input. Since some programs, such as compilers,
may have their inputs formalized through grammars, it is common to use context-free
grammars to specify the set of its valid entries. In the original work the author developed
a tool that automatically generates tests for compilers. In the present work we identify
types of problems in various areas where grammars are used to describe them , for example,
to specify software configurations, which are potential situations to use LGen. In addition,
we conducted case studies with grammars of different domains and from these studies it
was possible to evaluate the behavior and performance of LGen during the generation of
sentences, evaluating aspects such as execution time, number of generated sentences and
satisfaction of coverage criteria available in LGen.
Keywords: software testing, test generation, grammars.
14
1 Introdução
O software está presente em todos os segmentos da sociedade e já faz parte do coti-
diano das pessoas. Ele está em todo lugar: nas escolas, nos bancos, nos supermercados,
em automovéis, aparelhos celulares. A utilização de software tem atingido um maior
número de pessoas e a busca por soluções eficazes tem gerado uma preocupação em cons-
truir software confiável. Neste sentido, muitas formas de melhoria nas metodologias de
desenvolvimento de software estão sendo utilizadas.
Devido a essa crescente importância dos sistemas na indústria e na sociedade em
geral, técnicas que auxiliam na produção de software são cada vez mais relevantes
[Hierons et al., 2009]. Diversos métodos e ferramentas buscam melhorar o desenvolvi-
mento, como a utilização de métodos formais para descrever especificações, designs e
testes [Abdurazik, 2000].
O teste é um importante meio de avaliação do software para determinarsua quali-
dade e geralmente consome cerca de 50% dos esforços do processo de desenvolvimento,
sendo considerada uma área importante da engenharia de software [Myers, 2004]. Um dos
pontos fundamentais para que o processo de teste seja apropriado é a definição de uma
especificação clara, precisa e bem estruturada[Lamsweerde, 2000] e uma das maneiras
para que isso aconteça é o uso de métodos formais. As especificações formais possuem
sintaxe e semântica baseadas em fundamentos matemáticos e têm o objetivo de minimizar
falhas em sistemas computacionais, reduzindo erros nas fases iniciais do desenvolvimento
do software [Luo, 2009].
Métodos formais possuem uma sólida base matemática e fornecem estruturas para
especificação, verificação e desenvolvimento de software de forma sistemática. Essa base
matemática possibilita uma especificação e implementação mais clara, precisa e consis-
tente. Uma característica dos métodos formais é o uso de uma notação, que é a lin-
guagem de especificação, com semântica formal e que contribui para eliminar a ambigu-
idade [Plat et al., 1992].
15
Uma das maneiras para se escrever uma especificação formal é através de gramáticas
livres de contexto [Sobotkiewicz, 2008]. Uma gramática livre de contexto é um conjunto de
regras, em que cada regra tem um não-terminal (variável) no lado esquerdo, uma lista de
não-terminais ou terminais no lado direito e uma aplicação de regras gramaticais, chamada
derivação. As gramáticas são tradicionalmente usadas para descrever uma linguagem
ou analisar sentenças em uma linguagem, mas também podem ser usadas para gerar
sentenças, que são interpretadas como casos de testes [Hoffman et al., 2010]. De uma
perspectiva da engenharia de software, uma gramática pode ser considerada tanto como
uma especificação (definição de uma linguagem) como um programa. Elas estão presentes
no desenvolvimento de vários tipos de software e são utilizadas para definir uma sintaxe,
além de outras possibilidades [Lämmel, 2001].
Teste é o principal meio para avaliar o desenvolvimento do software e
pode ser originado de diversos artefatos, tais como: requisitos e especificações
[Ammann and Offutt, 2008]. É uma atividade da engenharia de software, com ciclo de
vida paralelo ao desenvolvimento e tem o objetivo de encontrar erros [Myers, 2004]. Um
erro é definido como a manifestação de algum defeito, um estado interno do software que
é incorreto [Ammann and Offutt, 2008]. Além desta, existem outras definições de erro na
literatura, que apresentam variações de significado segundo a fonte.
A abordagem que utiliza gramáticas livres de contexto para gerar casos de teste com a
sintaxe descrita pela gramática é a geração de testes baseada em gramática(GTBG), que
existe desde a década de 70. Inicialmente, ela foi desenvolvida para gerar o código fonte
para teste de compiladores, onde a gramática livre de contexto especifica a sintaxe da
linguagem. No entanto, o uso de gramáticas tem sido aplicado a muitos outros contextos,
como nas áreas de protocolos de redes e testes de firewall [Hoffman et al., 2010].
No trabalho proposto por [Hentz, 2010] foi desenvolvida uma ferramenta (LGen) para
geração automática de sentenças para testes de tradutores, que utiliza como entrada uma
gramática livre de contexto e gera como saída um conjunto de sentenças para serem
utilizadas como dados de entrada nos casos de testes 1. LGen possibilita a implementação
de diferentes critérios de cobertura que são usados durante a geração das sentenças. Esses
critérios são utilizados para limitar a quantidade de dados de teste. No trabalho original
foram implementados dois critérios de cobertura: cobertura de terminais e cobertura de
regras de produção, que foram definidos com base nos critérios de cobertura apresentados
1Em nosso trabalho, quando utilizamos LGen não estamos apenas gerando os dados de testes, mas
também identificando os casos de testes. Isso também acontece com as ferramentas apresentadas nos
trabalhos relacionados.
16
por [Ammann and Offutt, 2008].
O presente trabalho tem como objetivo identificar tipos de situações recorrentes em
áreas específicas, onde as gramáticas são utilizadas para descrevê-las e a partir daí, ex-
pandir o escopo de aplicação de LGen para diferentes áreas de aplicação. Pretende ainda
avaliar o LGen, quanto a sua utilidade em diferentes domínios de aplicação.
1.1 Objetivos
1.1.1 Objetivos Gerais
O trabalho proposto tem como objetivo identificar diferentes áreas de aplicação para
testes baseados em gramáticas, expandindo o escopo de aplicação de LGen [Hentz, 2010].
1.1.2 Objetivos Específicos
• Realizar uma revisão bibliográfica para identificar tipos de situações recorrentes em
áreas específicas, onde as gramáticas são utilizadas para descrevê-las.
• Levantar as características das gramáticas apresentadas nos trabalhos identificados
na pesquisa. Esse levantamento será útil para caracterizar cada área de aplicação
quanto às propriedades das suas gramáticas.
• Avaliar se geradores a partir de gramáticas têm potencial para ajudar desenvolve-
dores em seus processos de teste, nas áreas de aplicação selecionadas.
• Avaliar o conjunto de sentenças gerado por LGen. Essa avaliação deve considerar se
o conjunto de sentenças gerado satisfaz a um dos critérios de cobertura disponíveis
na ferramenta.
• Avaliar o comportamento de LGen durante o processo de geração das sentenças.
• Avaliar LGen em situações com gramáticas de tamanho real.
1.2 Organização do Trabalho
Este trabalho está organizado da seguinte forma: a fundamentação teórica está apre-
sentada no capítulo 2. Neste capítulo é feita uma apresentação sobre gramáticas, alguns
17
conceitos de teste de software e geração de teste baseada em sintaxe. No capítulo 3 ap-
resentamos LGen. No capítulo 4 apresentamos as áreas de aplicação selecionadas, que
utilizam gramáticas para descrever tipos de problemas em áreas diversas. O capítulo 5
será apresentada uma análise das gramáticas identificas na pesquisa. Os estudos de casos
são apresentados no capítulo 6. As considerações finais do trabalho são apresentadas no
capítulo 7.
18
2 Fundamentação Teórica
Neste capítulo faremos uma introdução aos conceitos necessários para o entendimento
do nosso trabalho. Iniciaremos com o conceito de gramática e sua classificação, utilizando
alguns exemplos. Em seguida serão apresentados alguns conceitos de Teste de Software,
Critérios de Cobertura e Geração de Testes Baseada em Gramáticas.
2.1 Gramáticas
Uma gramática constitui um sistema formal baseado em regras de substituição, capaz
de gerar cadeias pertencentes a uma determinada linguagem. Essa linguagem possui uma
sintaxe bem definida, de forma que, dada uma sentença, é possível saber se ela pertence
ou não a essa linguagem.
Definição 2.1.1. Gramáticas: Formalmente, uma gramática é uma 4-upla (Σ, V, S, P );
em que Σ representa um conjunto de símbolos terminais, V é um conjunto de símbolos
não-terminais, S representa o símbolo inicial da gramática e pertence à V e P corresponde
às regras de produção que tem seus elementos na forma α → β, tal que α ∈(Σ ∪ V ) * V
(Σ ∪ V ) * e β ∈(Σ ∪ V ) [Jiang et al., 2010].
S -> a | A | C
A -> aa
aC -> ab
Listagem 2.1: Exemplo de uma gramática
A Listagem 2.1 apresenta um exemplo de uma gramática. Neste exemplo, o S repre-
senta o símbolo inicial, os símbolos terminais são a e b. Os símbolos não-terminais são S,
A e C. A gramática possui cinco regras de produção. A notação | é usada para apresentar
as regras de produção com o mesmo lado esquerdo de maneira mais sucinta. Essa notação
representa uma alternativa.
19
A classificação de gramáticas formais é denominada de Hierárquia de Chomsky
[Chomsky, 1964]. Essa classificação é organizada de acordo com as restrições que se im-
põem sobre suas regras de produção. Ela começa pelo tipo 0, com maior nível de liberdade
em suas regras, e aumenta as restrições até o tipo 3.
Figura 1: Hierárquia de Chomsky [Rogers, 2012]
Definição 2.1.2. Seja G = (∑, V, S, P ) uma gramática [Jianget al., 2010].
1. G é também chamada de uma gramática irrestrita ou do tipo 0.
2. G é uma gramática sensível ao contexto ou do tipo 1 se cada produção α → β em
P satisfaz |α| ≤ |β|. Aqui |α| e |β| denotam o comprimento das cadeias, respectiva-
mente.
3. G é uma gramática livre de contexto ou do tipo 2 se cada produção do tipo α→ β
em P satisfaz |α| = 1.
4. G é uma gramática regular ou do tipo 3 se cada produção tem uma das seguintes
formas:
A→ cB, A→ c, A→ �
Onde A e B são símbolos não-terminais e c é um símbolo terminal.
A Hierárquia de Chomsky é representada na Figura 1. Para o nosso trabalho o foco
será nas Gramáticas Livres de Contexto. Estas gramáticas são usadas em aplicações
importantes tal como ocorre na especificação e compilação de linguagens de programação
[Sipser, 1996].
20
2.1.1 Gramáticas Livres de Contexto
As gramáticas livres de contexto tiveram seu início em estudos com linguagens hu-
manas, tendo como objetivo obter maior clareza sobre as relações entre verbo, substantivo
e preposição. Posteriormente, esses estudos foram relevantes para a compreensão dessas
relações. Em termos de aplicação, essas gramáticas têm papel importante na especificação
e compilação de linguagens de programação. Os compiladores e interpretadores possuem
um componente denominado parser . O parser tem a função de extrair o significado de
um programa antes de gerar o código compilado ou realizar execução interpretada. Assim,
as gramáticas livres de contexto auxiliam na construção do parser, uma vez que, muitas
metodologias que utilizam gramáticas estão disponíveis [Sipser, 1996].
Definição 2.1.3. Gramáticas Livres de Contexto: A representação de uma gramática é
dada por uma quádrupla G = (Σ, V, S, P ), onde :
• Σ é um conjunto de terminais ou variavéis.
• V é um conjunto de não-terminais.
• S representa o símbolo inicial, onde S ∈ V .
• P é um conjunto de regras de produção, representado na forma α→ β. Isso significa
que α pode ser substituído por β, em que α e β são símbolos de Σ e/ou V.
A forma para representar uma regra em uma gramática livre de contexto é:
A→ β
Onde A é um símbolo não-terminal e β é uma string de símbolos.
A fim de ilustrarmos a definição de uma gramática livre de contexto, a Listagem 2.2
apresenta a gramática G1.
A -> 0A1
A -> B
B -> #
Listagem 2.2: Gramática G1
A gramática G1 possui três regras de produção. A e B são símbolos não-terminais,
em que A é o símbolo inicial. Os símbolos terminais são representados por 0 ,1 e #. Para
21
gerar uma cadeia, começa-se com o símbolo inicial. As regras de produção são, então,
aplicadas até que uma cadeia que não continha nem o símbolo inicial, nem os designados
símbolos não-terminais, seja produzida. A linguagem formada pela gramática consiste de
todas as cadeias distintas que podem ser geradas dessa forma.
Por exemplo, se considerarmos a Gramática G1 para gerar a string 000#111, a
derivação da string seria:
A =⇒ 0A1 =⇒ 00A11 =⇒ 000A111 =⇒ 000B111 =⇒ 000#111
É possível usar uma estrutura de árvore para representar uma derivação da string. Na
Figura 2 mostramos uma árvore para uma derivação do tipo 000#111, para a gramática
G1.
Figura 2: Árvore para 000#111 da gramática G1 [Sipser, 1996]
O conjunto de todas as cadeias geradas desta maneira é chamado de linguagem de
uma gramática e é representado na forma L(G1) para a gramática G1.
2.1.2 Gramáticas ambíguas
Uma gramática é dita ambígua quando ela é capaz de gerar mais de uma árvore de
derivação para uma mesma sentença.
Definição 2.1.4. Gramáticas Ambíguas: Uma gramática G é ambígua, se há uma
seqüência x ∈ L(G), que possui pelo menos duas árvores de derivação distintas
[Jiang et al., 2010].
Considerando uma gramática ambígua G2. Para esta gramática todas as expressões
aritméticas válidas são compostas de inteiros positivos e pelos símbolos +, *, (,). O
símbolo n é usado para denotar qualquer número inteiro positivo e é tratado como um
símbolo terminal. As produções para esta gramáticas são apresentadas na Listagem 2.3.
22
S -> T + S | S + T | T
T -> F * T | T * F | F
F -> n | (S)
Listagem 2.3: Gramática G2
Esta gramática gera a string 1 + 2 ∗ 3 + 4 ambiguamente. Para esta expressão, duas
árvores distintas são possíveis. As duas árvores são mostradas na Figura 3. A árvore do
lado esquerdo significa que a primeira adição deve ser feita antes da segunda. A árvore
do lado direito diz o contrário.
Figura 3: Árvores de Derivação para a string 1 + 2 ∗ 3 + 4 [Jiang et al., 2010]
Neste exemplo as operações de adição e multiplicação são associativas, por isso, embo-
ra a gramática possibilite derivações diferentes para alguma expressão, sempre resultará
no mesmo valor. No entanto, existem situações em que a diferença na derivação pode
afetar o resultado final.
A importância em apresentar esse tipo de gramática é que elas confundem geradores
e reconhecedores levando a resultados nem sempre desejados - portanto precisa-se ter
atenção ao escrever uma gramática para que não seja ambígua.
2.2 Testes de Software
Para [Myers, 2004], testar um software significa executá-lo com o objetivo de encontrar
erros. À medida que os testes são executados, busca-se identificar esses erros e melhorar
a qualidade do software que está sendo testado. Para testar um software precisamos criar
casos de teste, que têm o objetivo de exercitar os possíveis cenários. Através dos casos
de teste passamos um conjunto de dados de entrada para um sistema e analisamos os
resultados produzidos. Um bom caso de teste é aquele que tem grande probabilidade de
encontrar o maior número de erros ainda não descobertos.
23
Teste é o principal meio que a indústria utiliza para avaliar o software que está sendo
desenvolvido e pode ser originado de diversos artefatos, tais como: requisitos e especifi-
cações. É uma atividade cara e trabalhosa, e abrange um alto número de tarefas, que
incluem: projeto, manutenção de scripts, execução de testes, comparação de resultados
esperados com resultados reais, dentre outras atividades cotidianas que consomem muito
tempo e esforço do engenheiro de teste [Ammann and Offutt, 2008]. Além disso, os custos
envolvidos associados às falhas de software são motivações para uma atividade de teste
cuidadosa, adequada e bem planejada [Pressman, 2001].
O processo de teste compreende desde o planejamento até a avaliação dos resultados
obtidos com os testes. Um ponto essencial do projeto é a escolha dos casos de teste.
Até mesmo quando o programa a ser testado parece simples, este pode envolver milhares
de entradas possíveis, o que exige um cuidado criterioso na elaboração dos casos de teste
[Ammann and Offutt, 2008]. Executar todas as possibilidades de entrada para o programa
testado é impossível, pois o número de entradas para um software pode ser infinito.
Este tipo de execução com todas as entradas possíveis é chamado de teste exaustivo
[Myers, 2004].
As técnicas de projeto de casos de testes são classificadas em testes funcionais
(Caixa Preta) e testes estruturais (Caixa Branca) [Myers, 2004]. O teste funcional
utiliza a especificação de requisitos do software e busca garantir que a funcionalidade
do mesmo esteja correta, como também que a integridade das informações seja preser-
vada [Sommerville, 2004]. O teste estrutural também tem os mesmos objetivos gerais do
teste funcional, a diferença é que o artefato de entrada para este tipo de teste é o próprio
código do sistema. A preocupação para este tipo de teste se concentra na estrutura interna
do programa. Nesta abordagem os dados de teste são derivados de uma análise lógica
do programa e sua preocupação está focada na execução de cada caminho do programa
[Myers, 2004].
No decorrer do texto utilizaremos o termo erro, no entanto, existem outros conceitos
importantes na literatura, como defeito e falha. Apresentaremos estes conceitos com base
na terminologia utilizada por [Ammann and Offutt, 2008].
• Defeito: é uma incorreção estática no software. Uma instrução ou comando incorreto
que pode gerar problemas durante a execução;• Erro: é a manifestação do defeito, um estado interno do software que está incorreto;
• Falha: é o comportamento externo do software, resultante do erro.
24
Nas próximas seções serão explicados sobre critérios de cobertura e critérios de testes
baseados em sintaxe, que é o critério que interessa ao nosso trabalho.
2.2.1 Critérios de Cobertura
Considerando os diversos cenários que precisam ser testados para buscar a garantia
de que o programa funcione corretamente, um dos pontos mais difíceis no processo de
teste de software está relacionado à definição dos casos de testes que exercitem estes
cenários. Isso, porque nem sempre é possível testar todos os cenários, sendo necessário
limitar a quantidade de casos de testes. Os critérios de cobertura fornecem informações
para limitar o número de casos de testes, tornando o processo de teste mais rápido e
preciso. Eles servem como base para definir quais entradas devem ser usadas nos casos
de teste.
A definição de critérios de cobertura apresentada por [Ammann and Offutt, 2008] é
dada com base em um outro conceito, que é o de requisitos de teste, definido como um
elemento específico de um artefato de software que um caso de teste deve satisfazer ou
cobrir. Um exemplo de requisito de teste é a execução de uma linha de código. O critério
de cobertura é um conjunto de regras que impõem a satisfação de requisitos de teste para
um conjunto de casos de teste.
Definição 2.2.1. Critério de Cobertura: Dado um conjunto de requisitos de teste TR
para um critério de cobertura C, o conjunto de testes T satisfaz C se e somente se para
todo requisito de teste tr em TR, exista pelo menos um caso de teste t em T tal que t
satisfaz tr [Ammann and Offutt, 2008].
A Figura 4 mostra uma representação da definição de critério de cobertura apresentada
anteriormente. O conjunto de requisitos de teste representados por TR são definidos pelo
critério de cobertura. O conjunto T representa os casos de testes, que irão satisfazer a
um determinado critério de cobertura.
Os principais critérios de cobertura de teste apresentados por
[Ammann and Offutt, 2008] são : cobertura de grafos, cobertura lógica, particiona-
mento do espaço de entrada e testes baseados em sintaxe. Para o nosso trabalho
utilizaremos testes baseados em sintaxe, que foram implementados na ferramenta de
geração de sentenças desenvolvida no trabalho de [Hentz, 2010].
25
Figura 4: Representação da definição de critério de cobertura
2.2.2 Critérios de Teste Baseados em Sintaxe
A principal característica presente nos testes baseados em sintaxe é o uso de uma
descrição sintática. Esta descrição é expressa através de uma especificação formal. Os
critérios de cobertura para este tipo de teste são aqueles que utilizam esta especificação
formal para descrever a sintaxe de entrada dos artefatos de software, e é utilizada para
a criação ou avaliação dos casos de testes. A sintaxe de entrada pode ser usada para
definir entradas válidas (sintaxe correta) ou inválidas (sintaxe incorreta). Dizemos que
a entrada é válida se ela obedece à especificação. Caso contrário, ela é dita inválida
[Ammann and Offutt, 2008].
Em engenharia de software é comum a utilização de estruturas de teoria dos autô-
matos para descrever a sintaxe de entrada dos artefatos de software. O uso de ex-
pressões regulares e gramáticas livres de contexto é um exemplo para esse tipo de des-
crição. As gramáticas livres de contexto podem ser usadas de duas formas: como re-
conhecedores, para validação dos casos de testes em relação a uma sintaxe e como ge-
radores, para geração de casos de testes baseados na gramática de uma determinada
linguagem[Ammann and Offutt, 2008].
Uma gramática livre de contexto pode ser expressa formalmente através de uma
notação, como a Backus-Naur Form (BNF) e Extended Backus-Naur Form (EBNF)
[Standard, 1996].
Em BNF uma gramática é definida por um conjunto de regras de produção, que
tem um lado esquerdo e um lado direito. O operador ::= permite descrever as regras
26
de produção da gramática. O símbolo do lado esquerdo é um símbolo não-terminal; do
lado direito os símbolos que constituem as regras de produção podem ser terminais ou
não-terminais. Na notação BNF, os símbolos não-terminais são delimitados por < e > e
as alternativas são separadas pelo símbolo ‘|’, como mostra a Listagem 2.4.
<bloco> ::= <instrucao> | <instrucao>
Listagem 2.4: Especificação de uma BNF
A notação EBNF foi definida pela norma padrão ISO/IEC 14977 [Standard, 1996].
Ela é uma extensão da BNF, para qual foram criados novos operadores, como o “+” que
representa símbolos com repetição (uma ou mais vezes). Em EBNF, os símbolos terminais
são utilizados entre aspas (simples ou dupla) e os colchetes < ... > podem ser omitidos
para os símbolos não-terminais.
A tabela 1 mostra um resumo dos operadores suportados pela notação de entrada
de LGen. Esta notação de entrada tem como base a EBNF. Cada regra de produção da
gramática é definida pela notação <NTerm1> = <exp>; onde <NTerm1> é um não-terminal
sendo definido e exp é uma expressão que o define.
Operador Sintaxe Descrição
Sequência Term1 , Term2 O termo Term1 é gerado e então Term2 será
gerado.
Alternativa Term1 | Term2 O termo Term1 ou Term2 pode ser gerado.
Opcional [Term1] O termo Term1 pode ou não ser gerado.
Um Ou Mais Term1+ O termo Term1 pode ser gerado uma ou mais
vezes.
Zero Ou Mais {Term1} O termo Term1 pode ser gerado zero ou mais
vezes.
Tabela 1: Resumo dos operadores suportados pela notação de entrada
A Listagem 2.5 mostra uma gramática livre de contexto expressa com a notação de
entrada de LGen. Ela possui um símbolo especial chamado símbolo inicial (bank). Todos
os símbolos que estão entre aspas são símbolos terminais. Nesta gramática as chaves “{
}” e o operador “+” representam símbolos com repetição. O primeiro representa zero ou
mais e o segundo representa um ou mais.
bank = {action};
action = dep | deb;
dep = "deposit" , account , amount;
deb = "debit" , account , amount;
account = digit , digit , digit;
amount = digit+, "." , digit , digit;
27
digit = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9";
Listagem 2.5: Gramática para transações bancárias. Adaptado de
[Ammann and Offutt, 2008]
Alguns critérios de cobertura podem ser definidos a partir de uma gramática. Os
mais comuns são: Critério de Cobertura de Terminais, Critério de Cobertura de Regras
de Produção e Critério de Cobertura de Derivações [Ammann and Offutt, 2008].
Definição 2.2.2. Critério de Cobertura de Terminais. Um conjunto TR deve conter pelo
menos um tr para cada símbolo terminal t na gramática G [Ammann and Offutt, 2008].
Isso significa que todos os terminais contidos na gramática devem ser utilizados pelos
casos de teste.
Definição 2.2.3. Critério de Cobertura de Regras de Produção. Um conjunto TR
deve conter pelo menos um tr para cada regra de produção p na gramática G
[Ammann and Offutt, 2008].
Para o critério de Regras de Produção todas as regras de produção contidas em uma
gramática devem ser utilizadas pelos casos de teste.
Definição 2.2.4. Critério de Cobertura de Derivações. Um conjunto TR deve con-
ter pelo menos um tr para cada string possível de ser derivada pela gramática G
[Ammann and Offutt, 2008].
Para este critério é necessária a utilização de todas as derivações possíveis de uma
gramática pelos casos de teste.
Para demonstrar o uso destes critérios de cobertura apresentamos um exemplo de
gramática na Listagem 2.5. Em relação a definição do critério de terminais (definição
2.2.2), para satisfazê-lo, os casos de teste selecionados deverão conter pelo menos um caso
de teste que utilize cada um dos terminais da gramática. Desta forma, podemos definir
o conjunto de requisitos de teste como TR = {“deposit",“debit", “0"...“9", “."} .
Com os dados de teste deposit 123 4.56 e debit 789 0.12, o critério de terminais é
satisfeito.
No caso do critério de cobertura de regras de produção (definição 2.2.3) o seu conjunto
de requisitos de teste é definido como apresentadona Listagem 2.6. Desta forma temos
17 regras de produção para esta gramática, sendo TR = {R1, R2, R3, R4, R5, . . . , R17}, tal
que Ri representa uma regra de produção.
28
1 bank = {action};
2 action = dep;
3 action = deb;
4 dep = "deposit" , account , amount;
5 deb = "debit" , account , amount;
6 account = digit , digit , digit;
7 amount = digit+, "." , digit , digit;
8 digit = "0";
9 digit = "1";
10 digit = "2";
11 digit = "3";
12 digit = "4";
13 digit = "5";
14 digit = "6";
15 digit = "7";
16 digit = "8";
17 digit = "9";
Listagem 2.6: Regras de Produção da gramática para transações bancárias
[Ammann and Offutt, 2008]
Se utilizarmos os casos de testes apresentados anteriormente, o critério de regras de
produção também é satisfeito, pois todas as regras de produção contidas nesta gramática
são utilizadas pelos casos de teste.
Em relação ao critério de cobertura de derivações (definição 2.2.4), o conjunto não é
satisfeito. Em geral, para o critério de derivações o número de derivações pode ser infinito
e a satisfação do critério é difícil de ser atingida.
É importante destacar que existe uma ordem entre esses critérios de cobertura, em
termos de quantidade de requisitos de teste. O número de requisitos de testes gerados
com o critério de terminais é exatamente igual ao número de símbolos terminais. Em
relação ao critério de regras de produção, o número de requisitos de testes é equivalente
ao número de regras de produção. No caso do critério de cobertura de derivações o número
de derivações depende da gramática, mas em geral pode ser infinito.
Outro ponto importante é a relação que existe entre os critérios de cobertura. Quando
o critério de derivações é atingido, por consequência os critérios de regras de produção
e terminais também são. O mesmo acontece com o critério de regras de produção, que
quando coberto, também cobre o critério de terminais.
O critério de cobertura a ser utilizado depende do contexto em que se está trabalhando.
Deve-se escolher o critério que melhor atenda à necessidade existente.
29
3 Lua Language Generator (LGen)
Como um dos nossos objetivos é avaliar o gerador de sentenças (LGen) desenvolvido no
trabalho de [Hentz, 2010], faz-se necessário apresentar a ferramenta. Desta forma, neste
capítulo são apresentados a definição, o funcionamento de LGen e uma breve descrição
da implementação da ferramenta.
3.1 Definição de LGen
LGen recebe como entrada uma gramática livre de contexto e gera como saída um
conjunto de sentenças da linguagem descrita pela gramática. O conjunto de sentenças
gerado representa um conjunto de dados de teste para aquela gramática.
Por questões de otimização, LGen utiliza dois critérios de cobertura: cobertura de
terminais e cobertura de regras de produção, explicados na seção 2.2.2. Esses critérios são
usados para limitar a quantidade de sentenças geradas, sem diminuir a sua qualidade e
procurando obter um bom (variado) conjunto de testes. Um outro elemento que o gerador
utiliza para limitar o número de sentenças são as restrições: uma em relação ao número
de passos de uma derivação ou tamanho da árvore de derivação (maxDerivLen). Quando
o limite configurado é atingido a derivação é interrompida e outra opção de derivação
dentro da gramática é executada. A outra, em relação ao número máximo de expansões
de um não-terminal dentro da derivação de uma sentença (maxCycles).
3.1.1 Controle de Derivações
O controle de derivações é baseado no número de ciclos de não-terminais (maxCycles)
e na altura da árvore de derivação (maxDerivLen). A configuração destes mecanismos de
controle não está associada à gramática, mas é realizada a cada execução do motor de
geração.
30
O primeiro mecanismo de controle (maxCycles) limita o número máximo de recursões
possíveis para um não-terminal. Estas recursões são contadas com base no número de
repetições de um não-terminal durante os passos de derivação de uma sentença.
Considerando a gramática da Listagem 3.1:
S -> AB
A -> a | aA
B -> b
Listagem 3.1: Gramática exemplo
Quando for realizada a derivação para essa gramática, pode ser gerado um ciclo in-
finito, por causa do não-terminal “A”. O controle de derivações (maxCycles) vai definir o
número máximo de recursões possíveis para esse não-terminal. Uma vez que esse limite é
extrapolado, a expansão do não-terminal é negada.
Quando o valor de maxCycles for igual a “1”, teríamos algo como apresentado na
Figura 5. A Figura 6 mostra um exemplo, quando o maxCycles for igual a “2”.
Figura 5: Derivação para o maxCycles igual a 1
Figura 6: Derivação para o maxCycles igual a 2
31
O segundo mecanismo (maxDerivLen) limita a altura da árvore de derivação para
uma sentença. Quando o limite configurado para o (maxDerivLen) é atingido a derivação
é interrompida.
Vamos considerar a gramática apresentada na Listagem 3.2.
Call = CallerOS, ServerOS,CalleeOS;
CallerOS = "Mac" | "Win" ;
ServerOS = "Lin" | "Sun" |"Win" ;
CalleeOS = "Mac" | "Win" ;
Listagem 3.2: Gramática call
Na execução de LGen, quando utilizamos maxDerivLen igual a “1”, teríamos algo
como está apresentado na Figura 7. Nesse caso, nenhuma sentença seria gerada, pois Si
∈/ T, onde T representa os símbolos terminais.
Figura 7: Árvore de derivação para o MaxDerivLen igual a 1
Se ao invés de 1, o maxDerivLen informado for igual a 2, seria gerada 12 sentenças,
o que corresponde a 12 (doze) àrvores de derivação. A Figura 8 mostra o exemplo da
primeira àrvore de derivação que seria gerada. As sentenças geradas para ela são (‘Mac’,
‘Lin’, ‘Mac’). Observamos que para essa gramática são necessários 2 passos de derivação
para a sua saturação.
Figura 8: Árvore de derivação para o MaxDerivLen igual a 2
32
3.2 Funcionamento de LGen
O processo de geração das sentenças ocorre em duas fases: (1) consiste na tradução
da gramática descrita através de uma notação EBNF para uma especificação descrita na
linguagem de programação Lua e (2) a especificação Lua é utilizada para a geração das
sentenças.
Para um melhor entendimento do funcionamento de LGen, apresentamos um exem-
plo prático. A gramática que será utilizada como entrada no gerador é usada para testar
as configurações de um software Voip, que é sensível à versão do sistema operacional
[Hoffman et al., 2010].
O primeiro passo é especificar a gramática com a notação aceita pela ferramenta.
Essa especificação pode ser visualizada através da gramática da Listagem 3.3. A gramática
possui 04(quatro) símbolos terminais, 04 (quatro) símbolos não-terminais e 08(oito) regras
de produção.
Call = CalerOS, ServerOS,CalleeOS;
CallerOS = "Mac" | "Win" ;
ServerOS = "Lin" | "Sun" |"Win" ;
CalleeOS = "Mac" | "Win" ;
Listagem 3.3: Gramática em EBNF
Com a gramática EBNF, o próximo passo é a tradução da notação EBNF para uma
especificação Lua. A especificação Lua do exemplo pode ser visualizada na Listagem 3.4.
Na especificação Lua, a representação de uma sequência (CallerOS, ServerOS,CalleeOS)
é feita através da função seq, como pode ser visto em seq(V.CallerOS, seq(V.ServerOS,
V.CalleeOS)). As alternativas que são representadas em EBNF pelo símbolo “|”, como
está em (‘Lin’ | ‘Sun’ |‘Win’), são definidas na especificação Lua através da função alt,
como está expressa em alt( terminal(‘Lin’), terminal(‘Sun’), terminal(‘Win’)). A função
seq é binária, por isso sua representação é feita com uma sequência de dois itens, no caso
da função alt a sua representação é diferente, porque ela é n-ária. Por necessidade de
implementação, o nome de cada não-terminal é etiquetado com “G.”, quando aparece na
sua definição, e com “V.”, quando é usado na definição de outro não-terminal. Detalhes
sobre esta implementação são apresentados em [Hentz, 2010].
Uma vez que a especificação Lua está disponível, é necessário fazer uma configuração
manual e só depois essa especificação é passada para o motor de geração, que irá gerar
as sentenças. A configuração a ser feita se refere ao símbolo inicial da gramática, que
33
G.startSymbol = "Call"
G.Call = seq(V.CallerOS, seq(V.ServerOS,V.CalleeOS))
G.CallerOS= alt( terminal("Mac"), terminal("Win"))
G.ServerOS= alt( terminal("Lin"), terminal("Sun"), terminal("Win"))
G.CalleeOS= alt( terminal("Mac"), terminal("Win"))
Listagem 3.4: Especificação Lua
precisa ser configurado através do código G.startSymbol = "< StartSymbol >", onde o
< StartSymbol > deve ser substituído pelo símbolo inicial da gramática. A especificação
de entrada para o gerador pode ser visualizada na Listagem 3.4.
No momento da geração, três parâmetros são configurados: (1) o número máximo de
recursão para cada símbolo não-terminal da gramática, que determina quantas vezes um
não-terminal será repetido recursivamente no processo de geração. Esse parâmetro foi
definido na seção 3.1.1, (2) a altura da árvore de derivação. Esse parâmetro foi definido
na seção 3.1.1 e o critério de cobertura a ser utilizado na geração. Esse parâmetro foi
definido na seção 2.2.2.
Os resultados dos testes serão apresentados em tabelas que contém as seguintes infor-
mações:
(1) maxDerivLen representa a altura da árvore de derivação.
(2) Tempo Exec. representa a duração da execução do motor de geração para a
configuração indicada, o tempo segue o formato mm:ss.zz em que mm representa os min-
utos, ss os segundos e zz os centésimos de segundos. Se refere ao tempo de processamento
da CPU.
(3) C. NT representa a proporção de não-terminais utilizados pelas sentenças ger-
adas. Esta informação será utilizada para traçar uma relação entre a execução apenas
com as restrições e a dos critérios de cobertura;
(4) C.Terminais representa o percentual de satisfação do critério de cobertura de
terminais;
(5) C.RP representa o percentual de satisfação do critério de cobertura de regras de
produções;
(6) Num. Sentenças representa o número de sentenças geradas.
Na Tabela 2 são apresentadas as configurações e os resultados obtidos na execução da
gramática apenas com as restrições de ciclos e número de passos de derivação. Para esta
34
gramática todos os não-terminais foram utilizados a partir da execução 1 e o conjunto de
sentenças geradas em todas as execuções é idêntico. As sentenças geradas são visualizadas
na Tabela 3.
Execução MaxDerivlen Tempo Exec. C.NT C.Terminais C.RP Num.
Sentenças
1 2 0 : 00.01 100% 100% 100% 12
2 3 0 : 00.01 100% 100% 100% 12
3 4 0 : 00.01 100% 100% 100% 12
4 5 0 : 00.01 100% 100% 100% 12
Tabela 2: Resultados da execução da gramática apenas com as restrições de ciclos e
número de passos de derivação.
Sentenças Terminais Cobertos Regras de Produção Cobertas
Mac Lin Mac Mac Lin 1, 2, 4, 7
Mac Lin Win Mac Lin Win 1, 2, 4, 8
Mac Sun Mac Mac Sun 1, 2, 5, 7
Mac Sun Win Mac Sun Win 1, 2, 5, 8
Mac Win Mac Mac Win 1, 2, 6, 7
Mac Win Win Mac Win 1, 2, 6, 8
Win Lin Mac Win Lin Mac 1, 3, 4, 7
Win Lin Win Win Lin 1, 3, 4, 8
Win Sun Mac Win Sun Mac 1, 3, 5, 7
Win Sun Win Win Sun 1, 3, 5, 8
Win Win Mac Win Mac 1, 3, 6, 7
Win Win Win Win 1, 3, 6, 8
TOTAL Win Mac Lin Sun 1...8
Tabela 3: Sentenças geradas apenas com as restrições de ciclos e número de passos de
derivação
Utilizando as mesmas configurações anteriores para a execução do gerador, agora
fazendo uso do critério de cobertura de terminais, o resultado pode ser visualizado na
Tabela 4. O critério de cobertura de terminais foi satisfeito a partir da execução 1. Para
esta gramática todos os não-terminais foram utilizados a partir da execução 1. No entanto,
foram cobertas apenas 75% das regras de produção. O conjunto de sentenças geradas em
todas as execuções é idêntico. Podemos observar uma redução do número de sentenças
geradas em relação às execuções utilizando apenas os controles de derivação. As sentenças
geradas são visualizadas na Tabela 5.
O último critério de cobertura que utilizamos foi o de regras de produção. Apresen-
tamos o seu resultado na Tabela 6. O critério de cobertura de regras de produção foi
satisfeito a partir da execução 1. Para esta gramática todos os não-terminais também
35
Execução MaxDerivlen Tempo Exec. C.NT C.Terminais C.RP Num.
Sentenças
1 2 0 : 00.01 100% 100% 75% 3
2 3 0 : 00.01 100% 100% 75% 3
3 4 0 : 00.01 100% 100% 75% 3
4 5 0 : 00.01 100% 100% 75% 3
Tabela 4: Resultados da execução da gramática com o Critério de Cobertura de Terminais
Sentenças geradas Terminais Cobertos Regras de Produção Cobertas
Mac Lin Mac Mac Lin 1, 2, 4, 7
Mac Lin Win Mac Lin Win 1, 2, 4, 8
Mac Sun Mac Mac Sun 1, 2, 5, 7
TOTAL Win Mac Lin Sun 1, 2, 4, 5, 7, 8
Tabela 5: Sentenças Geradas com o Critério de Cobertura de Terminais
foram utilizados a partir da execução 1. O conjunto de sentenças geradas em todas as
execuções é idêntico. Também observamos uma redução do número de sentenças geradas
em relação às execuções utilizando apenas os controles de derivação. As sentenças geradas
são visualizadas na Tabela 7.
Execução MaxDerivlen Tempo Exec. C.NT C.Terminais C.RP Num.
Sentenças
1 2 0 : 00.01 100% 100% 100% 5
2 3 0 : 00.01 100% 100% 100% 5
3 4 0 : 00.01 100% 100% 100% 5
4 5 0 : 00.01 100% 100% 100% 5
Tabela 6: Resultados da execução da gramática com o Critério de Cobertura de Regras
de Produção
Sentenças geradas Terminais Cobertos Regras de Produção Cobertas
Mac Lin Mac Mac Lin 1, 2, 4, 7
Mac Lin Win Mac Lin Win 1, 2, 4, 8
Mac Sun Mac Mac Sun 1, 2, 5, 7
Mac Win Mac Mac Win 1, 2, 6, 7
Win Lin Mac Win Lin Mac 1, 3, 4, 7
TOTAL Win Mac Lin Sun 1...8
Tabela 7: Sentenças Geradas com o Critério de Cobertura de Regras de Produção
Como resultado dos testes utilizando a gramática acima, observamos que os critérios
de cobertura de terminais e regras de produção foram satisfeitos em 100%. Para os dois
casos foi necessária a execução de 2 passos de derivação para a sua satisfação. O número
de passos necessários para a maior derivação nesta gramática é 2, assim é justificada a
estabilização do processo de geração nas configurações de maxDerivLen em 2, 3, 4 e 5.
36
Através do uso dos critérios de cobertura foi possível reduzir o número de sentenças
geradas em relação ao uso dos controles de derivações. Em relação ao tempo de geração,
não houve diferença, isso porque utilizamos uma gramática simples e pequena. Observa-
mos também que o número de sentenças que foi gerado varia de acordo com o critério de
cobertura utilizado.
3.3 Implementação de LGen
Nesta seção apresentamos a arquitetura e os componentes que integram o gerador de
sentenças. Em seguida apresentamos os critérios de cobertura implementados no gerador.
3.3.1 Arquitetura de LGen
A arquitetura do processo de geração das sentenças é apresentada na Figura 9. Essa
arquitetura representa os componentes que são utilizados durante o processo de geração
de sentenças. Os retângulos representam as informações (entrada/saída) e os círculos
representam os dois componentes (tradutor e motor de geração) que integram o gerador.
No processo de geração, a primeira etapa consiste na tradução da gramática descrita
através de uma notação EBNF para uma especificação que foi descrita na linguagem de
programação Lua. O responsável por esta etapa é o componente tradutor. Na segunda
etapa, a especificação Lua gerada no processo de tradução é utilizada para a geração do
conjunto de sentenças. Nesta etapa, o componente responsável é o motor de geração.
Entrada
EBNF Tradutor
Especificação
Lua
Motor de
Geração
Sentenças
Válidas
Figura 9: Arquitetura de LGen [hentz:2010]
A especificação EBNF é a notação de entrada do tradutor e contém construções que
são usadas para descrever uma gramática livre de contexto. A especificação Lua é o
resultado do processo de tradução. Ela contém representações Lua para as construções
EBNF. Essa especificação é passada para o motor de geração que irá gerar um conjunto
de sentenças.
Após o processo de tradução é necessário que o usuário realize alguns ajustes manuais
na especificação Lua que foi gerada. Esses ajustes foram explicados na seção 3.2. A con-
37
figuração dos critérios é realizada através da função setCoverageCriteria, que recebe como
parâmetro uma referência para um módulo que possui as implementações das funçõesde
construção que serão disparadas no momento da execução. Após o processo de tradução,
a especificação Lua gerada é enviada como entrada para o Motor de Geração, que retorna
como saída um conjunto de sentenças.
O motor de geração implementa restrições para limitar o número de sentenças geradas.
Estas restrições são o Controle de Derivações e os Critérios de Cobertura. O controle de
derivações foi explicado na seção 3.1.1.
3.3.2 Critérios de Cobertura
O motor de geração possibilita que diferentes critérios de cobertura sejam usados
durante a geração das sentenças. No trabalho original foram implementados dois critérios
de cobertura: cobertura de terminais e cobertura de regras de produção, no entanto, o
motor de geração suporta novos critérios de cobertura.
3.3.2.1 Critério de Cobertura de Terminais
Para o critério de cobertura de terminais, durante a geração de uma sentença, é
verificada se esta sentença acrescenta novos terminais ao conjunto dos terminais que já
foram utilizados. Se isso acontecer, esta sentença é adicionada ao conjunto de sentenças
que já foram geradas. Caso contrário, a sentença é eliminada. A implementação desse
critério é feita através de um módulo chamado terminalCoverage.lua.
3.3.2.2 Critério de Cobertura de Regras de Produções
Para o critério de cobertura de regras de produção é feito um controle durante a gera-
ção das sentenças, onde é verificada se a sentenças que está sendo gerada contribui para
a satisfação do critério. Se isso acontecer, a sentença é incluída ao conjunto de sentenças
geradas. Caso contrário, ela é eliminada. Essa verificação é realizada após a geração de
uma sentença e durante a execução da construção de alternativa. A implementação desse
critério é feita através do módulo productionCoverage.lua.
Tanto no critério de terminais quanto no critério de regras de produção ocorre um
mecanismo chamado previsões. Esse mecanismo verifica se um símbolo não-terminal tem
algum elemento que contribui para a satisfação do critério. Caso esta expansão não
contribua, o não-terminal não será expandido.
38
4 Aplicações com Gramáticas
O objetivo deste trabalho é identificar tipos de problemas recorrentes em áreas es-
pecíficas, onde as gramáticas são utilizadas para descrevê-los. Neste sentido foi realizado
um levantamento para identificá-los. Os exemplos encontrados na literatura foram: (1)
Descrições de configurações para: linha de produto de software [Bagheri et al., 2012], soft-
ware de telefonia Voip [Hoffman et al., 2011] e teste de firewall [Hoffman and Yoo, 2005]
[Hoffman et al., 2010], (2) Especificações de arquivos para: arquivos XML (eXten-
sible Markup Language) [Hoffman et al., 2009], protocolos de redes [Kaksonen, 2001]
e Processamento de Imagens [Hamdi, 2012], (3) Reconhecimento de padrões em re-
des de sensores [Lymberopoulos et al., 2006] [Teixeira et al., 2006] [Kitani et al., 2005] e
[Lymberopoulos et al., 2008]. Em alguns trabalhos as gramáticas são usadas para descr-
ever entradas para o software, mas outros tipos de informações também são formalmente
descritos pela gramáticas, como por exemplo, na especificação de configurações de soft-
ware.
Para seleção dos trabalhos foi realizada uma revisão bibliográfica. Para esta
revisão, utilizamos algumas técnicas que fazem parte de uma revisão sistemática
[Biolchini et al., 2005], são elas:
Objetivo: identificação de tipos de problemas em áreas específicas, onde gramáticas
são utilizadas para descrevê-los.
Recursos para Busca e Seleção de Estudos: Os recursos e estratégias para busca e
seleção de estudos foram definidos e selecionados com base em três itens, são eles:
• Identificação de fontes de busca: As fontes de busca identificadas são bases de dados
eletrônicas indexadas (IEEE e ACM ). Também foi utilizado o Google Acadêmico.
• Idioma dos trabalhos: Inglês. Por ser considerado o idioma mais aceito interna-
cionalmente para trabalhos científicos.
• Palavras-chave: “grammar-based test generation” (geração de teste baseada em
39
gramática) e “grammar testing”(teste de gramática). Diante dos resultados en-
contrados utilizando estas duas palavras-chave principais, identificamos possíveis
áreas que utilizavam gramáticas em seus contextos e que poderiam contribuir para
a pesquisa. Assim, acrescentamos outras palavras-chave mais direcionadas, que
foram: “automated testing of protocols” (teste automatizado de protocolos), “test
software product line” (teste de linha de produto de software), “grammar-based
image processing” (processamento de imagem baseada em gramática), “ specifica-
tion log files” (especificação de arquivos de log) e “ grammar- based bioinformatics”
(bioinformática baseada em gramática).
Seleção Preliminar: Consideramos apenas o resumo dos trabalhos para uma pré-
seleção.
Seleção Final: O processo de seleção final consiste na leitura completa dos trabalhos
incluídos ao final do processo de seleção preliminar. Para a seleção final, os trabalhos foram
escolhidos com base na sua relevância no contexto dos objetivos propostos no trabalho.
Nas subseções 4.1 e 4.2 descrevemos os trabalhos identificados nesta pesquisa e que
relacionam-se com o nosso estudo. Foram criadas subseções distintas, cada uma contendo
os trabalhos identificados por sua área de aplicação. Os trabalhos foram divididos em
duas categorias: trabalhos em que o uso de gramáticas está relacionado à geração de
testes e trabalhos em que o uso de gramáticas está relacionado a diversos fins.
4.1 Conjunto de trabalhos que utilizam gramáticas para
testes
Esta subseção descreve um conjunto de trabalhos que utilizam gramáticas e que estão
relacionadas ao projeto de testes a partir de gramáticas.
4.1.1 Linha de Produto de Software
O trabalho apresentado por [Bagheri et al., 2012] propõe a representação das carac-
terísticas (do inglês: features) de um modelo de linha de produto de software através
de gramáticas livres de contexto, expressas na notação EBNF. Estas características cor-
respondem às funcionalidades presentes em produtos de uma família de sistemas. Além
disso, a proposta estende os critérios de cobertura existentes para EBNF, propondo oito
novos critérios de cobertura para estes modelos.
40
As Linhas de Produto de Software (LPS) são usadas para facilitar o reuso do software
e compartilham um conjunto de características comuns. Estas características podem ser
representadas de várias formas, dentre elas de forma gráfica ou formal. A primeira através
de uma estrutura de árvore, a segunda através de uma gramática livre de contexto.
Para compor uma família de produtos com todas as características de um conjunto de
sistemas semelhantes são criados modelos de características, que descrevem as possíveis
configurações dos produtos de uma linha de produto. Um modelo de características é um
conjunto de características hierarquicamente organizadas e geralmente classificadas como:
Obrigatório, Opcional, Alternativo e OR. Uma característica opcional descreve uma fun-
cionalidade que pode ou não estar presente nos produtos de uma família de sistemas. A
característica obrigatória é uma característica que está presente em todos os produtos de
uma família de sistemas. Características alternativas representam funcionalidades mutu-
amente exclusivas, em outras palavras, as características alternativas definem um grupo
em que um, e apenas um pode estar presente em um produto. O construtor OR indica que
pelo menos uma das sub-características devem ser seleccionadas [Benavides et al., 2010a].
O processo de testes para linha de produto de software é complexo, porque ela possui
n características que precisam ser testadas para cada aplicação. Diante disso, é preciso
construir uma estratégia para reduzir o número de testes e ao mesmo tempo preservar
uma cobertura de falhas aceitável.
Os novos critérios de cobertura que foram desenvolvidos em [Bagheri et al., 2012]
constituem a base para a produção de conjuntos menores de configurações, que são, ao
mesmo tempo bastante eficientes na identificação de falhas em modelosde características.
Os oito critérios de cobertura desenvolvidos são: inclusão de cobertura máxima de terminal
(MxTI), inclusão de cobertura máxima de não-terminal (MxNTI), exclusão de cobertura
máxima de terminal (MxTE), exclusão de cobertura máxima de não-terminal (MxNTE),
inclusão de cobertura mínima de terminal (MinTI), inclusão de cobertura mínima de
não-terminal (MinNTI), exclusão de cobertura mínima de terminal (MinTE), exclusão
de cobertura mínima de não-terminal (MinNTE). Os novos critérios foram definidos com
base nos critérios apresentados por [Ammann and Offutt, 2008].
A Figura 10 apresenta um modelo típico da comunidade de linha de produto de soft-
ware, para um conjunto de aplicações para grafos [Ensan et al., 2012]. Uma característica
obrigatória é representada por uma aresta terminada por um círculo preenchido em preto.
Uma característica opcional é representada por uma aresta terminada por um círculo
vazio. Uma característica alternativa (ou-exclusivo) é representada por arestas que estão
41
ligadas por um arco vazio. Se o arco estiver cheio é permitido seleccionar mais de uma
alternativa (ou). A estrutura hierárquica para este modelo de características de linha de
produto foi representada usando gramáticas livres de contexto, através da notação EBNF,
como pode ser visualizado na Listagem 4.1.
GPL
Graph
Type
Search Algorithms
Directed Weighted
Undirected Unweighted
DFS BFS MST Cycle
Detection
Shortest
Path
Coloring Strongly
Con-
nected
Approximation Brutal
Force
Figura 10: Feature Model GPL [Bagheri et al., 2012].
Para avaliar o trabalho, foram realizados experimentos utilizando nove modelos de
características disponíveis no website Software Product Lines Online Tools - SPLOT
[Mendonca et al., 2009] - cujo objetivo é compartilhar modelos de linha de produto de
software de forma livre. Estes modelos são representados no formato Simple XML Fea-
ture Model (SXFM) 1, sendo que os mesmos foram convertidos para uma gramática EBNF
correspondente a cada modelo, através de um software desenvolvido pelos autores, que
automatiza este processo. O software é capaz de analisar os modelos em SXFM e au-
tomaticamente desenvolver a gramática EBNF correspondente. Após este processo, o
software gerou um uma suite de teste para cada um dos critérios de cobertura, para cada
modelo.
Para avaliar a eficácia dos critérios de cobertura foi desenvolvido um simulador de
geração de falhas. A falta de um conjunto de dados públicos que estejam disponíveis,
justificou o uso desse simulador. O simulador foi utilizado para os nove modelos de
característica, o que resultou num conjunto de falhas para cada um dos modelos que pre-
cisavam ser identificados e cobertos por conjuntos dos teste gerados. O simulador utiliza
três formas para gerar os defeitos, são elas: Falhas em características individuais (estas
características individuais serão consideradas para conter as falhas que deverão ser detec-
tadas pela suite de teste), Falhas em características ofensivas (essas falhas são geradas na
1formato XML para modelo de características
42
1 GPL = GraphType , Algorithms |
2 GraphType , Algorithms , Search;
3 GraphType = _r_1_2 |
4 _r_1_5;
5 LHS-directed = "t_directed" , "t_Strongly_Connected";
6 _r_1_2 = LHS-directed |
7 "t_undirected";
8 _r_1_5 = "t_weighted" |
9 "t_unweighted";
10 search = _r_8_9;
11 LHS-DFS = "t_DFS" , "t_Cycle_Detection";
12 _r_8_9 = LHS-DFS |
13 "t_BFS";
14 Algorithms = _r_12_13;
15 _r_12_13-sec = |
16 _r_12_13;
17 LHS-Cycle Detection = "t_Cycle_Detection" , "t_DFS";
18 LHS-Strongly_Connected = "t_Strongly_Connected" , "t_directed";
19 _r_12_13 = "t_Shortest Path" , _r_12_13-sec |
20 Coloring , _r_12_13-sec |
21 LHS-CycleDetection , _r_12_13-sec |
22 "t_MST" , _r_12_13-sec |
23 LHS-Strongly_Connected , _r_12_13-sec;
24 Coloring = _r_12_13_16_20;
25 _r_12_13_16_20-sec = |
26 _r_12_13_16_20;
27 _r_12_13_16_20 = "t_Approximation" , _r_12_13_16_20-sec |
28 "t_Brute_Force" , _r_12_13_16_20-sec;
Listagem 4.1: Gramática extraída do modelo de característica GPL [Bagheri et al., 2012]
forma de n-tuplas, em que cada tupla contém um conjunto de duas ou mais característi-
cas) e Falhas em características atrativas (um par de características é selecionado e uma
falha ocorre se uma das características do par está presente na configuração e a outra
não).
Como resultado do estudo, a estratégia apresentou uma redução dos números de
requisitos de testes, como também uma alta cobertura do número de falhas. Os resultados
mostraram que os critérios MxNTI e MxTI têm a maior cobertura de falhas e o critério
MxNTI tem a maior eficácia entre os oito critérios de cobertura que foram desenvolvidos.
4.1.2 Teste de Firewall
As gramáticas livres de contexto foram utilizadas na área de teste de firewall como
apresentado em [Hoffman and Yoo, 2005] e [Hoffman et al., 2010].
Em [Hoffman and Yoo, 2005], foi desenvolvida a ferramenta Blowtorch. A Blowtorch
é um framework desenvolvido em C++, para geração automática de teste de firewall. Ela
43
foi projetada para desenvolver testes com conjuntos de regras de firewall em um ambiente
de controle de processos [Byres and Savage, 2005].
No trabalho são apresentados quatro tipos de testes para verificar a política de segu-
rança de um firewall, são eles:
• Verificar se os pacotes SYN são enviados a uma taxa maior do que o permitido;
• Descartar todos os pacotes TCP com combinações de flag ilegal;
• Repetição do trafégo de produção (capturar o tráfego de PCN/DMZ e BN/DMZ),
verificando se o firewall permite que este trafégo seja permitido;
• Histórico de conexão de dados.
No entanto, o foco principal do trabalho é o teste que verifica o comportamento de
um firewall diante da inserção de combinações com flags ruins em conexões TCP. Existem
seis flags (urg,ack,psh,rst,syn e fin) de controle no cabeçalho TCP, mas nem todas as
combinações desses flags são significativas. Das 64 combinações possíveis, apenas 18 são
legais e 46 são ilegais [McCarty and Cox, 2002].
O teste deve determinar o comportamento do firewall diante das 46 combinações de
flags ruins. O comportamento desejado de um firewall para essa situação, seria derrubar
todos os pacotes que contêm estas combinações ilegais. O teste deve verificar quais pacotes
com flags ruins são filtrados por um firewall.
Além de verificar o comportamento do firewall, o teste permite determinar se o estado
da sessão TCP tem alguma influência sobre os pacotes encaminhados. Para determinar
se o estado faz alguma diferença, os pacotes com flags ruins são enviados em momentos
diferentes durante uma sessão TCP.
Para realização desses testes, os 46(quarenta e seis) pacotes com flags ruins foram
inseridos em 5 (cinco) locais diferentes, o que resultou em 230 casos de testes. Para criar
os casos de testes, foi utilizada uma gramática. Parte dessa gramática pode ser visualizada
na Figura 11.
Os testes foram executados com dois firewalls: iptables, que é um firewall de código
aberto que funciona em Linux e Pix Cisco, que é o padrão da industria.
Foram realizados dois testes. O primeiro enviou 46 (quarenta e seis) pacotes com flags
ruins através do firewall e o segundo enviou pacotes com flags ruins em lugares diferentes
44
Figura 11: Fragmento da gramatica [Hoffman and Yoo, 2005]
dentro de uma sessão TCP. O resultado mostrou que para o primeiro caso, 2 (dois) dos
46 (quarenta e seis) pacotes foram aceitos. Para o segundo teste, mais pacotes foram
encaminhados.
Em [Hoffman et al., 2010] foram apresentados dois estudos de caso que mostram a
combinação de duas abordagens: geração de testes baseada em gramáticas (GTBG) e
cobertura de matrizes. Na técnica de cobertura de matrizes, um template de testes é
desenvolvido com N parâmetros, cada um com um domínio finito. O espaço de teste é
o produto cartesiano dos domínios. Cada n-tupla em um espaço de teste especifica um
caso de teste. Geralmente o espaço de teste é grande para executar todos os casos de
testes. Um algoritmo de cobertura de matrizes obtém uma lista de domíniose gera um
subconjunto do espaço de teste contendo todas as combinações de parâmetros de um certo
tipo. Estas duas abordagens são utilizadas para automatizar o teste de software.
Um dos estudos de caso determina a efetividade de um firewall de rede quando diante
de flags ilegais. Um firewall é testado com um grande número de conexões TCP. Alguns
dos pacotes são normais, outros contêm pacotes com flags ilegais. Os firewalls são pro-
jetados para detectar e derrubar os pacotes com flags ilegais. Os testes determinam as
circunstâncias em que pacotes com flags ilegais são detectados e derrubados.
Para a realização dos estudos de caso foi utilizada a ferramenta YouGen, que engloba
as duas abordagens. A Yougen é responsável por definir e produzir os casos de testes.
A ferramenta recebe uma gramática livre de contexto G como entrada e produz um
45
subconjunto de L(G), gerando uma derivação para cada elemento de L(G). A ferramenta
é apresentada com detalhes em [Hoffman et al., 2011].
Uma sessão TCP vai por vários estados durante a sua vida útil e o estado da sessão
é controlado por um conjunto de seis flags booleanas dentro de cada pacote TCP, são
elas: SYN, ACK, FIN, PSH, RST, URG. Uma Conexão TCP é estabelecida através de
um processo denominado de handshake de três vias [Tanenbaum, 2003]. Para estabelecer
uma conexão TCP, o cliente envia um pacote com a flag SYN, logo depois o servidor
responde com um pacote com as flags SYN + ACK e por fim o cliente reponde com
um pacote ACK. Feito isso, uma conexão TCP está iniciada. O fim de uma conexão
TCP ocorre quando um lado envia um pacote com a flag FIN, o outro lado da conexão
reconhece a FIN e termina de enviar seus dados e seguir com a FIN correspondente. O
segundo FIN é reconhecido e a conexão é terminada. Para melhor entendimento, a figura
12 mostra quando uma conexão TCP está sendo estabelecida.
Figura 12: Conexão TCP sendo estabelecida [Hoffman et al., 2010]
Como algumas implementações TCP são vulneráveis à combinações com flags ile-
gais, os hackers, muitas vezes, enviam pacotes TCP com combinações de flags ilegais.
O teste deve determinar as circunstâncias em que os pacotes são ilegais. Um fragmento
da gramática utilizada nos testes pode ser visualizada na Listagem 4.2. Esta gramática
representa uma conexão TCP completa, com flags ruins injectados em sete posições.
Tanto o trabalho apresentado por [Hoffman and Yoo, 2005] quanto este
[Hoffman et al., 2010] tem sido utilizado para testar inserção de pacotes com flags
ilegais. No entanto, existem diferenças entre eles. No primeiro a conexão TCP continha
46
S ::= SEPARATOR BadFlags0 SYN BadFlags1 SYNACK BadFlags2 ACK1 BadFlags3
FINACK1 BadFlags4 FINACK2 BadFlags5 ACK2 BadFlags6;
SEPARATOR ::= ‘! ! ! ! ! ! ! ! !’;
SYN ::= ‘\n’ ‘SYN’ ‘SYN’ ‘ack’ ‘fin’ ‘psh’ ‘rst’ ‘urg’ ‘OUT’ ‘ACCEPT’;
SYNACK ::= ‘\n’ ‘SYNACK’ ‘SYN’ ‘ACK’ ‘fin’ ‘psh’ ‘rst’ ‘urg’ ‘IN’ ‘
ACCEPT’;
ACK1 ::= ‘\n’ ‘ACK1’ ‘syn’ ‘ACK’ ‘fin’ ‘psh’ ‘rst’ ‘urg’ ‘OUT’ ‘ACCEPT
’;
FINACK1 ::= ‘\n’ ‘FINACK1’ ‘syn’ ‘ACK’ ‘FIN’ ‘psh’ ‘rst’ ‘urg’ ‘IN’ ‘
ACCEPT’;
FINACK2 ::= ‘\n’ ‘FINACK2’ ‘syn’ ‘ACK’ ‘FIN’ ‘psh’ ‘rst’ ‘urg’ ‘OUT’ ‘
ACCEPT’;
ACK2 ::= ‘\n’ ‘ACK2’ ‘syn’ ‘ACK’ ‘fin’ ‘psh’ ‘rst’ ‘urg’ ‘IN’ ‘ACCEPT’;
BadFlags0 ::= BadFlag0;
BadFlag0 ::= ‘\n’ ‘badFlag0’ StaticBadFlags() ‘IN’ ‘DROP’;
BadFlags1 ::= ‘\n’ ‘badFlag1’ Flag1 ‘IN’ ‘DROP’;
Flag1 ::= StaticBadFlags();
BadFlags2 ::= ‘\n’ ‘badFlag2’ Flag2 ‘IN’ ‘DROP’;
Flag2 ::= StaticBadFlags();
BadFlags3 ::= ‘\n’ ‘badFlag3’ Flag3 ‘IN’ ‘DROP’;
Flag3 ::= StaticBadFlags();
BadFlags4 ::= ‘\n’ ‘badFlag4’ Flag4 ‘IN’ ‘DROP’;
Flag4 ::= StaticBadFlags();
BadFlags5 ::= ‘\n’ ‘badFlag5’ Flag5 ‘IN’ ‘DROP’;
Flag5 ::= StaticBadFlags();
BadFlags6 ::= ‘\n’ ‘badFlag6’ Flag6 ‘IN’ ‘DROP’;
Flag6 ::= StaticBadFlags();
Listagem 4.2: Gramática utilizada no teste de firewall [Hoffman et al., 2010]
apenas um único pacote com flags ruins, que incluia todas as combinações, produzindo
cerca de 200 milhões de testes. Além disso, os testes foram gerados manualmente. No
trabalho de [Hoffman et al., 2010] a ferramenta YouGen foi utilizada e as tags usadas
para escolher livremente as combinações.
4.1.3 Analisador feed RSS
Assim como apresentado na seção 4.1.2, o trabalho [Hoffman et al., 2009] tam-
bém utiliza as técnicas de geração de testes baseada em gramáticas (GTBG) e cober-
tura de matrizes. A combinação destas duas abordagens é também apresentada em
[Sobotkiewicz, 2008].
47
Neste estudo, as gramáticas livres de contexto são utilizadas para a geração au-
tomática de testes que avaliam um analisador de feed RSS. O RSS é uma família de for-
matos baseados em XML, para distribuição de conteúdos na Web que possuem múltiplas
versões disponíveis. Os feeds RSS disponibilizam conteúdo Web ou resumos de conteúdo
juntamente com os links para as versões completas deste conteúdo.
Um feed RSS possui uma estrutura de sintaxe que contém tags como: <rss>,
<channel>, <title>, <item>, <link> e <description>. Estas tags representam alguma
definição específica dentro do arquivo. A tag <title>, por exemplo, define o título do site.
O trabalho apresenta um estudo de caso com o feedparser [feed parser, 2002], uma
biblioteca Python, que analisa feeds em todos os formatos, incluindo Atom, RSS, e RDF.
O estudo foi realizado com as versões Atom 1.0, RSS 1.0 e RSS 2.0 e a proposta teve
como objetivo testar o feedparser para vulnerabilidades de injeção de HTML. Na suíte de
teste do RSS, o oráculo verifica se todos os elementos perigosos foram retirados.
O risco de segurança associado com a injeção HTML em feeds RSS implica que este
HTML contenha elementos perigosos, como por exemplo um código javascript malicioso,
que pode ser executado no lado do cliente. O teste para esse tipo de abordagem é difícil,
dada as muitas versões de feeds RSS existentes e os muitos tipos de elementos seguros
e inseguros. Esse tipo de teste exige muito esforço, já que exige testes que contemplem
muitas combinações de versões e locais de injeção HTML. Um fragmento da gramática
utilizada no estudo de caso pode ser visualizado na Listagem 4.3 2.
Os resultados dos testes mostram que o feedparser tem vulnerabilidades para injeção
de HTML. Mostra ainda que um feed RSS pode ser construído facilmente usando gramáti-
cas livres de contexto.
4.1.4 Teste de Protocolo de Rede
Em [Kaksonen, 2001] é apresentado um método que tem como objetivo avaliar a vul-
nerabilidade da implementação de um software, através de testes funcionais. Vulnerabili-
dade é definida como uma falha no projeto ou implementação de um software ou sistema
operacional, que quando explorada por um atacante resulta na violação da segurança de
um computador. Essas vulnerabilidades se apresentam de diferentes formas, como por
exemplo, através do uso de funções de uma biblioteca insegura.
2A gramática original apresentava duas regras idênticas tornando a gramática ambígua. A regra (
link_probe ::= type html html). Para o nosso estudo de caso, retiramos essa duplicação.
48
probes ::= title_probe rights_probe link_probe link_probe;
title_probe ::= type html html;
rights_probe ::= type html html;
link_probe ::= type html html;
type ::= ‘>’ | ‘type=’, html, ‘>’;
lt ::= ‘&lt;’;
gt ::= ‘&gt;’;
html ::= lt ‘script’ attr gt lt ‘/script’ gt;
html ::= lt ‘applet’ attr gt lt ‘/applet’ gt;
html ::= lt ‘embed’ attr gt lt ‘/embed’ gt;
html ::= lt ‘object’ attr gt lt ‘/object’ gt;
html ::= lt ‘meta’ attr gt lt ‘/meta’ gt;
html ::= lt ‘a’ attr gt lt ‘/a’ gt;
attr ::= ’’;
attr ::= ‘style’ value_empty;
attr ::= ‘abbr’ value_empty;
value_empty ::= ‘=’ ‘""’;
Listagem 4.3: Parte da gramática utilizada no estudo de caso - feed RSS
[Hoffman et al., 2010]
O método desenvolvido para este estudo, utiliza gramáticas para modelar a sintaxe de
entrada do software, bem como o seu comportamento. O método fornece os meios para
a criação de modelos a partir de especificações de protocolos. A gramática em BNF é a
notação base para esse método e é usada para especificar os protocolos.
O ponto de partida para projetar