Teste de Software
15: Geração randômica de teste
Marcelo d’Amorim
[email protected]
Problema
• Espaço de estados da aplicação é enorme
– Muitas operações
– Muitos dados
• Que sequência de operações escolher?
• Que dado construir?
Teste Randômico
• Constrói sequência e dados tomando
decisões randômicas
Teste Randômico
• Mostrou sucesso em vários casos
– Ideal: explorar espaço de estados de forma
uniforme (dependendo do gerador aleatório)
Caminhos de um programa
Exemplo: ling. funcional
• Como gerar dados para a função ML split?
local
fun split_iter (x::xs, left, right) = split_iter(xs, right, x::left)
| split_iter ([ ], left, right) = (left, right)
in
fun split(x) = split_iter(x,[ ],[ ])
end;
Exemplo: ling. funcional
• Como gerar dados para a função ML split?
local
fun split_iter (x::xs, left, right) = split_iter(xs, right, x::left)
| split_iter ([ ], left, right) = (left, right)
in
fun split(x) = split_iter(x,[ ],[ ])
end;
• Assumindo tipo de split: int list => (int list, int list)
– primeiro gera-se inteiros e lista vazia, depois listas
mais complexas
Generalização
• Gera-se dados recursivamente, baseado
na definição de tipo
– Passo 1: Gerar átomos
– Passo 2: Gerar objetos estruturados
Outro exemplo: Tipos estruturados
datatype inttree = empty | node of int * inttree * inttree;
Passo 1: Gerar átomos
int
inttree
-5, -2, 0, 2, 5
e
e = empty
Usa-se construtores elementares:
datatype inttree = empty | node of int * inttree * inttree;
Passo 1: Gerar objetos estruturados
int
inttree
Iteração 1
-5, -2, 0, 2, 5
e, (-2,e,e), (5,e,e)
Usa-se construtores elementares:
datatype inttree = empty | node of int * inttree * inttree;
Passo 1: Gerar objetos estruturados
int
inttree
Iteração 2
cópias!
-5, -2, 0, 2, 5
e, (-2,e,e), (5,e,e), (0, (-2,e,e),e),
(0,e, (5,e,e)), (0, (-2,e,e), (5,e,e))
Usa-se construtores elementares:
datatype inttree = empty | node of int * inttree * inttree;
Limitação
• Não considera invariantes do programa
– Exemplos
• Programa com comportamento especial para listas
ordenadas de tamanho N
• Programa que aceita apenas árvores com o tamanho
da sub-árvore esquera 2x o da direita
Falta de invariantes na geração
• Duas soluções:
– Usar código para construir dados
• Código precisa construir valores relevantes
– E.g. como testar caso lista ordenada em um algoritmo de
ordenação
– Execução simbólica
• Sucesso depende de limitações de um SAT solver
Teste randômico de
programas OO
Randoop
• Contratos (Oracles) default
– Mas o usuário pode definir os seus
• É necessário definir região para geração!
– Teste de unidade
• Aplica redução de suíte
– Baseada em equals, null, e exceções
– Usuário pode definir seus critérios de filtro
• Não explora particularidade de oo
– E.g., polimorfismo
Terminologia
• Randoop gera sequências como estas
• Cada sequência gera mais de um valor
– s1.1 (b1), s2.1 (b2), s3.1 e s3.2 (a1 e b3)
Feedback-directed
random test generation.
Carlos Pacheco et al.,
ICSE 2007
randomSeqsAndVals:
Feedback-directed random test generation. Carlos Pacheco et al., ICSE 2007
extend:
Feedback-directed random test generation. Carlos Pacheco et al., ICSE 2007