Improved Mixed Neighborhood Tabu Search by Random Selection for Combinatorial Interaction Testing
Combinatorial interaction testing (CIT) is a technique used to find minimal test suite among configuration options of a System Under Test (SUT) that uses a Covering Array (CA) as a combinatorial structure. CIT is very effective for reducing the costs of the testing process that uses a sampling technique instead of exhaustive testing. This paper proposes the modification of Mixed Neighborhood Tabu Search (RMiTS) algorithm using the random selection strategy. The base MiTS algorithm is originally used for generating t-way Mixed Covering Array (MCA). The modification improves the algorithm performance (running time) to cover all possible input configuration combinations to produce the optimal or near-optimal test suites. The modified algorithm is evaluated through a comparison against the base MiTS algorithm to confirm the performance improvements. Also, it is compared to a state-of-the-art algorithm known as Advanced Combinatorial Test Tool (ACTS) to confirm its efficiency. The experimental results confirm the effectiveness of the modifications that improved the performance for all applied benchmarks, and also it shows that RMiTS is more efficient than ACTS.
Ahmed, B. S. et al. (2017) ‘Handling constraints in combinatorial interaction testing in the presence of multi objective particle swarm and multithreading’, Information and Software Technology. Elsevier, 86, pp. 20–36. doi: 10.1016/J.INFSOF.2017.02.004.
Ahmed, B. S. and Zamli, K. Z. (2011) ‘A variable strength interaction test suites generation strategy using Particle Swarm Optimization’, Journal of Systems and Software, 84(12), pp. 2171–2185. doi: 10.1016/j.jss.2011.06.004.
Ahmed, B. S., Zamli, K. Z. and Lim, C. P. (2012) ‘Constructing a t-way interaction test suite using the particle swarm optimization approach’, International Journal of Innovative Computing, Information and Control. ICIC International, 8(1), pp. 431–452.
Avila-George, H. et al. (2012) ‘Simulated Annealing for Constructing Mixed Covering Arrays’, in. Springer, Berlin, Heidelberg, pp. 657–664. doi: 10.1007/978-3-642-28765-7_79.
Bryce, R. C., Colbourn, C. J. and Cohen, M. B. (2005) ‘A framework of greedy methods for constructing interaction test suites’, in Proceedings of the 27th international conference on Software engineering - ICSE ’05. New York, New York, USA: ACM Press, p. 146. doi: 10.1145/1062455.1062495.
Cohen, D. M. et al. (1997) ‘The AETG system: an approach to testing based on combinatorial design’, IEEE Transactions on Software Engineering, 23(7), pp. 437–444. doi: 10.1109/32.605761.
Cohen, M. B., Gibbons, P. B., Mugridge, W. B., Colbourn, C. J., et al. (2003) ‘A variable strength interaction testing of components’, in 27th Annual International Computer Software and Applications Conference. COMPAC 2003. IEEE Comput. Soc, pp. 413–418. doi: 10.1109/CMPSAC.2003.1245373.
Cohen, M. B., Gibbons, P. B., Mugridge, W. B. and Colbourn, C. J. (2003) ‘Constructing test suites for interaction testing’, in 25th International Conference on Software Engineering, 2003. Proceedings. IEEE, pp. 38–48. doi: 10.1109/ICSE.2003.1201186.
Cohen, M. B., Colbourn, C. J. and Ling, A. C. H. (2003) ‘Augmenting simulated annealing to build interaction test suites’, in Proceedings - International Symposium on Software Reliability Engineering, ISSRE. IEEE, pp. 394–405. doi: 10.1109/ISSRE.2003.1251061.
Cohen, M. B., Dwyer, M. B. and Shi, J. (2007) ‘Interaction testing of highly-configurable systems in the presence of constraints’, in Proceedings of the 2007 international symposium on Software testing and analysis - ISSTA ’07. New York, New York, USA: ACM Press, p. 129. doi: 10.1145/1273463.1273482.
Ghazi, S. A. and Ahmed, M. A. (2003) ‘Pair-wise test coverage using genetic algorithms’, in 2003 Congress on Evolutionary Computation, CEC 2003 - Proceedings. IEEE, pp. 1420–1424. doi: 10.1109/CEC.2003.1299837.
Glover, F. (1986) ‘Future paths for integer programming and links to artificial intelligence’, Computers and Operations Research. Pergamon, 13(5), pp. 533–549. doi: 10.1016/0305-0548(86)90048-1.
Glover, F. (1998) ‘Tabu Search: A Tutorial’, Interfaces, 20(4), pp. 74–94. doi: 10.1287/inte.20.4.74.
Glover, F. and Laguna, M. (1999) TABU search. Kluwer Academic Publishers.
Gonzalez-Hernandez, L. (2015) ‘New bounds for mixed covering arrays in t-way testing with uniform strength’, Information and Software Technology. Elsevier, 59, pp. 17–32. doi: 10.1016/j.infsof.2014.10.009.
Gonzalez-Hernandez, L. and Torres-Jimenez, J. (2010) ‘MiTS: A new approach of tabu search for constructing mixed covering arrays’, in Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Springer, Berlin, Heidelberg, pp. 382–393. doi: 10.1007/978-3-642-16773-7_33.
Kalaee, A. and Rafe, V. (2016) ‘An Optimal Solution for Test Case Generation Using ROBDD Graph and PSO Algorithm’, Quality and Reliability Engineering International. John Wiley & Sons, Ltd, 32(7), pp. 2263–2279. doi: 10.1002/qre.1934.
Kuhn, D. R., Kacker, R. N. and Lei, Y. (Associate professor of computer science) (2013) Introduction to combinatorial testing. CRC Press. Available at: https://www.crcpress.com/Introduction-to-Combinatorial-Testing/Kuhn-Kacker-Lei/p/book/9781466552296 (Accessed: 19 January 2019).
Lei, Y. et al. (2007) ‘IPOG: A general strategy for T-way software testing’, in Proceedings of the International Symposium and Workshop on Engineering of Computer Based Systems. IEEE, pp. 549–556. doi: 10.1109/ECBS.2007.47.
Lei, Y. and Tai, K. C. (1998) ‘In-parameter-order: A test generation strategy for pairwise testing’, in Proceedings - 3rd IEEE International High-Assurance Systems Engineering Symposium, HASE 1998. IEEE Comput. Soc, pp. 254–261. doi: 10.1109/HASE.1998.731623.
Lin, J. et al. (2016) ‘TCA: An efficient two-mode meta-heuristic algorithm for combinatorial test generation’, in Proceedings - 2015 30th IEEE/ACM International Conference on Automated Software Engineering, ASE 2015. IEEE, pp. 494–505. doi: 10.1109/ASE.2015.61.
McCaffrey, J. D. (2009) ‘Generation of Pairwise Test Sets Using a Genetic Algorithm’, in 2009 33rd Annual IEEE International Computer Software and Applications Conference. IEEE, pp. 626–631. doi: 10.1109/COMPSAC.2009.91.
Nie, C. and Leung, H. (2011) ‘A survey of combinatorial testing’, ACM Computing Surveys. ACM, 43(2), pp. 1–29. doi: 10.1145/1883612.1883618.
Ploskas, N. et al. (2016) ‘Introduction to GPU programming in MATLAB’, GPU Programming in MATLAB. Morgan Kaufmann, pp. 71–107. doi: 10.1016/B978-0-12-805132-0.00004-7.
Schmidt, B. et al. (2018) ‘Compute Unified Device Architecture’, Parallel Programming. Morgan Kaufmann, pp. 225–285. doi: 10.1016/B978-0-12-849890-3.00007-1.
Yu, L. et al. (2013) ‘ACTS: A combinatorial test generation tool’, in Proceedings - IEEE 6th International Conference on Software Testing, Verification and Validation, ICST 2013. IEEE, pp. 370–375. doi: 10.1109/ICST.2013.52.
Copyright (c) 2020 Imad Hadi Hasan, Moayad Potrus
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
At Zanco Journal, we're dedicated to protecting your rights as an author, and ensuring that any and all legal information and copyright regulations are addressed. Whether an author is published with Zanco Journal or any other publisher, we hold ourselves and our colleagues to the highest standards of ethics, responsibility and legal obligation