Conformance testing of Boolean programs with multiple faults

Pavithra Prabhakar, Mahesh Viswanathan

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Conformance testing is the problem of constructing a complete test suite of inputs based on a specification S such that any implementation I (of size less than a given bound) that is not equivalent to S gives a different output on the test suite than S. Typically I and S are assumed to be some type of finite automata. In this paper we consider the problem of constructing test suites for boolean programs (or more precisely modular visibly pushdown automata) that are guaranteed to catch all erroneous implementations that have at least R faults, and pass all correct implementations; if the incorrect implementation has fewer than R faults then the test suite may or may not detect it. We present a randomized algorithm for the construction of such test suites, and prove the near optimality of our test suites by proving lower bounds on the size of test suites.

Original languageEnglish (US)
Title of host publicationFormal Techniques for Distributed Systems - Joint 14th IFIP WG 6.1 International Conference, FMOODS 2012 and 32nd IFIP WG 6.1 International Conference, FORTE 2012, Proceedings
Pages101-117
Number of pages17
DOIs
StatePublished - 2012
Event14th IFIP International Conference on Formal Methods for Open Object-Based Distributed Systems, FMOODS 2012 and the 32nd IFIP International Conference on Formal Techniques for Networked and Distributed Systems, FORTE 2012 - Stockholm, Sweden
Duration: Jun 13 2012Jun 16 2012

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume7273 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other14th IFIP International Conference on Formal Methods for Open Object-Based Distributed Systems, FMOODS 2012 and the 32nd IFIP International Conference on Formal Techniques for Networked and Distributed Systems, FORTE 2012
CountrySweden
CityStockholm
Period6/13/126/16/12

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Conformance testing of Boolean programs with multiple faults'. Together they form a unique fingerprint.

Cite this