Università degli Studi di Salerno
Facoltà di Scienze Matematiche Fisiche e Naturali
Laurea Magistrale in Sistemi Informativi e Tecnologie del Software
Prioritizzazione di casi di test
basata su algoritmi genetici
Relatore:
Prof. Andrea De Lucia
Candidato:
Gianluca Carbone
Supervisione:
Dott. Annibale Panichella
Anno Accademico 2013/2014
0522500116
Sommario
•
•
•
•
Introduzione e Background
Approccio al problema di TC Prioritisation
Implementazione
Analisi Sperimentale
Prioritizzazione di casi di test
basata su GAs
2
Introduzione
Definizioni
• In base alla definizione dell’IEEE software glossary il testing di
regressione è “re-test selettivo di un sistema o componente per
verificare che modifiche non hanno causato effetti involontari e il
sistema o la componente è ancora conforme ai suoi requisiti
specificati”. (IEEE Std 1990)
• Minimizzazione, Selezione, e Ordinamento
 Le tecniche di Minimizzazione di test suite cercano di ridurre la grandezza
di una test suite attraverso l’eliminazione di test ridondanti dalla test suite in
relazione ai criteri di testing definiti
 Le tecniche di Selezione di test case hanno lo scopo di individuare test
case rilevanti al fine di testare recenti cambiamenti.
Prioritizzazione di casi di test
basata su GAs
3
Introduzione(2)
 Il problema di Test case Prioritisation ha lo scopo di ordinare i test case
di una test suite in modo tale che la rilevazione di fault sia massimizzata
senza eseguire l’intera test suite.
S1
S2
S3
T1
X
X
T2
X
X
T3
X
X
X
T4
X
X
X
S4
X
S5
S6
S7
S8
X
X
X
X
X
X
X
X
X
X
S9
X
COST
4
X
X
X
S10
X
5
3
3
Possibili ordinamenti:
 T1 - T2 - T3 - T4
 T2 - T3 - T4 - T1
 T4 - T3 - T2 - T1
…
Prioritizzazione di casi di test
basata su GAs
4
Background
Approcci al problema di TC Prioritisation
 Coverage-based prioritisation  copertura statement, branch, …
 History-based Approach  fault passati, file mappati con i test
case e poi divisi per livelli di priorità
 Requirement-based Approach  test case mappati ai requisiti del
software
 Model-based Approach  test case divisi per livelli di priorità in
base ad un modello predefinito
 Probabilistic Approach
 Distribution-based Approach  test case clusterizzati in base alla
loro similarità
…
Prioritizzazione di casi di test
basata su GAs
5
Background(2)
Contributo di questo lavoro
GAs (Genetic Algorithms) sono stati utilizzati efficacemente per
risolvere solo due problemi relativi al test di regressione:
 minimizzazione
 selezione
 ordinamento
Rappresentazione binaria
delle soluzioni
Rappresentazione binaria
Obiettivo  «Riempire questo gap», fornendo un approccio basato su
GAs per risolvere il problema di test case prioritisation.
Prioritizzazione di casi di test
basata su GAs
6
Algoritmi Genetici
Algoritmo Genetico Standard
Un algoritmo genetico è un algoritmo euristico ispirato al principio della selezione
naturale ed evoluzione biologica teorizzato nel 1859 da Charles Darwin.
(1) Generazione casuale della prima popolazione di soluzioni;
(2) Applicazione della funzione di fitness ;
(3) Selezione delle soluzioni in base alla fitness e della logica di selezione
(4) Procedimento di crossover e mutazione a partire dalle soluzioni scelte al punto 3.
(5) Nuova popolazione a partire dalle soluzioni identificate al punto 4.
(6) Ri-esecuzione della procedura a partire dal punto 2 .
Prioritizzazione di casi di test
basata su GAs
7
Approccio proposto alla soluzione del
problema di Test Case Prioritisation
Rappresentazione della soluzione
 Data una Test Suite (T1, T2, T3, T4, T5, T6)
