Conformance testing in the presence of multiple faults

Viraj Kumar, Mahesh Viswanathan

Research output: Contribution to conferencePaper

Abstract

Conformance testing is the problem of determining if a black-box implementation I is equivalent to a specification S, where both are modeled as finite state Mealy machines. The problem involves constructing a checking sequence based on the specification, which is a sequence of inputs that detects all faulty machines. Traditionally, conformance testing algorithms have assumed that the number of states in the implementation does not exceed that in the specification. This is because it is known that, in the absence of this assumption, the length of the checking sequence needs to be at least exponential in the number of extra states in the implementation. However, this has limited the applicability of these techniques in practice where the implementation typically has many more states than the specification. In this paper we relax the constraints on the size of the implementation and investigate the existence of polynomial length checking sequences for implementations with extra states, under the promise that they either have multiple faults or no faults at all. We present randomized algorithms to construct checking sequences that catch faulty implementations with at most Δ extra states, having at least r faults (where Δ and r are parameters to the algorithm), and pass all correct implementations. We demonstrate the near optimality of our algorithms by presenting lower bounds for this problem. One of the main technical lemmas used in our proof is an estimate of the probability that a random walk on directed graphs will reach a large target set. We believe that this lemma will be of independent interest in the context of verifying safety properties.

Original languageEnglish (US)
Pages1136-1145
Number of pages10
StatePublished - Jul 1 2005
EventSixteenth Annual ACM-SIAM Symposium on Discrete Algorithms - Vancouver, BC, United States
Duration: Jan 23 2005Jan 25 2005

Other

OtherSixteenth Annual ACM-SIAM Symposium on Discrete Algorithms
CountryUnited States
CityVancouver, BC
Period1/23/051/25/05

Fingerprint

Conformance Testing
Fault
Specifications
Testing
Specification
Directed graphs
Finite automata
Lemma
Polynomials
State Machine
Randomized Algorithms
Black Box
Directed Graph
Random walk
Optimality
Exceed
Safety
Lower bound
Target
Polynomial

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

Cite this

Kumar, V., & Viswanathan, M. (2005). Conformance testing in the presence of multiple faults. 1136-1145. Paper presented at Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, Vancouver, BC, United States.

Conformance testing in the presence of multiple faults. / Kumar, Viraj; Viswanathan, Mahesh.

2005. 1136-1145 Paper presented at Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, Vancouver, BC, United States.

Research output: Contribution to conferencePaper

Kumar, V & Viswanathan, M 2005, 'Conformance testing in the presence of multiple faults', Paper presented at Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, Vancouver, BC, United States, 1/23/05 - 1/25/05 pp. 1136-1145.
Kumar V, Viswanathan M. Conformance testing in the presence of multiple faults. 2005. Paper presented at Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, Vancouver, BC, United States.
Kumar, Viraj ; Viswanathan, Mahesh. / Conformance testing in the presence of multiple faults. Paper presented at Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, Vancouver, BC, United States.10 p.
@conference{04560ab41ddd42ed9d2ed96e05425bae,
title = "Conformance testing in the presence of multiple faults",
abstract = "Conformance testing is the problem of determining if a black-box implementation I is equivalent to a specification S, where both are modeled as finite state Mealy machines. The problem involves constructing a checking sequence based on the specification, which is a sequence of inputs that detects all faulty machines. Traditionally, conformance testing algorithms have assumed that the number of states in the implementation does not exceed that in the specification. This is because it is known that, in the absence of this assumption, the length of the checking sequence needs to be at least exponential in the number of extra states in the implementation. However, this has limited the applicability of these techniques in practice where the implementation typically has many more states than the specification. In this paper we relax the constraints on the size of the implementation and investigate the existence of polynomial length checking sequences for implementations with extra states, under the promise that they either have multiple faults or no faults at all. We present randomized algorithms to construct checking sequences that catch faulty implementations with at most Δ extra states, having at least r faults (where Δ and r are parameters to the algorithm), and pass all correct implementations. We demonstrate the near optimality of our algorithms by presenting lower bounds for this problem. One of the main technical lemmas used in our proof is an estimate of the probability that a random walk on directed graphs will reach a large target set. We believe that this lemma will be of independent interest in the context of verifying safety properties.",
author = "Viraj Kumar and Mahesh Viswanathan",
year = "2005",
month = "7",
day = "1",
language = "English (US)",
pages = "1136--1145",
note = "Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms ; Conference date: 23-01-2005 Through 25-01-2005",

}

TY - CONF

T1 - Conformance testing in the presence of multiple faults

AU - Kumar, Viraj

AU - Viswanathan, Mahesh

PY - 2005/7/1

Y1 - 2005/7/1

N2 - Conformance testing is the problem of determining if a black-box implementation I is equivalent to a specification S, where both are modeled as finite state Mealy machines. The problem involves constructing a checking sequence based on the specification, which is a sequence of inputs that detects all faulty machines. Traditionally, conformance testing algorithms have assumed that the number of states in the implementation does not exceed that in the specification. This is because it is known that, in the absence of this assumption, the length of the checking sequence needs to be at least exponential in the number of extra states in the implementation. However, this has limited the applicability of these techniques in practice where the implementation typically has many more states than the specification. In this paper we relax the constraints on the size of the implementation and investigate the existence of polynomial length checking sequences for implementations with extra states, under the promise that they either have multiple faults or no faults at all. We present randomized algorithms to construct checking sequences that catch faulty implementations with at most Δ extra states, having at least r faults (where Δ and r are parameters to the algorithm), and pass all correct implementations. We demonstrate the near optimality of our algorithms by presenting lower bounds for this problem. One of the main technical lemmas used in our proof is an estimate of the probability that a random walk on directed graphs will reach a large target set. We believe that this lemma will be of independent interest in the context of verifying safety properties.

AB - Conformance testing is the problem of determining if a black-box implementation I is equivalent to a specification S, where both are modeled as finite state Mealy machines. The problem involves constructing a checking sequence based on the specification, which is a sequence of inputs that detects all faulty machines. Traditionally, conformance testing algorithms have assumed that the number of states in the implementation does not exceed that in the specification. This is because it is known that, in the absence of this assumption, the length of the checking sequence needs to be at least exponential in the number of extra states in the implementation. However, this has limited the applicability of these techniques in practice where the implementation typically has many more states than the specification. In this paper we relax the constraints on the size of the implementation and investigate the existence of polynomial length checking sequences for implementations with extra states, under the promise that they either have multiple faults or no faults at all. We present randomized algorithms to construct checking sequences that catch faulty implementations with at most Δ extra states, having at least r faults (where Δ and r are parameters to the algorithm), and pass all correct implementations. We demonstrate the near optimality of our algorithms by presenting lower bounds for this problem. One of the main technical lemmas used in our proof is an estimate of the probability that a random walk on directed graphs will reach a large target set. We believe that this lemma will be of independent interest in the context of verifying safety properties.

UR - http://www.scopus.com/inward/record.url?scp=20744452761&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=20744452761&partnerID=8YFLogxK

M3 - Paper

AN - SCOPUS:20744452761

SP - 1136

EP - 1145

ER -