Accelerating Sequence Covering Array Generation and Optimization via Differential Evaluation and Process-Level Parallelism
Main Article Content
Abstract
Sequence Covering Arrays (SCAs) are an extension of combinatorial testing configurations designed to catch ordering faults. An SCA guarantees that all ordered t-way interactions exist as subsequences within the configuration. Generating and optimizing SCAs is computationally expensive, which has hindered their use in practice. This work presents a novel acceleration framework tailored for SCA construction routines. The key idea is to apply algorithm restructuring to existing routines to achieve gains without modifying their underlying semantics. The acceleration framework utilizes differential evaluation to prevent redundant global computations, leverages fixed-size tensors to streamline coverage management, and employs process-level parallelism to allocate independent evaluations over multiple CPU cores. Across all test scenarios, the performance improvements were clearly evident. Phase 1 shows marginal gains from purely algorithmic acceleration but demonstrates a speedup of 2.58× to 3.80× end-to-end when implemented in its accelerated and parallel form. However, phase 2 shows significant improvement from algorithmic restructuring yielding 2.21× – 10.41× speedup. When accelerated and parallelized, phase 2 shows 80.65× – 259.70× speedup end-to-end across all configurations. Best case speedup observed was 259.70×. These speedups demonstrate that scalable SCA construction is possible through restructuring for parallel evaluation while maintaining coverage correctness.
Downloads
Article Details
Section
How to Cite
References
Ahmed, B.S., Gambardella, L.M., Afzal, W. and Zamli, K.Z., 2017. Handling constraints in combinatorial interaction testing in the presence of multi-objective particle swarm optimization and multithreading. Information and Software Technology, 86, pp. 20–36. https://doi.org/10.1016/j.infsof.2017.02.004
Amdahl, G.M., 1967. Validity of the single processor approach to achieving large-scale computing capabilities. In: Proceedings of the April 18–20, 1967 Spring Joint Computer Conference (AFIPS '67 Spring), Atlantic City, NJ, USA, pp. 483–485. https://doi.org/10.1145/1465482.1465560
Bohm, S., Krieter, S., Heb, T., Thum, T. and Lochau, M., 2024. Incremental identification of t-wise feature interactions. In: Proceedings of the 18th International Working Conference on Variability Modelling of Software-Intensive Systems (VaMoS '24), pp. 27–36. https://doi.org/10.1145/3634713.3634715
Bombarda, A., Gargantini, A. and Calvagna, A., 2023. Multi-thread combinatorial test generation with SMT solvers. In: Proceedings of the 38th ACM/SIGAPP Symposium on Applied Computing (SAC ’23), Tallinn, Estonia, pp. 1698–1705. https://doi.org/10.1145/3555776.3577703
Castro, O., Bruneau, P., Sottet, J.-S. and Torregrossa, D., 2024. Landscape of high-performance Python to develop data science and machine learning applications. ACM Computing Surveys, 56(3), Article 65, pp. 1–30. https://doi.org/10.1145/3617588
Chee, Y.M., Colbourn, C.J., Horsley, D. and Zhou, J., 2013. Sequence covering arrays. SIAM Journal on Discrete Mathematics, 27(4), pp. 1844–1861. https://doi.org/10.1137/120894099
Demiroz, M. and Yılmaz, C., 2016. Using simulated annealing for computing cost-aware covering arrays. Applied Soft Computing, 49, pp. 1129–1144. https://doi.org/10.1016/j.asoc.2016.08.022
Fadhil, H.M., Abdullah, M.N. and Younis, M.I., 2023. Innovations in t-way test creation based on a hybrid hill climbing-greedy algorithm. IAES International Journal of Artificial Intelligence, 12(2), pp. 794–805. https://doi.org/10.11591/ijai.v12.i2.pp794-805
Fan, Y., Wan, C., Fu, C., Han, L. and Xu, H., 2023. VDoTR: Vulnerability detection based on tensor representation of comprehensive code graphs. Computers & Security, 130, P. 103247. https://doi.org/10.1016/j.cose.2023.103247
Guo, X., Song, X., Zhou, J., Wang, F., Tang, K. and Wang, Z., 2023. A memetic algorithm for high-strength covering array generation. IET Software, 17(4), pp. 538–553. https://doi.org/10.1049/sfw2.12138
Gustafson, J.L., 1988. Reevaluating Amdahl’s law. Communications of the ACM, 31(5), pp. 532–533. https://doi.org/10.1145/42411.42415
Islam, M., Khan, F., Alam, S. and Hasan, M., 2023. Artificial intelligence in software testing: A systematic review. In: Proceedings of the IEEE Region 10 Conference (TENCON 2023). https://doi.org/10.1109/TENCON58879.2023.10322349
Izquierdo-Marquez, I., Torres-Jimenez, J., Acevedo, B. and Avila-George, H., 2018. A greedy-metaheuristic 3-stage approach to construct covering arrays. Information Sciences, 460–461, pp. 172–189. https://doi.org/10.1016/j.ins.2018.05.047
Kuhn, D.R., Higdon, J.M., Lawrence, J.F., Kacker, R.N. and Lei, Y., 2012. Combinatorial methods for event sequence testing. In Proceedings of the IEEE International Conference on Software Testing, Verification and Validation (ICST), pp. 601–609. https://doi.org/10.1109/ICST.2012.147
Lara-Alvarez, M. and Avila-George, H., 2015. A new algorithm for post-processing covering arrays. International Journal of Advanced Computer Science and Applications, 6(12), pp. 250–254. https://doi.org/10.14569/IJACSA.2015.061234
Lee, S. and Kim, S., 2020. Parallel simulated annealing with a greedy algorithm for Bayesian network structure learning. IEEE Transactions on Knowledge and Data Engineering, 32(6), pp. 1157–1166. https://doi.org/10.1109/TKDE.2019.2899096.
Li, F., Zhou, J., Li, Y., Hao, D. and Zhang, L., 2022. AGA: An accelerated greedy additional algorithm for test case prioritization. IEEE Transactions on Software Engineering, 48(12), pp. 5102–5119. https://doi.org/10.1109/TSE.2021.3137929
Mercan, H., 2021. Unified Combinatorial Interaction Testing (U-CIT). PhD thesis, Sabancı University, Istanbul, Turkey.
Nasser, A., Zamli, K.Z., Alsewari, A.R. and Ahmed, B., 2018. An elitist-flower pollination-based strategy for constructing sequence and sequence-less t-way test suite, International Journal of Bio-Inspired Computation, 12(2), pp. 115–127. https://doi.org/10.1504/IJBIC.2018.094223
Nayeri, M., Colbourn, C.J. and Konjevod, G., 2013. Randomized post-optimization of covering arrays. European Journal of Combinatorics, 34(1), pp. 91–103. https://doi.org/10.1016/j.ejc.2012.07.017
Nie, C. and Leung, H., 2011. A survey of combinatorial testing. ACM Computing Surveys, 43(2), pp. 11:1–11:29. https://doi.org/10.1145/1883612.1883618
Petke, J., Cohen, M., Harman, M. and Yoo, S., 2015. Practical combinatorial interaction testing: Empirical Findings on Efficiency and Early Fault Detection. IEEE Transactions on Software Engineering, 41(9), pp. 901–924. https://doi.org/10.1109/TSE.2015.2421279
Rahman, M.M., Sultana, D., Khatun, S. and Mat Jusof, M.F., 2020. T-way strategy for sequence input interaction test case generation adopting fish swarm algorithm. In: Nasir, A.N.K. et al. (eds.), InECCE2019. Lecture Notes in Electrical Engineering, vol. 632. Singapore: Springer, pp. 87–99. https://doi.org/10.1007/978-981-15-2317-5_9
Sabharwal, S., Bansal, P. and Mittal, N., 2016. Construction of t-way covering arrays using genetic algorithm. International Journal of System Assurance Engineering and Management, 8, pp. 264–274. https://doi.org/10.1007/s13198-016-0430-6
Salehi, H., Gorodetsky, A., Solhmirzaei, R. and Jiao, P., 2023. High-dimensional data analytics in civil engineering: A review on matrix and tensor decomposition. Engineering Applications of Artificial Intelligence, 125, 106659. https://doi.org/10.1016/j.engappai.2023.106659
Sheng, Y., Sun, C., Jiang, S. and Wei, C., 2018. Extended covering arrays for sequence coverage, Symmetry, 10(5), P. 146. https://doi.org/10.3390/sym10050146
Torbunova, A., Strandberg, P.E. and Porres, I., 2024. Dynamic test case prioritization in industrial test result datasets. In: Proceedings of the 5th ACM/IEEE International Conference on Automation of Software Test (AST 2024), Lisbon, Portugal, pp. 154–158. https://doi.org/10.1145/3644032.3644452
Torres-Jimenez, J. and Rodriguez-Tello, E., 2012. New bounds for binary covering arrays using simulated annealing. Information Sciences, 185(1), pp. 137–152. https://doi.org/10.1016/j.ins.2011.09.020
Witharana, H., Jayasena, A. and Mishra, P., 2024. Incremental concolic testing of register-transfer level designs. ACM Transactions on Design Automation of Electronic Systems, 29(3), pp.1–23. https://doi.org/10.1145/3655621
Yang, J., Fu, C., Deng, F., Wen, M., Guo, X. and Wan, C., 2023. Toward interpretable graph tensor convolution neural network for code semantics embedding. ACM Transactions on Software Engineering and Methodology, 32(5), Article 115, pp.115:1–115:40. https://doi.org/10.1145/3582574
Younis, M.I., 2020. DEO: A dynamic event order strategy for t-way sequence covering array test data generation. Baghdad Science Journal, 17(2), pp. 575–582. https://doi.org/10.21123/bsj.2020.17.2.0575
Zabil, M.H.M., Zamli, K.Z. and Lim, K.C., 2018. Evaluating Bees algorithm for sequence-based t-way testing test data generation, Indian Journal of Science and Technology, 11(4), pp. 1–20. https://doi.org/10.17485/ijst/2018/v11i4/121086
Zamli, K. and Kader, M., 2021. Sequence t-way test generation using the Barnacles Mating Optimizer algorithm. In: Proceedings of the 10th International Conference on Software and Computer Applications (ICSCA 2021), Kuala Lumpur, Malaysia, pp. 88–93. https://doi.org/10.1145/3457784.3457797
Zeng, M.-F., 2016. Generating Covering Arrays Using Ant Colony Optimization: Exploration and Mining. Journal of Software, 27(4), pp. 855–878. https://doi.org/10.13328/j.cnki.jos.004974