Universidade Federal de Pernambuco

Centro de Ciências Exatas e da Natureza

Centro de Informática

Pós-graduação em Ciência da Computação

Busca Meta-Heurística para Resolução deCSP em Teste de Software

Mitsuo Takaki

Recife

Setembro de 2009

Universidade Federal de Pernambuco

Centro de Ciências Exatas e da Natureza

Centro de Informática

Mitsuo Takaki

Busca Meta-Heurística para Resolução de CSP em Teste deSoftware

Trabalho apresentado ao Programa de Pós-graduação em

Ciência da Computação do Centro de Informática da Uni-

versidade Federal de Pernambuco como requisito parcial

para obtenção do grau de Mestre em Ciência da Computa-

ção.

Orientador: Prof. Dr. Ricardo Bastos Cavalcante Prudêncio

Co-orientador: Prof. Dr. Marcelo Bezerra d’Amorim

Recife

Setembro de 2009

Takaki, Mitsuo Busca meta-heurística para resolução de CSP em teste de software / Mitsuo Takaki. - Recife: O autor, 2009. xi, 105 folhas : il., fig., tab.. Dissertação (mestrado) - Universidade Federal de Pernambuco. CIN. Ciência da Computação, 2009. Inclui bibliografia e apêndice. 1.Inteligência artificial. I. Título. 006.3 CDD (22.ed.) MEI-2009-137

Dedico esta dissertação à minha mãe, minha fonte de

inspiração durante este mestrado.

Agradecimentos

Agradeço à minha mãe, pela constante dedicação e apoio e por ter me mostrado o que é ser

pesquisador. Seu esforço para alcançar o que sonhava me serviu de inspiração neste mestrado.

À minha noiva Roberta, por estar sempre ao meu lado, me apoiando nos momentos mais

difíceis, e por me motivar e ajudar a concluir este trabalho.

Aos meu orientadores Ricardo Prudêncio e Marcelo d’Amorim, por terem me orientado e

ajudado em diversas situações, além do mestrado. Sou grato pelas orientações durante as difi-

culdades que surgiram no desenvolvimento deste trabalho. Obrigado por acreditarem na minha

capacidade e pelas oportunidades que obtive durante este período que trabalhamos juntos.

À professora Flávia Barros, que me orientou inicialmente, e que sem o seu apoio não estaria

onde estou agora. Obrigado pela oportunidade e pela confiança no meu trabalho.

Ao meu amigo Márcio Ribeiro, que, graças aos conhecimentos que me passou, pude con-

cluir este trabalho. Aos meus amigos Edeilson, Edilson, Eduardo, Leopoldo, Mário, Paulo e

Ivan pela convivência e apoio durante este mestrado.

iv

Resumo

Os algoritmos de busca meta-heurística vêm sendo pesquisados em inúmeros domínios, in-

clusive na resolução de restrições. Devido à sua capacidadede atuação em problemas que a

solução é desconhecida, são utilizados em diversas situações. Os algoritmos evolutivos são uma

família dos algoritmos de busca, que simulam o comportamento da natureza. Os problemas de

satisfação de restrição (CSP) são compostos por um conjunto de conjunções de variáveis, ca-

racterizando uma restrição. Valores são associados às variáveis, os quais devem satisfazer a

restrição, caso contrário, são considerados inválidos. Problemas de resolução de restrição estão

associados a diversos contextos, desde problemas de alocação de recursos a design de circuitos

integrados. Algoritmos de busca meta-heurística vêm sendoutilizados para a solução de CSP,

resolvendo o problema da limitação dos provadores de teoremas, que necessitam modelar uma

teoria para serem capazes de encontrar uma solução. Neste trabalho, investigamos o uso do

algoritmo de busca meta heurística em um tipo de teste de software (execução concólica) que

é tratado como um problema de CSP. A execução concólica se baseia no teste simbólico, o

qual extrai as decisões internas de um programa que formam uma restrição, também conheci-

das como Path Condition (PC). Estas restrições são formadas a partir das variáveis de entrada,

portanto, a solução de uma restrição determina as entradas necessárias para percorrer um deter-

minado caminho no software. As técnicas clássicas utilizamprovadores de teoremas, os quais

são limitados a teoria suportada, e métodos de randomização, que geram valores aleatórios

para as variáveis, reduzindo a complexidade da restrição. Apresente dissertação teve como

objetivo criar e analisar o desempenho de solucionadores baseados em algoritmos de busca

meta-heurística, sendo comparados às técnicas clássicas utilizadas neste contexto. Os resulta-

dos mostraram que o uso de heurísticas de busca pode permitira criação de novas técnicas de

resolução de restrição, no contexto de teste simbólico.

Palavras-chave: Problema de Satisfação de Restrição, Execução Concólica, Algoritmos de

Busca Meta-Heurística

v

Abstract

The meta-heuristic search algorithms have been researchedin several domains, including in

constraint satisfaction problem. Due to its good adaptability to be used in problems where the

actual solution is unknown, they are applied in innumerous contexts. The evolutive algorithms

are a search algorithm family that simulates the nature behavior. The constraint satisfaction

problem (CSP) is a set of variables conjunction, compoundinga constraint. Values are associ-

ated to the variables, which should satisfy the constraint;otherwise, it violates the restriction.

CSP are related to innumerous domains, from resource allocation to integrated circuits design.

Meta-heuristic search algorithms have been used for solving CSP, surpassing the theorem pro-

ver limitation problem that needs a theory modeling in orderto be able to find a solution. This

work, we investigated the usage of meta-heuristic search algorithms in a kind of software test

(concolic execution) that is dealt as a constraint satisfaction problem. The concolic execution is

based on the symbolic test, which is a technique used to gather internal decisions of software,

which compound a restriction also called as Path Condition (PC). These restrictions are formed

by the input variables, thus, the solution of them is used as input data to traverse a specific

path in the software. The classical techniques use theorem prover, which are constrained by the

theory supported, and randomization methods, that generates random values for the variables,

reducing the constraint complexity. The current dissertation had as main objective to create and

analyze the performance of meta-heuristic search based solvers, being compared to the classi-

cal techniques used in this context. The results have shown that the usage of search heuristics

may allow the creation of new constraint satisfaction techniques in the symbolic test domain.

Keywords: Constraint Satisfaction Problem, Concolic Execution, Meta-Heuristic Search Al-

gorithms

vi

Sumário

1 Introdução 1

1.1 Objetivos 3

1.2 Organização da Dissertação 5

2 Busca Meta-Heurística 7

2.1 Algoritmos de Busca e Otimização 7

2.2 Busca Local e Global 10

2.3 Algoritmos Evolutivos 11

2.3.1 Algoritmos Genéticos (AG) 11

2.3.2 Otimização por Enxame de Partículas (PSO) 11

2.3.3 Influência da Dimensionalidade e Tamanho da População 15

2.4 Problema de Satisfação de Restrições (CSP) 16

2.4.1 Algoritmos Completos 16

2.4.2 Algoritmos Incompletos 17

2.4.3 Algoritmos Evolutivos em CSP 17

2.5 Considerações Finais 18

3 Teste de Software 20

3.1 Teste de Software 20

3.2 Técnicas de Teste 21

3.3 Fases de Teste 23

3.4 Testes de Caixa Preta 25

3.5 Testes de Caixa Branca 28

3.6 Critérios de Adequação e Métricas 29

3.7 Criação de Casos de Teste 31

3.8 Teste Simbólico 32

3.8.1 Problema de Resolução de Restrições no Contexto de Teste Simbólico 33

vii

SUMÁRIO viii

3.9 Execução Concólica 34

3.10 Teste Randômico 35

3.11 Considerações Finais 36

4 Metodologia 38

4.1 Framework 38

4.1.1 Biblioteca Simbólica e Instrumentador 40

4.1.2 Driver 41

4.1.3 Solvers 41

4.1.4 SolversHíbridos 44

4.2 Representação do Problema 45

5 Experimentos 49

5.1 Descrição dos Experimentos 49

5.2 Resultados Gerais 52

5.2.1 Impacto dotimeout 55

5.2.2 Impacto dos Parâmetros dos Algoritmos de Busca 62

5.3 Discussão dos Resultados 66

5.4 Considerações Finais 70

6 Conclusões 71

6.1 Contribuições 71

6.2 Limitações e Trabalhos Futuros 72

6.3 Considerações Finais 74

A Gráficos 75

B Tabelas 79

C Códigos Fonte 89

Lista de Figuras

1.1 Conjunto de decisões internas. 3

2.1 Mínimo local e global. 8

2.2 Exemplo de um vale. 10

2.3 Operadores decross-overe mutação. 12

2.4 Algoritmo genético. 13

2.5 Algoritmo do PSO. 14

2.6 Exemplos de topologias. 15

3.1 Processo de Testes. 21

3.2 Processo de Testes. 23

3.3 Fases de Teste e Seus Requisitos. 24

3.4 Teste de Unidade. 25

3.5 Exemplo de um grafo de causa e efeito. 27

3.6 Exemplo de código fonte com umbranch. 30

3.7 Exemplo de código fonte com umloop. 30

3.8 Gráfico do custo relativo de correção de um defeito. 33

3.9 Conjunto de decisões internas (Path Condition). 34

3.10 Exemplo de um PC. 35

4.1 Arquitetura utilizada. 39

4.2 Exemplo de uma árvore semântica. 40

4.3 Código fonte de BST original e instrumentado. 42

4.4 Driver do programa BST. 43

4.5 Arquitetura utilizada pelossolvers. 44

4.6 Representação no plano cartesiano dos espaço de busca. 47

4.7 Operação de transposição da representação do problema para a árvore semântica. 48

ix

LISTA DE FIGURAS x

5.1 Diagrama de Venn do desempenho dossolversaleatórios. 56

5.2 Diagrama de Venn do desempenho dossolvershíbridos GCF. 57

5.3 Diagrama de Venn do desempenho dossolvershíbridos BCF. 58

5.4 Diagrama de Venn do desempenho dossolvershíbridos. 59

5.5 Comportamento da função MaxSAT. 60

5.6 Comportamento da função SAW. 61

5.7 Cobertura dossolversnos programasSwitcheColt 63

5.8 Influência dos parâmetros de AG. 64

