Full Record

Author | Chodoriwsky, Jacob N. |

Title | Error Locating Arrays, Adaptive Software Testing, and Combinatorial Group Testing |

URL | http://hdl.handle.net/10393/23083 |

Publication Date | 2012 |

Date Accessioned | 2012-07-17 08:04:05 |

University/Publisher | University of Ottawa |

Abstract | Combinatorial Group Testing (CGT) is a process of identifying faulty interactions (“errors”) within a particular set of items. Error Locating Arrays (ELAs) are combinatorial designs that can be built from Covering Arrays (CAs) to not only cover all errors in a system (each involving up to a certain number of items), but to locate and identify the errors as well. In this thesis, we survey known results for CGT, as well as CAs, ELAs, and some other types of related arrays. More importantly, we give several new results. First, we give a new algorithm that can be used to test a system in which each component (factor) has two options (values), and at most two errors are present. We show that, for systems with at most two errors, our algorithm improves upon a related algorithm by Mart´ınez et al. in terms of both robustness and efficiency. Second, we give the first adaptive CGT algorithm that can identify, among a given set of k items, all faulty interactions involving up to three items. We then compare it, performance-wise, to current-best nonadaptive method that can identify faulty interactions involving up to three items. We also give the first adaptive ELA-building algorithm that can identify all faulty interactions involving up to three items when safe values are known. Both of our new algorithms are generalizations of ones previously given by Mart´ınez et al. for identifying all faulty interactions involving up to two items. |

Subjects/Keywords | combinatorial group testing; CGT; error locating arrays; ELA; covering arrays; CA; adaptive; algorithm; testing problem; software testing; CAFE; forbidden edges; forbidden hyperedges; hypergraph testing; group testing for complexes; safe values |

Language | en |

Country of Publication | ca |

Record ID | handle:10393/23083 |

Repository | ottawa |

Date Indexed | 2018-01-03 |

Issued Date | 2012-01-01 00:00:00 |

Sample Search Hits | Sample Images

…combinatorial designs which cover all t-way
interactions. Such designs are arrays whose rows represent corresponding tests.
1.2
*Covering* Arrays
A *covering* array (CA) is a type of combinatorial design which, given a parameter t,
covers each t-way…

…interaction at least once. More formally, we deﬁne a *covering* array
as follows.
Definition 1.2.1 A *covering* array C is an N × k array with entries from a galphabet, such that each possible t-way interaction I of a testing problem T P (k, g)
occurs as…

…which a CA(N ; t, k, g) can exist.
Definition 1.2.2 The minimum integer N for which a CA(N ; t, k, g) exists is called
the *covering* array number, which we denote by CAN (t, k, g). A *covering* array
of size N = CAN (t, k…

…g) is called optimal.
Regrettably, not much is known about the exact values of *covering* array numbers.
However, some general bounds can be easily inferred. First, for any A ⊆ [1, k] such
that |A| = t, a CA(N ; t, k, g) must…

…include each of the g t possible t-subtests that are
indexed by the set A at least once. Therefore,
g t ≤ CAN (t, k, g).
Likewise, any *covering* array of strength t also covers all (t − 1)-subtests, and
any *covering* array with alphabet g…

…clearly covers all (g − 1)t subtests created from
a (g − 1)-alphabet. Furthermore, we can create a *covering* array on k − 1 factors by
simply removing one column. Hence, we get the following inequalities.
CAN (t − 1, k, g)…

…CAN (t, k, g)
CAN (t, k − 1, g) ≤ CAN (t, k, g)
CAN (t, k, g − 1) ≤ CAN (t, k, g)
Fortunately, the exact *covering* array number is known for pairwise interactions
and binary (g = 2) alphabets…

…x5B;20] has been applied in the context of *covering* arrays [12] to obtain the
following result.
Theorem 1.2.6 [20, 12] Let g > 2 be a positive integer. Then, as k → ∞, we have
CAN (2, k, g) ∼
g
log k.
2
Two more…