Prioritizzazione di casi di test basata su algoritmi genetici Relatore: Prof. Andrea De Lucia...

Prioritizzazione di casi di test basata su algoritmi genetici

Relatore:

Prof. Andrea De Lucia

Supervisione:

Dott. Annibale Panichella

Candidato:

Gianluca Carbone

0522500116

Università degli Studi di Salerno

Facoltà di Scienze Matematiche Fisiche e Naturali

Laurea Magistrale in Sistemi Informativi e Tecnologie del Software

Anno Accademico 2013/2014

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.


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.


4

S1 S2 S3 S4 S5 S6 S7 S8 S9 S10 COST

T1 X X X X X X X X 4T2 X X X X X X X X X 5T3 X X X X 3T4 X X X X X 3

Possibili ordinamenti:

T1 - T2 - T3 - T4 T2 - T3 - T4 - T1T4 - T3 - T2 - T1 …

BackgroundApprocci 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 GAs5

Background(2)

Contributo di questo lavoroGAs (Genetic Algorithms) sono stati utilizzati efficacemente per risolvere solo due problemi relativi al test di regressione:

minimizzazione Rappresentazione binaria selezione delle soluzioni

ordinamento Rappresentazione binaria

Obiettivo «Riempire questo gap», fornendo un approccio basato su GAs per risolvere il problema di test case prioritisation.


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 .


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

• Ordinamento dei test case


8

T1 T2 T3 T4 T5 T6

1 0 0 1 1 1

1 2 3 4 5 6

T1 T4 T6 T5 T2 T3

Approccio proposto alla soluzione del problema di Test Case Prioritisation(2)

Criteri di test1. Criterio di copertura di statement: numero di statement coperti.

2. Criterio di costo cumulativo: numero di istruzioni elementari nel codice.


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.


10

Approccio proposto alla soluzione del problema di Test Case Prioritisation (4)

Funzione di Fitness (la nostra soluzione):


11

P

P’

C

C’


Selezione Data una popolazione P di soluzioni, seleziona le migliori /2 soluzioni in base alla funzione obiettivo

Crossover Mutazione


12


Algoritmo Genetico


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.


14

Implementazione (2)Parametri di Input e Output Input1. Matrice binaria rappresentante la copertura degli Statements

2. Vettore di interi rappresentante il costo di ogni test case

Output1. FUN: file contenente il valore della funzione obiettivo raggiunto.

2. VAR: file contente il vettore ordinato della test suite.

3. Nome.fig: file Matlab; grafico rappresentante la curva che ottiene il più alto valore di fitness

4. Algorithm.log: file contenente informazioni relative all’esecuzione dell’algoritmo.


15

Analisi Sperimentale

Caso di Studio 4 Programmi Open-Source GNU disponibili dal Software-artifact

Infrastructure Repository (SIR): Bash, Flex, Gzip e Vim


16

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

Analisi Sperimentale (2)

Algoritmo Greedy


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 ?


18

Analisi Sperimentale (4) R: In che misura l’algoritmo genetico produce soluzioni ottimali in

termini di costo e copertura rispetto all’algoritmo Greedy ?


19

Algoritmo Greedy

Caso di studio Funzione di Fitness

VIM 6.341852054039E12BASH 9.031854710916E24FLEX 2.29745278156E11

GZIP 3.061952099E9

Algoritmo Genetico – dati statistici della funzione di fitness

Caso di studio

Min Max GA > Greedy Test Statistico di Wilcoxon (0.05)

VIM 6.341578700434E+24 6.342245195263E+24 25/30 A favore di GA

BASH 8.999917407306E+24 9.035568125545E24 5/30 A favore di Greedy

FLEX 2.29727E+22

2.29754E+22

8/30 A favore di Greedy

GZIP 3.06195E+18

4.82635E+18

29/30 A favore di GA

Analisi Sperimentale (5)


20

GZIP

FLEX

COST

COST

COV

COV

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 ?


21

Algoritmo Greedy

Caso di studio Funzione di FitnessVIM 6.341852054039E12BASH 9.031854710916E24FLEX 2.29745278156E11GZIP 3.061952099E9

Algoritmo Genetico – dati statistici della funzione di fitness

Caso di studio Min Max GA > Greedy Test Statistico di Wilcoxon (0.05)

VIM 6.341854933457E12 6.34258E+24


BASH 9.03185E+36

9.03382E+36


FLEX 2.29750432953E11 2.29753094106E11


GZIP 4.80943E+17

4.85923E+17


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 ?


22

Analisi Sperimentale (8)Metriche di Valutazione

APFD (Average Percentage Faults Detection)

APFD = Area Fault/Cost

Funzione obiettivo Metrica di valutazione


23

Analisi Sperimentale(9)


24

APFD Area Fault/CostVIM 0.7594627 2.514420352E9

FLEX 0.9734985 1.279374807E9BASH 0.7552334 5.219295093E9GZIP 0.9210526 7591128.0

ALGORITMO GENETICO APFD AREA Fault/Cost MIN MAX GA >

GreedyWilcoxon (0.05)

MIN MAX GA > Greedy

Wilcoxon (0.05)

VIM 0.7585784

0.7594350


2.514107265E9 2.519908542E9


FLEX 0.9733089

0.9791608


1.279223642E9 1.279558356E9


BASH 0.7550493

0.7552334

5/30 (=) A favore di Greedy

5.212456665E9 5.227715519E9


GZIP 0.9112974

0.9629629


7259609.0 7684738.0


R: Quale è l’efficacia nell'individuare i fault dell’algoritmo genetico rispetto all’algoritmo Greedy ?

Analisi Sperimentale(10)


25

APFD Area Fault/CostVIM 0.7594627 2.514420352E9FLEX 0.9734985 1.279374807E9BASH 0.7552334 5.219295093E9GZIP 0.9210526 7591128.0

ALGORITMO GENETICO APFD AREA Fault/Cost MIN MAX GA >

GreedyWilcoxon (0.05)

MIN MAX GA > Greedy Wilcoxon (0.05)

VIM 0.7588071

0.7594513


2.514970035E9

2.516918761E9


FLEX 0.9737830

0.9769943


1.279132683E9

1.279619949E9


BASH 0.7548336

0.7557103


5.219709529E9

5.227350902E9


GZIP 0.9981743

1 30/30 A favore di GA

7545241.0 7590586.08/30

A favore di 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 ?

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


26

?


27

Prioritizzazione di casi di test basata su algoritmi genetici Relatore: Prof. Andrea De Lucia...

Documents

Transcript of Prioritizzazione di casi di test basata su algoritmi genetici Relatore: Prof. Andrea De Lucia...