5.9 Influência dos parâmetros de AG. 65

5.10 Influência dos parâmetros de PSO. 67

5.11 Influência dos parâmetros de PSO. 68

A.1 Cobertura dossolversutilizando gráfico de barras empilhadas no experimento

BST. 75

A.2 Cobertura dossolversutilizando gráfico de barras empilhadas nos experimen-

tosFileSystemeTreeMap. 76

A.3 Cobertura dossolversutilizando gráfico de barras empilhadas nos experimen-

tosRatPolyeRationalScalar. 77

A.4 Cobertura dossolversutilizando gráfico de barras empilhadas nos experimen-

tosNewtoneHashMap. 78

Lista de Tabelas

4.1 Exemplo de uma representação através de um código genético. 46

5.1 Comparação dos Experimentos. 52

5.2 Tabela da cobertura média dos pares: experimento (linha) esolver(coluna). 53

5.3 Desvio padrão da tabela 5.2. 54

B.1 Comparação dos resultados dossolversno experimentoBST. 80

B.2 Comparação dos resultados dossolversno experimentoFileSystem. 81

B.3 Comparação dos resultados dossolversno experimentoTreeMap. 82

B.4 Comparação dos resultados dossolversno experimentoSwitch. 83

B.5 Comparação dos resultados dossolversno experimentoRatPoly. 84

B.6 Comparação dos resultados dossolversno experimentoRationalScalar. 85

B.7 Comparação dos resultados dossolversno experimentoNewton. 86

B.8 Comparação dos resultados dossolversno experimentoHashMap. 87

B.9 Comparação dos resultados dossolversno experimentoColt. 88

xi

CAPÍTULO 1

Introdução

Os algoritmos de busca meta-heurística constituem uma família de algoritmos utilizados na

solução de diversos problemas percorrendo um espaço de busca. O termo meta-heurística foi

inicialmente utilizado por Glover (1986), onde é descrito oalgoritmoTabu Searchcomo uma

meta-heurística sobreposta em outra heurística. Podem seraplicados em diversos contextos,

desde o design de circuitos integrados à teste de técnicas decriptografia (Silva e Sakallah;

1996).

O algoritmo de força bruta, ou busca cega, é o mais simples exemplo de um método de

busca, percorrendo todo o espaço de busca até que uma soluçãoseja encontrada. Este método

é capaz de garantir que, se existir, uma solução será encontrada, porém o tempo de busca

pode se tornar extremamente grande. Neste sentido, métodosque criam uma solução aleatória

e, iterativamente, melhoram até encontrar uma solução aceitável tornam possível encontrar

soluções em um espaço de tempo mais aceitável. Porém, estes métodos são algoritmos de

busca local, ou seja, não são capazes de transpor áreas de mínimos ou máximos locais, portanto

nescessitam de diferentes inicializações para buscar a melhor solução (mínimo ou máximo

global). Um exemplo de um método iterativo de melhoria de solução é o algoritmo de subida

da encosta (hill climbing), que simula a subida de uma colina e pára sua execução quando

chega ao topo. Para resolver o problema da transposição de áreas de mínimos ou máximos

locais, foram propostos diferentes algoritmos, como exemplo a têmpera simulada (simulated

annealing) (Kirkpatrick et al.; 1983). O algoritmo inicia realizandograndes passos e o tamanho

dos passos é reduzido gradativamente, permitindo percorrer grandes espaços no inicio e realizar

pequenos incrementos no final (Russell e Norvig; 2003, p. 94-131).

O algoritmo genético (AG) (Holland; 1975) e a otimização porenxame de partículas (Par-

ticle Swarm Optimization– PSO) (Kennedy e Eberhart; 1995) fazem parte dos algoritmosde

busca, mais especificamente dos algoritmos evolutivos, e sebaseiam em comportamentos ob-

servados na natureza. AG foi proposto para introduzir o comportamento de adaptação aos siste-

mas. PSO foi criado por Kennedy e Eberhart (1995) a partir da observação do comportamento

1

CAPÍTULO 1 INTRODUÇÃO 2

de grupos, o qual mimetiza a criação de estruturas sociais, onde indivíduos podem influenciar

o grupo e, ao mesmo tempo, os indivíduos são influenciados pelo grupo. Eles são métodos

de busca global, ou seja, são capazes de transpor áreas de mínimos, ou máximos, locais. Os

mínimos, ou máximos, locais são soluções do espaço de busca,porém não são as melhores

soluções de um problema. Em problemas de otimização, o algoritmo busca pelo mínimo ou

máximo global. A função objetivo, ou função defitness, direciona o algoritmo, avaliando a

qualidade das soluções candidatas. O algoritmo de subida daencosta, têmpera simulada, AG e

PSO podem ser denominados, de uma forma geral, de métodos de busca meta-heurística. Por

outro lado, o algoritmo de força bruta não é considerado uma meta-heurística por não utilizar

nenhuma heurística na busca da solução, pois o algoritmo percorre exaustivamente o espaço de

busca.

Algoritmos de busca meta-heurística têm sido usados com freqüência em problemas de

resolução de restrições (ouconstraint satisfaction problem, CSP). O problema de resolução de

restrições é a determinação de valores para variáveis que compõem uma restrição. Este tipo

de problema está relacionado a diversos contextos, desde o problema clássico de coloração de

grafos à problemas de alocação. O uso de algoritmos de busca neste contexto é bem conhecido

pelo comunidade (Zhou et al.; 2009; Lin; 2005; Rossi et al.; 2000; Marchiori e Rossi; 1999;

Folino et al.; 1998). Um exemplo de CSP é atribuir valores às variáveis (x e y) de forma a

satisfazer todas as cláusulas da seguinte sentença:(x = y2)∧ (x < 10)∧ (y≥ 0), onde uma

possível solução para esta restrição é:x = 4 ey = 2.

Diversas soluções foram propostas no desenvolvimento de funções defitness, mais especifi-

camenteMaxSAT (Folino et al.; 1998; Rossi et al.; 2000; Marchiori e Rossi; 1999) eStep-Wise

Adaptation of Weigths (SAW) (Bäck et al.; 1998; Eiben e van der Hauw; 1997). MaxSAT ape-

nas conta o número de cláusulas satisfeitas, o que permite identificar quando uma solução

candidata satisfaz a restrição. Entretanto, MaxSAT não é capaz de direcionar corretamente o

algoritmo, pois nem sempre encontrar uma solução candidataque resolve a maior parte das

cláusulas significa estar na direção correta. SAW utiliza ummétodo de identificar cláusulas

“difíceis” de resolver, atribuindo pesos as mesmas. Desta forma, a solução candidata que re-

solve uma cláusula difícil, deve ser recompensada por isto –através de um valor defitnessmais

alto.

O foco da presente dissertação é a resolução de CSP no contextode teste desoftware, mais

especificamente com teste simbólico. O teste simbólico é umatécnica de extração do conjunto

1.1 OBJETIVOS 3

Figura 1.1: Um exemplo de um conjunto de decisões internas.

de decisões internas de um sistema – também chamado dePath Condition(PC) –, as quais

caracterizam uma restrição e o conjunto de dados de entrada são as variáveis destas restrições.

Na figura 1.1 está um exemplo de um programa, onde as seguintesrestrições são geradas:

(x> y)∧(x%2= 0), (x> y)∧(x%2 6= 0), (x≤ y)∧(y % 2= 0) e(x≤ y)∧(y % 2 6= 0). Existem

soluções clássicas para resolver estes restrições, as quais envolvem o uso de provadores de

teorema. Os provadores de teorema possuem um poder de atuação limitado à teoria suportada.

Facilmente programas simples geram restrições não-lineares, como no exemplo da figura 1.1

que possui operador de resto de divisão (%). Ossolversaleatórios são capazes de resolver

restrições, independente do tipo de operador utilizado. Esta característica permite que estes

sejam aplicados na resolução de CSP, onde apresentam resultados motivantes (Godefroid et al.;

2005; Majumdar e Sen; 2007).

1.1 Objetivos

As soluções propostas por Godefroid et al. (2005) e Majumdare Sen (2007) não utilizam ne-

nhum tipo de heurística na geração de valores para a resolução de restrições ou para reduzir

a complexidade das restrições. Os resultados obtidos por estas técnicas produziram resultados

1.1 OBJETIVOS 4

motivantes e o uso de meta-heurísticas de busca pode produzir melhores resultados. O principal

objetivo deste trabalho é a aplicação de meta-heurísticas de busca emsolverspara resolver res-

trições provenientes de uma execução concólica, além de analisar o desempenho destessolvers

emsoftwarescom diferentes características.

O trabalho de Lakhotia et al. (2008) utilizou o algoritmo de subida da encosta para resolução

de restrições da execução concólica, porém o uso de algoritmos evolutivos, neste contexto, não

havia sido proposto anteriormente. O uso destes algoritmospara a resolução de restrições é a

principal contribuição deste trabalho.

Ossolversbaseados em algoritmos de busca foram propostos de duas formas: usados dire-

tamente e combinados aosolversimbólico (symSOL). Ossolvershíbridos utilizam três estra-

tégias: restrições “boas” primeiro (Good Constraints First– GCF), restrições “ruins” primeiro

(Bad Constraints First– BCF) e variáveis “ruins” primeiro (Bad Variables First– BVF). GCF

e BCF separa as restrições em partes “boas” e “ruins”. São chamadas de “boas” as restrições

que estão dentro do escopo da teoria suportada por symSOL e, conseqüentemente, “ruins” as

que estão fora do escopo. GCF resolve primeiro as restrições “boas” no symSOL e passa o

restante para osolverrandômico (puramente aleatório, AG ou PSO). Isto permite que a restri-

ção seja simplificada, gerando uma nova restrição reduzida.De forma contrária, BCF resolve

as restrições “ruins” primeiro, passando para symSOL uma restrição com complexidade redu-

zida, permitindo que este a resolva. BVF, se baseia no DART Godefroid et al. (2005), gerando

valores aleatórios para as variáveis que compõem as cláusulas não satisfatíveis por symSOL.

Nesta dissertação, foram avaliadas quatro abordagens clássicas, umsolversimbólico e três

híbridos. Trêssolversaleatórios foram comparados, utilizando um algoritmo puramente ale-

