Master Thesis
1 like105 views
La tesi di laurea di Giovanni Grano esplora l'implementazione e il confronto di tecniche per la generazione automatica di casi di test basata su approcci di ricerca euristica, analizzando specificamente l'algoritmo Ocelot. Viene evidenziata l'ottimizzazione della copertura dei branch e la riduzione delle dimensioni delle suite di test rispetto a metodologie precedenti. I risultati suggeriscono una convergenza più rapida e una test suite significativamente più piccola mantenendo livelli di copertura comparabili.
![Puntatori
test (int a, int b, int* c, int* d, int* e)
#1 numeri reali
1 array ∀ puntatore
#1 array di associazione
Ridefinizione del cromosoma
[10,22] a e b
[0, 1, 22, 3] array #0
[23, 2, 2, 65] array #1
[22, 56, 3, 3] array #2
[0, 0, 1] associazione puntatori
Una matrice tiene traccia dei puntatori
agli array presenti nel cromosoma
0 1 22 3
23 2 2 65
22 56 3 3
if (c == d)
if (d == e)
return true; L’indice di riga viene utilizzato per calcolare la
distanza dal target](https://image.slidesharecdn.com/mhdthesis-160826075236/85/Master-Thesis-13-320.jpg)
Master Thesis
- 1. Università degli Studi di Salerno Dipartimento di Informatica Implementation and comparison of novel techniques for automated search based test data generation Tesi di Laurea Magistrale in Informatica Relatore Prof. Andrea De Lucia Candidato Giovanni Grano
- 2. Outline Approcci implementati Caso di studio Conclusioni e sviluppi futuri OCELOTOverview
- 3. OVERVIEW
- 4. Search Based Software Engineering Applica tecniche di ricerca euristiche a tipici problemi dell’ingegneria del software, opportunamente riformulati come problemi di ottimizzazione algoritmi genetici hill climbing AVM algoritmi memetici
- 5. Search Based Software Testing 0 175 350 525 700 1975 1979 1983 1989 1993 1997 2001 2005 2008 2011 2013 SBST è una sotto area di SBSE che utilizza euristiche di ottimizzazione per tecniche di ricerca, con lo scopo di automatizzare i processi di testing generazione automatica minimizzazione di test case prioritizzazione di test case selezione di test case
- 6. OCELOT
- 8. Overview del processo ! " # $ % & Instrumentazione del codice sorgente Generazione del makefile Compilazione della libreria Selezione dei target Ricerca soluzione Simulazione
- 9. if (a == 10) { b = 11; } else { b = 10; } if (_f_ocelot_trace( a == 10, //condizione originale _f_ocelot_eq_numeric(a, 10), //distanza da true _f_ocelot_neq_numeric(a, 10) //distanza da false )){ b = 11; } else { b = 10; } Instrumentazione Traccia gli eventi Registra le distanze
- 10. Compilazione Ubuntu Linux ' )* Windows Mac OS X Generazione del makefile Supporto multipiattaforma
- 11. if (a == 10) { b = 11; } else { b = 10; } Java Library+ Lista di eventi, Esecuzione e simulazione Data la lista di eventi registrati e il CFG della funzione, si simula l’esecuzione sul grafo
- 12. 0 0.2 scelta distanza False distanza True false 0 0.2 Esecuzione e simulazione Java Library+ Lista di eventi,
- 13. Puntatori test (int a, int b, int* c, int* d, int* e) #1 numeri reali 1 array ∀ puntatore #1 array di associazione Ridefinizione del cromosoma [10,22] a e b [0, 1, 22, 3] array #0 [23, 2, 2, 65] array #1 [22, 56, 3, 3] array #2 [0, 0, 1] associazione puntatori Una matrice tiene traccia dei puntatori agli array presenti nel cromosoma 0 1 22 3 23 2 2 65 22 56 3 3 if (c == d) if (d == e) return true; L’indice di riga viene utilizzato per calcolare la distanza dal target
- 14. Approccio path di base + single target Un target per ogni cammino linearmente indipendente Approach level Numero di nodi del path obiettivo non coperti Branch distance Somma delle distanze nel punto in cui il path diverge Ricerca single-target sui branch non coperti " parametri archi . T.C. 1 / no T.C. " single target . T.C. 2
- 16. Many Object Sorting Algorithm Riformulazione della branch coverage come problema multi-obiettivo Riformulazione della funzione di fitness Sia B = {b1, …, bm} l’insieme dei branch del programma, occorre trovare un insieme di casi di test che ottimizzi la copertura degli m branch Vettore di fitness La soluzione è rappresentata da un vettore di fitness {f1, …, fm}. Per ogni target viene considerata la somma tra branch distance e approach level Dominanza e ottimalità di Pareto Ogni soluzione è valutata in termini di dominanza di Pareto e ottimalità di Pareto
- 17. Many Object Sorting Algorithm Un caso di test x* si dice Pareto ottimale se e solo se non è dominato da nessun altro caso di test Ottimalità di Pareto Un caso di test x domina un altro caso di test y se e solo se: Dominanza di Pareto Ranking tradizionale vs nuovo criterio di preferenza
- 18. Many Object Sorting AlgorithmMany Object Sorting Algorithm L’algoritmo 1 Popolazione random iniziale 2 Si applicano crossover e mutazione Generazione offspring 3 Algoritmo di preference sorting 4 In accordo al rank assegnato e alla crowding distance Generazione nuova popolazione 5 Le soluzioni che coprono un target vengono aggiunte ad un archivio Archiviazione delle soluzioni Pi Qi F0 F1 F2 preference sorting Fn soluzioni rigettate Pi+1 nuova popolazione crowding distance
- 19. Algoritmo basato sul CDG Algoritmo memory-based che cerca di massimizzare la coverage collaterale Copertura collaterale Attraverso l’analisi del Control Dependence Graph si mira a massimizzare la coverage collaterale per un dato caso di test Funzione di fitness secondaria Una funzione di fitness secondaria misura la coverage collaterale raggiunta Coverable branches Attraverso il CDG calcoliamo il numero di coverable branches per un arco obiettivo
- 20. Algoritmo basato su CDG S 61 32 87 54 FTFT FT Coverable edges Funzione di fitness per la collateral coverage
- 21. CASO DI STUDIO
- 22. Research Questions Branch coverage RQ 1 ' # casi di test RQ 2 0 Convergenza RQ 3 I due approcci introdotti sono stati valutati empiricamente utilizzando come baseline la metodologia basata sui path linearmente indipendenti
- 23. ! 1 Caso di studio 1Funzioni sotto esame !Setting funzione LOC #branch V(G) triangle 21 14 7 gimp_rbg_to_hsl_int 58 14 7 gimp_rbg_to_hsc4 62 18 9 cliparc 136 64 32 Csqrt 26 6 3 Parametro valore popolazione iniziale 100 crossover rate 0.8 mutation rate 0.2 constant mutation rate mutation rate/20 search budget 30.000 2 2Operatori tipologia operatore selezione Binary Tournament crossover SBX Crossover mutazione Polynomial + Constant Mutation
- 24. RQ 1. Branch coverage 0 0,3 0,5 0,8 1 triangle gimp_rgb_to_hsl_int gimp_rgb_to_hsc4 cliparc Csqrt 1,00 0,95 0,67 0,910,91 1,00 0,95 0,67 0,930,93 1,00 0,95 0,67 0,930,93 McCabe MOSA CDG Based
- 25. RQ 2. Dimensione della test suite 0 12,5 25 37,5 50 triangle gimp_rgb_to_hsl_int gimp_rgb_to_hsc4 cliparc Csqrt 3 15 3 56 3,2 16,6 2,8 5 6,8 4 43,5 32 11,210,5 McCabe MOSA CDG Based
- 26. RQ 3. Velocità di convergenza 0 50000 100000 150000 200000 triangle 76.532 26.351 196.766 McCabe MOSA CDG Based 0 75000 150000 225000 300000 gimp_rgb_to_hsl_int 66.280 6.054 259.252 0 225000 450000 675000 900000 gimp_rgb_to_hsc4 66.280 340 841.764 0 400000 800000 1200000 1600000 cliparc 133.753 79.420 1.526.544 0 375 750 1125 1500 Csqrt 1.427 1.086 1.409
- 27. Analisi dei risultati Coverage Test Suite Size Convergenza RQ1 RQ2 RQ3 L’algoritmo multi-obiettivo converge dopo un numero di valutazioni delle soluzioni candidate estremamente più piccolo Convergenza I nuovi approcci garantiscono una test suite del 50% più piccola, rispetto all’approccio dei path di base, al netto della minimizzazione Test Suite Size Gli algoritmi introdotti in OCELOT non incrementano il livello di coverage raggiunto dalla tecnica dei path di base Coverage
- 28. In sommario
- 29. Sviluppi futuri 25% 13% 9% Approcci multi-obiettivo su un insieme ridotto di branch S 61 32 87 54 FTFT FT 109 FT
- 30. Sviluppi futuri 25% 13% 9% Uso di algoritmi evolutivi non genetici