Improved pairwise test suites for non-prime-power orders
- Author(s): Himer Avila-George 1 ; Jose Torres-Jimenez 2 ; Idelfonso Izquierdo-Marquez 2
-
-
View affiliations
-
Affiliations:
1:
Unidad de Transferencia Tecnológica Tepic , CONACYT-CICESE , Tepic, Nayarit , Mexico ;
2: Information Technology Laboratory , CINVESTAV-Tamaulipas , Ciudad Victoria, Tamaulipas , Mexico
-
Affiliations:
1:
Unidad de Transferencia Tecnológica Tepic , CONACYT-CICESE , Tepic, Nayarit , Mexico ;
- Source:
Volume 12, Issue 3,
June
2018,
p.
215 – 224
DOI: 10.1049/iet-sen.2017.0107 , Print ISSN 1751-8806, Online ISSN 1751-8814
Software testing has become a critical component of the modern software development process. Therefore, a lot of research has been done in this area in recent years, and as a result new algorithms, methodologies, and tools have been created. One of the most used testing strategies is pairwise testing; this technique ensures that all possible combinations of values between any two input parameters are covered by at least one test. In this work, a new algorithm called add factor and stochastic optimisation (AFSO) is used to build small pairwise test suites for non-prime-power orders. Starting from an orthogonal array of order , AFSO iteratively adds a factor and then reduces to zero the number of uncovered combinations by means of a simulated annealing algorithm. The results of the AFSO algorithm improved the size of 92 pairwise test suites with non-prime-power orders. One of these improved test suites is used in a real-word application to show the usefulness of the new results.
Inspec keywords: simulated annealing; program testing; domain boundaries
Other keywords: improved pairwise test suites; nonprime-power orders; result new algorithms; real-world test suites; simulated annealing algorithm; \lcub 10\comma; testing strategies; software testing; modern software development process
Subjects: Diagnostic, testing, debugging and evaluating systems; Combinatorial mathematics; Optimisation techniques; Software engineering techniques; Other topics in statistics
References
-
-
1)
-
6. Dalal, S.R., Jain, A., Karunanithi, N., et al: ‘Model-based testing in practice’. Proc. 21st Int. Conf. Software Engineering, Los Angeles, California, USA, May 1999, pp. 285–294.
-
-
2)
-
43. Cohen, M.B., Dwyer, M.B., Shi, J.: ‘Interaction testing of highly-configurable systems in the presence of constraints’. Proc. 2007 Int. Symp. Software Testing and Analysis, London, UK, July 2007, pp. 129–139.
-
-
3)
-
14. Ronneseth, A.H., Colbourn, C.J.: ‘Merging covering arrays and compressing multiple sequence alignments’, Discrete Appl. Math., 2009, 157, (9), pp. 2177–2190.
-
-
4)
-
47. Younis, M.I., Zamli, K.Z.: ‘MIPOG - an efficient t-way minimization strategy for combinatorial testing’, Int. J. Comput. Theory Eng., 2011, 3, (3), pp. 388–397.
-
-
5)
-
24. Avila-George, H., Torres-Jimenez, J., Rangel-Valdez, N., et al: ‘Supercomputing and grid computing on the verification of covering arrays’, J. Supercomputing, 2012, 62, (2), pp. 916–945.
-
-
6)
-
28. Todorov, D.T.: ‘Four mutually orthogonal Latin squares of order 14’, J. Comb. Des., 2012, 20, (8), pp. 363–367.
-
-
7)
-
40. Colbourn, C.J.: ‘Augmentation of covering arrays of strength two’, Graphs Comb., 2015, 31, (6), pp. 2137–2147.
-
-
8)
-
4. Shasha, D.E., Kouranov, A.Y., Lejay, L.V., et al: ‘Using combinatorial design to study regulation by multiple input signals: a tool for parsimony in the post-genomics era’, Plant Physiol., 2001, 127, (4), pp. 1590–1594.
-
-
9)
-
20. Torres-Jimenez, J., Rodriguez-Tello, E.: ‘New bounds for binary covering arrays using simulated annealing’, Inf. Sci., 2012, 185, (1), pp. 137–152.
-
-
10)
-
7. Wallace, D.R., Kuhn, D.R.: ‘Failure modes in medical device software: an analysis of 15 years of recall data’, Int. J. Reliab. Qual. Safety Eng., 2001, 8, (4), pp. 351–371.
-
-
11)
-
29. Schellenberg, P.J., Van Rees, G.H.J., Vanstone, S.A.: ‘Four pairwise orthogonal Latin squares of order 15’, Ars Combinatoria, 1978, 6, pp. 141–150.
-
-
12)
-
37. Colbourn, C.J., Martirosyan, S.S., Mullen, G.L., et al: ‘Products of mixed covering arrays of strength two’, J. Comb. Des., 2006, 12, (2), pp. 124–138.
-
-
13)
-
34. Abel, R.J.R., Zhang, X., Zhang, H.: ‘Three mutually orthogonal idempotent Latin squares of orders 22 and 26’, J. Stat. Plan. Inference, 1996, 51, (2), pp. 101–106.
-
-
14)
-
45. Yan, J., Zhang, J.: ‘A backtracking search tool for constructing combinatorial test suites’, J. Syst. Softw., 2008, 81, (10), pp. 1681–1693.
-
-
15)
-
27. Johnson, D.M., Dulmage, A.L., Mendelsohn, N.S.: ‘Orthomorphisms of groups and orthogonal Latin squares’, Can. J. Math., 1961, 13, pp. 356–372.
-
-
16)
-
9. Sarkar, K., Colbourn, C.J., de Bonis, A., et al: ‘Partial covering arrays: algorithms and asymptotics’. Int. Workshop on Comb. Algorithms, Helsinki, Finland, August 2016, pp. 437–448.
-
-
17)
-
8. Godbole, A.P., Skipper, D.E., Sunley, R.A.: ‘t-covering arrays: upper bounds and Poisson approximations’, Comb. Probab. Comput., 1996, 5, (2), pp. 105–117.
-
-
18)
-
5. Vadde, K.K., Syrotiuk, V.R.: ‘Factor interaction on service delivery in mobile ad hoc networks’, IEEE J. Sel. Areas Commun., 2004, 22, (7), pp. 1335–1346.
-
-
19)
-
36. Developers, T.: ‘The SAGE mathematics software system (version 7.1)’ (SageMath, 2016).
-
-
20)
-
15. Younis, M.I., Zamli, K.Z., Klaib, M.F.J., et al: ‘Assessing IRPS as an efficient pairwise test data generation strategy’, Int. J. Adv. Intell. Paradigms, 2010, 2, (1), pp. 90–104.
-
-
21)
-
35. Abel, R.J.R., Colbourn, C.J., Wojtas, M.: ‘Concerning seven and eight mutually orthogonal Latin squares’, J. Comb. Des., 2004, 12, (2), pp. 123–131.
-
-
22)
-
25. Avila-George, H., Torres-Jimenez, J., Gonzalez-Hernandez, L., et al: ‘Metaheuristic approach for constructing functional test-suites’, IET Softw., 2013, 7, (2), pp. 104–117.
-
-
23)
-
3. Chen, C.H., Shiou, F.J.: ‘Determination of optimal ball-burnishing parameters for plastic injection moulding steel’, Int. J. Adv. Manuf. Technol., 2003, 21, (3), pp. 177–185.
-
-
24)
-
18. Bryce, R.C., Colbourn, C.J.: ‘The density algorithm for pairwise interaction testing’, Softw. Test. Verif. Reliab., 2007, 17, (3), pp. 159–182.
-
-
25)
-
30. Abel, R.J.R.: ‘Existence of five MOLS of orders 18 and 60’, J. Comb. Des., 2015, 23, (4), pp. 135–139.
-
-
26)
-
22. Sherwood, G.B.: ‘Getting the most from pairwise testing: a guide for practicing software engineers’, Testcover, 2011.
-
-
27)
-
23. Tarry, G.: ‘Le problème des 36 officiers’, Compte Rendu de l'Association Française pour l'Avancement de Science Naturel, 1901, 29, (2), pp. 170–203.
-
-
28)
-
39. Quiz-Ramos, P., Torres-Jimenez, J., Rangel-Valdez, N.: ‘Constant Row maximizing problem for covering arrays’. Proc. Eighth Mexican Int. Conf. Artificial Intelligence, Guanajuato, Mexico, February 2009, pp. 159–164.
-
-
29)
-
13. Colbourn, C.J.: ‘Strength two covering arrays: existence tables and projection’, Discrete Math., 2008, 308, (5), pp. 772–786.
-
-
30)
-
19. Cohen, M.B., Colbourn, C.J., Ling, A.C.H.: ‘Augmenting simulated annealing to build interaction test suites’. Proc. 14th Int. Symp. Software Reliability Engineering, Denver, CO, USA, November 2003, pp. 394–405.
-
-
31)
-
11. Bush, K.A.: ‘Orthogonal arrays of index unity’, Ann. Math. Stat., 1952, 23, (3), pp. 426–434.
-
-
32)
-
16. Calvagna, A., Gargantini, A.: ‘T-wise combinatorial interaction test suites construction based on coverage inheritance’, Softw. Test. Verif. Reliab., 2012, 22, pp. 507–526.
-
-
33)
-
42. Kuhn, D.R., Okun, V.: ‘Pseudo-exhaustive testing for software’. Proc. 30th Annual IEEE/NASA Software Engineering Workshop, Columbia, MD, USA, April 2006, pp. 153–158.
-
-
34)
-
50. Torres-Jimenez, J., Rodriguez-Cristerna, A.: ‘Metaheuristic post-optimization of the NIST repository of covering arrays’, CAAI Trans. Intell. Technol., 2017, 2, (1), pp. 31–38.
-
-
35)
-
10. Francetić, N., Stevens, B.: ‘Asymptotic size of covering arrays: an application of entropy compression’, J. Comb. Des., 2017, 25, (6), pp. 243–257.
-
-
36)
-
31. Todorov, D.T.: ‘Four mutually orthogonal Latin squares of order 20’, Ars Combinatoria, 1989, 27, pp. 63–65.
-
-
37)
-
17. Lei, Y., Tai, K.C.: ‘In-parameter-order: a test generation strategy for pairwise testing’. Proc. 3rd IEEE Int. Symp. High-Assurance Systems Engineering, Washington, DC, USA, August 1998, pp. 254–261.
-
-
38)
-
44. Cohen, M.B., Dwyer, M.B., Shi, J.: ‘Constructing interaction test suites for highly-configurable systems in the presence of constraints: A greedy approach’, IEEE Trans. Softw. Eng., 2008, 34, (5), pp. 633–650.
-
-
39)
-
38. Colbourn, C.J., Torres-Jimenez, J.: ‘Heterogeneous hash families and covering arrays’, Contemp. Math., 2010, 523, pp. 3–15.
-
-
40)
-
21. Nurmela, K.J.: ‘Upper bounds for covering arrays by tabu search’, Discrete Appl. Math., 2004, 138, pp. 143–152.
-
-
41)
-
41. Smith, B., Millar, W., Dunphy, J., et al: ‘Validation and verification of the remote agent for spacecraft autonomy’. IEEE Aerospace Conf., Snowmass at Aspen, CO, USA, August 1999, pp. 449–468.
-
-
42)
-
48. Ahmed, B.S., Zamli, K.Z., Lim, C.P.: ‘Application of particle swarm optimization to uniform and variable strength covering array construction’, Appl. Soft Comput., 2012, 12, (4), pp. 1330–1347.
-
-
43)
-
49. Hillmer, D.: ‘Introducing combinatorial testing in the organization a report on a first attempt’. IEEE Eighth Int. Conf. Software Testing, Verification and Validation Workshops, Graz, Austria, May 2015, pp. 1–9.
-
-
44)
-
32. Abel, R.J.R., Todorov, D.T.: ‘Four MOLS of orders 20, 30, 38, and 44’, J. Comb. Theory A, 1993, 64, (1), pp. 144–148.
-
-
45)
-
2. Yang, P., Tan, X., Sun, H., et al: ‘Fire accident reconstruction based on LES field model by using orthogonal experimental design method’, Adv. Eng. Softw., 2011, 42, (11), pp. 954–962.
-
-
46)
-
33. Nazarok, A.V.: ‘Five pairwise orthogonal Latin squares of order 21’, Issled. oper. i ASU, 1991, 1, pp. 54–56.
-
-
47)
-
12. Colbourn, C.J., Kéri, G., Rivas Soriano, P.P., et al: ‘Covering and radius-covering arrays: constructions and classification’, Discrete Appl. Math., 2010, 158, (11), pp. 1158–1180.
-
-
48)
-
1. Kuhn, D.R., Kacker, R.N., Lei, Y.: ‘Practical combinatorial testing’ (National Institute of Standards & Technology, Gaithersburg, MD, USA, 2010).
-
-
49)
-
46. Segall, I., Tzoref-Brill, R., Farchi, E.: ‘Using binary decision diagrams for combinatorial test design’. Proc. 2011 Int. Symp. Software Testing and Analysis, Toronto, ON, Canada, July 2011, pp. 254–264.
-
-
50)
-
26. Parker, E.T.: ‘Orthogonal Latin squares’, Proc. Natl. Acad. Sci., 1959, 45, (6), pp. 859–862.
-
-
1)