atório, AG e PSO. Às estratégias de hibridação, exceto BVF, foram combinados ossolvers

baseados em AG e PSO, substituindo osolverpuramente aleatório mais comumente utilizado.

Nesta avaliação foram utilizados nove experimentos, algumas implementações de estruturas

conhecidas, como árvore binária de busca e tabela de hash, e bibliotecas de uso matemático.

A partir da análise do desempenho dossolversnos experimentos escolhidos, foi possível

observar que o uso de meta-heurísticas de busca produz bons resultados, especialmente em

situações que o uso de umsolver simbólico não é possível ou sua capacidade de atuação é

limitada. Problemas em que o espaço de busca se torna muito grande, ossolversque utilizam

geração de valores puramente aleatória não são capazes de resolver a maior parte das restrições

geradas. Entretanto, em espaços de busca reduzidos o uso de heurísticas não se justifica devido

1.2 ORGANIZAÇÃO DA DISSERTAÇÃO 5

seu maior custo computacional.

1.2 Organização da Dissertação

Este trabalho está organizado da seguinte forma:

Capítulo 2 Introdução aos algoritmos de busca, passando pelo principais métodos de busca

iterativa e introdução aos algoritmos evolutivos. O problema de satisfação de restrições (CSP)

é apresentado e como estes algoritmos podem ser aplicados neste contexto. Considerando o

objetivo deste trabalho ser uma aplicação de algoritmos evolutivos em CSP, é dado uma maior

ênfase nestes algoritmos e suas aplicações em CSP, sendo apresentada uma proposta de repre-

sentação do problema e a determinação o espaço de busca de acordo com esta representação.

Capítulo 3 Introdução ao teste desoftware, separando em dois grupos: funcionais e estruturais.

Em cada grupo estão definidos os tipos de testes e seus critérios de adequação. O problema

da automação da geração de casos de teste é apresentado com a solução abordada no presente

trabalho:teste simbólico. O teste simbólico possui deficiências que são supridas com oadvento

da execução concólica. Esta solução determina a capacidadede suprir as lacunas deixadas pelo

teste simbólico. São apresentados ospath conditions(PC) e como estes podem ser vistos como

um CSP. O uso de provadores de teoremas (solverssimbólicos – symSOL) para a resolução

destes PCs, abordando que esta solução não é aplicável, pois freqüentemente uma aplicação

simples pode gerar restrições que estão fora do escopo do provador. No caso em que symSOL

é capaz de resolver problemas de aritmética inteira linear,estes PCs podem ser simplificados à

uma forma satisfatível. Esta solução é apresentada, contudo, suas deficiências são identificadas.

Capítulo 4 A metodologia utilizada é apresentada, com a arquitetura proposta para o desenvol-

vimento doframework, onde cada componente doframeworké apresentado. A representação

do problema escolhida é apresentada com suas possíveis implicações na definição do espaço de

busca.

Capítulo 5 A solução proposta para prover uma heurística aos métodos derandomização de

restrições é apresentada. São identificadas deficiências nos algoritmos escolhidos e como seu

desempenho é afetado pelo tempo de execução (timeout). Os experimentos escolhidos são

1.2 ORGANIZAÇÃO DA DISSERTAÇÃO 6

detalhados e caracterizados pelo tipo de restrição que sua execução gera. Os resultados obtidos

são apresentados, comparando o desempenho de cadasolverem nove experimentos. Os efeitos

do timeoute variação doseeddo número aleatório são analisados. Além disso, uma discussão

sobre as características dos algoritmos de busca de acordo com o experimento é realizada e

demonstradas as conclusões extraídas dos resultados.

Capítulo 6 As conclusões deste trabalho são apresentadas, como também, as contribuições,

limitações e perspectivas para os pontos de melhoria que poderão gerar mais investigação.

CAPÍTULO 2

Busca Meta-Heurística

Este capítulo apresenta uma introdução aos algoritmos de busca meta-heurística e o problema

de satisfação de restrições (Constraint Satisfaction Problem - CSP), dando uma ênfase maior

aos algoritmos evolutivos e suas aplicações em CSP. Ossolversde CSP estão sendo apresen-

tados, separados, em dois grupos: completos e incompletos.Os algoritmos incompletos se

referem ao tema principal nesta seção, visto que o objetivo deste trabalho é a aplicação de

algoritmos de busca meta-heurística na resolução de restrições.

2.1 Algoritmos de Busca e Otimização

A inteligência artificial vem sendo utilizada na resolução de problemas e, mais especifica-

mente, em problemas de otimização. A resolução automática érealizada através de métodos

inteligentes, onde a aquisição de conhecimento pode ocorrer durante a execução ou previa-

mente. Existem diversas técnicas, sendo que cada uma possuicaracterísticas que a tornam apta

a resolver problemas específicos. Contudo, não existe um método capaz de resolver qualquer

problema, este deve ser escolhido de acordo com o contexto.

São chamados de problemas de otimização os problemas que requerem que seus dados

sejam modificados para que atinjam um certo grau de qualidade. Vão desde problemas de rota

(e.g., problema do caixeiro viajante) até problemas complexos de otimização de funções. Os

problemas podem ser definidos por quatro componentes, segundo Russell e Norvig (2003, cap.

3): o estado inicial, as ações possíveis, o teste de objetivoe uma função de custo. Para resolver

os problemas, os algoritmos de otimização realizam uma busca de soluções em um espaço de

estados.

Máximo global (ou mínimo global) é a melhor solução em todo espaço de busca, a qual é

o objetivo de todos os problemas de otimização. Máximo local(ou mínimo local) é a melhor

solução em um subespaço de busca. Um exemplo de uma função e seu mínimo global e local

7

2.1 ALGORITMOS DE BUSCA E OTIMIZAÇÃO 8

Figura 2.1: Uma função de exemplo com seu mínimo global (círculo vermelho) e seu mínimo

local (triângulo azul).

é apresentada na figura 2.1. Algoritmos de busca que melhoramseus resultados sem guardar

estados anteriores tendem a ficarem presos em máximos locais.

Os algoritmos de busca procuram por soluções para um problema específico, em um grande

espaço de possíveis soluções. Uma função defitness, também chamada de função objetivo,

é utilizada para validar estes candidatos e medir a qualidade desta solução. Os algoritmos

de busca podem ser utilizados quando não há um conhecimento sobre a solução real para o

problema, entretanto, a função defitnessdeve ser capaz de identificar quando a solução foi

encontrada. Muitas pesquisas vem sendo realizadas nesta área e várias novas técnicas foram

propostas, cada uma aplicável a um determinado domínio. Dentre essas técnicas citamos inici-

almente:

• Busca por força-bruta

Também conhecido como busca cega, é o mais simples. Utiliza um método simples, o

qual precisa percorrer todo o espaço de busca, que, dependendo do problema, pode de-

mandar um esforço imenso. Toda possível solução deve ser analisada e nenhum conhe-

cimento é adquirido durante este processo. O uso de algoritmos baseados em heurísticas

pode reduzir o tempo gasto nesta operação. Entretanto, o algoritmo de força-bruta é ca-

2.1 ALGORITMOS DE BUSCA E OTIMIZAÇÃO 9

paz de garantir a existência, ou a ausência, de soluções parao problema, apesar de o

tempo aumentar consideravelmente quando o número de estados aumenta. Mas, eventu-

almente, a melhor solução será encontrada. Quando não há umalimitação de tempo, esta

torna-se a melhor escolha para um problema de otimização.

• Subida da encosta (Hill-Climbing)

Algoritmo iterativo de melhoria, em outras palavras, ele melhora sua solução inicial passo

a passo. A solução inicial é escolhida aleatoriamente e, então, é melhorada até atingir um

resultado aceitável. Esta técnica não armazena estados anteriores, move-se no espaço de

busca enxergando apenas o estado atual (Russell e Norvig; 2003, p. 94-131). Portanto,

não é capaz de atingir resultados ótimos, apesar de eventualmente poder atingir, mas

fornece soluções aceitáveis, as quais necessitariam de um longo período de tempo para

serem encontradas pelo algoritmo de força bruta. Devido a sua inicialização estocástica,

este algoritmo torna-se sensível à sua inicialização, ou seja, depende fortemente de um

bom estado inicial para encontrar o máximo global.

• Têmpera Simulada (Simulated Annealing)

O algoritmo de subida da encosta não é capaz de realizar movimentos de “descida” da

encosta para que possa sair de um máximo local. Introduzir uma certa aleatoriedade à

subida da encosta, pode trazer melhorias ao seu desempenho,permitindo que este saia

de picos e encontre novos máximos locais – podendo eventualmente encontrar o má-

ximo global. Criado por Kirkpatrick et al. (1983), foi inspirado na metalurgia, a têmpera

é o processo utilizado para temperar ou endurecer metais e vidros, aquecendo-os a al-

tas temperaturas e depois resfriando-os gradualmente. Um comportamento análogo é

reproduzido no algoritmo da têmpera simulada, que inicia sua busca com um grau de

exploração do espaço de estados alto e gradativamente reduzessa exploração.

• Algoritmos Evolutivos

É uma família de algoritmos baseados em comportamentos da natureza. Dentre estes

algoritmos, se destacam o algoritmo genético (Holland; 1975) e a otimização por enxame

de partículas (Kennedy e Eberhart; 1995). Estes algoritmosserão detalhados na seção

2.3.

2.2 BUSCA LOCAL E GLOBAL 10

Figura 2.2: Um função de exemplo onde é possível observar umaárea defitnesshomogêneo ou

um vale.

2.2 Busca Local e Global

Os algoritmos de busca local operam utilizando apenas um estado, o qual é melhorado itera-

tivamente. A busca local é uma meta-heurística (Glover; 1986) de busca por soluções, onde

uma solução inicial é aprimorada passo a passo, enxergando apenas estados anteriores. Este

comportamento acarreta em uma busca que, apesar de manter umhistórico, é incapaz de sair

de vales ou transpor áreas defitnesshomogêneo. Estas situações podem ser observadas na

figura 2.2, onde um exemplo de área comfitnesshomogêneo é apresentada. Nesta situação,

o algoritmo local não é capaz de sair de um vale, pois não ocorre incremento nofitnessem

