Browse Prior Art Database

A FORMAL NOTION OF PROGRAM-BASED TEXT DATA ADEOUACY

IP.com Disclosure Number: IPCOM000128214D
Original Publication Date: 1982-Dec-31
Included in the Prior Art Database: 2005-Sep-15
Document File: 12 page(s) / 38K

Publishing Venue

Software Patent Institute

Related People

MARTIN D. DAVIS: AUTHOR [+4]

Abstract

We propose a definition of the notion of adequacy of test data and discuss justification, difficulties, and properties of the notion. It is not the purpose of this paper to suggest a definite practically applicable criterion of test data adequacy. Rather we present a theoretical analysis which, it is believed, gives insight into such questions as: a) For a given program, what points must belong to a test set in order that it may be deemed adequate ? b) For a given program, how marry points must belong to an adequate test set ? c) 'What kind of approximation to "correctness" can be provided by the knowledge that a program has been "adequately" tested ? We believe, in general, that an adequacy criterion should be invoked only after the. test data fails to expose errors. Clearly, as long as there is an element of the test set on which the program does not agree with the specification, we know that the test data is still doing its job and that testing (and subsequent debugging) must continue. (In this paper, we ignore the question of whether and how we can tell whether a program agrees with a specification at a particular point. However, see [15], [3].) Once the program does agree with the specification on all elements of a set of test data, we must decide whether the testing phase can end, and hence we will need to invoke some kind of adequacy criterion.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 11% of the total text.

Page 1 of 12

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

A FORMAL NOTION OF PROGRAM-BASED TEXT DATA ADEOUACY

BY MARTIN D. DAVIS ELAINE J. WEYUKER

TECHNICAL RE-PORT 450 Oc'' i'78Z'.R .19 8 2 '"his research was supported in hart, by the National Science Foundation under grants MCS-80-02?38 and MCS-82-01167. A FORMAL NOTION OF PROGRAM-BASED TEST DATA ADEQUACY Martin D. Davis and Elaine J. Weyuker

Introduction

We propose a definition of the notion of adequacy of test data and discuss justification, difficulties, and properties of the notion. It is not the purpose of this paper to suggest a definite practically applicable criterion of test data adequacy. Rather we present a theoretical analysis which, it is believed, gives insight into such questions as: a) For a given program, what points must belong to a test set in order that it may be deemed adequate ? b) For a given program, how marry points must belong to an adequate test set ? c) 'What kind of approximation to "correctness" can be provided by the knowledge that a program has been "adequately" tested ? We believe, in general, that an adequacy criterion should be invoked only after the. test data fails to expose errors. Clearly, as long as there is an element of the test set on which the program does not agree with the specification, we know that the test data is still doing its job and that testing (and subsequent debugging) must continue. (In this paper, we ignore the question of whether and how we can tell whether a program agrees with a specification at a particular point. However, see [15], [3].) Once the program does agree with the specification on all elements of a set of test data, we must decide whether the testing phase can end, and hence we will need to invoke some kind of adequacy criterion.

This research was supported in part by the National Science Foundation under ;rants '.~'.CS-80- 02'38 and '.~ICS-82-O1I57. 2_ For a given program P, ue write P(c)=b to mean that the program P on input c halts with output b. We write P Q (P is equivalent to Q), where P and Q are programs, to mean that P(c) = Q(c) for every input c. In particular this implies that for each c, P(c) is defined if and only if Q(c) is defined. Our analysis will deal only with adequacy criteria which are entirely prograw-based in the sense that they depend completely on the program as written. Since no set of test data can distinguish two programs with identical input-output behavior, the broadest conceivable program-based adequacy criterion would be to regard a set of test data as adequate for a given program if the input-output behavior of the program on the test set is different from that of all programs that are inequivalent to it. However, it is easy to see that no set of test data can hope to be adequate in this sense unless it contains every point in the domain of the program. For, if the point c on which program P is defined is omitted from a test set, then we can easily construct a new pr...