The Hybrid Local Maximum Distance Algorithm with Dissimilarity-Based Test Case Prioritization for Software Product Line Testing

Abstract

Software Product Line (SPL) testing presents significant challenges due to configuration variability.  The software tester needs to ensure a good quality of common and variant-specific behaviours across product variants. Test Case Prioritization (TCP) is a well-established strategy for improving regression testing efficiency by enabling early fault detection. This paper proposes the hybrid prioritization approach that integrates a dissimilarity-based with the Enhanced Local Maximum Distance Algorithm (ELMDA). The proposed approach introduces three hybrid string distance techniques, NEHT1, NEHT2, and NEHT3 combining Jaro-Winkler and Manhattan distance to quantify test case diversity more effectively. These dissimilarity scores guide the selection of structurally and behaviourally distinct test cases, enhancing both fault detection and execution efficiency. Empirical evaluations using two SPL case studies which are GPS and i-Robot Roomba. Each case studies are tested against five mutant versions. Results shown that the proposed approach significantly outperforms existing techniques in terms of Average Percentage of Faults Detected (APFD) and execution time. Notably, NEHT1 achieves the highest APFD and lowest execution time across both experiments. Statistical analysis confirms the significance of these improvements. The results establish ELMDA with NEHT1 as a promising solution for effective and scalable SPL regression testing.