استفاده از الگوریتم توده ذرات بهینه در تولید دنباله آزمون کمینه در آرایه پوشش با قوه ثابت

نویسندگان

دانشگاه اراک

چکیده

تاکنون، تعداد زیادی الگوریتم مفید برای تولید آرایه پوشش که یکی از شاخه های آزمون ترکیبی ست، ارایه شده است. اصلی ترین چالشدر تولید چنین آرایه هایی، تولید آرایه با تعداد نمونه آزمون کمینه (بهره وری) در زمان مناسب (کارایی)، برای سیستم های بزرگ است. استراتژی های تولید آرایه پوشش قالبا به دو دسته کلی محاسباتی و فرامکاشفه ای تقسیم می شوند. استراتژی های محاسباتی معمولا کارایی بالایی دارند اما از نظر بهره وری نتایج ضعیفی را تولید می کند و استراتژی های فرامکاشفه ای از بهره وری مناسب و کارایی ضعیفی برخوردار هستند. در بین استراتژی های در دسترس استراتژی DPSO از نظر بهره وری بهترین نتایج را دارد، اما کارایی مناسبی ندارد و استراتژی GS کارایی مناسبی را دارد اما بهره وری مناسبی ندارد. در حالت کلی استراتژی که کارایی و بهره وری را توامان داشته باشد، به چشم نمی خورد. در این مقاله ما سعی کردیم با استفاده از توده ذرات دنباله آزمون مناسب را از نظر بهره وری و کارایی، تولید کنیم. همچنین برای افزایش بهره وری از یک تابع کمینه ساز ساده و تاثیرگذار استفاده شده است. نتایج ارزیابی نشان می دهد که راهکار پیشنهادی از نظر کارایی و بهره وری نتایج مطلوب دارد.

کلیدواژه‌ها


عنوان مقاله [English]

Using the Particle Swarm Optimization Algorithm to Generate the Minimum Test Suite in Covering Array with Uniform Strength

نویسندگان [English]

  • sajad esfandyari
  • vahid rafe
چکیده [English]

Up to now, several useful algorithms have been proposed to generate covering array, which is one of the branches of combinatorial testing. The main challenge in generating such arrays is generation of the arrays with a minimum number of test cases (for efficiency) at a proper time (for performance), for large systems. Covering array generation strategies are often divided into two general categories: computational and meta-heuristic. Computational strategies usually benefit high performance but have poor results in terms of efficiency. On the other hand, meta-heuristic strategies enjoy good efficiency but suffer low performance. Among the available strategies, the DPSO strategy generates the best results in terms of efficiency, but it does not benefit high performance; in contrast the GS strategy benefits good performance but has not good efficiency. Generally, there is no strategy that is good in terms of both efficiency and performance. In this paper, we try to produce an appropriate test suite of high efficiency and performance using PSO. A simple and effective minimizer function has also been used to increase the efficiency. The evaluation results show that the proposed solution has desirable outcomes in terms of efficiency and performance.

