Full Record

New Search | Similar Records

Author
Title Error Locating Arrays, Adaptive Software Testing, and Combinatorial Group Testing
URL
Publication Date
Date Accessioned
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 define 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…

.