• Selezione dei test case
T1
T2
T3
T4
T5
T6
1
0
0
1
1
1
• Ordinamento dei test case
1
2
3
4
5
6
T1
T4
T6
T5
T2
T3
Prioritizzazione di casi di test
basata su GAs
8
Approccio proposto alla soluzione del
problema di Test Case Prioritisation(2)
Criteri di test
1.
Criterio di copertura di statement: numero di statement coperti.
𝑗
𝐶𝑂𝑉 𝑗 =
𝑐𝑜𝑣 (𝑡𝑖 ) ,
𝑑𝑎 𝑚𝑎𝑠𝑠𝑖𝑚𝑖𝑧𝑧𝑎𝑟𝑒
𝑖=1
2. Criterio di costo cumulativo: numero di istruzioni elementari nel codice.
𝑗
𝐶𝑂𝑆𝑇 𝑗 =
𝑐𝑜𝑠𝑡 𝑡𝑖 ,
𝑑𝑎 𝑚𝑖𝑛𝑖𝑚𝑖𝑧𝑧𝑎𝑟𝑒
𝑖=1
Prioritizzazione di casi di test
basata su GAs
9
Approccio proposto alla soluzione del
problema di Test Case Prioritisation(3)
Problema Multi-Obiettivo (una possibile soluzione):
-
due funzioni di fitness da valutare.
un certo numero di soluzioni ottimali, che si andranno a trovare su
un fronte di Pareto.
Prioritizzazione di casi di test
basata su GAs
10
Approccio proposto alla soluzione del
problema di Test Case Prioritisation (4)
Funzione di Fitness (la nostra soluzione):
𝑗
𝑖=1 𝑐𝑜𝑣(𝑡𝑖 )
𝑗
𝑖=1 𝑐𝑜𝑠𝑡 ( 𝑡𝑖 )
 MAX 𝐶𝑂𝑉 𝑗 =
 MIN 𝐶𝑂𝑆𝑇 𝑗 =
𝑛
𝑐𝑜𝑠𝑡(𝑛)
𝑓 𝑥 𝑑𝑥 ≈
𝑐𝑜𝑠𝑡(1)
(𝑐𝑜𝑠𝑡 𝑗 + 1 − 𝑐𝑜𝑠𝑡 𝑗) ∗
𝑗=1
𝑐𝑜𝑣 𝑗 + 1 + 𝑐𝑜𝑣(𝑗)
2
C
C’
P
P’
Prioritizzazione di casi di test
basata su GAs
11
Approccio proposto alla soluzione del
problema di Test Case Prioritisation (5)
Selezione
Crossover
Data una popolazione P di soluzioni, seleziona le
migliori P /2 soluzioni in base alla funzione obiettivo
Mutazione
Prioritizzazione di casi di test
basata su GAs
12
Approccio proposto alla soluzione del
problema di Test Case Prioritisation (6)
Algoritmo Genetico
Prioritizzazione di casi di test
basata su GAs
13
Implementazione
Caratteristiche di sistema, Tools e Linguaggi
 Sistema 64 bit, 8GB RAM, Intel Core i7-2670QM CPU @
2.20GHz 2.20 GHz
 Java (IDE: Eclipse), MATLAB, R (test statistici)
• JMetal: Framework orientato agli oggetti basato su Java per la
risoluzione di problemi di ottimizzazione con tecniche metaeuristiche.
• MatlabControl: API Java che permette chiamate a MATLAB.
Prioritizzazione di casi di test
basata su GAs
14
Implementazione (2)
Parametri di Input e Output
 Input
1. Matrice binaria rappresentante la copertura degli Statements
2. Vettore di interi rappresentante il costo di ogni test case
 Output
1.
2.
3.
4.
FUN: file contenente il valore della funzione obiettivo raggiunto.
VAR: file contente il vettore ordinato della test suite.
Nome.fig: file Matlab; grafico rappresentante la curva che ottiene il più alto valore
di fitness
Algorithm.log: file contenente informazioni relative all’esecuzione dell’algoritmo.
Prioritizzazione di casi di test
basata su GAs
15
Analisi Sperimentale
Caso di Studio
 4 Programmi Open-Source GNU disponibili dal Software-artifact
