Construct Pairwise Test Suites Based on the Bak-Sneppen Model of Biological Evolution

Authors: Jianjun Yuan, Changjun Jiang

Abstract:

Pairwise testing, which requires that every combination of valid values of each pair of system factors be covered by at lease one test case, plays an important role in software testing since many faults are caused by unexpected 2-way interactions among system factors. Although meta-heuristic strategies like simulated annealing can generally discover smaller pairwise test suite, they may cost more time to perform search, compared with greedy algorithms. We propose a new method, improved Extremal Optimization (EO) based on the Bak-Sneppen (BS) model of biological evolution, for constructing pairwise test suites and define fitness function according to the requirement of improved EO. Experimental results show that improved EO gives similar size of resulting pairwise test suite and yields an 85% reduction in solution time over SA.

Keywords: Covering Arrays, Extremal Optimization, Simulated Annealing, Software Testing.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1057745

References:

[1] K. C. Tai and Y. Lei, "A test generation strategy for pairwise testing," IEEE Transactions on Software Engineering, vol. 28, pp. 109-111, January 2002.
[2] D. M. Cohen, 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, vol. 23, pp. 437-444, July 1997.
[3] D. R. Kuhn, D. R. Wallace, and A. M. Gallo, "Software fault interactions and implications for software testing," IEEE Transactions on Software Engineering, vol. 30, pp. 418-421, June 2004.
[4] S. R. Dalal et al. "Model-based testing in practice," in Proceedings of the International Conference on Software Engineering, pp. 285-294, 1999.
[5] C. J. Colbourn, M. B. Cohen, and R. C. Turban, "A deterministic density algorithm for pairwise interaction coverage," in Proceedings of IASTED International Conference on Software Engineering, pp. 345-352, 2004.
[6] Y. Lei, R. Kacker, D. R. Kuhn, V. Okun, and J. Lawrence, "IPOG: a general strategy for t-way software testing," in Proceedings of IEEE International Conference on the Engineering of Computer-Based Systems, pp. 549-556, 2007.
[7] L. Yu and K. C. Tai, "In-parameter-order: a test generation strategy for pairwise testing," in Proceedings of the 3rd IEEE International High-Assurance Systems Engineering Symposium, pp. 254-261, 1998.
[8] M. B. Cohen, P. B. Gibbons, W. B. Mugridge, and C. J. Colbourn, "Constructing test suites for interaction testing," in Proceedings of the 25th International Conference on Software Engineering, pp. 38-48, 2003.
[9] J. Stardom, "Metaheuristics and the search for covering and packing arrays," Master dissertation, Department of Mathematics, Simon Fraser University, Canada, 2001.
[10] B. Stevens, "Transversal covers and packings," Ph.D. dissertation, Department of Mathematics, University of Toronto, Canada, 1998.
[11] B. J. Garvin, M. B. Cohen, and M. B. Dwyer, "An improved meta-heuristic search for constrained interaction testing," in Proceedings of International Symposiumon Search-Based Software Engineering, pp. 13-22, 2009.
[12] S. Boettcher and A. G. Percus, "Extremal optimization: methods derived from co-evolution," in Proceedings of the Genetic and Evolutionary Computation Conference, pp. 825-832, 1999.
[13] P. Bak and K. Sneppen, "Punctuated equilibrium and criticality in a simple model of evolution," Physical Review Letters, Vol. 71, pp. 4083-4086, December 1993.
[14] M. Martin, E. Drucker, and W. D. Potter, "Genetic algorithm, extremal optimization, and particle swarm optimization applied to the discrete network configuration problem," in Proceedings of International Conference on Genetic and Evolutionary Methods, pp. 129-134, 2008.
[15] R. Brownlie, J. Prowse, and M. S. Padke, "Robust testing of AT&T PMX/StarMAIL using OATS," AT&T Technical Journal, vol. 71, pp. 41-47, May 1992.
[16] R. Mandl, "Orthogonal latin squares: an application of experiment design to compiler testing," Communications of the ACM, vol. 28, pp. 1054-1058, October 1985.
[17] T. W. Tung and W. S. Aldiwan, "Automating test case generation for the new generation mission software system," in Proceedings of IEEE Aerospace Conference, pp. 431-437, 2000.
[18] K. Nurmela, "Upper bounds for covering arrays by tabu search," Discrete Applied Mathematics, vol. 138, pp. 143-152, March 2004.
[19] S. A. Ghazi and M. A. Ahmed, "Pair-wise test coverage using genetic algorithms," in Proceedings of Congress on Evolutionary Computation, pp. 1420-1424, 2003.
[20] S. Boettcher and A. G. Percus, "Extremal optimization for graph partitioning," Physical Review E, vol. 64, pp. 1-13, July 2001.
[21] M. B. Cohen, "Designing test suites for software interaction testing," Ph.D. dissertation, Department of Computer Science, The University of Auckland, New Zealand, 2004.
[22] S. Boettcher and A. G. Percus, "Optimizing through co-evolutionary avalanches," Lecture Notes in Computer Science, vol. 1917, pp. 447-456, 2000.
[23] S Boettcher and M. Grigni, "Jamming model for the extremal optimization heuristic," Journal of Physics A-Mathematical and General, vol. 35, pp. 1109-1123, January 2002.
[24] C. Wohlin et al., Experimentation in software engineering: an introduction, Kluwer Academic Publishers, Norwell, MA, USA, 2000.