Effective methods to tackle the equivalent mutant problem when testing software with mutation

Abstract

Mutation Testing is undoubtedly one of the most effective software testing techniques that has been applied to different software artefacts at different testing levels. Apart from mutation’s versatility, its most important characteristic is its ability to detect real faults. Unfortunately, mutation’s adoption in practice is inhibited, primarily due to the manual effort involved in its application. This effort is attributed to the Equivalent Mutant Problem. The Equivalent Mutant Problem is a well-known impediment to mutation’s practical adoption that affects all phases of its application. To exacerbate the situation, the Equivalent Mutant Problem has been shown to be undecidable in its general form. Thus, no complete, automated solution exists. Although previous research has attempted to address this problem, its circumvention remains largely an open issue. This thesis argues that effective techniques that considerably ameliorate the problem’s adverse effects can be devised. To this end, the thesis introduces and empirically evaluates several such approaches that are based on Mutant Classification, Static Analysis and Code Similarity. First, the thesis proposes a novel mutant classification technique, named Isolating Equivalent Mutants (I-EQM) classifier, whose salient feature is the utilisation of second order mutants to automatically isolate first order equivalent ones. The empirical evaluation of the approach, based on real-world test subjects, suggests that I-EQM outperforms the existing techniques and results in a more effective testing process. Second, the thesis formally defines nine data flow patterns that can automatically detect equivalent and partially equivalent mutants. Their empirical evaluation corroborates this statement, providing evidence of their existence in real-world software and their equivalent mutant detection capabilities. Third, MEDIC (Mutants’ Equivalence Discovery), an automated framework that implements the aforementioned patterns and manages to detect equivalent and partially equivalent mutants in different programming languages, is introduced. The experimental investigation of the tool, based on a large set of manually analysed mutants, reveals that MEDIC can detect efficiently more than half of the considered equivalent mutants and provides evidence of automated stubborn mutant detection. Finally, the thesis proposes the concept of mirrored mutants, that is mutants affecting similar code fragments and, more precisely, analogous code locations within these fragments. It is postulated that mirrored mutants exhibit analogous behaviour with respect to their equivalence. The empirical evaluation of this concept supports this statement and suggests that the number of the equivalent mirrored mutants that have to be manually analysed can be reduced approximately by half.

Η Μέθοδος των Μεταλλάξεων είναι μία από τις πιο αποτελεσματικές τεχνικές Ελέγχου Λογισμικού η οποία έχει χρησιμοποιηθεί σε διάφορες γλώσσες προγραμματισμού και στα περισσότερα επίπεδα Ελέγχου. Το κύριο χαρακτηριστικό της Μεθόδου είναι η δυνατότητα εύρεσης πραγματικών σφαλμάτων που ενδέχεται να υπάρχουν στο εξεταζόμενο αντικείμενο. Παρά την αποτελεσματικότητά της, η Μέθοδος δεν χρησιμοποιείται ευρέως στην πράξη. Ο κύριος λόγος είναι το κόστος εφαρμογής της που αποδίδεται κυρίως στο Πρόβλημα των Ισοδύναμων Μεταλλακτών. Το Πρόβλημα των Ισοδύναμων Μεταλλακτών είναι ένα αρκετά μελετημένο πρόβλημα που έχει αποδειχθεί ότι είναι μη-αποφασίσιμο. Συνεπώς, η δημιουργία πλήρως αυτοματοποιημένων λύσεων δεν είναι εφικτή. Στην βιβλιογραφία της Μεθόδου έχουν προταθεί τεχνικές οι οποίες δυστυχώς δεν μπορούν να αντιμετωπίσουν επαρκώς το συγκεκριμένο πρόβλημα. Στόχος της παρούσας διατριβής είναι η εισαγωγή και η εμπειρική αξιολόγηση κατάλληλων τεχνικών που μπορούν να μειώσουν δραστικά το κόστος εφαρμογής της Μεθόδου. Αρχικά, η διατριβή εισαγάγει μία νέα τεχνική που βασίζεται στην Κατηγοριοποίηση Μεταλλακτών. Το κύριο χαρακτηριστικό της συγκεκριμένης τεχνικής είναι η χρήση μεταλλακτών δεύτερης τάξης για την κατηγοριοποίηση μεταλλακτών πρώτης τάξης. Η εμπειρική μελέτη της τεχνικής αυτής, βασισμένη σε πραγματικά συστήματα λογισμικού, έδειξε ότι είναι πιο αποτελεσματική από τις ήδη υπάρχουσες τεχνικές. Επιπρόσθετα, στα πλαίσια της διατριβής, υλοποιήθηκε ένα αυτοματοποιημένο εργαλείο για την ανίχνευση ισοδύναμων μεταλλακτών που βασίζεται σε συγκεκριμένες συνθήκες ροής ελέγχου και δεδομένων μεταξύ των μεταβλητών του υπό εξέταση προγράμματος. Η εμπειρική αξιολόγηση του εργαλείου έδειξε ότι μπορεί να ανιχνεύσει αυτόματα ένα μεγάλο μέρος των ισοδύναμων μεταλλακτών του υπό εξέταση προγράμματος και μπορεί να εφαρμοστεί σε διαφορετικές γλώσσες προγραμματισμού. Η συγκεκριμένη δυνατότητα του εργαλείου είναι ένα από τα βασικά χαρακτηριστικά που το ξεχωρίζουν από τα υπόλοιπα της βιβλιογραφίας. Τέλος, εξετάστηκε αν συγκεκριμένοι μεταλλάκτες που ανήκουν σε παρόμοια κομμάτια κώδικα έχουν κοινή συμπεριφορά ως προς την ισοδυναμία τους και ορίστηκαν τυπικά οι συνθήκες εύρεσής τους. Η εμπειρική μελέτη της τεχνικής έδειξε ότι πράγματι οι μεταλλάκτες αυτοί παρουσιάζουν τέτοια συμπεριφορά και μπορούν να μειώσουν στο μισό το κόστος εφαρμογής της μεθόδου των Μεταλλάξεων σε παρόμοια κομμάτια κώδικα.