nenhuma das direções. Além de vales, há também as situações de máximo (ou mínimo) locais

apresentadas na figura 2.1.

A busca global é utilizada de forma contrária à busca local. Esta visa encontrar a solução

ótima em um grande espaço de busca utilizando-se operações menos refinadas, mas que cobrem

uma maior área. Algumas estratégias de busca vêm utilizandoalgoritmos que combinam buscas

globais e locais. Soluções são geradas, a partir da busca global, e estas são refinadas utilizando

uma busca local.

2.3 ALGORITMOS EVOLUTIVOS 11

2.3 Algoritmos Evolutivos

Os algoritmos evolutivos são algoritmos de busca que utilizam operadores baseados em fenô-

menos da natureza. São chamados de evolutivos devido a esta característica de mimetizar estes

fenômenos naturais. Dentre os algoritmos mais populares, podemos citar os:Algoritmos Ge-

néticoseOtimização por Enxame de Partículas.

2.3.1 Algoritmos Genéticos (AG)

Algoritmos genéticos foram propostos por Holland (1975) para introduzir uma capacidade de

adaptação aos programas. Pesquisas na área de reprodução decomportamentos da natureza

produziram novas técnicas, como algoritmos baseados em inteligência de grupos (swarm intel-

ligence). Diferentemente de outras estratégias evolutivas, Holland (1975) analisou o fenômeno

de adaptação, como acontece na natureza, e como aplicá-lo aos sistemas de computadores.

AG é baseado na teoria evolutiva das espécies, que evoluem para melhorar suas capacida-

des de adaptação, de acordo com o ambiente. Cada solução candidata, chamada de indivíduo,

é modelada em uma estrutura de cromossomos e aplicada operações de recombinação a essas

estruturas, onde a preservação de informações criticas é o objetivo. Esta operação de recom-

binação é chamada decross-overe pode ser observada na figura 2.3a. Operadores de mutação

também são utilizados para modificar, levemente, as soluções (Whitley; 2002). A figura 2.3b

apresenta um exemplo de operação de mutação. Estas operações são realizadas entre a popula-

ção de soluções até que um certo grau de qualidade é atingido,de acordo com a funçãofitness

onde cada população de uma iteração é chamada degeração.

O algoritmo genético provê soluções viáveis em diversas áreas, onde variações do algoritmo

básico são utilizadas. Estas áreas vão desde problemas científicos a problemas de engenharia

(Mitchell; 1998). Alguns sistemas devem ser capazes de se adaptar a um ambiente em cons-

tante mudança, comportamento análogo ao fenômeno da natureza em que indivíduos devem se

adaptar para continuarem sua existência. O algoritmo básico do AG está na figura 2.4.

2.3.2 Otimização por Enxame de Partículas (PSO)

Kennedy e Eberhart (1995) propuseram a otimização por enxame de partículas, inspirado pelo

comportamento descentralizado de grupos. Cada partícula é um protótipo de solução e cada

2.3 ALGORITMOS EVOLUTIVOS 12

(a)Cross-Over

(b) Mutação

Figura 2.3: Operadores decross-overe mutação.

uma possui um grau de confiança em si mesma e um grau de confiançano grupo. As partículas

movem-se através do espaço de busca visando um resultado ótimo, enquanto informações são

adquiridas do problema para melhorar seu desempenho. O grupo armazena a melhor partícula

e cada partícula armazena sua melhor solução, até o momento.Estes dados influenciam a pró-

xima posição de cada partícula. As equações (2.1) e (2.2) mostram como a velocidade e a nova

posição são calculadas.r1 e r2 são números aleatórios entre 0 e 1, definidos durante a criação

de cada partícula, para criar uma distribuição homogênea dediferentes comportamentos, onde

existirão indivíduos com maior confiança em si mesmo, indivíduos com maior confiança no

grupo e indivíduos com um comportamento mais balanceado. Ser1 tende a zero, a confiança

da partícula em si mesma tende a zero e quandor2 tende a zero, a partícula tende a não confiar

no grupo. ω é chamado de inércia e é a proporção da velocidade anterior que será usado napróxima velocidade, proporciona uma mudança gradativa na direção do movimento da partí-

cula. Diferentemente de outros algoritmos evolutivos, PSOnão usa operadores decross-over

e mutação. O espaço de busca é percorrido pelo PSO através dasmudanças de posição das

partículas.

O grupo exerce uma influência em cada indivíduo, fazendo com que este siga a direção do

grupo. Entretanto, os indivíduos também exercem influênciano grupo, pois um indivíduo pode

2.3 ALGORITMOS EVOLUTIVOS 13

Algoritmo Algoritmo Genético

Entrada

n: Tamanho da população.

c: Taxa de cruzamento.

m: Taxa de mutação.

g: Número de gerações.

Saída

p: Conjunto de soluções candidatas.

1 init (p) { Inicializando a população.}

2 enquanto iteration< g||solutionFoundfaça

3 para i← 0. . .n faça

4 f itness(p[i])

5 order(p) { Ordena a população de acordo com o fitness de cada um.}

6 para i← 0. . .n faça{ Sorteia dois indivíduos para o cruzamento.}

7 indexFather← random(n)

8 indexMother← random(n)

9 shouldBreed← random()

10 shouldMutate← random()

11 seshouldBreed≥ c então

12 newSub jects← breed(p[indexFather], p[indexMother])

13 add(p,newSub jects)

14 seshouldMutate≥mentão

15 mutate(newSub jects)

16 para i← 0. . .n faça

17 seeval(p[1]) então

18 solutionFound← true

19 iteration← iteration+1

Figura 2.4: Algoritmo genético.

2.3 ALGORITMOS EVOLUTIVOS 14

vt+1 = ω ∗vt + r1∗c1∗ (bestsolutionparticle−xi)+ r2∗c2∗ (bestsolutiongroup−xi) (2.1)

xt+1 = xt +vt+1 (2.2)

Algoritmo PSO

Entrada

n: Tamanho da população.

ω: Inércia.c1: Grau de confiança na própria partícula.

c2: Grau de confiança na população.

g: Número de gerações.

Saída

p: Conjunto de soluções candidatas.

1 init (p) { Inicializando a população.}

2 enquanto iteration< g||solutionFoundfaça

3 para i← 0. . .n faça

4 f itness(p[i])

5 para i← 0. . .n faça{ Atualiza velocidade e posição.}

6 updateVelocity(p[i])

7 updatePosition(p[i])

Figura 2.5: Algoritmo do PSO.

tornar-se, em um determinado momento, a melhor solução do grupo (Li e Engelbrecht; 2007).

PSO é capaz de atingir bons resultados em, relativamente, poucos passos – se comparado ao

algoritmo genético. É bastante útil em problemas que utilizam dados de ponto flutuante e alta

dimensionalidade. Dimensionalidade é o número de dimensões do espaço de busca. Também

possui uma implementação bastante simples, o que o torna um algoritmo eficiente. Na figura

2.5, é possível observar o algoritmo básico do PSO.

As partículas podem ser organizadas através de uma topologia que determina como estas

irão se comportar e interagir uma com as outras. Partículas são influenciadas pelos vizinhos e

estas influenciam sua vizinhança. Na formação destas vizinhanças não se deve levar em conta a

2.3 ALGORITMOS EVOLUTIVOS 15

(a) Anel (b) Estrela

Figura 2.6: Exemplos de topologias utilizadas para determinar vizinhanças.

distância física, geralmente são utilizados seus rótulos (label) para determinar quais partículas

fazem parte do mesmo grupo.

As vizinhanças criam estruturas sociais que indicam com quais partículas um indivíduo

deve interagir (Lin; 2005). Esta estrutura é determinante no desempenho do algoritmo. Estas

estruturas podem utilizar formas já conhecidas, como estrela, anel, entre outros, como pode

ser visto na figura 2.6. Como esta determina a interação entre as partículas, vai determinar o

comportamento das mesmas no espaço de busca.

2.3.3 Influência da Dimensionalidade e Tamanho da População

O desempenho de algoritmos de busca é diretamente afetado com o aumento da dimensionali-

dade. Para problemas com um alto número de dimensões, ou seja, um vasto espaço de busca,

um número maior de partículas/indivíduos é necessário. Porém, com o aumento do tamanho

da população, o desempenho é degradado. A. Carlisle (2001) realizou diversos experimentos

e identificou, empiricamente, que uma população de 30 partículas é suficiente para resolver

muitos problemas de baixa dimensionalidade. Parsopoulos (2009) fez uma análise do desem-

penho do PSO em problemas com uma alta dimensionalidade (n≥ 100, onden é o número de

dimensões) e percebeu que PSO começa a perder desempenho devido ao tamanho do espaço

de busca. Parsopoulos (2009) propõe um novo algoritmo, chamado de (µPSO), para problemasde alta dimensionalidade.µPSO mantém um baixo custo computacional, enquanto minimizao

2.4 PROBLEMA DE SATISFAÇÃO DE RESTRIÇÕES (CSP) 16

impacto do aumento do número de dimensões.

2.4 Problema de Satisfação de Restrições (CSP)

O problema de satisfação de restrições (CSP) está relacionado à determinação de valores para

variáveis que satisfaçam ou atendam a um dado conjunto de restrições. Segundo Russell e

Norvig (2003, cap. 5), CSP é definido por um conjunto de variáveis x1,x2, . . . ,xn e por um

conjunto de cláusulasC1,C2, . . . ,Cn. Cada cláusulaCi envolve um subconjunto de variáveis e

valores atribuídos. Cada variávelxi possui um domínioDi, não-vazio, de valores possíveis. E

um estado do problema é uma atribuição a um conjunto de variáveis{xi = vi,x j = v j}, onde

vi ∈ Di . Quando uma atribuição não viola nenhuma restrição, então échamada de consistente

ou válida. CSP vem sendo pesquisado em vários contextos, desde design de circuitos integrados

através de computador a testes de criptografia (Eibach et al.; 2008). Um problema clássico de

CSP é o problema de coloração mapas, um caso específico do problema de coloração de grafo.

Neste caso, a cada região do mapa deve ser atribuída uma cor, sem que haja regiões vizinhas

com a mesma cor.

