تسريع توليد وتحسين مصفوفات التغطية المتسلسلة باستخدام التقييم التفاضلي والمعالجة المتوازية
محتوى المقالة الرئيسي
الملخص
تعتبر مصفوفات التغطية المتسلسلة (SCAs) من أهم التراكيب المستخدمة في اختبار التوافقية للتحقق من الأنظمة التي يعتمد فيها سلوكها على تسلسل الأحداث إذ تضمن ظهور جميع التفاعلات المرتبة ذات القوة t (درجة التفاعل) ضمن تسلسل اختبار واحد على الأقل. وبالرغم من قوة ضمان التغطية التي توفرها، إلا أن استخدامها في التطبيقات العملية ما زال مقصورًا بسبب الزمن الطويل اللازم لبنائها وتحسينها.
يقوم هذا البحث بتقديم إطار لتسريع بناء مصفوفات التغطية المتسلسلة من خلال تطبيق تقنيات تحسين الاداء على مراحل التوليد والمعالجة.
الهدف من هذا العمل هو تقليل زمن التنفيذ باستخدام توازي المعالجات وتقليل العمليات الزائدة داخل خط التنفيذ.
يعتمد الإطار المقترح على استخدام ثلاث تقنيات رئيسية وهي: التقييم التفاضلي لإزالة العمليات الزائدة، وتمثيل بيانات التغطية باستخدام مصفوفات متعددة الأبعاد لتقليل الأحمال الحسابية، والمعالجة المتوازية للتوزيع على عدة نوى من معالج الحاسوب. تم تطبيق هذه التقنيات الثلاثة على مرحلتي التوليد والتحسين مع ضمان صحة التغطية.
أظهرت النتائج التجريبية للأبحاث تحسنًا كبيرًا في أداء جميع الإعدادات التي تم اختبارها، فعلى سبيل المثال، انخفض زمن تنفيذ المرحلة الثانية من 2569 ثانية في إعداد البناء الأساسي إلى 379 ثانية عند تطبيق التسريع ثم الى 30.6 ثانية في الإصدار المتسارع– الموازي، وبالتالي تحسّنت السرعة الكلية بأكثر من 80 ضعفًا. تشير النتائج التجريبية في هذا البحث إلى صحة افتراض أن بناء مصفوفات التغطية المتسلسلة ذات الرتب العالية يمكن جعله عملي للاستخدام في إصدارات البرمجيات المستمرة وبيئات تطوير البرمجيات الحديثة.
##plugins.themes.bootstrap3.displayStats.downloads##
تفاصيل المقالة
القسم
كيفية الاقتباس
المراجع
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
