License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/DagSemProc.09281.3
URN: urn:nbn:de:0030-drops-22405
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2009/2240/
Go to the corresponding Portal

Colbourn, Charles J. ; McClary, Daniel W.

Locating and Detecting Arrays for Interaction Faults

pdf-format:
09281.ColbournCharles.Paper.2240.pdf (0.3 MB)

Abstract

The identification of interaction faults in component-based systems has focused on indicating the presence of faults, rather than their location and magnitude. While this is a valuable step in screening a system for interaction faults prior to its release, it provides little information to assist in the correction of such faults. Consequently tests to reveal the location of interaction faults are of interest. The problem of nonadaptive location of interaction faults is formalized under the hypothesis that the system contains (at most) some number d of faults, each involving (at most) some number t of interacting factors. Restrictions on the number and size of the putative faults lead to numerous variants of the basic problem. The relationships between this class of problems and interaction testing using covering arrays to indicate the presence of faults, designed experiments to measure and model faults, and combinatorial group testing to locate faults in a more general testing scenario, are all examined. While each has some definite similarities with the fault location problems for component-based systems, each has some striking differences as well. In this paper, we formulate the combinatorial problems for locating and detecting arrays to undertake interaction fault location. Necessary conditions for existence are established, and using a close connection to covering arrays, asymptotic bounds on the size of minimal locating and detecting arrays are established.

A final version of this paper appears in J Comb Optim (2008) 15: 17-48.

BibTeX - Entry

@InProceedings{colbourn_et_al:DagSemProc.09281.3,
  author =	{Colbourn, Charles J. and McClary, Daniel W.},
  title =	{{Locating and Detecting Arrays for Interaction Faults}},
  booktitle =	{Search Methodologies},
  pages =	{1--34},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{9281},
  editor =	{Rudolf Ahlswede and Ferdinando Cicalese and Ugo Vaccaro},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2009/2240},
  URN =		{urn:nbn:de:0030-drops-22405},
  doi =		{10.4230/DagSemProc.09281.3},
  annote =	{Keywords: Covering array, Orthogonal array, Factorial design, Cover-free family, Disjunct matrix, Locating array, Detecting array}
}

Keywords: Covering array, Orthogonal array, Factorial design, Cover-free family, Disjunct matrix, Locating array, Detecting array
Collection: 09281 - Search Methodologies
Issue Date: 2009
Date of publication: 10.11.2009

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI