Locating one pairwise interaction: Three recursive constructions

In a complex component-based system, choices (levels) for components (factors) may interact tocause faults in the system behaviour. When faults may be caused by interactions among few factorsat specific levels, covering arrays provide a combinatorial test suite for discovering the presence offaults. While well studied, covering arrays do not enable one to determine the specific levels of factorscausing the faults; locating arrays ensure that the results from test suite execution suffice to determinethe precise levels and factors causing faults, when the number of such causes is small. Constructionsfor locating arrays are at present limited to heuristic computational methods and quite specific directconstructions. In this paper three recursive constructions are developed for locating arrays to locateone pairwise interaction causing a fault.

PDF

___

A. N. Aldaco, C. J. Colbourn, V. R. Syrotiuk, Locating arrays: A new experimental design for screening complex engineered systems, SIGOPS Oper. Syst. Rev. 49(1) (2015) 31–40.
M. Chateauneuf, D. L. Kreher, On the state of strength-three covering arrays, J. Combin. Des. 10(4) (2002) 217–238.
M. B. Cohen, C. J. Colbourn, A. C. H. Ling, Constructing strength three covering arrays with augmented annealing, Discrete Math. 308(13) (2008) 2709–2722.
C. J. Colbourn, Covering arrays and hash families, Information Security and Related Combinatorics, NATO Peace and Information Security, IOS Press (2011), 99–136.
C. J. Colbourn, S. S. Martirosyan, G. L. Mullen, D. Shasha, G. B. Sherwood, J. L. Yucas, Products of mixed covering arrays of strength two, J. Combin. Des. 14(2) (2006) 124–138.
C. J. Colbourn, S. S. Martirosyan, T. van Trung, R. A. Walker II, Roux-type constructions for covering arrays of strengths three and four, Des. Codes Cryptogr. 41(1) (2006) 33–57.
C. J. Colbourn, D. W. McClary, Locating and detecting arrays for interaction faults, J. Comb. Optim. 15(1) (2008) 17–48.
A. Hartman, Software and hardware testing using combinatorial covering suites, Graph Theory, Combinatorics and Algorithms, Springer, 2005, 237–266.
C. Martínez, L. Moura, D. Panario, B. Stevens, Locating errors using ELAs, covering arrays, and adaptive testing algorithms, SIAM J. Discrete Math. 23(4) (2009/10) 1776–1799.
G. Roux, k-Propriétés dans les tableaux de n colonnes: cas particulier de la k-surjectivité et de la k-permutivité, Ph.D. Dissertation, University of Paris 6, 1987.
C. Shi, Y. Tang, J. Yin, Optimal locating arrays for at most two faults, Sci. China Math. 55(1) (2012) 197–206.
Y. Tang, C. J. Colbourn, J. Yin, Optimality and constructions of locating arrays, J. Stat. Theory Pract. 6(1) (2012) 20–29.
J. Yin, Cyclic difference packing and covering arrays, Des. Codes Cryptogr. 37(2) (2005) 281–292.