Search Based Software Testing

Il Search Based Software Testing è una branca del software testing nata da pochi anni. L’idea è creare casi di test automaticamente studiando il testing come un problema di ottimizzazione. Possiamo usare tecniche di ricerca operativa per la generazione dei casi di test, come ad esempio gli algoritmi genetici.

Perché la creazione dei test lo possiamo vedere come un problema di ricerca operativa? I problemi di ricerca operativa hanno come obiettivo massimizzare o minimizzare una funzione obiettivo, che nel nostro caso potrebbe essere massimizzare il numero di difetti scoperti o linee di codice coperte. Il tutto può essere fatto variando e/o aumentando i casi di test. In generale vorremmo aumentare l’efficacia senza perdere efficienza (aumentare il numero di test).

In questo post non verrà fatta una trattazione formale ed esaustiva sugli algoritmi genetici e non verranno mostrati esempi di codice relativi ai vari strumenti a disposizione. Lo scopo di questo post è di dare un’idea sull'applicazione degli algoritmi genetici al testing del software.

Algoritmi genetici applicati al testing

Un algoritmo genetico cerca di emulare quelli che sono i meccanismi genetici che portano all’evoluzione umana (Evoluzione di Darwin). Un individuo ha una sua sequenza di geni e quando nasce una figlio da due individui avremo un “incrocio” della sequenza di geni. Con l’avanzare delle generazioni la popolazione cambia (avremo i figli dei figli ecc). Nel tempo abbiamo una selezione naturale, dove i migliori sopravvivono e con il passare delle generazioni la popolazione dovrebbe migliorare.
Con questo sistema i geni migliori tendono ad emergere, ma è anche possibile che perdiamo in diversità e questo è un problema.
Ci possono essere delle mutazioni, ovvero che per qualche motivo un gene varia. Le mutazioni introducono cambiamenti nella popolazione e si evita a di avere sempre gli stessi geni.

Con questi tre meccanismi che sono: incrocio tra i cromosomi (soluzioni), mutazione casuale e selezione naturale avremo una lenta evoluzione della specie.

Un test è una sequenza di input o eventi (al posto della sequenza di geni), l’incrocio tra due test potrebbe essere prendere gli input (o gli eventi) dal primo e secondo test. Dopo il crossover nel caso migliore abbiamo un nuovo test, nel caso peggiore non lo abbiamo (test non eseguibile).
Nella pratica, più che una fusione complessa tra i due test, potremmo pensare di spezzare il cromosoma in un punto e poi unire due cromosomi di individui diversi, cioè unire due sequenze di test.
La mutazione di un test potrebbe essere cambiare il valore di un input a caso (tra le classi di equivalenza o proprio a caso), se non è eseguibile ho un “mutante” che non nasce.

Ad esempio se abbiamo una popolazione di 100 test, con il crossover ne otteniamo altri 50, poi abbiamo delle mutazioni e.g. 5, abbiamo 100(test vecchi) + 50(nuovi) + 5(mutanti), si possono anche non far morire i vecchi. Supponiamo di aver spazio solo per 100 test, allora dobbiamo selezionare i migliori tra i 155 test. Facciamo sopravvivere i migliori, usando una metrica che tiene conto di quelli che trovano più difetti, oppure coprono più codice. Procediamo in questo modo tenendo la popolazione costante. Le metriche che scelgo mi aiutano a capire se miglioriamo con le generazioni.

La metrica che valuta la bontà di un singolo test case è detta fitness locale, mentre quella che valuta la bontà di tutta la popolazione (test suite) è detta fitness globale. Ad esempio la fitness locale potrebbe essere la copertura complessiva di un singolo test, mentre la fitness globale la copertura di tutta la test suite. Adesso al variare delle generazioni posso valutare se la fitness globale migliora o peggiora.

