NDLI: Locating Errors Using ELAs, Covering Arrays, and Adaptive Testing Algorithms

Content Provider	Society for Industrial and Applied Mathematics (SIAM)
Author	Martnez, Conrado Moura, Lucia Stevens, Brett Panario, Daniel
Copyright Year	2009
Abstract	In this paper, we define and study error locating arrays (ELAs), which can be used in software testing for locating faulty interactions among parameters or components in a system. We give constructions of ELAs for arbitrary strength t, based on covering arrays. We show that the number of tests given by ELAs grows as $O(\log k)$, where k is the number of parameters/components in the system, assuming other quantities (the number g of values per parameter, the strength t of faulty interactions, and the number d of faulty interactions) are bounded by a constant. We then give a series of results for the case of pairwise interactions ($t=2$). We study the computational complexity of deciding whether a graph describing the faulty pairwise interactions is locatable. We characterize the locatable graphs for the binary case ($g=2$). We design and analyze efficient algorithms that locate errors under certain assumptions on the structure of the faulty pairwise interactions. Under the assumption of known safe values, our algorithm performs a number of tests that is polynomial in $\log k$ 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 $\log k$ whenever $d\in O(\log\log k)$.
Starting Page	1776
Ending Page	1799
Page Count	24
File Format	PDF
ISSN	08954801
DOI	10.1137/080730706
e-ISSN	10957146
Journal	SIAM Journal on Discrete Mathematics (SJDMEC)
Issue Number	4
Volume Number	23
Language	English
Publisher	Society for Industrial and Applied Mathematics
Publisher Date	2009-12-04
Access Restriction	Subscribed
Subject Keyword	Fault detection; testing algorithms detecting arrays software testing group testing component interaction testing Other designs, configurations locating arrays combinatorial designs covering arrays error locating arrays Applications of design theory
Content Type	Text
Resource Type	Article
Subject	Mathematics

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Constrained locating arrays for combinatorial interaction testing

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

Finding minimum locating arrays using a CSP solver

Locating and detecting arrays for interaction faults.

Sole error locating array and approximate error locating array

A polynomial construction of perfect sequence covering arrays

Using simulated annealing for locating array construction

Prioritizing Variable-Strength Covering Array

Perfect sequence covering arrays

Locating Errors Using ELAs, Covering Arrays, and Adaptive Testing Algorithms

Similar Documents

Constrained locating arrays for combinatorial interaction testing

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

Finding minimum locating arrays using a CSP solver

Locating and detecting arrays for interaction faults.

Sole error locating array and approximate error locating array

A polynomial construction of perfect sequence covering arrays

Using simulated annealing for locating array construction

Prioritizing Variable-Strength Covering Array

Perfect sequence covering arrays

Locating Errors Using ELAs, Covering Arrays, and Adaptive Testing Algorithms