Improving Test Distance for Failure Clustering with Hypergraph Modelling
This work addresses the challenge of debugging software with multiple faults, which is a practical problem for developers and automated debugging tools, representing a novel method for a known bottleneck.
The paper tackled the problem of clustering test failures by root cause in multi-fault scenarios, introducing a hypergraph-based distance metric that achieved perfect clustering in 418 out of 605 test runs and reduced wasted debugging effort by up to 82% compared to state-of-the-art techniques.
Automated debugging techniques, such as Fault Localisation (FL) or Automated Program Repair (APR), are typically designed under the Single Fault Assumption (SFA). However, in practice, an unknown number of faults can independently cause multiple test case failures, making it difficult to allocate resources for debugging and to use automated debugging techniques. Clustering algorithms have been applied to group the test failures according to their root causes, but their accuracy can often be lacking due to the inherent limits in the distance metrics for test cases. We introduce a new test distance metric based on hypergraphs and evaluate their accuracy using multi-fault benchmarks that we have built on top of Defects4J and SIR. Results show that our technique, Hybiscus, can automatically achieve perfect clustering (i.e., the same number of clusters as the ground truth number of root causes, with all failing tests with the same root cause grouped together) for 418 out of 605 test runs with multiple test failures. Better failure clustering also allows us to separate different root causes and apply FL techniques under SFA, resulting in saving up to 82% of the total wasted effort when compared to the state-of-the-art technique for multiple fault localisation.