Algorithms to locate errors using covering arrays
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).
|Series||Lecture Notes in Computer Science|
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