Abstract

Regression testing is a critical activity for maintaining software quality by identifying faults and ensuring system reliability. However, in large-scale software systems, executing all available test cases within limited time and computational resources is often impractical. Therefore, test case prioritization aims to arrange test cases in an effective execution order to maximize testing effectiveness, particularly during the early stages of regression testing. Existing test case prioritization approaches consider various optimization objectives, including fault detection capability, code coverage, risk reduction, and execution cost. In this study, we focus on the requirement-based test case prioritization problem, where the main goal is to maximize the rate of requirement coverage as early as possible. Since the possible orderings of test cases form a factorial-sized search space, this problem exhibits NP-hard characteristics, leading to the widespread use of heuristic and metaheuristic optimization techniques. However, sparse requirement traceability matrices (RTMs) introduce additional challenges, particularly due to isolated requirements and delayed coverage of critical requirement elements. To address these challenges, this study proposes a bottleneck-aware heuristic and metaheuristic framework for requirement-based test case prioritization under sparse RTMs. The main empirical contribution of the study is the deterministic AG+BH strategy, which combines Additional Greedy with the proposed Bottleneck Hunter mechanism. This strategy uses the structure of the RTM to identify test cases associated with delayed coverage, especially singleton requirements. The MH-DBO-GA component is included as a secondary metaheuristic extension based on Dragon Boat Optimization, Genetic Algorithm operators, and memetic local search. Its role is to provide additional search diversity rather than to replace the deterministic AG+BH strategy in the current APRC setting. The proposed framework is evaluated using two sparse requirement traceability matrix datasets. The results show that AG+BH provides the strongest practical deterministic trade-off on the evaluated datasets. It obtains the highest APRC on Dataset 2 and a near-best APRC on Dataset 1, where 2-Optimal gives a slightly higher APRC but requires 23 h 23 min of execution time. MH-DBO-GA does not outperform AG+BH in this setting, but it performs better than the standard stochastic metaheuristic baselines and can be considered as an exploratory extension when additional search diversity is needed. Furthermore, an ablation analysis is performed to examine the individual contributions of informed initialization, Bottleneck Hunter, and hybrid optimization components. Overall, the findings indicate that sparse RTM-based test case prioritization benefits primarily from problem-specific bottleneck-aware heuristic reasoning, while metaheuristic refinement should be interpreted as a complementary layer for more complex or future multi-objective settings.

IPC Classification

Keywords