Testing and fault localization of phylogenetic inference programs using metamorphic technique

Many phylogenetic inference programs are available to infer evolutionary relationships among taxa using aligned sequences of characters, typically DNA or amino acid. These programs are often used to infer the evolutionary history of species. However, it is in most cases impossible to systematically verify the correctness of the tree returned by these programs, as the correct evolutionary history is generally unknown and unknowable. Neither is it possible to verify whether any non-trivial tree is correct in accordance with the specication of the often complicated search and scoring algorithms used during computation. Since there is either no mechanism or infeasible (called test oracle) to get a mechanism that we can use to verify the correctness of the returned tree, testing the correctness of any phylogenetic inference program suffers from the oracle problem (a well known problem in software testing). Due to the oracle problem, testing is ineffective in determining inputs that cause the program to fail, and thus the testing team is unable to pass failure-causing inputs to the debugging team for locating the fault(s). Though there are many testing and fault localization techniques, they cannot be applied when programs suffer from the oracle problem. Here, we demonstrate how to apply a simple software testing technique, called Metamorphic Testing (MT), to alleviate the oracle problem in testing and fault localization in phylogenetic inference programs. Metamorphic testing checks whether certain necessary properties (called metamorphic relations, MRs) of a program are satisfied based on multiple inputs and outputs of the programs. In case a MR is being violated, the program has a failure. We found that metamorphic testing can detect failures in faulty phylogenetic inference programs. Furthermore, we document our experiences in using MT in statistical fault localization.