A criação desolversautomáticos vem evoluindo devido à crescente necessidade da comu-

nidade. Um dos ramos de pesquisa nesta área utilizasolversaleatórios, que geram valores para

satisfazer a restrição. Alguns resultados foram motivantes e aumentaram a pesquisa no uso de

solversaleatórios e sua aplicação em outras áreas. Existem vários algoritmos propostos para

resolver CSP, alguns são completos e outros incompletos.

2.4.1 Algoritmos Completos

Alguns algoritmos completos foram desenvolvidos para resolver o problema de satisfação de

restrições. Estes algoritmos são capazes de garantir que uma restrição é satisfatível ou insatis-

fatível de acordo com seu suporte de teoremas interno.

Provadores de teorema vêm sendo utilizados para este propósito, ou seja, resolver pro-

blemas de resolução de restrição. Porém estes apresentam uma desvantagem: possuem uma

capacidade de atuação limitada, pois necessitam que um teorema seja modelado e introduzido

ao mesmo. Devido esta limitação, não existe umsolvercompleto disponível para todo tipo de

teorema. Um exemplo é o CVC3 (CVC3 web page; s.d.). O solucionador CVC3 é um provador

2.4 PROBLEMA DE SATISFAÇÃO DE RESTRIÇÕES (CSP) 17

de teorema automático que suporta apenas aritmética linearde número inteiros e alguns casos

especiais de aritmética não linear. Para restrições dentrodeste escopo, o CVC3 é osolvermais

apropriado.

2.4.2 Algoritmos Incompletos

Algoritmos incompletos são baseados em solução aleatória.Esses algoritmos atribuem valores

aleatórios as variáveis do problema e verifica se eventualmente os valores satisfazem as res-

trições. Esses algoritmos não são capazes de afirmar que uma restrição é insatisfatível, sendo

apenas capazes de garantir que é satisfatível, quando a solução é encontrada. É classificado

como desconhecido quando não é capaz de encontrar uma solução. Vários algoritmos incom-

pletos foram propostos para CSP e, posteriormente, algoritmos de busca foram utilizados para

este propósito.

2.4.3 Algoritmos Evolutivos em CSP

A utilização de algoritmos evolutivos para resolver problemas de restrição já é bastante conhe-

cida na comunidade (Bäck et al.; 1998; Jong e Kosters; 1998; Lie Engelbrecht; 2007; Zhou

et al.; 2009; Eiben e van der Hauw; 1997). Nesse uso, cada solução do espaço de busca é

uma atribuição de valores para as variáveis do problema CSP. Os algoritmos evolutivos pos-

suem uma capacidade de percorrer os espaços de busca rapidamente e utilizam uma forma de

busca global, isto permite que sejam aplicados a este contexto com sucesso. A aquisição de

conhecimento do problema é realizada através de funções defitness, que avaliam a qualidade

da solução candidata e medem a distância da solução final.

Duas funções defitnesssão bastante usadas neste contexto de resolução de restrição, Max-

SAT(Folino et al.; 1998; Rossi et al.; 2000; Marchiori e Rossi; 1999) eStep-wise Adaptation

of Weights(SAW) (Bäck et al.; 1998; Eiben e van der Hauw; 1997). MaxSAT é uma função

simples que conta o número de cláusulas que são satisfeitas pela solução candidata. Apesar de

sua simplicidade, esta função é capaz de fornecer uma forma de avaliar a qualidade da solução,

pois a solução final deve satisfazer todas as cláusulas. Quanto mais próximo da solução final,

maior a quantidade de cláusulas satisfeitas. Porém, MaxSATnão é capaz de prover um direci-

onamento adequado ao algoritmo de busca. Este último deve ser capaz de tomar decisões onde

uma solução “ruim” pode se tornar uma solução “boa”, posteriormente.

2.5 CONSIDERAÇÕES FINAIS 18

Bäck et al. (1998) propuseram oStep-wise Adaptation of Weights(SAW) para reduzir o

impacto do problema encontrado pela função MaxSAT durante abusca por uma solução ótima.

SAW associa pesos a cada cláusula em uma restrição. Cada peso éatualizado a cada iteração

que a sua cláusula não é satisfeita. Através do uso de SAW, é possível identificar cláusulas que

são mais difíceis de serem resolvidas, com o passar das iterações. Osolversusa esta informação

para favorecer os indivíduos que estão resolvendo as cláusulas mais difíceis.

Problemas simples podem possuir vastos espaços de busca, com poucas soluções. Nem

sempre resolver uma cláusula significa estar no caminho correto. Este tipo de decisão é re-

alizada pela função SAW. Utilizando a função MaxSAT, o algoritmo poderia ficar preso em

uma das linhas azuis, que possuem um valor defitnessrelativamente alto. Em um algoritmo

completo, de força-bruta, para encontrar uma solução nesteespaço de busca, seria necessário

um grande esforço computacional, onde todos os estados seriam testados até que uma solução

fosse encontrada.

Algumas observações devem ser feitas sobre a resolução de CSPcom PSO. A representa-

ção do problema é realizada de acordo com o domínio do tipo dasvariáveis. Para restrições

com variáveis inteiras, apenas número inteiros serão utilizados na representação. Esta modifi-

cação permite que o PSO seja capaz de percorrer o espaço de busca de acordo com o tipo de

dados. PSO originalmente utiliza valores ponto-flutuante eesta característica dificulta a busca

por soluções em um domínio de valores inteiros. Esta soluçãofoi proposta por Kennedy e

Eberhart (1997), chamado de PSO discreto, ou binário. Permite aplicar PSO em outros con-

textos, além de otimização de funções matemáticas contínuas não-lineares. A adaptação do

algoritmo genético à resolução de CSP é realizada de forma simples, pois este não possui a

mesma dependência de números ponto-flutuante.

2.5 Considerações Finais

Os algoritmos de busca meta-heurística podem ser aplicadosem muitos contextos, incluindo

resolução de restrições. Estas pesquisas trouxeram muitassoluções práticas, com resultados

motivantes (Folino et al.; 1998; Silva e Sakallah; 1996; Takaki et al.; 2009;?; Zhou et al.;

2009), apesar de algoritmos incompletos não serem capazes de garantir que uma solução será

encontrada. Esta escolha, usar algoritmos incompletos devido a seu ganho de desempenho, é

2.5 CONSIDERAÇÕES FINAIS 19

aceitável quando existe uma limitação de tempo. Essa limitação de tempo é importante em pro-

blemas que necessitam obter um resultado em curtos espaços de tempo. O algoritmo utilizado

atualmente, CVC3, não é capaz de resolver restrições que estãofora do escopo de sua teoria

suportada, o que acontece freqüentemente.

Os algoritmos de busca são afetados com o aumento da dimensionalidade. Uma expressão

com vários literais acarreta em um vasto espaço de busca, devido à representação do problema

escolhida. O tamanho da população influencia diretamente nacapacidade de percorrer vas-

tos espaços de buscas, porém o tamanho da população está diretamente relacionado ao custo

computacional de cada iteração.

A função defitnessdeve ser bem escolhida para prover o devido direcionamento ao al-

goritmo para que este seja capaz de encontrar o máximo global. Atualmente, a função mais

apropriada para o CSP é a função SAW, proposta por Bäck et al. (1998). Esta é capaz de favo-

recer os indivíduos que são capazes de resolver as cláusulasmais difíceis. Isto é feito através

de pesos, associados a cada cláusula, que são incrementadosa cada iteração que as cláusulas

não são resolvidas.

CAPÍTULO 3

Teste de Software

Neste capítulo será apresentado o atual estado da arte do teste de software, enfocando em testes

de caixa branca, mais especificamente teste simbólico e concólico. As soluções conhecidas e

utilizadas são abordadas com suas principais lacunas. Serão apresentadas as diversas técnicas

de teste de software, além de métricas e critérios de adequação. A visão dospath condition

como problemas de resolução de restriçãoConstraint Satisfaction Problem(CSP) é apresentada

e como isto permitiu automatizar o teste simbólico.

3.1 Teste de Software

Com o aumento da importância dos softwares, testá-los se tornou uma tarefa essencial para

a garantia da sua qualidade. Devido a sua alta complexidade eseus grandes times de desen-

volvimento, o teste de software vem se tornando uma tarefa árdua. A comunidade de teste de

software vem buscando novos métodos que forneçam um alto nível de garantia de qualidade.

O teste não é capaz de garantir a ausência de erros, apenas é capaz de garantir a presença

de erros. Esta é a causa para que se invista em, cada vez melhores, novos métodos de teste de

software. Visando um aumento da qualidade do produto, os testes são executados exaustiva-

mente até que uma quantidade mínima de defeitos seja encontrada. Na figura 3.1 é possível

observar que a quantidade de defeitos encontrados é diretamente proporcional a probabilidade

de existirem novos defeitos.

Ao se utilizar um processo bem definido de desenvolvimento e testes, o controle de qua-

lidade de um produto pode ser automatizado e os erros minimizados. Porém, com o aumento

do esforço no controle de qualidade, o custo do produto é aumentado. A decisão da escolha

de um processo de testes deve ser feito de acordo com o tipo e necessidades do produto. Um

produto amador, que visa prover um serviço de baixa qualidade, não necessita de um processo

de testes detalhado e com várias fases. Isto acarretaria em um aumento no custo e no tempo de

20

3.2 TÉCNICAS DE TESTE 21

Figura 3.1: Quantidade de defeitos encontrados pela probabilidade de existência de novos de-

feitos (Myers e Sandler; 2004, cap. 2, fig. 2.2).

desenvolvimento, o que poderia fazer com que a empresa percaseu mercado.

3.2 Técnicas de Teste

Existem diversas técnicas de teste; cada uma tem um propósito específico. Para cada fase do

desenvolvimento de um software, existem técnicas e métodosque tratam das suas necessidades.

Estas podem ser separadas em dois grupos:

1. Teste de Caixa Preta

O código-fonte e as estruturas internas não são visíveis ao engenheiro de testes. Apenas

é levado em conta o comportamento do software como um todo; o software é visto como

uma caixa preta que apenas vemos suas entradas e saídas, mas não podemos ver as ope-

rações e estruturas internas. É utilizado na verificação de especificação, suas entradas e

