Finding minimum locating arrays using a CSP solver

DOI10.3233/FI-2020-1929MaRDI QIDQ5134287zbMATH OpenFDO

Authors Tatsuya Konishi, Hideharu Kojima, Hiroyuki Nakagawa, Tatsuhiro Tsuchiya

Publication date 16 November 2020

Published in Fundamenta Informaticae (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1904.07480

zbMATH Keywords

combinatorial interaction testingconstraint satisfaction problemlocating arraysoftware testing

Mathematics Subject Classification ID

Combinatorial aspects of packing and covering (05B40) Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) (68N30) Computational aspects of satisfiability (68R07) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Abstract: Combinatorial interaction testing is an efficient software testing strategy. If all interactions among test parameters or factors needed to be covered, the size of a required test suite would be prohibitively large. In contrast, this strategy only requires covering $t$-wise interactions where $t$ is typically very small. As a result, it becomes possible to significantly reduce test suite size. Locating arrays aim to enhance the ability of combinatorial interaction testing. In particular, $(overline1,t)$-locating arrays can not only execute all $t$-way interactions but also identify, if any, which of the interactions causes a failure. In spite of this useful property, there is only limited research either on how to generate locating arrays or on their minimum sizes. In this paper, we propose an approach to generating minimum locating arrays. In the approach, the problem of finding a locating array consisting of $N$ tests is represented as a Constraint Satisfaction Problem (CSP) instance, which is in turn solved by a modern CSP solver. The results of using the proposed approach reveal many $(overline1,t)$-locating arrays that are smallest known so far. In addition, some of these arrays are proved to be minimum.

Recommendations

• Optimality and constructions of locating arrays
• Arrays for combinatorial interaction testing: a review on constructive approaches
• Optimal locating arrays for at most two faults
• On a combinatorial framework for fault characterization
• Locating one pairwise interaction: three recursive constructions

Cited in

(2)

• A feature commonality-based search strategy to find high t-wise covering solutions in feature models
• Mixed-level covering, locating, and detecting arrays via cyclotomy

This page was built for publication: Finding minimum locating arrays using a CSP solver

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5134287)