In this paper, we define error locating arrays (ELAs), which can be used to locate faulty interactions between parameters or components in a software system. We give constructions of ELAs based on covering arrays. Under certain assumptions on the structure of the faulty interactions, we design and analyse efficient algorithms that locate errors. Under the assumption of known "safe values", our algorithm performs a number of tests that is polynomial in logk and d, where k is the number of parameters in the system and d is an upper bound on the number of faulty pairwise interactions. For the binary alphabet case, we provide an algorithm that does not require safe values and runs in expected polynomial time in logk whenever d∈ ∈O(loglogk).

Additional Metadata
Persistent URL dx.doi.org/10.1007/978-3-540-78773-0_44
Series Lecture Notes in Computer Science
Citation
Martínez, C. (Conrado), Moura, L. (Lucia), Panario, D, & Stevens, B. (2008). Algorithms to locate errors using covering arrays. In Lecture Notes in Computer Science. doi:10.1007/978-3-540-78773-0_44