Cost-Efficient Mixed-Level Covering Designs for Testing Experiments

Yasmeen Akhtar1, Frederick Kin Hing Phoa2
1School of Computing, Informatics and Decision Systems Engineering, Arizona State University, Tempe, USA
2Institute of Statistical Science, Academia Sinica, Taipei, Taiwan

Tóm tắt

A covering design is a traditional class of experimental plans for hardware and software testing purposes. This paper presents a class of size-optimal covering designs for testing experiments with mixed-level factors. Among all the factors of different levels, one or two factors have a high number of levels while other factors form a full factorial so that all level combinations among factor pairs are “covered” at least once and appeared almost equally frequent. We use the coloring techniques for hypergraphs to construct such near-balanced mixed-level covering designs with the minimum run size.

Từ khóa


Tài liệu tham khảo

Akhtar Y, Maity S (2017) Mixed covering arrays on 3-uniform hypergraphs. Discrete Appl Math 232:8–22 Ang N (2015) Generating Mixed-Level Covering Arrays with λ = 2 and Test Prioritization, M.Sc. thesis, Arizona State University Baranyai Z (1975) On the factorization of the complete uniform hypergraph. In: Infinite and Finite Sets, Coll. Math. J. Bolyai, 10, Bolyai J. Mat. Tirsulat, Budapest, North Holland, Amsterdam, pp 91–108 Baranyai Z (1978) La coloration des arêtes des hypergraphes complets II. In: Problèmes Combinatoires et Théorie des Graphes, Coll. C.N.R.S. Orsay 1976, (Bermond, Fournier, Las Vergnas, Sotteau), C.N.R.S., Paris, pp 19–22 Baranyai Z (1979) The edge-coloring of complete hypergraphs I. J Comb Theory Ser B 26:276–294 Berge C (1989) Hypergraphs-combinatorics of finite sets, vol 45. Elsevier Science Publishers B.V, North-Holland Bryce RC, Colbourn CJ (2009) A density-based greedy algorithm for higher strength covering arrays. Softw Test Verif Reliab 19(1):37–53 Cohen DM, Dalal SR, Fredman ML, Patton GC (1997) The AETG system: an approach to testing based on combinatorial design. IEEE Trans Softw Eng 23(7):437–444 Cohen MB, Gibbons PB, Mugridge WB, Colbourn CJ (2003) Constructing test suites for interaction testing. In: 25th international conference on software engineering, proceedings, Portland, OR, USA, 38-48 Dalal SR, Mallows CL (1998) Factor-covering designs for testing software. Technometrics 40(3):234–243 Godbole AP, Skipper DE, Sunley RA (1996) t-covering arrays: upper bounds and Poisson approximations. Comb Probab Comput 5:105–118 Gromping U, Xu H (2014) Generalized resolution for orthogonal arrays. Ann Stat 42:918–939 Hedayat AS, Sloane NJA, Stufken J (1999) Orthogonal arrays, theory and applications, springer series in statistics. Springer, New York Kim Y, Jang DH, Anderson-Cook CM (2016) Graphical methods for evaluating covering arrays. Qual Reliab Eng Int 32:1467–1481 Kuhn DR, Reily M (2002) An investigation of the applicability of design of experiments to software testing. In: Proceedings of 27th annual NASA Goddard/IEEE software engineering workshop, pp 91-96 Kuhn DR, Kacker R, Lei Y (2013) Introduction to combinatorial testing. CRC Press, Boca Raton Li W, Nachtsheim CJ, Wang K, Reul R, Albrecht M (2013) Conjoint analysis and discrete choice experiments for quality improvement. J Qual Technol 45:74–99 Lin YL, Phoa FKH, Kao MH (2017) Optimal design of fMRI experiments using circulant (almost-)orthogonal arrays. Ann Stat 45:2483–2510 Meagher K (2005) Covering arrays on graphs: qualitative independence graphs and extremal set partition theory, Ph.D. thesis, University of Ottawa Meagher K, Moura L, Zekaoui L (2007) Mixed covering arrays on graphs. J Comb Des 15:393–404 Moura L, Stardom J, Stevens B, Williams A (2003) Covering arrays with mixed alphabet sizes. J Comb Des 11:413–432 Raaphorst S (2013) Variable strength covering arrays, Ph.D. thesis, University of Ottawa Wang J, Wu CFJ (1992) Nearly orthogonal arrays with mixed levels and small runs. Technometrics 34(4):409–422 Wu CFJ, Hamada MS (2009) Experiments: planning, analysis and optimization, 2nd edn. Wiley, New Jersey Xu H (2002) An algorithm for constructing orthogonal and nearly-orthogonal arrays with mixed levels and small runs. Technometrics 44:356–368 Xu H (2003) Minimum moment aberration for nonregular designs and supersaturated designs. Stat Sin 13:691–708