Construct Pairwise Test Suites Based on the Bak-Sneppen Model of Biological Evolution
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.
[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.
[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.
@article{"International Journal of Information, Control and Computer Sciences:51834", author = "Jianjun Yuan and Changjun Jiang", title = "Construct Pairwise Test Suites Based on the Bak-Sneppen Model of Biological Evolution", 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.", volume = "3", number = "11", pages = "2538-6", }