Supponiamo che il nostro scopo è arrivare sulla vetta di una montagna e di avere tanta nebbia che non ci fa capire quando realmente siamo arrivati in cima.
A differenza degli algoritmi genetici altre tecniche, come la ricerca del massimo della programmazione lineare, arrivano in dei punti che sembrano vette (ottimi locali) ma non lo sono. Da quel punto non si muovono convinti di essere arrivati in cima, quindi non arriviamo all’ottimo assoluto.
Gli algoritmi genetici hanno più probabilità di trovare il massimo, perché ogni tanto cambiano “strada sulla montagna”. Per una serie di passi potrebbero non prendere la strada migliore, ma poi arriviamo in cima.
Notiamo che il miglior risultato dell’algoritmo genetico è possibile che non lo dia alla fine, cioè si deve valutare sempre la fitness globale perché è possibile che l’ottimo lo raggiungiamo e poi lo perdiamo.

In sintesi per usare una tecnica genetica dobbiamo:

• modellare i casi di test come sequenza di geni;
• dobbiamo dire come funzione l’operatore di crossover;
• poi dobbiamo proporre operatori e regole per la mutazione;
• dobbiamo definire una metrica per la bontà del test case (fitness locale) e test suite (fitness globale).

Gli algoritmi genetici sono iterativi. Data una test suite iniziale, ad ogni iterazione:

• Si creano nuovi test case effettuando dei crossover e/o mutazioni con il vincolo che i nuovi test ottenuti devono essere eseguibili;
• Si valuta la fitness locale di tutti i test;
• Si selezionano i test case con la migliore fitness, tali da mantenere lo stesso quantitativo di test case dell’iterazione precedente (se vogliamo tenere costante la popolazione);
• Si calcola la fitness globale e si termina se si è arrivati ad un valore di fitness globale considerato soddisfacente secondo un criterio prescelto.

Poi posso fermarmi:

• quando la fitness globale è arrivata ad un valore per noi soddisfacente;
• quando la fitness globale non migliora più per un certo numero di iterazioni;
• oppure quando è finito il tempo a disposizione.

Problematiche e osservazioni

Una problematica può essere: quanti figli facciamo fare a ogni coppia? Se faccio fare più figli ad ogni giro dopo poche iterazioni ho molti figli. Questo può portare ad un evoluzione più rapida, ma potrei avere figli tutti uguali.

Potrei fare un evoluzioni in cui tolgo i genitori, ma in questo modo potrei perdere buoni individui.

Tipicamente la mutazione è molto ridotta rispetto al crossover perché può portare a casi anormali (molti test case non eseguibili).

Posso avere un valore di mutazione dinamico, cioè all’inizio muto poco, e poi se mi sto impantanando nella salita verso l’ottimo muto di più.

Quando eseguiamo questi algoritmi ci sono dei parametri da considerare come la popolazione, cioè il numero complessivo di casi di test. Dobbiamo valutare se tenere costante la popolazione o aumentarla nel tempo. Ad esempio potrei tenere la popolazione costante così che per definizione il test sarà efficiente dato che decido io il numero di test.

Quando l’algoritmo si “impantana”, ad esempio abbiamo la stessa copertura per 4 iterazioni potremmo aumentare il fattore mutazione per vedere cosa accade. Questo può portare ad una fitness globale peggiore per delle iterazioni (magari sto scendendo da un ottimo locale), ma poi arrivo a una soluzione migliore.

Notiamo che se per fitness locale scegliamo la copertura del codice dobbiamo stare attenti. Supponiamo di avere 3 test che coprono rispettivamente 70%, 79% e 20% delle righe di codice di un software. Il nostro algoritmo potrebbe scegliere i primi due perché coprono più righe. Il problema nasce se i due test precedenti coprono le stesse righe. Nella peggiore delle ipotesi il 2° test compre le stesse righe del 1° più quel 9%, mentre è possibile che il 3° test case copriva il 20% di righe di codice che non coprivano gli altri due. Ora è possibile che se valuto la fitness globale, considerando il 1° e 3° test case avrò il 90% (70%+20%) di copertura. Quindi nel valutare la fitness locale si dovrebbe considerare anche una metrica di diversità delle righe di codice coperte. Oppure si può pesare una riga di codice, in pratica dare un punteggio, in base a quanti altri test case la coprono.