saídas são comparadas à sua especificação. O conjunto de dados utilizados como entrada

neste tipo de teste é criado a partir de documentos de especificação. Também é conhecido

como teste funcional ou teste baseado em especificação.

3.2 TÉCNICAS DE TESTE 22

2. Teste de Caixa Branca

As operações e estruturas internas são visíveis e são o principal foco deste tipo de teste.

O conjunto de dados de entrada é criado visando testar estruturas específicas do soft-

ware. Uma das métricas utilizadas é a medição da cobertura doteste. A cobertura mede

o quanto do código está sendo coberto por um teste. Esta cobertura pode ser medida

utilizandostatements, blocos,branches, caminhos, métodos ou classes, em um desenvol-

vimento orientado a objeto.

O termostatementse refere à menor e indivisível instrução utilizada em código fonte (Stan-

dard glossary of terms used in Software Testing; 2007). Poderia ser chamado delinha, porém,

em algumas linguagens de programação, um comando pode ocupar mais de uma linha.State-

mentprovê o significado necessário neste contexto de teste de software.

O teste de caixa branca, a principio, parece ser a melhor opção para realizar testes que

garantam a ausência de erros. Porém, para testes de caminhos, um teste minucioso pode ser

tornar impraticável. Em um simples programa, a quantidade de caminhos possíveis pode ser

extremamente grande. O teste exaustivo não é possível em grandes sistemas (Pressman; 2001).

Testes de caixa branca não são impossíveis de serem criados,os principais caminhos podem

ser escolhidos e exercitados através de técnicas de geraçãode dados de entrada, que forçam o

fluxo de controle a percorrer o caminho a ser exercitado. Alémda forma tradicional, este pode

ser combinado ao teste de caixa preta para prover uma abordagem que verifica a interface e o

funcionamento interno.

Pressman (2001) questiona por que utilizar testes de caixa branca, quando poderíamos ape-

nas verificar se os requisitos estão sendo cumpridos. Entretanto, os testes de caixa preta, por

mais minuciosos que sejam, não são capazes de realizar verificações que evitam os seguintes

tipos de defeitos:

• Os caminhos com as menores probabilidades de serem executados, possuem as maiores

chances de conter um erro. Processos mais comuns tendem a serem bem entendidos, por

isso possuem menor probabilidade de conterem um erro.

• Algumas conclusões sobre o fluxo do programa levam a cometererros e estes só podem

ser descobertos através de testes de caminho.

• Erros de digitação podem ser detectados pelo compilador, mas alguns destes erros só

podem ser encontrados através de testes.

3.3 FASES DE TESTE 23

3.3 Fases de Teste

O desenvolvimento de um software segue uma seqüencia de fases, onde cada uma tem um

objetivo e uma abordagem específica. Segundo Pressman (2001), o processo de testes é visto

como um espiral como pode ser visto na figura 3.2. Na figura 3.3 podem ser observadas as

fases e seus requisitos.

Figura 3.2: Processo de testes, com suas fases, utilizando uma representação de espiral (Press-

man; 2001, cap. 18, fig. 18.1).

1. Teste de Unidade

Foca na menor unidade do desenvolvimento de software – um componente ou módulo.

Os limites do teste são determinados pelo módulo a ser testado, o teste não deve ultra-

passar este limite. Utiliza a abordagem de caixa branca. Para cada teste, é desenvolvido

um driver e umstub, como pode ser visto na figura 3.4. Odriver é basicamente um

programa que aceita dados de entrada e repassa para o componente a ser testado. Ostub

é um subprograma que substitui os componentes necessários para executar o teste e que

não estão sendo testados. Este é constituído de uma interface simplificada, construída

apenas para permitir a execução do componente, suprindo suas dependências de outros

módulos.

2. Teste de Integração

Na fase anterior, os módulos são testados individualmente,porém, ao serem integrados,

problemas podem ocorrer na interface que os conecta. Módulos, ao serem integrados,

3.3 FASES DE TESTE 24

Figura 3.3: Fases do processo de teste e seus requisitos (Myers e Sandler; 2004, cap. 6, fig.

6.3).

3.4 TESTES DE CAIXA PRETA 25

podem gerar resultados inválidos e não produzir o comportamento esperado. O objetivo

é obter os módulos testados, providos da fase anterior, e criar uma estrutura de acordo

com a especificação.

3. Teste de Validação

Após a correção dos erros de integração, o software passa a ser validado de acordo com

as especificações do software. É realizado utilizando a abordagem de caixa preta para

garantir a conformidade com os requisitos.

4. Teste de Sistema

O software, ao final do desenvolvimento, deve ser testado no ambiente do cliente. Estes

testes estão fora do escopo do processo de testes, pois não são realizados apenas por

engenheiros de software.

Figura 3.4: Teste de unidade com seus principais componentes: caso de teste,driver e stub.

(Pressman; 2001, cap. 18, fig. 18.5).

3.4 Testes de Caixa Preta

Os testes de caixa preta, ou funcionais, visam garantir a conformidade do software com seus

requisitos. Os casos de teste são criados de acordo com as especificações, sem se preocupar

com as estruturas ou design internos. Nem sempre podem ser automatizados, pois podem exigir

3.4 TESTES DE CAIXA PRETA 26

intervenção humana. A base da criação de testes funcionais éparticionar os possíveis compor-

tamentos do programa em um número finito de classes, onde espera-se que cada classe estaja

funcionalmente correta. Um erro ocorre quando um programa não funciona como o esperado,

ou seja, um defeito não é apenas causado por erros de programação, a não conformidade com

requisitos também é caracterizada como um erro. Segundo Myers e Sandler (2004), existem os

seguintes tipos de teste que se enquadram nesta abordagem:

Particionamento de Equivalência. Um bom caso de teste é aquele que possui uma grande

chance de encontrar um defeito. Quando um software está sendo testado através de um teste

de caixa preta, este é visto como um módulo que possui entradas e defeito, conforme visto na

seção 3.2. Um teste exaustivo com todas as possíveis entradas é impossível de ser realizado.

Então o subconjunto de entradas que possua a maior probabilidade de encontrar defeitos deve

ser encontrado. Duas propriedades devem ser consideradas neste caso: cada caso de teste deve

conter o máximo possível de diferentes entradas para minimizar a quantidade de testes necessá-

rias e o domínio dos dados de entrada devem ser particionadosem um número finito declasses

de equivalência. Esta segunda propriedade garante que, se um caso de teste deuma determi-

nada classe de equivalência encontra um erro, outro caso de teste, da mesma classe, também

deve encontrar o mesmo erro. Estas classes são divididas em dois grupos: dados válidos e

inválidos. Em um módulo que possui como entrada apenas valores entre 1 e 999, existe uma

classe de equivalência válida: 1≤ n≤ 999 e existem duas classes de valores inválidos:n < 1 e

999< n.

Análise de Valores de Limite (boundary-value analysis). Exercita os limites do tipo de dados

de entrada. Difere do particionamento de equivalência em duas propriedades: 1. ao invés de

escolher valores qualquer dentro da classe de equivalênciacomo representante, um ou mais

valores devem ser selecionados que representam os extremosda classe. 2. ao invés de se preo-

cupar apenas com valores de entrada, os valores de saída também são verificados. É necessário

um bom conhecimento do problema para criar testes deboundary. Se o domínio dos valores

de entrada de um módulo é[−1.0,+1.0], devem ser criados testes que utilizam valores como

−1.0, 1.0,−1.001 e 1.001.

Grafo de Causa e Efeito. Explora uma das deficiências da análise de valores de limite eo

particionamento de equivalência, que é a combinação de valores de entrada. Uma situação

de erro pode ocorrer após uma seqüencia de valores de entrada. Esta situação poderia não

3.4 TESTES DE CAIXA PRETA 27

ser detectada pelas outras técnicas. As possíveis combinações podem tender a infinito e ao se

escolher um subconjunto de condições, que podem acarretar em um teste ineficaz. Utiliza uma

uma notação similar a lógica Booleana de circuitos digitais para representar o grafo. Este grafo

é utilizado para a escolha da seqüencia de valores de entrada. Um exemplo deste grafo pode

ser observado na figura 3.5.

Métodos de Estimativa de Erro (Error-guessing methods). É um processoad hoce intuitivo

de escrita de casos de teste, onde a experiência previa do engenheiro de testes é utilizada. A

idéia básica é identificar e listar os possíveis erros, ou possíveis situações de erro, e escrever

casos de teste baseado nesta lista.

Figura 3.5: Exemplo de um grafo de causa e efeito (Myers e Sandler; 2004, cap. 4, fig. 4.14).

3.5 TESTES DE CAIXA BRANCA 28

3.5 Testes de Caixa Branca

Os testes de caixa branca, ou estruturais, verificam o funcionamento interno de um software.

Estes não são capazes de garantir a ausência de defeitos, pois um defeito pode não se manifestar

mesmo executando a região de código que contenha o defeito. Para que este se manifeste, pode

ser necessário que o software esteja em um estado específico eapenas executar, sem criar este

estado, não fará com que o defeito se manifeste.

Existem diversas técnicas que seguem a abordagem de caixa branca. As técnicas de teste

são complementares, ou seja, não existe uma técnica que consiga encontrar todos os defeitos.

Estas devem ser utilizadas em conjunto ou em momentos diferentes, pois uma técnica não

substitui a outra. Segue, abaixo, uma lista das principais técnicas de testes de caixa branca,

segundo Young e Pezze (2005).

• Teste deStatement

É a forma mais básica e intuitiva de testar o fluxo de controle de um software. Cada

statementdeve ser executado pelo menos uma vez, seguindo a idéia de queum defeito

é revelado quando a região de código, que contém o defeito, é executada. Como visto

anteriormente, não é capaz de revelar todos os defeitos sem criar o estado específico em

que manifesta o defeito.

• Teste deBranch

Teste destatement, mesmo com uma cobertura total, pode não cobrir todos osbranches.

Cadabranchdeve ser executado pelo menos uma vez. Os testes cobrem, pelomenos, uma

ramificação do grafo de fluxo de controle do software. Em situações que uma ramificação

nunca é executada – por realmente ser inalcançável – o teste não satisfaz o critério de

adequação deste teste.

• Teste de Condição