Infrastructure Repository (SIR): Bash, Flex, Gzip e Vim
Program
LOC
# of Test Cases
# of Statement
Description
Bash
59,846
1200
14539
Shell language interpreter
Flex
10,459
567
3432
Fast lexical analyser
Gzip
5,680
215
1686
Data compression program
Vim
122,169
975
34049
Improved vi editor
Prioritizzazione di casi di test
basata su GAs
16
Analisi Sperimentale (2)
Algoritmo Greedy
Prioritizzazione di casi di test
basata su GAs
17
Analisi Sperimentale (3)
Research Questions
•
R𝑸𝟏 : In che misura l’algoritmo genetico produce soluzioni ottimali in termini di
costo e copertura rispetto all’algoritmo Greedy ?
•
R𝑸𝟐 : In che misura l’algoritmo genetico migliora l'ottimalità della soluzione
prodotta dall'algoritmo Greedy, se si include nella popolazione iniziale la
soluzione prodotta dall’algoritmo Greedy ?
•
R𝑸𝟑 : Quale è l’efficacia nell'individuare i fault dell’algoritmo genetico rispetto
all’algoritmo Greedy ?
•
R𝑸𝟒 : In che misura l'algoritmo genetico migliora l'efficacia dell'algoritmo
Greedy, se si include nella popolazione iniziale la soluzione prodotta
dall’algoritmo Greedy ?
Prioritizzazione di casi di test
basata su GAs
18
Analisi Sperimentale (4)
 R𝑸𝟏 : In che misura l’algoritmo genetico produce soluzioni ottimali in
termini di costo e copertura rispetto all’algoritmo Greedy ?
Algoritmo Greedy
Caso di studio
Funzione di Fitness
VIM
FLEX
6.341852054039E12
9.031854710916E24
2.29745278156E11
GZIP
3.061952099E9
BASH
Algoritmo Genetico – dati statistici della funzione di
fitness
Caso di
studio
Min
Max
GA > Greedy
VIM
6.341578700434E+24
6.342245195263E+24
25/30
BASH
8.999917407306E+24
9.035568125545E24
5/30
FLEX
2.29727E+22
2.29754E+22
8/30
GZIP
3.06195E+18
4.82635E+18
29/30
Prioritizzazione di casi di test
basata su GAs
Test Statistico di
Wilcoxon (0.05)
A favore di GA
A favore di
Greedy
A favore di
Greedy
A favore di GA
19
Analisi Sperimentale (5)
COV
GZIP
COST
COV
FLEX
COST
Prioritizzazione di casi di test
basata su GAs
20
Analisi Sperimentale(6)
• R𝑸𝟐 : In che misura l’algoritmo genetico migliora l'ottimalità della
soluzione prodotta dall'algoritmo Greedy, se si include nella
popolazione iniziale la soluzione prodotta dall’algoritmo Greedy ?
Algoritmo Greedy
Caso di studio
VIM
BASH
FLEX
GZIP
Funzione di Fitness
6.341852054039E12
9.031854710916E24
2.29745278156E11
3.061952099E9
Algoritmo Genetico – dati statistici della funzione di
fitness
Caso di studio
Min
Max
GA > Greedy
VIM
6.341854933457E12
6.34258E+24
30/30
Test Statistico di
Wilcoxon (0.05)
A favore di GA
BASH
9.03185E+36
9.03382E+36
30/30
A favore di GA
FLEX
2.29750432953E11
2.29753094106E11 30/30
A favore di GA
GZIP
4.80943E+17
4.85923E+17
30/30
A favore di GA
Prioritizzazione di casi di test
basata su GAs
21
Analisi Sperimentale (7)
Research Questions
•
R𝑸𝟏 : In che misura l’algoritmo genetico produce soluzioni ottimali in termini
di costo e copertura rispetto all’algoritmo Greedy ?
•
R𝑸𝟐 : In che misura l’algoritmo genetico migliora l'ottimalità della soluzione
prodotta dall'algoritmo Greedy, se si include nella popolazione iniziale la
soluzione prodotta dall’algoritmo Greedy ?
•
R𝑸𝟑 : Quale è l’efficacia nell'individuare i fault dell’algoritmo genetico
rispetto all’algoritmo Greedy ?
•
R𝑸𝟒 : In che misura l'algoritmo genetico migliora l'efficacia dell'algoritmo
Greedy, se si include nella popolazione iniziale la soluzione prodotta
dall’algoritmo Greedy ?
Prioritizzazione di casi di test
basata su GAs
22
Analisi Sperimentale (8)
Metriche di Valutazione
 APFD (Average Percentage Faults Detection)
