SymPcNSGA-Testing: A Hybrid Approach to Mitigate Path Explosion in Software Programs

Abstract

The path explosion problem poses a significant barrier in the domain of software testing, making it nearly impossible to exhaustively explore all execution paths in large or complex software. Despite the extensive use of symbolic execution in the literature, the issue of path explosion remains largely unresolved. To address this limitation, we propose SymPcNSGA-Testing (Symbolic execution, Path Clustering, and Non-dominated Sorting Genetic Algorithm-II Testing), a hybrid methodology combining symbolic execution, path clustering, and multi-objective optimization using NSGA-II (Non-dominated Sorting Genetic Algorithm-II). Our approach aims to select a reduced yet representative set of execution paths that ensures maximum branch coverage while minimizing redundancy. SymPcNSGA-Testing operates in three stages: 1) symbolic execution with KLEE to explore the path space, 2) clustering of paths using the Ktest-cluster algorithm to group similar execution behaviors, and 3) multi-objective path optimization using NSGA-II, which selects representative paths that balance high branch coverage and minimal path set size. We evaluated our methodology on ten open-source programs from the Coreutils 9.5 package and compared it against several KLEE exploration strategies (DFS, BFS, NURS, Merging, and Covering-New). The results demonstrate that SymPcNSGA-Testing outperforms some of KLEE’s strategies by achieving high branch coverage while effectively mitigating the path explosion problem. This study highlights the benefits of combining symbolic analysis and evolutionary multi-objective optimization to enhance test efficiency in complex software systems.