Exercita as condições lógicas contidas em um módulo de um software. Teste debranch

enxerga apenas as ramificações, enquanto que teste de condição enxerga as estruturas

lógicas que compõem as condições dosbranches. Por essa característica, alguns defeitos

podem escapar, pois o teste debranchpoderá irá exercitar apenas as ramificações, sem

levar em conta que a condição pode conter um defeito. Na figura3.7, existem dois

3.6 CRITÉRIOS DE ADEQUAÇÃO E MÉTRICAS 29

caminhos possíveis –if eelse. Entretanto, se a condição contiver um erro como(x == 1

||y ==−1), o teste debranchnão irá identificar este erro.

• Teste de Caminho

Visa cobrir os possíveis caminhos de um software. É realizado criando-se entradas que

resultem em um determinado caminho. Alguns defeitos podem se manifestar após uma

seqüencia de decisões, ou seja, um caminho específico do software. Programas que con-

tenhamloopspodem gerar um número infinito de caminhos, o que torna este critério

difícil de ser totalmente coberto. É importante observar que um aumento na cobertura de

caminhos, não necessariamente acarreta em um aumento na cobertura destatements.

– Teste de Loop

Variação do teste de caminho, onde o principal objetivo é testar osloops. Para que

isto seja realizado, é estabelecido um critério de parada para que exista um número

finito de possíveis caminhos. O teste de caminho não é capaz deverificar todos os

caminhos em situações descritas na figura 3.6, pois poderá gerar infinitos possíveis

caminhos.

• Teste de Chamada de Procedimento/Método

Visa cobrir o fluxo de controle entre procedimentos ou métodos, útil em testes de inte-

gração ou testes de sistemas. Se o teste unitário foi bem sucedido, os defeitos que restam

serão de interface. Esta é a principal razão para se utilizaresta técnica na fase de inte-

gração. Nesta fase de teste, o principal foco deve ser a interface entre módulos, tornando

fundamental o uso de testes de chamada de procedimento.

3.6 Critérios de Adequação e Métricas

Critérios de adequação é um conjunto de obrigações que o par [Programa, Suite de Testes]

deve satisfazer. Uma suite de testes é dita que satisfaz o critério de adequação quando todas as

obrigações do critério são satisfeitas por, pelo menos, um caso de teste, segundo Young e Pezze

(2005).

3.6 CRITÉRIOS DE ADEQUAÇÃO E MÉTRICAS 30

1 pub l i c c l a s s ClassUnderTes t {

2 pub l i c vo id foo ( i n t x , i n t y ) {

3 i f ( x == −1 | | y == −1) {

4 . . .

5 } e l s e {

6 . . .

7 }

8 }

9 }

Figura 3.6: Exemplo de código fonte com umbranch.

1 pub l i c c l a s s PathWithLoop {

2 pub l i c vo id foo ( i n t x ) {

3 boolean s t o p = t rue ;

4

5 whi le ( s t o p ) {

6 . . .

7 }

8 }

9 }

Figura 3.7: Exemplo de código fonte com umloop, situação em que o teste de caminho pode

se tornar impraticável.

Algumas métricas são extraídas das suites de testes para prover uma medida quantitativa

da qualidade das suites de testes. Existem diversas medidase critérios de adequação. Cada

técnica de teste possui seu critério específico, como no teste destatement, cadastatementdeve

ser executado pelo menos uma vez. Caso esta exigência não sejacumprida, a suite de testes

falha neste critério. Estas informações também são utilizadas para medir o progresso do de-

senvolvimento dos testes, porém estas métricas podem ocultar e desviar do objetivo principal:

garantir a qualidade do software.

Métricas são utilizadas para analisar um software. Acomplexidade ciclomáticaé uma mé-

trica de software que fornece uma medida quantitativa da complexidade lógica de um sistema.

No contexto de teste de caminho, esta métrica define o número de caminhos independentes

3.7 CRIAÇÃO DE CASOS DE TESTE 31

e provê um limite máximo de testes necessários para garantirque todos osstatementssejam

executados, pelo menos uma vez (Pressman; 2001). Para extração de métricas, são utilizados

métodos estáticos, que analisam estaticamente osoftware, e métodos dinâmicos, que obtém as

métricas a partir da execução. Técnicas como a proposta por Buse e Weimer (2009), utilizam

um método estático para predizer osbranchesexistentes em um sistema.

Os critérios de adequação também fornecem informações úteis no desenvolvimento de um

software. Se o critério destatementnão é capaz de ser cumprido, isto significa que algum

trecho de código não é atingível, o que pode ser causado por algum erro de programação. Por

outro lado, alguns critérios não pode ser totalmente cumpridos. Critérios baseados em especi-

ficação pode exigir combinações de diferentes módulos, porém nem todas as combinações são

possíveis (Young e Pezze; 2005).

Dentre os diversos critérios, a principal questão é decidirqual destes critérios melhor se

enquadra na situação do desenvolvimento de um software. A definição de um critério como

mais “forte” ou mais “fraco” é extremamente subjetiva e específica para cada projeto. Alguns

critérios podem sobrepor outros, como no caso de um critérioestrutural que exige a cobertura

debranchessobrepõe a cobertura destatements.

3.7 Criação de Casos de Teste

O grau de esforço e complexidade na criação de casos de teste pode ser comparado ao esforço

relativo ao desenvolvimento de umsoftware. Estes testes devem ser desenvolvidos para encon-

trar a maior quantidade de erros possíveis em um mínimo tempoe esforço (Pressman; 2001).

Os testes de caixa preta são utilizados para testar a interface do software. Estes são utilizados

para garantir que o objeto a ser testado (pode ser um módulo, uma classe ou até o sistema

inteiro) está seguindo as especificações e que seu funcionamento básico está operacional. A

especificação funcional é a principal fonte de informação para a criação de casos de teste. Já

o teste de caixa branca, visa garantir o funcionamento das estruturas internas do produto e se

baseia nas estruturas internas e no desenvolvimento do software para criar seus testes.

Nestas abordagens, a geração de dados para a criação de testes produzem resultados dife-

rentes. Devido a diferença de propósitos, estes dados devemser gerados de formas diferentes.

Conforme visto na seção 3.4, testes de caixa preta podem utilizar dados de entrada para verifi-

3.8 TESTE SIMBÓLICO 32

cação de limites (boundaries), porém verificando apenas conformidade com os requisitos.No

teste de caixa branca, estes dados são gerados visando exercitar as estruturas de dados internas,

pois estas não estão visíveis no teste funcional. Existem diversas técnicas de geração de casos

de teste, como a execução concólica, vista adiante.

A automação de testes se tornou necessária devido a necessidade de identificar a presença

de defeitos sem intervenção humana. A verificação de softwares é uma árdua tarefa que exige

um grande esforço. Quanto mais tarde um defeito é encontrado, mais custoso se torna sua

correção. Na figura 3.8, o gráfico mostra o custo relativo de correção de um defeito de acordo

com a fase em que é encontrado. Como é possível observar, se um defeito é encontrado na

fase de levantamento de requisitos, o custo é de ordem 1. Porém se encontrado na fase final,

esta correção tem um custo de quase mil vezes maior, se comparado a fase inicial. Por causa

disto, inúmeros métodos foram criados para encontrar os defeitos o mais cedo possível, mais

próximo do instante em que o desenvolvedor introduz o erro. Uma das técnicas propostas para

geração automática de testes é a execução simbólica, utilizada em testes de caixa branca e de

caminho. Pode ser utilizado em testes unitários e de integração.

Existem diversas técnicas de geração automática de casos detestes ou de dados de entrada,

para serem utilizados por um teste já existente. Algumas técnicas utilizam um método aleató-

rio de geração de dados, os quais são modificados sem seguir nenhum critério sobre o tipo das

estruturas utilizadas nosoftware, como a técnica defuzzingcriada por Miller et al. (1990). A

técnica defuzzingse enquadra no tipo de teste de caixa-preta, pois não leva em consideração

nenhuma das estruturas internas e é utilizada unicamente com o intuito de verificar a confor-

midade das funcionalidades. Existe um aprimoramento destatécnica, chamado dewhite box

fuzzing. Ganesh et al. (2009) apresenta uma ferramenta que utiliza este método, chamada de

Buzz Fuzz, que analisa a estrutura do código dosoftwarena geração dos dados.

3.8 Teste Simbólico

Teste simbólico é uma técnica proposta por King (1976) para prover uma melhoria na auto-

mação de testes. Esta técnica é capaz de extrair as tomadas dedecisões internas, chamadas de

Path Condition(PC). Esta extração é feita usando os valores simbólicos ao invés dos valores

concretos. Com esta mudança, o programa é executado usando todo domínio do tipo da variá-

3.8 TESTE SIMBÓLICO 33

Figura 3.8: Gráfico de custo relativo de correção de um defeito de acordo com a fase em que é

encontrado (Pressman; 2001, cap. 8, fig. 8.1).

vel. O teste simbólico fornece uma forma prática de verificara corretude do software. A figura

3.9 mostra um exemplo de um conjunto de decisões internas de um exemplo de código. A va-

lidação de um programa utilizando uma análise formal é capazde prover melhores resultados,

mas sem resultados práticos devido sua alta complexidade.

3.8.1 Problema de Resolução de Restrições no Contexto de Teste Simbólico

A técnica proposta por King (1976) não fornecia um processo automático de resolver as res-

trições encontradas e, assim, fornecer dados de entrada. Clarke (1976) combinou a execução

simbólica com umsolverde restrições automático. Se o conjunto de restrições for linear, téc-

nicas de programação linear são utilizadas para obter uma solução. Apesar desta melhoria, a

intervenção humana ainda era necessária para resolver as restrições que não fossem lineares,

utilizando o método do gradiente conjugado.

Cadapath conditionpode ser visto como um problema de resolução de restrição e ossolvers

3.9 EXECUÇÃO CONCÓLICA 34

Figura 3.9: Um exemplo de um conjunto de decisões internas (Path Condition).

podem ser utilizados para gerar dados de entrada que satisfazem a restrição. Estes dados de

entrada são usados pelo software que está sendo testado e cada restrição satisfeita é um caminho

da árvore de fluxo de controle. Mas a capacidade dossolvers, usados para gerar estes dados de