APFD = 1 −
𝑇𝐹1 +𝑇𝐹2 +⋯+𝑇𝐹𝑚
𝑛𝑚
 Area Fault/Cost
Funzione obiettivo
+
1
2𝑛
Metrica di valutazione
Prioritizzazione di casi di test
basata su GAs
23
Analisi Sperimentale(9)
R𝑸𝟑 : Quale è l’efficacia nell'individuare i fault dell’algoritmo genetico rispetto
all’algoritmo Greedy ?
Area Fault/Cost
2.514420352E9
1.279374807E9
5.219295093E9
7591128.0
APFD
0.7594627
0.9734985
0.7552334
0.9210526
VIM
FLEX
BASH
GZIP
ALGORITMO GENETICO
APFD
VIM
FLEX
BASH
GZIP
AREA Fault/Cost
MIN
MAX
GA >
Greedy
Wilcoxon
(0.05)
MIN
MAX
GA >
Greedy
Wilcoxon
(0.05)
0.758578
4
0.973308
9
0.755049
3
0.911297
4
0.75943
50
0.97916
08
0.75523
34
0.96296
29
0/30
A favore di
Greedy
A favore di
GA
A favore di
Greedy
A favore di
GA
2.514107265E9
2.519908
542E9
1.279558
356E9
5.227715
519E9
7684738.
0
29/30
A favore di
GA
A favore di
GA
A favore di
GA
A favore di
Greedy
29/30
5/30 (=)
24/30
1.279223642E9
5.212456665E9
7259609.0
Prioritizzazione di casi di test
basata su GAs
19/30
18/30
8/30
24
Analisi Sperimentale(10)
R𝑸𝟒 : In che misura l'algoritmo genetico migliora l'efficacia dell'algoritmo Greedy, se
si include nella popolazione iniziale la soluzione prodotta dall’algoritmo Greedy ?
Area Fault/Cost
2.514420352E9
1.279374807E9
5.219295093E9
7591128.0
APFD
VIM
FLEX
BASH
GZIP
0.7594627
0.9734985
0.7552334
0.9210526
ALGORITMO GENETICO
APFD
VIM
FLEX
BASH
GZIP
AREA Fault/Cost
MIN
MAX
GA >
Greedy
Wilcoxon
(0.05)
MIN
MAX
0.758807
1
0.973783
0
0.7594
513
0.9769
943
0/30
A favore di
Greedy
A favore di
GA
2.514970035
E9
1.279132683
E9
2.516918761 30/30
E9
1.279619949 17/30
E9
A favore di
GA
A favore di
GA
A favore di 5.219709529 5.227350902 30/30
GA
E9
E9
A favore di 7545241.0
7590586.0
GA
8/30
A favore di
GA
A favore di
Greedy
0.754833 0.7557
6
103
0.998174 1
3
30/30
16/30
30/30
Prioritizzazione di casi di test
basata su GAs
GA > Greedy
Wilcoxon
(0.05)
25
Conclusioni e lavori futuri
 Risultati ottenuti complessivamente buoni (funzioni di
Fitness e metriche di Valutazione)
 Tempo di esecuzione alto per ottenere una soluzione
per programmi di grandi dimensioni (VIM e BASH)
 Casi di studio pochi (4)
 Valutare approcci Multi-obiettivo o con altri criteri di
Testing
 Iniezione di diversità nell’algoritmo genetico
- convergenza più rapida verso soluzioni migliori
Prioritizzazione di casi di test
basata su GAs
26
?
Prioritizzazione di casi di test
basata su GAs
27