Improved Mixed Neighborhood Tabu Search by Random Selection for Combinatorial Interaction Testing

Imad H. Hasan; Moayad Y. Potrus

doi:10.21271/ZJPAS.32.5.1

Authors

Imad H. Hasan Department of Software and Informatics Engineering, College of Engineering , Salahaddin University-Erbil, Kurdistan Region, Iraq.
Moayad Y. Potrus Department of Software and Informatics Engineering, College of Engineering , Salahaddin University-Erbil, Kurdistan Region, Iraq.

DOI:

https://doi.org/10.21271/ZJPAS.32.5.1

Keywords:

Combinatorial Interaction Testing, Covering Array, Combinatorial Optimization, Software Testing

Abstract

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.

References

AHMED, B. S. 2016. Test case minimization approach using fault detection and combinatorial optimization techniques for configuration-aware structural testing. Engineering Science and Technology, an International Journal, 19, 737-753.

AHMED, B. S., GAMBARDELLA, L. M., AFZAL, W. & ZAMLI, K. Z. 2017. Handling constraints in combinatorial interaction testing in the presence of multi objective particle swarm and multithreading. Information and Software Technology, 86, 20-36.

AHMED, B. S. & ZAMLI, K. Z. 2011. A variable strength interaction test suites generation strategy using Particle Swarm Optimization. Journal of Systems and Software, 84, 2171-2185.

AHMED, B. S., ZAMLI, K. Z. & 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, 8, 431-452.

AVILA-GEORGE, H., TORRES-JIMENEZ, J., HERNÁNDEZ, V. & GONZALEZ-HERNANDEZ, L. 2012. Simulated Annealing for Constructing Mixed Covering Arrays. Springer, Berlin, Heidelberg.

BRYCE, R. C., COLBOURN, C. J. & COHEN, M. B. A framework of greedy methods for constructing interaction test suites. 2005 New York, New York, USA. ACM Press, 146-146.

COHEN, D. M., DALAL, S. R., FREDMAN, M. L. & PATTON, G. C. 1997. The AETG system: an approach to testing based on combinatorial design. IEEE Transactions on Software Engineering, 23, 437-444.

COHEN, M. B., COLBOURN, C. J. & LING, A. C. H. Augmenting simulated annealing to build interaction test suites. 2003 2003a. IEEE, 394-405.

COHEN, M. B., DWYER, M. B. & SHI, J. Interaction testing of highly-configurable systems in the presence of constraints. 2007 2007 New York, New York, USA. ACM Press, 129-129.

COHEN, M. B., GIBBONS, P. B., MUGRIDGE, W. B. & COLBOURN, C. J. Constructing test suites for interaction testing. 2003 2003b. IEEE, 38-48.

COHEN, M. B., GIBBONS, P. B., MUGRIDGE, W. B., COLBOURN, C. J. & COLLOFELLO, J. S. A variable strength interaction testing of components. 2003 2003c. IEEE Comput. Soc, 413-418.

GHAZI, S. A. & AHMED, M. A. Pair-wise test coverage using genetic algorithms. 2003. IEEE, 1420-1424.

GLOVER, F. 1986. Future paths for integer programming and links to artificial intelligence. Computers and Operations Research, 13, 533-549.

GLOVER, F. 1998. Tabu Search: A Tutorial. Interfaces, 20, 74-94.

GLOVER, F. & 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, 59, 17-32.

GONZALEZ-HERNANDEZ, L. & TORRES-JIMENEZ, J. 2010. MiTS: A new approach of tabu search for constructing mixed covering arrays. 2010. Springer, Berlin, Heidelberg, 382-393.

KALAEE, A. & RAFE, V. 2016. An Optimal Solution for Test Case Generation Using ROBDD Graph and PSO Algorithm. Quality and Reliability Engineering International, 32, 2263-2279.

KUHN, D. R., KACKER, R. N. & LEI, Y. 2013. Introduction to combinatorial testing, CRC Press.

LEI, Y., KACKER, R., KUHN, D. R., OKUN, V. & LAWRENCE, J. 2007. IPOG: A general strategy for T-way software testing. 2007/03//. IEEE, 549-556.

LEI, Y. & TAI, K. C. 1998. In-parameter-order: A test generation strategy for pairwise testing. 1998/11//. IEEE Comput. Soc, 254-261.

LIN, J., LUO, C., CAI, S., SU, K., HAO, D. & ZHANG, L. TCA: An efficient two-mode meta-heuristic algorithm for combinatorial test generation. 2016/11// 2016. IEEE, 494-505.

MCCAFFREY, J. D. Generation of Pairwise Test Sets Using a Genetic Algorithm. 2009. IEEE, 626-631.

NIE, C. & LEUNG, H. 2011. A survey of combinatorial testing. ACM Computing Surveys, 43, 1-29.

PLOSKAS, N., SAMARAS, N., PLOSKAS, N. & SAMARAS, N. 2016. Introduction to GPU programming in MATLAB. GPU Programming in MATLAB, 71-107.

POTRUS, Y. M. 2016. Maintenance Scheduling Optimization for Electrical Grid Using Binary Gray Wolf Optimization Technique. ZANCO Journal of Pure and Applied Sciences, 28.

SCHMIDT, B., GONZÁLEZ-DOMÍNGUEZ, J., HUNDT, C., SCHLARB, M., SCHMIDT, B., GONZÁLEZ-DOMÍNGUEZ, J., HUNDT, C. & SCHLARB, M. 2018. Compute Unified Device Architecture. Parallel Programming, 225-285.

YU, L., LEI, Y., KACKER, R. N. & KUHN, D. R. ACTS: A combinatorial test generation tool. 2013/03//. IEEE, 370-375.