entrada, limita que a técnica seja eficaz.

3.9 Execução Concólica

Ao método de execução simbólica faltava um valor concreto, oqual é necessário em casos de

indexação de vetores e conversão de tipos. Uma nova técnica foi proposta para preencher as

lacunas do teste simbólico. O software é executado usando dados concretos, mas os valores

simbólicos são armazenados em cada tomada de decisão durante a execução. Esta técnica é

chamada de execução concólica (Godefroid et al.; 2005), visto que combina execução concreta

e simbólica. A figura 3.10 representa umpath conditionextraído de uma execução concólica,

usando o mesmo código da figura 3.9, porém com dados concretos. Na figura, é possível

observar que a partir daquelas entradas, apenas um caminho éconhecido. Existem outros

caminhos a serem percorridos, porém estão ocultos ao algoritmo de execução.

É importante ter em mente que na execução concólica, é levadoem conta o critério de

3.10 TESTE RANDÔMICO 35

Figura 3.10: Um exemplo de umpath conditionextraído usando execução concólica.

adequação de caminhos. Apesar desta técnica ser capaz de satisfazer o critério destatements,

este não é seu objetivo. Encontrar soluções para novos caminhos nem sempre acarreta em um

aumento na cobertura de código. Porém, conforme visto na seção 3.5, esta técnica é capaz

de encontrar defeitos não descobertos pela técnica de cobertura destatements, pois apenas

executar uma região de código nem sempre é suficiente para queum erro se manifeste.

3.10 Teste Randômico

Teste randômico é uma técnica de geração de dados de entrada para a criação de casos de

teste para cobertura de código. As principais ferramentas são DART (Godefroid et al.; 2005) e

Randoop (Pacheco e Ernst; 2007).

DART provê uma execução simbólica com umsolverde restrições aleatório. A ferramenta

armazena o caminho que um determinado dado de entrada produziu, e seus valores simbólicos.

Sempre que uma expressão sai do escopo da teoria suportada pelo solver, um valor aleatório

3.11 CONSIDERAÇÕES FINAIS 36

é gerado até que um limite de tempo seja excedido ou uma solução seja encontrada. Quando

uma solução é encontrada, uma nova execução é realizada com estes novos dados e, assim,

novos PCS são gerados. Este método propõe duas soluções: (1) utiliza dados concretos quando

é necessário; (2) geração de dados aleatórios quando a expressão está fora do escopo suportado

pelosolver. DART é reduzido a um simplessolverrandômico quando a expressão está fora do

escopo da teoria suportada.

3.11 Considerações Finais

Com o crescimento da complexidade dos softwares desenvolvidos, o processo de testes se

tornou uma árdua tarefa. O processo de testes deve ser realizado de forma incremental, o qual

se assemelha a um espiral (Pressman; 2001). Cada fase possui seus objetivos e suas técnicas de

testes. Estas técnicas podem ser separadas em dois grupos:teste de caixa pretaeteste de caixa

branca. Os testes de caixa branca, mais especificamente ostestes de caminhopossuem uma

necessidade de um método de geração de dados de entrada para cobrir os possíveis caminhos

de um software. Os testes de caminho possuem um importante problema, osloopspodem gerar

uma grande quantidade de possíveis caminhos.

As técnicas de teste, seus critérios de adequação e métricaspermitem obter informações

sobre a qualidade dos testes criados e sobre o próprio software sob teste. Métricas, como

a complexidade ciclomática, auxiliam também no desenvolvimento e planejamento de testes,

pois esta permite obter uma estimativa da quantidade de testes necessários para prover uma

adequação destatements.

O teste simbólico possibilita a geração de dados para testesde caminhos, porém não é

capaz de resolver o problema deloops, além de outros problemas, como indexação de vetores

com valores simbólicos. A execução concólica resolve este problema combinando execução

simbólica, guardando as restrições criadas, e execução concreta, utilizando o valor concreto

para realizar ações de indexação e decisões deloops. Para a resolução das restrições de forma

automática, são utilizados provadores de teoremas que não são capazes de resolver restrições

que estão fora do escopo da teoria suportada pelo mesmo. Paraisto, DART (Godefroid et al.;

2005) e Randoop (Pacheco e Ernst; 2007) utilizam geração aleatória de valores. Apesar de sua

simplicidade, este método é capaz de resolver boa parte das restrições. A execução concólica

3.11 CONSIDERAÇÕES FINAIS 37

vem sendo aplicada no teste de diversos softwares, inclusive em linguagem de scripts como

PHP (Wassermann et al.; 2008).

Ossolversque são utilizados atualmente são restritos à teoria suportada. Esta limitação é

atualmente contornada utilizando-se uma randomização dasrestrições que estão fora do escopo

da teoria suportada pelosolver. Apesar de esta solução ser eficiente, esta randomização neces-

sita de pequenos intervalos para guiar o algoritmo, caso contrário, a probabilidade de encontrar

uma solução diminui à medida que o intervalo aumenta.

Soluções híbridas, ou até puramente aleatórias, têm apresentado resultados que poderiam

ser melhorados através de algoritmos baseados em heurística, os quais seriam capazes de intro-

duzir um melhor direcionamento, ao invés de percorrer aleatoriamente o espaço de busca.

Uma outra solução adotada para complementar a efetividade dossolvershíbridos é a rando-

mização das variáveis que compõem cláusulas que contém operações que estão fora da teoria

suportada pelosolver.

CAPÍTULO 4

Metodologia

Este capítulo apresenta a metodologia utilizada no desenvolvimento deste trabalho, onde será

detalhado oframeworkutilizado, com seus principais componentes, e a representação do pro-

blema utilizada pelos algoritmos de busca meta-heurística.

4.1 Framework

Foi definido umframeworkpara a realização das experimentações utilizando a arquitetura de-

finida na figura 4.1. A utilização doframeworksegue o seguinte fluxo: (1) umsoftwarea ser

testado é passado para o instrumentador, que introduz a bibilioteca simbólica; após a instru-

mentação, dá-se início à execução concólica (2) que é iniciada com um valor pré-definido e

nesta primeira execução são gerados PCs, que são armazenadose passados para ossolvers(3)

que tentam resolver as restrições; as soluções encontradasservem de entrada para odriver (4)

que reinicia a execução concólica com estes novos dados de entradas. Ao final deste ciclo, são

produzidos um conjunto de PCs e um conjunto de dados de entradaque permitem percorrer o

caminho determinado por um PC.

Os principais componentes destaframeworksão:

• Biblioteca Simbólica

Tipos simbólicos, que representam os tipos primitivos, sãoutilizados para guardar os

valores simbólicos gerados durante a execução, além de conter valores concretos, para

permitir a execução concreta.

• Instrumentador

Ferramenta desenvolvida para introduzir a biblioteca simbólica em umsoftware. Permite

reduzir drástricamente o tempo de preparação de umsoftware, realizando a instrumenta-

ção de forma automática.

38

4.1 FRAMEWORK 39

Figura 4.1: Arquitetura utilizada para acoplar ossolversaoframeworkde execução concólica.

• Execução Concólica

Frameworkcriado para realizar a execução concólica, onde os os PCs são armazenados

a medida que osoftwareé executado.

• Driver

Test driverque inicia a execução do programa. Recebe um conjunto de dadosde entradas,

os quais são passados para osoftwarea ser testado. Cada execução gera um conjunto de

PCs, que representam os caminhos que não foram executados. Alguns destes PCs podem

não ser satisfeitos, o que caracteriza em um trecho de códigoinatingível.

• Solver

Conjunto desolversque são utilizados para resolver as restrições e gerar dadosde entrada

para odriver executar o programa e percorrer o caminho relativo a este PC.

4.1 FRAMEWORK 40

Figura 4.2: Exemplo de uma árvore semântica.

4.1.1 Biblioteca Simbólica e Instrumentador

A biblioteca simbólica possui tipos simbólicos que representam os tipos primitivos da lingua-

gem Java. Para cada tipo primitivo, foi criado seu tipo simbólico correspondente. As classes

simbólicas armazenam um valor concreto e um valor simbólico, onde o valor simbólico apenas

é associado ao se criar uma expressão, comox> y. Foi utilizada uma árvore semântica que gera

a expressão, onde as variáveis e as constantes estão sempre nas folhas da árvore. Na figura 4.2

é possível observar um exemplo de árvore semântica. Os quadrados representam expressões

(como soma, comparação) e as folhas são as variáveis (branco) ou constantes (cinza).

O instrumentador foi desenvolvido utilizando as bibliotecas de manipulação debyte code

Java, ASM (ASM webpage; s.d.) e BCEL (Byte Code Engineering Library) (BCEL webpage;

s.d.). O uso destas bibliotecas permite a manipulação desoftwaresJava, sem a necessidade de

haver um código fonte. O instrumentador é utilizado para introduzir a biblioteca simbólica no

programa a ser testado, ou seja, substituir todos os tipos primitivos por tipos simbólicos. A

transformação exibida nas figuras 4.3 e 4.3b é realizada de forma automática, sem modificar a

semântica do programa. Esta transformação é também chamadade instrumentação.

Um exemplo de umsoftwareantes de ser instrumentado pode ser observado na figura 4.3a,

onde o código fonte do nó de uma árvore binária de busca é apresentado. Na figura 4.3b é

4.1 FRAMEWORK 41

apresentado o mesmo código após a instrumentação. Como pode-se observar, o atributoinfo

é do tipoint e, após a instrumentação, este torna-se em um tipo simbólico, SymInt. O tipo

SymInt é uma representação simbólico do tipoint, onde este armazena o valor concreto

inteiro e o seu valor simbólico.

4.1.2 Driver

O driver é utilizado para dar início à execução dosoftware. Deve ser criado umdriver espe-

cífico para cada programa a ser testado. Odriver utilizado nesteframeworkpossui o mesmo

papel de umtest driverdescrito pela literatura de testes (Pressman; 2001, cap. 18).

Na figura 4.4, é possível observar o código fonte de umdriver para o programa BST. São

realizadas chamadas aos métodos do programa que serão testados. Os métodos que não são

chamados, direta ou indiretamente, não serão testados pelaexecução concólica, pois o trecho

de código