Evo Suite

Lo strumento EvoSuite è nato in ambito accademico ma è oggi è supportato anche da Google. Di base è uno strumento per la generazione automatica di casi di test di unità. Può essere usato standalone oppure come plugin all’interno di IDE come Eclipse.

EvoSuite non considera la copertura come suo obiettivo, ma invece cerca di trovare quanti più difetti è possibile. Questo obiettivo è difficile se il codice è piccolo e non ha difetti, oppure il codice ha dei difetti ma non so quali sono. Allora potremmo pensare di inventarci noi i difetti, ovvero prendiamo il codice sorgente e lo cambiamo “a caso”, questo codice si dice codice mutante. Abbiamo ora mutazione dei test ma anche del codice.
Per fare le mutazioni sul codice viene utilizzato muJava.
Il codice mutante potrebbe non compilare, in questo caso si dice che il mutante è nato morto, l’altro caso è che il mutante si può eseguire e si suppone che questo funzioni diversamente dall’originale e questo è considerato un malfunzionamento.
Ad esempio se abbiamo una mutazione nel ramo del if, un test che non passa in quel ramo del if darà un output identico a quello del programma originale, quindi quel test non è in grado di accorgersi della mutazione e quindi quel test non è efficace. Ma un test che passa per il ramo mutato e ci da un risultato diverso si è accorto della mutazione e si dice che ha ucciso il mutante (perché ha riconosciuto il mutamento).
Quindi questa tecnica ad ogni ciclo prende il programma originale e genera un certo numero di mutanti, poi prende i test e li fa evolvere, successivamente dalla popolazione dei test prendiamo ogni test e lo proviamo su ognuno dei programmi mutati, si vede il numero di mutamenti che riconosce, è quella sarà la fitness locale.

Quindi la bravura dei singoli test è riconoscere i mutanti. Un test che riconosce tanti mutanti è migliore perché i mutanti sono programmi originali con un difetto (che è stato messo a caso) che può essere rappresentativo di difetto che mette un programmatore umano, quindi i test che facciamo hanno la possibilità di riconoscere un difetto.
Ad esempio un errore classico potrebbe essere = al posto di ==, oppure < con <=, quindi questo tool fa modifiche ma ha comunque dei vincoli. Ad esempio non mi metto a togliere le parentesi che le trova già il compilatore. Per far vedere al tool gli errori più comuni posso fare una statistica sugli errori, oppure si fa su dei repository della storia del software, li sopra troviamo errori di una certa complessità dato che non troviamo errori banali (si suppone che chi fa commit mette codice di buona qualità e toglie gli errori banali) e poi troviamo errori specifici di quel programma che non sapremmo mettere in un altro programma identico. Mettere mutanti significativi è un problema aperto. Un altro mutante è inverti l’ordine delle righe di codice (magari in del codice che manipola uno stack inseriamo errori).

Questo tool non si è limitato alla copertura del codice, ma si è impegnato a trovare le mutazioni. Qui infatti abbiamo un’ulteriore fattore di casualità i programmi mutati.
Se facciamo noi un programma con dei difetti questi non vengono visti, il tool si accorge di aver ucciso il mutante se l’output del programma originale e quello mutato sono diversi, infatti per lui l’oracolo è semplice, gli basta valutare se sono diversi gli output del programma originale e quello mutato, in pratica è il risultato del programma non mutato.
Generando test case che trovano questi difetti probabilmente troveranno anche i difetti del software da testare. Notiamo che ai casi di test generati automaticamente manca l’oracolo, che dobbiamo aggiungere noi.