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.
References
[1]
Cadar, C., Dunbar, D., Engler, D.R., et al. (2008) KLEE: Unassisted and Automatic Generation of High-Coverage Tests for Complex Systems Programs. 8th USENIX Symposium on Operating Systems Design and Implementation, San Diego, 8-10 December 2008, 209-224.
[2]
Copeland, P.T. (2014) Using State Merging and State Pruning to Address the Path Explosion Problem Faced by Symbolic Execution. Master’s Thesis, Air Force Institute of Technology.
[3]
Baars, A., Harman, M., Hassoun, Y., Lakhotia, K., McMinn, P., Tonella, P., et al. (2011) Symbolic Search-Based Testing. 2011 26th IEEE/ACM International Conference on Automated Software Engineering (ASE 2011), Lawrence, 6-10 November 2011, 53-62. https://doi.org/10.1109/ase.2011.6100119
[4]
He, J., Sivanrupan, G., Tsankov, P. and Vechev, M. (2021) Learning to Explore Paths for Symbolic Execution. Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security, 15-19 November 2021, 2526-2540. https://doi.org/10.1145/3460120.3484813
[5]
Staats, M. and Pǎsǎreanu, C. (2010) Parallel Symbolic Execution for Structural Test Generation. Proceedings of the 19th International Symposium on Software Testing and Analysis, Trento, 12-16 July 2010, 183-194. https://doi.org/10.1145/1831708.1831732
[6]
Bucur, S., Ureche, V., Zamfir, C. and Candea, G. (2011) Parallel Symbolic Execution for Automated Real-World Software Testing. Proceedings of the Sixth Conference on Computer Systems, Salzburg, 10-13 April 2011, 183-198. https://doi.org/10.1145/1966445.1966463
[7]
van Vliet, D. (2023) A Heuristic Approach to the Path Explosion Problem for Complex Heap Programs. Master’s Thesis, Utrecht University.
[8]
Xiao, X., Zhang, X. and Li, X. (2010) New Approach to Path Explosion Problem of Symbolic Execution. 2010 First International Conference on Pervasive Computing, Signal Processing and Applications, Harbin, 17-19 September 2010, 301-304. https://doi.org/10.1109/pcspa.2010.80
[9]
Zhang, Y., Chen, Z., Shuai, Z., Zhang, T., Li, K. and Wang, J. (2020) Multiplex Symbolic Execution: Exploring Multiple Paths by Solving Once. Proceedings of the 35th IEEE/ACM International Conference on Automated Software Engineering, 21-25 December 2020, 846-857. https://doi.org/10.1145/3324884.3416645
[10]
Bessler, G., Cordova, J., Cullen-Baratloo, S., Dissem, S., Lu, E., Devin, S., et al. (2021) Metrinome: Path Complexity Predicts Symbolic Execution Path Explosion. 2021 IEEE/ACM 43rd International Conference on Software Engineering: Companion Proceedings (ICSE-Companion), Madrid, 25-28 May 2021, 29-32. https://doi.org/10.1109/icse-companion52605.2021.00028
[11]
Gong, D., Zhang, W. and Yao, X. (2011) Evolutionary Generation of Test Data for Many Paths Coverage Based on Grouping. Journal of Systems and Software, 84, 2222-2233. https://doi.org/10.1016/j.jss.2011.06.028
[12]
Zhu, Z.M., Xu, X. and Jiao, L. (2017) Improved Evolutionary Generation of Test Data for Multiple Paths in Search-Based Software Testing. 2017 IEEE Congress on Evolutionary Computation (CEC), San Sebastian, 5-8 June 2017, 612-620. https://doi.org/10.1109/cec.2017.7969367
[13]
Semujju, S.D., Huang, H., Liu, F., Xiang, Y. and Hao, Z. (2023) Search-Based Software Test Data Generation for Path Coverage Based on a Feedback-Directed Mechanism. Complex System Modeling and Simulation, 3, 12-31. https://doi.org/10.23919/csms.2022.0027
[14]
Hassan, A., Shah, W., Husein, A., Talib, M.S., Mohammed, A.A.J. and Iskandar, M. (2019) Clustering Approach in Wireless Sensor Networks Based on K-Means: Limitations and Recommendations. International Journal of Recent Technology and Engineering, 7, 119-126.