کلیدواژه‌ها [English]

  • Combinatorial testing
  • Test suit generation
  • Covering array
  • PSO
  1. A. Alsewari, Abdul Rahman, و Kamal Z. Zamli. “Design and implementation of a harmony-search-based variable-strengtht-way testing strategy with constraints support.” Information and Software Technology 54, شماره 6 (2012): 553–568. Arshem, J. TVG download page. 2019. http://sourceforge.net/projects/tvg. Bryce, Renée C., و Charles J. Colbourn. “The density algorithm for pairwise interaction testing: Research Articles.” Software Testing, Verification & Reliability 17, شماره 3 (2007): 159 - 182 . Bryce, Renée, و Charles J. Colbourn. “A density-based greedy algorithm for higher strength covering arrays.” Software Testing Verification and Reliability 17, شماره 1 (2009): 37-53. Calvagna, Andrea, و Angelo Gargantini. “IPO-s: incremental generation of combinatorial interaction test data based on symmetries of covering arrays.” International Conference on Software Testing, Verification, and Validation Workshops. Denver, CO, USA, 2009. Cohen, M, B. Designing Test Suites for Software Interactions Testing. PHD Thesis, University of Auckland,Department of Computer Science ,Auckland,, 2004. Cohen, Myra B., Matthew B. Dwyer, and Jiangfan Shi. "Interaction testing of highly-configurable systems in the presence of constraints." international symposium on Software testing and analysis. London, United Kingdom, 2007. 129-139. Czerwonka, J. "Pairwise testing in real world: practical extensions to test case generator." 24th Pacific Northwest Software Quality Conference, IEEE Computer Society. Portland, OR, USA, 2006. Esfandyari, Sajad, and Vahid Rafe. "A tuned version of genetic algorithm for efficient test suite generation in interactive t-way testing strategy." Information and Software Technology 94 (2018): 165-185. Hartman, A. IBM Intelligent Test Case Handler. IBM alphaworks. 2019. http://www.alphaworks.ibm.com/tech/whitch. Jenkins, Bob. Jenny download web page. Bob Jenkins’ Website. 2019. http://burtleburtle.net/bob/math/jenny.html. Kennedy, Jim, و Russell Eberhart. “Particle swarm optimization.” International Conference on Neural Networks. Perth, WA, Australia, Australia: IEEE, 1995. Kuhn, Rick. ACTS page download. 2019. http://csrc.nist.gov/groups/SNS/acts/download_tools.html. Lehmann, Eckard, and Joachim Wegener. "Test case design by means of the CTE XL." 8th European International Conference on Software Testing, Analysis & Review. Copenhagen, Denmark, 2000. 1-10. Lei, Y, R Kacker, D, R Kuhn, V Okun, و J Lawrence. “IPOG: a general strategy for t-way software testing.” 4th Annual IEEE International Conference and Workshops on the Engineering of Computer-Based Systems, IEEE Computer Society. Tucson, AZ, 2007. 549–556. Lei, Yu, Raghu Kacker, D, Richard Kuhn, Vadim Okun, and James Lawrence. "IPOG/IPOG-D: efficient test generation for multi-way combinatorial testing, Software Testing." Software Testing, Verification & Reliability 18, no. 3 (2008): 125-148. Lin, Jinkun, Chuan Luo, Shaowei Cai, Kaile Su, Dan Hao, and Lu Zhang. "TCA: An Efficient Two-Mode Meta-Heuristic Algorithm for Combinatorial Test Generation (T)." 30th IEEE/ACM International Conference on Automated Software Engineering (ASE). Lincoln, NE, USA: IEEE, 9-13 Nov. 2015. M. Cohen, D, S R. Dalal, M L. Fredman, and G C. Patton. "The AETG system: an approach to testing based on combinatorial design." IEEE Transactions on Software Engineering 23, no. 7 (1997): 437 - 444. Rafe, Vahid. "Scenario-driven analysis of systems specified through graph transformations." (J. Visual Lang. Comput) 24 (2013): 136–145. S. Ahmed, Bestoun, Kamal Z. Zamli, and Chee PengLim. "Application of Particle Swarm Optimization to uniform and variable strength covering array construction." Applied Soft Computing 12, no. 4 (2012): 1330–1347. S. Ahmed, Bestoun, Taib Sh. Abdulsamad, and Moayad Y. Potrus. "Achievement of minimized combinatorial test suite for configuration-aware software functional testing using the Cuckoo Search algorithm." Information and Software Technology 66 (2015): 13–29. Shiba, Toshiaki, Tatsuhiro Tsuchiya, and Tohru Kikuno. "Using artificial life techniques to generate test cases for combinatorial testing." 28th Annual International Computer Software and Applications Conference. Hong Kong, China, 2004. Stardom, John. "Metaheuristics and the Search for Covering and Packing Array." Thesis (M.Sc.), Simon Fraser University, 2001, 2001. Tung, Yu,-Wen, و W.S. Aldiwan. “Automating test case generation for the new generation mission software system.” 2000 IEEE Aerospace Conference. Proceedings (Cat. No.00TH8484). Big Sky, MT, USA, USA, 2000. Wu, Huayao, Changhai Nie, Fei-Ching Kuo, Hareton Leung, and Charles J. Colbourn. "A Discrete Particle Swarm Optimization for Covering Array Generation." IEEE Transactions on Evolutionary Computation 19, no. 4 (2015): 575-591. Wu, Huayao, Changhai Nie, Fei-Ching Kuo, Hareton Leung, و Charles J. Colbourn. DPSO Page Download. 2015. https://github.com/waynedd/DPSO (دستیابی در 2019). Yu, Y.T., S.P. Ng, و E.Y.K. Chan. “Generating, selecting and prioritizing test cases from specifications with tool support.” Third International Conference on Quality Software. Dallas, TX, USA, USA, 2003. Z.Zamli, Kamal, FakhrudDin, GrahamKendall, و Bestoun S.Ahmed. “An Experimental Study of Hyper-Heuristic Selection and Acceptance Mechanism for Combinatorial t-way Test Suite Generation.” Information Sciences 399 (2017): 121-153. Kuhn, D. Richard; Kacker, Raghu N.; Lei, Yu, " Introduction to Combinatorial Testing", Chapman & Hall/CRC Innovations in Software Engineering and Software Development Series, CRC Press, 2013.