A Condition Coverage-Based Black Hole Inspired Meta-Heuristic for Test Data Generation

Combinatorial Testing (CT) strategy is one of the well-known methods to achieve high code coverage rates during testing for safety critical systems. While generating test data in CT, we often encounter the problem of test case explosion, especially for the systems with multiple parameters and values. To overcome this challenge, search-based CT (CSST) strategies are introduced. In this study, we propose a new algorithm that inspires from a binary variant of Black Hole Algorithm (BBH) in CSST and adopt BBH according to the CT challenges in an industrial context. The proposed BBH version, BH-AllStar, aims the following: (1) obtaining higher condition coverage, (2) avoiding being stuck in local minima and (3) handling discrete input values. We finalize the solution space of BH-AllStar by reassessing the previously removed stars and incorporating the useful ones into it. We evaluate our approach on a real-life software project in the safety-critical domain with respect to condition coverage, number of test cases and execution time. Compared to BBH, BH-AllStar generates more test cases which achieve up to 43% increase in condition coverage.