Constructing subtle higher order mutants from Java and AspectJ programs

Abstract

Mutation testing is a fault-based testing technique that helps testers measure and improve the fault-detection effectiveness of their test suites. However, a majority of traditional First Order Mutants (FOMs), which are created by making a single syntactic change to the source code, represent trivial faults that are often easily detected (i.e. killed). Research has shown that the majority of real faults not detected during testing are complex faults that cannot be simulated with FOMs because fixing these faults requires making multiple changes to the source code. Higher Order Mutants (HOMs), which are created by making multiple syntactic changes to the source code, can be used to simulate such faults. The majority of HOMs of a given program are killed by any test suite that kills all the FOMs. We refer to HOMs that are not killed as subtle HOMs. They represent cases where single faults interact by masking each other with respect to the given test suite and produce complex faulty behavior that cannot be simulated with FOMs. The fault-detection effectiveness of the given test suite can be improved by adding test cases that detect the faults denoted by subtle HOMs. Because subtle HOMs are rare in the exponentially large space of candidate HOMs, the cost of finding them can be high even for small programs. A brute force approach that evaluates every HOM in the search space by constructing, compiling, and executing the HOM against the given test suite is unrealistic. We developed a set of search techniques for finding subtle HOMs in the context of Java and AspectJ programming languages. We chose Java because of its popularity, and the availability of experimental tools and open source programs. We chose AspectJ because of its unique concepts and constructs and their consequent testing challenges. We developed four search-based software engineering techniques: (1)~Genetic Algorithm, (2)~Local Search, (3)~Test-Case Guided Local Search, (4)~Data-Interaction Guided Local Search. We also developed a Restricted Random Search technique and a Restricted Enumeration Search technique. Each search technique explores the search space in a different way and that affects the type of subtle HOMs that can be found by each technique. Each of the guided local search techniques uses a heuristic to improve the ability of Local Search to find subtle HOMs. Due to the unavailability of higher order mutation testing tools for AspectJ and Java programs, we developed HOMAJ, a Higher Order Mutation Testing tool for AspectJ and Java programs for finding subtle HOMs. HOMAJ implements the developed search techniques and automates the process of creating, compiling, and executing both FOMs and HOMs. The results of our empirical studies show that all of the search techniques were able to find subtle HOMs. However, Local Search and both the Guided Local Search techniques were more effective than the other techniques in terms of their ability to find subtle HOMs. The search techniques found more subtle HOMs by combining faults created by primitive Java mutation operators than by combining faults created by Java class level operators and AspectJ operators. Composing subtle HOMs of lower degrees generated by Restricted Enumeration Search is an effective way to find new subtle HOMs of higher degrees because such HOMs are likely to exist as compositions of multiple subtle HOMs of lower degrees. However, the search-based software engineering techniques were able to find subtle HOMs of higher degrees that could not be found by combining subtle HOMs of lower degrees.