Download E. Alba, F. Chicano, S. Janson, Testeo de Software con dos

1/23
Jornadas de Ingeniería del Software y Bases de Datos 2006
Testeo de Software con Dos
Técnicas Metaheurísticas
Introducción
Generador
Algoritmos de
Optimización
Experimentos
Conclusiones y
Trabajo Futuro
Enrique Alba y Francisco Chicano
Sitges, Barcelona, España, 3-6 de Octubre de 2006
Jornadas de Ingeniería del Software y Bases de Datos 2006
2/23
Introducción
• Tras la codificación, el software requiere una fase de prueba
• El objetivo es comprobar que el software cumple la especificación
• Las empresas software dedican aprox. el 50% de recursos a dicha fase
Introducción
1.0, 2.3
1.0, 2.3
Generador
Algoritmos de
Optimización
Experimentos
Conclusiones y
Trabajo Futuro
10.5
Ok!
• En este trabajo proponemos una herramienta automática basada en
Metaheurísticas para generar los casos de prueba
Mal!
2.7, 5.4
2.7, 5.4
15.0
Sitges, Barcelona, España, 3-6 de Octubre de 2006
3/23
Jornadas de Ingeniería del Software y Bases de Datos 2006
Criterio de Adecuación
• Objetivo del generador de casos de prueba: proponer casos que
encuentren el máximo número de errores en un software incorrecto
Introducción
Generador
Algoritmos de
Optimización
Experimentos
Conclusiones y
Trabajo Futuro
Sitges, Barcelona, España, 3-6 de Octubre de 2006
4/23
Jornadas de Ingeniería del Software y Bases de Datos 2006
Criterio de Adecuación
• Objetivo del generador
casos
de prueba: proponer casos que
DIFÍCILdeDE
COMPROBAR
encuentren el máximo número de errores en un software incorrecto
Introducción
Generador
Algoritmos de
Optimización
Experimentos
Conclusiones y
Trabajo Futuro
Sitges, Barcelona, España, 3-6 de Octubre de 2006
5/23
Jornadas de Ingeniería del Software y Bases de Datos 2006
Criterio de Adecuación
• Objetivo del generador
casos
de prueba: proponer casos que
DIFÍCILdeDE
COMPROBAR
encuentren el máximo número de errores en un software incorrecto
Introducción
• Ejemplos de criterios de adecuación
Generador
Algoritmos de
Optimización
Cobertura de
Instrucciones
Experimentos
Conclusiones y
Trabajo Futuro
Ejecutar todas las
instrucciones
Cobertura de Ramas
Tomar todas las ramas
del programa
Cobertura de
Condiciones
Hacer verdaderas y falsas
todas las condiciones atómicas
Más severo
Sitges, Barcelona, España, 3-6 de Octubre de 2006
6/23
Jornadas de Ingeniería del Software y Bases de Datos 2006
Paradigmas
• Tres paradigmas de generación de casos de prueba:
¾ Generación Aleatoria
1.2, 0.7
Inputs: a,b
Introducción
Generador
c = a+b
¾ Generación Simbólica
Algoritmos de
Optimización
Experimentos
Conclusiones y
Trabajo Futuro
α, β
1.0, -2.0
α+β < 0
3.5, 1.2
α+β ≥ 0
true
c<0
¾ Generación Dinámica
-1.0, -0.5
1.0, -0.5
Sitges, Barcelona, España, 3-6 de Octubre de 2006
false
7/23
Jornadas de Ingeniería del Software y Bases de Datos 2006
Paradigmas
• Tres paradigmas de generación de casos de prueba:
¾ Generación Aleatoria
1.2, 0.7
Inputs: a,b
Introducción
Generador
c = a+b
¾ Generación Simbólica
Algoritmos de
Optimización
Experimentos
Conclusiones y
Trabajo Futuro
α, β
1.0, -2.0
α+β < 0
3.5, 1.2
α+β ≥ 0
true
c<0
¾ Generación Dinámica
-1.0, -0.5
1.0, -0.5
Sitges, Barcelona, España, 3-6 de Octubre de 2006
false
Jornadas de Ingeniería del Software y Bases de Datos 2006
8/23
Descomposición del Objetivo
• El objetivo global se descompone en pequeños objetivos parciales
Introducción
c1 true
c1 false
Generador
c2 true
c2 false
Algoritmos de
Optimización
c3 true
c3 false
Problema de Minimización
Distancia
Experimentos
Conclusiones y
Trabajo Futuro
Cobertura de
Condiciones
Seis objetivos parciales
Caso de prueba actual
Objetivo parcial (c3 true)
Casos de Prueba
Sitges, Barcelona, España, 3-6 de Octubre de 2006
Jornadas de Ingeniería del Software y Bases de Datos 2006
9/23
Generador de Casos de Prueba
Generador de Casos de Prueba
Selecciona un
objetivo parcial
Introducción
Generador
Algoritmo de
Optimización
Algoritmos de
Optimización
Experimentos
Conclusiones y
Trabajo Futuro
sí
Datos de entrada
Distancia
Programa
Continuar?
no
Fin
Sitges, Barcelona, España, 3-6 de Octubre de 2006
10/23
Jornadas de Ingeniería del Software y Bases de Datos 2006
Algoritmos de Optimización
Metaheurísticas
Trayectoria
Población
Introducción
Generador
Algoritmos de
Optimización
Experimentos
Conclusiones y
Trabajo Futuro
Problema de Optimización
Sitges, Barcelona, España, 3-6 de Octubre de 2006
11/23
Jornadas de Ingeniería del Software y Bases de Datos 2006
Algoritmos de Optimización
Metaheurísticas
Metaheurísticas
basadas en Población
Introducción
Generador
Algoritmos de
Optimización
Trayectoria
Algoritmos
Evolutivos
Población
Optimización
basada en
Nubes de Partículas
Optimización basada en
Colonias de Hormigas
Búsqueda
Dispersa
Experimentos
Conclusiones y
Trabajo Futuro
Problema de Optimización
Sitges, Barcelona, España, 3-6 de Octubre de 2006
12/23
Jornadas de Ingeniería del Software y Bases de Datos 2006
Nubes de Partículas (PSO)
• Optimización basada en Nubes de Partículas
¾ Partícula
(0.2, -1.4, 3.5) → Vector Solución (posición)
Introducción
Generador
(1.0, 10.3, 7.2) → Velocidad
¾ Actualización
Inercia
Mejor personal
Algoritmos de
Optimización
Mejor en vecindario
Experimentos
¾ Perturbación (cuando no mejoran los resultados)
Conclusiones y
Trabajo Futuro
v
v’
Sitges, Barcelona, España, 3-6 de Octubre de 2006
13/23
Jornadas de Ingeniería del Software y Bases de Datos 2006
Nubes de Partículas (PSO)
Nube
Programa
n partículas
Introducción
Generador
Actualización
Algoritmos de
Optimización
(0.1, -5.2, 3.0, ...)
Experimentos
7.3
Conclusiones y
Trabajo Futuro
(si no hay mejora)
Perturbación
Nube modificada
Sitges, Barcelona, España, 3-6 de Octubre de 2006
14/23
Jornadas de Ingeniería del Software y Bases de Datos 2006
Estrategia Evolutiva (ES)
• Estrategia Evolutiva
¾ Individuo
(0.2, -1.4, 3.5) → Vector Solución
(1.0, 10.3, 7.2) → Desviaciones estándar
Introducción
Generador
Algoritmos de
Optimización
Experimentos
Conclusiones y
Trabajo Futuro
(1.7, 0.3, 2.1) → Ángulos
¾ Mutación Gaussiana
Solución Seleccionada
Nueva solución
Nueva población
¾ Reemplazo → (μ+λ) y (μ,λ)
Población previa
μ individuos
Nuevos individuos
Sitges, Barcelona, España, 3-6 de Octubre de 2006
15/23
Jornadas de Ingeniería del Software y Bases de Datos 2006
Estrategia Evolutiva (ES)
• Estrategia Evolutiva
¾ Individuo
(0.2, -1.4, 3.5) → Vector Solución
(1.0, 10.3, 7.2) → Desviaciones estándar
Introducción
Generador
Algoritmos de
Optimización
Experimentos
Conclusiones y
Trabajo Futuro
(1.7, 0.3, 2.1) → Ángulos
¾ Mutación Gaussiana
Solución Seleccionada
Nueva solución
Nueva población
¾ Reemplazo → (μ+λ) y (μ,λ)
Población previa
μ individuos
μ individuos
Nuevos individuos
Sitges, Barcelona, España, 3-6 de Octubre de 2006
16/23
Jornadas de Ingeniería del Software y Bases de Datos 2006
Estrategia Evolutiva (ES)
Población
Programa
μ individuos
Introducción
Generador
Algoritmos de
Optimización
Mutación Gaussiana
(0.1, -5.2, 3.0, ...)
Experimentos
Conclusiones y
Trabajo Futuro
λ individuos
(μ+λ) Reemplazo
7.3
Nueva población
Sitges, Barcelona, España, 3-6 de Octubre de 2006
Jornadas de Ingeniería del Software y Bases de Datos 2006
17/23
Medidas de Cobertura
• Cobertura:
c=
Introducción
while(1<2)
{
/* algo */
}
p = malloc(4);
if (!p)
{
error();
}
Pérdida de cobertura
dependiente del código
Pérdida de cobertura
dependiente del entorno
Algoritmos de
Optimización
Conclusiones y
Trabajo Futuro
número total de objetivos parciales
• Inconvenientes: pérdidas inevitables de cobertura
Generador
Experimentos
objetivos parciales cubiertos
• Cobertura corregida:
cc =
objetivos parciales cubiertos
número total de objetivos parciales alcanzables
Sitges, Barcelona, España, 3-6 de Octubre de 2006
18/23
Jornadas de Ingeniería del Software y Bases de Datos 2006
Experimentos: Programas
• Benchmark: 6 programas en C
Introducción
Generador
Algoritmos de
Optimización
Experimentos
Programa
Conds. LdC
Args.
Fuente
triangle
21
53
3 Michael et al., 2001
calday
11
72
3 C-Recipes
select
28
200
21 C-Recipes
bessel
21
245
2 C-Recipes
sa
netflow
30
55
332
112
23 C-Recipes
66 Wegener
Conclusiones y
Trabajo Futuro
Sitges, Barcelona, España, 3-6 de Octubre de 2006
Jornadas de Ingeniería del Software y Bases de Datos 2006
19/23
Experimentos: Parámetros
• Parámetros de los algoritmos
PSO
Introducción
Generador
Algoritmos de
Optimización
Experimentos
Conclusiones y
Trabajo Futuro
Parámetro
ES
Parámetro
Valor
Partículas
Valor
10
Población
25
w
0.729
Selección
Aleatoria
c1
1.494
Mutación
Gaussiana
c2
1.494
Hijos (λ)
5
Prob. de perturb.
Parada
0.5
Obj. o 1000 evals.
Reemplazo
Parada
(μ+λ)
Obj. o 1000 evals.
• Realizamos 30 ejecuciones independientes para conseguir confianza
estadística en los resultados
Sitges, Barcelona, España, 3-6 de Octubre de 2006
Jornadas de Ingeniería del Software y Bases de Datos 2006
20/23
Experimentos: Resultados (I)
Programas
Introducción
Generador
Algoritmos de
Optimización
Experimentos
Conclusiones y
Trabajo Futuro
PSO
ES
Cov.
Evals.
triangle
93.98
11295.77
99.84
2370.03
99.67
3209.47
calday
100.00
179.33
98.18
3166.47
90.91
75.03
select
88.89
380.13
83.33
13.27
83.33
83.20
bessel
97.56
116.90
97.56
350.63
97.56
533.03
100.00
165.67
99.94
2337.30
96.72
176.63
97.77
4681.70
98.17
307.77
96.42
917.90
sa
netflow
Cov.
GA
Evals.
Cov.
Evals.
• PSO y ES tienen una eficacia similar
• La cobertura obtenida por GA es igualada o superada por PSO o ES
en todos los casos
Sitges, Barcelona, España, 3-6 de Octubre de 2006
Jornadas de Ingeniería del Software y Bases de Datos 2006
21/23
Experimentos: Resultados (y II)
Programas
Introducción
Generador
Algoritmos de
Optimización
Experimentos
Conclusiones y
Trabajo Futuro
PSO
ES
Cov.
Evals.
triangle
93.98
11295.77
99.84
2370.03
99.67
3209.47
calday
100.00
179.33
98.18
3166.47
90.91
75.03
select
88.89
380.13
83.33
13.27
83.33
83.20
bessel
97.56
116.90
97.56
350.63
97.56
533.03
100.00
165.67
99.94
2337.30
96.72
176.63
97.77
4681.70
98.17
307.77
96.42
917.90
sa
netflow
Cov.
GA
Evals.
Cov.
Evals.
Wegener: 40703 evals.
• Pérdida de cobertura dependiente del entorno en select
• Se encuentran casos de prueba que para los que netflow no termina
Sitges, Barcelona, España, 3-6 de Octubre de 2006
22/23
Jornadas de Ingeniería del Software y Bases de Datos 2006
Conclusiones y Trabajo Futuro
Conclusiones
• Hemos aplicado PSO y ES al problema de testeo de software
Introducción
• Hemos usado un conjunto de seis programas con diversas
características para evaluar nuestra propuesta
Generador
• Las técnicas PSO y ES tienen una eficacia similar
Algoritmos de
Optimización
• Ambas técnicas superan a los algoritmos genéticos
Experimentos
Conclusiones y
Trabajo Futuro
Trabajo Futuro
• Hibridar las técnicas para mejorar el balance entre explotación y
exploración
• Extender la propuesta para programas con entradas no numéricas
• Paralelizar las técnicas siguiendo esquemas de población
distribuida
Sitges, Barcelona, España, 3-6 de Octubre de 2006
23/23
Jornadas de Ingeniería del Software y Bases de Datos 2006
FIN
Gracias por su Atención !!!
Introducción
Generador
Algoritmos de
Optimización
Experimentos
Conclusiones y
Trabajo Futuro
Sitges, Barcelona, España, 3-6 de Octubre de 2006